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

Minimax-Optimale Kern-Zwei-Stichproben-Tests mit Zufallsmerkmalen

Grundinformationen

  • Papier-ID: 2502.20755
  • Titel: Minimax Optimal Kernel Two-Sample Tests with Random Features
  • Autoren: Soumya Mukherjee, Bharath K. Sriperumbudur (Pennsylvania State University)
  • Klassifizierung: math.ST cs.LG stat.ML stat.TH
  • Veröffentlichungsdatum: 17. Oktober 2025 (arXiv-Preprint)
  • Papier-Link: https://arxiv.org/abs/2502.20755

Zusammenfassung

Dieses Papier präsentiert eine spektral regularisierte Zwei-Stichproben-Testmethode basierend auf Zufallsfourier-Merkmalen (RFF) für das Zwei-Stichproben-Testproblem auf Basis von Reproduzierenden-Kern-Hilbert-Raum-(RKHS-)Einbettungen. Die Methode behält statistische Optimalität bei, während sie die Rechenkomplexität erheblich von kubisch auf nahezu linear reduziert und eine vollständig datengesteuerte praktisch realisierbare Version bereitstellt.

Forschungshintergrund und Motivation

Kernproblem

Der Zwei-Stichproben-Test ist ein grundlegendes Problem der Statistik, das darauf abzielt, durch die Analyse zweier Zufallsstichproben zu bestimmen, ob ihre Wahrscheinlichkeitsverteilungen gleich sind. Traditionelle parametrische und nichtparametrische Testmethoden haben erhebliche Einschränkungen bei der Verarbeitung hochdimensionaler Daten oder Verteilungen auf nicht-euklidischen Bereichen.

Einschränkungen bestehender Methoden

  1. Suboptimalität des MMD-Tests: Obwohl der Maximum Mean Discrepancy (MMD)-Test weit verbreitet ist, fehlt ihm die Minimax-Optimalität, da er nur Mittelwerteinbettungen berücksichtigt und Kovarianzoperator-Informationen ignoriert
  2. Rechenbottleneck spektral regularisierter Methoden: Kürzlich vorgeschlagene spektral regularisierte MMD-Tests erreichen zwar Minimax-Optimalität, haben aber eine Rechenkomplexität von O(n³), was ihre Anwendung auf großskalige Daten einschränkt
  3. Schwierigkeit der Parameterwahl: Die Wahl des Regularisierungsparameters hängt von unbekannten Verteilungseigenschaften ab und es fehlen datengesteuerte adaptive Strategien

Forschungsmotivation

Dieses Papier zielt darauf ab, durch Zufallsfourier-Merkmals-Approximationstechniken die Recheneffizienz spektral regularisierter Zwei-Stichproben-Tests erheblich zu verbessern, während die statistische Optimalität erhalten bleibt, und praktisch anwendbare adaptive Versionen zu entwickeln.

Kernbeiträge

  1. Recheneffiziente und statistisch optimale Tests: Präsentation eines auf RFF basierenden spektral regularisierten Zwei-Stichproben-Tests, der die Rechenkomplexität von O(n³) auf O(nl²+nld) reduziert und unter ausreichenden Bedingungen Minimax-Optimalität bewahrt
  2. Theoretische Garantien: Etablierung der theoretischen Verbindung zwischen der RFF-Approximationsordnung und statistischer Optimalität, Beweis der Minimax-Optimalität des Tests, wenn die Anzahl der Merkmale l bestimmte Bedingungen erfüllt
  3. Praktische adaptive Version: Entwicklung einer vollständig datengesteuerten Version basierend auf Permutationstests, einschließlich adaptiver Auswahlstrategien für Regularisierungsparameter und Kernfunktionen
  4. Umfassende experimentelle Validierung: Validierung der Methodeneffektivität durch synthetische und Benchmark-Datensätze, Demonstration eines guten Kompromisses zwischen Recheneffizienz und statistischer Leistung

Methodische Details

Aufgabendefinition

Gegeben sind unabhängige Stichproben X₁:N und Y₁:M aus Verteilungen P und Q. Teste die Hypothese H₀: P = Q gegen H₁: P ≠ Q.

Kernmethodische Architektur

1. Spektral regularisiertes Framework

Für eine Kernfunktion K definiere die spektral regularisierte Diskrepanz:

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

wobei T der Integraloperator ist, u = dP/dR - 1 die Likelihood-Ratio-Abweichung ist und gλ die Regularisierungsfunktion ist.

2. Zufallsfourier-Merkmals-Approximation

Für Kernfunktionen der Form K(x,y) = ∫φ(x,θ)φ(y,θ)dΞ(θ) konstruiere den approximierten Kern:

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

3. Approximierte Teststatistik

Konstruiere die Teststatistik basierend auf dem approximierten Kern Kₗ:

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

wobei die Funktion t die Quadratwurzel des regularisierten Kovarianzoperators beinhaltet.

Technische Innovationen

1. Theoretische Innovationen

  • Minimax-Optimalitätsbedingungen: Etablierung der genauen Beziehung zwischen RFF-Merkmalanzahl l und statistischer Optimalität
  • Polynomial- und Exponentialabfall: Separate Analyse verschiedener Abfallmuster der Eigenwerte des Integraloperators
  • Nichtasymptotische Analyse: Bereitstellung von Leistungsgarantien bei endlichen Stichproben

2. Algorithmische Innovationen

  • Adaptive Regularisierung: Datengesteuerte Wahl des Regularisierungsparameters durch kombinierte Tests
  • Kernfunktions-Adaptivität: Erweiterung auf adaptive Auswahl mehrerer Kernfunktionen
  • Permutationstest-Implementierung: Vollständig datengesteuerte Berechnung kritischer Werte

3. Rechnerische Innovationen

  • Effiziente Algorithmen: Detaillierte Rechenkomplexitätsanalyse und optimierte Implementierung
  • Parallelisierung: Natürliche Parallelisierungseigenschaften von Permutationstests

Experimentelle Einrichtung

Datensätze

  1. Synthetische Daten:
    • Gaußsche Mittelwertverschiebung: P = N(0,I), Q = N(μ,I)
    • Gaußsche Skalenverschiebung: P = N(0,I), Q = N(0,σ²I)
    • Cauchy-Medianverschiebung: Cauchy-Verteilungen mit unterschiedlichen Medianen
  2. Echte Daten:
    • MNIST-Datensatz: 7×7 Pixel handgeschriebene Ziffernbilder, Dimension d=49
    • Erkennung von Verteilungsunterschieden zwischen verschiedenen Ziffernuntermengen

Bewertungsmetriken

  • Statistische Teststärke (Power): Wahrscheinlichkeit, die Nullhypothese unter der Alternativhypothese korrekt abzulehnen
  • Rechenzeit: Vergleich der Algorithmus-Laufzeiten
  • Fehler erster Art: Kontrolle auf α=0,05-Niveau

Vergleichsmethoden

  • Exakter adaptiver Test: Spektral regularisierter Test basierend auf vollständiger Kernmatrix
  • Unterschiedliche RFF-Merkmalanzahlen: Leistungsvergleich für l ∈ {1,3,5,7,9,15,20}

Implementierungsdetails

  • Regularisierungsfunktion: Showalter-Regularisierer gλ(x) = (1-e^(-x/λ))/x
  • Kernfunktionen: Gaußscher und Laplace-Kern mit adaptiver Bandbreitenwahl
  • Permutationszahl: RFF-Version B=550-800, exakte Version B'=250-450

Experimentelle Ergebnisse

Hauptergebnisse

1. Statistische Leistung

  • Gaußsche Mittelwertverschiebung: Bei RFF-Merkmalen l≥7 nähert sich die Teststärke der exakten Methode an
  • Gaußsche Skalenverschiebung: Gute Leistung bei l≥5
  • Cauchy-Verteilung: Benötigt mehr Merkmale (l≥10-15) zur Verarbeitung schwerer Verteilungen
  • MNIST-Daten: Gute Leistung auf komplexen echten Daten bei l≥15

2. Recheneffizienz

Signifikante Einsparungen bei der Rechenzeit:

  • Gaußsche Experimente: RFF-Methode benötigt nur 33-44% der Rechenzeit
  • Skalenverschiebung: 30-40% des Zeitaufwands
  • Cauchy-Experimente: Nur 5-6% des Zeitaufwands
  • MNIST: 5-15% des Zeitaufwands

3. Theoretische Validierung

Experimentelle Ergebnisse validieren theoretische Vorhersagen:

  • Merkmalanzahl-Anforderungen hängen mit Datendimension und Verteilungskomplexität zusammen
  • Rechen-Statistik-Kompromiss stimmt mit theoretischer Analyse überein

Ablationsstudien

Durch Vergleich unterschiedlicher RFF-Merkmalanzahlen wird validiert:

  1. Existenz von Merkmalanzahl-Schwellwerten
  2. Zu wenige Merkmale führen zu Teststärkeverlust
  3. Angemessene Merkmalanzahl erreicht optimalen Kompromiss

Experimentelle Erkenntnisse

  1. Dimensionseffekt: Hochdimensionale Daten benötigen mehr RFF-Merkmale
  2. Verteilungstyp-Einfluss: Schwere Verteilungen benötigen mehr Merkmale zur Leistungsgarantie
  3. Praktische Schwellwerte: Theoretisch erforderliche Merkmalanzahl kann in der Praxis angemessen reduziert werden

Verwandte Arbeiten

Kernmethoden-Zwei-Stichproben-Tests

  • MMD-Test: Bahnbrechende Arbeiten von Gretton et al. (2006, 2012)
  • Minimax-Optimalität: Neueste Fortschritte von Li & Yuan (2024), Schrab et al. (2023)
  • Spektral-Regularisierung: Theoretischer Durchbruch von Hagrass et al. (2024)

Zufallsmerkmals-Approximation

  • RFF-Theorie: Grundlegendes Framework von Rahimi & Recht (2007)
  • MMD-Beschleunigung: Anwendungen von Zhao & Meng (2015), Choi & Kim (2024)
  • Rechen-Statistik-Kompromiss: Theoretische Analyse von Sriperumbudur & Sterge (2022)

Vorteile dieses Papiers

Hauptvorteile gegenüber bestehenden Arbeiten:

  1. Allgemeinere Kernfunktionen: Nicht auf translationsinvariante Kerne beschränkt
  2. Breitere Anwendbarkeit: Unterstützung für nicht-euklidische Bereiche
  3. Stärkere theoretische Garantien: Nichtasymptotische Minimax-Optimalität
  4. Praktischere Algorithmen: Vollständig datengesteuerte Implementierung

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Theoretischer Beitrag: Erste Etablierung der Minimax-Optimalitätstheorie für spektral regularisierte Zwei-Stichproben-Tests unter RFF-Approximation
  2. Algorithmischer Beitrag: Bereitstellung eines recheneffizienten und statistisch optimalen praktischen Algorithmus
  3. Empirische Validierung: Validierung der Methodeneffektivität auf verschiedenen Datentypen

Einschränkungen

  1. Merkmalanzahl-Wahl: Obwohl theoretische Anleitung vorhanden ist, erfordert die praktische Wahl noch empirische Anpassung
  2. Kernfunktions-Abhängigkeit: Leistung hängt immer noch von der Kernfunktionswahl ab
  3. Schwere Verteilungen: Für extreme schwere Verteilungen können große Merkmalmengen erforderlich sein

Zukünftige Richtungen

  1. Alternative Approximationsmethoden: Erkundung von Nyström und anderen Approximationstechniken
  2. Kostengünstige Permutationstests: Kombination mit kostengünstigen Permutationstests zur weiteren Reduktion der Rechenkosten
  3. Automatische Hyperparameter-Abstimmung: Entwicklung intelligenterer Strategien zur Hyperparameter-Wahl

Tiefgreifende Bewertung

Stärken

  1. Theoretische Strenge: Vollständige nichtasymptotische theoretische Analyse, einschließlich ausreichender Bedingungen und Minimax-Optimalitätsbeweise
  2. Hohe Praktikabilität: Algorithmus ist vollständig datengesteuert, benötigt kein Vorwissen
  3. Umfangreiche Experimente: Abdeckung synthetischer und echter Daten, verschiedene Verteilungstypen
  4. Klare Darstellung: Detaillierte technische Details, vollständige Beweise

Mängel

  1. Komplexitätsanalyse: Obwohl asymptotische Komplexität reduziert wird, können Konstanten-Faktoren groß sein
  2. Parameterempfindlichkeit: Auswahl von Regularisierungsparameter und Merkmalanzahl bleibt empfindlich
  3. Behandlung schwerer Verteilungen: Verbesserungsbedarf bei der Verarbeitung schwerer Verteilungen

Einflussfähigkeit

  1. Theoretischer Wert: Bietet neues theoretisches Framework für Rechen-Statistik-Kompromiss von Kernmethoden
  2. Praktischer Wert: Wichtige Anwendungsaussichten bei Zwei-Stichproben-Tests auf großskaligen Daten
  3. Methodologischer Beitrag: RFF-Approximation in statistischen Tests bietet neue Forschungsideen für verwandte Arbeiten

Anwendungsszenarien

  1. Großskalige Daten: Rechenvorteil ist bei großen Stichprobenmengen offensichtlich
  2. Hochdimensionale Daten: Signifikante Vorteile gegenüber traditionellen Methoden in hochdimensionalen Einstellungen
  3. Echtzeit-Anwendungen: Verbesserung der Recheneffizienz ermöglicht Echtzeit-Tests
  4. Nichtparametrische Einstellungen: Anwendbar auf allgemeine Fälle mit unbekannter Verteilungsform

Literaturverzeichnis

  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.

Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Statistik-Papier, das erfolgreich Zufallsmerkmals-Approximationstechniken auf spektral regularisierte Zwei-Stichproben-Tests anwendet und dabei die statistische Optimalität bewahrt und die Recheneffizienz erheblich verbessert. Die theoretische Analyse des Papiers ist tiefgreifend und detailliert, die experimentelle Validierung ist umfassend und hat wichtige Bedeutung sowohl für die statistische Lerntheorie als auch für praktische Anwendungen.