Better Privacy Guarantees for Larger Groups

Sintesi Tecnica: Migliori Garanzie di Privacy per Gruppi Più Grandi

Problema
Questo articolo affronta un problema aperto posto da Pujol e Desfontaines [2023] riguardante la progettazione di istogrammi privati per gruppi fissi e disgiunti. I meccanismi standard di privacy differenziale tipicamente aggiungono rumore di una magnitudo fissa a ogni conteggio, fornendo un errore assoluto uniforme ma risultando in errori relativi significativamente più piccoli per i gruppi grandi rispetto a quelli piccoli. La questione centrale è se sia possibile "spendere" questo surplus di accuratezza in modo diverso: permettendo l'errore di un gruppo di scalare proporzionalmente al suo conteggio ($x_i$) per fornire garanzie di privacy più forti (un budget di privacy minore) per i membri di gruppi più grandi.

L'articolo investiga questo scenario sotto il modello di adiacenza "add-or-remove-one" (aggiungi o rimuovi uno). L'obiettivo è trovare un meccanismo in cui il budget di privacy $v(n)$ dipenda solo dal conteggio del gruppo $n$, sia non crescente e soddisfi la zero-concentrated differential privacy (zCDP) per gruppo dipendente dal conteggio. Ciò richiede di limitare la divergenza di Rényi in entrambe le direzioni per ogni ordine $\alpha > 1$ tra dataset adiacenti.

Un ostacolo tecnico critico identificato è la condizione al contorno allo zero. La formulazione originale richiedeva che l'errore assoluto atteso fosse strettamente minore di $r x_i$. Per $x_i = 0$, ciò implica $E|\hat{x}_i| < 0$, il che è impossibile. Inoltre, rilassare la disuguaglianza in $\leq$ mantenendo una divergenza di Rényi finita bidirezionale attraverso l'arco $0 \leftrightarrow 1$ porta a una contraddizione (costringendo l'output al conteggio 1 a essere deterministico, violando il limite dell'errore).

Metodologia e Formulazione Riparata
Per risolvere il problema del contorno, gli autori propongono una "formulazione riparata" del requisito di utilità:
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
Questo mantiene il target dell'errore relativo per tutti i conteggi positivi introducendo al contempo una tolleranza assoluta fissa a zero, rendendo il problema fattibile.

L'articolo impiega due approcci metodologici primari:

1. Fattibilità (Limite Superiore): Gli autori specializzano un esistente framework di "trasformazione traslata" (Finley et al. [2026]). Trasformano lo spazio dei conteggi tramite un logaritmo con un offset $c$ (ovvero $\log(x_i + c)$), aggiungono rumore Gaussiano a varianza fissa e applicano un drift deterministico prima di esponentiare e ritagliare (clipping).

   • Innovazione Chiave: A differenza dei meccanismi log-normal standard che utilizzano un drift di $-\sigma^2/2$ per garantire l'imparzialità della media (mean-unbiasedness), questo meccanismo utilizza un drift di $-\sigma^2$. Questo specifico drift è scelto per minimizzare l'errore moltiplicativo assoluto atteso, che si allinea con la metrica di utilità dell'articolo.
   • Meccanismo di Privacy: Lavorando nello spazio logaritmico con varianza uguale, il meccanismo assicura che la divergenza di Rényi tra conteggi adiacenti sia finita per tutti gli ordini $\alpha$, evitando l'ostruzione del "tail" (coda) dove le varianze diseguali causano una divergenza infinita in una direzione.

2. Impossibilità (Limite Inferiore): Gli autori dimostrano che nessun meccanismo che soddisfi la formulazione riparata dell'utilità e i requisiti di zCDP dipendente dal conteggio può ottenere un tasso di decadimento del budget di privacy più veloce dell'inverso del quadrato del conteggio.

   • Argomento a due conteggi: Un test tra due conteggi specifici stabilisce l'esponente $n^{-2}$.
   • Argomento a molti conteggi: Utilizzando una variabile casuale di "offset nascosto" e argomenti informativi, gli autori derivano un limite inferiore più stretto sul coefficiente principale del budget di privacy.

Risultati Chiave

• Tasso Asintotico Ottimale: Per ogni $0 < r < 1$ fissato, il budget di privacy ottimale $v(n)$ decade come $\Theta_r(n^{-2})$.

  • Limite Superiore: Il meccanismo Gaussiano log-traslato raggiunge $v(n) = O_r(n^{-2})$. Nello specifico, per $n \to \infty$, $v(n) \approx \frac{1}{2\sigma^2 n^2}$.
  • Limite Inferiore: Qualsiasi meccanismo che soddisfi i requisiti deve avere $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$. Ciò conferma che il tasso inverso-quadrato è intrinseco e non un artefatto della costruzione.

• Coefficienti Principali: L'articolo restringe il divario tra il miglior limite superiore e il limite inferiore per il coefficiente principale $C^*$ nel limite di $r$ piccolo e $n$ grande:
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  Il rapporto tra questi limiti è circa 2.995, indicando che i limiti sono entro un fattore tre.

• Fallimento della Gaussiana a Varianza Disuguale: L'articolo dimostra che un meccanismo ingenuo che rilascia $N(n, r^2 n^2)$ (rumore Gaussiano con varianza proporzionale al quadrato del conteggio) fallisce la definizione di zCDP. Sebbene abbia la scala di errore corretta, le varianze diseguali tra conteggi adiacenti causano una divergenza di Rényi infinita in una direzione per ordini $\alpha$ sufficientemente elevati, violando il requisito "per tutti gli ordini" di zCDi.

• Caso Trivial: A $r=1$, un rilascio indipendente dai dati (ad esempio, restituire sempre $0.5$) soddisfa il criterio riparato con perdita di privacy nulla ($v \equiv 0$).

Significato e Rivendicazioni
L'articolo sostiene di fornire la prima prova indipendente dal meccanismo che il tasso inverso-quadrato è ottimale per questa specifica formulazione della privacy di gruppo.

• Fattibilità: Stabilisce che la formulazione "riparata" è risolvibile e fornisce un meccanismo concreto e composibile (log-Gaussiano traslato) che raggiunge il tasso ottimale.
• Ottimalità: Dimostra che nessun meccanismo, indipendentemente dalla complessità o dalla struttura di correlazione, può migliorare il tasso di decadimento $n^{-2}$.
• Precisione: Utilizzando argomenti di informazione su molti conteggi, l'articolo stringe significativamente i limiti sul coefficiente principale rispetto alle precedenti analisi a due conteggi, riducendo l'incertezza a un fattore inferiore a tre.

Gli autori dichiarano esplicitamente che determinare il valore esatto del coefficiente ottimale $C^*$ rimane una questione aperta. Notano inoltre che i loro risultati si applicano a gruppi fissi e disgiunti; gruppi sovrapposti o dipendenti dai dati richiederebbero un'analisi di sensibilità separata. Il meccanismo è distorto (a causa del drift $-\sigma^2$) ma è calibrato specificamente per minimizzare l'errore assoluto atteso, non per essere imparziale.