Résumé Technique : Un Test d'Indépendance à Noyau Martingale

1. Énoncé du Problème

L'article aborde les défis de calibration computationnelle et statistique inhérents aux tests d'indépendance basés sur les noyaux, spécifiquement le Critère d'Indépendance de Hilbert–Schmidt (HSIC) et son extension à l'indépendance conjointe, le dHSIC.

Les implémentations standards du HSIC et du dHSIC reposent sur des statistiques V dégénérées. Sous l'hypothèse nulle d'indépendance ($H_0$), les statistiques redimensionnées convergent vers une somme pondérée de variables aléatoires $\chi^2$, où les poids dépendent de la distribution conjointe inconnue des données. Par conséquent, la calibration pratique nécessite des tests de permutation pour approximer la distribution nulle. Ce processus implique de recalculer la statistique $B$ fois (généralement $B \ge 200$), augmentant le coût computationnel par test de $O(n^2)$ à $O(B n^2)$, soit un facteur de deux ordres de grandeur.

Les auteurs visent à éliminer entièrement l'étape de permutation en construisant des statistiques possédant une limite nulle connue et libre de distribution (normale standard), réduisant ainsi le coût par test pour qu'il corresponde à la complexité quadratique de la statistique V biaisée elle-même.

2. Méthodologie

L'approche proposée adapte la récente construction martingale MMD pour les tests à deux échantillons (Chatterjee et Ramdas [2025]) au contexte de l'indépendance. L'idée centrale est de transformer l'estimateur quadratique standard en une somme de différences martingales, qui peut ensuite être étudiante pour converger vers une distribution normale standard via le théorème central limite (TCL) pour les martingales auto-normalisées.

2.1 La Statistique mHSIC (Indépendance Bivariée)

Pour tester l'indépendance entre deux variables $X$ et $Y$, les auteurs définissent le mHSIC.

• Construction : La statistique est une somme étudiante, triangulaire inférieure, du produit de Hadamard de deux matrices de Gram empiriquement centrées ($K_X$ et $K_Y$).
  $$\hat{T}^{\text{mHSIC}}_n = \frac{1}{n} \sum_{i=2}^n \frac{1}{i} \sum_{j=1}^{i-1} (HK_XH)_{ij} (HK_YH)_{ij}$$
• Studentisation : La statistique est normalisée par sa variation quadratique empirique $\hat{\sigma}_n$.
• Fondement Théorique : Sous $H_0$, le produit de noyaux $\bar{k}_X \bar{k}_Y$ (où $\bar{k}$ désigne les noyaux centrés sur la population) forme une séquence de différences martingales. Bien que la matrice de centrage empirique $H$ introduise un biais, les auteurs prouvent que ce biais est de l'ordre $O_P(1/\sqrt{n})$ et asymptotiquement négligeable après studentisation.
• Propriétés : Sous des conditions de moments d'ordre quatre bornés, le mHSIC converge vers $\mathcal{N}(0, 1)$ quelle que soit la loi des données. Il est consistant contre toute alternative fixe et maintient un coût computationnel de $O(n^2)$ sans division d'échantillon.

2.2 La Statistique mdHSIC (Indépendance Conjointe)

Pour tester l'indépendance conjointe parmi $d$ variables ($X_1, \dots, X_d$), une extension naïve du mHSIC échoue.

• L'Échec du Produit Direct : Le remplacement du noyau bivarié par un produit $d$-fois répété de noyaux empiriquement centrés résulte en un biais agrégé de $O_P(d/\sqrt{n})$. Lorsque le nombre de variables $d$ dépasse $\sqrt{n}$, ce biais domine l'échelle studentisée, brisant la calibration normale standard.
• La Solution Martingale Fractionnée (mdHSIC) : Pour résoudre cela, les auteurs introduisent une unique division par moitié de l'échantillon :
  1. Division : L'échantillon est divisé en $S_1$ (première moitié) et $S_2$ (deuxième moitié).
  2. Centrage : Les plongements moyens et les noyaux centrés sont estimés en utilisant uniquement $S_1$.
  3. Exécution Martingale : La somme martingale auto-normalisée triangulaire inférieure est calculée en utilisant les noyaux centrés par $S_1$ appliqués aux paires au sein de $S_2$.
• Fondement Théorique : Cette construction garantit que le résidu de moyenne conditionnelle du produit de noyaux est de l'ordre $O_P(m^{-d/2})$ (où $m \approx n/2$). Ce résidu est exponentiellement petit en $d$, le rendant négligeable pour tout $d \ge 2$ fixe.
• Propriétés : Le mdHSIC converge vers $\mathcal{N}(0, 1)$ pour tout $d$ fixe sous l'indépendance conjointe. Le coût par test est de $O(d n^2)$, linéaire en $d$, évitant le facteur de permutation $B$.

3. Contributions Clés

1. mHSIC : Une statistique sans permutation et sans division d'échantillon pour l'indépendance bivariée qui converge vers une distribution normale standard sous l'hypothèse nulle, correspondant au coût $O(n^2)$ de la statistique V biaisée HSIC.
2. mdHSIC : Une statistique sans permutation pour l'indépendance conjointe de $d$ variables. Elle corrige le biais de centrage empirique des extensions par produit direct via une unique division par moitié de l'échantillon, assurant la normalité asymptotique pour tout $d$ fixe avec une complexité $O(d n^2)$.
3. Garanties Théoriques : Preuves de convergence vers $\mathcal{N}(0, 1)$ sous l'hypothèse nulle (Théorèmes 3 et 6) et de consistance contre les alternatives fixes, reposant sur le TCL pour les martingales auto-normalisées (Fan [2018]).
4. Validation Empirique : Démonstration que les deux statistiques correspondent aux taux d'erreur de type I et à la puissance des tests des bases de référence calibrées par permutation tout en réalisant des accélérations significatives.

4. Résultats Expérimentaux

Les auteurs ont évalué les méthodes sur des données synthétiques avec des dimensions et des tailles d'échantillon variables.

• Calibration (Erreur de Type I) :
  • mHSIC : Sur des données bivariées avec des dimensions ambiantes allant jusqu'à 500, le taux d'erreur de type I empirique à $\alpha=0.05$ est resté serré autour du niveau nominal pour des $n$ suffisamment grands. Les auteurs notent une « malédiction de la dimensionnalité à échantillon fini » où le taux d'erreur s'inflate si $d_{\text{ambient}} \gtrsim n^{0.875}$ en raison du biais de centrage résiduel.
  • mdHSIC : Sur des tâches d'indépendance conjointe avec $d \in \{2, \dots, 10\}$, le taux d'erreur de type I est resté dans l'intervalle $[0.036, 0.066]$ à travers toutes les tailles d'échantillon et dimensions testées, confirmant la calibration libre de distribution.
• Puissance : Les deux statistiques ont montré des augmentations monotones de la puissance avec la force de dépendance et la taille de l'échantillon, correspondant aux performances des bases de référence basées sur les permutations.
• Efficacité Computationnelle :
  • Le mHSIC et le mdHSIC ont été 25 à 60 fois plus rapides que leurs homologues calibrés par permutation (HSIC-perm et dHSIC-perm avec $B=200$).
  • Pour $n=16\,000$, le mHSIC a pris 0,042 seconde contre 2,532 secondes pour le HSIC-perm.
  • L'accélération s'adapte avec $n$ car le coût de la permutation croît linéairement avec $B$, tandis que le coût martingale reste constant par test.

5. Signification et Revendications

L'article prétend résoudre le goulot d'étranglement de la calibration dans les tests d'indépendance à noyaux. En exploitant les structures martingales, les auteurs éliminent le besoin de rééchantillonnage par permutation coûteux, réduisant la charge computationnelle de deux ordres de grandeur tout en préservant la validité statistique.

• Sans Permutation : La signification principale est le remplacement de l'étape de permutation $O(B n^2)$ par une simple recherche de quantile normal, rendant les tests réalisables pour des ensembles de données à grande échelle où la permutation est prohibitive.
• Robustesse : Les méthodes sont libres de distribution ; la limite nulle est normale standard quelle que soit la loi sous-jacente des données, sous réserve que des conditions de moments légères soient remplies.
• Évolutivité : La statistique mdHSIC aborde spécifiquement le problème d'évolutivité dans les tests d'indépendance conjointe de haute dimension, où les extensions naïves échouent en raison d'un biais cumulatif.

Les auteurs positionnent leur travail comme une adaptation directe du paradigme martingale MMD (Chatterjee et Ramdas [2025]) au problème de l'indépendance, offrant une alternative pratique aux méthodes existantes de division d'échantillon (comme le xHSIC) en conservant la structure triangulaire inférieure qui utilise toutes les paires disponibles dans la deuxième moitié de l'échantillon, améliorant ainsi la puissance statistique par rapport aux approches de blocs croisés rectangulaires.