Riepilogo Tecnico: AdaPrivate-TS

Problema

I sistemi di raccomandazione online affrontano una tensione fondamentale tra l'apprendimento delle preferenze degli utenti dai dati comportamentali privati e la fornitura di rigorose garanzie di privacy. Sebbene la Differential Privacy (DP) offra una protezione forte, essa introduce tipicamente rumore che degrada le prestazioni dell'apprendimento. Gli algoritmi esistenti per i bandit contestuali privati trattano spesso il rumore della privacy come pura corruzione, portando a un regret significativo. Inoltre, molti approcci si affidano alla joint DP (proteggendo l'intera sequenza di azioni) o alla composizione sequenziale, il che comporta costi di privacy elevati (ad esempio, un regret di $O(T^{3/4})$) o richiede un curatore centrale fidato.

Questo articolo affronta la sfida di progettare un algoritmo di bandit contestuale differenzialmente privato che operi sotto event-level DP (proteggendo le singole coppie utente-ricompensa) con contesti stocastici, con l'obiettivo di minimizzare il regret mantenendo una privacy rigorosa senza un'entità centrale fidata.

Metodologia: AdaPrivate-TS

Gli autori propongono AdaPrivate-TS, un nuovo algoritmo che integra il Thompson Sampling (TS) con la zero-concentrated Differential Privacy (zCDP a lotti).

Intuizione Centrale: Il Rumore come Incertezza

Il contributo teorico centrale è l'osservazione che il rumore DP, quando aggiunto alle statistiche sufficienti di un bandit lineare, non si limita a corrompere la stima, ma gonfia strutturalmente la covarianza posteriore.

• Nel Thompson Sampling standard, la distribuzione posteriore è $\theta | H_t \sim \mathcal{N}(\hat{\theta}_t, v^2 A_t^{-1})$.
• Quando viene aggiunto rumore Gaussiano $\eta \sim \mathcal{N}(0, \sigma^2 I)$ alla statistica sufficiente $b_t$ per la privacy, la distribuzione di campionamento risultante diventa:
  $$\tilde{\theta}_t \sim \mathcal{N}\left(\hat{\theta}_t, v^2 A_t^{-1} + \sigma^2 A_t^{-2}\right)$$
• A differenza dei metodi Upper Confidence Bound (UCB), che trattano questo rumore come errore, il Thompson Sampling interpreta naturalmente la covarianza gonfiata ($v^2 A_t^{-1} + \sigma^2 A_t^{-2}$) come aumentata incertezza. Ciò spinge l'algoritmo a esplorare maggiormente nelle direzioni in cui il rumore della privacy è dominante, convertendo efficacementamente la "corruzione" in un segnale di esplorazione benefico.

Componenti Algoritmici

1. Composizione zCDP a lotti (Batched): L'algoritmo elabora le interazioni in lotti. Rilascia statistiche sufficienti rumorose (specificamente il vettore $b$) alla fine di ogni lotto. Utilizzando la composizione parallela, il costo totale di privacy è determinato dal costo massimo di un singolo lotto ($\max_k \rho_k = \rho$) piuttosto che dalla somma dei costi, permettendo al costo di privacy di rimanere logaritmico in $T$.
2. Amplificazione della Privacy: Per ridurre ulteriormente il rumore a budget di privacy stringenti ($\epsilon \leq 1$), gli autori impiegano il sottocampionamento di Poisson. Includendo ogni ricompensa nella somma del lotto con una probabilità $q$, il costo effettivo della privacy è ridotto di un fattore di circa $2q^2$ senza riscalare la sensibilità, sfruttando l'analisi della Rényi Differential Privacy (RDP).
3. Esplorazione Adattiva: L'algoritmo decresce il parametro di esplorazione $v_k$ nel tempo ($v_k = v_0 \cdot \gamma^{k-1}$) per bilanciare un'esplorazione aggressiva iniziale con una raffinata sfruttamento (exploitation) man mano che il modello converge.

Modello di Privacy

L'algoritmo soddisfa la event-level DP, dove dataset adiacenti differiscono esattamente per una singola coppia utente-ricompensa $(u_t, r_t)$. Le azioni sono trattate come output dell'algoritmo, non come input privati. Il meccanismo utilizza la zCDP per vincoli di composizione più stretti, convertendo in $(\epsilon, \delta)$-DP tramite formule di conversione standard.

Contributi Chiave

1. Thompson Sampling Privato: Il documento prova che l'aggiunta di rumore DP alle statistiche sufficienti produce una specifica inflazione della covarianza posteriore ($v^2 A^{-1} + \sigma^2 A^{-2}$). Ciò consente al TS di interpretare il rumore come incertezza invece che come corruzione.
2. Limite di Regret Stretto: Sotto event-level DP con contesti stocastici, gli autori dimostrano un limite di regret dove il costo di privacy è $O(\sqrt{d} \cdot \log T / \sqrt{\rho})$. Questo è logaritmico in $T$, un miglioramento significativo rispetto ai costi $O(\sqrt{T})$ o $O(T^{3/4})$ associati alla composizione sequenziale o alla joint DP.
3. Analisi dell'Amplificazione della Privacy: Viene fornita un'analisi rigorosa basata su RDP del sottocampionamento di Poisson per i bandit, dimostrando guadagni del 2–4% a valori di $\epsilon$ bassi.
4. Valutazione Esaustiva: Esperimenti estesi su dataset sintetici e reali (MovieLens-25M, Jester) validano le affermazioni teoriche.

Risultati Sperimentali

• Performance vs. Non-Privata: AdaPrivate-TS raggiunge il 93–99% delle prestazioni del Thompson Sampling non privato per budget di privacy $\epsilon \in [0.5, 5]$.
• Confronto con UCB: L'algoritmo supera i baseline UCB privati di 0,5–3,7% in media. Con l'esplorazione adattiva calibrata, il vantaggio cresce fino a un massimo del 18% in configurazioni di privacy estrema.
• Dati del Mondo Reale: Sui dataset MovieLens e Jester, AdaPrivate-TS ottiene le migliori prestazioni complessive tra i baseline event-level, dominando in particolare per $\epsilon \geq 2$.
• Privacy delle Feature: Quando le feature vengono privatizzate tramite DP-SVD, il vantaggio del TS rispetto a UCB aumenta a +11%, confermando che il meccanismo "rumore-come-incertezza" si estende oltre la privacy della ricompensa alla privacy delle feature.
• Ablazione: L'analisi dei componenti mostra che la combinazione di TS, amplificazione della privacy ed esplorazione adattiva produce un guadagno cumulativo di +6,3% rispetto a un baseline UCB privato con rumore.

Significato e Rivendicazioni

L'articolo sostiene che il Thompson Sampling è intrinsecamente più adatto rispetto a UCB per i bandit contestuali privati perché può sfruttare le proprietà strutturali del rumore DP come fonte di esplorazione anziché come fonte di errore.

Le rivendicazioni chiave riguardanti la significatività includono:

• Efficienza: L'uso della composizione parallela con l'elaborazione a lotti permette un costo di privacy che è logaritmico nell'orizzonte temporale $T$, evitando le severe penalità della composizione sequenziale.
• Praticità: L'algoritmo opera senza un curatore centrale fidato, basandosi solo sulla privacy a livello di evento, il che è appropriato per scenari in cui gli utenti contribuiscono con poche interazioni.
• Robustezza: Il metodo rimane stabile sotto feature private (DP-SVD) e offre un modo principato per restringere i budget di privacy tramite il sottocampionamento di Poisson senza sacrificare la qualità della raccomandazione.
• Novità Teorica: L'identificazione dell'inflazione della covarianza indotta dal rumore come meccanismo per il "rumore-come-incertezza" fornisce una nuova prospettiva per progettare algoritmi di apprendimento privati, andando oltre il paradigma di trattare il rumore della privacy esclusivamente come corruzione.

Gli autori concludono che AdaPrivate-TS offre uno strumento principato per i professionisti che necessitano di bilanciare rigorosi requisiti di privacy con prestazioni di raccomandazione di alta qualità, specialmente in contesti con contesti stocastici e vincoli di privacy a livello di evento.