Sintesi Tecnica: Verifica Pubblica Efficiente di ML Privato tramite Regolarizzazione

Definizione del Problema

La Privacy Differenziale (DP) è il framework standard per proteggere le informazioni sensibili nei dataset di addestramento del machine learning, garantendo che gli utenti del modello non possano inferire specifici punti dati. Tuttavia, esiste una lacuna critica: i fornitori di dati e il pubblico mancano di metodi efficienti per verificare se un modello rilasciato sia stato effettmente addestrato sotto garanzie DP.

I metodi di verifica attuali affrontano due limitazioni primarie:

1. Auditing Black-box: Gli approcci che interrogano un trainer di modelli con dataset differenti sono statisticamente insufficienti. Il paper dimostra che, sotto l'assunto di firme digitali, un trainer malevolo può inserire una backdoor "computazionalmente indistinguibile". Questa backdoor rimane dormiente durante gli audit standard, ma permette al trainer di esporre il dataset a entità specifiche, rendendo l'algoritmo non privato nonostante superi qualsiasi controllo black-box.
2. Costi di Verifica Interattiva: Gli esistenti proof interattivi per la DP (ad esempio, verificare DP-SGD) richiedono al verificatore di ricalcolare quasi tutti i passaggi di addestramento. Ad esempio, verificare la DP su MNIST richiedeva precedentemente circa 100 ore di calcolo, scalando con il costo dell'addestramento. Ciò rende la verifica pubblica impraticabile per dataset di grandi dimensioni.

Il paper affronta la sfida di progettare un algoritmo DP in cui il costo di verifica sia strettamente inferiore al costo di addestramento, specificamente per l'Ottimizzazione Convessa Stocastica (DP-SCO).

Metodologia

1. Fondamento Teorico: Backdoor Indistinguibili

Gli autori formalizzano innanzitutto l'insufficienza dell'auditing black-box. Costruiscono un algoritmo di addestramento backdoored $T'$ che è computazionalmente indistinguibile da un algoritmo DP legittimo $T$ per qualsiasi auditor polinomiale.

• Meccanismo: L'algoritza incorpora un passaggio di verifica della firma digitale nei dati di addestramento. Se un input specifico contiene una firma valida (che solo il trainer malevolo possiede), l'algoritmo restituisce il dataset di addestramento grezzo invece del modello.
• Implicazione: Questo prova che senza protocolli interattivi, nessun auditor pubblico può garantire la privacy di un modello, rendendo necessario un passaggio alla certificazione interattiva.

2. Algoritmo Core: Phased ERM Modificato

Per ottenere una verifica efficiente, gli autori propongono una modifica dell'algoritmo Phased Empirical Risk Minimization (ERM) (Feldman et al., 2020).

• Standard Phased ERM: Risolve una serie di obiettivi regolarizzati su sottoinsiemi di dati disgiunti, aumentando la forza della regolarizzazione attraverso le fasi. Si basa sulla composizione parallela dei budget di privacy per ottenere garanzie strette. Tuttavia, verificare la composizione parallela è costoso perché il verificatore deve confermare che ogni fase abbia utilizzato un sottoinsieme specifico e disgiunto di dati.
• La Modifica: Gli autori alterano i criteri di arresto per gli approssimanti minimizzatori in ogni fase.
  • Invece di richiedere che l'eccesso di perdita (excess loss) sia piccolo, richiedono che la norma del gradiente sia piccola ($\|\nabla F_i(\tilde{w}_i)\|_2 \leq \frac{2}{n_i} L$).
  • Regolano il budget di privacy $\delta$ per ogni fase a $\delta / \lceil \log_2(n) \rceil$.
• Beneficio Risultante: Questa modifica consente all'algoritmo di derivare trade-off privacy-utilità quasi ottimali utilizzando solo la standard composizione sequenziale invece della composizione parallela. La composizione standard è significativamente più facile da verificare perché non richiede di provare la disgiunzione dei sottoinsiemi di dati, ma solo che il rumore sia stato aggiunto correttamente e che le norme dei gradienti siano state soddisfatte.

3. Protocollo di Verifica

Il protocollo proposto (Algoritmo 2) prevede un proof interattivo tra un Prover (trainer) e un Verifier (pubblico):

1. Impegno (Commitment): Il Prover si impegna (commit) sul dataset e sui pesi del modello in ogni fase.
2. Verifica del Gradiente: Utilizzando le Zero-Knowledge Proofs (ZKP), il Verifier controlla che la norma del gradiente dell'approssimante minimizzatore sia al di sotto della soglia richiesta.
3. Verifica del Rumore: Il Verifier controlla che il rumore Gaussiano sia stato aggiunto ai pesi utilizzando uno schema di impegno gaussiano discreto.
4. Complessità: La verifica richiede il controllo di $n$ gradienti (dove $n$ è la dimensione del dataset) e $d \cdot \lceil \log_2(n) \rceil$ impegni di variabili casuali Gaussiane (dove $d$ è la dimensione).

4. Estensione all'Unlearning di Macchina

Gli autori estendono queste tecniche all'Approssimata Machine Unlearning per perdite fortemente convesse. Sfruttando la stabilità delle funzioni fortemente convesse, dimostrano che l'unlearning può essere certificato controllando i gradienti sul dataset di ritenzione ($D'$) piuttosto che sull'intero dataset, richiedendo solo $|D'|$ controlli del gradiente e $d$ impegni del rumore.

Risultati Chiave

Garanzie Teoriche

• Trade-off Privacy-Utilità: L'algoritmo modificato raggiunge un rischio di popolazione in eccesso di $\tilde{O}(L D (\frac{1}{\sqrt{n}} + \frac{\sqrt{d \ln(1/\delta)}}{\epsilon n}))$, che è quasi ottimale (corrisponde ai limiti inferiori noti fino ai fattori $\log \log(n)$).
• Efficienza di Verifica: La certificazione richiede la verifica di solo $n$ gradienti e $d \cdot \lceil \log(n) \rceil$ variabili casuali Gaussiane.
  • Rispetto ai più rapidi algoritmi di addestramento noti per DP-SCO, che richiedono $\tilde{\Omega}(\min(n^{1.5}, n^2/\sqrt{d}))$ gradienti, il costo di verifica è significativamente inferiore (almeno un miglioramento di $O(\sqrt{n})$ in contesti non smooth).
  • In contesti smooth, la riduzione dei controlli delle variabili casuali Gaussiane (da $\Omega(dn)$ a $d \log n$) fornisce un vantaggio sostanziale in termini di tempo di esecuzione.

Valutazione Empirica

Gli autori hanno implementato il protocollo utilizzando l'EMP-toolkit per la regressione logistica binaria sul dataset MNIST ($n=60.000, d=784$).

• Confronto dei Tempi di Esecuzione:
  • Approccio Precedente (verifica DP-SGD): ~100 ore.
  • Approccio Proposto: ~3 ore su una CPU laptop.
• Analisi dei Colli di Bottiglia:
  • Verifica del Gradiente: Domina il tempo di esecuzione. Il numero di gradienti da verificare è stato ridotto di oltre 4 volte rispetto ai metodi precedenti.
  • Verifica del Rumore: Il tempo per verificare le variabili casuali Gaussiane è sceso drasticamente (da costo dominante a trascurabile, impiegando meno tempo di una singola verifica del gradiente).
  • Comunicazione: L'overhead di rete (LAN/WAN) è risultato insignificante rispetto al calcolo.
  • Addestramento: Il tempo di addestramento è stato trascurabile (secondi) poiché non richiede crittografia omomorfica, a differenza del processo di verifica.

Significato e Rivendicazioni

Il paper sostiene di presentare il primo algoritmo DP-SCO noto in cui la verifica DP scala meglio del costo di addestramento.

• Cambio di Paradigma: Sposta il campo dall' "auditing black-box" (provabilmente insufficiente contro avversari con capacità computazionali limitate) alla "verifica pubblica efficiente" tramite proof interattive.
• Praticità: Riducendo il tempo di verifica da ~100 ore a ~3 ore su hardware standard per dati di scala MNIST, il paper sostiene che la certificazione pubblica della ML privata sta diventando fattibile.
• Limitazioni: Gli autori notano con modestia che l'approccio attuale è limitato ai contesti convessi e non si applica direttamente alle reti neurali profonde (sebbene potrebbe applicarsi al fine-tuning dell'ultimo strato). Riconoscono inoltre che per dataset molto grandi, la scalabilità lineare con $n$ potrebbe essere ancora impraticabile, e che è necessario ulteriore lavoro per gestire i gradienti stocastici in modo più efficiente (ad esempio, tramite smoothing randomizzato).

In sintesi, il paper stabilisce che sfruttando la regolarizzazione per stabilizzare l'ottimizzazione e modificando i criteri di verifica per concentrarsi sulle norme dei gradienti anziché sull'eccesso di perdita, è possibile costruire algoritmi DP che siano sia quasi ottimali in utilità che efficientemente verificabili dal pubblico.