Implicit Bias of Per-sample Adam on Separable Data: Departure from the Full-batch Regime

Dit artikel toont aan dat de impliciete bias van per-stap Adam op lineair scheidbare data kan afwijken van de volledige-batch-regime en zelfs convergeren naar een $\ell_2$-max-margin classifier, terwijl de bias van Signum onafhankelijk blijft van de batchgrootte.

De kern

Stel je voor dat je een enorme, complexe puzzel probeert op te lossen. In de wereld van kunstmatige intelligentie is die puzzel het vinden van de perfecte manier om data te classificeren (bijvoorbeeld: is dit een foto van een kat of een hond?). Om dit te doen, gebruiken computers een algoritme genaamd Adam. Adam is de "standaard" in de wereld van AI; het is de favoriete tool van bijna iedereen omdat het snel werkt.

Maar er is een geheim: Adam heeft een eigen "persoonlijkheid" of voorkeur. Het neigt er niet alleen naar om de puzzel op te lossen, maar het zoekt altijd naar een specifiek type oplossing, zelfs als er duizenden andere oplossingen mogelijk zijn. Dit noemen wetenschappers de "impliciete bias".

Tot nu toe dachten onderzoekers dat Adam altijd dezelfde voorkeur had: het hield van oplossingen die leken op de $\ell_\infty$-max-margin.

• De analogie: Stel je voor dat je een muur moet bouwen tussen twee groepen mensen (rood en blauw). De $\ell_\infty$-voorkeur betekent dat Adam de muur zo bouwt dat hij zo ver mogelijk weg blijft van de enkele persoon die het dichtst bij de muur staat, ongeacht hoe de rest van de groep eruitziet. Het kijkt puur naar de "ergste" situatie en bouwt daar een buffer omheen.

Het grote verrassing: Het hangt af van hoe je kijkt

Deze nieuwe paper (geschreven door onderzoekers van de Seoul National University en KAIST) ontdekt iets verrassends: Die voorkeur van Adam is niet altijd hetzelfde. Het hangt af van hoe je de data aan Adam geeft.

De onderzoekers vergelijken twee manieren van werken:

1. De "Volle Bak" (Full-batch): Adam kijkt naar alle puzzelstukjes tegelijk.
   • Gedrag: Hier gedraagt Adam zich zoals we altijd dachten. Hij bouwt die specifieke muur die de "ergste" persoon het beste beschermt ($\ell_\infty$).
2. De "Incrementele" of "Stuk-voor-stuk" methode (Mini-batch/Incremental): Adam kijkt naar slechts één puzzelstukje per keer, of een heel klein groepje, en past zijn strategie direct aan.
   • Gedrag: Hier gebeurt het wonder. Adam verandert zijn persoonlijkheid! In plaats van naar de "ergste" persoon te kijken, gaat hij nu op zoek naar de $\ell_2$-max-margin.
   • De analogie: In plaats van alleen naar de dichtstbijzijnde persoon te kijken, kijkt Adam nu naar het gemiddelde van de hele groep. Hij bouwt een muur die in het midden ligt, precies in het midden van de groep, alsof hij een eerlijke scheidsrechter is die iedereen evenveel ruimte wil geven.

Waarom is dit belangrijk?

Stel je voor dat je een chef-kok bent.

• Als je alle ingrediënten tegelijk in de pan gooit (Full-batch), krijg je een gerecht met een heel specifieke smaak (de $\ell_\infty$-smaak).
• Als je de ingrediënten één voor één toevoegt en constant proeft (Mini-batch), krijg je een heel ander gerecht (de $\ell_2$-smaak).

De onderzoekers tonen aan dat de manier waarop we Adam gebruiken in de echte wereld (waar we vaak met kleine groepjes data werken) zijn "smaak" volledig verandert. Dit betekent dat de theorie over Adam, die tot nu toe alleen gold voor het "volledige" scenario, niet klopt voor de dagelijkse praktijk.

De "Signum" tegenhanger

Om het nog interessanter te maken, kijken ze ook naar een andere optimizer genaamd Signum.

• Signum is als een koppige muis. Het maakt niet uit of je alle data tegelijk geeft of stuk voor stuk: Signum blijft altijd dezelfde "muur" bouwen. Het houdt altijd van die specifieke $\ell_\infty$-smaak, ongeacht de situatie.
• Dit laat zien dat Adam uniek is: zijn gedrag is flexibel en afhankelijk van de data, terwijl Signum star en voorspelbaar blijft.

Samenvatting in het kort

• Het probleem: We dachten dat Adam altijd op dezelfde manier "leerde" (altijd naar de ergste situatie kijken).
• De ontdekking: Als je Adam gebruikt met kleine stapjes (zoals in de echte wereld), verandert hij van gedrag. Hij gaat dan kijken naar het gemiddelde in plaats van de ergste situatie.
• De les: De manier waarop je een algoritme gebruikt (hoeveel data je per keer bekijkt) bepaalt niet alleen hoe snel het leert, maar ook wat het uiteindelijk leert. Het is alsof je een speler een andere tactiek laat spelen afhankelijk van of hij alleen of in een team speelt.

Dit is een belangrijke ontdekking voor de toekomst van AI, omdat het ons helpt te begrijpen waarom bepaalde modellen beter werken dan andere, en hoe we ze beter kunnen sturen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Implicit Bias of Per-Sample Adam on Separable Data: Departure from the Full-Batch Regime", geschreven in het Nederlands.

Probleemstelling

De implicit bias (de voorkeur van een optimalisatiealgoritme voor bepaalde oplossingen zonder expliciete regularisatie) is cruciaal voor het begrijpen van waarom diepe neurale netwerken goed generaliseren. Voor lineaire classificatie op lineair scheidbare data is aangetoond dat Standaard Gradient Descent (GD) convergeert naar de $\ell_2$-max-margin oplossing, terwijl Full-Batch Adam convergeert naar de $\ell_\infty$-max-margin oplossing.

Echter, bestaande theoretische analyses van Adam zijn grotendeels beperkt tot het full-batch regime (waarbij de gradient over de hele dataset wordt berekend). In de praktijk wordt Adam bijna uitsluitend gebruikt in het mini-batch regime (vaak met batchgrootte 1 of kleine batches). De centrale vraag die dit paper beantwoordt is: Behoudt Adam zijn kenmerkende $\ell_\infty$-bias ook onder mini-batch updates, of verandert dit gedrag?

Methodologie

Het paper onderzoekt dit probleem door te focussen op Incremental Adam (Inc-Adam), een variant die één voorbeeld per stap verwerkt in een cyclische volgorde (batchgrootte 1). De auteurs gebruiken de volgende methodologische stappen:

1. Asymptotische Analyse: Ze analyseren het gedrag van de iteraties wanneer de trainingsfout naar nul gaat. Ze tonen aan dat het gedrag van Inc-Adam fundamenteel verschilt van Full-Batch Adam (Det-Adam).

   • Full-Batch Adam: Convergeert asymptotisch naar een SignGD-achtig gedrag (gebaseerd op het teken van de gradient), wat leidt tot $\ell_\infty$-bias.
   • Incremental Adam: De update-regel wordt gedomineerd door een gewogen, gepreconditieerde Gradient Descent. De "preconditioner" (de schaling in Adam) trackt de som van de kwadraten van mini-batch gradienten, wat afwijkt van de kwadratische full-batch gradient. Dit leidt tot complexe, data-afhankelijke dynamiek.

2. Gestructureerde Data (Scaled Rademacher): Om de kernverschillen te isoleren, construeren de auteurs een specifieke dataset genaamd "Scaled Rademacher" (SR) data. Op deze data verdwijnt de coördinaat-afhankelijke aanpassing van Adam, waardoor ze kunnen bewijzen dat Inc-Adam convergeert naar de $\ell_2$-max-margin oplossing, in tegenstelling tot de $\ell_\infty$-bias van full-batch Adam.

3. Proxy-algoritme voor General Data: Voor algemene datasets is de analyse complex. De auteurs introduceren een uniform-averaging proxy (AdamProxy) die geldt in de limiet waar de momentum parameter $\beta_2 \to 1$.

   • Ze karakteriseren de convergentierichting als de oplossing van een parametrisch optimalisatieprobleem met een Mahalanobis-norm.
   • De covariantiematrix van deze norm wordt bepaald door een data-afhankelijke vaste-puntvergelijking (fixed-point equation) tussen duale variabelen.

4. Vergelijking met Signum: Als tegenhanger analyseren ze het algoritme Signum (SignSGD met momentum). Ze bewijzen dat Signum, in tegenstelling tot Adam, zijn $\ell_\infty$-bias behoudt voor elke batchgrootte, mits de momentum parameter $\beta$ dicht genoeg bij 1 ligt.

Belangrijkste Bijdragen en Resultaten

1. Afwijking van Full-Batch Gedrag: Het paper levert het eerste theoretische bewijs dat de implicit bias van Adam afhangt van het batching-schema.

   • Resultaat: Full-batch Adam convergeert naar $\ell_\infty$-max-margin.
   • Resultaat: Incremental Adam (batchgrootte 1) convergeert op specifieke gestructureerde data (SR-data) naar de $\ell_2$-max-margin oplossing. Dit is een scherp contrast met de full-batch variant.

2. Data-Afhankelijke Bias: Voor algemene datasets is de bias van mini-batch Adam niet universeel $\ell_2$ of $\ell_\infty$, maar data-afhankelijk.

   • De convergentierichting wordt bepaald door een vaste-puntoplossing van een parametrisch probleem.
   • Experimenten tonen aan dat mini-batch Adam op Gaussische data convergeert naar een richting die verschilt van zowel de standaard $\ell_2$- als $\ell_\infty$-oplossingen, maar wel nauwkeurig voorspeld wordt door hun vaste-puntformulering.

3. Robuustheid van Signum: Het paper bewijst dat Signum (met voldoende hoge momentum) zijn $\ell_\infty$-bias behoudt, ongeacht de batchgrootte. Dit suggereert dat de $\ell_\infty$-bias van Adam in het full-batch regime voornamelijk komt door de interactie tussen de momentum en de volledige gradient, en niet inherent is aan de "sign"-component alleen.

4. Empirische Validatie: Uitgebreide experimenten bevestigen de theorie:

   • Op SR-data convergeert mini-batch Adam naar $\ell_2$, terwijl full-batch Adam naar $\ell_\infty$ gaat.
   • Op Gaussische data convergeert mini-batch Adam naar de voorspelde vaste-puntoplossing.
   • De batchgrootte beïnvloedt de convergentierichting: naarmate de batchgrootte groter wordt (dichter bij full-batch), verschuift de bias van mini-batch Adam terug naar $\ell_\infty$.

Significantie en Implicaties

• Theoretisch Inzicht: Dit werk breekt het paradigma dat Adam altijd een $\ell_\infty$-bias heeft. Het toont aan dat de "coördinaat-afhankelijke aanpassing" (coordinate-wise adaptivity) die Adam kenmerkt, in het mini-batch regime kan leiden tot een compleet ander convergentiegedrag dan in het full-batch regime.
• Praktische Relevantie: Aangezien moderne deep learning bijna uitsluitend mini-batch training gebruikt, suggereert dit dat de voordelen van Adam (zoals snellere convergentie of betere generalisatie in taalmodellen) mogelijk niet puur voortkomen uit een $\ell_\infty$-geometrie, zoals eerder werd verondersteld. Het verlies van de $\ell_\infty$-bias in mini-batch settings kan verklaren waarom het prestatieverschil tussen Adam en SGD soms kleiner wordt bij kleinere batches.
• Toekomstige Richtingen: De auteurs wijzen erop dat het begrijpen van de overgang tussen mini-batch en full-batch bias essentieel is voor het optimaliseren van hyperparameters (zoals batchgrootte en momentum) in grote schaal training. Het paper biedt ook een nieuw wiskundig raamwerk (vaste-puntanalyse) om de implicit bias van adaptieve methoden te bestuderen.

Kortom, dit paper demonstreert dat de implicit bias van Adam niet invariant is voor het batching-schema, en dat mini-batch Adam een rijkere, data-afhankelijke bias vertoont die fundamenteel verschilt van de bekende full-batch resultaten.