Not All Learnable Distribution Classes are Privately Learnable

Riepilogo Tecnico: "Non tutte le classi di distribuzioni apprendibili sono apprendibili in modo privato"

Enunciato del Problema
Il lavoro affronta una domanda fondamentale all'intersezione tra la teoria dell'apprendimento statistico e la privacy differenziale (DP): ogni classe di distribuzioni che è apprendibile nel contesto standard (non privato) è anche apprendibile sotto i vincoli della privacy differenziale $(\varepsilon, \delta)$?

Sebbene sia stabilito che la privacy differenziale pura ($\varepsilon$-DP, dove $\delta=0$) imponga separazioni rigide tra classi apprendibili e classi apprendibili in modo privato (spesso caratterizzate da numeri di copertura/packing), lo status della privacy differenziale approssimata ($(\varepsilon, \delta)$-DP) rimaneva una questione aperta. La letteratura recente ha prodotto framework sempre più generali per l'apprendimento privato di distribuzioni, portando Ashtiani [Ash22] a ipotizzare che la risposta alla domanda sopra sia affermativa: ovvero che ogni classe di distribuzioni apprendibile sia apprendibile in modo privato.

Metodologia e Costruzione
Gli autori confutano questa congettura costruendo una specifica classe di distribuzioni, denotata come $\mathcal{H}_w$, che funge da controesempio. La costruzione utilizza un meccanismo a "trappola" che coinvolge miscele di distribuzioni:

1. La Struttura della Classe: La classe $\mathcal{H}_{w,d}$ consiste in miscele su $d+1$ componenti che condividono un vettore di parametri comune $\mathbf{p} \in [0,1]^d$.
   • La Componente "Chiave": Una distribuzione prodotto binaria su $\{0,1\}^d$ con peso di miscelazione $w$. Un singolo campione da questa componente rivela informazioni sull'intero vettore di parametri $\mathbf{p}$.
   • Le Componenti "Difficili": $d$ componenti aggiuntive, ciascuna supportata su $\{\pm j\}$ per $j \in \{1, \dots, d\}$, con peso di miscelazione $(1-w)/d$. Un campione da una di queste rivela informazioni su una sola coordinata di $\mathbf{p}$.
2. La Trappola: Il peso di miscelazione $w$ è impostato a $1/(2\alpha)$ (dove $\alpha$ è l'errore target). Questo garantisce che le componenti "difficili" dominino la miscela (alta probabilità di campionamento da esse), mentre la componente "chiave" è rara.
3. Il Trucco della Dimensionalità: La classe $\mathcal{H}_w$ è definita come l'unione di queste classi su tutte le dimensioni $d \ge 2$. La costruzione garantisce che, sebbene la dimensione $d$ non sia fissata a priori, la difficoltà dell'apprendimento scala con $d$.

Risultati e Dimostrazioni Chiave
Il lavoro stabilisce una separazione tra apprendibilità non privata e apprendibilità privata per la classe $\mathcal{H}_w$ rispetto alla distanza di Variazione Totale (TV):

1. Apprendibilità Non Privata (Campioni Finiti):
   Gli autori dimostrano che $\mathcal{H}_w$ è apprendibile con un numero costante di campioni (indipendente da $d$) fino a un errore costante.

   • Meccanismo: Poiché la componente "chiave" appare con probabilità $w$, un algoritmo non privato può raccogliere campioni sufficienti per osservare la componente chiave. Una volta osservata, la dimensione $d$ viene identificata e il vettore di parametri $\mathbf{p}$ può essere stimato tramite la media campionaria della distribuzione prodotto binaria.
   • Complessità: La complessità campionaria è $O(1/\alpha^3 \cdot \log(1/\beta))$, che è costante rispetto alla dimensione $d$.

2. Non Apprendibilità Privata (Richiesti Campioni Infiniti):
   Gli autori dimostrano che nessun meccanismo $(\varepsilon, \delta)$-DP può apprendere questa classe con la stessa garanzia di errore utilizzando un numero finito di campioni.

   • Riduzione: Costruiscono una riduzione dal problema della stima della densità su $\mathcal{H}_{w,d}$ al problema della stima dei parametri $\ell_1$ per distribuzioni prodotto binarie.
   • Limite Inferiore: Sfruttando i limiti inferiori noti per la stima della media privata delle distribuzioni prodotto binarie (specificamente da [KLSU19]), mostrano che la complessità campionaria per l'apprendimento di $\mathcal{H}_{w,d}$ sotto DP scala come $\Omega(\sqrt{d}/(\sqrt{\alpha}\varepsilon))$.
   • Contraddizione: Poiché la classe $\mathcal{H}_w$ include distribuzioni per qualsiasi $d \ge 2$, e la dimensione campionaria richiesta cresce con $\sqrt{d}$, nessuna dimensione campionaria finita $n$ è sufficiente per apprendere l'intera classe $\mathcal{H}_w$ sotto DP. Quando $d \to \infty$, la dimensione campionaria richiesta tende all'infinito.

Contributi Chiave

• Confutazione della Congettura: Il lavoro fornisce un controesempio esplicito alla congettura di Ashtiani secondo cui ogni classe di distribuzioni apprendibile è apprendibile in modo privato sotto $(\varepsilon, \delta)$-DP.
• Separazione dell'Apprendibilità: Dimostra una separazione rigida in cui una classe è apprendibile con $O(1)$ campioni in modo non privato ma richiede un numero infinito di campioni per essere appresa in modo privato.
• Costruzione a Trappola: Gli autori introducono una specifica costruzione a "trappola" in cui una componente rara agisce come chiave per un parametro ad alta dimensionalità, altrimenti oscurato da una componente dominante e difficile da apprendere. Questa struttura impedisce ai meccanismi privati di accedere alla "chiave" senza violare i vincoli di privacy o richiedere dimensioni campionarie proibitive.

Significato e Affermazioni
Il lavoro afferma di "confutare debolmente" la congettura. Gli autori notano esplicitamente che una "confutazione forte" richiederebbe di dimostrare che la classe è apprendibile per qualsiasi errore target (non solo errore costante) con campioni finiti in modo non privato, cosa che non dimostrano. Tuttavia, il loro risultato è significativo perché mostra che, anche per garanzie di errore costante, il panorama dell'apprendimento privato di distribuzioni è fondamentalmente diverso dall'apprendimento non privato.

Il lavoro evidenzia che i framework generali per l'apprendimento privato non possono basarsi semplicemente su riduzioni in scatola nera da apprenditori non privati senza ipotesi strutturali aggiuntive. Stabilisce che l'esistenza di una componente "chiave" che è rara ma essenziale per l'apprendimento può creare una barriera insormontabile per gli algoritmi privati, anche quando l'algoritmo non privato è efficiente.

Conclusione
Il lavoro conclude che l'agenda di progettare algoritmi generali di apprendimento privato che funzionino per tutte le classi di distribuzioni apprendibili non può essere pienamente realizzata. Esistono classi apprendibili in cui il vincolo di privacy altera fondamentalmente la complessità campionaria da finita a infinita, indipendentemente dalla specifica tolleranza all'errore (entro il regime costante considerato).