Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Models

Technische Samenvatting: Twee-punts deterministische equivalentie voor stochastische gradiëntdynamica in lineaire modellen

Probleemstelling
Modern diep leren vertoont voorspelbare schaalwetten waarbij de prestaties verbeteren met toename van data, modelgrootte en rekenkracht. Hoewel recente werken de schaalgedrag van kernmethoden en modellen met willekeurige kenmerken hebben geanalyseerd die zijn getraind met Stochastic Gradient Descent (SGD), behandelen bestaande theoretische kaders vaak specifieke effecten—zoals een eindige datasetgrootte, een eindige modelbreedte en SGD-ruis—in isolatie of vertrouwen op complexe dynamische mean field-theorie (DMFT)-benaderingen. Een unificerend analytisch kader dat het samenspel van beperkte data, beperkte kenmerken en SGD-ruis in hoog-dimensionale lineaire modellen kan vastleggen, met name voor tijdsafhankelijke dynamica en out-of-distribution (OOD) scenario's, blijft een uitdaging. Specifiek vertrouwen standaard technieken voor willekeurige matrices vaak op "één-punts" resolventen, die ontoereikend zijn wanneer de matrices die de dynamica beheersen (bijvoorbeeld empirische covariantie, populatiecovariantie en kenmerkmatrices) niet commuteren.

Methodologie
De auteurs ontwikkelen een nieuw analytisch kader gebaseerd op twee-punts deterministische equivalenties voor resolventen van willekeurige matrices. De kern van de methodologie omvat:

1. Modelopzet: Het artikel beschouwt lineaire regressie en lineaire modellen met willekeurige kenmerken ($f(x) = x^\top F v$) die worden getraind via SGD met een batchgrootte $B$ op een dataset van grootte $P$. De analyse opereert in de hoog-dimensionale limiet waarbij de invoerdimensie $D$, de kenmerkbreedte $N$ en de datasetgrootte $P$ gezamenlijk naar oneindig groeien met vaste verhoudingen.
2. Gereduceerde Dynamica: Volgend op eerder werk leiden de auteurs een gereduceerd model af voor de evolutie van trainings- en generalisatiefouten. Dit houdt in dat de covariantie van het gewichtsverschil ($\Delta w_t \Delta w_t^\top$) wordt gevolgd en dat de risicodynamica wordt uitgedrukt als een Volterra-integraalvergelijking. Deze vergelijking bestaat uit een "forcerende term" (gradiëntstroomcomponent) en een "kernterm" (SGD-ruiscomponent).
3. Fourier-ruimte Analyse: De auteurs transformeren de tijdsdomeindynamica naar Fourier-ruimte. Dit onthult dat de forcerende termen producten bevatten van twee resolventen die worden geëvalueerd bij verschillende argumenten (frequenties), namelijk $(\lambda + AB)^{-1} M (\lambda' + BA)^{-1}$.
4. Twee-punts Deterministische Equivalentie: De primaire technische innovatie is de afleiding van een deterministische equivalentie voor deze producten van twee-punts resolventen. Met behulp van theorie van vrije waarschijnlijkheid, specifiek de eigenschappen van de S-transformatie en een planaire diagrammatische expansie, evalueren de auteurs het asymptotische gedrag van deze producten. Zij onderscheiden tussen "ongescheiden" bijdragen (die factoriseren in één-punts equivalenties) en "verbonden" bijdragen die gemengde cumulanten bevatten, wat leidt tot een zelfconsistente vergelijking voor de twee-puntsfunctie.
5. Toepassing op Risico: Deze equivalenties worden toegepast om scherpe asymptotische uitdrukkingen af te leiden voor zowel het trainings- als het testrisico (generalisatie), inclusief scenario's met covariaatverschuiving (waarbij testdata een andere verdeling volgt dan de trainingsdata).

Belangrijkste Bijdragen

• Nieuwe Deterministische Equivalentie: Het artikel leidt een nieuwe klasse van "twee-punts deterministische equivalenties" af voor resolventen van willekeurige matrices die worden geëvalueerd bij willekeurige paren argumenten. Dit breidt eerdere "één-punts" resultaten uit om niet-commuterende matrices te behandelen, wat essentieel is voor dynamica op eindige tijden en datasetgroottes.
• Unificerende Afleiding: Het kader biedt een unificerende afleiding van prestaties voor hoog-dimensionale lineaire regressie, kernregressie en lineaire modellen met willekeurige kenmerken. Het herstelt eerder bekende asymptotica (bijvoorbeeld uit DMFT-benaderingen in [16] en één-punts equivalentietechnieken in [17]) terwijl het nieuwe resultaten biedt voor tijdsafhankelijke dynamica.
• Karakterisering van SGD-ruis: De auteurs modelleren expliciet de interactie van beperkte data, beperkte kenmerken en SGD-ruis. Zij leiden scherpe asymptotica af voor de "SGD-kernterm", waarbij wordt aangetoond hoe ruis bijdraagt aan de risicodynamica in de loop van de tijd.
• Analyse van Covariaatverschuiving: De methodologie wordt uitgebreid naar out-of-distribution scenario's, waarbij exacte asymptotische formules worden geboden voor generalisatiefout wanneer testcovariaten een andere Gaussische verdeling volgen dan de trainingsset.
• Verbinding met DMFT: Het artikel legt een directe link tussen de afgeleide grootheden van willekeurige matrices en Dynamical Mean Field Theory. Het interpreteert de S-transformatie van vrije waarschijnlijkheid als een responsfunctie en identificeert de twee-punts deterministische equivalenties met de correlatiefuncties die in DMFT worden gebruikt.

Resultaten
De auteurs verkrijgen expliciete, scherpe asymptotische formules voor:

• Trainings- en Testverlies: Uitdrukkingen voor de tijds-evolutie van trainings- en generalisatiefout in modellen met willekeurige lineaire kenmerken, opgesplitst in bijdragen van gradiëntstroom (forcerend) en SGD-ruis (kern).
• Gradiëntstroomtermen: Nieuwe twee-punts equivalenties voor de forcerende termen, die het niet-commutatieve karakter van de empirische en populatiecovarianties op eindige tijden vastleggen.
• SGD-kerntermen: Asymptotische uitdrukkingen voor de kernen die de accumulatie van SGD-ruis beheersen, inclusief correcties voor eindige batchgroottes en kenmerkdimensies.
• Statische Limieten: De resultaten herstellen de bekende statische (oneindige-tijd) limieten, zoals de prestaties van ridgeless regressie, en valideren zo de dynamische aanpak.
• OOD-prestaties: Gesloten-formule asymptotica voor generalisatiefout onder covariaatverschuiving, die eerdere statische resultaten herstellen en uitbreiden naar de dynamische setting.

Betekenis
Het artikel claimt betekenis door een unificerend en rigoureus analytisch instrument te bieden voor het begrijpen van de schaalwetten en leer-dynamica van hoog-dimensionale lineaire modellen. Door twee-punts deterministische equivalenties in te voeren, overbruggen de auteurs de kloof tussen statische theorie van willekeurige matrices en de dynamische, niet-commutatieve aard van SGD-training. Dit maakt een nauwkeurige karakterisering mogelijk van hoe beperkte data, een beperkte modelbreedte en stochastische ruis samenspannen om de prestaties te bepalen. Het werk suggereert dat de S-transformatie en planaire diagrammatische methoden een krachtig alternatief bieden voor DMFT voor het afleiden van deze resultaten, wat potentieel de analyse van complexe leer-dynamica vereenvoudigt terwijl de wiskundige rigorousheid in de hoog-dimensionale limiet behouden blijft. De auteurs merken op dat hoewel zij geen kwantitatieve foutgrenzen bewijzen voor eindige dimensies, de asymptotische formules naar verwachting goede benaderingen zullen bieden, gebaseerd op bekende resultaten in statische settings en numeriek bewijs uit eerdere literatuur.