Resumo Técnico: Filtros de Privacidade f-Diferencial: Validade e Soluções Aproximadas

Declaração do Problema

O artigo aborda o desafio de contabilizar a perda de privacidade sob composição totalmente adaptativa na privacidade diferencial (DP). Em cenários totalmente adaptativos, a escolha dos mecanismos e seus parâmetros de privacidade pode depender do histórico de saídas anteriores, um cenário comum em algoritmos iterativos como o gradiente descendente estocástico diferencialmente privado (DP-SGD).

Embora existam filtros de privacidade (regras de parada) para DP $(\epsilon, \delta)$ e DP de Rényi (RDP), a validade de filtros baseados em Privacidade f-Diferencial (f-DP) permanece incerta. A f-DP caracteriza a extensão total do teste de hipóteses adversarial por meio de funções de troca e recupera a DP $(\epsilon, \delta)$ por meio de funções de troca lineares por partes. Sabe-se que os produtos tensoriais de f-DP fornecem os resultados de composição mais apertados para cenários não adaptativos. A questão central é se um filtro "natural" de f-DP — que rastreia o produto tensorial acumulativo de funções de troca e para quando uma curva prescrita é cruzada — permanece válido sob total adaptatividade.

Metodologia e Estrutura Teórica

1. Análise da Validade do Filtro Natural de f-DP

Os autores investigam o filtro "natural" de f-DP, definido como continuar enquanto o produto tensorial das funções de troca realizadas $f_1 \otimes \dots \otimes f_t$ permanecer acima de uma curva de orçamento $f_B$.

• Construção de Contraexemplo: O artigo demonstra que essa abordagem é fundamentalmente inválida no cenário totalmente adaptativo. Mesmo que os mecanismos individuais sejam válidos e a função de troca composta nunca exceda o limiar ao longo de um histórico específico, a composição adaptativa pode violar o orçamento.
• Mecanismo de Falha: A falha ocorre porque o produto adaptativo de funções de troca depende da realização específica das saídas, o que determina a seleção dos mecanismos subsequentes. Se uma família de funções de troca futuras potenciais contiver um "ponto de calibração" (onde as funções se intersectam), a seleção adaptativa pode explorar isso para alcançar um perfil de perda de privacidade estritamente pior (função de troca mais baixa) do que o limite inferior do produto tensorial dos ramos individuais. Esse fenômeno ocorre até mesmo para mecanismos Gaussianos com amostragem, o cavalo de batalha da aprendizagem de máquina privada.

2. Caracterização das Condições de Validade

Os autores estabelecem condições necessárias e suficientes para que o filtro natural de f-DP seja válido:

• Cadeias de Blackwell: O filtro é válido se e somente se a família de funções de troca disponíveis (e seus produtos tensoriais) formar uma cadeia de Blackwell. Uma família é uma cadeia de Blackwell se quaisquer duas funções na família estiverem totalmente ordenadas (uma domina a outra ponto a ponto).
• Implicação: Isso explica por que RDP e DP Gaussiana (GDP) admitem filtros simples e válidos: suas garantias são de valor escalar (ou formam cadeias de Blackwell como as funções de troca Gaussianas $G_\mu$ onde $\mu$ é um escalar), garantindo comparabilidade. Em contraste, funções de troca gerais de f-DP nem sempre são ordenadas de Blackwell, levando à falha do filtro natural.

3. Teorema do Limite Central (CLT) Totalmente Adaptativo

Para contornar a invalidade dos filtros exatos de f-DP, o artigo prova um Teorema do Limite Central (CLT) de f-DP totalmente adaptativo.

• Abordagem: Os autores modelam a perda de privacidade como um processo estocástico de Variáveis Aleatórias de Perda de Privacidade (PLRVs). Usando uma variante de martingale do limite de Berry–Esseen (Fan, 2019), eles provam que, sob condições de regularidade específicas (médias e variâncias condicionais limitadas e momentos de ordem superior controlados), a perda de privacidade cumulativa converge para uma distribuição Gaussiana.
• Resultado: Essa convergência permite a construção de filtros GDP aproximados. Em vez de rastrear a função de troca completa, pode-se rastrear as médias e variâncias condicionais cumulativas das PLRVs. O erro dessa aproximação é quantificado pelo termo de erro do CLT $\Delta$.

4. Filtro GDP Aproximado para Mecanismos Gaussianos com Amostragem

Como uma instanciação concreta, os autores derivam aproximações de momentos em forma fechada para mecanismos Gaussianos com amostragem em dois regimes assintóticos:

• Baixa amostragem ($q \ll 1$): A média e a variância da PLRV são aproximadas usando expansões de Taylor.
• Alta amostragem ($q \approx 1$): Aproximações semelhantes são derivadas para o limite onde a taxa de amostragem se aproxima de 1.
• Algoritmo: Eles propõem um algoritmo que rastreia essas aproximações de momentos para impor um orçamento. Este filtro evita rastrear a função de troca completa, oferecendo uma alternativa computacionalmente eficiente à contabilidade baseada em FFT numérica.

Resultados Principais

1. Invalidade de Filtros Naturais: O filtro natural de f-DP é inválido para composições totalmente adaptativas de mecanismos Gaussianos com amostragem. Contraexemplos explícitos mostram que a composição adaptativa pode violar o orçamento mesmo quando todos os ramos não adaptativos o satisfazem.
2. Caracterização de Validade: O filtro natural é válido se e somente se a família de funções de troca formar uma cadeia de Blackwell. Isso fornece uma fronteira teórica nítida para quando a contabilidade baseada em funções de troca é possível sob total adaptatividade.
3. Aproximação Baseada em CLT: O CLT totalmente adaptativo estabelece que as perdas de privacidade cumulativas convergem para distribuições Gaussianas. Isso permite a construção de filtros GDP aproximados que são provadamente válidos em regimes assintóticos.
4. Comparação de Desempenho:
   • Em regimes assintóticos ($q \ll 1$ e $q \approx 1$), o filtro GDP aproximado proposto produz garantias de privacidade estritamente mais apertadas do que a contabilidade RDP totalmente adaptativa (especificamente o filtro de RDP de ordem única $(1, B)$).
   • O artigo observa que, embora a contabilidade baseada em RDP seja conhecida por ser frouxa, essa folga mostra-se decorrer da redução com perda para divergências de Rényi, e não de uma barreira fundamental na composição adaptativa.
   • No entanto, a aproximação baseada em CLT é conhecida por ser otimista (subestimando a perda de privacidade) em taxas de amostragem moderadas e realistas (por exemplo, $q=0,1$), uma limitação compartilhada com aproximações de CLT não adaptativas.

Significado e Alegações

O artigo afirma resolver uma questão aberta central sobre filtros de f-DP:

• Resolução Teórica: Ele demonstra definitivamente que a extensão intuitiva da composição padrão de f-DP para filtros adaptativos falha, esclarecendo por que noções baseadas em divergência (RDP) têm sucesso onde noções baseadas em funções de troca (f-DP geral) falham sem restrições estruturais.
• Contribuição Construtiva: Ao provar o CLT totalmente adaptativo, o artigo fornece uma metodologia geral para construir filtros GDP aproximados para qualquer família de mecanismos onde os momentos das PLRVs possam ser aproximados analiticamente.
• Implicação Prática: Para mecanismos Gaussianos com amostragem, o filtro proposto oferece uma alternativa em forma fechada e eficiente à contabilidade numérica. Em regimes extremos de amostragem, ele fornece garantias estritamente mais apertadas do que os filtros baseados em RDP mais avançados atuais, demonstrando que a "folga" no RDP é um artefato da representação, e não um custo inerente da adaptatividade.

Os autores permanecem modestos quanto às limitações, reconhecendo que a abordagem baseada em CLT é otimista em taxas de amostragem realistas e que fechar a lacuna em taxas moderadas permanece um desafio aberto. Eles também observam que a validade do filtro natural está restrita a condições estruturais específicas (cadeias de Blackwell) que não são geralmente atendidas por mecanismos arbitrários de f-DP.