Quadratic Objective Perturbation: Curvature-Based Differential Privacy

Riepilogo Tecnico: Perturbazione Quadratica dell'Obiettivo per ERM con Privacy Differenziale

Enunciato del Problema
Il lavoro affronta la sfida di ottenere la Privacy Differenziale (DP) nei problemi di Minimizzazione del Rischio Empirico (ERM), in particolare negli ambienti moderni di apprendimento automatico dove i dati sono sensibili e i modelli sono spesso sovrapparametrizzati. La formulazione standard prevede la minimizzazione di una somma di funzioni di perdita convesse più un regolarizzatore su un dataset $D$. Gli approcci esistenti, in particolare la Perturbazione Lineare dell'Obiettivo (LOP), impongono la privacy aggiungendo un termine lineare casuale alla funzione obiettivo. Tuttavia, la LOP si basa sull'assunzione forte che i gradienti delle funzioni di perdita siano limitati uniformemente. Tale assunzione è frequentemente violata nell'apprendimento profondo moderno e nei sistemi sovrapparametrizzati, dove i gradienti possono essere illimitati, rendendo la LOP inapplicabile o richiedendo meccanismi di clipping irrealistici che degradano l'utilità.

Metodologia: Perturbazione Quadratica dell'Obiettivo (QOP)
Gli autori propongono la Perturbazione Quadratica dell'Obiettivo (QOP), un meccanismo che perturba la funzione obiettivo con una forma quadratica casuale anziché lineare. Invece di risolvere il problema originale, il meccanismo risolve:
$$\theta_{priv} = \arg\min_{\theta \in C} \left\{ J(\theta; D) + \frac{\sigma^2}{2}(\theta - \tilde{\theta}^*)^T W (\theta - \tilde{\theta}^*) \right\}$$
dove $W$ è una matrice casuale estratta da una distribuzione (specificamente un insieme di Wishart) e $\tilde{\theta}^*$ è un'approssimazione di un minimizzatore comune delle funzioni di perdita.

Le caratteristiche metodologiche chiave includono:

1. Privacy Basata sulla Curvatura: A differenza della LOP, che sposta il minimizzatore e richiede gradienti limitati per controllare la sensibilità, la QOP modifica la curvatura dell'obiettivo. Il termine quadratico casuale induce una forte convessità, e la sensibilità dell'output è controllata attraverso le proprietà spettrali (autovalori) della matrice casuale $W$.
2. Regime di Interpolazione: L'analisi presuppone l'esistenza di un minimizzatore comune $\theta^*$ per tutte le singole funzioni di perdita (il regime di interpolazione), una condizione standard nell'apprendimento sovrapparametrizzato dove è raggiungibile una perdita di training nulla.
3. Soluzioni Approssimate: Il quadro si estende a scenari pratici in cui il problema perturbato è risolto in modo approssimato (accuratezza $\tau$) e il punto di ancoraggio $\tilde{\theta}^*$ è un'approssimazione (accuratezza $\eta$) del vero minimizzatore comune. Il meccanismo aggiunge rumore gaussiano alla soluzione approssimata per tenere conto di questi errori.
4. Implementazione Algoritmica: Il problema perturbato risultante mantiene una struttura composita (somma finita liscia + regolarizzatore non liscio + vincoli), permettendo di essere risolto in modo efficiente utilizzando schemi di Scissione a Tre Operatori Stocastici (StoTOS).

Contributi Chiave

1. Nuovo Meccanismo di Perturbazione: Introduzione della QOP, che elimina la necessità dell'assunzione di gradienti limitati richiesta dai precedenti metodi di perturbazione lineare.
2. Analisi della Privacy sotto Assunzioni più Deboli: Una nuova dimostrazione di privacy che garantisce che la privacy differenziale $(\epsilon, \delta)$ possa essere assicurata nel regime di interpolazione senza assumere gradienti limitati. La dimostrazione sfrutta le proprietà spettrali della matrice casuale $W$ per limitare la sensibilità del minimizzatore.
3. Robustezza all'Approssimazione: Estensione delle garanzie di privacy a scenari che coinvolgono risoluzioni inesatte e punti di ancoraggio approssimati, mostrando che una privacy significativa è preservata nonostante queste imperfezioni pratiche.
4. Garanzie di Utilità: Derivazione di limiti sul rischio empirico in eccesso, quantificando il compromesso tra parametri di privacy, accuratezza del risolutore e la distanza tra il vero minimizzatore e il minimizzatore comune.

Risultati

• Confronto Teorico: Il lavoro stabilisce che QOP e LOP soddisfano leggi di scala fondamentalmente diverse. L'analisi teorica mostra che il rischio della LOP scala con il diametro dell'insieme dei vincoli (a causa della sua dipendenza dai limiti dei gradienti), mentre il rischio della QOP rimane stabile e indipendente dal diametro dei vincoli.
• Esperimenti Numerici: I risultati empirici sui minimi quadrati lineari con regressione LASSO confermano le scoperte teoriche. Nei regimi con gradienti illimitati (grandi diametri dei vincoli), il rischio empirico della LOP aumenta significativamente, mentre la QOP rimane stabile. Anche nei regimi a dominio ridotto, la QOP dimostra un rischio empirico inferiore rispetto alla LOP e alla LOP con clipping dei gradienti.
• Efficienza Algoritmica: L'uso di schemi di scissione stocastica permette di risolvere in modo efficiente i problemi perturbati, validando la fattibilità pratica dell'approccio.

Significato e Affermazioni
Il lavoro afferma che la QOP fornisce un'alternativa naturale ai metodi classici di perturbazione dell'obiettivo, in particolare per gli ambienti moderni di apprendimento automatico dove forti assunzioni di regolarità (come gradienti limitati) sono raramente soddisfatte. Spostando il controllo della sensibilità dai limiti dei gradienti alla curvatura dell'obiettivo tramite perturbazioni di matrici casuali, gli autori offrono un quadro che è sia teoricamente solido sotto assunzioni più deboli sia empiricamente superiore in termini di stabilità. Il lavoro suggerisce che le perturbazioni basate sulla curvatura sono un meccanismo più robusto per bilanciare privacy e utilità nei modelli sovrapparametrizzati. Gli autori notano che il lavoro futuro potrebbe concentrarsi sul rilassare l'assunzione del minimizzatore comune ed esplorare la privacy differenziale di Rényi per garanzie più strette.