Un Test à Deux Échantillons à Noyau Martingale

Informations Fondamentales

• ID de l'article: 2510.11853
• Titre: A Martingale Kernel Two-Sample Test
• Auteurs: Anirban Chatterjee (University of Chicago), Aaditya Ramdas (Carnegie Mellon University)
• Classification: stat.ME, math.ST, stat.TH
• Date de publication: 13 octobre 2025
• Lien de l'article: https://arxiv.org/abs/2510.11853

Résumé

La divergence maximale moyenne (Maximum Mean Discrepancy, MMD) est une mesure de distance multivariée largement utilisée dans les tests à deux échantillons. La statistique de test MMD standard possède une distribution nulle difficile à traiter, nécessitant généralement des méthodes de rééchantillonnage ou de permutation coûteuses pour l'étalonnage. Cet article exploite l'interprétation martingale de l'estimateur MMD au carré pour proposer la MMD martingale (mMMD) — une statistique de temps quadratique qui suit une distribution gaussienne standard asymptotiquement sous l'hypothèse nulle. De plus, nous démontrons que le test est convergent pour toute hypothèse alternative fixe, et pour les grands effectifs d'échantillon, mMMD offre des économies de calcul significatives par rapport au test MMD standard, avec une perte de puissance mineure.

Contexte et Motivation de la Recherche

Description du Problème

Le test à deux échantillons est un problème classique en statistique, dont l'objectif est de tester si deux distributions P et Q sont égales sur la base d'échantillons indépendants: $H_0: P = Q \quad \text{vs} \quad H_1: P \neq Q$

Limitations des Méthodes Existantes

1. Méthodes paramétriques: Échouent souvent en cas de mauvaise spécification du modèle ou sur des données non-euclidiennes
2. Méthodes non paramétriques classiques: Principalement adaptées aux données univariées, extension multivariée difficile
3. Test MMD standard: La distribution nulle est une somme infinie de variables χ² pondérées, dont les poids dépendent de distributions inconnues, nécessitant des méthodes de rééchantillonnage ou de permutation intensives en calcul

Motivation de la Recherche

• La MMD en tant que méthode à noyau démontre une excellente performance dans la détection de différences de distribution dans des domaines généraux
• La détermination du seuil τα est un défi pratique clé pour le test MMD
• Les approximations paramétriques existantes basées sur les moments manquent de garanties de convergence ou de précision
• Nécessité d'une méthode alternative efficace avec une distribution nulle traitable

Contributions Principales

1. Proposition du test mMMD: Une nouvelle variante MMD basée sur la structure martingale, avec une distribution nulle gaussienne standard
2. Garanties théoriques:
   • Preuve de la normalité asymptotique sous l'hypothèse nulle (Théorèmes 2, 3)
   • Établissement de la convergence pour les hypothèses alternatives fixes (Théorèmes 6, 7)
   • Convergence en distribution sous l'hypothèse alternative (Théorème 8)
3. Efficacité computationnelle: Évite le rééchantillonnage, maintient la complexité O(n²) mais réduit significativement le temps d'exécution réel
4. Applications étendues:
   • Test multi-noyau (mmMMD)
   • Famille généralisée de statistiques Tn,γ, incluant MMD standard et mMMD comme cas particuliers

Détails de la Méthode

Définition de la Tâche

Étant donné deux échantillons indépendants de distributions P et Q sur un espace métrique X:

• Xn = {X₁, ..., Xn} ~ P
• Yn = {Y₁, ..., Yn} ~ Q

Objectif: Tester H₀: P = Q vs H₁: P ≠ Q

Idée Centrale: Structure Martingale

Observation clé: La forme modifiée de l'estimateur MMD au carré possède une structure martingale.

Approche par fonction témoin:

• Fonction témoin théoriquement optimale: f₀ = (νP - νQ)/‖νP - νQ‖K
• Pour chaque 2 ≤ i ≤ n, estimation utilisant les données historiques: $\hat{f}_i = \frac{1}{i}\sum_{j=1}^{i-1}[K(X_j, \cdot) - K(Y_j, \cdot)]$

Statistique mMMD

$T_n := \frac{1}{n}\sum_{i=2}^n \langle \hat{f}_i, K(X_i, \cdot) - K(Y_i, \cdot) \rangle_K$

En utilisant l'astuce du noyau, cela se simplifie en: $T_n = \frac{1}{n}\sum_{i=2}^n \frac{1}{i}\sum_{j=1}^{i-1}[K(X_i, X_j) - K(X_i, Y_j) - K(X_j, Y_i) + K(Y_i, Y_j)]$

Statistique Normalisée

Pour réaliser la normalité asymptotique, définissez l'estimateur de variance: $\sigma_n^2 := \frac{1}{n^2}\sum_{i=2}^n \left(\frac{1}{i}\sum_{j=1}^{i-1}K(X_i, X_j) - K(X_i, Y_j) - K(X_j, Y_i) + K(Y_i, Y_j)\right)^2$

Statistique de test finale: $\eta_n = T_n/\sigma_n$

Règle de Test

$\Psi_n := \mathbf{1}\{\eta_n > z_{1-\alpha}\}$ où z₁₋α est le quantile (1-α) de la distribution normale standard.

Points d'Innovation Technique

1. Identification de la structure martingale: Première identification de la séquence de différences martingales dans l'estimateur MMD
2. Éviter le rééchantillonnage: Utilisation du théorème central limite martingale pour obtenir directement une distribution gaussienne standard
3. Indépendance dimensionnelle: Sous des conditions appropriées, la distribution nulle ne dépend pas de la dimensionnalité des données
4. Cadre unifié: La famille Tn,γ unifie plusieurs variantes MMD

Configuration Expérimentale

Expériences de Vérification Théorique

Vérification de la distribution nulle:

• Dimensions: d ∈ {10, 100, 250, 500}
• Distributions de données: Nd(0d, Id) et td(10)
• Noyaux: Gaussien et Laplacien (heuristique de bande passante médiane)
• Effectif d'échantillon: n = 200, 2000 répétitions

Expériences de Comparaison de Puissance

Configuration:

• P = Nd(0d, Id), Q = Nd(μd,j,ε, Id)
• Configurations: (d,j,ε) = (10,5,0.3), (50,5,0.3), (100,5,0.5)
• Méthodes de comparaison: MMD standard, MMD temps linéaire (LMMD), MMD par blocs (BMMD), MMD croisé (xMMD), BetMMD

Expériences sur Données Réelles

Ensemble de données MNIST:

• 5 paires de chiffres avec chevauchement croissant
• 100 échantillons par groupe, 100 répétitions
• Niveau de signification: α = 0,05

Expériences Multi-Noyau

Configuration:

• mmMMD Gauss: 3 noyaux gaussiens, bandes passantes (1,2,4)λmed
• mmMMD Laplace: 3 noyaux laplaciens, mêmes bandes passantes
• mmMMD Mixte: Noyaux gaussiens et laplaciens mixtes

Résultats Expérimentaux

Vérification de la Distribution Nulle

• Résultats principaux: La distribution empirique de ηn correspond étroitement à la distribution gaussienne standard dans tous les paramètres
• Robustesse: Les résultats démontrent une robustesse à la distribution des données, au choix du noyau et à la dimensionnalité
• Avantage comparatif: Contraste frappant avec la distribution nulle complexe du MMD standard

Comparaison de Puissance

Résultats clés:

• La puissance de mMMD est proche de celle du MMD standard, supérieure aux autres variantes efficaces en calcul
• Performance comparable à xMMD, mais évite la division d'échantillon

Efficacité Computationnelle

Résultats: mMMD est environ 100 fois plus rapide que le MMD standard, comparable aux autres méthodes efficaces.

Résultats des Expériences MNIST

• Tendance: La puissance de toutes les méthodes diminue avec l'augmentation du chevauchement
• Classement de performance: mMMD et xMMD > BMMD > LMMD
• Signification pratique: Validation des avantages théoriques sur données réelles

Travaux Connexes

Développement des Tests à Noyau à Deux Échantillons

1. Méthodes précoces: Approches conservatrices basées sur les grandes déviations
2. Méthodes spectrales: Approximation spectrale de Gretton et al. (2009), nécessitant des hypothèses fortes
3. U-statistiques incomplètes: MMD temps linéaire, MMD par blocs, etc.
4. Stratégies de division d'échantillon: Kübler et al. (2022), Shekhar et al. (2022)

Avantages Relatifs de cet Article

• Complétude théorique: Établissement simultané de la théorie de distribution sous hypothèse nulle et alternative
• Efficacité computationnelle: Évite la charge computationnelle des tests de permutation
• Praticité: Pas besoin de division d'échantillon, préserve l'information d'échantillon complète

Conclusions et Discussion

Conclusions Principales

1. Contribution théorique: Première utilisation de la structure martingale pour construire un test MMD avec distribution nulle gaussienne standard
2. Valeur pratique: Réduction significative des coûts computationnels, maintien de bonnes performances statistiques
3. Extensibilité: Le cadre s'étend aux paramètres multi-noyau et aux familles de statistiques plus générales

Limitations

1. Limitations théoriques:
   • Manque de support théorique pour la sélection de bande passante par heuristique médiane
   • Optimalité minimax non déterminée pour γ > 1/2
2. Limitations pratiques:
   • Complexité computationnelle toujours O(n²)
   • Puissance légèrement inférieure au MMD standard dans certains paramètres

Directions Futures

1. Extensions théoriques:
   • Garanties théoriques pour noyaux dépendant des données
   • Applicabilité à des fonctions noyau plus générales
   • Caractérisation complète de l'optimalité minimax
2. Améliorations méthodologiques:
   • Combinaison avec techniques d'approximation de noyau pour réduire la complexité
   • Extension aux tests d'indépendance
   • Applications aux tests basés sur la distance

Évaluation Approfondie

Points Forts

1. Innovation forte: La perspective martingale est une contribution nouvelle à la recherche MMD
2. Rigueur théorique: Théorie asymptotique complète, incluant taux de convergence de type Berry-Esseen
3. Valeur pratique élevée: Résout le goulot d'étranglement computationnel pratique du test MMD
4. Expériences suffisantes: Évaluation complète de la vérification théorique aux applications réelles
5. Clarté de rédaction: Équilibre bien les détails techniques et les explications intuitives

Insuffisances

1. Lacunes théoriques: Analyse théorique incomplète pour la bande passante dépendant des données
2. Perte de puissance: La puissance est effectivement inférieure au MMD standard dans certains cas
3. Portée d'application: Vérification principalement sur l'espace euclidien
4. Complexité computationnelle: Toujours O(n²), pas d'amélioration fondamentale

Impact

1. Valeur académique: Offre une nouvelle perspective à la théorie MMD, peut inspirer davantage de méthodes basées sur les martingales
2. Valeur pratique: Directement applicable aux tâches de test à deux échantillons à grande échelle
3. Reproductibilité: Méthode simple et claire, facile à implémenter et vérifier
4. Extensibilité: Le cadre possède un bon potentiel d'extension

Scénarios d'Application

1. Données à grande échelle: Avantages d'efficacité computationnelle évidents
2. Données haute-dimensionnelles: Caractéristique de distribution nulle indépendante de la dimension avantageuse
3. Applications en temps réel: Satisfait les besoins d'immédiateté en évitant les tests de permutation
4. Scénarios multi-noyau: mmMMD présente des avantages quand le choix de noyau est incertain

Références

1. Gretton, A., et al. (2012a). A kernel two-sample test. JMLR, 13(1), 723-773.
2. Shekhar, S., Kim, I., & Ramdas, A. (2022). A permutation-free kernel two-sample test. NeurIPS, 35, 18168-18180.
3. Li, T. & Yuan, M. (2024). On the optimality of Gaussian kernel based nonparametric tests against smooth alternatives. JMLR, 25(334), 1-62.
4. Fan, X. & Shao, Q. M. (2018). Berry–Esseen bounds for self-normalized martingales. Communications in Mathematics and Statistics, 6(1), 13-27.

Résumé: Cet article est un travail statistique théorique de haute qualité qui, grâce à l'identification ingénieuse d'une structure martingale, fournit une nouvelle solution au problème classique du test MMD. Les contributions théoriques sont solides, la vérification expérimentale est complète, et l'article possède une valeur académique et pratique importante.