On the Convergence Rate of LoRA Gradient Descent

Sintesi Tecnica: Sul Tasso di Convergenza della Discesa del Gradiente LoRA

Enunciato del Problema
L'Adattamento a Basso Rango (LoRA) è diventato un metodo standard per l'adattamento fine dei grandi modelli linguistici grazie alla sua efficienza, aggiornando solo le matrici adattatrici a basso rango $A$ e $B$ in modo che i pesi finali siano $W_0 + BA$. Tuttavia, la comprensione teorica della sua convergenza è limitata. Mentre la funzione di perdita originale $\ell(W)$ è tipicamente assunta essere liscia secondo Lipschitz, la funzione di perdita riparametrizzata $L(BA)$ non è liscia secondo Lipschitz rispetto alle matrici adattatrici $A$ e $B$. Questa mancanza di regolarità impedisce l'applicazione diretta delle tecniche classiche di analisi della convergenza. I lavori teorici esistenti rientrano in tre categorie: (1) analisi asintotiche in regimi infiniti (ad esempio, Kernel Tangente Neurale o larghezza infinita), che non forniscono tassi non asintotici per modelli finiti; (2) analisi di algoritmi modificati (ad esempio, GaLore, LoRA-One) che non affrontano strettamente la formulazione originale di LoRA; e (3) analisi dell'algoritmo LoRA originale che si basano su assunzioni forti e artificiali, come matrici adattatrici uniformemente limitate, per imporre la regolarità secondo Lipschitz. Di conseguenza, il tasso di convergenza non asintotico dell'algoritmo originale di discesa del gradiente LoRA senza assunzioni di limitatezza rimane una questione aperta.

Metodologia
Gli autori forniscono la prima analisi di convergenza non asintotica dell'algoritmo originale di discesa del gradiente LoRA sotto assunzioni minime: la funzione di perdita originale è liscia secondo Lipschitz e limitata inferiormente. La dimostrazione procede in tre passaggi chiave:

1. Riformulazione tramite Matrici Accodate: Il problema viene riformulato accodando le matrici adattatrici $B \in \mathbb{R}^{m \times r}$ e $A^T \in \mathbb{R}^{r \times n}$ in una singola variabile $V \in \mathbb{R}^{(m+n) \times r}$. L'aggiornamento originale $BA$ viene recuperato come un blocco specifico del prodotto esterno $VV^T$. Ciò permette di considerare l'ottimizzazione come una discesa del gradiente su una nuova funzione $J(V) = L(E_1 V V^T E_2)$, dove $E_1$ e $E_2$ sono matrici estrattrici.
2. Lemma di Discesa Modificato: Poiché $J(V)$ non è liscia secondo Lipschitz (a causa del fattore moltiplicativo $V$ nel gradiente), gli autori derivano un lemma di discesa modificato. Questo lemma limita la diminuzione della funzione $J(V_{t+1}) - J(V_t)$ utilizzando termini di ordine superiore che coinvolgono le norme dei parametri $\|V_t\|$ e del gradiente.
3. Controllo del Tasso di Apprendimento: Per garantire la discesa ad ogni passo, il tasso di apprendimento $\eta_t$ è controllato dinamicamente in base alla norma corrente dei parametri e alla norma del gradiente. Nello specifico, $\eta_t$ è impostato inversamente proporzionale a $\|V_t\|^2 + \|\nabla L(E_1 V_t V_t^T E_2)\|$. Gli autori dimostrano che anche se la norma dei parametri $\|V_t\|$ cresce illimitatamente (il che forza $\eta_t$ a diminuire), la somma dei tassi di apprendimento $\sum \eta_t$ diverge sufficientemente lentamente (come una serie armonica) da garantire la convergenza, sebbene a un tasso più lento rispetto alla discesa del gradiente standard.

Contributi Chiave

• Tasso di Convergenza Non Asintotico: Il documento dimostra che la norma minima del gradiente sotto la discesa del gradiente LoRA converge a zero a un tasso di $O(1/\log T)$, dove $T$ è il numero di iterazioni. Questo risultato vale senza assumere matrici adattatrici limitate o regolarità secondo Lipschitz della funzione di perdita riparametrizzata.
• Recupero dei Tassi Standard: Gli autori mostrano che se le norme degli adattatori sono limitate (una condizione spesso assunta nei lavori precedenti), il tasso di convergenza migliora fino al tasso standard $O(1/T)$, corrispondente al tasso per funzioni lisce secondo Lipschitz.
• Dipendenza dalla Posizione: L'analisi rivela una "dipendenza dalla posizione" nella dinamica LoRA: la convergenza viene rallentata se gli iterati si allontanano dall'origine (aumentando $\|V_t\|$) e accelerata se si muovono verso l'origine. Ciò è attribuito alla ristrutturazione geometrica del paesaggio di perdita operata dalla parametrizzazione LoRA, che crea un punto stazionario all'origine indipendentemente dalla struttura della perdita originale.
• Schemi Pratici di Tasso di Apprendimento: Motivati dal requisito teorico di controllare $\eta_t$ in base alle norme dei parametri e del gradiente, gli autori propongono e validano schemi pratici di tasso di apprendimento adattivo ($\eta_{adapt}$, $\eta_{adapt2}$ e $\eta_{norm}$) che si adattano in base alla norma degli adattatori accodati o al valore della perdita.

Risultati

• Teorici: Il Teorema 3.5 stabilisce il tasso di convergenza $O(1/\log T)$ per il caso generale e $O(1/T)$ per il caso limitato. La dimostrazione evidenzia che la relazione ricorsiva tra tasso di apprendimento, norma dei parametri e norma del gradiente introduce un rallentamento nella convergenza rispetto alla discesa del gradiente standard.
• Empirici: Gli esperimenti sono stati condotti su regressione logistica con embedding CIFAR-10 e ResNet-18 addestrato su CIFAR-10.
  • I tassi di apprendimento adattivi e normalizzati derivati dalla teoria hanno dimostrato una convergenza più rapida e stabile rispetto ai tassi di apprendimento costanti.
  • Negli esperimenti di regressione logistica, la norma dei parametri $\|V_t\|$ è stata osservata crescere illimitatamente per 1000 epoche, confermando lo scenario teorico in cui la convergenza rallenta fino a $O(1/\log T)$.
  • Negli esperimenti con ResNet-18, $\|V_t\|$ è convergente verso un insieme limitato, risultando in una convergenza più rapida.
  • Nell'adattamento fine di Modelli Linguistici su Grande Scala (LLM) (TinyLlama-1.1B), i tassi adattivi hanno mostrato benefici significativi quando i parametri sono stati inizializzati con norme piccole, ma si sono comportati in modo simile ai tassi costanti quando inizializzati con norme grandi (dove $\|V_t\|$ è grande e cresce lentamente rispetto alla sua dimensione).

Significato
Il documento afferma di colmare un divario significativo nella comprensione teorica di LoRA fornendo la prima analisi di convergenza non asintotica per l'algoritmo originale senza assunzioni artificiali di limitatezza. Chiarisce che il tasso di convergenza di LoRA non dipende dal rango $r$ scelto, ma è governato dall'interazione tra il tasso di apprendimento e la norma degli iterati. Il lavoro evidenzia che la riparametrizzazione di LoRA altera fondamentalmente la geometria di ottimizzazione, portando potenzialmente a soluzioni diverse rispetto all'adattamento fine a rango completo. Inoltre, le strategie di tasso di apprendimento proposte offrono un metodo pratico per stabilizzare e accelerare l'addestramento LoRA tenendo conto della struttura unica indotta dalla riparametrizzazione a basso rango.