On the Convergence Rate of LoRA Gradient Descent

Technische Samenvatting: Over de Convergentiesnelheid van LoRA Gradient Descent

Probleemstelling
Low-Rank Adaptation (LoRA) is een standaardmethode geworden voor het fijnafstemmen van grote taalmodellen vanwege zijn efficiëntie, waarbij alleen laag-rang adaptermatrices $A$ en $B$ worden bijgewerkt zodat de uiteindelijke gewichten $W_0 + BA$ zijn. De theoretische understanding van de convergentie ervan is echter beperkt. Waar de oorspronkelijke verliesfunctie $\ell(W)$ doorgaans wordt verondersteld Lipschitz-glad te zijn, is de herparametriseerde verliesfunctie $L(BA)$ niet Lipschitz-glad met betrekking tot de adaptermatrices $A$ en $B$. Dit gebrek aan gladheid verhindert de directe toepassing van klassieke convergentieanalysetechnieken. Bestaande theoretische werken vallen in drie categorieën: (1) asymptotische analyses in oneindige regimes (bijvoorbeeld Neural Tangent Kernel of oneindige breedte), die geen niet-asymptotische snelheden bieden voor eindige modellen; (2) analyses van gewijzigde algoritmen (bijvoorbeeld GaLore, LoRA-One) die niet strikt de oorspronkelijke LoRA-vormulering adresseren; en (3) analyses van het oorspronkelijke LoRA-algoritme die steunen op sterke, kunstmatige aannames, zoals uniform begrensde adaptermatrices, om Lipschitz-gladheid af te dwingen. Bijgevolg blijft de niet-asymptotische convergentiesnelheid van het oorspronkelijke LoRA gradient descent-algoritme zonder begrenzingaannames een open vraag.

Methodologie
De auteurs bieden de eerste niet-asymptotische convergentieanalyse van het oorspronkelijke LoRA gradient descent-algoritme onder minimale aannames: de oorspronkelijke verliesfunctie is Lipschitz-glad en onderbegrensd. Het bewijs verloopt in drie sleutelstappen:

1. Hervorming via Gestapelde Matrices: Het probleem wordt hervormd door de adaptermatrices $B \in \mathbb{R}^{m \times r}$ en $A^T \in \mathbb{R}^{r \times n}$ te stapelen tot één variabele $V \in \mathbb{R}^{(m+n) \times r}$. De oorspronkelijke update $BA$ wordt hersteld als een specifiek blok van het uitwendige product $VV^T$. Dit maakt het mogelijk de optimalisatie te beschouwen als gradient descent op een nieuwe functie $J(V) = L(E_1 V V^T E_2)$, waarbij $E_1$ en $E_2$ extractor-matrices zijn.
2. Gewijzigd Descendlemma: Aangezien $J(V)$ niet Lipschitz-glad is (vanwege de multiplicatieve factor $V$ in de gradiënt), leiden de auteurs een gewijzigd descendlemma af. Dit lemma begrenst de functiedaling $J(V_{t+1}) - J(V_t)$ met hogere-orde termen die de normen van de parameters $\|V_t\|$ en de gradiënt betrekken.
3. Leerstapcontrole: Om daling bij elke stap te garanderen, wordt de leerstap $\eta_t$ dynamisch gecontroleerd op basis van de huidige parameternorm en gradiëntnorm. Specifiek wordt $\eta_t$ omgekeerd evenredig ingesteld met $\|V_t\|^2 + \|\nabla L(E_1 V_t V_t^T E_2)\|$. De auteurs bewijzen dat zelfs als de parameternorm $\|V_t\|$ onbegrensd groeit (wat $\eta_t$ dwingt te dalen), de som van de leerstappen $\sum \eta_t$ voldoende langzaam divergeert (als een harmonische reeks) om convergentie te garanderen, zij het met een langzamere snelheid dan standaard gradient descent.

Belangrijkste Bijdragen

• Niet-Asymptotische Convergentiesnelheid: Het artikel bewijst dat de minimale gradiëntnorm onder LoRA gradient descent convergeert naar nul met een snelheid van $O(1/\log T)$, waarbij $T$ het aantal iteraties is. Dit resultaat geldt zonder begrensde adaptermatrices of Lipschitz-gladheid van de herparametriseerde verliesfunctie aan te nemen.
• Herstel van Standaard Snelheden: De auteurs tonen aan dat als de adapternormen begrensd zijn (een voorwaarde die vaak in eerdere werken wordt verondersteld), de convergentiesnelheid verbetert naar de standaard $O(1/T)$, wat overeenkomt met de snelheid voor Lipschitz-gladde functies.
• Positie-afhankelijkheid: De analyse onthult een "positie-afhankelijkheid" in LoRA-dynamica: convergentie vertraagt als iteraten zich van de oorsprong verwijderen (toenemend $\|V_t\|$) en versnelt als ze zich naar de oorsprong bewegen. Dit wordt toegeschreven aan de geometrische herstructurering van het verlieslandschap door de LoRA-parametrizatie, die een stationair punt creëert in de oorsprong, ongeacht de oorspronkelijke verliesstructuur.
• Praktische Leerstapschema's: Gemotiveerd door de theoretische vereiste om $\eta_t$ te controleren op basis van parameter- en gradiëntnormen, stellen de auteurs praktische adaptieve leerstapschema's voor en valideren deze ($\eta_{adapt}$, $\eta_{adapt2}$ en $\eta_{norm}$) die zich aanpassen op basis van de norm van de gestapelde adapters of de verlieswaarde.

Resultaten

• Theoretisch: Stelling 3.5 vestigt de $O(1/\log T)$ convergentiesnelheid voor het algemene geval en $O(1/T)$ voor het begrenste geval. Het bewijs toont aan dat de recursieve relatie tussen de leerstap, parameternorm en gradiëntnorm een vertraging in convergentie introduceert in vergelijking met standaard gradient descent.
• Empirisch: Experimenten werden uitgevoerd op logistische regressie met CIFAR-10 embeddings en ResNet-18 getraind op CIFAR-10.
  • Adaptieve en genormaliseerde leerstappen, afgeleid van de theorie, toonden snellere en stabielere convergentie in vergelijking met constante leerstappen.
  • In logistische regressie-experimenten werd waargenomen dat de parameternorm $\|V_t\|$ onbegrensd groeide over 1000 epochen, wat het theoretische scenario bevestigt waarbij convergentie vertraagt naar $O(1/\log T)$.
  • In ResNet-18-experimenten convergeerde $\|V_t\|$ naar een begrensd verzameling, wat resulteerde in snellere convergentie.
  • Bij fijnafstemming van Large Language Models (LLM) (TinyLlama-1.1B) toonden adaptieve snelheden aanzienlijke voordelen wanneer parameters werden geïnitieerd met kleine normen, maar gedroegen zich vergelijkbaar met constante snelheden wanneer ze werden geïnitieerd met grote normen (waarbij $\|V_t\|$ groot is en langzaam groeit ten opzichte van zijn omvang).

Betekenis
Het artikel claimt een significante kloof in het theoretische begrip van LoRA te dichten door de eerste niet-asymptotische convergentieanalyse te bieden voor het oorspronkelijke algoritme zonder kunstmatige begrenzingaannames. Het verduidelijkt dat de convergentiesnelheid van LoRA niet afhankelijk is van de gekozen rang $r$, maar wordt bepaald door de interactie tussen de leerstap en de norm van de iteraten. Het werk benadrukt dat de herparametrizatie van LoRA de optimalisatiegeometrie fundamenteel verandert, wat mogelijk leidt tot verschillende oplossingen in vergelijking met full-rank fijnafstemming. Bovendien bieden de voorgestelde leerstapstrategieën een praktische methode om LoRA-training te stabiliseren en te versnellen door rekening te houden met de unieke structuur die wordt veroorzaakt door laag-rang herparametrizatie.