Near-Optimal Private Linear Regression via Iterative Hessian Mixing

Enunciato del Problema
Questo lavoro affronta il problema della Minimizzazione dei Minimi Quadrati Ordinari con Privacy Differenziale (DP-OLS). Dato un dataset $(X, Y)$ dove $X \in \mathbb{R}^{n \times d}$ e $Y \in \mathbb{R}^n$, l'obiettivo è stimare un predittore lineare $\theta$ che minimizzi il rischio empirico $L(\theta) = \|Y - X\theta\|_2^2$ soddisfacendo al contempo la privacy differenziale $(\varepsilon, \delta)$. Gli autori assumono dati limitati ($\|x_i\| \leq C_X, |y_i| \leq C_Y$) e un sistema sovradeterminato ($n \geq d$).

Il lavoro si colloca all'interno della tensione tra privacy e utilità. Sebbene il metodo di Perturbazione Adattiva delle Statistiche Sufficienti (AdaSSP) (Wang, 2018) sia stato il baseline di riferimento, offrendo prestazioni empiriche solide e limiti teorici quasi ottimali, soffre di limiti di errore che includono fattori moltiplicativi dipendenti dalla probabilità di fallimento $\varrho$ e dalla dimensione dei dati $d$. Nello specifico, i limiti possono incorrere in un fattore di $\sqrt{d}$ o $\log(1/\varrho)$ che può diventare proibitivo. Al contrario, gli approcci di schizzo Gaussiano (Sheffet, 2017; Lev et al., 2025) offrono meccanismi alternativi ma sono storicamente stati considerati meno competitivi o privi di garanzie teoriche chiare riguardo a quando superano AdaSSP.

Metodologia: Mixing Iterativo dell'Hessiana (IHM)
Gli autori propongono il Mixing Iterativo dell'Hessiana (IHM), un nuovo algoritmo per DP-OLS che combina lo schizzo Gaussiano con una strategia di raffinamento iterativo ispirata allo Schizzo Iterativo dell'Hessiana (IHS) di Pilanci & Wainwright (2016).

A differenza dei metodi di schizzo standard che applicano una matrice Gaussiana casuale $S$ ai dati concatenati $(X, Y)$, IHM applica il meccanismo di schizzo principalmente all'interno della struttura dell'Hessiana (matrice Gram). L'algoritmo procede iterativamente:

1. Inizializzazione: Iniziare con $\hat{\theta}_0 = \vec{0}_d$.
2. Schizzo: Ad ogni iterazione $t$, campionare una matrice Gaussiana $S_t$ e vettori di rumore $\xi_t, \zeta_t$.
3. Hessiana Schizzata: Calcolare una versione rumorosa e schizzata della matrice del disegno: $\tilde{X}_t = S_t X + \eta \xi_t$.
4. Stima del Gradiente: Calcolare una stima rumorosa e troncata del gradiente: $\tilde{G}_t = X^\top \text{clip}_C(Y - X\hat{\theta}_t) - \eta^2 \hat{\theta}_t + \sigma \zeta_t$.
5. Aggiornamento: Aggiornare la stima utilizzando l'inversa dell'Hessiana schizzata: $\hat{\theta}_{t+1} = \hat{\theta}_t + (\frac{1}{k} \tilde{X}_t^\top \tilde{X}_t)^{-1} \tilde{G}_t$.

Una scelta progettuale critica è che lo schizzo viene applicato a $X$ (all'interno dell'Hessiana) piuttosto che alla coppia completa $(X, Y)$. Ciò permette all'algoritmo di sfruttare il condizionamento di $X$ (specificamente $\lambda_{\min}(X^\top X)$) per ridurre il livello di rumore richiesto, mentre lo schizzo di $(X, Y)$ forza una dipendenza da $\lambda_{\min}((X, Y)^\top (X, Y))$, che è spesso più piccolo e porta a un rumore maggiore.

Contributi Chiave

1. Proposta Algoritmica: L'introduzione di IHM, che adatta il framework IHS al setting della privacy differenziale.
2. Garanzie Teoriche:
   • Privacy: Dimostrazione che IHM soddisfa la $(\varepsilon, \delta)$-DP.
   • Utilità: Derivazione di limiti di rischio empirico in eccesso. Gli autori mostrano che IHM migliora i limiti di AdaSSP rimuovendo un fattore moltiplicativo che può essere grande quanto $\sqrt{d}$. Il limite dipende da $\gamma_h = \sqrt{\max\{d, \log(1/\varrho), g_X\}} \frac{\log(1/\delta)}{\varepsilon}$, dove $g_X$ è correlato al numero di condizionamento di $X$.
3. Rianalisi dello Schizzo Gaussiano: Il lavoro fornisce una nuova analisi di accuratezza per i precedenti metodi di schizzo Gaussiano (in particolare l'approccio di Mixing Lineare di Lev et al., 2025). Questa analisi chiarisce i limiti di questi metodi, in particolare la loro dipendenza dalla perdita residua $L(\theta^*)$ e dal valore minimo dell'autovalore della matrice aumentata $(X, Y)$.
4. Selezione dei Parametri: Gli autori forniscono linee guida pratiche per la scelta degli iperparametri (dimensione dello schizzo $k$, iterazioni $T$ e livello di troncamento $C$) che non richiedono una complessa ottimizzazione dipendente dai dati in molti regimi.

Risultati
Il lavoro presenta una rigorosa valutazione empirica su 33 dataset reali dal repository UCI e dataset sintetici.

• Prestazioni: IHM supera costantemente o eguaglia le prestazioni di AdaSSP e del baseline Mixing Lineare (LinMix) su un'ampia gamma di dataset e livelli di privacy ($\varepsilon \in [0.1, 10]$).
• Regimi: Gli esperimenti dimostrano la superiorità di IHM in vari regimi:
  • Dataset con residui grandi (dove i metodi di schizzo tipicamente faticano).
  • Dataset con $X$ ben condizionato ma $(X, Y)$ mal condizionato (dove il focus di IHM su $X$ offre un vantaggio).
  • Dataset dove $\|\theta^*\|$ è piccolo.
• Robustezza: Anche in impostazioni sintetiche progettate per innescare frequenti troncamenti (violando le assunzioni teoriche), IHM mantiene prestazioni competitive.

Significato e Affermazioni
Il lavoro afferma che IHM rappresenta un passo significativo in avanti nella regressione lineare con privacy differenziale, unificando i benefici dell'efficienza basata sullo schizzo con le forti garanzie teoriche della perturbazione delle statistiche sufficienti.

• Miglioramento Teorico: Rimuovendo il fattore $\sqrt{d}$ presente nei limiti di AdaSSP, IHM raggiunge garanzie di utilità quasi ottimali che sono più vicine ai limiti inferiori informazionali.
• Utilità Pratica: Il metodo offre un'alternativa robusta che non richiede le specifiche condizioni "favorevoli" (ad esempio, basso residuo, relazioni specifiche tra autovalori) di cui i precedenti metodi di schizzo avevano bisogno per superare AdaSSP.
• Direzioni Future: Gli autori notano che, sebbene IHM sia una versione privata dello schizzo di Newton applicato alla perdita quadratica, il lavoro futuro potrebbe esplorare versioni private dello schizzo di Newton per modelli generali e l'uso di proiezioni casuali strutturate per migliorare l'efficienza computazionale.

In sintesi, il lavoro sostiene che, limitando attentamente l'operazione di schizzo all'Hessiana e sfruttando un framework di mixing iterativo, è possibile realizzare un algoritmo di regressione lineare con privacy differenziale che è sia teoricamente superiore ad AdaSSP nella sua scalatura dell'errore sia empiricamente robusto attraverso diverse distribuzioni di dati reali.