Sintesi Tecnica: FPT (Fixed-Parameter Tractability) della Generazione di Dati Sintetici Privati

Definizione del Problema

Il documento affronta il problema della Generazione di Dati Sintetici Privati. Dato un dataset sensibile $X$ su un dominio $D = \{0, 1\}^d$ e una famiglia di query di conteggio $\mathcal{F}$ (funzioni $f: D \to \{0, 1\}$), l'obiettivo è generare un dataset sintetico $X'$ che preservi le proprietà statistiche di $X$ rispetto a $\mathcal{F}$ soddisfacendo al contempo la Differential Privacy (DP).

L'errore è misurato come la deviazione massima tra le risposte alle query sui dati originali e quelli sintetici: $\max_{f \in \mathcal{F}} |f(X) - f(X')|$. Sebbene i tassi di errore ottimali per i dati sintetici DP siano noti teoricamente (a seconda del regime della dimensione del dominio $|D|$, della dimensione della famiglia di query $|\mathcal{F}|$ e della dimensione del dataset $n$), gli algoritmi esistenti che raggiungono tali tassi operano tipicamente in un tempo esponenziale nella dimensione $d$. Al contrario, sotto le standard assunzioni crittografiche, produrre dati sintetici accurati per famiglie di query generali (ad esempio, marginali a 2 vie) è computazionalmente difficile.

Gli autori indagano se sia possibile ottenere la Fixed-Parameter Tractability (FPT) identificando un parametro strutturale della famiglia di query che permetta algoritmi efficienti, anche quando $d$ è grande.

Metodologia

Il documento propone due distinti approcci algoritmici, entrambi unificati da un framework di programmazione dinamica su una decomposizione ad albero del grafo di incidenza della famiglia di query. Il parametro strutturale chiave identificato è il treewidth ($tw(\mathcal{F})$) del grafo di incidenza $G(\mathcal{F})$, un grafo bipartito che connette le variabili $[d]$ e le query $\mathcal{F}$.

1. Approccio di Programmazione Lineare (LP) (Regime di Piccola Famiglia di Query)

Per i regimi in cui la dimensione della famiglia di query $|\mathcal{F}|$ è piccola, gli autori formulano il problema come un Programma Lineare (LP) per trovare un istogramma frazionario $h$ coerente con le stime rumorose delle query.

• Problema Primal: Minimizzare la deviazione massima $\alpha$ soggetto a vincoli che corrispondono ai conteggi rumorosi.
• Problema Duale: Il duale dell'LP ha $2|\mathcal{F}|$ variabili e $2^d$ vincoli. Risolverlo tramite il metodo dell'Ellissoide richiede un separatore (separation oracle).
• Contributo FPT: Il separatore si riduce alla massimizzazione di una funzione lineare sull'ipercubo booleano. Gli autori dimostrano che questo problema di massimizzazione è FPT rispetto a $tw(\mathcal{F})$ utilizzando la programmazione dinamica. Ciò consente di risolvere il duale dell'LP in tempo polinomiale in $d$ e $|\mathcal{F}|$, ma esponenziale solo in $tw(\mathcal{F})$.
• Output: Una volta risolto il duale, viene estratta una soluzione primale (istogramma frazionario) con supporto ridotto, e un dataset sintetico viene generato tramite campionamento.

2. Subsampled Private Multiplicative Weights Update (PMWU) (Regime Sparso)

Per i regimi in cui la dimensione del dataset $n$ è piccola (il setting sparso), gli autori adattano il framework Private Multiplicative Weights Update (PMWU).

• Sfida: Il PMWU standard mantiene una distribuzione su l'intero dominio $D$ (dimensione $2^d$), il che è intrattabile.
• Soluzione: Invece di mantenere esplicitamente la distribuzione completa, l'algoritmo la mantiene implicitamente come una distribuzione di Gibbs. Ad ogni passo, campiona un dataset sottocampionato da questa distribuzione.
• Contributo FPT: L'ostacolo tecnico principale è il campionamento dalla distribuzione di Gibbs definita dai pesi correnti. Gli autori dimostrano che il campionamento da tali distribuzioni è FPT in $tw(\mathcal{F})$. Ottengono questo risultato:
  1. Calcolando la funzione di partizione (costante di normalizzazione) della distribuzione di Gibbs utilizzando lo stesso framework di programmazione dinamica usato per il separatore dell'LP.
  2. Utilizzando la funzione di partizione calcolata e i punteggi locali per eseguire un campionamento di Gibbs perfetto tramite una traversata ricorsiva della decomposizione ad albero (dalla radice alle foglie), campionando le probabilità condizionate ad ogni passo.
• Output: L'algoritmo aggiorna iterativamente i pesi basandosi sugli errori delle query rumorose e restituisce il dataset sottocampionato finale.

Contributi Chiave

1. Parametrizzazione Strutturale: Il documento identifica il treewidth del grafo di incidenza della famiglia di query come il parametro critico per ottenere la FPT nella generazione di dati sintetici privati. Questo parametro non cresce necessariamente con la dimensione dello scope della query, permettendo la trattabilità polinomiale in casi come le query gerarchiche.
2. Framework Unificato: Entrambi gli approcci (l'approccio LP per piccoli $|\mathcal{F}|$ e l'approccio PMWU per piccoli $n$) si basano su un framework unificato di programmazione dinamica su una decomposizione ad albero per risolvere problemi di ottimizzazione (separatore) e inferenza (funzione di partizione/campionamento).
3. Tassi di Errore Ottimali: Gli algoritmi proposti raggiungono i tassi di errore ottimali noti per la DP in tutti i regimi (piccolo $|D|$, piccolo $|\mathcal{F}|$ e piccolo $n$), ma con tempi di esecuzione che sono esponenziali solo nel treewidth anziché nella dimensione $d$.
4. Campionamento FPT: Il documento stabilisce che il campionamento da distribuzioni di Gibbs associate a famiglie di query a treewidth limitato è un problema FPT, un risultato di interesse indipendente per i modelli grafici probabilistici e la fisica statistica.

Risultati

Il documento fornisce le seguenti garanzie teoriche:

• Complessità: Entrambi gli algoritmi operano in tempo $\text{poly}(d, |\mathcal{F}|, n, 2^{tw(\mathcal{F})}, \text{size}(\mathcal{F}))$.
• Accuratezza:
  • Per piccoli $|\mathcal{F}|$ (approccio LP): L'errore corrisponde al limite ottimale $\Theta(\min(\frac{\sqrt{|D| \ln |\mathcal{F}|}}{n\varepsilon}, \frac{\sqrt{|\mathcal{F}| \log(1/\delta)}}{n\varepsilon}, \dots))$.
  • Per piccoli $n$ (approccio PMWU): L'errore corrisponde al limite ottimale per il regime sparso, specificamente $O((\frac{d \ln(|\mathcal{F}| d n \varepsilon)}{n \varepsilon})^{1/3})$ per la DP pura e $O((\frac{\sqrt{d \ln(1/\delta)} \ln(|\mathcal{F}| d n \varepsilon)}{n \varepsilon})^{1/2})$ per la DP approssimata.
• Applicazioni: Il framework è applicato a specifiche famiglie di query:
  • Query Gerarchiche: Il treewidth è limitato dalla profondità della gerarchia, recuperando la trattabilità polinomiale per le query stile US Census.
  • Query Marginali Partizionate: Dimostra la superiorità dell'approccio PMWU nei regimi sparsi rispetto agli approcci densi.
  • MRF a struttura ad albero e Famiglie Geometriche: Mostra un treewidth costante o basso per le query derivanti da modelli grafici a struttura ad albero e query di reticolo spaziale.

Significato

Il documento sostiene di fornire un approccio unificato che gestisce carichi di lavoro di query generali e distingue chiaramente tra istanze "facili" e "difficili" in base alla complessità strutturale (treewidth) della famiglia di query.

Stabilendo la FPT, gli autori colmano il divario tra la possibilità teorica di tassi di errore ottimali e i vincoli di efficienza computazionale pratica. Dimostrano che per molte classi naturali e importanti di query (come le query gerarchiche utilizzate nei censimenti nazionali o le query su dati a struttura ad albero), è possibile generare dati sintetici privati accurati in modo efficiente, superando la barriera dell' "esponenziale in $d$" che affligge gli algoritmi per il caso generale. Il lavoro estende i metodi esistenti (come l'algoritmo Census TopDown) fornendo un meccanismo generale che si adatta ai carichi di lavoro forniti dall'analista senza richiedere la materializzazione esplicita di istogrammi ad alta dimensione.