Adaptive Power Iteration Method for Differentially Private PCA

Riepilogo Tecnico: Metodo di Iterazione di Potenza Adattiva per PCA con Privacy Differenziale

Enunciato del Problema
Il lavoro affronta il problema del calcolo approssimato del vettore singolare principale di una matrice $A \in \mathbb{R}^{n \times d}$, dove ogni riga rappresenta un punto dati privato. L'obiettivo è progettare un algoritmo che soddisfi la privacy differenziale $(\epsilon, \delta)$ (DP) nel modello standard in cui gli input adiacenti differiscono esattamente per una riga (con norma $\ell_2$ limitata). Sebbene le garanzie nel caso peggiore per questo problema siano ben consolidate (ad esempio, da Dwork et al. [DTTZ14]), spesso producono limiti di errore che scalano con la dimensione ambientale $d$, rendendoli poco pratici per dati ad alta dimensionalità. Il lavoro mira a ottenere garanzie "oltre il caso peggiore" che sfruttino le proprietà strutturali della matrice di input, in particolare la bassa coerenza, senza richiedere la conoscenza a priori di tali parametri.

Metodologia
Gli autori propongono un nuovo algoritmo di Iterazione di Potenza Adattiva (Algoritmo 1). A differenza dei metodi privati standard che aggiungono rumore all'intero passo di aggiornamento basandosi sulla sensibilità nel caso peggiore, questo approccio introduce un meccanismo di filtraggio per ridurre dinamicamente la sensibilità.

1. Filtraggio Adattivo: In ogni iterazione $t$, l'algoritmo filtra le righe $a$ della matrice di input $A$ per le quali il valore $\|a\|_2 |\langle a, x^{(t)} \rangle|$ supera una soglia $\theta^{(t)}$. Questa quantità rappresenta il contributo di un punto dati specifico all'aggiornamento dell'iterazione di potenza.
2. Selezione della Soglia: La soglia $\theta^{(t)}$ non è fissa; è determinata in modo adattivo in ogni iterazione utilizzando la Tecnica del Vettore Spars (specificamente l'algoritmo AboveThreshold). Ciò permette all'algoritmo di trovare una soglia che garantisca che il numero di righe filtrate sia piccolo (circa $\tilde{O}(1/\epsilon)$) mentre si limita la sensibilità del restante aggiornamento.
3. Aggiornamento Privato: Dopo il filtraggio, l'algoritmo esegue un passo di iterazione di potenza sulla matrice filtrata $A^{(t)}$ e aggiunge rumore gaussiano scalato in base alla soglia $\theta^{(t)}$.
4. Quadro di Analisi: L'analisi si discosta dai lavori precedenti (ad esempio, Hardt e Roth [HR13]) che si basavano sulla simmetria del segno delle iterazioni. Gli autori introducono una nuova analisi che traccia due sequenze: $m^{(t)}$ (la componente dell'iterazione lungo il vettore di autovalore principale) e $M^{(t)}$ (il massimo prodotto scalare dell'iterazione con le righe nel sottospazio rimanente). Dimostrano che, nonostante il rumore introdotto dal filtraggio, $m^{(t)}$ cresce esponenzialmente più velocemente di $M^{(t)}$, a condizione che il gap di autovalori $\kappa = (\sigma_1^2 - \sigma_2^2)/\sigma_1^2$ sia sufficientemente grande rispetto al parametro di coerenza.

Contributi Chiave

• Algoritmo Innovativo: Il lavoro presenta il primo metodo di iterazione di potenza privato che ottiene garanzie oltre il caso peggiore per matrici a bassa coerenza nel modello di privacy a livello di riga (dove un singolo cambiamento di riga è limitato in norma $\ell_2$).
• Tecnica di Filtraggio Adattivo: L'introduzione di un passo di filtraggio adattivo che rimuove i contributi "outlier" all'iterazione di potenza, permettendo alla scala del rumore di adattarsi alla struttura effettiva dei dati piuttosto che al limite del caso peggiore.
• Adattamento Senza Parametri: L'algoritmo non richiede la conoscenza a priori del parametro di coerenza $\Upsilon$ o del gap di autovalori $\kappa$; si adatta automaticamente ad essi.
• Garanzie Teoriche:
  • Caso Deterministico: Per matrici deterministiche a bassa coerenza, l'algoritmo ottiene un limite di errore che migliora lo stato dell'arte [DTTZ14] e [dN26] nei regimi in cui la coerenza è piccola e il gap di autovalori non è troppo ridotto. Nello specifico, l'errore scala con $\Upsilon^2$ e il gap di autovalori, piuttosto che solo con la dimensione $d$.
  • Caso Stocastico (Gaussiano): Per dati i.i.d. campionati da una distribuzione gaussiana, l'algoritmo fornisce garanzie di errore che si confrontano favorevolmente con i risultati dello stato dell'arte [LKJO22], in particolare in termini di requisiti di complessità del campione e intervallo di parametri di privacy validi $\epsilon$.

Risultati
Il principale risultato teorico (Teorema 1.1 e Corollario 1.1) stabilisce che per una matrice $A$ con gap di autovalori $\kappa$ e parametro correlato alla coerenza $\Upsilon$, l'algoritmo restituisce un vettore $x$ tale che:
$$\sin^2(v_1, x) \leq \tilde{O}\left( \frac{\min\{4n/\sigma_1^2, d\}\Upsilon^2 + \sigma_1^2\Upsilon^2/\kappa + d\sigma_1^2\Upsilon^2\kappa}{\epsilon^2(\sigma_1^2 - \sigma_2^2)^2} \right)$$
Si dimostra che questo limite è superiore a [DTTZ14] quando $\Upsilon$ è piccolo (ad esempio, $\Upsilon \approx 1/\sqrt{n}$ per dati casuali) e $\kappa$ non è estremamente piccolo.

Nel contesto i.i.d. gaussiano (Teorema 1.2), l'errore è limitato da:
$$\sin^2(v_1, x) \leq \tilde{O}\left( \frac{d}{\epsilon^2 n^2 \sigma_1^2 \kappa^2} + \frac{1}{\epsilon^2 n^2 \sigma_1^2 \kappa^3} + \frac{1}{n \sigma_1^2 \kappa^2} + \frac{1}{n^2 \sigma_1^4 \kappa^2} \right)$$
Questo risultato vale per dimensioni del campione $n \geq \tilde{\Omega}(d + \frac{1}{\epsilon \sigma_1^2 \kappa})$, che rappresenta un miglioramento significativo rispetto ai lavori precedenti che richiedevano una complessità del campione esponenziale per gap di autovalori piccoli o $\epsilon$ ristretti.

Significato
Il lavoro afferma di risolvere una questione aperta riguardante la possibilità di ottenere garanzie oltre il caso peggiore per la PCA privata nel modello naturale di privacy a livello di riga. Combinando il filtraggio adattivo con un'analisi raffinata della convergenza del metodo delle potenze, il lavoro dimostra che proprietà strutturali come la bassa coerenza possono essere sfruttate per ridurre significativamente l'errore degli algoritmi privati senza compromettere la privacy. Gli autori collocano questo lavoro come un complemento a Hardt e Roth [HR13], estendendo le loro intuizioni "oltre il caso peggiore" a un modello di privacy più generale e naturale in cui l'intera riga è l'unità di privacy, piuttosto che le singole voci. I risultati suggeriscono che per molte applicazioni pratiche che coinvolgono dati strutturati o casuali, la PCA privata può essere eseguita con un'utilità molto superiore a quanto precedentemente ritenuto possibile sotto le assunzioni del caso peggiore.