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

Resumen Técnico: Un Marco de Muestreo Jerárquico para Acotar el Error de Generalización del Aprendizaje Federado

Enunciado del Problema
El Aprendizaje Federado (FL) permite que múltiples clientes entrenen colaborativamente un modelo global manteniendo los datos localizados. Aunque existen cotas de generalización para el aprendizaje supervisado centralizado, su aplicación directa al FL a menudo falla al no aprovechar la estructura específica del entorno FL, particularmente la naturaleza no i.i.d. de los datos que surge de las estrategias de muestreo jerárquico. La literatura existente carece de un marco unificado que abarque diversas estrategias de muestreo jerárquico y estructuras de comunicación, dependiendo frecuentemente de supuestos que chocan con la naturaleza distribuida del FL o que no tienen en cuenta las dependencias inducidas por fuentes de datos jerárquicas.

Metodología
Los autores proponen un marco generalizado para el Aprendizaje Federado Jerárquico (HFL) modelado como una estructura de árbol multicapa. En este entorno:

• Muestreo Jerárquico: El conjunto de datos está indexado por un árbol con una topología fija. La raíz representa una meta-distribución $D$. Los nodos en capas intermedias representan clientes o clústeres (distribuciones sobre nodos inferiores), y los nodos hoja representan puntos de datos reales. El muestreo procede recursivamente desde la raíz hasta las hojas, induciendo dependencias entre los conjuntos de datos de los clientes.
• Construcción de Supermuestra: Para analizar la generalización, los autores adaptan la técnica de "supermuestra" (originalmente de Steinke et al., 2020). Construyen un conjunto de datos "fantasma" $\bar{\mu}$ con propiedades estadísticas idénticas al conjunto de datos original $\mu$. Para cada nodo en el árbol, una variable binaria $U$ selecciona entre el nodo original y su copia fantasma. Esto permite medir la sensibilidad del algoritmo al cambio de un solo nodo en el árbol de muestreo.
• Distancia de Wasserstein: El error de generalización se acota utilizando la distancia de Wasserstein-1 ($W$) entre la distribución de la hipótesis de salida condicionada a una selección específica de nodo versus la distribución incondicional. Este enfoque se basa en el supuesto de que la función de pérdida $\ell(w, z)$ es $L$-Lipschitz con respecto a la hipótesis $w$.

Contribuciones Clave

1. Marco HFL Generalizado: El artículo introduce un marco que abarca diversas estrategias de muestreo jerárquico y marcos FL anteriores como casos especiales, modelando explícitamente las dependencias inducidas por la estructura del árbol.
2. Cota de Generalización de Wasserstein: Los autores derivan una nueva cota de generalización en términos de la distancia de Wasserstein. Esta cota es válida para una amplia gama de funciones de pérdida (bajo el supuesto de Lipschitz) y se demuestra que es estrictamente más ajustada que las cotas existentes de última generación basadas en Información Mutua Condicional (CMI) para pérdidas acotadas.
3. Cotas Conscientes de la Privacidad: El marco se extiende para incorporar supuestos de Privacidad Diferencial (DP). Al imponer restricciones de privacidad local en los pasos de agregación dentro del árbol, los autores derivan cotas de generalización basadas en la privacidad algorítmica.
4. Estudio de Caso del Modelo de Ubicación Gaussiana (GLM): La precisión de las cotas derivadas se evalúa utilizando un Modelo de Ubicación Gaussiana. Los autores demuestran que su cota recupera la tasa asintótica correcta del error de generalización con respecto al número de puntos de datos, aunque exhibe una discrepancia de escala con respecto a la profundidad del árbol de muestreo en comparación con el error real.

Resultados

• Teorema Principal (Teorema 5): Bajo el supuesto de Lipschitz, el error de generalización esperado está acotado por una suma sobre las capas del árbol de la distancia de Wasserstein esperada entre la distribución de la hipótesis condicionada a un nodo seleccionado y la distribución incondicional de la hipótesis.
• Relación con CMI (Corolario 6 y 9): Para pérdidas acotadas, la cota de Wasserstein implica las cotas CMI existentes. Los autores muestran que su derivación evita la holgura introducida por las cadenas de desigualdades (como la desigualdad de Pinsker aplicada múltiples veces) encontradas en pruebas anteriores basadas en CMI, resultando en una cota estrictamente más ajustada.
• Implicaciones de Privacidad (Teorema 13): Bajo supuestos de privacidad diferencial $\epsilon$ para la agregación local, el error de generalización está acotado por una función de los parámetros de privacidad $\epsilon_l$ a través de las capas, involucrando específicamente $\sqrt{\min(\epsilon_l, \epsilon_l(e^{\epsilon_l}-1))}$.
• Análisis GLM: En el Modelo de Ubicación Gaussiana, el error de generalización real escala como $\sqrt{\frac{\sum \sigma_l^2/N_l}{\sum \sigma_l^2}}$. La cota de Wasserstein derivada escala como $\sum \frac{\sigma_l}{N_l}$. Aunque la cota captura la escala con el número de puntos de datos ($N_l$), los autores notan que pasa por alto la escala específica con la profundidad del árbol ($L$) observada en el error real, particularmente cuando las varianzas son homogéneas a través de las capas.

Significado y Afirmaciones
El artículo afirma proporcionar una base teórica más general y ajustada para comprender la generalización en el Aprendizaje Federado al tener en cuenta explícitamente las dependencias de datos jerárquicos. Al utilizar la distancia de Wasserstein, el marco captura la geometría de las distribuciones y la sensibilidad del algoritmo de aprendizaje a la estructura de muestreo de manera más efectiva que los enfoques teóricos de la información anteriores. Los autores afirman que su cota implica estrictamente las cotas CMI existentes para pérdidas acotadas, ofreciendo un refinamiento y no simplemente una alternativa. Además, la capacidad del marco para integrarse sin problemas con los supuestos de Privacidad Diferencial demuestra su utilidad en el análisis de sistemas FL que preservan la privacidad. Los autores reconocen limitaciones, señalando que la cota actual no tiene en cuenta explícitamente las restricciones de comunicación o las limitaciones computacionales de los nodos individuales, aunque sugieren que estas pueden incorporarse mediante condiciones de independencia como se muestra en su derivación del Corolario 10. Se sugiere trabajo futuro para extender el marco a estructuras de árbol generales (no fijas).