DP-MacAdam: Differentially Private Mechanism with Adaptive Clipping and Adaptive Momentum

Resumo Técnico: DP-MacAdam

Definição do Problema
O Gradiente Descendente Estocástico Diferencialmente Privado (DP-SGD) é o framework padrão para aprendizado de máquina com preservação de privacidade, mas sofre de uma limitação prática significativa: sua dependência de um limiar de clipping de gradiente ($C$) fixo. Na prática, selecionar $C$ é difícil; um valor muito pequeno descarta sinal através de um clipping excessivo, enquanto um valor muito grande aumenta a sensibilidade, necessitando da adição de mais ruído para satisfazer o orçamento de privacidade.

Abordagens existentes tentam endereçar isso de duas maneiras distintas e complementares, mas nenhuma aproveita totalmente as estatísticas disponíveis:

1. Clipping Adaptativo (ex: AdaClip): Utiliza estimativas empíricas da média e variância do gradiente para deslocar e escalar dinamicamente os gradientes antes do clipping. Isso reduz o ruído esperado adicionado por iteração, mas descarta essas estatísticas após o pré-processamento, revertendo para uma atualização de SGD padrão que ignora a informação adaptativa.
2. Momento Adaptativo (ex: DP-Adam): Utiliza médias móveis exponenciais (EMA) dos momentos do gradiente para computar taxas de aprendizado adaptativas por coordenada (semelhante ao Adam). No entanto, baseia-se em um clipping isotrópico fixo, renunciando aos benefícios de redução de ruído do clipping adaptativo.

O problema central abordado é a falta de um algoritmo que simultaneamente explore as mesmas estatísticas de gradiente tanto para clipping adaptativo quanto para atualizações de momento adaptativo sob garantias de privacidade diferencial (DP) sem incorrer em custos de privacidade adicionais.

Metodologia: DP-MacAdam
Os autores propõem o DP-MacAdam (Mecanismo Diferencialmente Privado com Clipping Adaptativo e Momento Adaptativo), um algoritmo que unifica o clipping adaptativo por coordenada do AdaClip com as atualizações de momento adaptativo do Adam.

• Estatísticas Unificadas: O algoritmo mantém estimativas contínuas da média do gradiente ($m_t$) e da variância ($s_t$) derivadas inteiramente de gradientes privatizados. Pela propriedade de pós-processamento de DP, essas estimativas satisfazem $(\epsilon, \delta)$-DP sem custo adicional.
• Clipping Adaptativo & Momento:
  • Os gradientes são centralizados e escalonados usando as estimativas atuais da média ($\hat{m}_{t-1}$) e um vetor de escala ($b_{t-1}$) antes do clipping.
  • Os gradientes transformados e privatizados são então usados para atualizar tanto os termos de momento (primeiro e segundo momentos) para a atualização de parâmetros quanto a estimativa de variância para a próxima iteração de escala.
• Estimativa de Variância com Correção de Viés: Uma contribuição técnica crítica é a derivação de um novo fator de correção de viés, $\kappa_t = 2(\beta_1 - \beta_1^t)/(1 + \beta_1)$.
  • A EMA padrão introduz viés de inicialização.
  • No cenário de DP, a estimativa de variância é adicionalmente enviesada pela inflação de ruído adicionada durante o processo de clipping.
  • Os autores derivam $\kappa_t$ para obter uma estimativa não enviesada da verdadeira variância do gradiente a partir da EMA de estimativas de variância instantânea corrigidas de ruído, contabilizando tanto o viés de inicialização da EMA quanto a estrutura de correlação introduzida pela média ponderada.
• Escalonamento de Ruído: O algoritmo realiza o clipping dos gradientes transformados para uma norma $\ell_2$ unitária. O ruído é adicionado à média do lote de gradientes clipados em vez de gradientes individuais, escalonando a variância do ruído por $1/B^2$. O algoritmo subtrai o termo de variância de ruído conhecido da estimativa de variância para recuperar a variância do gradiente sem ruído.

Principais Contribuições

1. Design de Algoritmo: O DP-MacAdam é o primeiro algoritmo a combinar o clipping adaptativo por coordenada do estilo AdaClip com o momento adaptativo do estilo Adam sob garantias de DP.
2. Derivação Teórica: Os autores derivam um fator de correção de viés específico ($\kappa_t$) que permite a estimativa não enviesada da variância do gradiente a partir da EMA de estimativas corrigidas de ruído, abordando tanto a inflação de ruído de DP quanto o viés de inicialização da EMA.
3. Desempenho Empírico: O algoritmo alcança utilidade de modelo melhorada em comparação com as principais linhas de base (DP-SGD, AdaClip, DP-Adam e DP-AdamBC) em vários orçamentos de privacidade no MNIST e CIFAR-10. Crucialmente, ele alcança isso sem exigir ajuste manual do limiar de clipping ou pré-processamento de redução de dimensionalidade.

Resultos Experimentais
Os autores avaliaram o DP-MacAdam no MNIST (rede totalmente conectada) e CIFAR-10 (CNN de 5 camadas) contra DP-SGD, AdaClip, DP-Adam e DP-AdamBC.

• MNIST: O DP-MacAdam superou consistentemente todas as linhas de base em multiplicadores de ruído ($\sigma$) variando de 0,5 a 1,0, atingindo até 93,2% de acurácia (vs. 92,8% para DP-Adam e 90,0% para DP-SGD em $\sigma=0,5$).
• CIFAR-10: O DP-MacAdam alcançou a maior acurácia na maioria dos orçamentos de privacidade, atingindo 59,96% em $\sigma=0,5$ (vs. 58,90% para DP-Adam).
• Observações: Os autores observam que, embora o DP-MacAdam-BC (uma variante incorporando correção de viés do segundo momento para o Adam) tenha mostrado ganhos no MNIST, ele teve desempenho inferior no CIFAR-10. Eles hipotetizam que a correção de viés do segundo momento gera maiores ganhos em tarefas onde o Adam supera o SGD no cenário não privado.
• Eficiência: Ao contrário do AdaClip, o DP-MacAdam opera diretamente nos dados brutos sem gastar orçamento de privacidade em redução de dimensionalidade (ex: PCA).

Significância e Alegações
O artigo afirma que o DP-MacAdam representa um passo significativo ao demonstrar que as estatísticas usadas para o clipping adaptativo podem ser efetivamente reutilizadas para impulsionar as atualizações de momento adaptativo, melhorando assim a utilidade do modelo sem comprometer a privacidade. Os autores enfatizam que sua abordagem remove a necessidade de ajuste manual do limiar de clipping, um grande obstáculo prático na implementação do DP-SGD.

Os autores mantêm a modéstia quanto ao escopo de seu trabalho, observando que:

• A escolha ótima do vetor de escala $b_t$ sob sua estimativa de variância baseada em EMA é deixada para trabalhos futuros.
• Uma análise de convergência formal do DP-MacAdam não é fornecida neste trabalho.
• A avaliação empírica é atualmente limitada a tarefas de classificação de imagem (MNIST, CIFAR-10), com trabalhos futuros sugeridos para tarefas mais complexas como PLN e conjuntos de dados maiores.