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

Titel: Fundamentele Bias bij het Inverteren van Random Sampling Matrices met Toepassing op Sub-sampled Newton (SSN)

Auteurs: Chengmei Niu, Zhenyu Liao, Zenan Ling (HUST) en Michael W. Mahoney (ICSI/LBNL/UC Berkeley).

1. Het Probleem

In het veld van Randomized Numerical Linear Algebra (RandNLA) en Machine Learning (ML) wordt random sketching (zoals random sampling en random projectie) veel gebruikt om de rekenkosten voor grote matrices te verlagen. Een veelvoorkomend doel is het schatten van de inverse van een matrix, specifiek $(A^\top A + C)^{-1}$, waarbij $A$ een grote matrix is ($n \gg d$) en $C$ een regularisatieterm is.

Hoewel de geschatte matrix $\tilde{A}^\top \tilde{A}$ vaak een onbevooroordeelde (unbiased) schatter is van $A^\top A$, is de inverse daarvan niet onbevooroordeeld. Dit fenomeen staat bekend als inversion bias:
$$\mathbb{E}[(\tilde{A}^\top \tilde{A} + C)^{-1}] \neq (A^\top A + C)^{-1}$$

Eerdere studies hebben deze bias voor dichte Gaussische projecties en sub-Gaussische projecties (zoals LESS) gekarakteriseerd en gecorrigeerd. Echter, voor random sampling (waarbij rijen van $A$ worden geselecteerd) en gestructureerde projecties (zoals SRHT), was de analyse van deze bias onvolledig. Bestaande methoden om de bias te corrigeren (gebaseerd op eerdere werken van Dereziński et al.) leverden voor random sampling slechts "vacu" (niet-zinnige) resultaten op, wat betekent dat de foutgrenzen te groot waren om nuttig te zijn. Dit vormt een probleem voor methoden zoals Sub-sampled Newton (SSN), waar een nauwkeurige schatting van de Hessiaan-inversie cruciaal is voor convergentie.

2. Methodologie

De auteurs gebruiken een geavanceerde combinatie van Niet-Asymptotische Random Matrix Theory (RMT) en RandNLA om de bias te analyseren en te corrigeren.

• Fine-grained Analyse: In plaats van een ruwe benadering te gebruiken, ontwikkelen ze een "leave-one-out" analyse framework. Ze leiden een zelf-consistente vergelijking af voor de verwachting van de inverse matrix.
• Zelf-consistente Vergelijking: Ze tonen aan dat de verwachting van de geschatte inverse dicht bij $(A^\top D A + C)^{-1}$ ligt, in plaats van $(A^\top A + C)^{-1}$, waarbij $D$ een diagonaalmatrix is die afhangt van de leverage scores en de steekproefverdeling.
• De-biasing Techniek: Op basis van deze analyse stellen ze een nieuwe de-biased sampling matrix $\check{S}$ voor. Deze matrix past de weging van de gesamplede rijen aan op basis van de exacte (of benaderde) leverage scores $\ell_i^C$:
  $$\check{S} = \text{diag}\left\{ \sqrt{\frac{m}{m - \ell_{is}^C / \pi_{is}}} \right\} \cdot S$$
  Hierbij is $m$ het aantal steekproeven, $\pi_i$ de sampling kans, en $\ell_i^C$ de leverage score.
• Toepassing op SSN: Ze passen deze correctie toe op de Sub-sampled Newton methode, waarbij de Hessiaan-inversie wordt benaderd via deze gecorrigeerde steekproeven.

3. Belangrijkste Bijdragen

1. Precieze Karakterisering van Inversion Bias:
   De auteurs leveren de eerste nauwkeurige karakterisering van de inversion bias voor algemene random sampling (uniform en niet-uniform, gebaseerd op leverage scores) en gestructureerde projecties (SRHT). Ze tonen aan dat de bias complexer is dan bij Gaussische projecties en afhankelijk is van de verhouding tussen de sampling kans en de leverage scores.

2. Efficiënte De-biasing Methode:
   Ze stellen een nieuwe de-biasing techniek voor die de inverse matrix onbevooroordeeld maakt tot op een zeer kleine foutmarge ($\epsilon$).

   • Voor exacte leverage score sampling reduceert dit tot een eenvoudige scalair herschaling.
   • Voor benaderde leverage scores en SRHT (Subsampled Randomized Hadamard Transform) tonen ze aan dat een scalair herschaling (met factor $m/(m-d_{eff})$) voldoende is om de bias significant te verlagen, mits de steekproefgrootte $m$ groot genoeg is.

3. Probleem-Onafhankelijke Convergentie voor SSN:
   Ze bewijzen de eerste probleem-onafhankelijke lokale convergentie snelheid voor Sub-sampled Newton (SSN) met de-biasing. De convergentie van hun methode komt overeen met die van de Newton Sketch methode met dichte Gaussische projecties, maar met veel lagere rekenkosten.

4. Fase-overgang in Bias:
   Ze onthullen een fase-overgang in de bias bij het gebruik van scalair de-biasing: als de sampling ver genoeg afwijkt van de exacte leverage scores, neemt de bias toe. Dit biedt inzicht in de trade-off tussen de nauwkeurigheid van de leverage score schatting en de uiteindelijke convergentie.

4. Resultaten

• Theoretische Bewijzen:
  • Stelling 3.2: Bewijst dat de voorgestelde de-biased sampling matrix $\check{S}$ leidt tot een $(\epsilon, \delta)$-onbevooroordeelde schatter van de inverse.
  • Stelling 4.3: Bewijst dat de de-biased SSN methode lokaal convergeert met een snelheid die evenredig is met $d_{eff}/m$ (waarbij $d_{eff}$ de effectieve dimensie is), onafhankelijk van de conditiegetal van het probleem.
• Numerieke Experimenten:
  • Getest op MNIST en CIFAR-10 datasets voor logistieke regressie.
  • De de-biased SSN methode (met name met Approximate Ridge Leverage Score sampling, SSN-ARLev) presteert aanzienlijk beter dan de standaard Newton-LESS methode en eerste-orde methoden (GD, SGD).
  • De methode behaalt een superieure "complexiteit-convergentie" trade-off: het bereikt een lage relatieve fout in minder tijd dan Newton-LESS, terwijl de rekentijd voor SSN-ARLev vrijwel constant blijft naarmate de steekproefgrootte $m$ toeneemt (in tegenstelling tot Newton-LESS waar de tijd sterk toeneemt).

5. Betekenis en Impact

• Overbrugging van Theorie en Praktijk: Dit werk sluit de kloof tussen de theoretische garanties van random sketching en de praktische toepassing in tweede-orde optimalisatie. Het toont aan dat random sampling, vaak gezien als minder nauwkeurig dan Gaussische projecties, kan worden gebruikt voor snelle en nauwkeurige Newton-methoden als de inversion bias correct wordt behandeld.
• Efficiëntie: De voorgestelde methode maakt het mogelijk om tweede-orde optimalisatie (Newton-stappen) toe te passen op zeer grote datasets met een lagere rekenkost dan traditionele methoden, zonder in te leveren op convergentiesnelheid.
• Toekomstperspectief: De auteurs suggereren dat deze de-biasing techniek kan worden gecombineerd met adaptieve steekproefstrategieën om zelfs kwadratische convergentie te bereiken, en dat het kader kan worden uitgebreid naar afhankelijke steekproefmethoden (zoals volume sampling).

Kortom, dit paper biedt een fundamentele oplossing voor een lang bestaand probleem in RandNLA (inversion bias bij sampling) en levert direct een krachtig, schaalbaar algoritme voor machine learning optimalisatie op.