🤖 machine learning

Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States

Este artigo apresenta o primeiro limite convergente de privacidade diferencial para otimização de ordem zero, introduzindo um mecanismo de ruído híbrido e uma nova análise de acoplamento que supera as limitações dos frameworks padrão de divergência deslocada causadas por atualizações anisotrópicas.

Autores originais: Eli Chien, Wei-Ning Chen, Pan Li

Publicado 2026-05-04

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Eli Chien, Wei-Ning Chen, Pan Li

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

A Visão Geral: Escondendo o Rastro Enquanto Resolve um Quebra-Cabeça Gigante

Imagine que você tem um quebra-cabeça massivo e complexo (um modelo de IA enorme) que precisa ser resolvido. Você deseja resolvê-lo usando um método específico chamado Otimização de Ordem Zero.

O Problema:
Geralmente, para resolver um quebra-cabeça, você olha para as peças e descobre exatamente para onde movê-las (gradientes). Mas na "Otimização de Ordem Zero", você não tem permissão para olhar diretamente para as peças. Em vez disso, você precisa adivinhar um movimento, ver como a imagem fica, adivinhar um movimento diferente, ver como essa fica e, em seguida, calcular a média dessas suposições para descobrir a melhor direção. É como tentar encontrar a saída de um labirinto escuro batendo nas paredes e ouvindo os ecos, em vez de ver o mapa.

O Desafio de Privacidade:
Você quer resolver esse quebra-cabeça usando dados de muitas pessoas, mas deve proteger a privacidade delas (Privacidade Diferencial). Para fazer isso, você geralmente adiciona "ruído" (estática) às suas suposições para que ninguém possa dizer se os dados de uma pessoa específica foram usados.

O Jeito Antigo (A Armadilha da "Composição"):
Métodos anteriores tratavam cada etapa individual do processo de resolução do quebra-cabeça como um evento separado. Eles pensavam: "Se eu adicionar ruído ao passo 1, passo 2, passo 3... e assim por diante, o custo total de privacidade se acumula como uma conta". Se você der 1.000 passos, o custo de privacidade torna-se enorme, e você eventualmente precisa parar porque "gastou" todo o seu orçamento de privacidade. É como pagar uma pedágio a cada milha que você dirige; eventualmente, você não pode mais pagar para terminar a viagem.

A Descoberta do Artigo:
Este artigo diz: "Espere um minuto! Não precisamos pagar uma pedágio a cada passo se mantivermos os passos intermediários ocultos".

Eles introduzem um conceito chamado Amplificação de Privacidade por Iteração (PABI). Pense nisso assim:

O Jeito Antigo: Você diz a todos a sua localização a cada 10 pés. Eles podem traçar seu caminho exato.
O Novo Jeito: Você só diz a todos onde começou e onde terminou. Você mantém o caminho no meio em segredo. Como o caminho está oculto, o "ruído" que você adicionou no início realmente faz um trabalho muito melhor protegendo sua identidade quando você chega ao fim. O custo de privacidade para de crescer e, na verdade, estabiliza.

Os Obstáculos Específicos Que Eles Superaram

Os autores enfrentaram dois problemas principais ao tentar aplicar essa ideia de "caminho oculto" aos métodos de Ordem Zero:

1. O Problema do Ruído "Anisotrópico" (A Estática Unidirecional)
Nos métodos padrão, você adiciona ruído em todas as direções (como estática em uma tela de TV em todos os lugares). Na Ordem Zero, você só adiciona ruído ao longo da direção específica que você adivinhou (como estática em apenas uma linha).

O Problema: As ferramentas matemáticas usadas para provar a privacidade para o ruído de "todas as direções" não funcionam para o ruído de "uma direção". É como tentar usar uma estaca quadrada em um buraco redondo. A matemática padrão diz: "Isso não funciona porque o ruído não é uniforme".

2. A Barreira "Lipschitz" (A Encosta Escorregadia)
Para provar a privacidade, os matemáticos geralmente precisam provar que o sistema é "estável" — ou seja, uma pequena mudança na entrada leva a uma pequena e previsível mudança na saída.

O Problema: Na Ordem Zero, como as direções são aleatórias, o sistema não é perfeitamente estável o tempo todo. É estável apenas na maioria das vezes. As antigas ferramentas matemáticas exigem que seja estável sempre, então elas falharam.

A Solução: Um Motor Híbrido e um Processo "Fantasma"

Os autores construíram um novo motor para resolver esses problemas:

1. O Mecanismo de Ruído Híbrido
Em vez de escolher entre "ruído em todos os lugares" ou "ruído em uma direção", eles criaram uma mistura.

Eles adicionam ruído ao longo da direção específica que estão adivinhando (para manter a resolução do quebra-cabeça eficiente).
Eles também adicionam um pouquinho de ruído em todas as outras direções (apenas o suficiente para satisfazer os requisitos matemáticos).
O Resultado: Isso lhes dá o melhor dos dois mundos: bom desempenho na resolução do quebra-cabeça e uma estrutura matemática que permite provas de privacidade.

2. O Processo "Fantasma" (O Truque de Acoplamento)
Como não podiam usar as antigas ferramentas matemáticas, eles inventaram um novo truque.

Imagine duas pessoas, Alice e Bob, tentando resolver o quebra-cabeça com dados ligeiramente diferentes.
Os autores criaram uma versão "Fantasma" do processo que fica exatamente no meio entre Alice e Bob.
Eles provaram que Alice e o Fantasma estão muito próximos, e Bob e o Fantasma estão muito próximos.
Ao usar esse "Fantasma" como uma ponte, eles puderam provar que Alice e Bob também estão próximos o suficiente para serem considerados privados, mesmo sem as antigas ferramentas matemáticas.

A Descoberta Surpreendente: Mais Direções = Melhor Privacidade

Uma das descobertas mais legais no artigo é sobre $K$ , o número de direções que você adivinha de uma vez.

Crença Antiga: Usar mais direções ( $K > 1$ ) torna o quebra-cabeça mais fácil de resolver (melhor utilidade), mas custa mais privacidade.
Nova Descoberta: Sob essa nova análise de "caminho oculto", usar mais direções na verdade melhora a privacidade enquanto mantém a qualidade da resolução do quebra-cabeça alta.
A Analogia: Imagine tentar encontrar uma agulha em um palheiro. Se você olhar apenas para um ponto, precisa de muita "cobertura" (ruído) para esconder o que está fazendo. Se você olhar para 10 pontos de uma vez, a "cobertura" se espalha de forma mais eficaz, tornando mais difícil para um observador descobrir em qual ponto específico você estava olhando.

Resumo do Que Eles Afirmam

Eles criaram a primeira prova matemática de que a otimização de Ordem Zero pode ter um custo de privacidade convergente. Isso significa que o custo de privacidade para de crescer após um certo número de passos, em vez de crescer para sempre.
Eles provaram que, ao esconder os passos intermediários da otimização, você obtém garantias de privacidade muito mais fortes do que se pensava possível anteriormente.
Eles mostraram que usar múltiplas direções aleatórias de uma vez (direções ortonormais) não é apenas bom para velocidade, mas na verdade uma arma secreta para privacidade.
Eles forneceram uma nova receita de "Ruído Híbrido" que torna isso possível.

O Que Eles NÃO Afirmam:

Eles não afirmam que isso funciona para todo tipo de modelo de IA ou conjunto de dados imediatamente; sua matemática depende de suposições específicas (como a função de perda ser "suave" e "côncava").
Eles não afirmam que isso resolve todos os problemas de privacidade em IA, apenas que fornece um limite teórico melhor para este tipo específico de método de otimização.
Eles não fornecem uma ferramenta de software pronta para uso ao público ainda; este é um quadro teórico que abre caminho para futuras ferramentas.

1. Declaração do Problema

O artigo aborda o desafio de treinar modelos em grande escala (por exemplo, LLMs) sob restrições de Privacidade Diferencial (DP), ao mesmo tempo em que gerencia limitações estritas de memória.

Contexto: Métodos DP de primeira ordem padrão (como DP-SGD) exigem o armazenamento de gradientes por amostra durante a retropropagação, levando a uma sobrecarga massiva de memória que escala mal com o tamanho do modelo.
Tendência de Solução: Métodos de otimização de ordem zero (ZO) emergiram como uma alternativa eficiente em termos de memória, pois exigem apenas passagens forward (avaliações de perda) e não calculam gradientes explícitos.
A Lacuna: Embora os métodos ZO existentes (por exemplo, DPZero) funcionem bem empiricamente, sua análise teórica de privacidade depende de teoremas de composição padrão. Isso resulta em custos de privacidade que crescem linearmente com o número de etapas de treinamento ( $T$ ), forçando um compromisso entre utilidade e privacidade.
O Desafio Central: Estender a Amplificação de Privacidade por Iteração (PABI) — uma técnica que produz limites de privacidade convergentes (constantes) para métodos de primeira ordem — para métodos de ordem zero.
- Por que é difícil: A PABI de primeira ordem depende da adição de ruído Gaussiano isotrópico (independente da direção) aos gradientes, permitindo o uso de lemas de "divergência de Rényi deslocada". Em contraste, métodos ZO eficientes adicionam ruído escalar anisotrópico (dependente da direção) ao longo de direções de atualização aleatórias. Essa anisotropia quebra a propriedade de Lipschitz global exigida pelos quadros padrão de divergência deslocada, tornando as ferramentas PABI existentes inaplicáveis.

2. Metodologia

Os autores propõem um novo quadro que combina um Mecanismo de Ruído Híbrido e uma Análise de Acoplamento para contornar as limitações da análise padrão.

A. Mecanismo de Ruído Híbrido (Noisy-ZOGD)

Em vez de escolher ruído puramente direcional (eficiente, mas difícil de analisar) ou ruído puramente isotrópico (fácil de analisar, mas desperdiçador de utilidade), os autores propõem uma regra de atualização unificada:
$w_{t+1} = \Pi_{\mathcal{B}_R} \left[ w_t - \frac{\eta}{K} \sum_{k=1}^K \hat{g}_t(w_t; u_{t,k}) + \frac{\eta}{\sqrt{K}} \sum_{k=1}^K G^{(1)}_{t,k} u_{t,k} + \eta \sqrt{d} G^{(2)}_t \right]$

Atualizações de dimensão $K$ : Utiliza $K$ direções aleatórias por etapa para reduzir a variância da estimativa do gradiente.
Ruído Híbrido:
1. Ruído Direcional ( $G^{(1)}$ ): Ruído Gaussiano escalar adicionado ao longo das direções de atualização $u_{t,k}$ . Isso preserva a utilidade ao concentrar o ruído onde existe sensibilidade.
2. Ruído Isotrópico ( $G^{(2)}$ ): Pequeno ruído Gaussiano isotrópico adicionado em todas as dimensões. Isso é crucial para a análise teórica lidar com o "deslocamento" no processo de acoplamento.
Direções Ortonormais: As direções de atualização $\{u_{t,k}\}$ são amostradas como um conjunto ortonormal da variedade de Stiefel (em vez de vetores aleatórios i.i.d.), o que aperta os limites de privacidade.

B. Nova Análise de Acoplamento (Contornando a Divergência Deslocada)

A prova padrão de PABI depende do lema da Divergência de Rényi Deslocada, que exige uma condição de Lipschitz global. Como o mapa de atualização ZO não é globalmente Lipschitz (apenas Lipschitz pontual com alta probabilidade), os autores constroem um processo auxiliar acoplado $\tilde{W}_t$ :

Construção: Eles definem uma trajetória auxiliar $\tilde{W}_t$ que fica "no meio" de dois processos de treinamento adjacentes ( $W_t$ no conjunto de dados $D$ e $W'_t$ no conjunto de dados $D'$ ).
Decomposição: A análise de privacidade é dividida em duas partes:
- Limite de Variação Total (TV): Mede a probabilidade de o acoplamento falhar (ou seja, $W_t$ e $\tilde{W}_t$ divergirem). Isso é limitado usando a propriedade de Lipschitz pontual da atualização ZO (que se mantém com alta probabilidade).
- Limite de Divergência de Rényi: Mede a divergência entre o processo auxiliar $\tilde{W}_t$ e o processo adjacente $W'_t$ . Como $\tilde{W}_t$ é construído para alinhar com a estrutura do ruído, esta parte pode ser analisada usando mecanismos Gaussianos deslocados padrão.
Resultado: Esta abordagem evita a necessidade de uma constante de Lipschitz global, permitindo um limite de privacidade convergente mesmo com ruído anisotrópico.

3. Principais Contribuições

Primeira PABI Convergente para Ordem Zero: O artigo fornece a primeira prova teórica de que a otimização de ordem zero com estados ocultos atinge um limite de privacidade convergente (o custo de privacidade satura após um número fixo de etapas) em vez de crescer linearmente com $T$ .
Mecanismo de Ruído Híbrido: Introduz um esquema de injeção de ruído que equilibra utilidade (via ruído direcional) e tratabilidade analítica (via um pequeno componente isotrópico).
Papel da Dimensão de Atualização ( $K$ ):
- Revela que, sob análise de estado oculto, aumentar o número de direções de atualização $K$ reduz a perda de privacidade (contrário à análise de composição padrão onde $K$ aumenta o custo).
- Demonstra que o uso de direções de atualização ortonormais melhora significativamente os limites de privacidade em comparação com direções aleatórias i.i.d.
Nova Técnica de Acoplamento: Desenvolve uma construção específica de processo auxiliar que contorna a barreira de Lipschitz global, uma técnica potencialmente aplicável a outros cenários de otimização não suave ou não Lipschitz.

4. Resultados Principais

Limite de Privacidade: Para perdas suaves e fortemente convexas, o algoritmo Noisy-ZOGD proposto satisfaz $(\epsilon, \delta)$ $(ϵ, δ)$ -DP com:
$\epsilon = O\left( \sqrt{\frac{\Delta^2 \log(1/\delta)}{n^2 \sigma^2} \min\left(T, \frac{R n \sqrt{d}}{K \Delta}\right)} \right)$
- O limite satura em $T \approx \frac{R n \sqrt{d}}{K \Delta}$ , significando que iterações adicionais não aumentam o custo de privacidade.
- O limite é inversamente proporcional a $K$ , mostrando que o uso de mais direções melhora a privacidade.
Comparação:
- vs. Composição Padrão: A análise padrão produz $\epsilon \propto \sqrt{T}$ , que cresce ilimitadamente. O método proposto converge.
- vs. Perturbação de Saída: Embora a perturbação de saída (adicionar ruído apenas no final) seja independente de $T$ , ela é geralmente mais fraca para $T$ práticos. O método proposto oferece um limite mais apertado para $T$ intermediários.
Utilidade: O mecanismo de ruído híbrido mantém as mesmas garantias de utilidade que o ruído puramente direcional (DPZero), pois a variância total do ruído é preservada.

5. Significado

Escalabilidade: Este trabalho permite a justificação teórica do treinamento de modelos massivos (bilhões de parâmetros) com DP e memória limitada, um gargalo crítico no ajuste fino atual de LLMs.
Design Algorítmico: Inverte a crença de que o uso de múltiplas direções de ordem zero ( $K > 1$ ) é puramente um compromisso de utilidade. O artigo prova que é também um benefício de privacidade, incentivando o uso de atualizações de dimensão mais alta em algoritmos DP-ZO.
Avanço Teórico: Ao resolver o problema do "ruído anisotrópico" na PABI, o artigo preenche uma lacuna significativa entre a teoria de privacidade de primeira ordem e de ordem zero, oferecendo um novo conjunto de ferramentas (acoplamento com processos auxiliares) para analisar dinâmicas de otimização complexas e não Lipschitz sob restrições de privacidade.
Impacto Prático: Fornece diretrizes concretas para praticantes: use direções ortonormais, ajuste o parâmetro de ruído híbrido $\beta_t$ e aproveite $K$ maior para alcançar melhores compromissos privacidade-utilidade sem aumentar os custos de memória.