Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton

1. Problématique

L'article aborde un problème central en algèbre linéaire numérique randomisée (RandNLA) et en apprentissage automatique (ML) : le biais d'inversion (inversion bias).

• Contexte : Les méthodes de « sketching » (esquisses) aléatoires, telles que l'échantillonnage aléatoire (random sampling) et la projection aléatoire, sont utilisées pour réduire la complexité computationnelle des tâches ML à grande échelle (ex: régression, optimisation de second ordre).
• Le problème : Bien que l'esquisse $\tilde{A}$ soit un estimateur non biaisé de la matrice originale $A$ (c'est-à-dire $\mathbb{E}[\tilde{A}^\top\tilde{A}] = A^\top A$), l'opérateur d'inversion étant non linéaire, l'inverse de l'esquisse n'est pas un estimateur non biaisé de l'inverse original.
  $$\mathbb{E}[(\tilde{A}^\top\tilde{A} + C)^{-1}] \neq (A^\top A + C)^{-1}$$
• Conséquence : Ce biais introduit des erreurs systématiques dans les pipelines ML, notamment dans les méthodes d'optimisation de second ordre comme la méthode de Newton sous-échantillonnée (SSN), dégradant leurs taux de convergence.
• Lacune existante : Des travaux récents (Dereziński et al.) ont montré comment corriger ce biais pour les projections gaussiennes denses et les projections sub-gaussiennes structurées (LESS). Cependant, il n'existait pas de caractérisation précise ni de méthode de correction efficace pour les méthodes d'échantillonnage aléatoire (uniforme ou basé sur les scores de levier) et les projections structurées comme la transformée de Hadamard aléatoire sous-échantillonnée (SRHT).

2. Méthodologie

Les auteurs développent une analyse fine (fine-grained) en combinant la théorie des matrices aléatoires non asymptotiques (RMT) et la RandNLA.

A. Analyse du Biais d'Inversion

Au lieu d'utiliser des bornes grossières, les auteurs établissent une équation auto-cohérente pour l'espérance de l'inverse.

• Ils montrent que pour un échantillonnage aléatoire avec une distribution d'importance $\{\pi_i\}$, l'espérance conditionnelle de l'inverse $(A^\top S^\top S A + C)^{-1}$ est proche de $(A^\top D A + C)^{-1}$, où $D$ est une matrice diagonale dépendante implicitement de $A$, de la taille de l'échantillon $m$ et des scores de levier.
• Contrairement aux projections gaussiennes où le biais est corrigé par un simple facteur scalaire, l'échantillonnage aléatoire nécessite une correction plus complexe car les erreurs varient selon les lignes de la matrice.

B. Technique de Débiaisage (De-biasing)

Les auteurs proposent une méthode de correction précise :

1. Correction Matricielle (Fine-grained) : Ils définissent une nouvelle matrice d'échantillonnage $\check{S}$ qui ré-pondère les lignes échantillonnées. Le facteur de pondération pour la ligne $s$ échantillonnée est :
   $$\check{S}_{ss} = \sqrt{\frac{m}{m - \ell^C_{is}/\pi_{is}}}$$
   où $\ell^C_{is}$ est le score de levier exact de la ligne échantillonnée. Cette correction rend l'estimateur de l'inverse presque non biaisé.
2. Approximation et Cas Particuliers :
   • Ils montrent que si les scores de levier sont approximatifs (ce qui est plus rapide à calculer), le biais augmente légèrement mais reste contrôlé.
   • Pour les cas où la distribution d'échantillonnage est proche des scores de levier exacts (ou pour la SRHT où les scores sont quasi-uniformes après transformation), la correction matricielle se réduit à un simple facteur scalaire $\frac{m}{m - d_{eff}}$, similaire aux projections gaussiennes, mais avec un biais résiduel beaucoup plus faible.

C. Application à la Méthode de Newton Sous-échantillonnée (SSN)

Les auteurs intègrent ces résultats de débiaisage dans l'algorithme SSN. Au lieu d'utiliser l'inverse de la Hessienne sous-échantillonnée brute, ils utilisent l'inverse corrigé. Cela permet d'établir des garanties de convergence locales indépendantes du problème (problem-independent).

3. Contributions Clés

1. Caractérisation Précise du Biais : Première analyse fine du biais d'inversion pour l'échantillonnage aléatoire général (uniforme et basé sur les scores de levier) et pour la SRHT.
2. Méthode de Débiaisage : Proposition d'une technique de débiaisage efficace (matricielle ou scalaire selon le cas) qui corrige le biais avec une précision théorique garantie.
3. Taux de Convergence : Établissement des premiers taux de convergence locaux indépendants du problème pour la méthode SSN débiaisée. Ces taux correspondent presque à ceux obtenus avec des projections gaussiennes denses (Newton Sketch), comblant ainsi l'écart de performance entre l'échantillonnage et les projections denses.
4. Validation Numérique : Démonstration empirique sur des jeux de données réels (MNIST, CIFAR-10) montrant que la SSN débiaisée surpasse les méthodes de premier ordre (GD, SGD) et la méthode Newton-LESS en termes de compromis temps-convergence.

4. Résultats Principaux

• Théorème 3.1 & 3.2 : Prouvent que l'inverse de la matrice échantillonnée peut être rendu non biaisé à un niveau $\epsilon$ en utilisant la matrice de correction $\check{S}$. Le biais résiduel est de l'ordre de $\tilde{O}(d_{eff}^{-3\nu/2})$ ou $O(\epsilon)$, bien inférieur aux bornes précédentes qui étaient vides (vacuous).
• Théorème 4.3 : Démontre que la méthode SSN débiaisée converge localement avec un taux linéaire de la forme :
  $$\left( \mathbb{E} \left[ \frac{\|\check{\beta}_T - \beta^*\|_H}{\|\check{\beta}_0 - \beta^*\|_H} \right] \right)^{1/T} \leq \frac{\rho_{max} d_{eff}}{m} (1 + \epsilon)$$
  Ce taux est comparable à celui de Newton Sketch avec des projections gaussiennes, mais avec une complexité computationnelle bien inférieure (car l'échantillonnage est moins coûteux que la multiplication par une matrice dense).
• Expériences Numériques (Section 5) :
  • Sur MNIST et CIFAR-10, la SSN débiaisée (avec échantillonnage de scores de levier approximatifs, ARLev) converge plus rapidement que Newton-LESS pour une même taille d'esquisse $m$.
  • Le temps d'exécution de la SSN reste constant ou augmente très lentement avec $m$, tandis que Newton-LESS (basé sur des projections denses) devient prohibitif.
  • La figure 4 confirme que le débiaisage scalaire réduit drastiquement le biais d'inversion, surtout pour les échantillonnages basés sur les scores de levier.

5. Signification et Impact

• Théorique : L'article résout un problème fondamental de la RandNLA en montrant que l'échantillonnage aléatoire, souvent considéré comme moins précis que les projections gaussiennes pour l'inversion, peut atteindre des performances équivalentes une fois correctement débiaisé. Cela étend le cadre théorique de la RMT aux schémas d'échantillonnage discrets.
• Pratique : Pour les applications d'optimisation à grande échelle (régression logistique, réseaux de neurones), cette méthode offre un compromis supérieur entre complexité computationnelle et vitesse de convergence. Elle permet d'utiliser des méthodes de second ordre (Newton) sur des données massives sans le coût prohibitif du calcul exact de la Hessienne ou des projections denses.
• Futur : Les auteurs suggèrent que cette technique de débiaisage pourrait être combinée avec des schémas d'échantillonnage adaptatifs pour atteindre une convergence quadratique, et pourrait être étendue à d'autres méthodes d'échantillonnage dépendantes (comme l'échantillonnage par volume).

En résumé, ce travail transforme l'échantillonnage aléatoire en une méthode robuste et précise pour l'inversion de matrices, rendant les algorithmes d'optimisation de second ordre plus accessibles et efficaces pour les problèmes de données massives.