DP-SPRT: Differentially Private Sequential Probability Ratio Tests

Resumo Técnico: DP-SPRT: Testes de Razão de Probabilidade Sequencial com Privacidade Diferencial

Definição do Problema

O teste de hipóteses sequencial, especificamente o Teste de Razão de Probabilidade Sequencial (SPRT) de Wald, é um método fundamental para tomar decisões com o mínimo de dados, interrompendo a coleta assim que a evidência estatística é suficiente. No entanto, aplicar o SPRT a dados sensíveis (ex: ensaios clínicos, registros financeiros) acarreta riscos significativos à privacidade. A natureza adaptativa do teste sequencial significa que a decisão de interromper a coleta de dados pode vazar informações sobre observações recentes. Embora a Privacidade Diferencial (DP) seja o padrão para proteger dados em configurações de amostra fixa, os mecanismos de DP existentes (ex: AboveThreshold) não são diretamente otimizáveis para testes sequenciais, que exigem o monitoramento simultâneo de limites superiores e inferiores. Tentativas anteriores de privatizar o SPRT basearam-se em noções de privacidade mais fracas, careceram de um método para calibrar limiares para taxas de erro específicas ou exigiram simulações de Monte Carlo que vazam privacidade para o ajuste de parâmetros.

Metodologia

Os autores propõem o DP-SPRT, um framework geral para testes de razão de probabilidade sequencial com privacidade diferencial. O núcleo da metodologia envolve duas inovações principais:

1. O Mecanismo OutsideInterval:
   Para abordar a necessidade de monitorar simultaneamente dois limiares (para aceitar $H_0$ ou $H_1$), os autores introduzem um novo mecanismo chamado OutsideInterval. Ao contrário da composição ingênua de técnicas existentes como o AboveThreshold (que exigiria duas instâncias separadas e dobraria o custo de privacidade), o OutsideInterval processa uma sequência de consultas e interrompe quando o resultado de uma consulta cai fora de um intervalo pré-definido $[T_0, T_1]$.

   • Ele adiciona ruído tanto aos resultados das consultas quanto aos limiares.
   • Crucialmente, ele utiliza a mesma realização de ruído para ambas as comparações de limiar, o que torna a análise de privacidade mais rigorosa.
   • Este mecanismo alcança uma melhoria de fator-2 nas garantias de privacidade em comparação com a composição de duas instâncias separadas de AboveThreshold.

2. Framework DP-SPRT:
   Os autores adaptam o SPRT clássico injetando ruído cuidadosamente calibrado tanto na estatística de teste (média empírica) quanto nos limiares de decisão.

   • Alocação de Ruído: O framework suporta várias distribuições de ruído, analisando especificamente o ruído de Laplace (para $\epsilon$-DP pura) e o ruído Gaussiano (para Privacidade Diferencial de Rényi, RDP).
   • Controle de Erro: Uma função de correção $C(n, \delta)$ e um parâmetro de alocação de erro $\gamma$ são introduzidos para decompor o orçamento total de erro entre o erro estatístico do SPRT e o erro introduzido pelo ruído de privacidade. Isso permite que o teste seja calibrado para atingir taxas prescritas de Erro Tipo I ($\alpha$) e Tipo II ($\beta$) sem ajuste empírico.
   • Subamostragem (Subsampling): Para regimes de alta privacidade, os autores propõem uma variante usando subamostragem para computar a média empírica, o que amplifica a privacidade e reduz a magnitude do ruído necessário.

Principais Contribuições

1. Framework Geral: Introdução do DP-SPRT, um invólucro (wrapper) que suporta vários mecanismos de ruído enquanto fornece garantias rigorosas de privacidade e controle de erro para testes de hipóteses sequenciais.
2. Mecanismo OutsideInterval: Um novo mecanismo privado para comparar uma sequência de consultas contra dois limiares simultaneamente. Oferece uma melhoria de privacidade de fator-2 sobre a composição ingênua e é aplicável a outros problemas de monitoramento contínuo.
3. Limites Teóricos:
   • Limites Superiores: São derivados limites superiores genéricos para o erro e a complexidade de amostragem do DP-SPRT para observações de Bernoulli, acomodando tanto ruído de Laplace quanto Gaussiano.
   • Limites Inferiores: Os autores provam um limite inferior na complexidade de amostragem para qualquer teste $\epsilon$-DP com erros prescritos. Isso revela dois regimes: um onde a privacidade tem impacto mínimo no tamanho da amostra, e outro onde requisitos de alta privacidade aumentam significativamente o tamanho de amostra esperado.
   • Quase-Otimalidade: Ao comparar seus limites superiores com os limites inferiores derivados, os autores mostram que o DP-SPRT com ruído de Laplace é quase-ótimo quando as taxas de erro são pequenas e as duas hipóteses estão próximas.
4. Calibração Prática: Diferente de trabalhos anteriores (ex: PrivSPRT) que dependem de simulações de Monte Carlo para determinar limiares (um processo que pode vazar privacidade), o DP-SPRT fornece limiares teoricamente calibrados que garantem o controle de erro.

Resultados

• Desempenho Teórico: A análise demonstra que o DP-SPRT com ruído de Laplace alcança uma complexidade de amostragem quase-ótima no regime de erros pequenos e hipóteses próximas, correspondendo ao limite inferior derivado até um fator multiplicativo constante.
• Desempenho Experimental: Experimentos com dados simulados de Bernoulli ($p_0=0.3, p_1=0.7$) com erros alvo de $\alpha=\beta=0.05$ mostram:
  • Eficiência: Variantes do DP-SPRT (Laplace, Gaussiana e Laplace com subamostragem) consistentemente requerem menos amostras (tempos de parada menores) do que o método PrivSPRT existente em vários níveis de privacidade ($\epsilon$).
  • Precisão: As taxas empíricas de Erro Tipo I para o DP-SPRT permanecem abaixo do $\alpha$ alvo em todos os níveis de privacidade. Em contraste, o PrivSPRT ocasionalmente excede a taxa alvo, o que é atribuído ao ruído introduzido durante sua calibração de Monte Carlo.
  • Benefícios da Subamostragem: A variante de subamostragem do DP-SPRT mostra melhorias substanciais em regimes de alta privacidade (baixo $\epsilon$), validando o efeito de amplificação de privacidade.

Significância e Alegações

O artigo afirma preencher uma lacuna significativa na literatura ao fornecer o primeiro teste sequencial $\epsilon$-DP que pode ser teoricamente calibrado para atingir erros Tipo I e Tipo II prescritos sem ajuste de hiperparâmetros ou simulações que vazam privacidade. Os autores enfatizam que seu trabalho:

• Estabelece um equilíbrio (trade-off) rigoroso entre privacidade e utilidade para testes sequenciais, particularmente para distribuições de Bernoulli.
• Demonstra que o ruído de Laplace, anteriormente considerado inadequado para testes sequenciais por alguns, é na verdade quase-ótimo em regimes específicos quando usado com seu framework.
• Introduz o mecanismo OutsideInterval como uma contribuição potencialmente independente para qualquer aplicação que exija o monitoramento simultâneo de dois limiares sob privacidade diferencial.
• Fornece um limite inferior rigoroso que caracteriza o custo fundamental da privacidade em testes sequenciais, mostrando que, embora a privacidade aumente a complexidade de amostragem, o algoritmo proposto minimiza esse custo de forma eficaz.

Os autores mantêm um tom modesto quanto ao seu escopo, observando que suas garantias de otimalidade são atualmente estabelecidas para observações de Bernoulli e hipóteses simples, com extensões para hipóteses compostas e outras distribuições identificadas como trabalhos futuros.