Riepilogo Tecnico: Integrazione della Correlazione delle Caratteristiche nella Privacy Differenziale con Applicazioni in DP-ERM

Enunciato del Problema

La Privacy Differenziale (DP) standard impone vincoli di privacy uniformi su tutte le caratteristiche di un dataset, trattando ogni caratteristica come ugualmente sensibile. Questa assunzione porta spesso a compromessi privacy-utilità eccessivamente conservativi nelle applicazioni reali, dove la sensibilità delle caratteristiche è eterogenea. Ad esempio, nei dati sanitari, le misurazioni della pressione arteriosa possono essere altamente sensibili, mentre le fasce d'età lo sono meno. Tuttavia, queste caratteristiche sono frequentemente correlate; rivelare l'età può involontariamente divulgare informazioni sulle distribuzioni della pressione arteriosa.

Gli approcci DP "semi-sensibili" esistenti tentano di affrontare questo problema trattando alcune caratteristiche come pubbliche e altre come private. Tuttavia, questi metodi spesso assumono l'indipendenza tra caratteristiche sensibili e non sensibili. Quando esistono correlazioni, trattare una caratteristica come pubblica può comunque compromettere la privacy della caratteristica sensibile con cui è correlata, portando a potenziali violazioni della privacy. Al contrario, applicare un rumore uniforme a tutte le caratteristiche (DP standard) distorce il dataset inutilmente, degradando l'utilità. Il documento identifica un vuoto nella letteratura esistente: la mancanza di framework che tengano rigorosamente conto delle correlazioni tra caratteristiche sensibili e non sensibili per migliorare l'utilità senza sacrificare le garanzie di privacy.

Metodologia: Framework CorrDP

Gli autori propongono CorrDP (Privacy Differenziale Consapevole delle Correlazioni), una definizione rilassata di DP che incorpora le correlazioni delle caratteristiche nel vincolo di privacy.

1. Definizione di CorrDP

CorrDP modifica la definizione standard di DP introducendo una metrica di distanza $d(D, D')$ tra database vicini $D$ e $D'$.

• Database Vicini: Definiti come quelli che differiscono per al massimo una voce, dove la differenza si verifica o nelle caratteristiche sensibili ($S$) o in quelle non sensibili ($U$), ma non simultaneamente in entrambe.
• Metrica di Distanza: Il vincolo di privacy viene rilassato in base alla correlazione tra la caratteristica modificata e le caratteristiche sensibili.
  $$P(A(D) \in R) \leq e^{\frac{\epsilon}{d(D, D')}} P(A(D') \in R) + \delta$$
• Scelta della Metrica: Il documento utilizza la Distanza di Variazione Totale (TV) per quantificare la correlazione. Nello specifico, $d(D, D')$ è definita come la massima distanza TV tra le distribuzioni condizionate delle caratteristiche sensibili date le caratteristiche non sensibili, prima e dopo la modifica.
  • Se la modifica avviene in una caratteristica sensibile, $d(D, D') = 1$ (DP standard).
  • Se la modifica avviene in una caratteristica non sensibile indipendente dalle caratteristiche sensibili, $d(D, D') = 0$ (nessun costo di privacy).
  • Se la modifica avviene in una caratteristica non sensibile correlata con le caratteristiche sensibili, $d(D, D') \in (0, 1)$, rilassando il budget di privacy a $\epsilon / d(D, D')$.

2. Meccanismi e Algoritmi

Gli autori adattano i meccanismi standard al framework CorrDP:

• Meccanismo di Laplace CorrDP: Introduce una "sensibilità correlata" $\Delta_C f$ che pesa la sensibilità delle caratteristiche non sensibili in base alla loro distanza TV rispetto alle caratteristiche sensibili. Ciò consente una riduzione dell'iniezione di rumore sulle caratteristiche non sensibili.
• CorrDP-SGD (Discesa del Gradiente Stocastica): Applicata alla Minimizzazione del Rischio Empirico (DP-ERM).
  • Calibrazione del Rumore: La varianza del rumore $\sigma_i^2$ per la $i$-esima caratteristica viene aggiustata. Per le caratteristiche sensibili ($i \in S$), viene utilizzato il rumore standard. Per le caratteristiche non sensibili ($i \in U$), la scala del rumore viene ridotta di un fattore dipendente da $\max\{TV(i), m_s^2/m^2\}$, dove $m_s$ è il numero di caratteristiche sensibili e $m$ è la dimensione totale.
  • Gestione delle Correlazioni Sconosciute: Quando la distanza TV è sconosciuta, gli autori propongono una procedura di stima utilizzando un limite superiore di confidenza della distanza TV empirica. Dimostrano che questa fase di stima, se opportunamente delimitata, mantiene le garanzie di privacy e utilità.

3. Garanzie Teoriche

• Privacy: Gli algoritmi proposti soddisfano la $(\epsilon, \delta)$-CorrDP.
• Utilità: Per funzioni di perdita convesse (inclusi Modelli Lineari Generalizzati come OLS e Regressione Logistica), il divario di utilità (rischio empirico in eccesso) è limitato da:
  $$R(\theta_{priv}) = \tilde{O}\left( \frac{\sqrt{m_s + \min\{\sum_{i \in U} TV(i), m_s/4\}}}{n\epsilon} \right)$$
  Ciò rappresenta un miglioramento rispetto al limite standard DP-ERM di $\tilde{O}(\sqrt{m}/(n\epsilon))$ quando il numero di caratteristiche sensibili $m_s$ è piccolo rispetto alle caratteristiche totali $m$, e le caratteristiche non sensibili sono debolmente correlate con quelle sensibili.
• Limite Inferiore: Il documento stabilisce un limite inferiore quasi corrispondente, confermando che il miglioramento dell'utilità è teoricamente stretto.

Contributi Chiave

1. Nuovo Framework (CorrDP): Introduzione di una nozione di DP che incorpora esplicitamente le correlazioni delle caratteristiche tramite una metrica di distanza (distanza TV), riducendosi alla DP standard quando tutte le caratteristiche sono sensibili.
2. Utilità Migliorata in DP-ERM: Progettazione di algoritmi CorrDP-SGD che incorporano un rumore dipendente dalla distanza. I risultati teorici mostrano un miglioramento dell'utilità di un fattore $\sqrt{m/m_s}$ in condizioni moderate.
3. Stima della Distanza: Una procedura per stimare la distanza TV sconosciuta dal dataset utilizzando limiti superiori di confidenza, garantendo che l'errore di stima non comprometta le garanzie di privacy o utilità.
4. Estensione alle Reti Neurali: Adattamento del framework alle reti neurali, riducendo specificamente il rumore nel primo livello dove vengono elaborate le caratteristiche non sensibili, ottenendo prestazioni migliori rispetto alla DP-SGD standard.
5. Validazione Empirica: Esperimenti su dataset sintetici e reali (Adult, Sepsis, Credit Card, Medical Cost) dimostrano che CorrDP supera costantemente la DP standard e le linee di base "Parziali" (scartando le caratteristiche sensibili), raggiungendo una accuratezza comparabile a quella "Semi" (ignorando le correlazioni) ma con garanzie di privacy più forti.

Risultati

• Dati Sintetici: Nei compiti di regressione ridge, CorrDP ha ottenuto divari di utilità inferiori (migliore accuratezza) rispetto alla DP standard su vari budget di privacy ($\epsilon$), in particolare nei regimi ad alta privacy. Ha prestazioni comparabili alla linea di base "Semi" (che ignora le correlazioni) ma con protezione rigorosa della privacy.
• Dataset Reali:
  • Adult (Previsione del Reddito): CorrDP ha superato la linea di base Semi e ha subito un calo di accuratezza inferiore al 4% rispetto ai modelli non privati nei regimi ad alta privacy.
  • Sepsis (Previsione della Sopravvivenza): Utilizzando una rete neurale a 2 livelli, CorrDP ha eguagliato le prestazioni di Semi e ha costantemente superato la DP Standard.
  • Credit Card e Medical Cost: Sono state osservate tendenze simili, con CorrDP che ha raggiunto un'utilità vicina a quella di Semi mantenendo rigorose garanzie di privacy.
• Stima della Distanza TV: Il metodo di stima proposto ha gestito con successo le correlazioni sconosciute, con le scale del rumore aggiustate dinamicamente in base alla forza della correlazione stimata (ad esempio, nel dataset Adult, la caratteristica "workclass" richiedeva un rumore più elevato a causa dell'alta correlazione con le caratteristiche sensibili).

Significato e Affermazioni

Il documento afferma che CorrDP offre un modo principiato per rilassare i vincoli di privacy in presenza di correlazioni delle caratteristiche senza compromettere le rigorose garanzie di privacy. Quantificando la "perdita" dalle caratteristiche non sensibili a quelle sensibili tramite la distanza TV, il framework consente un'iniezione di rumore dipendente dalla distanza.

Gli autori sottolineano che il loro approccio:

• Non si basa su dati pubblici o su assunzioni specifiche sulla geometria del gradiente (a differenza di altri metodi di miglioramento dell'utilità).
• Fornisce una generalizzazione naturale della DP standard e della DP semi-sensibile.
• Dimostra che tenere conto delle correlazioni consente un'utilità significativamente migliore in contesti ad alta dimensionalità dove solo un sottoinsieme di caratteristiche è realmente sensibile.

Il lavoro è presentato come un passo verso un machine learning che preserva la privacy più pratico, riconoscendo che i dati reali spesso contengono livelli di sensibilità eterogenei e dipendenze complesse che la DP standard non riesce a sfruttare per guadagni di utilità. Gli autori notano limitazioni, come il costo computazionale della stima delle distanze TV in alta dimensionalità e la necessità di partizioni chiaramente definite tra sensibili e non sensibili, indicando queste come direzioni per ricerche future.