Resumo Técnico: Aprendizado Modulado para Regressão Privada e Distribuída com Uma Amostra por Cliente

Declaração do Problema

Este trabalho aborda uma limitação crítica nos paradigmas padrão de Aprendizado Federado (FL) e Aprendizado com Privacidade Diferencial (DP): a suposição de que os dispositivos dos clientes possuem conjuntos de dados locais grandes o suficiente para calcular atualizações de gradiente significativas. Em muitos cenários do mundo real — como rastreadores de fitness, sensores vestíveis e monitores de eventos diários — os clientes podem deter apenas uma única amostra de dados (ou muito poucas).

Neste regime de "uma amostra por cliente", o FL baseado em DP-SGD padrão falha porque:

1. Atualizações Locais Não Confiáveis: Um gradiente local calculado em um único ponto é altamente ruidoso e não confiável para estimar coeficientes do modelo, particularmente nos primeiros rounds de treinamento.
2. Amplificação de Ruído de Privacidade: O ruído injetado para satisfazer a privacidade diferencial degrada ainda mais a utilidade dessas atualizações locais já fracas, tornando a convergência do modelo global ineficaz.

O artigo pergunta: Podemos habilitar aprendizado distribuído útil e com privacidade diferencial quando cada cliente contribui apenas um ponto de dados de exemplo?

Metodologia

Os autores propõem um framework de Aprendizado Modulado. Em vez de os clientes enviarem coeficientes do modelo (como no FL padrão) ou gradientes brutos, os clientes transmitem uma representação transformada privadamente de sua única amostra de dados. O servidor então agrega essas representações para recuperar uma estimativa não enviesada do gradiente centralizado.

Mecanismo Central: Transformação Modulada por Cosseno

O protocolo opera em rounds. Em cada round $t$, o servidor mantém um modelo global $\beta_t$ e seleciona uma direção de modulação $v_t$ (ortogonal a $\beta_t$).

1. Processamento no Lado do Cliente:
Dada uma amostra privada $(x_i, y_i)$, o cliente executa as seguintes etapas:

• Modulação: O cliente amostra uma fase aleatória $\phi_i \sim \text{Unif}[0, 2\pi]$ e calcula um vetor de características modulado:
  $$g_i = (1 - \alpha)x_i + \lambda \cos(\omega \langle x_i, v_t \rangle + \phi_i) v_t$$
  Aqui, $\alpha, \lambda, \omega$ são hiperparâmetros. O termo $(1-\alpha)x_i$ preserva o sinal, enquanto o termo cosseno introduz uma perturbação contrativa e que preserva a privacidade.
• Injeção de Ruído: Para garantir privacidade diferencial local (LDP) $(\epsilon, \delta)$, o cliente adiciona ruído gaussiano $\xi_i \sim \mathcal{N}(0, \sigma_{DP}^2 I)$:
  $$\tilde{g}_i = g_i + \xi_i$$
• Transmissão: O cliente envia o par $(\tilde{g}_i, y_i)$ ao servidor. Note que $y_i$ é tratado como público/não sensível nesta configuração específica, enquanto $x_i$ é a entrada privada.

2. Agregação e Desenviesamento no Lado do Servidor:
O servidor recebe $\{(\tilde{g}_i, y_i)\}_{i=1}^K$ e realiza correções algébricas para remover o viés introduzido pela modulação e pelo ruído:

• Estimação de Covariância: O servidor calcula a covariância empírica das características recebidas e subtrai os termos de viés conhecidos (a variância da modulação e a variância do ruído):
  $$\hat{\Sigma}_x = \frac{1}{(1-\alpha)^2} \left( \frac{1}{K}\sum \tilde{g}_i \tilde{g}_i^\top - \frac{\lambda^2}{2} v_t v_t^\top - \sigma_{DP}^2 I \right)$$
  O Teorema 3.1 e o Corolário 3.2 provam que $\hat{\Sigma}_x$ é um estimador não enviesado da verdadeira covariância dos dados $\Sigma_x = \frac{1}{K}\sum x_i x_i^\top$.
• Recuperação do Gradiente: O servidor constrói um estimador de gradiente não enviesado $G$:
  $$G = \hat{\Sigma}_x \beta_t - \frac{1}{1-\alpha} \frac{1}{K} \sum y_i \tilde{g}_i$$
  Este $G$ satisfaz $\mathbb{E}[G] = \nabla L(\beta_t)$, correspondendo ao gradiente centralizado não privado em expectativa.

Variantes

• Modulação Multi-Vetor: Para reduzir a constante de Lipschitz (e, portanto, o ruído necessário $\sigma_{DP}$), os autores generalizam o método para usar $m$ vetores ortonormais. Isso reduz o limite de sensibilidade de $|1-\alpha| + \lambda\omega$ para $|1-\alpha| + \frac{\lambda\omega}{\sqrt{m}}$.
• Estimador Não Iterativo (One-Shot): O artigo também deriva um estimador de momentos de forma fechada que resolve para $\beta$ em um único passo, evitando os custos de composição de privacidade dos métodos iterativos.

Principais Contribuições

1. Estimação de Gradiente Não Enviesada a partir de Amostras Únicas: O artigo demonstra que, ao transformar dados por meio de um mapa específico modulado por cosseno e aplicar desviamento pós-processamento, um servidor pode recuperar uma estimativa de gradiente não enviesada mesmo quando os clientes detêm apenas uma amostra cada.
2. Otimização do Trade-off Privacidade-Utilidade:
   • O método estabelece um limite inferior de Cramér-Rao sobre o erro de reconstrução, provando que os parâmetros de modulação ($\lambda, \omega$) aumentam ativamente a dificuldade de reconstruir a entrada privada $x_i$ além da proteção oferecida pelo ruído gaussiano sozinho.
   • A variante multi-vetor mostra-se capaz de reduzir a variância de ruído necessária por um fator relacionado a $\sqrt{m}$, melhorando a utilidade para um orçamento de privacidade fixo.
3. Garantias Teóricas:
   • Não Enviesamento: Prova rigorosa de que o estimador do servidor é não enviesado.
   • Convergência: O artigo estabelece a normalidade assintótica do estimador e deriva limites de variância, mostrando taxas de convergência para o descenso de gradiente estocástico projetado.
   • Contabilidade de Privacidade: O método utiliza contabilidade de privacidade diferencial concentrada zero (zCDP), que oferece limites de composição mais apertados do que o DP padrão $(\epsilon, \delta)$ para rounds sequenciais.
4. Limites Inferiores de Reconstrução: Os autores derivam um limite inferior teórico sobre o erro quadrático médio de qualquer atacante não enviesado tentando reconstruir $x_i$ a partir da mensagem transmitida, quantificando a proteção de privacidade diretamente em termos dos parâmetros do protocolo.

Resultados Experimentais

Os autores avaliaram a abordagem em cinco conjuntos de dados de regressão do mundo real (por exemplo, emissões de CO2, Equidade na duração do casamento, Escolha de Modo) onde cada exemplo de treinamento foi tratado como um cliente separado.

• Comparação: Os estimadores Modulado Iterativo e Modulado One-Shot propostos foram comparados contra uma linha de base DP-SGD FedAvg ajustada.
• Descobertas:
  • Alta Privacidade (Baixo $\epsilon$): O estimador Modulado One-Shot superou os métodos iterativos. Como depende de uma única liberação privada, evita a perda cumulativa de privacidade (composição) inerente ao DP-SGD iterativo, tornando-se mais robusto quando o orçamento de privacidade é extremamente restrito.
  • Privacidade Moderada/Baixa (Alto $\epsilon$): O estimador Modulado Iterativo melhorou consistentemente com mais rounds e eventualmente superou o método one-shot e a linha de base DP-SGD na maioria das tarefas.
  • Desempenho da Linha de Base: O DP-SGD lutou significativamente neste regime porque o ruído necessário para proteger uma única amostra por round, composto ao longo de múltiplos rounds, sobrecarregou o sinal.

Significado e Alegações

O artigo alega resolver um regime específico onde o aprendizado federado padrão é inaplicável: aprendizado a partir de dispositivos com dados extremamente limitados (uma amostra) sob restrições estritas de privacidade.

• Mudança de Paradigma: Diferentemente do FL privado tradicional que compartilha atualizações de modelo (gradientes/pesos), esta abordagem compartilha representações de dados privatizadas. Essa mudança permite que o servidor realize correções estatísticas globais que são impossíveis quando os clientes enviam apenas gradientes locais ruidosos.
• Praticidade: O método habilita dispositivos com dados mínimos a aprender colaborativamente modelos de regressão precisos sem sacrificar a privacidade individual ou exigir grandes conjuntos de dados locais.
• Rigor Teórico: O trabalho fornece um framework teórico completo, incluindo provas de não enviesamento, análise de variância, garantias de convergência e limites inferiores de reconstrução, estabelecendo que o método não é apenas heurístico, mas estatisticamente sólido.

Os autores concluem que esta abordagem torna viável a implantação de aprendizado de máquina com preservação de privacidade em cenários anteriormente considerados impossíveis devido à escassez de dados e aos requisitos de privacidade.