Refined Convergence and Topology Learning ...
Document type :
Communication dans un congrès avec actes
Title :
Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data
Author(s) :
Bars, Batiste Le [Auteur]
Machine Learning in Information Networks [MAGNET]
Bellet, Aurelien [Auteur]
Machine Learning in Information Networks [MAGNET]
Tommasi, Marc [Auteur]
Machine Learning in Information Networks [MAGNET]
Lavoie, Erick [Auteur]
Ecole Polytechnique Fédérale de Lausanne [EPFL]
Kermarrec, Anne-Marie [Auteur]
Ecole Polytechnique Fédérale de Lausanne [EPFL]
Machine Learning in Information Networks [MAGNET]
Bellet, Aurelien [Auteur]

Machine Learning in Information Networks [MAGNET]
Tommasi, Marc [Auteur]

Machine Learning in Information Networks [MAGNET]
Lavoie, Erick [Auteur]
Ecole Polytechnique Fédérale de Lausanne [EPFL]
Kermarrec, Anne-Marie [Auteur]
Ecole Polytechnique Fédérale de Lausanne [EPFL]
Conference title :
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023)
City :
Valencia, Spain
Country :
Espagne
Start date of the conference :
2023
HAL domain(s) :
Informatique [cs]/Apprentissage [cs.LG]
Statistiques [stat]/Machine Learning [stat.ML]
Statistiques [stat]/Machine Learning [stat.ML]
English abstract : [en]
One of the key challenges in decentralized and federated learning is to design algorithms that efficiently deal with highly heterogeneous data distributions across agents. In this paper, we revisit the analysis of the ...
Show more >One of the key challenges in decentralized and federated learning is to design algorithms that efficiently deal with highly heterogeneous data distributions across agents. In this paper, we revisit the analysis of the popular Decentralized Stochastic Gradient Descent algorithm (D-SGD) under data heterogeneity. We exhibit the key role played by a new quantity, called neighborhood heterogeneity, on the convergence rate of D-SGD. By coupling the communication topology and the heterogeneity, our analysis sheds light on the poorly understood interplay between these two concepts. We then argue that neighborhood heterogeneity provides a natural criterion to learn data-dependent topologies that reduce (and can even eliminate) the otherwise detrimental effect of data heterogeneity on the convergence time of D-SGD. For the important case of classification with label skew, we formulate the problem of learning such a good topology as a tractable optimization problem that we solve with a Frank-Wolfe algorithm. As illustrated over a set of simulated and real-world experiments, our approach provides a principled way to design a sparse topology that balances the convergence speed and the per-iteration communication costs of D-SGD under data heterogeneity.Show less >
Show more >One of the key challenges in decentralized and federated learning is to design algorithms that efficiently deal with highly heterogeneous data distributions across agents. In this paper, we revisit the analysis of the popular Decentralized Stochastic Gradient Descent algorithm (D-SGD) under data heterogeneity. We exhibit the key role played by a new quantity, called neighborhood heterogeneity, on the convergence rate of D-SGD. By coupling the communication topology and the heterogeneity, our analysis sheds light on the poorly understood interplay between these two concepts. We then argue that neighborhood heterogeneity provides a natural criterion to learn data-dependent topologies that reduce (and can even eliminate) the otherwise detrimental effect of data heterogeneity on the convergence time of D-SGD. For the important case of classification with label skew, we formulate the problem of learning such a good topology as a tractable optimization problem that we solve with a Frank-Wolfe algorithm. As illustrated over a set of simulated and real-world experiments, our approach provides a principled way to design a sparse topology that balances the convergence speed and the per-iteration communication costs of D-SGD under data heterogeneity.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Files
- document
- Open access
- Access the document
- 2204.04452.pdf
- Open access
- Access the document
- 2204.04452
- Open access
- Access the document