Technische Samenvatting: To Grok Grokking: Provable Grokking in Ridge Regression

Probleemstelling

Het artikel onderzoekt het fenomeen van grokking, gedefinieerd als het begin van generalisatie lang nadat een model een perfecte trainingsprestatie (overfitting) heeft bereikt. Hoewel dit voorheen voornamelijk werd waargenomen in complexe, niet-lineaire neurale netwerken en algoritmische datasets, streven de auteurs ernaar om rigoureuze, end-to-end theoretische garanties voor dit fenomeen vast te stellen in een klassieke, lineaire setting. Specifiek adresseert het artikel de kloof in de bestaande literatuur waar eerdere werken ofwel ontbreken aan formele bewijzen van de "vertraging" tussen overfitting en generalisatie, ofwel steunen op specifieke, niet-generaliseerbare probleemstructuren (bijv. modulaire optelling). De kernvraag is of grokking bewezen kan worden in over-geparameteriseerde ridge regressie met behulp van gradiëntafdaling (GD) met weight decay, en zo ja, hoe hyperparameters de "grokking-tijd" kwantitatief controleren.

Methodologie

De auteurs formuleren het probleem binnen een teacher-student framework:

• Setting: Over-geparameteriseerde lineaire regressie waarbij het studentmodel $N(x; \theta) = \langle \theta, \phi(x) \rangle$ een realiseerbare teacher-functie leert $N^*(x) = \langle \theta^*, \phi(x) \rangle$.
• Optimalisatie: De student wordt getraind met behulp van Gradient Descent (GD) met een vaste stapgrootte $\eta$ en een $\ell_2$-regularisatieterm (weight decay) $\lambda$. De doelfunctie is de geregulariseerde gemiddelde kwadratische fout:
  $$L_n(\theta; \lambda) = \frac{1}{2n}\sum_{i=1}^n (N(x_i; \theta) - N^*(x_i))^2 + \frac{\lambda}{2}\|\theta\|_2^2$$
• Analyse-strategie: De auteurs deconstrueren de parametervector $\theta$ in twee orthogonale componenten ten opzichte van de dataspanning:
  1. $\theta_{\parallel}$: De component in de rijruimte van de feature-matrix $\Phi$ (de door data gespande subruimte).
  2. $\theta_{\perp}$: De component in de nulruimte van $\Phi$ (de complementaire subruimte).
• Theoretische benadering: Het bewijs analyseert de convergentiesnelheden van de trainingsverlies (empirische fout) en de generalisatieverlies (populatiefout) afzonderlijk. Het kernmechanisme berust op het aantonen dat $\theta_{\parallel}$ snel convergeert om de trainingsdata te fitten, terwijl $\theta_{\perp}$ traag vervalt door weight decay, wat een langdurige periode van slechte generalisatie veroorzaakt.

Belangrijkste Bijdragen

1. Eerste End-to-End Bewijsbare Grokking: Het artikel biedt het eerste rigoureuze kwantitatieve bewijs dat de drie verschillende stadia van grokking in een lineaire setting aantoont:
   • (i) Snelle overfitting van de trainingsdata.
   • (ii) Een aanhoudende vertraging waarbij de generalisatiefout hoog blijft ondanks een trainingsfout van nul.
   • (iii) Uiteindelijke convergentie naar een model met een willekeurig kleine generalisatiefout.
2. Kwantitatieve Grenzen aan Grokking-tijd: De auteurs leiden expliciete ondergrenzen af voor de "grokking-tijd" ($t_2 - t_1$), waarbij $t_1$ de tijd tot overfitting is en $t_2$ de tijd tot generalisatie. Deze grenzen worden uitgedrukt in termen van modelhyperparameters:
   • Weight Decay ($\lambda$): De grokking-tijd schaalt invers met $\lambda$ ($t_2 \propto 1/\lambda$). Een kleinere $\lambda$ vertraagt de generalisatie aanzienlijk.
   • Initialisatie-schaal ($\nu^2$): Het vergroten van de initialisatie-schaal vergroot de grokking logaritmisch ($t_1, t_2 \propto \ln(\nu^2)$).
   • Over-parameterisatie: Het fenomeen wordt getoond een hoge-dimensie setting te vereisen ($m \gg n$).
3. Hyperparameter Controle: Het artikel stelt voldoende voorwaarden vast op hyperparameters (steekproefomvang $n$, feature-dimensie $m$, weight decay $\lambda$ en initialisatie-schaal $\nu^2$) om grokking te induceren of te elimineren.
4. Empirische Validatie op Niet-Lineaire Modellen: Hoewel de theorie is afgeleid voor lineaire regressie, demonstreren de auteurs empirisch dat de kwantitatieve afhankelijkheden van hyperparameters (bijv. het effect van $\lambda$ op de vertraging) kwalitatief overeenkomen met het gedrag dat wordt waargenomen in niet-lineaire twee-laagse ReLU neurale netwerken.

Belangrijkste Resultaten

• Convergentiesnelheden: De trainingsfout convergeert met een snelheid die wordt gedomineerd door de kleinste niet-nul eigenwaarde van de empirische feature-covariantie ($\lambda^+_{\min}(\Phi^\top \Phi)$), wat snel gaat. In contrast hiermee wordt de generalisatiefout ondergrens bepaald door een term die vervalt met de snelheid van $(1 - \eta\lambda)^t$, wat willekeurig traag is voor een kleine $\lambda$.
• Het Grokking Mechanisme: De vertraging ontstaat omdat GD met een kleine weight decay effectief alleen de projectie van gewichten op de dataspanning bijwerkt om de trainingsverlies te minimaliseren, terwijl de orthogonale component (die bijdraagt aan de generalisatiefout) slechts traag vervalt via de langzame weight decay term.
• Stellingen:
  • Stelling 4.1: Vestigt grokking voor de zero teacher, met overeenkomende boven- en ondergrenzen op de verliesconvergentie.
  • Stelling 4.2: Generaliseert het resultaat naar elke realiseerbare teacher, met expliciete grenzen voor $t_1$ en $t_2$ (Vergelijkingen 6 en 7).
  • Stelling 4.4 & 4.5: Bewijzen de snelle convergentie van de trainingsverlies en de persistentie van slechte generalisatie, respectievelijk.
  • Stelling 4.6: Bewijst dat GD uiteindelijk convergeert naar een globaal minimum met goede generalisatiegaranties.

Betekenis en Claims

Het artikel claimt een fundamenteel theoretisch kader te bieden voor het begrijpen van grokking. Door het fenomeen te isoleren in de eenvoudige, transparante setting van lineaire regressie, betogen de auteurs dat:

• Grokking geen inherente faalmodus is van deep learning architecturen of niet-lineariteiten, maar eerder een gevolg is van specifieke trainingscondities (met name de interactie tussen over-parameterisatie en kleine weight decay).
• Het fenomeen geen fundamentele wijzigingen vereist aan de modelarchitectuur of leeralgoritmen om te vermijden; het kan worden gecontroleerd via hyperparameter-tuning.
• De resultaten bieden de eerste rigoureuze kwantitatieve grenzen op de vertraging van generalisatie, waarmee zij verder gaan dan de empirische observaties of heuristische verklaringen (zoals de "lazy-to-rich" regime transities) die in de eerdere literatuur worden gevonden.
• De bevindingen suggeren dat het "test error plateau" dat vaak wordt gezien in classificatie (een artefact van discrete metrieken) ook bestaat in regressie wanneer deze wordt geëvalueerd via drempelgebaseerde accuratiewaarden, wat de universaliteit van het fenomeen bevestigt over verschillende soorten verliesfuncties heen.

De auteurs blijven bescheiden over de reikwijdte van hun werk, waarbij zij opmerken dat hoewel hun lineaire analyse rigoureuze bewijzen biedt, het uitbreiden van deze resultaten naar niet-realiseerbare settings of het bewijzen van de "lazy-to-rich" transitie in diepe neurale netwerken een openstaande uitdaging blijft die nieuwe theoretische instrumenten vereist.