Resumen Técnico: Condiciones de Validez Práctica para el Aprendizaje Federado Tolerante a Bizantinos

1. Planteamiento del Problema

En el Aprendizaje Federado (FL), un servidor central agrega actualizaciones de modelos de alta dimensión procedentes de $n$ clientes. Cuando hasta $t$ clientes son bizantinos (maliciosos o defectuosos), pueden enviar vectores arbitrarios para interrumpir el proceso de aprendizaje. El desafío central consiste en definir condiciones de validez—garantías geométricas que especifican dónde debe situarse la salida de la agregación en relación con las entradas honestas—sin depender de distribuciones de datos específicas ni de modelos de ataque.

La condición clásica de validez convexa, que exige que la salida se sitúe dentro de la envolvente convexa de los vectores honestos, es teóricamente sólida pero prácticamente defectuosa para el FL moderno. Padece de una resiliencia dependiente de la dimensión, tolerando como máximo $t < n/(d+1)$ clientes bizantinos en $d$ dimensiones. Este límite es demasiado restrictivo para modelos de alta dimensión. Además, las reglas de agregación prácticas a menudo producen salidas fuera de la envolvente convexa de los vectores honestos mientras permanecen cercanas a la población honesta, un comportamiento que la validez convexa no logra capturar.

2. Metodología y Marco de Trabajo

Los autores proponen un nuevo marco de validez basado en la Esfera Mínima Encapsulante (MEB) en lugar de la envolvente convexa.

• Validez MEB: Requiere que el vector de salida se sitúe dentro de la esfera más pequeña que encapsula todos los vectores de entrada honestos. A diferencia de la envolvente convexa, la MEB es un objeto de dimensión completa que acomoda naturalmente salidas que salen de la envolvente convexa pero permanecen dentro de la escala geométrica de las actualizaciones honestas.
• Validez c-MEB (Relajada): Reconociendo que la validez MEB exacta sigue sufriendo limitaciones de resiliencia en altas dimensiones, los autores introducen una relajación multiplicativa. Un algoritmo satisface validez c-MEB si la salida se sitúa dentro de una esfera centrada en el centro de la MEB honesta, pero con un radio expandido por un factor $c$ (es decir, radio $c \cdot r^*$).
• Zona Segura: Los autores definen una "zona segura" para la validez MEB como la intersección de las MEB de todos los subconjuntos posibles de $n-t$ vectores. Demuestran que satisfacer la validez MEB requiere un acuerdo dentro de esta intersección.

3. Contribuciones y Resultados Clave

A. Límites de la Validez MEB Exacta

El artículo establece que la validez MEB exacta no es universalmente alcanzable en entornos de alta dimensión.

• Resultado de Imposibilidad: Los autores demuestran que ningún algoritmo de acuerdo puede satisfacer la validez MEB exacta si $n \le (d+1)t - d$. Esto refleja las limitaciones de resiliencia de la validez convexa, demostrando que la contención geométrica estricta es insuficiente para la tolerancia a bizantinos en altas dimensiones.

B. Algoritmo Óptimo para Validez MEB Relajada

Bajo la suposición de una mayoría honesta ($n > 2t$), los autores presentan MinMax-MEB, una regla de agregación óptima para la validez c-MEB.

• Mecanismo: El algoritmo calcula la MEB para cada subconjunto de $n-t$ clientes. Luego selecciona un vector de salida que minimiza la distancia normalizada máxima hacia estas MEB candidatas.
• Límite de Relajación: Utilizando el teorema de Soddy-Gosset (una generalización del teorema de Descartes sobre esferas tangentes), los autores demuestran que para $n > 2t$, el factor de relajación óptimo $c$ está acotado superiormente por:
  $$c < \sqrt{2}$$
  Específicamente, $c \le 1 + \frac{k-1}{k+1+\sqrt{2(k+1)k}}$, donde $k = \min\{d, \frac{n}{n-t} - 1\}$. Este límite es ajustado para $d=2$.

C. Garantías de Validez para Agregadores Prácticos

El artículo analiza reglas de agregación robustas existentes para determinar sus constantes de validez c-MEB:

1. Promedio de Diámetro Mínimo (MDA): Satisface validez MEB de $\left(1 + \frac{2t}{n-t}\right)$.
2. Medoide: Satisface validez MEB de $\frac{3n-2t}{n-2t}$. Los autores también demuestran que el medoide no puede satisfacer la validez c-MEB para $c \le 2$.
3. Mediana Geométrica: Satisface validez MEB de $\frac{2(n-t)}{n-2t}$. El artículo proporciona contraejemplos que muestran que la mediana geométrica no satisface la validez 1.08-MEB y no satisface la validez convexa.

Estos resultados demuestran que los algoritmos prácticos estándar, aunque violan la validez convexa estricta, satisfacen inherentemente la validez MEB relajada con factores constantes dependientes de la relación entre nodos bizantinos y honestos.

D. Comparación Sistemática de Condiciones de Validez

Los autores mapean las relaciones entre la validez MEB y las condiciones existentes:

• Validez Convexa $\implies$ Validez MEB: Dado que la envolvente convexa está contenida dentro de la MEB, cualquier salida que satisfaga la validez convexa satisface automáticamente la validez MEB.
• Validez MEB $\nRightarrow$ Validez Convexa: La validez MEB permite salidas fuera de la envolvente convexa (por ejemplo, en un subespacio de dimensión inferior colapsado por la envolvente convexa).
• Relación con la Validez Convexa Relajada: La validez c-MEB implica validez convexa relajada $(\delta, 2)$ con $\delta = (c+1)r^*$. Por el contrario, la validez convexa relajada implica una validez MEB relajada.
• Relación con la Validez de Caja: La validez de caja (límites por coordenada) implica validez $\sqrt{d}$-MEB, pero la validez MEB no implica validez de caja, ya que la MEB es de dimensión completa mientras que la caja puede colapsar en ciertas dimensiones.

4. Significado y Afirmaciones

El artículo afirma que la validez c-MEB ofrece una alternativa práctica a la validez convexa para el Aprendizaje Federado Tolerante a Bizantinos.

• Puente entre Teoría y Práctica: Conecta las condiciones de validez geométrica utilizadas en la computación distribuida con el comportamiento de las reglas de agregación prácticas utilizadas en FL.
• Independencia de la Dimensión: A diferencia de la validez convexa, la condición MEB relajada no padece de límites de resiliencia dependientes de la dimensión (siempre que $n > 2t$), lo que la hace adecuada para modelos de alta dimensión.
• Límite de Sesgo: Los autores señalan que la validez c-MEB proporciona un límite independiente de la distribución sobre el sesgo del agregado en relación con la actualización promedio honesta, conectando las garantías geométricas con los análisis estándar de la optimización robusta a bizantinos.

5. Limitaciones

Los autores reconocen varias limitaciones:

• Complejidad Computacional: La regla óptima MinMax-MEB requiere calcular MEB para todos los subconjuntos de tamaño $n-t$, lo cual es computacionalmente costoso para $t$ grandes. Las reglas prácticas (Medoide, Mediana Geométrica) son más eficientes pero ofrecen factores de relajación más débiles.
• Supuestos del Modelo: El marco asume un servidor de confianza, comunicación fiable, geometría euclidiana y un límite superior conocido $t$ sobre los clientes bizantinos.
• Ajuste de los Límites: Aunque el límite $c < \sqrt{2}$ es ajustado para $d=2$, los factores óptimos para dimensiones superiores y para algoritmos específicos como MDA y Medoide pueden ser más ajustados de lo que se ha demostrado actualmente.
• Aditivo vs. Multiplicativo: El artículo señala que la relación entre las relajaciones multiplicativas y aditivas de la validez MEB sigue siendo una pregunta abierta.