Certifying the Right to Be Forgotten: Primal-Dual Optimization for Sample and Label Unlearning in Vertical Federated Learning

O artigo propõe o FedORA, um algoritmo de otimização primal-dual que certifica o direito ao esquecimento em Aprendizado Federado Vertical, permitindo a remoção eficiente de amostras ou rótulos específicos com garantias teóricas e menor custo computacional em comparação ao retreinamento completo.

O essencial

Imagine que você tem um time de especialistas trabalhando juntos para criar um "cérebro" artificial (uma Inteligência Artificial), mas ninguém pode mostrar os dados dos seus clientes uns aos outros por questões de privacidade. Isso é o Aprendizado Federado Vertical.

Agora, imagine que um cliente diz: "Quero que a IA esqueça completamente que eu existo". Isso é o "Direito ao Esquecimento".

O problema é: como fazer a IA esquecer uma pessoa específica ou um tipo de dado sem ter que apagar tudo e começar do zero (o que seria caríssimo e demorado)? E pior: como fazer isso quando os dados estão divididos entre várias empresas?

Os autores deste artigo criaram uma solução chamada FedORA. Vamos explicar como ela funciona usando analogias simples:

1. O Problema: O "Esquecimento" Difícil

Antes do FedORA, tentar fazer uma IA esquecer algo era como tentar apagar uma mancha de tinta de uma parede pintada de branco.

• O jeito antigo (Subir a Escada): Era como tentar apagar a mancha esfregando a parede com força na direção errada (chamado de "gradiente ascendente"). Isso muitas vezes fazia a IA esquecer demais, confundindo-se e esquecendo coisas que ela deveria lembrar, ou não esquecendo nada de verdade.
• O jeito "Recomeçar do Zero": Era como demolir a casa inteira e construir de novo apenas com os tijolos que sobraram. Funciona, mas é lento e caro.

2. A Solução: O FedORA (O "Detetive da Otimização")

O FedORA é como um detetive muito inteligente que usa um sistema de "pressão e equilíbrio" para apagar a mancha sem estragar a parede.

A. A Analogia do "Balde de Pressão" (Otimização Primal-Dual)

Imagine que o modelo da IA é um balde de água.

• A Água Limpa (Dados que queremos manter): Queremos que o balde continue cheio e limpo com os dados dos clientes que não pediram para ser esquecidos.
• A Água Suja (Dados para esquecer): Temos uma mancha de tinta (os dados do cliente que pediu o esquecimento) dentro do balde.

O FedORA não tenta apenas jogar a tinta fora. Ele usa um sistema de dois lados:

1. Lado Primal (O Guardião): Foca em manter a água limpa e o balde estável. Ele garante que a IA continue funcionando bem para os outros.
2. Lado Dual (O Fiscal): É como um fiscal que segura uma corda. Se a IA ainda "lembra" da tinta (se a mancha não sumiu), o fiscal puxa a corda com mais força para forçar a IA a esquecer. Se a mancha sumiu, o fiscal relaxa a corda.

Esse equilíbrio garante que a IA esqueça o que precisa, mas não perca a memória do resto.

B. A "Confusão Saudável" (Função de Perda)

Aqui está a parte mais criativa.

• O jeito errado: Tentar fazer a IA errar a resposta do cliente que pediu para ser esquecido (ex: dizer que a foto de um gato é um cachorro). Isso é perigoso, pois a IA pode começar a achar que tudo é cachorro.
• O jeito do FedORA: O FedORA diz: "Não importa se você erra ou acerta. O importante é que você fique confuso".
  • Imagine que a IA é um professor. Quando um aluno pede para ser esquecido, o professor não diz "você é burro". Ele diz: "Eu não tenho certeza de quem você é. Você pode ser um gato, um cachorro, um pássaro ou um peixe. Eu não sei mais".
  • Ao forçar a IA a ficar incerta (como se tivesse 50% de chance de ser tudo), o FedORA apaga a memória específica daquele dado sem bagunçar o resto da aula.

C. O "Trabalho Inteligente" (Lotes Assimétricos)

Para fazer isso rápido, o FedORA é esperto com o esforço:

• Para o que vai ser esquecido: Ele olha tudo de uma vez (o lote completo), para ter certeza de que apagou tudo.
• Para o que vai ficar: Ele não precisa olhar todos os dados de novo. Ele olha apenas uma pequena amostra (como provar um pedaço de bolo para ver se está bom, sem comer o bolo todo).
  Isso economiza muita energia e tempo, como se você limpasse a sala inteira, mas só passasse o aspirador rápido nos lugares que já estavam limpos.

Por que isso é importante?

1. Privacidade Real: Garante que, se você pedir para ser esquecido, a IA realmente não sabe mais nada sobre você (nem mesmo que você fez parte do treinamento).
2. Economia: Não precisa reconstruir o cérebro da IA do zero. É rápido e barato.
3. Segurança: O FedORA prova matematicamente que o resultado é tão bom quanto começar do zero, mas sem o trabalho duro.

Resumo final:
O FedORA é como um mágico da memória. Em vez de rasgar a página do livro onde está escrito o nome de alguém (o que estragaria o livro), ele usa um truque de ilusão para fazer o nome desaparecer e deixar a página em branco, sem estragar o resto da história. E ele faz isso rápido, sem gastar a mágica inteira.

Resumo técnico

Resumo Técnico: FedORA para Desaprendizado em Aprendizado Federado Vertical

1. O Problema

O Aprendizado Federado (FL) permite o treinamento colaborativo de modelos sem compartilhamento direto de dados, mas os modelos de IA podem "memorizar" informações sensíveis durante o processo, violando regulamentações como o GDPR que garantem o "Direito ao Esquecimento". Isso exige a remoção da influência de dados específicos (amostras) ou classes inteiras (rótulos) dos modelos treinados, sem a necessidade de um retreinamento completo (Retrain), que é computacionalmente proibitivo.

O foco deste trabalho é o Aprendizado Federado Vertical (VFL), onde diferentes partes possuem características complementares dos mesmos usuários. O desaprendizado no VFL é particularmente desafiador devido à:

• Arquitetura Distribuída: A remoção de dados afeta todas as partes simultaneamente, exigindo coordenação complexa.
• Dependência de Recursos: As características interdependentes dificultam o isolamento e a remoção de contribuições de dados específicos.
• Limitações dos Métodos Atuais: Abordagens existentes (como ascensão de gradiente) frequentemente falham em equilibrar a eficácia do esquecimento com a preservação da utilidade do modelo, levando a instabilidade ou "esquecimento excessivo" que degrada o desempenho.

2. Metodologia: FedORA

Os autores propõem o FedORA (Federated Optimization for data Removal via primal-dual Algorithm), um framework baseado em otimização primal-dual para desaprendizado de amostras e rótulos no VFL.

Principais Componentes Técnicos:

• Formulação como Otimização Restrita:
  O problema é formulado como minimizar a perda nos dados restantes ($L_r$) sujeito a uma restrição de que a perda nos dados a serem esquecidos ($L_u$) deve ser superior a um limiar $\gamma$. Isso é resolvido usando multiplicadores de Lagrange e o framework Primal-Dual (inspirado no algoritmo PDHG/Chambolle-Pock).

  • Variável Primal ($\Theta$): Atualiza os parâmetros do modelo para manter o desempenho nos dados restantes.
  • Variável Dual ($\Omega$): Atua como um "certificado" de força de desaprendizado. Se o modelo ainda "lembra" os dados alvo, $\Omega$ aumenta para aplicar pressão de esquecimento; se a restrição é satisfeita, $\Omega$ diminui.

• Função de Perda de Desaprendizado Baseada em Incerteza:
  Diferente dos métodos tradicionais que forçam a má-classificação (aumentando a perda), o FedORA busca promover incerteza de classificação.

  • O objetivo é que o modelo saia com uma distribuição de probabilidade uniforme sobre as classes para as amostras a serem esquecidas.
  • A função de perda combina Entropia (para maximizar a incerteza) e Divergência KL (para minimizar o desvio em relação à distribuição uniforme), evitando o esquecimento catastrófico.

• Tamanho de Passo Adaptativo:
  Para garantir estabilidade na convergência, o algoritmo ajusta dinamicamente os tamanhos de passo ($\tau$ para primal, $\sigma$ para dual) com base na mudança relativa dos parâmetros entre iterações. Se as atualizações são grandes (instabilidade), o passo é reduzido; se são pequenas, o passo é aumentado para acelerar a convergência.

• Design de Lotes Assimétricos (Asymmetric Batch):
  Para reduzir o custo computacional e de comunicação:

  • Dados a serem esquecidos ($D_u$): Processados em lotes completos (batch total) para garantir a remoção total da influência.
  • Dados restantes ($D_r$): Processados apenas em subconjuntos (mini-batches) selecionados aleatoriamente. Como esses dados já influenciaram o modelo durante o treinamento inicial, não é necessário processar o conjunto completo para manter a utilidade.

3. Contribuições Principais

1. Primeiro Método Primal-Dual para VFL: O FedORA é a primeira abordagem a utilizar otimização primal-dual para desaprendizado de amostras e rótulos no VFL, tratando-o como um problema de otimização restrita.
2. Nova Função de Perda: Introdução de uma função de perda que incentiva a incerteza (distribuição uniforme) em vez de erro de classificação, mitigando a instabilidade de métodos de ascensão de gradiente.
3. Eficiência Computacional: Implementação de um mecanismo de tamanho de passo adaptativo e um design de lote assimétrico que reduz significativamente o custo computacional e de comunicação sem sacrificar a qualidade.
4. Garantias Teóricas: Prova teórica de que a diferença entre o modelo obtido pelo FedORA e o modelo retreinado do zero (Train-from-scratch) é limitada (bounded), validando a eficácia do desaprendizado.

4. Resultados Experimentais

Os autores avaliaram o FedORA em conjuntos de dados tabulares (Income) e de imagem (MedMNIST, CIFAR-10, CIFAR-100, Tiny-ImageNet), comparando com métodos Retrain, Ascensão de Gradiente (GA), ICO e CVFU.

• Eficácia de Desaprendizado:

  • O FedORA alcançou uma precisão nos dados esquecidos (Unlearning Accuracy) significativamente menor (melhor) do que o Retrain em cenários complexos (ex: <35% no CIFAR-100 vs >59% do Retrain), indicando que o modelo "esqueceu" melhor os dados.
  • Em ataques de inferência de associação (MIA) e backdoor, o FedORA reduziu as taxas de sucesso para níveis próximos ao acaso (50% para MIA, <10% para Backdoor), demonstrando que os dados foram efetivamente removidos.

• Preservação de Utilidade:

  • A precisão no conjunto de teste (dados restantes) do FedORA foi comparável à do Retrain (o padrão-ouro), superando consistentemente outros métodos de desaprendizado rápido (GA, ICO, CVFU), especialmente em datasets complexos.

• Eficiência:

  • O FedORA foi o segundo método mais rápido, perdendo apenas para a Ascensão de Gradiente (que tem baixa eficácia) e sendo significativamente mais rápido que o Retrain e o CVFU.
  • O uso de lotes assimétricos (processando apenas uma fração $\delta$ dos dados restantes) reduziu o tempo de execução em até 4,5x sem perda significativa de desempenho.

• Robustez:

  • O método manteve sua eficácia sob distribuições de dados não-IID e em cenários com ruído de privacidade (Differential Privacy).

5. Significado e Impacto

O trabalho do FedORA é significativo porque resolve um dos maiores gargalos da privacidade em IA: como remover dados específicos de modelos distribuídos verticalmente de forma eficiente e certificada.

• Certificação: Ao usar a dualidade de Lagrange, o método fornece uma garantia matemática de que o desaprendizado foi eficaz.
• Viabilidade Prática: Ao equilibrar a eficácia do esquecimento com a preservação da utilidade e reduzir custos computacionais, o FedORA torna o cumprimento do "Direito ao Esquecimento" viável em grandes sistemas de aprendizado federado vertical, onde o retreinamento completo é impossível.
• Inovação Conceitual: A mudança de paradigma de "forçar o erro" para "promover a incerteza" oferece uma nova direção para a pesquisa em desaprendizado de máquina, evitando a degradação do modelo.

Em suma, o FedORA estabelece um novo estado da arte para o desaprendizado em VFL, oferecendo uma solução teoricamente fundamentada, computacionalmente eficiente e empiricamente robusta.