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

Sur les Limites de la Quantité de Mouvement dans l'Optimisation Décentralisée et Fédérée

Informations Fondamentales

ID de l'article : 2511.20168
Titre : On the Limits of Momentum in Decentralized and Federated Optimization
Auteurs : Riccardo Zaccone (Polytechnique de Turin), Sai Praneeth Karimireddy (USC), Carlo Masone (Polytechnique de Turin)
Classification : cs.LG (Apprentissage Automatique), cs.AI
Date de Publication : Novembre 2025 (prépublication arXiv)
Lien de l'article : https://arxiv.org/abs/2511.20168

Résumé

Cet article explore en profondeur les limitations théoriques de la quantité de mouvement (momentum) dans l'apprentissage fédéré et l'optimisation décentralisée. Bien que des recherches récentes aient exploré l'utilisation de la quantité de mouvement dans les méthodes locales pour améliorer la SGD distribuée, en particulier dans l'apprentissage fédéré pour atténuer les effets de l'hétérogénéité statistique, il reste peu clair si la quantité de mouvement peut garantir la convergence sous une hétérogénéité non bornée dans les scénarios décentralisés avec participation partielle des clients. Cet article démontre par analyse théorique de motifs de participation cyclique des clients que la quantité de mouvement est inévitablement affectée par l'hétérogénéité statistique. De plus, les tailles de pas décroissantes ne sont d'aucune aide : tout calendrier de décroissance plus rapide que Θ(1/t) entraîne une convergence vers une constante dépendant de l'initialisation et de la limite d'hétérogénéité. Des expériences numériques et d'apprentissage profond valident la justesse de la théorie et sa pertinence dans les scénarios pratiques.

Contexte et Motivation de la Recherche

Problème Central

Le problème central que cet article aborde est : Dans les scénarios d'apprentissage décentralisé avec participation partielle des clients, les méthodes classiques de quantité de mouvement peuvent-elles garantir la convergence sous des conditions d'hétérogénéité non bornée ?

Importance du Problème

Besoins pratiques de l'apprentissage fédéré : Les applications modernes d'apprentissage profond nécessitent un entraînement sur des îlots de données distribuées ou des appareils personnels, où les clients ne peuvent généralement pas participer à chaque tour (en raison de défaillances réseau, de restrictions de confidentialité ou d'indisponibilité temporaire)
Défi de l'hétérogénéité statistique : La nature non-identiquement distribuée (non-IID) des données des clients entraîne une dérive des clients (client drift) et des mises à jour de serveur biaisées
Compréhension théorique insuffisante : Bien que la quantité de mouvement soit largement appliquée aux algorithmes distribués, sa compréhension théorique dans les environnements décentralisés reste incomplète

Limitations des Approches Existantes

Algorithmes d'apprentissage fédéré basés sur la quantité de mouvement tels que FedAvgM et FedCM fonctionnent bien en pratique, mais manquent de garanties théoriques sous participation partielle
Résultats théoriques existants :
- 8 prouve que la quantité de mouvement peut converger sous hétérogénéité non bornée avec participation complète
- 9 propose GHBM qui réalise des garanties similaires sous participation partielle cyclique
- Mais les propriétés théoriques de la quantité de mouvement classique sous participation partielle restent peu claires

Motivation de la Recherche

Par une analyse théorique rigoureuse, clarifier les limitations fondamentales des méthodes classiques de quantité de mouvement, fournissant des orientations théoriques pour la conception d'algorithmes d'apprentissage fédéré.

Contributions Principales

L'article apporte les contributions majeures suivantes :

Preuve théorique que la quantité de mouvement ne peut pas éliminer les effets de l'hétérogénéité : Sous l'échantillonnage cyclique des clients, démonstration formelle que la quantité de mouvement ne peut pas éliminer les effets de l'hétérogénéité des données — un problème central dans l'apprentissage distribué et fédéré
Résultats négatifs sur les tailles de pas décroissantes : Preuve que tout calendrier de décroissance de taille de pas plus rapide que Θ(1/t) entraîne une convergence vers une constante dépendant de l'initialisation et de la limite d'hétérogénéité, plutôt que vers la solution optimale
Cadre d'analyse systématique : Par la modélisation de la dynamique de l'algorithme comme un système linéaire en temps discret, fourniture d'une décomposition claire :
- Réponse à entrée nulle (zero-input response) capture tous les objectifs partagés par les clients
- Réponse à état nul (zero-state response) isole les objectifs d'hétérogénéité
Validation expérimentale : Validation par expériences numériques sur les problèmes théoriques et expériences d'apprentissage profond (CIFAR-10) de la pertinence des résultats théoriques dans les scénarios pratiques

Détails de la Méthode

Définition de la Tâche

Considérez un système d'apprentissage distribué où un ensemble de clients S collaborent pour résoudre un problème d'apprentissage, formalisé comme un problème d'optimisation de somme finie :

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

où :

$f_i(\theta)$ est la fonction objectif locale du client $i$
$f(\theta)$ est la fonction objectif globale
À chaque tour $t$ , seul un sous-ensemble $S_t \subset S$ de clients participe (participation partielle)

Cadre d'Analyse Théorique

1. Construction du Problème d'Hétérogénéité Minimal

Pour analyser le comportement de la quantité de mouvement sous hétérogénéité, un scénario minimal le plus favorable à la quantité de mouvement est construit :

Deux clients : $f_1(\theta) = \frac{\mu}{2}\theta^2 + G\theta$ , $f_2(\theta) = \frac{\mu}{2}\theta^2 - G\theta$
Échantillonnage cyclique : Sélection alternée d'un client à chaque tour
Objectif global : $f(\theta) = \frac{1}{2}(f_1(\theta) + f_2(\theta)) = \frac{\mu}{2}\theta^2$ , solution optimale $\theta^* = 0$

Cette configuration satisfait :

Forte convexité $\mu$ (Hypothèse III.1)
Différence de gradient bornée : $\frac{1}{|S|}\sum_{i=1}^{|S|} \|\nabla f_i(\theta) - \nabla f(\theta)\| \leq G$ (Hypothèse III.2)
Participation cyclique (Hypothèse III.3)

2. Modélisation du Système Linéaire en Temps Discret (Lemme III.4)

Les règles de mise à jour de FedAvgM et FedCM sont modélisées comme un système linéaire en temps discret :

undefined