Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States

1. Enunciato del Problema

Il documento affronta la sfida di addestrare modelli su larga scala (ad esempio, LLM) sotto vincoli di Privacy Differenziale (DP) gestendo al contempo severe limitazioni di memoria.

• Contesto: I metodi DP di primo ordine standard (come DP-SGD) richiedono l'archiviazione dei gradienti per campione durante la retropropagazione, portando a un enorme sovraccarico di memoria che scala male con la dimensione del modello.
• Tendenza della Soluzione: I metodi di ottimizzazione di ordine zero (ZO) sono emersi come un'alternativa efficiente in termini di memoria perché richiedono solo passaggi in avanti (valutazioni della perdita) e non calcolano gradienti espliciti.
• Il Divario: Sebbene i metodi ZO esistenti (ad esempio, DPZero) funzionino bene empiricamente, la loro analisi teorica della privacy si basa su teoremi di composizione standard. Ciò comporta costi di privacy che crescono linearmente con il numero di passaggi di addestramento ($T$), costringendo a un compromesso tra utilità e privacy.
• La Sfida Principale: Estendere l'Amplificazione della Privacy per Iterazione (PABI) — una tecnica che produce limiti di privacy convergenti (costanti) per i metodi di primo ordine — ai metodi di ordine zero.
  • Perché è difficile: La PABI di primo ordine si basa sull'aggiunta di rumore Gaussiano isotropo (indipendente dalla direzione) ai gradienti, permettendo l'uso di lemmi sulla "divergenza di Rényi spostata". Al contrario, i metodi ZO efficienti aggiungono rumore scalare anisotropo (dipendente dalla direzione) lungo direzioni di aggiornamento casuali. Questa anisotropia rompe la proprietà di Lipschitz globale richiesta dai framework standard di divergenza spostata, rendendo inapplicabili gli strumenti PABI esistenti.

2. Metodologia

Gli autori propongono un nuovo framework che combina un Meccanismo di Rumore Ibrido e un'Analisi di Accoppiamento per aggirare i limiti dell'analisi standard.

A. Meccanismo di Rumore Ibrido (Noisy-ZOGD)

Invece di scegliere tra rumore puramente direzionale (efficiente ma difficile da analizzare) o rumore puramente isotropo (facile da analizzare ma spreco di utilità), gli autori propongono una regola di aggiornamento unificata:
$$w_{t+1} = \Pi_{\mathcal{B}_R} \left[ w_t - \frac{\eta}{K} \sum_{k=1}^K \hat{g}_t(w_t; u_{t,k}) + \frac{\eta}{\sqrt{K}} \sum_{k=1}^K G^{(1)}_{t,k} u_{t,k} + \eta \sqrt{d} G^{(2)}_t \right]$$

• Aggiornamenti $K$-dimensionali: Utilizza $K$ direzioni casuali per passaggio per ridurre la varianza della stima del gradiente.
• Rumore Ibrido:
  1. Rumore Direzionale ($G^{(1)}$): Rumore Gaussiano scalare aggiunto lungo le direzioni di aggiornamento $u_{t,k}$. Questo preserva l'utilità concentrando il rumore dove esiste sensibilità.
  2. Rumore Isotropo ($G^{(2)}$): Piccolo rumore Gaussiano isotropo aggiunto su tutte le dimensioni. Questo è cruciale per l'analisi teorica per gestire lo "spostamento" nel processo di accoppiamento.
• Direzioni Ortonormali: Le direzioni di aggiornamento $\{u_{t,k}\}$ sono campionate come un insieme ortonormale dalla varietà di Stiefel (anziché vettori casuali i.i.d.), il che restringe i limiti di privacy.

B. Nuova Analisi di Accoppiamento (Aggirando la Divergenza Spostata)

La prova PABI standard si basa sul lemma della Divergenza di Rényi Spostata, che richiede una condizione di Lipschitz globale. Poiché la mappa di aggiornamento ZO non è globalmente Lipschitz (solo Lipschitz puntuale con alta probabilità), gli autori costruiscono un processo ausiliario accoppiato $\tilde{W}_t$:

1. Costruzione: Definiscono una traiettoria ausiliaria $\tilde{W}_t$ che si trova "in mezzo" a due processi di addestramento adiacenti ($W_t$ sul dataset $D$ e $W'_t$ sul dataset $D'$).
2. Decomposizione: L'analisi della privacy è divisa in due parti:
   • Limite di Variazione Totale (TV): Misura la probabilità che l'accoppiamento fallisca (cioè che $W_t$ e $\tilde{W}_t$ divergano). Questo è limitato utilizzando la proprietà Lipschitz puntuale dell'aggiornamento ZO (che vale con alta probabilità).
   • Limite di Divergenza di Rényi: Misura la divergenza tra il processo ausiliario $\tilde{W}_t$ e il processo adiacente $W'_t$. Poiché $\tilde{W}_t$ è costruito per allinearsi alla struttura del rumore, questa parte può essere analizzata utilizzando meccanismi Gaussiani spostati standard.
3. Risultato: Questo approccio evita la necessità di una costante di Lipschitz globale, permettendo un limite di privacy convergente anche con rumore anisotropo.

3. Contributi Chiave

1. Prima PABI Convergente per Ordine Zero: Il documento fornisce la prima prova teorica che l'ottimizzazione di ordine zero con stati nascosti raggiunge un limite di privacy convergente (il costo della privacy satura dopo un numero fisso di passaggi) invece di crescere linearmente con $T$.
2. Meccanismo di Rumore Ibrido: Introduce uno schema di iniezione di rumore che bilancia l'utilità (tramite rumore direzionale) e la trattabilità analitica (tramite una piccola componente isotropa).
3. Ruolo della Dimensione di Aggiornamento ($K$):
   • Rivela che, sotto l'analisi degli stati nascosti, aumentare il numero di direzioni di aggiornamento $K$ riduce la perdita di privacy (contrariamente all'analisi di composizione standard dove $K$ aumenta il costo).
   • Dimostra che l'uso di direzioni di aggiornamento ortonormali migliora significativamente i limiti di privacy rispetto alle direzioni casuali i.i.d.
4. Tecnica di Accoppiamento Innovativa: Sviluppa una specifica costruzione di processo ausiliario che aggira la barriera di Lipschitz globale, una tecnica potenzialmente applicabile ad altri contesti di ottimizzazione non lisci o non Lipschitz.

4. Risultati Chiave

• Limite di Privacy: Per perdite lisce e fortemente convesse, l'algoritmo Noisy-ZOGD proposto soddisfa la $(\epsilon, \delta)$-DP con:
  $$\epsilon = O\left( \sqrt{\frac{\Delta^2 \log(1/\delta)}{n^2 \sigma^2} \min\left(T, \frac{R n \sqrt{d}}{K \Delta}\right)} \right)$$
  • Il limite satura a $T \approx \frac{R n \sqrt{d}}{K \Delta}$, il che significa che ulteriori iterazioni non aumentano il costo della privacy.
  • Il limite è inversamente proporzionale a $K$, mostrando che l'uso di più direzioni migliora la privacy.
• Confronto:
  • vs. Composizione Standard: L'analisi standard produce $\epsilon \propto \sqrt{T}$, che cresce senza limiti. Il metodo proposto converge.
  • vs. Perturbazione dell'Output: Sebbene la perturbazione dell'output (aggiunta di rumore solo alla fine) sia indipendente da $T$, è generalmente più debole per $T$ pratici. Il metodo proposto offre un limite più stretto per $T$ intermedi.
• Utilità: Il meccanismo di rumore ibrido mantiene le stesse garanzie di utilità del rumore puramente direzionale (DPZero) perché la varianza totale del rumore è preservata.

5. Significato

• Scalabilità: Questo lavoro permette la giustificazione teorica dell'addestramento di modelli massicci (miliardi di parametri) con DP e memoria limitata, un collo di bottiglia critico nell'attuale fine-tuning degli LLM.
• Progettazione Algoritmica: Ribalta la convinzione che l'uso di più direzioni di ordine zero ($K > 1$) sia puramente un compromesso di utilità. Il documento dimostra che è anche un vantaggio per la privacy, incoraggiando l'uso di aggiornamenti a dimensionalità più elevata negli algoritmi DP-ZO.
• Avanzamento Teorico: Risolvendo il problema del "rumore anisotropo" nella PABI, il documento colma un divario significativo tra la teoria della privacy di primo ordine e di ordine zero, offrendo un nuovo toolkit (accoppiamento con processi ausiliari) per analizzare dinamiche di ottimizzazione complesse e non Lipschitz sotto vincoli di privacy.
• Impatto Pratico: Fornisce linee guida concrete per i praticanti: utilizzare direzioni ortonormali, regolare il parametro di rumore ibrido $\beta_t$ e sfruttare un $K$ più grande per ottenere migliori compromessi privacy-utilità senza aumentare i costi di memoria.