Resumo Técnico: Contabilidade de Privacidade sem Amostragem para Mecanismos de Matriz sob Alocação Aleatória

Declaração do Problema

O artigo aborda o desafio de calcular garantias de privacidade determinísticas e apertadas para o treinamento de modelos com privacidade diferencial que utiliza mecanismos de fatoração de matriz combinados com alocação aleatória (também conhecida como esquema de "bolas em caixas" ou subamostragem de iteração balanceada).

Embora a amplificação de privacidade por subamostragem seja uma técnica padrão para reduzir o ruído no Descenso de Gradiente Estocástico com Privacidade Diferencial (DP-SGD), o esquema de "bolas em caixas" é preferido à subamostragem de Poisson para treinamento em grande escala devido à sua eficiência computacional e cobertura uniforme dos dados. No entanto, quando combinado com fatoração de matriz (que introduz ruído correlacionado entre iterações para melhorar a utilidade), os métodos existentes de contabilidade de privacidade enfrentam limitações significativas:

1. Dependência de Monte Carlo: Abordagens recentes (e.g., Choquette-Choo et al., 2025) dependem de amostragem de Monte Carlo para estimar parâmetros de amplificação. Esta abordagem é computacionalmente cara, particularmente em regimes de alta privacidade onde o número necessário de amostras escala inversamente com $\delta$ (e.g., mostrar $(\epsilon, 10^{-8})$-DP é $10^5$ vezes mais caro que $(\epsilon, 10^{-3})$-DP).
2. Garantias Probabilísticas: Estes métodos baseados em amostragem frequentemente produzem garantias que valem apenas com alta probabilidade ou exigem que o mecanismo empregue abstenção aleatória, em vez de fornecer limites determinísticos $(\epsilon, \delta)$-DP.
3. Intratabilidade Computacional: A distribuição de perda de privacidade para mecanismos de matriz sob alocação aleatória envolve misturas de alta dimensão, tornando a avaliação exata da divergência do bastão de hóquei intratável sem amostragem.

Metodologia

Os autores propõem dois procedimentos de contabilidade distintos e sem amostragem que calculam limites determinísticos explicitamente, aproveitando a estrutura do esquema de alocação aleatória e as correlações introduzidas pela fatoração de matriz.

1. Contabilizador de Divergência de Rényi (Programação Dinâmica)

Este método calcula um limite superior para a divergência de Rényi, que é então convertido para $(\epsilon, \delta)$-DP usando teoremas de conversão padrão.

• Insight Central: A distribuição de perda de privacidade para a direção "remover" (onde um ponto de dados é removido do conjunto de dados) pode ser expressa como uma soma sobre uma matriz de Gram $G$ derivada da matriz de estratégia $C$.
• Redução de Complexidade: Para matrizes gerais, provar-se que o cálculo desta soma é #P-completo. No entanto, para matrizes estruturadas (e.g., matrizes banda onde a matriz de estratégia $C$ tem largura de banda $p$), a matriz de Gram $G$ herda uma estrutura ciclicamente banda.
• Algoritmo: Os autores formulam uma abordagem de programação dinâmica para calcular a soma exatamente para matrizes de largura de banda $p$.
  • Complexidade: O tempo de execução é reduzido de exponencial $O(2^\alpha)$ (na ordem $\alpha$) para polinomial $O(b p \alpha^{2p})$, onde $b$ é o número de lotes por época.
  • Truncamento: Para matrizes que não são estritamente banda, mas possuem entradas de decaimento rápido (e.g., matrizes inversas banda), o método truncar a matriz de Gram e adiciona um termo de correção aditivo computável para garantir que o limite permaneça válido.
• Direção Adicionar: Um limite superior analítico apertado e separado é derivado para a direção "adicionar" usando a desigualdade da média aritmética-média geométrica (AM-GM).

2. Contabilizador de Composição Condicional

Este método aborda o regime de "$\epsilon$ pequeno" (alta privacidade) onde as fórmulas de conversão de Rényi podem ser frouxas. Ele supera a interdependência dos passos causada pela correlação do ruído e contagens de participação fixas.

• Conceito: Em vez de assumir passos independentes, o método usa composição condicional. Ele identifica resultados "bons" onde as distribuições condicionais do mecanismo no passo $n$ são dominadas por um par de distribuições fixas e fatorizáveis $(P^{(n)}, Q^{(n)})$.
• Eventos Ruins: O método contabiliza resultados "ruins" (onde a dominância falha) limitando sua probabilidade $\delta_E$. A perda total de privacidade é a composição dos passos independentes mais $\delta_E$.
• Critério de Dominância: Os autores derivam um critério baseado em funções de risco reverso de pesos de mistura Gaussiana. Eles mostram que, se a função de risco reverso posterior for pontualmente menor que a função de risco reverso de uma distribuição alvo, a dominância vale.
• Limites de Cauda: Para determinar os parâmetros das distribuições dominantes, os autores derivam limites analíticos de cauda sobre a perda de privacidade de misturas Gaussianas ternárias. Eles utilizam uma família variacional de distribuições para apertar esses limites, otimizando sobre parâmetros de temperatura para minimizar o desvio padrão do limite de cauda.
• Eficiência: Embora a avaliação inicial seja $O(N^2 b^2)$, avaliações subsequentes para diferentes multiplicadores de ruído $\sigma$ podem ser amortizadas para $O(N b^2)$, tornando-o eficiente para calibração de mecanismos.

Contribuições Principais

1. Contabilidade Determinística: O artigo introduz os primeiros métodos sem amostragem para calcular garantias determinísticas $(\epsilon, \delta)$-DP para mecanismos de matriz sob alocação aleatória, eliminando a necessidade de estimativa de Monte Carlo.
2. Complexidade Aprimorada para DP-SGD: Para o caso especial de ruído não correlacionado (DP-SGD padrão), o contabilizador de Rényi proposto melhora a complexidade computacional da contabilidade exata sob alocação aleatória de exponencial $O(2^\alpha)$ para polinomial $O(b \alpha^2)$, superando significativamente métodos exatos anteriores.
3. Generalização para Ruído Correlacionado: O quadro estende-se a mecanismos de matriz banda e não banda arbitrários (incluindo Raiz Quadrada Banda, Inversa Banda e Toeplitz Linear Bufferizada), lidando com as complexas correlações inter-passos inerentes a esses mecanismos.
4. Apertamento Dual-Regime: A combinação do contabilizador de Rényi (forte no regime de baixa privacidade/grande-$\epsilon$) e do contabilizador de composição condicional (mais apertado no regime de alta privacidade/pequeno-$\epsilon$) fornece uma solução de contabilidade abrangente.

Resultados

Os autores avaliam seus métodos contra o contabilizador de Monte Carlo mais avançado através de vários mecanismos de matriz (DP-SGD, BSR, BISR, BandMF, BandInvMF, BLT) e configurações (época única e múltipla).

• Precisão: No regime de baixa privacidade ($\epsilon \ge 2$), o contabilizador de Rényi corresponde estreitamente à referência de Monte Carlo. No regime de alta privacidade ($\epsilon \le 1$), o contabilizador de composição condicional produz limites mais apertados, permitindo multiplicadores de ruído calibrados $\sigma$ menores em comparação com as estimativas de Monte Carlo.
• Robustez: O desempenho mantém-se através de diferentes larguras de banda ($p$) e números de lotes ($b$).
• Utilidade: Experimentos no CIFAR-10 demonstram que os multiplicadores de ruído derivados dessas garantias sem amostragem preservam os benefícios de utilidade do uso de ruído correlacionado sobre ruído não correlacionado.
• Tempo de Execução: Os métodos superam a dependência $O(\delta^{-1})$ da amostragem de Monte Carlo. Embora o contabilizador de composição condicional tenha um custo inicial mais alto para grande $N$, seu custo amortizado para calibração é significativamente menor que o de Monte Carlo para orçamentos de privacidade estritos.

Significado e Alegações

O artigo alega fornecer a primeira contabilidade de privacidade sem amostragem para mecanismos com gradientes e participações correlacionados. Seu significado reside em:

• Habilitar Garantias Determinísticas: Remove a dependência de limites probabilísticos ou abstenção aleatória, que são frequentemente impraticáveis ou teoricamente mais fracos para sistemas de produção.
• Escalabilidade: Ao reduzir a complexidade da contabilidade exata de Rényi para alocação aleatória de exponencial para polinomial, torna a contabilidade de privacidade precisa viável para execuções de treinamento em grande escala onde a amostragem de Monte Carlo seria computacionalmente proibitiva.
• Calibração Prática: A capacidade de calcular eficientemente limites apertados através de uma ampla gama de $\epsilon$ e $\delta$ facilita uma melhor calibração de multiplicadores de ruído, melhorando diretamente o compromisso utilidade-privacidade no aprendizado profundo com privacidade diferencial.

Os autores reconhecem limitações, notando que a complexidade do contabilizador de Rényi permanece exponencial na largura de banda $p$ (embora polinomial em $\alpha$), e o método de composição condicional depende de uma partição grosseira de resultados que pode ser pessimista. Eles sugerem que trabalhos futuros poderiam explorar partições mais granulares e inferência variacional mais eficiente para apertar ainda mais os limites.