2025-11-27T01:52:18.796624

On the Limits of Momentum in Decentralized and Federated Optimization

Zaccone, Karimireddy, Masone

Recent works have explored the use of momentum in local methods to enhance distributed SGD. This is particularly appealing in Federated Learning (FL), where momentum intuitively appears as a solution to mitigate the effects of statistical heterogeneity. Despite recent progress in this direction, it is still unclear if momentum can guarantee convergence under unbounded heterogeneity in decentralized scenarios, where only some workers participate at each round. In this work we analyze momentum under cyclic client participation, and theoretically prove that it remains inevitably affected by statistical heterogeneity. Similarly to SGD, we prove that decreasing step-sizes do not help either: in fact, any schedule decreasing faster than $Î\left(1/t\right)$ leads to convergence to a constant value that depends on the initialization and the heterogeneity bound. Numerical results corroborate the theory, and deep learning experiments confirm its relevance for realistic settings.

academic

Sobre los Límites del Momentum en Optimización Descentralizada y Federada

Información Básica

ID del Artículo: 2511.20168
Título: On the Limits of Momentum in Decentralized and Federated Optimization
Autores: Riccardo Zaccone (Politécnico de Turín), Sai Praneeth Karimireddy (USC), Carlo Masone (Politécnico de Turín)
Clasificación: cs.LG (Aprendizaje Automático), cs.AI
Fecha de Publicación: Noviembre de 2025 (preimpresión en arXiv)
Enlace del Artículo: https://arxiv.org/abs/2511.20168

Resumen

Este artículo explora en profundidad las limitaciones teóricas del momentum en aprendizaje federado y optimización descentralizada. Aunque investigaciones recientes han explorado el uso de momentum en métodos locales para mejorar SGD distribuido, particularmente en aprendizaje federado para mitigar los efectos de la heterogeneidad estadística, permanece sin claridad si el momentum puede garantizar convergencia bajo heterogeneidad no acotada en escenarios descentralizados con participación parcial de clientes. Este artículo demuestra mediante análisis teórico de patrones de participación cíclica de clientes que el momentum inevitablemente se ve afectado por la heterogeneidad estadística. Además, los tamaños de paso decrecientes no ayudan: cualquier cronograma con decaimiento más rápido que Θ(1/t) resulta en convergencia a un valor constante que depende de la inicialización y del límite de heterogeneidad. Experimentos numéricos y de aprendizaje profundo validan la corrección de la teoría y su relevancia en escenarios prácticos.

Antecedentes de Investigación y Motivación

Problema Central

El problema central que este artículo aborda es: ¿Pueden los métodos clásicos de momentum garantizar convergencia bajo heterogeneidad no acotada en escenarios de aprendizaje descentralizado con participación parcial de clientes?

Importancia del Problema

Necesidades prácticas del aprendizaje federado: Las aplicaciones modernas de aprendizaje profundo requieren entrenamiento en islas de datos distribuidos o dispositivos personales, donde los clientes típicamente no pueden participar en cada ronda (debido a fallos de red, restricciones de privacidad o indisponibilidad temporal)
Desafío de heterogeneidad estadística: La naturaleza no independiente e idénticamente distribuida (non-IID) de los datos de clientes causa desviación de clientes (client drift) y actualizaciones sesgadas del servidor
Comprensión teórica insuficiente: Aunque el momentum se aplica ampliamente en algoritmos distribuidos, la comprensión teórica de sus propiedades en entornos descentralizados sigue siendo incompleta

Limitaciones de Métodos Existentes

Algoritmos federados basados en momentum como FedAvgM y FedCM funcionan bien en la práctica pero carecen de garantías teóricas bajo participación parcial
Resultados teóricos previos:
- 8 Demuestra que con participación completa el momentum puede converger bajo heterogeneidad no acotada
- 9 El GHBM propuesto logra garantías similares bajo participación parcial cíclica
- Pero las propiedades teóricas del momentum clásico bajo participación parcial permanecen sin clarificar

Motivación de la Investigación

Mediante análisis teórico riguroso, clarificar las limitaciones fundamentales de los métodos de momentum clásicos para proporcionar orientación teórica en el diseño de algoritmos de aprendizaje federado.

Contribuciones Principales

Las contribuciones principales de este artículo incluyen:

Demostración teórica de que el momentum no puede eliminar efectos de heterogeneidad: Bajo muestreo cíclico de clientes, se demuestra formalmente que el momentum no puede eliminar los efectos de la heterogeneidad de datos, el problema central en aprendizaje descentralizado y federado
Resultados negativos para tamaños de paso decrecientes: Se demuestra que cualquier cronograma de tamaño de paso con decaimiento más rápido que Θ(1/t) resulta en convergencia a un valor constante que depende de la inicialización y del límite de heterogeneidad, en lugar de la solución óptima
Marco de análisis sistemático: Mediante modelado de la dinámica del algoritmo como un sistema lineal de tiempo discreto, se proporciona una descomposición clara:
- Respuesta de entrada cero (zero-input response) captura el objetivo compartido por todos los clientes
- Respuesta de estado cero (zero-state response) aísla el objetivo de heterogeneidad
Validación experimental: Mediante experimentos numéricos del problema teórico y experimentos de aprendizaje profundo (CIFAR-10) se validan los hallazgos teóricos en escenarios prácticos

Explicación Detallada del Método

Definición de la Tarea

Considérese un sistema de aprendizaje distribuido donde el conjunto de clientes S colaboran para resolver un problema de aprendizaje, formalizado como un problema de optimización de suma finita:

$\theta^* = \arg\min_{\theta \in \mathbb{R}^d} \left[ f(\theta) := \frac{1}{|S|} \sum_{i \in S} f_i(\theta) \right]$

Donde:

$f_i(\theta)$ es la función objetivo local del cliente $i$
$f(\theta)$ es la función objetivo global
En cada ronda $t$ , solo un subconjunto $S_t \subset S$ de clientes participa (participación parcial)

Marco de Análisis Teórico

1. Construcción del Problema de Heterogeneidad Más Simple

Para analizar el comportamiento del momentum bajo heterogeneidad, se construyó el escenario más simple y favorable para el momentum:

Dos clientes: $f_1(\theta) = \frac{\mu}{2}\theta^2 + G\theta$ , $f_2(\theta) = \frac{\mu}{2}\theta^2 - G\theta$
Muestreo cíclico: Se selecciona alternadamente un cliente en cada ronda
Objetivo global: $f(\theta) = \frac{1}{2}(f_1(\theta) + f_2(\theta)) = \frac{\mu}{2}\theta^2$ , con solución óptima $\theta^* = 0$

Esta configuración satisface:

Convexidad fuerte con parámetro $\mu$ (Supuesto III.1)
Diferencia de gradientes acotada: $\frac{1}{|S|}\sum_{i=1}^{|S|} \|\nabla f_i(\theta) - \nabla f(\theta)\| \leq G$ (Supuesto III.2)
Participación cíclica (Supuesto III.3)

2. Modelado como Sistema Lineal de Tiempo Discreto (Lema III.4)

Se modelan las reglas de actualización de FedAvgM y FedCM como un sistema lineal de tiempo discreto:

undefined