Sintesi Tecnica: Dependency Triad (DT) per la Quantificazione delle Dipendenze nella Local Differential Privacy

1. Definizione del Problema

La raccolta di dati utente multidimensionali sotto la Local Differential Privacy (LDP) affronta una sfida critica: la Correlation-Induced Privacy Leakage (CPL) (perdita di privacy indotta da correlazione). Mentre i meccanismi LDP (es. $\epsilon$-LDP) limitano la fuga di informazioni per i singoli attributi, le dipendenze inter-attributo possono inavvertitamente rivelare informazioni correlate, aumentando le vulnerabilità della privacy oltre il budget previsto.

Le soluzioni esistenti per quantificare la CPL soffrono di due limitazioni primarie che ne ostacolano l'applicabilità pratica:

1. Vincoli di Scalabilità e Meccanismo: Molti algoritmi esistenti (es. ITS, CBP, HCC-1/2, LTM) sono o limitati a specifici meccanismi LDP (es. perturbazione a due livelli) o soffrono di un'elevata complessità temporale e spaziale (es. $O(a^2b^2)$ o $O(a^2b \log b)$) rispetto alle dimensioni degli alfabeti degli attributi ($a, b$). Ciò li rende intrattabili per attributi ad alta cardinalità o per la calibrazione iterativa del budget di privacy.
2. Dipendenza dalle Distribuzioni di Ground-Truth: Gli attuali metodi assumono l'accesso all'esatta distribuzione di probabilità congiunta tra gli attributi. In scenari LDP reali, questa distribuzione è raramente nota; è spesso stimata da dati pregressi, dataset pubblici o sottoinsiemi della popolazione. Le discrepanze tra la distribuzione a priori nota e quella reale (dovute a cambiamenti demografici, bias di campionamento o obsolescenza) possono portare a una sottostima della perdita di informazioni, creando vulnerabilità della privacy, o a una sovrastima, riducendo l'utilità dei dati.

Il documento sostiene che sia necessario un metrico in grado di stimare la CPL in tempo costante, che sia compatibile con distribuzioni sparse e che rimanga robusto rispetto all'incertezza distributiva senza richiedere la conoscenza della ground-truth.

2. Metodologia: La Dependency Triad (DT)

Gli autori propongono la Dependency Triad (DT), un nuovo metrico che riassume le informazioni di dipendenza a coppie rilevanti per la CPL utilizzando tre parametri: $(\alpha, \beta, \delta)$.

A. Concetto Core

Invece di memorizzare l'intera distribuzione congiunta $a \times b$, la DT comprime la struttura di dipendenza in tre parametri scalari. Ciò consente una stima della CPL in tempo costante ($O(1)$) per qualsiasi budget di privacy $\epsilon$.

B. Derivazione dei Parametri

La derivazione prevede l'approssimazione dei vettori di probabilità condizionata $G$ e $G'$ (che rappresentano $P(\hat{X}|X_k=x)$ e $P(\hat{X}|X_k=x')$) attraverso i loro rapporti elemento per elemento.

1. $\alpha$ (Limite Superiore dei Rapporti): Rappresenta il rapporto di verosimiglianza massimo, governando il comportamento della fuga nel regime di bassa privacy (grande $\epsilon$). È definito come:
   $$\alpha = \ln \left( \max_{\hat{x}, x, x'} \frac{p(\hat{x}|x) + \Delta_{\hat{x},x}}{p(\hat{x}|x') - \Delta_{\hat{x},x'}} \right)$$
   dove $\Delta$ rappresenta la matrice di incertezza.

2. $\delta$ (Correzione della Sparsità): Tiene conto dei casi in cui la distribuzione è sparsa (ovvero, i denominatori diventano zero). Cattura la concentrazione di massa nei casi limite in cui $p(\hat{x}|x') = 0$.

3. $\beta$ (Limite Inferiore Calibrato): Originariamente, veniva utilizzato un parametro $\gamma$ (rapporto minimo). Tuttavia, gli autori hanno riscontrato che $(\alpha, \gamma, \delta)$ poteva portare a errori di sovrastima. Per migliorare l'accuratezza mantenendo al contempo un limite superiore conservativo, introducono un passaggio di calibrazione. $\beta$ viene derivato calibrando il limite inferiore a un budget di privacy specifico $\epsilon_0$ (tipicamente $\epsilon_0 \to 0$) per corrispondere alla CPL esatta ($CPL^\star$) della distribuzione nota. Ciò assicura che lo stimatore sia un limite superiore stretto per tutti gli $\epsilon \geq \epsilon_0$.

C. Gestione dell'Incertezza Distributiva

Per affrontare la mancanza di dati di ground-truth, la DT incorpora esplicitamente un insieme di incertezza $\Delta$ attorno alla distribuzione $P_K$. I parametri $(\hat{\alpha}, \hat{\beta}, \hat{\delta})$ sono calcolati ottimizzando sull'area ammissibile definita da $P_K \pm \Delta$. Ciò garantisce che la stima della CPL risultante sia un limite superiore conservativo anche se la distribuzione effettiva $P_A$ devia da $P_K$ entro i limiti di incertezza.

D. Algoritmi

• Algoritmo 1: Calcola i parametri $(\alpha, \beta, \delta)$ da una distribuzione nota e una matrice di incertezza. Comporta l'iterazione su coppie di attributi e la risoluzione di un Programma Lineare (LP) rilassato per trovare $\phi$ (usato per $\beta$), con una complessità di pre-calcolo di $O(a^2b^{3.5})$.
• Algoritmo 2: Stima la CPL utilizzando i parametri DT pre-calcolati e il budget di privacy $\epsilon$ in tempo costante $O(1)$.

3. Contributi Chiave

1. Nuovo Metrico (DT): Il primo metrico progettato specificamente per riassumere le dipendenze a coppia per l'analisi della perdita LDP utilizzando solo tre parametri. Funge da surrogato conservativo della distribuzione congiunta completa.
2. Garanzie Teoriche:
   • Limite Superiore: Gli autori dimostrano che lo stimatore basato su DT è un limite superiore stretto sulla vera CPL ($CPL^\star$), garantendo che la perdita di privacy riportata non sottostimi mai la reale perdita di privacy.
   • Robustezza all'Incertezza: Viene dimostrato che il metrico rimane valido e conservativo anche quando la distribuzione a priori è incerta o errata.
   • Complessità: Riduce la complessità spaziale da $O(ab)$a$O(1)$ e il tempo di valutazione da polinomiale a costante.
3. Meccanismo di Calibrazione: Un metodo per calibrare il parametro $\beta$ per minimizzare l'errore di stima preservando al contempo la garanzia di privacy, affrontando i gap di accuratezza delle semplici approssimazioni di rapporto.
4. Validazione Empirica: Esperimenti estesi su cinque dataset del mondo reale (SPM, CelebA, Adult, CVD, DSS) e dati sintetici dimostrano che la DT stima costantemente la CPL con un basso Errore Quadratico Medio Normalizzato (NMSE < 0,025) attraverso diversi regimi di dipendenza e budget di privacy.

4. Risultati Sperimentali

• Accuratezza: La DT raggiunge errori di stima molto bassi rispetto alla $CPL^\star$ ottimale (calcolata tramite baseline come HCC-2 e LTM) nei dataset reali. Nei regimi di alta privacy ($\epsilon \in (0, 1]$), l'NMSE è eccezionalmente basso (< 0,003).
• Scalabilità: A differenza delle baseline che richiedono ricalcoli per ogni budget di privacy, la DT consente una valutazione rapida. In uno scenario di calibrazione del budget, la DT ha completato il compito in 7 secondi rispetto ai 61 secondi della baseline LTM.
• Robustezza all'Incertezza: Quando testata con shift distributivi (simulati variando i margini di errore fino al 10%-20%), la DT ha mantenuto un limite superiore stretto sulla perdita effettiva, mentre i metodi che ignorano l'incertezza rischiavano la sottostima.
• Regimi Strutturali: La DT ha performato bene in varie strutture di dipendenza (bassa entropia, sparsità, one-to-many, ecc.). È stata estremamente stretta per dipendenze concentrate e conservativamente accurata per distribuzioni sparse o sensibili alla coda.
• Trade-off Privacy-Utilità: In compiti di attacco di inferenza sugli attributi e stima dei margini k, la calibrazione del budget abilitata dalla DT ha ottenuto un'utilità comparabile o migliore (distanza di Variazione Totale inferiore) rispetto ai metodi di splitting standard (SPL) o campionamento casuale (RS), particolarmente per i marginali di ordine superiore, mantenendo al contempo una robusta resistenza agli attacchi di inferenza.

5. Significato e Rivendicazioni

Il documento sostiene che la Dependency Triad (DT) colma il divario tra l'analisi teorica della privacy e l'implementazione pratica in contesti LDP multidimensionali.

• Applicabilità Pratica: Rimuovendo il requisito di distribuzioni ground-truth e abilitando la stima in tempo costante, la DT rende fattibile l'analisi rigorosa della CPL in pipeline di raccolta dati reali dove le distribuzioni sono incerte e ad alta dimensionalità.
• Sicurezza: La natura conservativa dello stimatore assicura che le garanzie di privacy non siano compromesse da mismatch distributivi, un requisito critico per l'implementazione di LDP in ambienti non fidati.
• Efficienza: La capacità di eseguire la stima della perdita in tempo costante permette una calibrazione iterativa e dinamica del budget di privacy, ottimizzando il trade-off privacy-utilità senza incorrere in costi computazionali proibitivi.

Gli autori concludono che, sebbene la DT non caratterizzi completamente la distribuzione congiunta sottostante, fornisce un mattone sufficiente, trattabile e teoricamente solido per valutare la perdita totale di privacy in contesti multidimensionali, superando i limiti di scalabilità e disponibilità dei dati dei metodi esistenti.