Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe

Sintesi Tecnica: Apprendimento Continuativo con Privacy di Partecipazione

Problema
I moderni sistemi di apprendimento federato e in streaming rilasciano frequentemente snapshot intermedi del modello durante l'addestramento, esponendo l'intera traiettoria degli aggiornamenti $(w(t))_{t \ge 0}$ a un avversario, anziché solo un modello finale. Mentre le analisi classiche della privacy differenziale (DP) per il rilascio continuativo assumono spesso flussi con vicinato di Hamming (dove due flussi differiscono esattamente in un indice temporale), molte implementazioni reali richiedono la privacy di partecipazione. In questo scenario, un utente può desiderare di garantire la plausibile denegabilità riguardo alla propria effettiva partecipazione. Ciò motiva l'uso di flussi con vicinato a singola modifica (edit-distance), dove due flussi sono vicini se uno può essere ottenuto dall'altro tramite l'inserimento o la cancellazione di un singolo evento dell'utente.

La difficoltà principale risiede nel fatto che un singolo inserimento o cancellazione sposta l'allineamento di tutte le posizioni successive nello stream. Di conseguenza, una coppia di vicini per distanza di modifica (edit-neighbor) può essere arbitrariamente lontana dall'essere vicina per Hamming. Inoltre, l'apprendimento continuativo è intrinsecamente interattivo: i modelli rilasciati influenzano i futuri aggiornamenti degli utenti, creando un ciclo di feedback adattivo. Le standard primitive di DP per il rilascio continuativo (ad esempio, le somme prefisse basate su alberi) sono state analizzate originariamente sotto assunzioni di Hamming statiche e non adattive, e le loro garanzie non si trasferiscono direttamente alla combinazione di flussi con vicinato per distanza di modifica e interazione adattiva.

Metodologia: Una Ricetta di Aggregazione e Buffering Auditabile
Gli autori propongono una pipeline modulare composta da due componenti primari: un wrapper di buffering randomizzato e una primitiva DP per il rilascio continuativo certificata.

1. Buffering Randomizzato (RandBin):

   • Questo componente funge da interfaccia che converte un flusso di eventi con vicinato a singola modifica in uno stream di aggiornamenti per bin di tipo Hamming e sparso.
   • Introduce ritardi casuali, rilasciando gli aggiornamenti degli utenti in "bin" di dimensione controllata $[U, 2U]$, dove $U$ è un parametro calibrato dal budget di privacy $(\varepsilon, \delta)$.
   • Randomizzando i confini di questi bin, un singolo inserimento o cancellazione nello stream di input induce solo una perturbazione limitata in stile Hamming nello stream di bin emesso (nello specifico, influenzando al massimo due bin adiacenti).
   • Il meccanismo fornisce esplicite garanzie di backlog e ritardo, assicurando che il numero di eventi in attesa rimanga limitato con alta probabilità.

2. Certificazione della Sicurezza Adattiva:

   • Gli autori introducono un teorema di certificazione per determinare quando una standard prova DP non adattiva per una primitiva continuativa rimane valida sotto interazione adattiva (feedback).
   • La certificazione richiede due condizioni strutturali per la primitiva a valle:
     • Randomicità Fresca per Round: Il meccanismo deve utilizzare una randomicità indipendente ad ogni step di rilascio.
     • Contesto Stabile (Decomponibilità Quantitativa): Gli aggiornamenti adattivi comuni possono cambiare la statistica rilasciata, ma non devono alterare il costo di privacy della discrepanza di Hamming unica tra flussi vicini.
   • Le primitive che soddisfano queste condizioni (ad esempio, somme prefisse basate su alberi, meccanismi a matrice triangolare inferiore) sono considerate "sicure rispetto al feedback", permettendo alle loro analisi di privacy non adattive di essere traslate direttamente nel setting adattivo.

3. Composizione Modulare:

   • La pipeline compone il buffering randomizzato (che riduce l'adiacenza per distanza di modifica ad adiacenza di Hamming) con l'aggregatore DP certificato.
   • La garanzia di privacy end-to-end è derivata tramite un teorema di composizione modulare, combinando la proprietà di preservazione del vicinato (NPDP) del wrapper con la proprietà DP adattiva dell'aggregatore.

Contributi Chiave

• Formalizzazione dell'Apprendimento Continuativo con Vicinato per Distanza di Modifica: Il lavoro formalizza la privacy di partecipazione tramite stream di aggiornamento utente con vicinato a singola modifica in un contesto di apprendimento continuativo con rilasci intermedi e feedback adattivo.
• Legame Esplicito Privacy-Latenza: Gli autori forniscono una pipeline modulare in cui i parametri di privacy target $(\varepsilon, \delta)$ determinano esplicitamente il livello di buffering $U$, inducendo così un ritardo/obsolescenza quantificabile nel processo di apprendimento.
• Teorema di Certificazione per la Sicurezza Adattiva: Viene stabilita una condizione riutilizzabile e verificabile sotto la quale le standard prove DP di Hamming per primitive continuative non adattive rimangono valide sotto interazione adattiva. Questa condizione combina la randomicità fresca con un requisito di contesto stabile.
• Garanzia End-to-End: Il lavoro dimostra che la pipeline composta raggiunge la $(\varepsilon, \delta)$-DP per stream con vicinato a singola modifica sotto feedback.

Risultati e Istanziazione

• Garanzie Teoriche: Il teorema principale (Teorema 3.1) afferma che impostando il livello di buffering $U = \Theta(\frac{1}{\varepsilon_b} \log \frac{1}{\delta_b})$, il sistema raggiunge la $(\varepsilon, \delta)$-DP per stream a singola modifica. Il backlog è limitato da $O(\frac{1}{\varepsilon_b} \log t (\log t + \log \frac{1}{\delta_b}))$.
• Istanziazione SGD: La ricetta è istanziata con lo Stochastic Gradient Descent (SGD) in streaming. L'aggregatore utilizza meccanismi standard di somma prefissa basati su alberi o matrici triangolari inferiori.
• Contesto Sperimentale: Il documento cita esperimenti in un lavoro complementare [CSZZ26] che riportano l'accuratezza rispetto a $(\varepsilon, \delta)$ e le distribuzioni empiriche del ritardo. La convergenza teorica delle varianti di DP-SGD è notata come già ampiamente analizzata nella letteratura precedente.

Significato e Rivendicazioni
Il lavoro sostiene di colmare una lacuna fondamentale tra la privacy di partecipazione (adiacenza per distanza di modifica) e il rilascio continuativo adattivo. Dimostra che le analisi naive del rilascio continuativo non sono applicabili a stream con vicinato per distanza di modifica a causa degli spostamenti di allineamento. Introducendo un'interfaccia di "schermatura" (buffering randomizzato) e una certificazione strutturale per la sicurezza adattiva, gli autori consentono il riutilizzo sicuro delle canoniche primitive DP continuative (come le somme prefisse ad albero) in contesti interattivi e sensibili alla partecipazione.

Il lavoro enfatizza la modularità e l'auditabilità: la pipeline separa il problema della gestione dell'adiacenza per distanza di modifica (upstream) dal problema della gestione del feedback adattivo (downstream). Ciò consente ai progettisti di sistema di integrare diverse primitive certificate mantenendo rigorose garanzie di privacy end-to-end con espliciti trade-off tra privacy, latenza e utilità. Gli autori osservano che la loro condizione di certificazione è sufficiente ma non necessaria, e che il ritardo indotto dal buffering è un costo intrinseco per ottenere la privacy di partecipazione in un contesto continuativo.