Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning

Technische Samenvatting: Zero-order Parameter-free Optimalisatie voor LMO-gebaseerde Methoden

Probleemstelling
Het fijn afstemmen (fine-tuning) van Large Language Models (LLMs) is een centrale toepassing van moderne optimalisatie, maar het kampt met een kritieke flessenhals: de geheugenoverhead van backpropagation. Het opslaan van tussenliggende activaties, gradiënten en optimizer-states voor modellen zoals OPT-1.3B vereist aanzienlijk geheugen (bijv. ~25 GB), wat de schaalbaarheid beperkt. Zeroth-order (ZO) optimalisatie biedt een geheugenefficiënt alternatief door gradiëntberekeningen te vervangen door eindverschillen-schattingen afgeleid van functie-waarde queries. Bestaande ZO-methoden lijden echter onder twee primaire beperkingen:

1. Hyperparametergevoeligheid: De prestaties zijn sterk afhankelijk van de stapgrootte (stepsize) en de gladheidsparameter ($\tau$). Optimale instellingen vereisen doorgaans kennis van probleemafhankelijke constanten (bijv. Lipschitz-constanten, afstand tot het optimum) die in de praktijk niet beschikbaar zijn, wat kostbare taakspecifieke grid searches noodzakelijk maakt.
2. Geometrische Mismatch: Standaard Euclidische updates leggen mogelijk de heterogene structuur van parameterblokken (bijv. matrixvormige gewichten in LLM's) niet goed vast. Methoden die gebruikmaken van Linear Minimization Oracles (LMO's) kunnen zich aanpassen aan niet-Euclidische geometrieën (zoals spectrale normen voor matrices), maar het combineren hiervan met parameter-vrije (PF) adaptatie in een ZO-setting blijft onverkend.

Methodologie
De auteurs stellen AdaNAGED (ADAptive Norm-Agnostic Gradient-frEe Descent) voor, een nieuw algoritme dat drie paradigma's verenigt: geheugenefficiënte zeroth-order optimalisatie, parameter-vrije adaptatie en geometrie-bewuste updates via LMO's.

• Parameter-vrije Estimatie:

  • Gladheid ($L$): In plaats van een vooraf bekende Lipschitz-constante te vereisen, schat de methode de lokale gladheid iteratief langs het optimalisatietraject. Het berekent de ratio van het verschil in ZO-gradiëntbenaderingen tot de afstand tussen opeenvolgende iteraties: $L_t = \|g_t(x_{t+1}, e_t)_* / \|x_{t+1} - x_t\|$. Cruciaal is dat dezelfde perturbatie-richting $e_t$ (opgeslagen als een random seed) op beide punten wordt gebruikt om de geheugenefficiëntie te behouden.
  • Initiële Kloof ($\Delta$): De methode gebruikt een bekende ondergrens van de objectieve functie ($f_{min}$) om de initiële kloof $\Delta \leq f(x_0) - f_{min}$ te schatten, waardoor de noodzaak om de afstand tot het optimum te kennen wordt vermeden.
  • Adaptieve Stapgrootte: De stapgrootte $\gamma_t$ wordt bijgewerkt met behulp van een AdaGrad-Norm stijl accumulatie van de lokale gladheidsschattingen ($S_t = S_{t-1} + L_t$), resulterend in $\gamma_t \propto 1/\sqrt{S_t}$.
  • Smoothing Parameter ($\tau$): Om stabiliteit te garanderen, wordt $\tau_t$ lineair geschaald met de stapgrootte ($\tau_t = \rho C_2 \gamma_t$), afgeleid van de theoretische vereisten van het convergentiebewijs.

• LMO-gebaseerde Updates:
  Het algoritme definieert updates via een Linear Minimization Oracle over een norm-bal: $v_t = \text{lmo}(g_t)$. Dit stelt de methode in staat om aan te passen aan verschillende geometrieën:

  • Vector Geometrie: Het gebruik van de $\ell_\infty$ norm levert een Sign-SGD-achtige update op.
  • Matrix Geometrie: Het gebruik van de spectrale norm levert een Muon-achtige update op. Omdat exacte poolontbinding (SVD) computationeel duur is, introduceren de auteurs AdaMuGED, die de pool-operator benadert met enkele stappen van de Newton–Schulz (N-SS) iteratie, waardoor matrixinversie wordt vermeden.

Belangrijkste Bijdragen

1. Nieuwe Parameter-vrije ZO Constructie: Het artikel introduceert een methode om lokale gladheid te schatten en stapgroottes in te stellen in de zeroth-order setting zonder voorafgaande kennis van probleemconstanten. Dit behoudt de geheugenefficiëntie van ZO door alleen generator-seeds voor perturbatie-richtingen op te slaan.
2. Vereniging van Paradigma's: Het voorgestelde AdaNAGED algoritme combineert geheugenefficiënte ZO, verminderde hyperparameter-afhankelijkheid en geometrie-bewuste LMO-updates.
3. Convergentiegaranties: De auteurs stellen convergentiesnelheden vast voor Lipschitz-continue, gladde en convexe objectieven. De resulterende snelheid is asymptotisch optimaal ($O(1/\epsilon^2)$), met extra factoren die rekening houden met de parameter-vrije estimatie en stochasticiteit.
4. Praktische Varianten: De introductie van AdaMuGED breidt het framework uit naar matrix-waardige parameters met behulp van Newton–Schulz iteraties, waardoor het toepasbaar is op LLM fine-tuning waar parameters als matrices gestructureerd zijn.

Experimentele Resultaten
De methoden werden geëvalueerd op de fine-tuning van het OPT-1.3B model op de SST-2 sentiment classificatie taak, een benchmark voor geheugenbeperkte LLM-adaptatie.

• Baselines: De auteurs vergeleken de methoden met getunede zeroth-order optimizers: ZO-AdaMM, ZO-SignSGD, en ZO-Muon.
• Prestaties:
  • AdaNAGED (SignSGD-achtig) bereikte een nauwkeurigheid van 0,903, binnen 0,7 procentpunt van de getunede ZO-SignSGD (0,910).
  • AdaMuGED (Muon-achtig) bereikte een nauwkeurigheid van 0,908, waardoor de kloof met de getunede ZO-SignSGD werd verkleind tot 0,2 procentpunt en het AdaNAGED met 0,5 procentpunt versloeg.
  • De getunede ZO-Muon bleef de sterkste baseline met 0,921, wat het voordeel van matrix-bewuste geometrie bevestigt.
• Conclusie: De parameter-vrije methoden vertoonden competitieve prestaties ten opzichte van handmatig getunede baselines, wat valideert dat adaptieve regels een groot deel van de prestaties van getunede ZO-methoden kunnen evenaren zonder dure hyperparameter search.

Significantie
Het artikel beweert de eerste methode te presenteren die opereert op het snijvlak van Zeroth-Order, Parameter-Free, en Linear Minimization Oracle optimalisatie. De significantie ligt in het aantonen dat:

1. Geheugenefficiëntie: ZO-optimalisatie praktisch kan worden gemaakt voor LLM's door backpropagation te vermijden.
2. Automatisering: De afhankelijkheid van kostbare, taakspecifieke hyperparameter tuning kan worden geëlimineerd door middel van adaptieve, parameter-vrije estimatie van gladheid en stapgroottes.
3. Geometrische Flexibiliteit: Het framework ondersteunt niet-Euclidische updates (via LMO's) die aansluiten bij de structurele eigenschappen van modelparameters (bijv. matrices), wat de conditionering en stabiliteit verbetert.

De auteurs hanteren een bescheiden standpunt door op te merken dat hoewel hun parameter-vrije benadering competitief is, de getunede baselines (met name ZO-Muon) nog steeds een lichte voorsprong hebben, wat suggereert dat handmatige tuning optimaal blijft, maar dat de voorgestelde methode een robuust, geautomatiseerd alternatief biedt.