🤖 machine learning

Federated and differentially private estimation of KL divergence

Este artigo apresenta o FedPriKL, um novo método de privacidade diferencial para estimar a divergência KL em ambientes federados que alcança precisão não enviesada e de baixa variância com sensibilidade limitada, minimizando o overhead de comunicação em comparação com as linhas de base existentes.

Autores originais: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Publicado 2026-08-24

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

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

No mundo moderno dos dados, a informação está frequentemente dispersa por milhões de dispositivos individuais, desde smartphones a rastreadores de saúde vestíveis. Essa natureza dispersa cria uma forma poderosa de aprender sobre o mundo sem nunca reunir os dados de todos em um cofre central. Essa abordagem, conhecida como aprendizado federado (federated learning), permite que um sistema central construa modelos ao pedir que os dispositivos realizem cálculos em seus próprios dados locais e, em seguida, compartilhem apenas os resultados. No entanto, um desafio crítico permanece: como saber se os dados que estão sendo usados estão mudando ao longo do tempo? Se o comportamento das pessoas que utilizam um aplicativo mudar, os modelos construídos com base em dados antigos podem se tornar imprecisos ou irrelevantes. Para corrigir isso, os analistas precisam medir a diferença entre os dados atuais e um padrão conhecido, uma tarefa que geralmente exige ver os dados brutos. Mas em um mundo onde a privacidade é primordial, revelar os dados brutos é frequentemente impossível. A solução requer uma maneira de medir essa diferença matematicamente sem nunca expor os detalhes individuais que compõem os dados.

Pesquisadores da EPFL, da Universidade de Oxford, da Universidade de Warwick e do Infectious Diseases Data Observatory desenvolveram um novo método chamado FedPriKL para resolver exatamente este problema. O trabalho deles foca em uma medida matemática específica usada para comparar dois conjuntos de dados, uma ferramenta que nos diz o quanto um grupo de informações se afastou de um ponto de referência. Neste cenário, o ponto de referência é um padrão público com o qual todos concordam, enquanto o outro grupo são os dados privados e sensíveis mantidos pelos usuários em seus dispositivos. O objetivo é calcular a distância entre esses dois grupos sem que o servidor central veja os registros individuais. Os pesquisadores criaram um protocolo que permite que um coordenador central peça a uma pequena seleção aleatória de dispositivos para verificar a frequência com que certos itens aparecem em seus dados locais. Esses dispositivos então enviam de volta apenas as contagens para esses itens específicos, que são combinadas de forma segura. Para garantir que mesmo essas contagens não possam ser rastreadas até uma única pessoa, o sistema adiciona uma quantidade cuidadosamente calculada de ruído matemático ao resultado final.

A equipe descobriu que seu método funciona com um alto grau de precisão, mantendo garantias estritas de privacidade. Eles provaram matematicamente que sua abordagem produz uma estimativa não enviesada, o que significa que o resultado é correto em média, e que a quantidade de ruído necessária para proteger a privacidade é pequena o suficiente para não arruinar a utilidade dos dados. Em seus experimentos, eles testaram o sistema usando um grande conjunto de dados de dígitos manuscritos, simulando um cenário do mundo real onde milhares de usuários contribuem com dados. Eles descobriram que, ao escolher cuidadosamente quantos dispositivos consultar e quanto ruído adicionar, o sistema poderia produzir resultados quase tão precisos quanto se nenhuma proteção de privacidade tivesse sido usada. Isso é uma melhoria significativa em relação aos métodos anteriores, nos quais os dispositivos tentavam esconder seus dados adicionando ruído antes do envio, uma técnica que frequentemente levava a resultados imprecisos. O novo método mantém a adição de ruído para o final do processo, após os dados terem sido seguramente combinados, o que preserva a integridade da medição.

Os pesquisadores também exploraram como diferentes configurações afetam o resultado. Eles descobriram que o sistema funciona bem mesmo quando apenas uma pequena fração do total de usuários é solicitada a participar em qualquer rodada dada, e que a quantidade de dados que cada usuário precisa enviar é muito pequena, muitas vezes menos de um quilobyte. Isso torna o sistema prático para dispositivos com bateria e memória limitadas. O estudo mostrou que o método pode distinguir com precisão entre pequenas mudanças e grandes mudanças nos dados, o que é essencial para decidir quando um modelo de computador precisa ser atualizado. Embora a versão atual do sistema dependa de uma etapa intermediária de confiança para combinar os dados de forma segura, os pesquisadores demonstraram que essa etapa pode ser realizada usando hardware seguro existente ou técnicas criptográficas avançadas, garantindo que nenhuma entidade individual veja os dados brutos. O trabalho fornece um caminho concreto para monitorar tendências de dados de uma forma que respeite a privacidade do usuário, permitindo que as organizações mantenham seus modelos precisos sem comprometer a confidencialidade dos indivíduos que geram os dados.

Resumo Técnico: FedPriKL – Estimativa de Divergência KL Federada e com Privacidade Diferencial

Declaração do Problema

Na aprendizagem federada e análise modernas, uma tarefa crítica é o monitoramento do desvio de distribuição para determinar quando os modelos requerem retreinamento ou ajuste fino. Isso exige a comparação da distribuição empírica dos dados mantidos por clientes distribuídos ( $P$ ) contra uma distribuição de referência pública fixa ( $\Pi$ ). No entanto, compartilhar diretamente os dados dos clientes ou histogramas completos é frequentemente inviável devido aos altos custos de comunicação e restrições de privacidade.

As abordagens existentes enfrentam obstáculos significativos:

Privacidade: A coleta centralizada de amostras viola a privacidade do usuário.
Resultados de Impossibilidade: O Teorema da Invariância de Deslocamento [9] implica que estimar a divergência KL entre duas distribuições desconhecidas em um espaço menor que o tamanho do domínio é impossível.
Comunicação: Transmitir histogramas completos dos clientes para um servidor é proibitivo em termos de largura de banda para domínios grandes.
Viés na Perturbação Local: As abordagens padrão de privacidade diferencial local (LDP), onde os clientes adicionam ruído antes da agregação, introduzem um viés significativo ao estimar funções não lineares como a divergência KL, particularmente ao lidar com pequenas massas de probabilidade.

O artigo aborda o problema de estimar $D_{KL}(\Pi \parallel P)$ em um cenário federado horizontal onde $P$ é definido pelos dados agregados de $n$ clientes, e $\Pi$ é um benchmark público conhecido. O objetivo é alcançar privacidade diferencial (DP) formal ao nível do exemplo, minimizando o overhead de comunicação e mantendo a precisão do estimador.

Metodologia: FedPriKL

Os autores propõem o FedPriKL, um protocolo baseado em amostragem que utiliza um modelo de "agregador confiável" para alcançar uma estimativa não viesada sob DP. A inovação técnica central é um estimador de Monte Carlo não viesado baseado em razões de verossimilhança, combinado com agregação segura e injeção de ruído calibrado.

Componentes Principais:

Estimador de Monte Carlo Não Viesado:
Em vez de computar a divergência total, o método amostra $m$ pontos $x_i$ da distribuição de referência $\Pi$ . Para cada amostra, o protocolo estima a razão de verossimilhança $r(x) = P(x)/\Pi(x)$ .
Usando a identidade derivada do Fato IV.2, a divergência KL é estimada através da função:
$\Phi(r(x), \lambda) = \lambda(r(x) - 1) - \ln(r(x))$
A esperança desta função sobre as amostras de $\Pi$ é igual a $D_{KL}(\Pi \parallel P)$ . O parâmetro $\lambda$ controla a variância do estimador.
Fluxo de Trabalho do Protocolo (Algoritmo 2):
- Amostragem: O servidor seleciona lotes disjuntos de clientes ( $C_t$ ) e amostra pontos $x_{i,t}$ de $\Pi$ .
- Agregação Segura (SecAgg): Os clientes computam a frequência dos pontos amostrados em seus conjuntos de dados locais. Essas frequções são agregadas usando um protocolo de agregação segura (ex: compartilhamento de segredo de Shamir) para computar a massa de probabilidade empírica global $P(x)$ sem revelar os dados individuais dos clientes.
- Processamento do Agregador Confiável: As probabilidades agregadas são enviadas a um agregador confiável. O agregador computa as razões de verossimilhança $r(x)$ , aplica a transformação não linear $\Phi$ e adiciona ruído Gaussiano calibrado ( $\eta_{\epsilon, \delta}$ ) ao resultado.
- Estimativa Final: Os valores transformados ruidosos são calculados pela média para produzir a estimativa DP final.
Mecanismo de Privacidade:
Ao contrário das abordagens de linha de base onde os clientes adicionam ruído localmente (pré-agregação), o FedPriKL adiciona ruído após a agregação segura, mas antes que a transformação não linear seja finalizada. Isso evita o viés introduzido pelo corte (clipping) de valores negativos no ruído local (um problema comum em LDP). A sensibilidade do estimador é limitada (Teoremas IV.4 e IV.5), permit um calibramento preciso do ruído para satisfazer $(\epsilon, \delta)$ -DP.
Modelo de Confiança:
O protocolo assume um agregador confiável (ou uma realização de TEE/SMC) que vê apenas as estatísticas agregadas de forma segura dos pontos amostrados, não os dados brutos dos clientes. O servidor é "honesto-mas-curioso" e recebe apenas a estimativa ruidosa final.

Principais Contribuições

Formalização do Problema: O artigo formaliza o problema de computar a divergência KL em um cenário federado com garantias formais de privacidade diferencial, abordando especificamente o caso de uma referência pública versus uma distribuição empírica privada.
Algoritmo FedPriKL: Os autores apresentam o primeiro estimador federado baseado em amostragem e eficiente em comunicação para $D_{KL}(\Pi \parallel P)$ que oferece DP ao nível do exemplo.
Análise Teórica:
- Não Viesamento: Provado que o estimador é não viesado (Teorema IV.7).
- Limites de Sensibilidade: Estabeleceu sensibilidade limitada para o estimador, permitindo a derivação de escalas de ruído ótimas (Teoremas IV.4, IV.5).
- Caracterização de Variância: Forneceu uma caracterização teórica da variância do estimador como uma função de $\lambda$ , $\epsilon$ e tamanho da amostra, e derivou o $\lambda$ ótimo para minimizar a variância (Teoremas V.1, V.3).
Eficiência de Comunicação: O payload por cliente é independente do tamanho do domínio. Para um domínio de $2^{16}$ elementos, o payload permanece abaixo de 1 KB.

Resultados Experimentais

Os autores avaliaram o FedPriKL no conjunto de dados FEMNIST (dígitos manuscritos particionados por escritor), comparando-o com um estimador não privado e uma abordagem de linha de base LDP (Algoritmo 1).

Precisão vs. Privacidade: O FedPriKL atinge uma precisão comparável ao estimador não privado quando o orçamento de privacidade $\epsilon$ é moderado ( $0.5 \le \epsilon \le 1.0$ ).
Superioridade sobre a Linha de Base: O FedPrikl supera significativamente a linha de base (perturbação local) em termos de precisão e estabilidade. A linha de base sofre com o viés devido ao corte necessário de estimativas de probabilidade negativas.
Sensibilidade de Parâmetros:
- $\lambda$ : O parâmetro de variância ótimo $\lambda$ é encontrado empiricamente como próximo de 0.
- Tamanho da Amostra ( $m$ ): Um pequeno número de amostras ( $m=10$ ) é suficiente para atingir precisão próxima da ótima, mantendo a comunicação do cliente leve.
- Tamanho do Lote (Batch Size): Variar o número de clientes participantes afeta a taxa de convergência, mas não altera fundamentalmente o $\lambda$ ótimo.
Robustez: O método mantém baixo erro absoluto através de diferentes magnitudes de divergência (de pequenos a grandes valores de KL).

Significância e Alegações

O artigo afirma que o FedPriKL é o primeiro estimador federado eficiente em comunicação para divergência KL entre uma referência pública e uma população privada que oferece privacidade diferencial formal ao nível do exemplo.

A significância reside em sua capacidade de:

Habilitar a Detecção de Desvio: Fornecer um mecanismo de preservação de privacidade para plataformas detectarem mudanças de distribuição e dispararem o retreinamento de modelos sem expor dados sensíveis dos usuários.
Superar a Impossibilidade: Ao restringir o problema a uma referência pública conhecida, ele contorna os resultados de impossibilidade relativos ao esboço (sketching) de distribuições desconhecidas.
Equilibrar Utilidade e Privacidade: Demonstra que uma alta utilidade pode ser mantida sob restrições estritas de privacidade ao mover a etapa de injeção de ruído para uma fase pós-agregação via um componente confiável, evitando assim o viés inerente aos métodos de perturbação local.

Os autores observam que a dependência de um agregador confiável (ou TEE/SMC) é um compromisso prático que pode ser resolvido via hardware seguro ou computação multipartidária, e identificam a remoção dessa suposição de confiança como uma direção para trabalhos futuros.