How Well Can Differential Privacy Be Audited in One Run?

1. Il Problema

La Privacy Differenziale (DP) è lo standard teorico per proteggere i dati di addestramento nel machine learning. Tuttavia, le prove analitiche che garantiscono i limiti superiori dei parametri di privacy ($\epsilon$) sono spesso lasche o contengono errori di implementazione. Di conseguenza, è nata la necessità di audit empirici per stabilire limiti inferiori reali sulla privacy di un algoritmo.

Esistono due approcci principali:

1. Audit Classico: Esegue l'algoritmo centinaia o migliaia di volte su dataset che differiscono per un solo elemento per stimare le distribuzioni di output. È asintoticamente preciso ma computazionalmente proibitivo.
2. Audit in Una Esecuzione (One-Run Auditing - ORA): Esegue l'algoritmo una sola volta, intervenendo su molti esempi di addestramento simultaneamente. Sebbene sia computazionalmente efficiente e abbia mostrato risultati empirici promettenti (es. su DP-SGD), la sua precisione teorica e i suoi limiti fondamentali non erano stati completamente caratterizzati.

Il paper si pone la domanda: Quanto è preciso l'ORA nel rivelare il vero parametro di privacy di un algoritmo? E quali fattori determinano questo limite?

2. Metodologia e Impostazione

Gli autori analizzano l'ORA attraverso un framework basato sul gioco d'azzardo (guessing-based).

• Setup: Un auditor sceglie un vettore di coppie di opzioni per ogni elemento del dataset. Per ogni elemento, un bit casuale determina quale delle due opzioni viene inserita nel dataset di addestramento.
• Esecuzione: L'algoritmo viene eseguito una sola volta sul dataset generato.
• Guessing: Basandosi sull'output dell'algoritmo, un "indovino" (guesser) tenta di ricostruire i bit casuali scelti. L'auditor può astenersi dal fare una previsione (abstention) se non è sicuro.
• Metrica: L'efficacia è misurata dal rapporto tra le previsioni corrette e il numero totale di previsioni effettuate. L'obiettivo è vedere se questa efficacia può avvicinarsi a quella di un indovino perfetto (che corrisponderebbe al vero $\epsilon$).

Gli autori introducono il concetto di Privacy Loss Distribuzionale (distribuzionale privacy loss) per quantificare l'incertezza dell'auditor sugli altri elementi del dataset quando ne sta tentando di indovinare uno specifico.

3. Contributi Chiave

A. Identificazione dei "Gap" Fondamentali

Il lavoro dimostra che l'ORA non è asintoticamente stretto (cioè non raggiunge il vero $\epsilon$) per tutti gli algoritmi. Identificano tre "gap" fondamentali che limitano l'efficacia dell'ORA:

1. Gap della Privacy Non-Peggiorativa per gli Elementi (Non-worst-case privacy for elements):

   • La DP è definita dal caso peggiore per ogni elemento. L'ORA, per ottenere un numero sufficiente di previsioni, deve fare previsioni su elementi che potrebbero non subire la perdita di privacy massima in quel particolare output.
   • Esempio: L'algoritmo "Name and Shame" che sceglie un elemento a caso e lo stampa. L'ORA deve indovinare su molti elementi non esposti, abbassando l'efficacia media verso il 50%.

2. Gap degli Output Non-Peggiorativi (Non-worst-case outputs):

   • La DP considera il caso peggiore tra tutti gli output possibili. L'ORA esegue l'algoritmo una sola volta; se l'output generato è "sicuro" (non peggiorativo), l'auditor non può rilevare la vera privacy.
   • Esempio: L'algoritmo "All or Nothing" che stampa l'input solo con probabilità $p$. Se $p$ è basso, l'auditor vede spesso null e non può indovinare nulla.

3. Gap di Interferenza (Interference Gap):

   • Questo è il contributo più significativo. Se l'output dell'algoritmo aggrega informazioni da più elementi (es. una somma o un XOR), l'effetto di un singolo elemento è "misto" con gli altri.
   • Nella definizione di DP, l'avversario conosce tutti gli input tranne uno. Nell'ORA, l'auditor non conosce gli altri input (sono stati campionati casualmente). Questa incertezza sugli altri elementi impedisce di isolare l'effetto del singolo elemento.
   • Esempio: L'algoritmo XOR. L'output è la somma modulo 2 di tutti gli input. Senza conoscere gli altri bit, l'auditor non può fare meglio del caso (50% di accuratezza), anche se l'algoritmo non è affatto privato.

B. Caratterizzazione Teorica dell'Efficacia Ottimale

Gli autori formalizzano l'efficacia massima raggiungibile dall'ORA utilizzando nuove nozioni di privacy rilassata:

• DDP (Distributional Differential Privacy): Relativa al gap di interferenza.
• AC-DDP (Average-Case DDP): Relativa agli output non peggiorativi.
• AE-AC-DDP (Average-Element AC-DDP): Relativa alla privacy non peggiorativa per gli elementi.

Dimostrano che l'efficacia ottimale dell'ORA è limitata da queste misure rilassate e non dal vero $\epsilon$ dell'algoritmo, a meno che l'algoritmo non soddisfi condizioni specifiche (es. essere "locale" o avere perdite di privacy isolate).

C. Nuovi Approcci per Mitigare l'Interferenza

Per superare il gap di interferenza, specialmente in algoritmi complessi come DP-SGD (Stochastic Gradient Descent con privacy), propongono due strategie:

1. Multi-elemento per Coordinata: Invece di assegnare un solo elemento di audit per ogni dimensione del modello (come fatto in lavori precedenti), assegnarne più di uno. Questo aumenta il numero di potenziali previsioni corrette, bilanciando il costo dell'interferenza aggiuntiva. Gli esperimenti mostrano che un numero ottimale di elementi per coordinata migliora i limiti di privacy stimati.
2. Adaptive ORA (AORA): Una nuova variante in cui l'indovino può usare i valori reali dei bit già indovinati per migliorare la previsione degli elementi successivi.
   • Teorema: AORA è valida (garantisce limiti inferiori corretti) e riduce drasticamente il gap di interferenza.
   • Risultato: Per algoritmi come XOR o Count-In-Sets, AORA raggiunge un'efficacia perfetta, mentre l'ORA classica fallisce completamente.

4. Risultati Sperimentali

Gli autori hanno testato le loro teorie su DP-SGD:

• Interferenza: Hanno confermato che l'interferenza tra gradienti riduce l'efficacia dell'ORA.
• Ottimizzazione: Mostrano che aumentare il numero di elementi di audit per coordinata (fino a un certo punto) migliora la stima di $\epsilon$, superando i risultati ottenuti con un solo elemento per coordinata.
• AORA vs ORA: L'Adaptive ORA produce limiti di privacy più stretti (più vicini al vero $\epsilon$) rispetto all'ORA non adattiva, specialmente quando il numero di elementi per coordinata è alto, grazie alla sua capacità di "sbloccare" le informazioni man mano che procede.

5. Significato e Implicazioni

Questo lavoro è fondamentale per la comunità della privacy perché:

1. Chiarezza Teorica: Spiega perché l'audit in una sola esecuzione può fallire nel rilevare violazioni della privacy in certi scenari, distinguendo tra limiti computazionali e limiti intrinseci del metodo.
2. Interpretazione dei Risultati: Avverte che un audit ORA che non rileva violazioni non garantisce che l'algoritmo sia sicuro; potrebbe semplicemente essere limitato dal "gap di interferenza".
3. Miglioramento Pratico: Introduce AORA e la strategia dei multi-elementi come metodi pratici per rendere l'audit più efficace e affidabile per algoritmi reali come DP-SGD, senza sacrificare la validità statistica.
4. Sicurezza: Previene l'uso dell'audit come "fig leaf" (scusa) per algoritmi con garanzie di privacy scadenti, fornendo strumenti per una valutazione più rigorosa.

In sintesi, il paper trasforma l'audit della privacy da una "scatola nera" empirica a una disciplina con limiti teorici ben definiti e strategie concrete per massimizzarne l'efficacia.