Adaptive Data Admission and Retention for Streaming Federated Learning

Resumen Técnico: Admisión y Retención de Datos Adaptativa para Aprendizaje Federado de Flujo Continuo (Streaming)

Declaración del Problema
Este artículo aborda el desafío del Aprendizaje Federado de Flujo Continuo (Streaming Federated Learning - FL) en entornos donde los dispositivos cliente tienen memoria limitada y los datos de entrenamiento llegan secuencialmente con costos de muestreo variables en el tiempo. A diferencia de las configuraciones tradicionales de FL con conjuntos de datos estáticos fuera de línea, el FL de flujo continuo implica un flujo constante de nuevas muestras que incurren en costos de adquisición, anotación o transmisión. Los clientes no pueden almacenar todos los datos históricos indefinidamente. En consecuencia, el sistema se enfrenta a un compromiso fundamental: admitir muestras frescas mejora la diversidad y la generalización de los datos, pero incurre en costos inmediatos, mientras que retener y reutilizar muestras históricas reduce los costos pero conlleva el riesgo de "desequilibrio de reutilización" (dependencia excesiva de datos obsoletos) y desbordamiento de memoria.

El problema central se formula como una tarea de optimización estocástica con restricciones. El objetivo es minimizar el riesgo de población excesivo acumulado (la diferencia entre el riesgo del modelo aprendido y el riesgo de población óptimo) sujeto a dos restricciones a largo plazo:

1. Presupuesto de costo de muestreo: El costo promedio de admitir muestras no debe exceder un límite prescrito.
2. Restricción de ocupación de búfer: El número promedio de muestras almacenadas en el búfer local de cada cliente no debe exceder su capacidad de memoria.

Crucialmente, el marco desacopla el control: un Servidor de Parámetros (PS) central decide las cantidades de admisión (cuántas muestras nuevas aceptar), mientras que los clientes individuales gestionan de forma independiente sus búferes locales (qué muestras descartar) basándose en información local, sin que el PS acceda a los datos brutos.

Metodología
Los autores proponen un marco unificado que comprende un límite de aprendizaje teórico y una política de control en línea.

1. Derivación del Límite de Error de Aprendizaje:
   El artículo deriva primero un límite superior explícito sobre el riesgo de población excesivo acumulado. Este límite caracteriza explícitamente tres factores críticos:

• Tamaño de la muestra de entrenamiento instantánea ($n(t)$): El número de muestras actualmente en el búfer utilizadas para el entrenamiento.
• Crecimiento de muestras distintas ($N(t)$): El número acumulado de muestras únicas observadas.
• Desequilibrio de reutilización: La pérdida de diversidad estadística causada por una reutilización desigual de las muestras almacenadas.
  Para capturar esto, los autores introducen una métrica de tamaño de muestra efectivo, $\tilde{N}_{eff}(t) = N(t) \cdot \tilde{V}(t)$, donde $\tilde{V}(t)$ es un factor que mide la uniformidad de la reutilización de muestras. El límite muestra que el rendimiento del aprendizaje se degrada si la reutilización de muestras es altamente desigual.

2. Política de Desviación de Restricción Activa (ACDPP - Active-Constraint Drift-Plus-Penalty):
   Para optimizar el sistema en línea, los autores desarrollan la política ACDPP, que combina:

• Retención de $K$ pasos en el lado del cliente: Una regla estructurada donde cada muestra admitida se retiene exactamente durante $K$ rondas antes de ser descartada. Esta regla determinista simplifica el patrón de reutilización, permitiendo que el factor de tamaño de muestra efectivo $\tilde{V}(t)$ se exprese en forma cerrada.
• Admisión en línea en el lado del servidor: Un algoritmo Drift-Plus-Penalty (DPP) modificado. El servidor mantiene una cola virtual de deuda de costo para rastrear las violaciones del presupuesto de costo de muestreo. Minimiza una expresión de "desviación más penalización" (drift-plus-penalty) donde el término de penalización es un sustituto del límite de error de aprendizaje derivado anteriormente.
• Restricciones Rectangulares Variables en el Tiempo: Una adición novedosa al marco estándar de DPP. La región de admisión factible está restringida dentro de un intervalo variable en el tiempo $[\Lambda_{min}(t), \Lambda_{max}(t)]$ que se reduce gradualmente hacia un punto operativo objetivo $\bar{\Lambda}$ a medida que transcurre el tiempo. Este diseño equilibra la flexibilidad inicial (para adaptarse a costos variables) con la estabilidad en etapas tardías (para minimizar los términos $1/n(t)$ en el límite de error).

Contribuciones Clave

• Caracterización Teórica: El artículo establece un límite de error de aprendizaje para el FL de flujo continuo basado en memoria que vincula explícitamente el rendimiento con el tamaño de muestra instantáneo, el recuento de muestras distintas y el desequilibrio de reutilización mediante una representación de tamaño de muestra efectivo.
• Diseño de Algoritmo: La propuesta de la política ACDPP, que integra una regla de retención de $K$ pasos en el cliente con una regla de admisión en línea en el servidor que presenta restricciones rectangulares variables en el tiempo.
• Garantías de Rendimiento: Los autores demuestran que la política propuesta logra:
  • Regret Sublineal: El riesgo excesivo acumulado crece de forma sublineal respecto a un benchmark de oráculo sin costos (que tiene memoria ilimitada y costo de muestreo cero).
  • Violación de Costo Sublineal: La violación acumulada del presupuesto de costo de muestreo crece de forma sublineal.
  • Violación de Búfer Acotada: Mediante la selección offline del horizonte de retención $K$, se demuestra que la violación acumulada de la ocupación del búfer está uniformemente acotada ($O(1)$).
• Marco de Comparación: El análisis emplea una cadena de comparación de múltiples pasos que conecta la política ACDPP con una política de admisión constante auxiliar y, finalmente, con el oráculo sin costo, proporcionando límites de regret explícitos.

Resultados Experimentales
La política fue evaluada en tres conjuntos de datos de clasificación de imágenes: MNIST, CIFAR-10 e ImageNette, bajo particiones de datos tanto no-i.i.d. como i.i.d.

• Rendimiento: ACDPP superó consistentemente a las líneas base, incluyendo una política híbrida (mezcla de muestras frescas y antiguas) y una política de admisión constante. En CIFAR-10 (no-i.i.d.), ACDPP mejoró la precisión de prueba en 26.7 puntos porcentuales sobre la línea base híbrida y 3.5 puntos sobre la línea base de admisión constante.
• Velocidad de Convergencia: ACDPP convergió significativamente más rápido, alcanzando las precisiones objetivo aproximadamente entre 2.2x y 2.6x más rápido que las líneas base en varios conjuntos de datos.
• Satisfacción de Restricciones: Los experimentos confirmaron que la política mantuvo la ocupación del búfer dentro de los límites prescritos y estabilizó la cola de deuda de costo, validando sus garantías teóricas.

Significancia y Reivindicaciones
El artículo afirma cerrar una brecha en la literatura existente al proporcionar un marco centrado en el aprendizaje que optimiza conjuntamente la admisión y la gestión de memoria bajo costos dinámicos, en lugar de centrarse únicamente en recursos a nivel de sistema (comunicación/computación) o en la selección estática de muestras.

• Va más allá de los métodos de selección basados en "puntuación" (que asumen que las muestras con gradientes altos son valiosas) al minimizar directamente el riesgo de población excesivo acumulado con garantías de regret teórico.
• Aborda el desafío específico de los datos de flujo continuo (streaming) donde el aprendiz debe decidir cuántas muestras admitir y cuánto tiempo retenerlas, un problema no abordado completamente por trabajos previos centrados en recursos o en la selección.
• Los autores enfatizan que su enfoque proporciona garantías de regret explícitas y sublineales y maneja los efectos acoplados de la admisión y la retención de muestras, ofreciando una solución fundamentada para el entrenamiento de modelos a gran escala y conscientes de la privacidad en sistemas de borde (edge systems) con flujos de datos en evolución.