Optimal Rates for Pure {\varepsilon}-Differentially Private Stochastic Convex Optimization with Heavy Tails

1. Il Problema

Il lavoro si concentra sul problema dell'Ottimizzazione Convoca Stocastica (SCO) in un contesto di Privacy Differenziale Pura ($\varepsilon$-DP).

• Obiettivo: Minimizzare il rischio eccessivo $F(w) - \min_{w'} F(w')$ per una funzione di perdita convessa $F(w) = \mathbb{E}_{z \sim P}[f(w, z)]$, dove i dati provengono da una distribuzione sconosciuta $P$.
• Vincolo di Privacy: L'algoritmo deve soddisfare la privacy differenziale pura ($\delta = 0$), che garantisce che non vi sia alcuna probabilità di una violazione catastrofica della privacy, a differenza della privacy approssimata $(\varepsilon, \delta)$.
• Sfida dei "Coda Pesante" (Heavy Tails): A differenza della letteratura precedente che assume gradienti limitati uniformemente (parametro di Lipschitz $L$ finito), questo lavoro assume solo che i gradienti abbiano un momento $k$-simo limitato ($\mathbb{E}[\|\nabla f\|^k] \le G_k^k$). Questo permette distribuzioni di gradienti non limitate e con code pesanti, tipiche in scenari reali (es. regressione lineare con feature non limitate), rendendo i limiti basati su $L$ troppo pessimistici o vuoti.

Il gap principale affrontato è che, mentre i tassi ottimali per la privacy approssimata $(\varepsilon, \delta)$ in questo setting sono noti, il caso della privacy pura $\varepsilon$-DP rimaneva aperto, senza algoritmi noti che raggiungessero i limiti minimax teorici.

2. Metodologia

L'approccio proposto si discosta dai metodi standard basati su gradienti rumorosi e troncamento (clipped gradients), che si sono rivelati subottimali per la privacy pura a causa della mancanza di tecniche di composizione avanzate.

La metodologia si basa su tre pilastri principali:

1. Estensione di Lipschitz (Lipschitz Extension):
   Invece di trancare i gradienti, l'autore trasforma la funzione di perdita originale $f$ in una sua estensione di Lipschitz $f_C$:
   $$f_C(w, z) := \inf_{y \in W} [f(y, z) + C\|w - y\|]$$
   Questa trasformazione converte il problema di ottimizzazione con gradienti a coda pesante in un problema di ottimizzazione con una funzione $C$-Lipschitziana, controllando il "bias" introdotto dall'estensione attraverso l'assunzione sul momento $k$-simo.

2. Localizzazione tramite Perturbazione dell'Output:
   Poiché il bias dell'estensione di Lipschitz scala con il diametro dell'intero dominio $W$ (troppo grande), l'algoritmo utilizza un passo di localizzazione:

   • Si risolve un problema regolarizzato sull'estensione di Lipschitz.
   • Si aggiunge rumore di Laplace alla soluzione ottenuta (perturbazione dell'output) per ottenere un sottoinsieme più piccolo $W_0 \subset W$ che contiene il minimizzatore con alta probabilità.
   • Il bias viene quindi ridotto scalando con il diametro di $W_0$ (molto più piccolo di $W$).

3. Riformulazione Convessa Congiunta e Subgradiente Adattivo:
   Minimizzare l'estensione di Lipschitz è computazionalmente difficile (spesso impossibile in tempo finito esatto). L'autore introduce una riformulazione congiuntamente convessa del problema:
   $$\Phi_Z(w, y_1, \dots, y_n) := \frac{1}{n}\sum_{i=1}^n [f(y_i, z_i) + C\|w - y_i\|] + \frac{\lambda}{2}\|w - w_0\|^2$$
   Per ottimizzare questa funzione senza conoscere il parametro di Lipschitz (che potrebbe essere infinito), viene sviluppato un metodo del subgradiente proiettato adattivo con proiezioni approssimate ($\xi$-inexact). Questo metodo garantisce la convergenza in tempo finito con probabilità 1 e in tempo polinomiale con alta probabilità, anche senza stime a priori della costante di Lipschitz.

L'algoritmo finale, chiamato Localized Double Output Perturbation, combina due passaggi di perturbazione dell'output (uno per la localizzazione del dominio e uno per la privacy della soluzione finale) con l'ottimizzazione efficiente sopra descritta.

3. Contributi Chiave

1. Tasso Minimax Ottimale per $\varepsilon$-DP:
   Il paper caratterizza il tasso di rischio eccessivo minimax ottimale per la SCO con code pesanti sotto privacy pura, fino a fattori logaritmici:
   $$\tilde{O}\left( G_k D \left(\frac{d}{n\varepsilon}\right)^{1-1/k} + \frac{G_2 D}{\sqrt{n}} \right)$$
   Questo tasso è più acuto di quelli basati su $L$ quando i gradienti hanno code pesanti ($G_k \ll L$).

2. Algoritmi in Tempo Polinomiale:
   Viene presentato il primo algoritmo in tempo polinomiale che raggiunge questo tasso ottimale per la privacy pura.

   • Con alta probabilità, il tempo di esecuzione è polinomiale.
   • Se il parametro di Lipschitz nel caso peggiore è finito e polinomialmente limitato, il tempo di esecuzione è polinomiale con probabilità 1.
   • Per classi strutturate (perdite tipo hinge/ReLU e valore assoluto su sfere, ellissoidi e poliedri), l'algoritmo raggiunge il tasso ottimale in tempo polinomiale con probabilità 1 anche se il parametro di Lipschitz è infinito.

3. Nuovi Limiti Inferiori (Lower Bounds):
   Viene dimostrato un nuovo limite inferiore con alta probabilità che è più stretto (migliore per fattori logaritmici) rispetto ai limiti precedenti basati sull'aspettativa (di [BD14]). Il limite combina tecniche di "packing" per la parte privata e costruzioni a due punti per la parte non privata.

4. Impossibilità di Calcolo Esatto:
   Viene provato un risultato di impossibilità: il calcolo esatto dell'estensione di Lipschitz non è possibile in tempo finito partendo da informazioni locali, giustificando la necessità dell'approccio approssimato certificato utilizzato nell'algoritmo.

4. Risultati Principali

• Teorema 3.1 (Main Theorem): L'algoritmo Localized Double Output Perturbation è $\varepsilon$-DP e soddisfa il limite di rischio eccessivo ottimale sopra citato con alta probabilità.
• Efficienza Computazionale: L'algoritmo risolve il problema in tempo polinomiale. Per sottoclassi strutturate (es. perdite lineari, hinge, ReLU su domini compatti), l'efficienza è garantita con probabilità 1 anche in presenza di gradienti illimitati.
• Confronto con lo Stato dell'Arte:
  • Risolve il "gap" della privacy pura per la SCO a code pesanti.
  • Supera i metodi basati su clipping dei gradienti, che sono inefficienti o subottimali per la privacy pura.
  • Fornisce limiti superiori e inferiori che coincidono fino a fattori logaritmici.

5. Significato e Impatto

Questo lavoro è significativo perché:

1. Colma un vuoto teorico fondamentale: Fornisce la prima soluzione efficiente e ottimale per la privacy pura in un setting realistico (gradienti a coda pesante) dove le soluzioni precedenti erano o inefficienti o subottimali.
2. Ridefinisce le garanzie di privacy: Dimostra che è possibile ottenere garanzie di privacy rigorose ($\delta=0$) senza sacrificare l'efficienza computazionale o la precisione statistica, anche quando i dati sono "sporchi" (code pesanti).
3. Innovazione Algoritmica: Introduce un nuovo framework che combina estensioni di Lipschitz, localizzazione adattiva e ottimizzazione convessa congiunta, offrendo strumenti nuovi per la privacy differenziale che vanno oltre il semplice clipping dei gradienti.
4. Applicabilità Pratica: Le condizioni sufficienti per l'efficienza con probabilità 1 (es. perdite hinge/ReLU su domini poliedrici) coprono molti problemi di apprendimento automatico reali, rendendo la teoria immediatamente rilevante per l'addestramento di modelli sensibili.

In sintesi, il paper stabilisce il nuovo standard teorico e pratico per l'ottimizzazione stocastica privata in scenari realistici con dati non limitati, dimostrando che la privacy pura non deve comportare un compromesso eccessivo sulle prestazioni.