Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

Sintesi Tecnica: Coefficienti di Dobrushin per Meccanismi Privati Oltre la Local Differential Privacy

Enunciato del Problema
Il saggio affronta i limiti nell'uso della Local Differential Privacy (LDP) come metrica esclusiva per quantificare la privacy nei kernel di Markov discreti (meccanismi di privacy). Sebbene l'LDP sia ampiamente adottata, gli autori rilevano due problemi primari:

1. Eccessiva restrittività: Nelle applicazioni statistiche come la stima dei parametri, ottenere garanzie LDP stringenti (piccolo $\epsilon$) può portare a una degradazione estrema delle prestazioni di stima (alto rischio minimax).
2. Comportamento controintuitivo con probabilità nulle: La definizione standard di LDP produce un costo di privacy infinito se un meccanismo assegna probabilità zero a qualsiasi output per un dato input ($K_{Y|X=x}(y) = 0$). Ciò tratta i meccanismi con significativa randomizzazione (es. $K_1$ nell'esempio del saggio) in modo identico ai mapping identità o ai meccanismi triviali (es. $K_2$) se entrambi contengono voci nulle, fallendo nel distinguere tra comportamenti "rumorosi" e "deterministici" in termini di fuga di privacy.

Per affrontare questi problemi, gli autori investigano i coefficienti di Dobrushin (coefficienti di contrazione della distanza di Variazione Totale) per meccanismi che soddisfano la Pointwise Maximal Leakage (PML) anziché la stretta LDP. La PML è un adattamento puntuale della maximal leakage che dipende dalla distribuzione dei dati $P_X$. Gli autori analizzano specificamente i meccanismi in cui la distribuzione di input $P_X$ ha una massa di probabilità minima limitata inferiormente da una costante $c > 0$ (ovvero, $\min_x P_X(x) \geq c$). Questo framework permette l'analisi di meccanismi con assegnazioni a probabilità zero che sarebbero altrimenti considerati "infinitamente privati" (o infinitamente fugaci) sotto l'LDP.

Metodologia
Il saggio impiega strumenti informativi per derivare i limiti sulla contrazione delle $f$-divergenze attraverso i meccanismi di privacy.

• Definizioni: Gli autori definiscono la $(\epsilon, c)$-PML come un vincolo in cui la PML è limitata da $\epsilon$ per tutte le distribuzioni di input nel set $Q_X(c) = \{P_X : \min_x P_X(x) \geq c\}$. Questo generalizza l'LDP, poiché l'LDP corrisponde al limite $c \to 0$.
• Coefficienti di Contrazione: L'oggetto centrale di studio è il coefficiente di Dobrushin $\eta_{TV}(\epsilon, c)$, definito come il supremo della contrazione della distanza di Variazione Totale (TV) su tutti i kernel che soddisfano la $(\epsilon, c)$-PML.
• Riduzione a Output Binari: Gli autori dimostrano che, per trovare il massimo coefficiente di Dobrushin, è sufficiente considerare meccanismi con spazi di output binari ($|Y|=2$). Ciò semplifica significativamente il problema di ottimizzazione.
• Disuguaglianze: La derivazione utilizza la disuguaglianza di Binette (una generalizzazione della disuguaglianza inversa di Pinsker) per estendere i limiti TV a $f$-divergenze generali (come la Entropia Relativa e la divergenza di Hellinger).

Contributi Chiave e Risultati

1. Limiti Raggiungibili sui Coefficienti di Dobrushin:
   Il saggio deriva un limite superiore stretto sul coefficiente di Dobrushin $\eta_{TV}(\epsilon, c)$ per ogni kernel che soddisfa la $(\epsilon, c)$-PML. Il limite è dato da:
   $$\eta_{TV}(\epsilon, c) \leq \min\left( \frac{e^\epsilon - 1}{e^\epsilon(1 - Nc) + 1}, 1 \right)$$
   dove $N$ è la dimensione dell'alfabeto di input.

• Analisi dei Regimi: Gli autori mostrano che, se $\epsilon \geq \log(2/Nc)$, il coefficiente di contrazione è 1 (non avviene contrazione). Se $\epsilon < \log(2/Nc)$, il coefficiente è strettamente minore di 1, indicando una contrazione indotta dalla privacy.
• Recupero dell'LDP: Per $c \to 0$, il limite recupera il risultato noto per l' $\epsilon$-LDP: $\eta_{TV} \leq \frac{e^\epsilon - 1}{e^\epsilon + 1}$.
• Costruzione di Meccanismi: Il saggio fornisce costruzioni esplicite di meccanismi (specificamente meccanismi a output binario) che raggiungono tali limiti, dimostrando che i limiti sono raggiungibili.

2. Estensione a $f$-Divergenze Generali:
   Utilizzando la disuguaglianza di Binette, gli autori estendono i limiti TV a $f$-divergenze generali. Derivano forti disuguaglianze di elaborazione dei dati (SDPI) per l'Entropia Relativa e la divergenza di Hellinger sotto vincoli $(\epsilon, c)$-PML. Questi limiti dipendono dal fattore di contrazione TV e dai rapporti estremi delle distribuzioni di output.

3. Applicazione al Rischio Minimax:
   I limiti derivati sono applicati alla stima del rischio minimax privato. Utilizzando il metodo a due punti di Le Cam e la proprietà di tensorializzazione delle $f$-divergenze, gli autori mostrano che la complessità campionaria necessaria per raggiungere un certo livello di rischio aumenta di un fattore proporzionale all'inverso del coefficiente di Dobrushin privato. Specificamente, se il coefficiente è 1, la complessità campionaria corrisponde al setting non privato; se è minore di 1, la dimensione effettiva del campione è ridotta.

Significatività e Rivendicazioni
Il saggio sostiene di fornire un framework più sfumato per l'analisi dei meccanismi di privacy rispetto alla sola LDP. Introducendo il parametro $c$, gli autori possono quantificare la fuga di privacy per meccanismi che contengono voci a probabilità zero, che sono esclusi o trattati patologicamente sotto la LDP standard.

• Limiti Più Stretti: Per i meccanismi che soddisfano l'LDP, i limiti proposti sono più stretti o più adattabili rispetto ai risultati precedenti quando la distribuzione di input ha una massa minima $c$ nota.
• Oltre l'LDP: Il framework estende l'analisi dei coefficienti di contrazione all'intera classe di kernel discreti, inclusi quelli che non soddisfano alcuna garanzia LDP finita.
• Interpretazione Operativa: I risultati collegano i coefficienti di contrazione teorici direttamente alla degradazione delle prestazioni di stima statistica, offrendo uno strumento per quantificare il "costo" della privacy in termini di aumento del rischio o della complessità campionaria.

Gli autori sottolineano che il loro lavoro recupera i risultati esistenti dell'LDP come un caso speciale, offrendo al contempo un'interpolazione continua tra i vincoli di distribuzione uniforme e il pieno regime LDP, affrontando così la natura "eccessivamente restrittiva" dell'LDP in specifici contesti statistici.