Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data

Bars, Batiste Le; Bellet, Aurelien; Tommasi, Marc; Lavoie, Erick; Kermarrec, Anne-Marie

Type de document :

Pré-publication ou Document de travail

Titre :

Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data

Auteur(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]

Discipline(s) HAL :

Informatique [cs]/Apprentissage [cs.LG]
Statistiques [stat]/Machine Learning [stat.ML]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Projet ANR :

Apprentissage automatique décentralisé et préservant la vie privée

Collections :