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

Riepilogo Tecnico: Ottimizzazione Parameter-free di Ordine Zero per Metodi basati su LMO

Definizione del Problema
L'affinamento (fine-tuning) dei Large Language Models (LLM) è un'applicazione centrale dell'ottimizzazione moderna, ma affronta un collo di bottiglia critico: l'overhead di memoria della backpropagation. Memorizzare attivazioni intermedie, gradienti e stati dell'ottimizzatore per modelli come OPT-1.3B richiede una memoria sostanziale (ad esempio, ~25 GB), limitandone la scalabilità. L'ottimizzazione di ordine zero (ZO) offre un'alternativa efficiente dal punto di vista della memoria, sostituendo i calcoli del gradiente con stime di differenza finita derivate da query sui valori della funzione. Tuttavia, gli esistenti metodi ZO soffrono di due limitazioni primarie:

1. Sensibilità agli Iperparametri: Le prestazioni dipendono fortemente dal passo (stepsize) e dal parametro di smoothing ($\tau$). Le impostazioni ottimali richiedono tipicamente la conoscenza di costanti dipendenti dal problema (ad esempio, costanti di Lipschitz, distanza dall'ottimo) che non sono disponibili nella pratica, rendendo necessari costosi grid search specifici per ogni task.
2. Disallineamento Geometrico: Gli aggiornamenti euclidei standard potrebbero non catturare la struttura eterogenea dei blocchi di parametri (ad esempio, pesi a forma di matrice negli LLM). I metodi che utilizzano Linear Minimization Oracles (LMO) possono adattarsi a geometrie non euclidee (come le norme spettrali per le matrici), ma combinare questo aspetto con l'adattamento parameter-free (PF) in un contesto ZO rimane inesplorato.

Metodologia
Gli autori propongono AdaNAGED (ADAptive Norm-Agnostic Gradient-frEe Descent), un nuovo algoritmo che unifica tre paradigmi: ottimizzazione di ordine zero efficiente in termini di memoria, adattamento parameter-free e aggiornamenti aware della geometria tramite LMO.

• Stima Parameter-Free:

  • Smoothness ($L$): Invece di richiedere una costante di Lipschitz a priori, il metodo stima la smoothness locale iterativamente lungo la traiettoria di ottimizzazione. Calcola il rapporto tra la differenza nelle approssimazioni del gradiente ZO e la distanza tra iterati consecutivi: $L_t = \|g_t(x_{t+1}, e_t)\|_* / \|x_{t+1} - x_t\|$. Fondamentalmente, la stessa direzione di perturbazione $e_t$ (memorizzata come seed casuale) viene utilizzata in entrambi i punti per mantenere l'efficienza della memoria.
  • Gap Iniziale ($\Delta$): Il metodo utilizza un limite inferiore noto della funzione obiettivo ($f_{min}$) per stimare il gap iniziale $\Delta \leq f(x_0) - f_{min}$, evitando la necessità di conoscere la distanza dall'ottimo.
  • Stepsize Adattiva: La stepsize $\gamma_t$ viene aggiornata utilizzando un'accumulazione in stile AdaGrad-Norm della stima della smoothness locale ($S_t = S_{t-1} + L_t$), producendo $\gamma_t \propto 1/\sqrt{S_t}$.
  • Parametro di Smoothing ($\tau$): Per garantire la stabilità, $\tau_t$ è scalato linearmente con la stepsize ($\tau_t = \rho C_2 \gamma_t$), derivato dai requisiti teorici della prova di convergenza.

• Aggiornamenti basati su LMO:
  L'algoritmo definisce gli aggiornamenti tramite un Linear Minimization Oracle su una palla di norma: $v_t = \text{lmo}(g_t)$. Ciò consente al metodo di adattarsi a diverse geometrie:

  • Geometria Vettoriale: Utilizzando la norma $\ell_\infty$, si ottiene un aggiornamento simile a Sign-SGD.
  • Geometria Matriciale: Utilizzando la norma spettrale si ottiene un aggiornamento simile a Muon. Poiché la decomposizione polare esatta (SVD) è computazionalmente costosa, gli autori introducono AdaMuGED, che approssima l'operatore polare utilizzando pochi passi dell'iterazione Newton–Schulz (N-SS), evitando l'inversione di matrice.

Contributi Chiave

1. Nuova Costruzione ZO Parameter-Free: Il paper introduce un metodo per stimare la smoothness locale e impostare le stepsize in un contesto di ordine zero senza la conoscenza a priori delle costanti del problema. Questo preserva l'efficienza della memoria di ZO memorizzando solo i seed dei generatori per le direzioni di perturbazione.
2. Unificazione dei Paradigmi: Il proposto algoritmo AdaNAGED combina l'ottimizzazione ZO efficiente in termini di memoria, la riduzione della dipendenza dagli iperparametri e gli aggiornamenti LMO geometricamente consapevoli.
3. Garanzie di Convergenza: Gli autori stabiliscono tassi di convergenza per obiettivi Lipschitz continui, smooth e convessi. Il tasso risultante è asintoticamente ottimale ($O(1/\epsilon^2)$), con fattori aggiuntivi che tengono conto della stima parameter-free e della stochasticità.
4. Varianti Pratiche: L'introduzione di AdaMuGED estende il framework ai parametri con valore matriciale utilizzando le iterazioni Newton–Schulz, rendendolo applicabile al fine-tuning di LLM dove i parametri sono strutturati come matrici.

Risultati Sperimentali
I metodi sono stati valutati sul fine-tuning del modello OPT-1.3B sul task di classificazione del sentiment SST-2, un benchmark per l'adattamento di LLM con vincoli di memoria.

• Baseline: Gli autori hanno confrontato i risultati con ottimizzatori ZO ottimizzati (tuned): ZO-AdaMM, ZO-SignSGD e ZO-Muon.
• Performance:
  • AdaNAGED (simile a SignSGD) ha raggiunto un'accuratezza di 0.903, entro 0.7 punti percentuali da ZO-SignSGD ottimizzato (0.910).
  • AdaMuGED (simile a Muon) ha raggiunto un'accuratezza di 0.908, riducendo il gap rispetto a ZO-SignSGD ottimizzato a 0.2 punti percentuali e superando AdaNAGED di 0.5 punti percentuali.
  • Il ZO-Muon ottimizzato è rimasto la baseline più forte con 0.921, confermando il beneficio della geometria consapevole della matrice.
• Conclusione: I metodi parameter-free hanno dimostrato performance competitive rispetto alle baseline ottimizzate manualmente, validando il fatto che le regole adattive possono recuperare gran parte delle performance dei metodi ZO ottimizzati senza una costosa ricerca degli iperparametri.

Significatività
Il paper sostiene di presentare il primo metodo che opera all'intersezione tra ottimizzazione di Ordine Zero, Parameter-Free e Linear Minimization Oracle. La sua significatività risiede nel dimostrare che:

1. Efficienza della Memoria: L'ottimizzazione ZO può essere resa pratica per gli LLM evitando la backpropagation.
2. Automazione: La dipendenza da costosi tuning degli iperparametri specifici per task può essere eliminata attraverso la stima adattiva e parameter-free di smoothness e stepsize.
3. Flessibilità Geometrica: Il framework supporta aggiornamenti non euclidei (tramite LMO) che si allineano con le proprietà strutturali dei parametri del modello (ad esempio, le matrici), migliorando il condizionamento e la stabilità.

Gli autori mantengono una posizione modesta, osservando che, sebbene il loro approccio parameter-free sia competitivo, le baseline ottimizzate (particolarmente ZO-Muon) mantengono ancora un leggero vantaggio, suggerendo che l'ottimizzazione manuale rimane ottimale ma che il metodo proposto offre un'alternativa robusta e automatizzata.