Timezone: »
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 Decentralized Stochastic Gradient Descent algorithm (D-SGD) under data heterogeneity. We first exhibit the key role played by a new quantity, called neighborhood heterogeneity, on the convergence rate of D-SGD. Neighborhood heterogeneity provides a natural criterion to learn data-dependent and sparse topologies that reduce the detrimental effect of data heterogeneity on the convergence of D-SGD. For the important case of classification with label skew, we formulate the problem of learning a topology as a tractable optimization problem that we solve with a Frank-Wolfe algorithm. As illustrated over a set of experiments, the learned sparse topology is showed to balance the convergence speed and the per-iteration communication costs of D-SGD.
Author Information
Batiste Le bars (Ecole Normale Superieure)
Aurélien Bellet (INRIA)
Marc Tommasi (INRIA)
Erick Lavoie
Anne-marie Kermarrec (School of Computer and Communication Sciences, EPFL - EPF Lausanne)
More from the Same Authors
-
2020 : Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties »
Aurélien Bellet -
2020 : Privacy Amplification by Decentralization »
Aurélien Bellet -
2022 : Fairness Certificates for Differentially Private Classification »
Paul Mangold · Michaël Perrot · Marc Tommasi · Aurélien Bellet -
2023 Poster: Epidemic Learning »
Martijn De Vos · Sadegh Farhadkhani · Rachid Guerraoui · Anne-marie Kermarrec · Rafael Pires · Rishi Sharma -
2022 Poster: FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settings »
Jean Ogier du Terrail · Samy-Safwan Ayed · Edwige Cyffers · Felix Grimberg · Chaoyang He · Regis Loeb · Paul Mangold · Tanguy Marchand · Othmane Marfoq · Erum Mushtaq · Boris Muzellec · Constantin Philippenko · Santiago Silva · Maria Teleńczuk · Shadi Albarqouni · Salman Avestimehr · Aurélien Bellet · Aymeric Dieuleveut · Martin Jaggi · Sai Praneeth Karimireddy · Marco Lorenzi · Giovanni Neglia · Marc Tommasi · Mathieu Andreux -
2022 Poster: Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging »
Edwige Cyffers · Mathieu Even · Aurélien Bellet · Laurent Massoulié -
2021 Poster: Federated Multi-Task Learning under a Mixture of Distributions »
Othmane Marfoq · Giovanni Neglia · Aurélien Bellet · Laetitia Kameni · Richard Vidal -
2020 Workshop: Privacy Preserving Machine Learning - PriML and PPML Joint Edition »
Borja Balle · James Bell · Aurélien Bellet · Kamalika Chaudhuri · Adria Gascon · Antti Honkela · Antti Koskela · Casey Meehan · Olga Ohrimenko · Mi Jung Park · Mariana Raykova · Mary Anne Smart · Yu-Xiang Wang · Adrian Weller -
2020 Session: Orals & Spotlights Track 10: Social/Privacy »
Yanan Sui · Aurélien Bellet -
2018 Workshop: Privacy Preserving Machine Learning »
Adria Gascon · Aurélien Bellet · Niki Kilbertus · Olga Ohrimenko · Mariana Raykova · Adrian Weller -
2018 : Aurélien Bellet »
Aurélien Bellet -
2017 : Personalized and Private Peer-to-Peer Machine Learning »
Aurélien Bellet · Rachid Guerraoui · Marc Tommasi -
2016 Workshop: Private Multi-Party Machine Learning »
Borja Balle · Aurélien Bellet · David Evans · Adrià Gascón -
2016 Poster: On Graph Reconstruction via Empirical Risk Minimization: Fast Learning Rates and Scalability »
Guillaume Papa · Aurélien Bellet · Stephan Clémençon -
2015 Poster: SGD Algorithms based on Incomplete U-statistics: Large-Scale Minimization of Empirical Risk »
Guillaume Papa · Stéphan Clémençon · Aurélien Bellet -
2015 Poster: Extending Gossip Algorithms to Distributed Estimation of U-statistics »
Igor Colin · Aurélien Bellet · Joseph Salmon · Stéphan Clémençon -
2015 Spotlight: Extending Gossip Algorithms to Distributed Estimation of U-statistics »
Igor Colin · Aurélien Bellet · Joseph Salmon · Stéphan Clémençon -
2012 Poster: Fiedler Random Fields: A Large-Scale Spectral Approach to Statistical Network Modeling »
Antonino Freno · Mikaela Keller · Marc Tommasi