Sintesi Tecnica: Rivedere l'Approssimazione dell'Eside di Ordine Zero: Una Prospettiva di Ottimizzazione della Policy a Singolo Step

1. Definizione del Problema

L'ottimizzazione di ordine zero (ZO) affronta scenari in cui la funzione obiettivo $F(\theta) = \mathbb{E}_\xi[f(\theta; \xi)]$ è una scatola nera accessibile solo tramite valutazioni rumorose della funzione. Sebbene la stima del gradiente ZO sia ben consolidata, un'accurata approssimazione dell'eside di ordine zero rimane una sfida significativa, particolarmente in regimi ad alta dimensionalità e con elevato rumore.

Informazioni accurate sulla curvatura sono critiche per:

• Ottimizzazione bilevel senza derivate.
• Quantificazione dell'incertezza.
• Fine-tuning consapevole della curvatura di Large Language Models (LLM).

I metodi esistenti affrontano due limitazioni primarie:

1. Alta Varianza: Gli stimatori classici randomizzati (ad esempio, stimatori di tipo Stein) spesso soffrono di un'elevata varianza in contesti ad alta dimensionalità, portando a un'ottimizzazione instabile.
2. Ambito Limitato: La ricerca precedente si è concentrata principalmente sulla stima della matrice eside $\nabla^2 F(\theta)$ stessa. Vi è poca attenzione rivolta all'inverso dell'eside regolarizzato $(\nabla^2 F(\theta) + \lambda I_d)^{-1}$ e al prodotto eside-gradiente inverso $(\nabla^2 F(\theta) + \lambda I_d)^{-1}\nabla F(\theta)$, che sono essenziali per gli aggiornamenti di secondo ordine ZO.
3. Efficienza di Query: I metodi ingenui di differenza finita richiedono $O(d^2)$ query, mentre i metodi randomizzati esistenti spesso non riescono a bilanciare la riduzione della varianza con il riutilizzo delle query in modo efficace.

2. Metodologia

2.1. Framework Teorico: Prospettiva di Ottimizzazione della Policy (PO)

Gli autori propongono un framework unificato che reinterpreta l'approssimazione dell'eside ZO attraverso la lente dell'Ottimizzazione della Policy (PO) a Singolo Step.

• Obiettivo Smussato (Smoothed): L'obiettivo ZO viene riformulato come un obiettivo smussato $F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)}[\mathbb{E}_\xi[f(x; \xi)]]$, dove $\pi_\theta$ è una policy di campionamento parametrizzata (ad esempio, Gaussiana $N(\theta, \mu^2 I_d)$).
• Identità dell'Eside: Differenziando il gradiente della policy, gli autori derivano un'identità generale dell'eside per l'obiettivo smussato:
  $$\nabla^2 F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)} \left[ H_{\pi_\theta} \cdot \mathbb{E}_\xi[f(x; \xi)] \right]$$
  dove $H_{\pi_\theta}$ è l'eside della densità logaritmica della policy.
• Unificazione degli Stimatori: Questa prospettiva rivela che i classici stimatori di tipo Stein (one-point, two-point, three-point) e gli stimatori a differenza centrale sono casi speciali di questo framework, distinti unicamente dalla scelta del loro baseline (ad esempio, baseline zero, baseline ancora $f(\theta)$, o campionamento antitetico).

2.2. ZoVH: Stimatore dell'Eside con Riduzione della Varianza

Sulla base del framework PO, gli autori introducono ZoVH (Zeroth-Order Variance-reduced Hessian), che impiega due tecniche chiave:

1. Baseline Media Ottimale:

   • A differenza degli stimatori del gradiente dove i baseline sono spesso euristici, gli autori dimostrano che per lo stimatore dell'eside derivato dall'identità rank-one, il baseline medio $\hat{b} = \frac{1}{K}\sum f(x_k)$ è l'unica scelta che preserva l'imparzialità (unbiasedness).
   • Teoricamente, viene dimostrato che questo baseline minimizza la varianza dello stimatore tra tutti i baseline costanti.

2. Strategia di Riutilizzo delle Query:

   • Per ridurre ulteriormente la varianza senza aumentare i costi di query, ZoVH utilizza un buffer di memoria delle query della funzione passate.
   • Ciò viene interpretato come apprendimento off-policy all'interno del framework PO, dove i dati storici (generati dalle iterazioni precedenti) vengono pesati tramite importance sampling per stimare l'eside corrente.
   • Questo aumenta efficacementamente la dimensione del campione da $K$ a $NK$ (dove $N$ è la lunghezza della storia) senza ulteriori valutazioni della funzione.

2.3. Approssimazioni dell'Inverso Efficienti

Per abilitare aggiornamenti pratici di secondo ordine, il paper estende ZoVH per approssimare l'inverso dell'eside e il prodotto inverso eside-gradiente:

• Inverso dell'Eside: Utilizza l'identità di Woodbury per calcolare efficientemente l'inverso dello stimatore dell'eside rank-$K$ regolarizzato ($O(K^2 d)$ o $O(Kd)$ con approssimazione diagonale) senza invertire una matrice densa $d \times d$.
• Prodotto Corretto dal Bias: Quando vengono utilizzate le stesse direzioni casuali sia per la stima del gradiente che per quella dell'eside (per risparmiare query), viene introdotto un bias di correlazione. Gli autori propongono una strategia "leave-one-out" per correggere questo bias, consentendo il calcolo efficiente di $(\nabla^2 F + \lambda I)^{-1}\nabla F$ con un overhead minimo.

3. Contributi Chiave

1. Prospettiva PO Unificata: Ha stabilito un'equivalenza teorica tra gli stimatori generali dell'eside ZO e l'eside di un obiettivo PO smussato, unificando gli stimatori randomizzati classici come istanze specifiche della selezione del baseline.
2. Algoritmo ZoVH: Ha sviluppato una suite completa di stimatori con riduzione della varianza per l'eside completo, il suo inverso regolarizzato e il prodotto inverso eside-gradiente corretto dal bias.
3. Garanzie Teoriche:
   • Ha dimostrato l'imparzialità (unbiasedness) dello stimatore dell'eside con il baseline medio.
   • Ha dimostrato l'ottimalità della varianza del baseline medio.
   • Ha fornito limiti di errore per l'intera suite ZoVH (decomposizione bias-varianza).
   • Ha stabilito garanzie di convergenza per il risultante algoritmo ZO consapevole della curvatura verso un punto stazionario $\epsilon$.
4. Efficienza Pratica: Ha introdotto un meccanismo di riutilizzo delle query che migliora l'efficienza del campionamento senza gonfiare il budget di query, e ha derivato approssimazioni dell'inverso stabili adatte a problemi ad alta dimensionalità come il fine-tuning di LLM.

4. Risultati Sperimentali

Gli autori hanno validato ZoVH attraverso benchmark sintetici, addestramento di reti neurali e attacchi avversari black-box.

• Accuratezza della Stima dell'Eside:

  • Su funzioni sintetiche (Quadratic, Rosenbrock, Styblinski-Tang) e strati CNN, ZoVH (con riutilizzo delle query, $N=4$) ha costantemente ottenuto l'errore della norma di Frobenius più basso rispetto ai classici stimatori Stein e a differenza centrale.
  • ZoVH ($N=1$) ha mostrato un miglioramento dell'accuratezza di 8 volte rispetto allo stimatore a differenza centrale su funzioni Quadratic e Rosenbrock.
  • Sugli strati CNN, ZoVH ($N=4$) ha ottenuto una riduzione dell'errore di 9 volte rispetto allo stimatore a differenza centrale.

• Convergenza dell'Ottimizzazione:

  • In compiti di ottimizzazione sintetica, ZoVH ($N=4$) ha superato significativamente Vanilla ZOO, HiZOO e ZoAR sia in velocità di convergenza che in accuratezza finale, ottenendo un accelerazione media di 22 volte rispetto a Vanilla ZOO.
  • Negli Attacchi Avversari Black-Box, ZoVH ($N=4$) ha richiesto 4 volte meno iterazioni per ottenere un attacco riuscito rispetto a Vanilla ZOO.

• Fine-Tuning di LLM:

  • Applicato al fine-tuning di modelli OPT-1.3B e OPT-13B su compiti GLUE/SuperGLUE.
  • ZoVH ha dimostrato una convergenza più veloce e una maggiore accuratezza nei test rispetto a MeZO e HiZOO.
  • L'overhead di runtime e memoria è stato minimo, con ZoVH che è solo leggermente più lento di MeZO e utilizza una memoria trascurabile (memorizzando solo valori scalari e seed).

5. Significato e Rivendicazioni

Il paper sostiene che ZoVH fornisca una base robusta per l'ottimizzazione senza derivate consapevole della curvatura. Collegando il divario tra l'approssimazione ZO e l'Ottimizzazione della Policy, il lavoro offre:

• Chiarezza Teorica: Una derivazione rigorosa che spiega perché certi stimatori funzionano e come ottimizzarli tramite la selezione del baseline.
• Utilità Pratica: Un metodo che raggiunge una precisione di stima e una performance di convergenza superiori in applicazioni reali (inclusi gli LLM) senza i costi proibitivi degli schemi a differenza finita completi.
• Scalabilità: La capacità di gestire problemi ad alta dimensionalità (ad esempio, milioni di parametri negli LLM) attraverso approssimazioni dell'inverso efficienti e il riutilizzo delle query, rendendo l'ottimizzazione del secondo ordine fattibile in contesti black-box dove prima era impraticabile.

Gli autori sottolineano che, sebbene il metodo introduca un bias di smussamento (inerente ai metodi ZO), i guadagni nella riduzione della varianza e nell'efficienza delle query superano significativamente questo compromesso, portando a una convergenza più rapida e stabile in ambienti rumorosi e ad alta dimensionalità.