2025-11-14T20:13:11.521057

Minimax Optimal Kernel Two-Sample Tests with Random Features

Mukherjee, Sriperumbudur
Reproducing Kernel Hilbert Space (RKHS) embedding of probability distributions has proved to be an effective approach, via MMD (maximum mean discrepancy), for nonparametric hypothesis testing problems involving distributions defined over general (non-Euclidean) domains. While a substantial amount of work has been done on this topic, only recently have minimax optimal two-sample tests been constructed that incorporate, unlike MMD, both the mean element and a regularized version of the covariance operator. However, as with most kernel algorithms, the optimal test scales cubically in the sample size, limiting its applicability. In this paper, we propose a spectral-regularized two-sample test based on random Fourier feature (RFF) approximation and investigate the trade-offs between statistical optimality and computational efficiency. We show the proposed test to be minimax optimal if the approximation order of RFF (which depends on the smoothness of the likelihood ratio and the decay rate of the eigenvalues of the integral operator) is sufficiently large. We develop a practically implementable permutation-based version of the proposed test with a data-adaptive strategy for selecting the regularization parameter. Finally, through numerical experiments on simulated and benchmark datasets, we demonstrate that the proposed RFF-based test is computationally efficient and performs almost similarly (with a small drop in power) to the exact test.
academic

मिनिमैक्स इष्टतम कर्नेल दो-नमूना परीक्षण यादृच्छिक विशेषताओं के साथ

मूल जानकारी

  • पेपर ID: 2502.20755
  • शीर्षक: Minimax Optimal Kernel Two-Sample Tests with Random Features
  • लेखक: Soumya Mukherjee, Bharath K. Sriperumbudur (पेंसिल्वेनिया स्टेट विश्वविद्यालय)
  • वर्गीकरण: math.ST cs.LG stat.ML stat.TH
  • प्रकाशन तिथि: 17 अक्टूबर, 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2502.20755

सारांश

यह पेपर पुनरुत्पादक कर्नेल हिल्बर्ट स्पेस (RKHS) एम्बेडिंग पर आधारित दो-नमूना परीक्षण समस्या के लिए यादृच्छिक फूरियर विशेषताओं (RFF) सन्निकटन पर आधारित एक वर्णक्रमीय नियमितकृत दो-नमूना परीक्षण विधि प्रस्तावित करता है। यह विधि सांख्यिकीय इष्टतमता को बनाए रखते हुए कम्प्यूटेशनल जटिलता को घन स्तर से लगभग रैखिक तक कम करती है, और पूरी तरह से डेटा-संचालित व्यावहारिक कार्यान्वयन संस्करण प्रदान करती है।

अनुसंधान पृष्ठभूमि और प्रेरणा

मुख्य समस्या

दो-नमूना परीक्षण सांख्यिकी में एक मौलिक समस्या है, जिसका उद्देश्य दो यादृच्छिक नमूनों का विश्लेषण करके यह निर्धारित करना है कि क्या उनके स्रोत की संभाव्यता वितरण समान हैं। पारंपरिक पैरामीट्रिक और गैर-पैरामीट्रिक परीक्षण विधियों को उच्च-आयामी डेटा या गैर-यूक्लिडियन डोमेन पर वितरण को संभालने में महत्वपूर्ण सीमाएं का सामना करना पड़ता है।

मौजूदा विधियों की सीमाएं

  1. MMD परीक्षण की उप-इष्टतमता: यद्यपि अधिकतम माध्य विसंगति (MMD) परीक्षण व्यापक रूप से लागू होता है, लेकिन इसमें मिनिमैक्स इष्टतमता का अभाव है, यह केवल माध्य एम्बेडिंग पर विचार करता है और सहप्रसरण ऑपरेटर जानकारी को नजरअंदाज करता है
  2. वर्णक्रमीय नियमितकरण विधियों की कम्प्यूटेशनल बाधा: हाल ही में प्रस्तावित वर्णक्रमीय नियमितकृत MMD परीक्षण ने मिनिमैक्स इष्टतमता प्राप्त की है, लेकिन कम्प्यूटेशनल जटिलता O(n³) है, जो बड़े पैमाने के डेटा पर इसके अनुप्रयोग को सीमित करता है
  3. पैरामीटर चयन में कठिनाई: नियमितकरण पैरामीटर का चयन अज्ञात वितरण विशेषताओं पर निर्भर करता है, डेटा-संचालित अनुकूली रणनीति का अभाव है

अनुसंधान प्रेरणा

यह पेपर सांख्यिकीय इष्टतमता को बनाए रखते हुए यादृच्छिक फूरियर विशेषता सन्निकटन तकनीक के माध्यम से वर्णक्रमीय नियमितकृत दो-नमूना परीक्षण की कम्प्यूटेशनल दक्षता में काफी सुधार करने का लक्ष्य रखता है, और व्यावहारिक रूप से उपयोगी अनुकूली संस्करण विकसित करता है।

मुख्य योगदान

  1. कम्प्यूटेशनल रूप से कुशल और सांख्यिकीय रूप से इष्टतम परीक्षण: RFF पर आधारित वर्णक्रमीय नियमितकृत दो-नमूना परीक्षण प्रस्तावित करता है, जो कम्प्यूटेशनल जटिलता को O(n³) से O(nl²+nld) तक कम करता है, साथ ही पर्याप्त शर्तों के तहत मिनिमैक्स इष्टतमता को बनाए रखता है
  2. सैद्धांतिक गारंटी: RFF सन्निकटन क्रम और सांख्यिकीय इष्टतमता के बीच सैद्धांतिक संबंध स्थापित करता है, यह साबित करता है कि जब विशेषता संख्या l विशिष्ट शर्तों को पूरा करती है तो परीक्षण की मिनिमैक्स इष्टतमता
  3. व्यावहारिक अनुकूली संस्करण: क्रमचय परीक्षण पर आधारित पूरी तरह से डेटा-संचालित संस्करण विकसित करता है, जिसमें नियमितकरण पैरामीटर और कर्नेल फ़ंक्शन की अनुकूली चयन रणनीति शामिल है
  4. व्यापक प्रायोगिक सत्यापन: सिंथेटिक डेटा और बेंचमार्क डेटासेट के माध्यम से विधि की प्रभावशीलता को सत्यापित करता है, कम्प्यूटेशनल दक्षता और सांख्यिकीय प्रदर्शन का अच्छा संतुलन प्रदर्शित करता है

विधि विवरण

कार्य परिभाषा

वितरण P और Q से स्वतंत्र नमूने X₁:N और Y₁:M दिए गए, परिकल्पना H₀: P = Q बनाम H₁: P ≠ Q का परीक्षण करें।

मुख्य विधि आर्किटेक्चर

1. वर्णक्रमीय नियमितकरण ढांचा

कर्नेल फ़ंक्शन K के लिए, वर्णक्रमीय नियमितकृत विसंगति को परिभाषित करें:

ηλ(P,Q) = 4⟨Tgλ(T)u, u⟩_{L²(R)}

जहां T समाकल ऑपरेटर है, u = dP/dR - 1 संभावना अनुपात विचलन है, gλ नियमितकरण फ़ंक्शन है।

2. यादृच्छिक फूरियर विशेषता सन्निकटन

K(x,y) = ∫φ(x,θ)φ(y,θ)dΞ(θ) रूप के कर्नेल फ़ंक्शन के लिए, सन्निकटन कर्नेल का निर्माण करें:

Kₗ(x,y) = (1/l)∑ᵢ₌₁ˡ φ(x,θᵢ)φ(y,θᵢ)

3. सन्निकटन परीक्षण सांख्यिकी

सन्निकटन कर्नेल Kₗ के आधार पर परीक्षण सांख्यिकी का निर्माण करें:

η̂λ,l = (1/[n(n-1)m(m-1)]) ∑ᵢ≠ⱼ ∑ᵢ'≠ⱼ' t(Xᵢ,Xⱼ,Yᵢ',Yⱼ')

जहां t फ़ंक्शन नियमितकृत सहप्रसरण ऑपरेटर के वर्गमूल को शामिल करता है।

तकनीकी नवाचार बिंदु

1. सैद्धांतिक नवाचार

  • मिनिमैक्स इष्टतमता शर्तें: RFF विशेषता संख्या l और सांख्यिकीय इष्टतमता के बीच सटीक संबंध स्थापित करता है
  • बहुपद और घातीय क्षय स्थितियां: समाकल ऑपरेटर eigenvalues के विभिन्न क्षय पैटर्न का अलग से विश्लेषण करता है
  • गैर-स्पर्शोन्मुख विश्लेषण: सीमित नमूने के तहत प्रदर्शन गारंटी प्रदान करता है

2. एल्गोरिथ्म नवाचार

  • अनुकूली नियमितकरण: संयुक्त परीक्षण के माध्यम से नियमितकरण पैरामीटर की डेटा-संचालित चयन को लागू करता है
  • कर्नेल फ़ंक्शन अनुकूलन: बहु-कर्नेल फ़ंक्शन की अनुकूली चयन तक विस्तारित करता है
  • क्रमचय परीक्षण कार्यान्वयन: पूरी तरह से डेटा-संचालित महत्वपूर्ण मान गणना प्रदान करता है

3. कम्प्यूटेशनल नवाचार

  • कुशल एल्गोरिथ्म: विस्तृत कम्प्यूटेशनल जटिलता विश्लेषण और अनुकूलित कार्यान्वयन
  • समानांतरकरण: क्रमचय परीक्षण की प्राकृतिक समानांतरकरण विशेषता

प्रायोगिक सेटअप

डेटासेट

  1. सिंथेटिक डेटा:
    • गॉसियन माध्य विस्थापन: P = N(0,I), Q = N(μ,I)
    • गॉसियन स्केल विस्थापन: P = N(0,I), Q = N(0,σ²I)
    • कॉची माध्यिका विस्थापन: विभिन्न माध्यिका के साथ कॉची वितरण
  2. वास्तविक डेटा:
    • MNIST डेटासेट: 7×7 पिक्सल हस्तलिखित अंक छवियां, आयाम d=49
    • विभिन्न अंक उप-समुच्चय के वितरण अंतर का पता लगाना

मूल्यांकन मेट्रिक्स

  • सांख्यिकीय शक्ति (Power): वैकल्पिक परिकल्पना के तहत मूल परिकल्पना को सही ढंग से अस्वीकार करने की संभावना
  • कम्प्यूटेशनल समय: एल्गोरिथ्म रन टाइम की तुलना
  • प्रथम प्रकार की त्रुटि: α=0.05 स्तर पर नियंत्रण

तुलना विधियां

  • सटीक अनुकूली परीक्षण: पूर्ण कर्नेल मैट्रिक्स पर आधारित वर्णक्रमीय नियमितकृत परीक्षण
  • विभिन्न RFF विशेषता संख्याएं: l ∈ {1,3,5,7,9,15,20} की प्रदर्शन तुलना

कार्यान्वयन विवरण

  • नियमितकरण फ़ंक्शन: Showalter regularizer gλ(x) = (1-e^(-x/λ))/x
  • कर्नेल फ़ंक्शन: गॉसियन और लाप्लास कर्नेल, बैंडविड्थ अनुकूली चयन
  • क्रमचय संख्या: RFF संस्करण B=550-800, सटीक संस्करण B'=250-450

प्रायोगिक परिणाम

मुख्य परिणाम

1. सांख्यिकीय प्रदर्शन

  • गॉसियन माध्य विस्थापन: RFF विशेषता संख्या l≥7 होने पर, शक्ति सटीक विधि के करीब है
  • गॉसियन स्केल विस्थापन: l≥5 होने पर अच्छा प्रदर्शन प्राप्त करता है
  • कॉची वितरण: भारी-पूंछ वाले वितरण को संभालने के लिए अधिक विशेषताओं की आवश्यकता है (l≥10-15)
  • MNIST डेटा: l≥15 होने पर जटिल वास्तविक डेटा पर अच्छा प्रदर्शन

2. कम्प्यूटेशनल दक्षता

महत्वपूर्ण कम्प्यूटेशनल समय बचत:

  • गॉसियन प्रयोग: RFF विधि केवल 33-44% कम्प्यूटेशनल समय की आवश्यकता है
  • स्केल विस्थापन: 30-40% समय खपत
  • कॉची प्रयोग: केवल 5-6% कम्प्यूटेशनल समय की आवश्यकता है
  • MNIST: 5-15% समय खपत

3. सैद्धांतिक सत्यापन

प्रायोगिक परिणाम सैद्धांतिक भविष्यवाणियों को सत्यापित करते हैं:

  • विशेषता संख्या की आवश्यकता डेटा आयाम और वितरण जटिलता से संबंधित है
  • कम्प्यूटेशनल-सांख्यिकीय व्यापार-बंद सैद्धांतिक विश्लेषण के अनुरूप है

विलोपन प्रयोग

विभिन्न RFF विशेषता संख्याओं की तुलना के माध्यम से, निम्नलिखित को सत्यापित करता है:

  1. विशेषता संख्या सीमा का अस्तित्व
  2. बहुत कम विशेषताएं शक्ति हानि का कारण बनती हैं
  3. उपयुक्त विशेषता संख्या सर्वोत्तम संतुलन प्राप्त करती है

प्रायोगिक निष्कर्ष

  1. आयाम प्रभाव: उच्च-आयामी डेटा को अधिक RFF विशेषताओं की आवश्यकता है
  2. वितरण प्रकार प्रभाव: भारी-पूंछ वाले वितरण को प्रदर्शन सुनिश्चित करने के लिए अधिक विशेषताओं की आवश्यकता है
  3. व्यावहारिक सीमा: सिद्धांत द्वारा आवश्यक विशेषता संख्या व्यवहार में उचित रूप से कम की जा सकती है

संबंधित कार्य

कर्नेल विधि दो-नमूना परीक्षण

  • MMD परीक्षण: Gretton et al. (2006, 2012) का अग्रणी कार्य
  • मिनिमैक्स इष्टतमता: Li & Yuan (2024), Schrab et al. (2023) की हाल की प्रगति
  • वर्णक्रमीय नियमितकरण: Hagrass et al. (2024) का सैद्धांतिक सफलता

यादृच्छिक विशेषता सन्निकटन

  • RFF सिद्धांत: Rahimi & Recht (2007) का मूल ढांचा
  • MMD त्वरण: Zhao & Meng (2015), Choi & Kim (2024) का अनुप्रयोग
  • कम्प्यूटेशनल-सांख्यिकीय व्यापार-बंद: Sriperumbudur & Sterge (2022) का सैद्धांतिक विश्लेषण

इस पेपर के लाभ

मौजूदा कार्य की तुलना में मुख्य लाभ:

  1. अधिक सामान्य कर्नेल फ़ंक्शन: अनुवाद-अपरिवर्तनीय कर्नेल तक सीमित नहीं
  2. व्यापक प्रयोज्यता: गैर-यूक्लिडियन डोमेन का समर्थन करता है
  3. मजबूत सैद्धांतिक गारंटी: गैर-स्पर्शोन्मुख मिनिमैक्स इष्टतमता
  4. अधिक व्यावहारिक एल्गोरिथ्म: पूरी तरह से डेटा-संचालित कार्यान्वयन

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. सैद्धांतिक योगदान: पहली बार RFF सन्निकटन के तहत वर्णक्रमीय नियमितकृत दो-नमूना परीक्षण की मिनिमैक्स इष्टतमता सिद्धांत स्थापित करता है
  2. एल्गोरिथ्म योगदान: कम्प्यूटेशनल रूप से कुशल और सांख्यिकीय रूप से इष्टतम व्यावहारिक एल्गोरिथ्म प्रदान करता है
  3. अनुभवजन्य सत्यापन: विभिन्न डेटा प्रकारों पर विधि की प्रभावशीलता को सत्यापित करता है

सीमाएं

  1. विशेषता संख्या चयन: यद्यपि सैद्धांतिक मार्गदर्शन प्रदान करता है, लेकिन व्यावहारिक चयन को अभी भी अनुभवजन्य समायोजन की आवश्यकता है
  2. कर्नेल फ़ंक्शन निर्भरता: प्रदर्शन अभी भी कर्नेल फ़ंक्शन के चयन पर निर्भर करता है
  3. भारी-पूंछ वाले वितरण: अत्यधिक भारी-पूंछ वाले वितरण के लिए बड़ी संख्या में विशेषताओं की आवश्यकता हो सकती है

प्रभाव

  1. सैद्धांतिक मूल्य: कर्नेल विधियों के कम्प्यूटेशनल-सांख्यिकीय व्यापार-बंद के लिए नया सैद्धांतिक ढांचा प्रदान करता है
  2. व्यावहारिक मूल्य: बड़े पैमाने के डेटा के दो-नमूना परीक्षण में महत्वपूर्ण अनुप्रयोग संभावना है
  3. पद्धति संबंधी योगदान: सांख्यिकीय परीक्षण में RFF सन्निकटन का अनुप्रयोग संबंधित अनुसंधान के लिए नई सोच प्रदान करता है

प्रयोज्य परिदृश्य

  1. बड़े पैमाने का डेटा: जब नमूना आकार बड़ा हो तो कम्प्यूटेशनल लाभ स्पष्ट है
  2. उच्च-आयामी डेटा: उच्च-आयामी सेटिंग में पारंपरिक विधियों की तुलना में महत्वपूर्ण लाभ
  3. वास्तविक समय अनुप्रयोग: कम्प्यूटेशनल दक्षता में सुधार वास्तविक समय परीक्षण को संभव बनाता है
  4. गैर-पैरामीट्रिक सेटिंग: वितरण रूप अज्ञात होने पर सामान्य स्थितियों के लिए उपयुक्त

संदर्भ

  1. Gretton, A., et al. (2012). A kernel two-sample test. JMLR.
  2. Hagrass, O., et al. (2024). Spectral regularized kernel two-sample tests. Annals of Statistics.
  3. Rahimi, A., & Recht, B. (2007). Random features for large-scale kernel machines. NIPS.
  4. Choi, I., & Kim, I. (2024). Computational-statistical trade-off in kernel two-sample testing with random Fourier features.
  5. Sriperumbudur, B. K., & Sterge, N. (2022). Approximate kernel PCA: Computational versus statistical trade-off. Annals of Statistics.

समग्र मूल्यांकन: यह एक उच्च-गुणवत्ता वाला सैद्धांतिक सांख्यिकी पेपर है जो यादृच्छिक विशेषता सन्निकटन तकनीक को वर्णक्रमीय नियमितकृत दो-नमूना परीक्षण में सफलतापूर्वक लागू करता है, सांख्यिकीय इष्टतमता को बनाए रखते हुए कम्प्यूटेशनल दक्षता में काफी सुधार करता है। पेपर का सैद्धांतिक विश्लेषण गहन और विस्तृत है, प्रायोगिक सत्यापन व्यापक है, और सांख्यिकीय शिक्षण सिद्धांत और व्यावहारिक अनुप्रयोग दोनों के लिए महत्वपूर्ण मूल्य है।