Universal Shuffle Asymptotics: Sharp Privacy Analysis in the Gaussian Regime

1. Problema e Contesto

Il lavoro si concentra sul modello di shuffle per la privacy differenziale (DP), un paradigma che interpola tra il modello locale (LDP) e quello centrale (CDP). In questo modello, $n$ utenti applicano un randomizzatore locale a un bit di dati e inviano i messaggi a uno "shuffler" fidato, che permuta casualmente i messaggi prima di inviarli all'analista. L'analista osserva solo l'istogramma (il conteggio delle occorrenze) dei messaggi, non la loro provenienza.

Il problema principale affrontato è la mancanza di analisi sharp (precise) a livello di esperimento per l'amplificazione della privacy ottenuta tramite lo shuffle. La letteratura esistente fornisce spesso limiti di ordine (rate) o costanti asintotiche generiche, ma manca di:

• Espansioni esatte per divergenze di ordine superiore (come la Divergenza di Jensen-Shannon).
• Curve di privacy $(\varepsilon, \delta)$ complete e limitate per $n$ finito.
• Una corretta caratterizzazione della covarianza nei regimi di composizione proporzionale.
• Una teoria unificata che colleghi l'asintotica gaussiana alla struttura esatta dei likelihood ratio.

L'articolo si focalizza sul regime gaussiano, definito da randomizzatori locali con output finito e supporto completo (full support), dove gli esperimenti di shuffle adiacenti sono asintoticamente equivalenti a uno shift gaussiano unidimensionale.

2. Metodologia

L'autore sviluppa un quadro teorico basato su due pilastri strutturali:

1. Identità Esatte del Likelihood Ratio:

   • Per la coppia canonica di dataset adiacenti (uno con tutti gli 0, l'altro con un singolo 1), viene dimostrata un'identità lineare esatta per il likelihood ratio in termini di una statistica di punteggio media.
   • Per coppie generali, il likelihood ratio è espresso come un'aspettativa condizionata di un incremento di punteggio dato l'istogramma osservato.

2. Linearizzazione dell'Aspettativa Condizionata:

   • Viene provato un teorema completo di linearizzazione dell'aspettativa condizionata con resti espliciti su un "typical set" (insieme tipico).
   • La dimostrazione si avvale di un lemma di rapporto di Edgeworth su reticolo, che permette di approssimare i rapporti di probabilità per somme di vettori one-hot (istogrammi) con errori controllati di ordine superiore.

Assunzioni Chiave:

• Supporto completo ($\delta_{full} > 0$) per garantire che i log-likelihood ratio siano limitati.
• Composizione proporzionale: $k/n \to \pi$, dove $k$ è il numero di utenti con input 1.

3. Contributi Chiave e Risultati

A. Correzione della Covarianza per Composizioni Fisse

Un contributo fondamentale è l'identificazione della covarianza corretta per composizioni proporzionali.

• Molti lavori precedenti utilizzavano la covarianza della miscela i.i.d. ($\Sigma_{mix}$), che è errata per lo shuffle con composizione fissa.
• L'autore dimostra che la covarianza corretta è $\Sigma_\pi = (1-\pi)\Sigma_0 + \pi\Sigma_1$.
• La differenza è un termine di rango uno $\pi(1-\pi)vv^\top$ che, se ignorato, porta a una costante di Fisher sottostimata (e quindi a una stima della privacy troppo ottimistica).

B. Espansioni Sharp della Divergenza di Jensen-Shannon (JSD)

• Coppia Canonica: Viene derivata un'espansione esatta fino all'ordine $O(n^{-3})$ per la JSD, identificando i termini di ordine superiore legati ai momenti della distribuzione locale.
• Composizioni Proporzionali: Viene stabilito che il termine principale della JSD è universale e dato da:
  $$\text{JSD}(T_{n,k} \| T_{n,k+1}) = \frac{I_\pi}{8n} + O(n^{-2})$$
  dove $I_\pi = v^\top \Sigma_\pi^+ v$ è la costante di Fisher corretta. Questo risolve il problema aperto di ottenere un resto uniforme $O(n^{-2})$ per tutte le composizioni proporzionali.

C. Equivalenza alla Privacy Differenziale Gaussiana (GDP)

• Viene stabilita l'equivalenza asintotica tra l'esperimento di shuffle e un esperimento di shift gaussiano $G_{\mu_n}$ con parametro $\mu_n = \sqrt{I_\pi/n}$.
• Vengono forniti limiti di Berry-Esseen espliciti di ordine $O(n^{-1/2})$ per la distribuzione del log-likelihood ratio sotto entrambe le ipotesi (nulla e alternativa).
• Questo permette di derivare la curva di privacy $(\varepsilon, \delta)$ limite completa e di fornire correzioni quantitative per $n$ finito.

D. Local Asymptotic Normality (LAN) e Equivalenza di Le Cam

• L'articolo dimostra la proprietà LAN per il modello di shuffle, mostrando che la distanza di Le Cam tra l'esperimento di shuffle e l'esperimento gaussiano corrispondente è dell'ordine $O(n^{-1/2})$.
• Ciò implica che la statistica di punteggio scalare è asintoticamente sufficiente per qualsiasi test o funzione di privacy.

E. Confronto tra Modelli "Bundled" e "Unbundled"

• Viene analizzato il modello unbundled (multi-messaggio), dove ogni utente invia $m$ messaggi indipendenti che vengono permutati singolarmente.
• Si dimostra che per $m \ge 2$, lo shuffle unbundled offre una privacy strettamente migliore rispetto al modello bundled (dove i $m$ messaggi sono trattati come un singolo messaggio in un alfabeto più grande).
• Il parametro GDP per il modello unbundled è $\mu_{unb} = \sqrt{m I_\pi / n}$, mentre per il modello bundled è $\mu_{bund} = \sqrt{((1+\chi^2)^m - 1)/n}$. Poiché $\mu_{unb} < \mu_{bund}$, l'approccio unbundled è superiore.

F. Regime di Confine e Applicazioni

• Randomized Response (RR): Viene analizzato il comportamento al confine del regime gaussiano (quando il parametro di privacy locale $\varepsilon_0$ cresce con $n$). Viene fornito un teorema di Berry-Esseen al confine con una dipendenza esplicita dal parametro di scala.
• Stima della Frequenza: Viene presentata un'applicazione pratica per la stima della frequenza con RR shuffle, mostrando come la calibrazione esatta della privacy (basata sulle formule binomiali esatte) permetta di utilizzare meno rumore rispetto ai limiti di amplificazione conservativi.

4. Significato e Impatto

Questo lavoro rappresenta un avanzamento significativo nella teoria della privacy differenziale per diversi motivi:

1. Precisione Quantitativa: Sposta l'analisi da limiti asintotici generici ("order-level") a costanti esatte e curve di privacy complete, essenziali per la progettazione di protocolli reali.
2. Correzione Teorica: Corregge un errore sottile ma diffuso nella letteratura riguardante la covarianza nelle composizioni proporzionali, che influenzava direttamente la stima della privacy.
3. Unificazione: Fornisce un quadro unificato che collega divergenze di f-divergence, privacy differenziale gaussiana (GDP) e teoria asintotica classica (LAN, Edgeworth) nel contesto dello shuffle.
4. Guida Pratica: Offre formule computabili per la calibrazione della privacy in scenari reali (es. stima di frequenza) e dimostra i vantaggi pratici di modelli di shuffle multi-messaggio non aggregati (unbundled).

In sintesi, il documento stabilisce una "teoria della privacy a livello di esperimento" per il regime gaussiano, fornendo gli strumenti matematici necessari per ottenere stime di privacy ottimali e non conservative.