Exactly Optimal and Communication-Efficient Private Estimation via Block Designs

Sintesi Tecnica: Stima Privata Esattamente Ottimale e Comunicativamente Efficiente tramite i Disegni a Blocchi

Formulazione del Problema
Il documento affronta il problema della stima privata di distribuzioni discrete nel framework della Local Differential Privacy (LDP). In questo contesto, $n$ client osservano punti dati $X_i$ estratti da una distribuzione ignota $P$ su un dominio di dimensione $v$. Ogni client applica un meccanismo di privacy $Q$ per generare un output privatizzato $Y_i$ che soddisfi l' $\epsilon$-LDP prima di inviarlo a un server centrale. Il server costruisce quindi uno stimatore $\hat{P}_n$ per recuperare $P$. L'obiettivo è minimizzare il rischio nel caso peggiore (errore di stima) sotto una specifica funzione di perdita (principalmente $\ell_u^u$ per $1 \le u \le 2$) e, simultaneamente, minimizzare il costo di comunicazione, definito come la dimensione dell'alfabeto di output $b = |\mathcal{Y}|$.

Sebbene lo schema di Subset Selection (SS) sia noto per raggiungere l'esatto trade-off ottimalità-privacy per tutti i $(v, \epsilon)$, esso soffre di costi di comunicazione proibitivi (esponenziali in $v$). Al contrario, schemi comunicativamente efficienti come l'Hadamard Response (HR) e il Projective Geometry Response (PGR) spesso raggiungono solo prestazioni di ordine ottimale o quasi-ottimali, con gap di prestazione che diventano significativi nei regimi di privacy intermedia. Il documento mira a colmare questo divario trovando schemi che siano sia esattamente ottimali (o quasi-ottimali) che comunicativamente efficienti.

Metodologia
Gli autori propongono una nuova classe di schemi LDP basati sui disegni a blocchi combinatori e su una classe più ampia chiamata Disegni Regolari e Bilanciati a Coppie (RPBD).

1. Schemi di Disegno a Blocchi:

   • Il meccanismo è costruito utilizzando una struttura di incidenza $(X, Y, I)$ dove $X$ è il dominio di input e $Y$ è il dominio di output.
   • La struttura è definita dai parametri $(v, b, r, k, \lambda)$, che rappresentano la dimensione di input, la dimensione di output, la regolarità, l'uniformità e il bilanciamento a coppie, rispettivamente.
   • Il meccanismo produce un elemento $y \in I_x$ con probabilità proporzionale a $e^\epsilon$ e un elemento in $Y \setminus I_x$ altrimenti.
   • Viene derivato un stimatore non distorto canonico basato sui conteggi degli output che cadono in set specifici.
   • Insight Chiave: Gli autori stabiliscono che, per una dimensione di input $v$ fissa e un budget di privacy $\epsilon$, il rischio di uno schema a blocchi dipende solo dal parametro $k$ (la dimensione dell'intersezione tra i set di input e output), non da $b$, $r$ o $\lambda$. Nello specifico, due schemi a blocchi con lo stesso $k$ sono "marginalmente equivalenti" e producono rischi identici per funzioni di perdita decomponibili.

2. Condizioni di Ottimalità:

   • Sfruttando la nota ottimalità esatta dello schema SS, il documento prova che qualsiasi schema a blocchi con un parametro $k \in K^*_{v,\epsilon}$ (l'insieme degli interi che minimizzano la funzione di rischio) è anche esattamente ottimale.
   • Il documento caratterizza precisamente $K^*_{v,\epsilon}$, dimostrando che uno schema è esattamente ottimale se $k$ soddisfa specifici limiti legati a $\epsilon$ e $v$.

3. Efficienza di Comunicazione:

   • L'ineguaglianza di Fisher impone che, per qualsiasi schema non distorto o consistente, $b \ge v$.
   • Gli autori si concentrano sui disegni a blocchi simmetrici dove $b = v$, raggiungendo il costo di comunicazione minimo teorico per schemi non distorti.
   • Quando un disegno a blocchi simmetrico con l'ottimale $k$ non esiste per un dato $(v, \epsilon)$, il documento utilizza disegni a blocchi derivati e residui per costruire schemi non simmetrici che rimangano esattamente ottimali o quasi-ottimali con un basso $b$.

4. Schemi RPBD:

   • Per affrontare la "scarsa esistenza" dei disegni a blocchi per arbitrarie combinazioni di parametri, gli autori rilassano il vincolo di uniformità, proponendo Disegni Regolari e Bilanciati a Coppie (RPBD).
   • Gli schemi RPBD abbandonano il requisito che $|I_y| = k$ per ogni $y$, mantenendo solo la regolarità ($r$) e il bilanciamento a coppie ($\lambda$).
   • Gli autori mostrano che gli schemi RPBD con un rapporto $[b:r:\lambda]$ simile a quello dell'ottimale schema SS raggiungono un rischio quasi-ottimale. Questi possono essere costruiti troncando esistenti disegni a blocchi simmetrici.

Risultati Chiave

• Ottimalità Esatta con Basso Costo: Il documento identifica numerosi nuovi schemi LDP che raggiungono l'esatto trade-off ottimalità-privacy (eguagliando il limite inferiore $M_{v,u,\epsilon}$) con il minimo costo di comunicazione possibile ($b=v$) per una gamma più ampia di coppie $(v, \epsilon)$ rispetto a quanto precedentemente noto.
• Unificazione: Il framework unifica gli schemi esistenti (Randomized Response, Subset Selection, Hadamard Response, Projective Geometry Response) sotto l'unica etichetta dei disegni a blocchi.
• Near-Ottimalità tramite Troncamento: Per i casi in cui non esistono disegni a blocchi esattamente ottimali, il documento dimostra che il troncamento di disegni a blocchi simmetrici per formare schemi RPBD produce prestazioni quasi-ottimali con costi di comunicazione significativamente inferiori rispetto ai precedenti metodi allo stato dell'arte (ad esempio, PGR).
  • Esempio: Per $v=100, \epsilon=1$, uno schema RPBD troncato basato su un insieme di differenze residuo quarticamente raggiunge un errore di stima inferiore e richiede circa 6,66 bit per client, rispetto agli 8,41 bit di uno schema PGR troncato.
• Connessione con la Congettura di Hadamard: Il documento collega l'esistenza di schemi esattamente ottimali con minimo costo di comunicazione nel regime di alta privacy ($\epsilon \approx 0$) alla congettura di Hadamard. Se la congettura è vera, schemi esattamente ottimali con $b=v$ (o $b=2v$) esistono per tutti i $v$.

Significato
Il documento sostiene di fornire un nuovo framework unificato per la scoperta di schemi LDP che superino il tradizionale trade-off tra ottimalità esatta ed efficienza di comunicazione. Spostando l'attenzione da costruzioni specifiche ad hoc alle proprietà combinatorie dei disegni a blocchi, gli autori dimostrano che:

1. Molti schemi precedentemente proposti (HR, PGR) sono in realtà esattamente ottimali per specifici regimi, un fatto non stabilito precedentemente.
2. Nuovi schemi possono essere generati sistematicamente per raggiungere l'ottimalità esatta con i minimi costi di comunicazione per un set più ampio di parametri.
3. Il rilassamento verso gli schemi RPBD consente prestazioni quasi-ottimali con bassi costi di comunicazione in scenari in cui la costruzione di esattamente ottimi disegni a blocchi è matematicamente impossibile.

Il lavoro sottolinea che analizzare l'esatto trade-off privacy-utilità (inclusi i fattori costanti) è cruciale per l'implementazione pratica, e l'approccio proposto tramite i disegni a blocchi offre un percorso rigoroso per raggiungere ciò senza sacrificare l'efficienza di comunicazione.