Resumo Técnico: Auditoria Sequencial para $f$-Privacidade Diferencial

Declaração do Problema

A Privacidade Diferencial (DP) é o padrão para quantificar a privacidade no processamento de dados, mas verificar se uma implementação específica adere às suas garantias teóricas continua sendo um desafio crítico. Os auditores empíricos existentes tipicamente dependem de procedimentos de amostra fixa (lote/batch) direcionados à noção tradicional de $(\varepsilon, \delta)$-DP. Essas abordagens sofrem de duas limitações primárias:

1. Ineficiência: Elas exigem um tamanho de amostra pré-especificado. Como o "tamanho do efeito" (a magnitude da violação de privacidade) é desconhecido antes do teste, os profissionais frequentemente escolhem tamanhos de amostra excessivamente grandes para evitar resultados inconclusivos, levando a custos computacionais proibitivos, especialmente para procedimentos de treinamento caros como o DP-SGD.
2. Expressividade Limitada: O framework $(\varepsilon, \delta)$ oferece uma visão "localizada" da privacidade, falhando em capturar todo o espectro de compensação entre privacidade e utilidade. Em contraste, a $f$-Privacidade Diferencial ($f$-DP) caracteriza todo o comportamento de privacidade por meio de uma única curva de compensação, tornando-a mais adequada para testes estatísticos e melhor adaptada a mecanismos modernos como o DP-SGD.

Embora trabalhos recentes tenham introduzido testes sequenciais para $(\varepsilon, \delta)$-DP, há uma carência de auditores sequenciais para o framework $f$-DP, que é mais expressivo e capaz de determinar adaptativamente os tamanhos de amostra mantendo garantias estatísticas rigorosas.

Metodologia

Os autores propõem o APT (Advanced Privacy Testing), um framework de auditoria sequencial para $f$-DP. A ideia central é coletar amostras de forma adaptativa até que uma decisão (violação ou não violação) seja alcançada com significância estatística, em vez de usar um tamanho de lote fixo.

1. Framework de Teste Sequencial

O auditor enquadra o problema como um teste de hipótese:

• $H_0$: O mecanismo satisfaz a curva $f$-DP reivindicada $f$ (ou seja, a função de compensação $T(\alpha) \geq f(\alpha)$ para todo $\alpha$).
• $H_1$: O mecanismo viola a reivindicação (ou seja, $\exists \alpha^*$ tal que $T(\alpha^*) < f(\alpha^*)$).

Ao contrário das abordagens sequenciais ingênuas que aplicam repetidamente testes de amostra fixa (o que infla a taxa de falso rejeição), o APT emprega inferência válida a qualquer momento (anytime-valid inference). Ele constrói um estatístico de teste sequencial baseado nos erros de classificação empíricos $(\hat{\alpha}, \hat{\beta})$ e os compara contra funções de fronteira derivadas da teoria de aproximação Gaussiana (especificamente, o comportamento do movimento Browniano). Isso garante que a taxa de falso rejeição (nível de significância $\gamma$) seja controlada mesmo conforme o tamanho da amostra cresce indefinidamente.

2. Construção do Classificador

Para estimar a função de compensação, o auditor requer um classificador $\phi$ para distinguir entre distribuições de saída $P$ (de um conjunto de dados $D$) e $Q$ (de um conjunto de dados vizinho $D'$). O framework suporta ambos:

• Configuração Whitebox: O analista conhece os parâmetros do mecanismo (ex: distribuição de ruído). Um classificador de Razão de Verossimilhança paramétrico (ex: limiarização Gaussiana) é utilizado.
• Configuração Blackbox: Apenas o acesso de entrada/saída está disponível. O auditor utiliza Estimativa de Densidade Kernel (KDE) para aproximar as densidades de $P$ e $Q$, construindo um classificador de Razão de Verossimilhança perturbado.

3. Ajuste de Limiar Ótimo

Um componente crítico é a seleção do limiar ideal $\eta$ para o classificador. Os autores propõem uma nova estratégia geométrica (Equação 8) que seleciona $\eta$ para maximizar a distância euclidiana entre o par de erros estimados $(\hat{\alpha}, \hat{\beta})$ e a curva reivindicada $f$ ao longo da diagonal de 45 graus. Mostra-se que isso é mais poderoso para detectar violações do que as regras de seleção anteriores baseadas em distância vertical.

4. Fluxo do Algoritmo

O algoritmo APT (Algoritmo 1) procede da seguinte forma:

1. Burn-in: Desenha uma pequena amostra inicial para calibrar parâmetros e construir um classificador inicial.
2. Loop Sequencial: Itera o desenho de novas amostras $(X_k, Y_k)$.
3. Atualização: Atualiza periodicamente o classificador (se estiver em modo blackbox) e reestima os erros de classificação.
4. Decisão: Aplica estimadores ajustados por confiança para verificar se os erros estimados caem significativamente abaixo da curva reivindicada $f$. Se a fronteira for cruzada, o algoritmo para e reporta uma violação.

Principais Contribuições

1. Primeiro Auditor Sequencial de $f$-DP: O artigo apresenta o primeiro auditor capaz de testar sequencialmente reivindicações de $f$-DP, suportando tanto configurações whitebox quanto blackbox.
2. Garantias Teóricas: Os autores fornecem provas (Teorema 3.1) mostrando que:
   • A taxa de falso rejeição é limitada por um $\gamma$ especificado pelo usuário (mesmo para tamanhos de amostra infinitos).
   • O tamanho de amostra necessário para detectar uma violação é próximo do ótimo, dentro de um fator logarítmico do mínimo teórico exigido por um teste de amostra fixa com tamanho de efeito conhecido.
3. Melhoria no Ajuste do Classificador: Uma nova estratégia geométrica para selecionar o limiar do classificador ideal que melhora o poder de detecção em relação aos métodos existentes de lote fixo.
4. Implementação de Código Aberto: Os autores fornecem um repositório público com código para reproduzir os resultados e aplicar o auditor.

Resultados Experimentais

Os autores avaliaram o APT em benchmarks sintéticos (mecanismos Gaussiano e Laplace) e em um cenário real de DP-SGD.

• Eficiência de Amostra: Em experimentos controlados, o APT detectou violações com significativamente menos amostras do que as linhas de base de lote fixo. Para violações fortes, a detecção ocorreu frequentemente em poucas centenas de amostras.
• Comparação com Trabalhos Anteriores: O artigo compara o APT com um auditor sequencial recente de $(\varepsilon, \delta)$-DP [22] em benchmarks de ruído aditivo.
  • Em regimes de $\varepsilon$ pequeno, o APT exigiu aproximadamente 10%–25% das amostras reportadas por [22] para rejeitar mecanismos com bugs.
  • Em regimes de $\varepsilon$ maior, o substituto baseado em MMD usado por [22] sofre de um "efeito de saturação" onde a margem de teste desaparece, causando falha na detecção. O APT permanece eficaz em uma gama mais ampla de parâmetros de privacidade porque não depende deste substituto.
• DP-SGD Real: Em um cenário de auditoria de "uma execução" (one-run) no CIFAR-10, a abordagem sequencial demonstrou que, para violações claras, o número de pontuações de canário necessárias para atingir uma decisão foi drasticamente reduzido (caindo de milhares para centenas) comparado à execução de um teste de lote fixo no conjunto completo.

Significância e Alegações

O artigo afirma que o APT aborda o gargalo computacional na auditoria de privacidade ao eliminar a necessidade de tamanhos de amostra pré-especificados e, muitas vezes, excessivos. Ao mudar o foco para $f$-DP e utilizar testes sequenciais, o método permite:

• Redução de Custo: Particularmente benéfico para mecanismos caros como o DP-SGD, onde reexecutar o treinamento ou pontuar um grande número de canários é proibitivo.
• Controle Rigoroso: Mantendo garantias estritas de significância estatística sem a penalidade de "espiar" (peeking) associada aos testes sequenciais ingênuos.
• Adaptabilidade: A capacidade de detectar violações rapidamente quando estas são grandes, enquanto continua a amostrar apenas o tempo necessário para violações sutis.

Os autores enfatizam que este trabalho pretende complementar as ferramentas de auditoria existentes, fornecendo um wrapper sequencial genérico que pode ser aplicado a qualquer auditor de $f$-DP para melhorar a eficiência de amostragem. Eles explicitamente observam que sua comparação com [22] não é uma alegação de dominância universal, pois os dois métodos auditam objetos de privacidade diferentes, mas sim uma demonstração de eficiência superior em regimes específicos e relevantes.