Resumo Técnico: Verificação Pública Eficiente de Aprendizado de Máquina Privado via Regularização

Declaração do Problema

A Privacidade Diferencial (DP - Differential Privacy) é o padrão para proteger informações sensíveis em treinamentos de aprendizado de máquina, garantindo que os usuários do modelo não possam inferir pontos de dados específicos. No entanto, existe uma lacuna crítica: provedores de dados e o público carecem de métodos eficientes para verificar se um modelo lançado foi de fato treinado sob garantias de DP.

Os métodos de verificação atuais enfrentam duas limitações primárias:

1. Auditoria de Caixa-Preta (Black-box Auditing): Abordagens que consultam um treinador de modelo com diferentes conjuntos de dados são estatisticamente insuficientes. O artigo demonstra que, sob a suposição de assinaturas digitais, um treinador malicioso pode plantar uma "backdoor computacionalmente indetectável". Esta backdoor permanece dormente durante auditorias padrão, mas permite que o treinador vaze o conjunto de dados para entidades específicas, tornando o algoritmo não privado, apesar de passar em qualquer verificação de caixa-preta.
2. Custos de Verificação Interativa: As verificações de provas interativas existentes para DP (por exemplo, verificar DP-SGD) exigem que o verificador recompute quase todas as etapas de treinamento. Por exemplo, verificar DP no dataset MNIST anteriormente exigia aproximadamente 100 horas de computação, escalando com o custo de treinamento. Isso torna a verificação pública impraticável para grandes conjuntos de dados.

O artigo aborda o desafio de projetar um algoritmo de DP onde o custo de verificação seja estritamente inferior ao custo de treinamento, especificamente para Otimização Convexa Estocástica (DP-SCO).

Metodologia

1. Fundamentação Teórica: Backdoors Indetectáveis

Os autores primeiro formalizam a insuficiência da auditoria de caixa-preta. Eles constroem um algoritmo de treinamento com backdoor $T'$ que é computacionalmente indistinguível de um algoritmo DP legítimo $T$ para qualquer auditor de tempo polinomial.

• Mecanismo: O algoritmo incorpora uma etapa de verificação de assinatura digital nos dados de treinamento. Se uma entrada específica contiver uma assinatura válida (que apenas o treinador malicioso possui), o algoritmo retorna o conjunto de dados de treinamento bruto em vez do modelo.
• Implicação: Isso prova que, sem protocolos interativos, nenhum auditor público pode garantir a privacidade de um modelo, necessitando de uma mudança para a certificação interativa.

2. Algoritmo Central: ERM em Fases Modificado

Para alcançar uma verificação eficiente, os autores propõem uma modificação do algoritmo de Minimização de Risco Empírico (ERM) em Fases (Feldman et al., 2020).

• ERM em Fases Padrão: Resolve uma série de objetivos regularizados em subconjuntos disjuntos de dados, aumentando a força da regularização ao longo das fases. Baseia-se na composição paralela de orçamentos de privacidade para alcançar garantias estreitas. No entanto, verificar a composição paralela é caro porque o verificador deve confirmar que cada fase utilizou um subconjunto de dados específico e disjunto.
• A Modificação: Os autores alteram os critérios de parada dos minimizadores aproximados em cada fase.
  • Em vez de exigir que o excesso de perda seja pequeno, eles exigem que a norma do gradiente seja pequena ($\|\nabla F_i(\tilde{w}_i)\|_2 \leq \frac{2}{n_i} L$).
  • Eles ajustam o orçamento de privacidade $\delta$ para cada fase para $\delta / \lceil \log_2(n) \rceil$.
• Benefício Resultante: Esta modificação permite que o algoritmo derive trade-offs de privacidade-utilidade quase ótimos usando apenas a composição sequencial padrão em vez da composição paralela. A composição padrão é significativamente mais fácil de verificar porque não exige provar a disjunção dos subconjuntos de dados, apenas que o ruído foi adicionado corretamente e que as normas dos gradientes foram satisfeitas.

3. Protocolo de Verificação

O protocolo proposto (Algoritmo 2) envolve uma prova interativa entre um Provedor (treinador) e um Verificador (público):

1. Comprometimento (Commitment): O Provedor compromete o conjunto de dados e os pesos do modelo em cada fase.
2. Verificação de Gradiente: Usando Provas de Conhecimento Zero (ZKPs), o Verificador checa se a norma do gradiente do minimizador aproximado está abaixo do limite exigido.
3. Verificação de Ruído: O Verificador checa se o ruído Gaussiano foi adicionado aos pesos usando um esquema de compromisso Gaussiano discreto.
4. Complexidade: A verificação requer a checagem de $n$ gradientes (onde $n$ é o tamanho do conjunto de dados) e $d \cdot \lceil \log_2(n) \rceil$ compromissos de variáveis aleatórias Gaussianas (onde $d$ é a dimensão).

4. Extensão para Machine Unlearning

Os autores estendem estas técnicas para o Aprendizado de Máquina Aproximado (Machine Unlearning) para perdas fortemente convexas. Ao aproveitar a estabilidade de funções fortemente convexas, eles mostram que o unlearning pode ser certificado verificando gradientes no conjunto de dados de retenção ($D'$) em vez do conjunto completo, exigendo apenas $|D'|$ checagens de gradiente e $d$ compromissos de ruído.

Principais Resultados

Garantias Teóricas

• Trade-off Privacidade-Utilidade: O algoritmo modificado alcança um risco de população excedente de $\tilde{O}(L D (\frac{1}{\sqrt{n}} + \frac{\sqrt{d \ln(1/\delta)}}{\epsilon n}))$, que é quase ótimo (correspondendo aos limites inferiores conhecidos até fatores de $\log \log(n)$).
• Eficiência de Verificação: A certificação requer a verificação de apenas $n$ gradientes e $d \cdot \lceil \log(n) \rceil$ variáveis aleatórias Gaussianas.
  • Comparado aos algoritmos de treinamento mais rápidos conhecidos para DP-SCO, que exigem $\tilde{\Omega}(\min(n^{1.5}, n^2/\sqrt{d}))$ gradientes, o custo de verificação é significativamente menor (pelo menos uma melhoria de $O(\sqrt{n})$ em configurações não suaves).
  • Em configurações suaves, a redução nas checagens de variáveis aleatórias Gaussianas (de $\Omega(dn)$ para $d \log n$) fornece uma vantagem substancial de tempo de execução.

Avaliação Empírica

Os autores implementaram o protocolo usando o toolkit EMP para regressão logística binária no dataset MNIST ($n=60.000, d=784$).

• Comparação de Tempo de Execução:
  • Abordagem Anterior (verificação de DP-SGD): ~100 horas.
  • Abordagem Proposta: ~3 horas em uma CPU de laptop.
• Análise de Gargalo:
  • Verificação de Gradiente: Domina o tempo de execução. O número de gradientes a serem verificados foi reduzido em mais de 4 vezes em comparação com métodos anteriores.
  • Verificação de Ruído: O tempo para verificar variáveis aleatórias Gaussianas caiu drasticamente (de ser o custo dominante para tornar-se insignificante, levando menos tempo que uma única verificação de gradiente).
  • Comunicação: O overhead de rede (LAN/WAN) mostrou-se insignificante comparado à computação.
  • Treinamento: O tempo de treinamento foi desprezível (segundos) porque não requer criptografia homomórfica, ao contrário do processo de verificação.

Significância e Alegações

O artigo afirma apresentar o primeiro algoritmo de DP-SCO conhecido onde a verificação de DP escala melhor do que o custo de treinamento.

• Mudança de Paradigma: Ele move o campo da "auditoria de caixa-preta" (provadamente insuficiente contra adversários computacionalmente limitados) para a "verificação pública eficiente" via provas interativas.
• Praticidade: Ao reduzir o tempo de verificação de ~100 horas para ~3 horas em hardware padrão para dados de escala MNIST, o artigo argumenta que a certificação pública de ML privado está se tornando viável.
• Limitações: Os autores notam modestamente que a abordagem atual é limitada a configurações convexas e não se aplica diretamente a redes neurais profundas (embora possa se aplicar ao ajuste fino da última camada). Eles também reconhecem que para conjuntos de dados muito grandes, a escala linear com $n$ ainda pode ser impraticável, e trabalhos futuros são necessários para lidar com gradientes estocásticos de forma mais eficiente (ex: via suavização aleatória).

Em resumo, o artigo estabelece que, ao utilizar a regularização para estabilizar a otimização e modificar os critérios de verificação para focar em normas de gradiente em vez de excesso de perda, é possível construir algoritmos de DP que são tanto próximos do ótimo em utilidade quanto eficientemente verificáveis pelo público.