A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning

Resumo Técnico: Uma Estrutura de Amostragem Hierárquica para Limitar o Erro de Generalização do Aprendizado Federado

Declaração do Problema
O Aprendizado Federado (AF) permite que múltiplos clientes treinem colaborativamente um modelo global mantendo os dados localizados. Embora existam limites de generalização para aprendizado supervisionado centralizado, aplicá-los diretamente ao AF frequentemente falha em aproveitar a estrutura específica da configuração de AF, particularmente a natureza não i.i.d. dos dados decorrente de estratégias de amostragem hierárquica. A literatura existente carece de uma estrutura unificada que abranja diversas estratégias de amostragem hierárquica e estruturas de comunicação, frequentemente dependendo de suposições que colidem com a natureza distribuída do AF ou falhando em contabilizar as dependências induzidas por fontes de dados hierárquicas.

Metodologia
Os autores propõem uma estrutura generalizada para Aprendizado Federado Hierárquico (AFH) modelada como uma estrutura de árvore multicamadas. Neste cenário:

• Amostragem Hierárquica: O conjunto de dados é indexado por uma árvore com topologia fixa. A raiz representa uma meta-distribuição $D$. Nós em camadas intermediárias representam clientes ou clusters (distribuições sobre nós inferiores), e nós folha representam pontos de dados reais. A amostragem procede recursivamente da raiz até as folhas, induzindo dependências entre os conjuntos de dados dos clientes.
• Construção de Supersamplagem: Para analisar a generalização, os autores adaptam a técnica de "supersamplagem" (originalmente de Steinke et al., 2020). Eles constroem um conjunto de dados "fantasma" $\bar{\mu}$ com propriedades estatísticas idênticas ao conjunto de dados original $\mu$. Para cada nó na árvore, uma variável binária $U$ seleciona entre o nó original e sua cópia fantasma. Isso permite a medição da sensibilidade do algoritmo à mudança de um único nó na árvore de amostragem.
• Distância de Wasserstein: O erro de generalização é limitado usando a distância de Wasserstein-1 ($W$) entre a distribuição da hipótese de saída condicionada a uma seleção específica de nó versus a distribuição incondicional. Esta abordagem depende da suposição de que a função de perda $\ell(w, z)$ é $L$-Lipschitziana em relação à hipótese $w$.

Contribuições Principais

1. Estrutura Generalizada de AFH: O artigo introduz uma estrutura que abrange diversas estratégias de amostragem hierárquica e estruturas anteriores de AF como casos especiais, modelando explicitamente as dependências induzidas pela estrutura da árvore.
2. Limite de Generalização de Wasserstein: Os autores derivam um novo limite de generalização em termos da distância de Wasserstein. Este limite vale para uma ampla gama de funções de perda (sob a suposição de Lipschitz) e demonstra ser estritamente mais apertado do que os limites existentes de Informação Mutual Condicional (CMI) de última geração para perdas limitadas.
3. Limites Conscientes de Privacidade: A estrutura é estendida para incorporar suposições de Privacidade Diferencial (PD). Ao impor restrições de privacidade local nas etapas de agregação dentro da árvore, os autores derivam limites de generalização baseados em privacidade algorítmica.
4. Estudo de Caso do Modelo de Localização Gaussiana (GLM): A precisão dos limites derivados é avaliada usando um Modelo de Localização Gaussiana. Os autores demonstram que seu limite recupera a taxa assintótica correta do erro de generalização em relação ao número de pontos de dados, embora exiba uma discrepância de escala em relação à profundidade da árvore de amostragem comparado ao erro real.

Resultados

• Teorema Principal (Teorema 5): Sob a suposição de Lipschitz, o erro de generalização esperado é limitado por uma soma sobre as camadas da árvore da distância de Wasserstein esperada entre a distribuição da hipótese condicionada a um nó selecionado e a distribuição incondicional da hipótese.
• Relação com CMI (Corolário 6 e 9): Para perdas limitadas, o limite de Wasserstein implica os limites de CMI existentes. Os autores mostram que sua derivação evita a frouxidão introduzida pelas cadeias de desigualdades (como a desigualdade de Pinsker aplicada múltiplas vezes) encontradas em provas anteriores baseadas em CMI, resultando em um limite estritamente mais apertado.
• Implicações de Privacidade (Teorema 13): Sob suposições de privacidade diferencial $\epsilon$ para agregação local, o erro de generalização é limitado por uma função dos parâmetros de privacidade $\epsilon_l$ através das camadas, envolvendo especificamente $\sqrt{\min(\epsilon_l, \epsilon_l(e^{\epsilon_l}-1))}$.
• Análise GLM: No Modelo de Localização Gaussiana, o erro de generalização real escala como $\sqrt{\frac{\sum \sigma_l^2/N_l}{\sum \sigma_l^2}}$. O limite de Wasserstein derivado escala como $\sum \frac{\sigma_l}{N_l}$. Embora o limite capture a escala com o número de pontos de dados ($N_l$), os autores observam que ele perde a escala específica com a profundidade da árvore ($L$) observada no erro real, particularmente quando as variâncias são homogêneas entre as camadas.

Significado e Alegações
O artigo alega fornecer uma base teórica mais geral e apertada para entender a generalização no Aprendizado Federado, contabilizando explicitamente as dependências hierárquicas de dados. Ao utilizar a distância de Wasserstein, a estrutura captura a geometria das distribuições e a sensibilidade do algoritmo de aprendizado à estrutura de amostragem de forma mais eficaz do que abordagens anteriores baseadas em teoria da informação. Os autores afirmam que seu limite implica estritamente os limites de CMI existentes para perdas limitadas, oferecendo um refinamento e não apenas uma alternativa. Além disso, a capacidade da estrutura de integrar-se perfeitamente com suposições de Privacidade Diferencial demonstra sua utilidade na análise de sistemas de AF que preservam a privacidade. Os autores reconhecem limitações, observando que o limite atual não contabiliza explicitamente restrições de comunicação ou limitações computacionais de nós individuais, embora sugiram que estes podem ser incorporados via condições de independência conforme demonstrado em sua derivação do Corolário 10. Trabalhos futuros são sugeridos para estender a estrutura para estruturas de árvore gerais (não fixas).