On The Impact of Client Sampling on Federated Learning Convergence - 3IA Côte d’Azur – Interdisciplinary Institute for Artificial Intelligence Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

On The Impact of Client Sampling on Federated Learning Convergence

Résumé

While clients' sampling is a central operation of current state-of-the-art federated learning (FL) approaches, the impact of this procedure on the convergence and speed of FL remains under-investigated. In this work we introduce a novel decomposition theorem for the convergence of FL, allowing to clearly quantify the impact of client sampling on the global model update. Contrarily to previous convergence analyses, our theorem provides the exact decomposition of a given convergence step, thus enabling accurate considerations about the role of client sampling and heterogeneity. First, we provide a theoretical ground for previously reported experimental results on the relationship between FL convergence and the variance of the aggregation weights. Second, we prove for the first time that the quality of FL convergence is also impacted by the resulting covariance between aggregation weights. Our theory is general, and is here applied to Multinomial Distribution (MD) and Uniform sampling, the two default client sampling schemes of FL, and demonstrated through a series of experiments in non-iid and unbalanced scenarios. Our results suggest that MD sampling should be used as default sampling scheme, due to the resilience to the changes in data ratio during the learning process, while Uniform sampling is superior only in the special case when clients have the same amount of data.
Fichier principal
Vignette du fichier
On_The_Impact.pdf (931.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03500307 , version 1 (22-12-2021)
hal-03500307 , version 2 (12-07-2022)

Identifiants

  • HAL Id : hal-03500307 , version 1

Citer

Yann Fraboni, Richard Vidal, Laetitia Kameni, Marco Lorenzi. On The Impact of Client Sampling on Federated Learning Convergence. 2021. ⟨hal-03500307v1⟩
197 Consultations
228 Téléchargements

Partager

Gmail Facebook X LinkedIn More