Resumo Técnico: Funções de Trade-off para DP-SGD com Subamostragem Baseada em Embaralhamento Aleatório

Declaração do Problema

O Descenso de Gradiente Estocástico com Privacidade Diferencial (DP-SGD) é o mecanismo padrão para treinar modelos de aprendizado profundo sob restrições de privacidade. Embora o framework de Privacidade Diferencial $f$ ($f$-DP) forneça a caracterização mais apertada possível das garantias de privacidade por meio de funções de trade-off entre as taxas de falso-positivo e falso-negativo, as análises existentes focaram predominantemente na subamostragem de Poisson (onde pontos de dados são incluídos independentemente em minibatches com probabilidade fixa).

No entanto, implementações práticas de DP-SGD e otimização estocástica tipicamente empregam embaralhamento aleatório, onde o conjunto de dados é permutado uma vez por época e partitionado em minibatches de tamanho fixo. Essa discrepância entre o algoritmo analisado (Poisson) e o algoritmo implantado (embaralhamento) deixou as garantias de privacidade de sistemas do mundo real caracterizadas de forma imprecisa. Trabalhos anteriores sobre DP-SGD embaralhado forneceram apenas limites superiores para a função de trade-off (limites inferiores para a perda de privacidade) por meio de eventos adversariais explícitos ou avaliações numéricas, carecendo de expressões fechadas e transparentes. Além disso, resultados recentes de impossibilidade indicam que, para multiplicadores de ruído baixos ($\sigma \le 1/\sqrt{2 \ln M}$), a função de trade-off é comprovadamente limitada a uma distância da diagonal ideal de adivinhação aleatória ($1-a$), mas o comportamento no regime de alto ruído permaneceu uma questão em aberto que exigia uma análise apertada e em forma fechada.

Metodologia

Os autores derivam uma análise apertada e em forma fechada da função de trade-off para DP-SGD com embaralhamento aleatório dentro do framework $f$-DP. A metodologia procede através das seguintes etapas:

1. Redução Adversarial: O problema é reduzido a um problema de teste de hipóteses escalar. Sob o modelo de adversário de pior caso (que pode isolar a contribuição de um único registro diferente), o adversário observa $M$ rodadas. Sob a hipótese nula ($H_0$), todas as observações são ruído puro $N(0, 1)$. Sob a hipótese alternativa ($H_1$), exatamente uma rodada (escolhida uniformemente ao acaso pela permutação de embaralhamento) contém uma observação deslocada $N(1/\sigma, 1)$, enquanto o restante permanece como ruído.
2. Teste de Razão de Verossimilhança: Pelo lema de Neyman-Pearson, o teste ótimo aplica um limiar à razão de verossimilhança, o que se reduz a aplicar um limiar à média amostral de variáveis lognormais $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$, onde $X_j \sim N(0, 1)$.
3. Análise Não-Assintótica (Berry-Esseen): Para uma única época, os autores aplicam o teorema de Berry-Esseen para limitar a taxa de convergência da média amostral dessas variáveis lognormais para uma distribuição normal. Isso produz um limite inferior concreto e não-assintótico para a função de trade-off $f(a)$ no regime $\sigma \ge \sqrt{3/\ln M}$. O limite é expresso como $f(a) \ge 1 - a - \delta$, onde $\delta$ é uma função explícita do multiplicador de ruído $\sigma$ e do número de rodadas $M$.
4. Análise Assintótica (Expansão de Edgeworth): Para melhorar os limites de Berry-Esseen, que são limitados por um termo de erro de $O(1/\sqrt{M})$, os autores introduzem uma técnica de prova baseada em uma expansão de Edgeworth de dois termos. Esta generalização do Teorema do Limite Central permite uma estimativa assintótica mais fina da distribuição da soma de variáveis lognormais. Essa abordagem estabelece o comportamento assintótico da função de trade-off quando $M \to \infty$, com o número de épocas $E$ escalando como $E = c_M^2 M$, onde $c_M \to 0$.

Contribuições Principais

1. Limite Inferior em Forma Fechada para Época Única: O artigo fornece o primeiro limite inferior apertado e em forma fechada para a função de trade-off de DP-SGD embaralhado no regime de alto ruído ($\sigma \ge \sqrt{3/\ln M}$). O limite é dado por:
   $$f(a) \ge 1 - a - \delta$$
   onde $\delta$ é explicitamente definido em termos de $\sigma$ e $M$ (Teorema 4.1). Este resultado é apertado até fatores constantes dentro do framework de prova de Berry-Esseen.
2. Recomendações Concretas de Parâmetros: Os autores derivam configurações específicas de parâmetros para privacidade diferencial significativa. Para uma única época ($E=1$) com $\sigma=1$ e $\delta=10^{-2}$, eles mostram que um tamanho de conjunto de dados de $N \approx 1,14 \times 10^7$ partitionado em $M \approx 1,14 \times 10^6$ rodadas é suficiente. Isso demonstra que privacidade significativa é alcançável em configurações de aprendizado federado com grandes conjuntos de dados e uma única época.
3. Caracterização Assintótica de DP-Gaussiana: Usando expansões de Edgeworth, o artigo estabelece que, para $\sigma$ fixo, à medida que $M \to \infty$ e $E = c_M^2 M$ com $c_M \to 0$, a função de trade-off composta $E$ vezes converge uniformemente para a diagonal de adivinhação aleatória ($1-a$). Isso melhora a dependência do número de épocas da penalidade linear $O(E)$ sugerida pela composição ingênua para uma separação assintótica $O(\sqrt{E})$ (Corolário 5.3).
4. Comparação com Subamostragem de Poisson: Os autores comparam seus resultados assintóticos com o assintótico correspondente da subamostragem de Poisson. Eles descobrem que, no limite de baixo ruído ($\sigma \to 0$), o embaralhamento aleatório é assintoticamente um fator de $\sqrt{2}$ mais próximo da diagonal ideal de adivinhação aleatória do que a subamostragem de Poisson, enquanto os dois regimes tornam-se equivalentes no limite de alto ruído ($\sigma \to \infty$).

Resultados

• Validade do Regime: A análise é válida para $\sigma \ge \sqrt{3/\ln M}$. Este regime é complementar ao resultado de impossibilidade de Ertan e van Dijk [12], que mostra que para $\sigma < 1/\sqrt{2 \ln M}$, a função de trade-off é limitada a uma distância de $1-a$. Juntos, esses resultados mapeiam o panorama de privacidade do DP-SGD embaralhado.
• Limites de Composição:
  • Não-Assintótico: A iteração do limite de época única produz $f^{\otimes E}(a) \ge (1-\delta)^E - a$, implicando uma dependência linear em $E$ para a perda de privacidade.
  • Assintótico: A análise baseada em Edgeworth sugere uma dependência mais apertada, onde a separação da diagonal escala como $O(\mu \sqrt{E})$ em vez de $O(\mu E)$, desde que $E$ escale sublinearmente com $M$.
• Implicações Práticas: O artigo identifica o regime de época única como o "ponto ideal prático" para DP-SGD embaralhado. Em cenários de aprendizado federado onde os clientes participam de poucas épocas, garantias de privacidade significativas ($\delta \approx 0,01$) são alcançáveis com tamanhos de conjunto de dados realistas. Por outro lado, o artigo destaca uma "explosão de múltiplas épocas" onde o aumento de $E$ sob o limite de composição linear torna rapidamente o tamanho de conjunto de dados necessário $N$ impraticável (por exemplo, exigindo $N \sim 10^{11}$ para $E=100$).

Significado e Alegações

O artigo alega fornecer uma análise apertada e em forma fechada que resolve a incompatibilidade entre os algoritmos analisados na literatura (Poisson) e aqueles implantados na prática (embaralhamento aleatório). Ao derivar limites transparentes e interpretáveis, os autores permitem que os praticantes leiam diretamente os requisitos de parâmetros sem depender de ferramentas numéricas opacas.

O significado do trabalho reside em:

1. Ponte entre Teoria e Prática: Validar que o embaralhamento aleatório, o padrão em frameworks de aprendizado de máquina, admite uma análise rigorosa de privacidade que é frequentemente mais favorável do que a subamostragem de Poisson em regimes de baixo ruído.
2. Definição do Panorama de Privacidade: Complementar resultados de impossibilidade existentes para definir os limiares de ruído precisos necessários para privacidade significativa no DP-SGD embaralhado.
3. Orientação para Seleção de Parâmetros: Oferecer fórmulas concretas para selecionar $M$, $N$ e $\sigma$ para atingir orçamentos de privacidade específicos, particularmente relevantes para aplicações de aprendizado federado.

Os autores permanecem modestos quanto ao trabalho futuro, observando que, embora os resultados assintóticos sugiram uma dependência aprimorada de $\sqrt{E}$ para múltiplas épocas, derivar uma prova concreta e em forma fechada dessa dependência (em oposição ao limite assintótico) permanece um problema em aberto. Adicionalmente, tornar as sequências $\delta_M$ e $\gamma_M$ na expansão de Edgeworth explícitas para obter um limite concreto de múltiplas épocas é identificado como uma direção para pesquisa futura.