DP-SPRT: Differentially Private Sequential Probability Ratio Tests

Sintesi Tecnica: DP-SPRT: Test di Rapporto di Probabilità Sequenziale Differenzialmente Privato

Definizione del Problema

Il test di ipotesi sequenziale, specificamente il Test di Rapporto di Probabilità Sequenziale (SPRT) di Wald, è un metodo fondamentale per prendere decisioni con un numero minimo di dati, interrompendo la raccolta non appena l'evidenza statistica è sufficiente. Tuttavia, l'applicazione dello SPRT a dati sensibili (ad esempio, trial clinici, registri finanziari) comporta rischi significari per la privacy. La natura adattiva del testing sequenziale significa che la decisione di interrompere la raccolta dei dati può rivelare informazioni sulle osservazioni recenti. Sebbene la Differential Privacy (DP) sia il framework standard per proteggere i dati in contesti a campione fisso, gli esistenti meccanismi DP (ad esempio, AboveThreshold) non sono direttamente ottimali per il testing sequenziale, che richiede il monitoraggio simultaneo sia dei limiti superiori che di quelli inferiori. I tentativi precedenti di privatizzare lo SPRT si sono basati su nozioni di privacy più deboli, mancavano di un metodo per calibrare le soglie per specifici tassi di errore, o richiedevano simulazioni Monte Carlo che violavano la privacy per la calibrazione.

Metodologia

Gli autori propongono DP-SPRT, un framework generale per i test di rapporto di probabilità sequenziale differenzialmente privati. Il nucleo della metodologia coinvolge due innovazioni principali:

1. Il Meccanismo OutsideInterval:
   Per affrontare la necessità di monitorare simultaneamente due soglie (per accettare $H_0$ o $H_1$), gli autori introducono un nuovo meccanismo chiamato OutsideInterval. A differenza delle composizioni naive di tecniche esistenti come AboveThreshold (che richiederebbero due istanze separate e raddoppierebbero il costo della privacy), OutsideInterval elabora una sequenza di query e si interrompe quando il risultato di una query cade al di fuori di un intervallo predefinito $[T_0, T_1]$.

   • Aggiunge rumore sia ai risultati delle query che alle soglie.
   • Fondamentalmente, utilizza la stessa realizzazione di rumore per entrambi i confronti delle soglie, il che rende più stringente l'analisi della privacy.
   • Questo meccanismo ottiene un miglioramento del fattore 2 nelle garanzie di privacy rispetto alla composizione di due istanze separate di AboveThreshold.

2. Framework DP-SPRT:
   Gli autori adattano il classico SPRT iniettando rumore accuratamente calibrato sia nella statistica del test (media empirica) che nelle soglie decisionali.

   • Allocazione del Rumore: Il framework supporta varie distribuzioni di rumore, analizzando specificamente il rumore di Laplace (per la pure $\epsilon$-DP) e il rumore Gaussiano (per la Rényi Differential Privacy, RDP).
   • Controllo dell'Errore: Una funzione di correzione $C(n, \delta)$ e un parametro di allocazione dell'errore $\gamma$ vengono introdotti per scomporre il budget totale dell'errore tra l'errore statistico dello SPRT e l'errore introdotto dal rumore di privacy. Ciò consente di calibrare il test per raggiungere prescritti tassi di errore di Tipo I ($\alpha$) e Tipo II ($\beta$) senza una sintonizzazione empirica.
   • Sottocampionamento (Subsampling): Per regimi di alta privacy, gli autori propongono una variante che utilizza il sottocampionamento per calcolare la media empirica, il che amplifica la privacy e riduce l'entità del rumore richiesto.

Contributi Chiave

1. Framework Generale: Introduzione di DP-SPRT, un wrapper che supporta vari meccanismi di rumore fornendo al contempo garanzie di privacy rigorose e controllo dell'errore per il testing ipotetico sequenziale.
2. Meccanismo OutsideInterval: Un nuovo meccanismo privato per confrontare una sequenza di query contro due soglie simultaneamente. Offre un miglioramento della privacy di un fattore 2 rispetto alla composizione naive ed è applicabile ad altri problemi di monitoraggio continuo.
3. Limiti Teorici:
   • Limiti Superiori: Sono derivati limiti superiori generici sull'errore e sulla complessità campionaria per DP-SPRT per osservazioni Bernoulli, accogliendo sia il rumore di Laplace che quello Gaussiano.
   • Limiti Inferiori: Gli autori dimostrano un limite inferiore sulla complessità campionaria per qualsiasi test $\epsilon$-DP con errori prescritti. Ciò rivela due regimi: uno in cui la privacy ha un impatto minimo sulla dimensione del campione, e un altro in cui requisiti di privacy elevati aumentano significativamente la dimensione campionaria attesa.
   • Near-Ottimalità: Confrontando i loro limiti superiori con i limiti inferiori derivati, gli autori mostrano che DP-SPRT con rumore di Laplace è vicino all'ottimalità quando i tassi di errore sono piccoli e le due ipotesi sono vicine.
4. Calibrazione Pratica: A differenza del lavoro precedente (ad esempio, PrivSPRT) che si affida a simulazioni Monte Carlo per determinare le soglie (un processo che può violare la privacy), DP-SPRT fornisce soglie teoricamente calibrate che garantiscono il controllo dell'errore.

Risultati

• Performance Teorica: L'analisi dimostra che DP-SPRT con rumore di Laplace raggiunge una complessità campionaria quasi ottimale nel regime di piccoli errori e ipotesi vicine, eguagliando il limite inferiore derivato fino a una costante moltiplicativa.
• Performance Sperimentale: Esperimenti su dati Bernoulli simulati ($p_0=0.3, p_1=0.7$) con errori target $\alpha=\beta=0.05$ mostrano:
  • Efficienza: Le varianti di DP-SPRT (Laplace, Gaussiano e Laplace con sottocampionamento) richiedono costantemente meno campioni (tempi di arresto minori) rispetto al metodo PrivSPRT esistente attraverso vari livelli di privacy ($\epsilon$).
  • Accuratezza: I tassi di errore empirici di Tipo I per DP-SPRT rimangono al di sotto del target $\alpha$ in tutti i livelli di privacy. Al contrario, PrivSPRT occasionalmente eccede il tasso target, un fenomeno attribuito al rumore introdotto durante la sua calibrazione Monte Carlo.
  • Benefici del Sottocampionamento: La variante di sottocampionamento di DP-SPRT mostra miglioramenti sostanziali nei regimi di alta privacy (basso $\epsilon$), validando l'effetto di amplificazione della privacy.

Significato e Rivendicazioni

L'articolo sostiene di colmare una lacuna significativa nella letteratura fornendo il primo test sequenziale $\epsilon$-DP che può essere teoricamente calibrato per ottenere prescritti errori di Tipo I e Tipo II senza la sintonizzazione di iperparametri o simulazioni che violano la privacy. Gli autori sottolineano che il loro lavoro:

• Stabilisce un compromesso (trade-off) stretto tra privacy e utilità per il testing sequenziale, particolarmente per le distribuzioni di Bernoulli.
• Dimostra che il rumore di Laplace, precedentemente considerato inadatto per il testing sequenziale da alcuni, è in realtà vicino all'ottimalità in regimi specifici quando utilizzato con il loro framework.
• Introduce il meccanismo OutsideInterval come un contributo potenzialmente indipendente per qualsiasi applicazione che richieda il monitoraggio simultaneo di due soglie sotto la differential privacy.
• Fornisce un limite inferiore rigoroso che caratterizza il costo fondamentale della privacy nel testing sequenziale, mostrando che, sebbene la privacy aumenti la complessità campionaria, l'algoritmo proposto ne minimizza efficacementamente il costo.

Gli autori mantengono un tono modesto riguardo all'ambito del loro lavoro, notando che le loro garanzie di ottimalità sono attualmente stabilite per osservazioni Bernoulli e ipotesi semplici, con estensioni a ipotesi composte e altre distribuzioni identificate come lavori futuri.