Missing Mass for Differentially Private Domain Discovery

1. Introduzione e Problema

Il lavoro affronta il problema della scoperta di dominio differenzialmente privata (DP). In molti scenari di analisi dati moderni (come query, recensioni o cronologie di acquisto), il dominio degli elementi (l'insieme di tutti gli elementi possibili) è sconosciuto a priori o troppo vasto per essere gestito esplicitamente.

• Il problema: Ogni utente possiede un sottoinsieme di elementi da un dominio condiviso ma sconosciuto. L'obiettivo è estrarre un sottoinsieme informativo di elementi che rappresenti il dominio, preservando la privacy differenziale.
• La sfida: La privacy differenziale complica la scoperta del dominio perché aggiungere rumore per proteggere i singoli utenti può portare all'omissione di elementi frequenti o all'inclusione di elementi rari, degradando l'utilità.
• Metrica di valutazione: Il paper propone di misurare la qualità non in termini di cardinalità (numero di elementi unici), ma di massa mancante (missing mass). La massa mancante è definita come la frazione totale di frequenza degli elementi che non vengono inclusi nell'output. Minimizzare questa massa significa catturare la maggior parte della "massa" (frequenza) dei dati reali.

2. Metodologia

Il cuore della proposta è l'uso e l'analisi teorica del Weighted Gaussian Mechanism (WGM) come meccanismo fondamentale per la scoperta del dominio, seguito da algoritmi noti per problemi specifici.

A. Weighted Gaussian Mechanism (WGM) per Set Union

Il WGM è un meccanismo semplice e scalabile che opera in tre fasi:

1. Campionamento: Per ogni utente, si campiona senza sostituzione un sottoinsieme di elementi fino a un limite di contributo $\Delta_0$.
2. Istogramma Pesato: Si costruisce un istogramma dove il conteggio di ogni elemento è pesato in base al numero di elementi campionati dall'utente (normalizzazione $\ell_2$).
3. Soglia Rumorosa: Si aggiunge rumore gaussiano ai conteggi pesati e si restituiscono gli elementi il cui conteggio rumoroso supera una soglia $T$.

Il paper dimostra che il WGM offre garanzie di utilità forti in termini di massa mancante:

• Dati Zipfiani: Per dataset che seguono una legge di potenza (Zipf), il WGM garantisce una massa mancante $\ell_1$ quasi ottimale.
• Indipendente dalla distribuzione: Viene fornita una garanzia di massa mancante $\ell_\infty$ (massimo errore di frequenza) valida per qualsiasi distribuzione di dati, senza assumere che siano Zipfiani.

B. Applicazione a Problemi Complessi

Gli autori utilizzano il WGM come un "precursore" per risolvere varianti a dominio sconosciuto di due problemi classici:

1. Selezione Top-k: Trovare i $k$ elementi più frequenti.
   • Approccio: Esegui WGM per ottenere un dominio candidato $D$, poi esegui un algoritmo di selezione Top-k privato (come il Peeling Exponential Mechanism) solo su $D$.
2. $k$-Hitting Set: Trovare un insieme di $k$ elementi che intersechi il maggior numero possibile di sottoinsiemi degli utenti (utile per riassunti dati e selezione di feature).
   • Approccio: Esegui WGM per ottenere $D$, poi esegui un algoritmo greedy privatizzato per la massimizzazione submodulare su $D$.

In entrambi i casi, il budget di privacy viene diviso a metà: metà per il WGM (scoperta del dominio) e metà per l'algoritmo specifico sul dominio ridotto.

3. Contributi Chiave

1. Garanzie di Utilità Assolute: A differenza di lavori precedenti che fornivano garanzie relative ad altri algoritmi, questo paper è il primo a fornire garanzie di utilità assolute (in termini di massa mancante) per l'unione di insiemi differenzialmente privata.
2. Analisi Teorica del WGM:
   • Teorema 3.3: Garanzia di massa mancante $\ell_1$ quasi ottimale per dati Zipfiani.
   • Teorema 3.6: Garanzia di massa mancante $\ell_\infty$ indipendente dalla distribuzione.
3. Nuovi Algoritmi per Top-k e Hitting Set:
   • Viene proposto un framework a due stadi che combina WGM con algoritmi noti.
   • Vengono forniti limiti superiori teorici per la massa mancante nel Top-k e per l'errore additivo nel $k$-Hitting Set.
   • Vengono dimostrati limiti inferiori (lower bounds) che mostrano come la dipendenza da $k/\epsilon$ sia inevitabile per algoritmi che rispettano l'assunzione di "soundness" (l'output deve essere un sottoinsieme degli input).
4. Validazione Empirica: Sperimentazione su sei dataset reali (Reddit, Amazon, Movie Reviews, Steam) che dimostra che i metodi basati su WGM sono competitivi o superiori rispetto agli stati dell'arte, pur essendo molto più scalabili.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su sei dataset reali divisi in "grandi" (Reddit, Amazon Games, Movie Reviews) e "piccoli" (Steam, Amazon Magazine, Amazon Pantry).

• Set Union (Unione di Insiemi): Il WGM ottiene una massa mancante entro il 5% rispetto ai meccanismi "Policy" (che sono più complessi e computazionalmente pesanti), dimostrando un eccellente compromesso tra efficienza e utilità.
• Top-k Selection: Il metodo proposto (WGM + Peeling Exponential) supera costantemente i baselines a dominio limitato (come quello di Durfee & Rogers, 2019) su tutti i dataset, specialmente all'aumentare di $k$.
• $k$-Hitting Set: Il metodo proposto performa in modo paragonabile o superiore agli algoritmi greedy non privati e a quelli privati che assumono un dominio pubblico noto. Questo è significativo perché, in scenari reali, il dominio totale è privato; il WGM riesce a ricostruire un dominio più piccolo ma di alta qualità che facilita la fase successiva.

5. Significato e Impatto

Questo lavoro è significativo per diversi motivi:

• Cambio di Paradigma: Sposta il focus dalla cardinalità alla "massa" (frequenza), offrendo una metrica di utilità più rilevante per le applicazioni pratiche dove gli elementi frequenti sono cruciali.
• Scalabilità: Dimostra che meccanismi semplici e non adattivi come il WGM possono ottenere prestazioni teoriche e pratiche superiori rispetto a metodi sequenziali complessi e costosi.
• Fondamento Teorico: Fornisce le prime garanzie di utilità rigorose per problemi di scoperta di dominio a dominio sconosciuto, colmando un vuoto nella letteratura sulla privacy differenziale.
• Applicabilità Pratica: I risultati empirici confermano che queste tecniche sono immediatamente applicabili in sistemi industriali per la gestione di dati sensibili su larga scala (es. analisi di query o log di click).

In sintesi, il paper stabilisce che una strategia semplice basata sul WGM, combinata con una corretta analisi della massa mancante, è la via più efficace per la scoperta di dominio differenzialmente privata, offrendo sia garanzie teoriche solide che prestazioni empiriche superiori.