Can 5th Generation Local Training Methods Support Client Sampling? Yes!

Michał Grudzien, Grigory Malinovsky, Peter Richtárik

Research output: Contribution to conferencePaperpeer-review

Abstract

The celebrated FedAvg algorithm of McMahan et al. (2017) is based on three components: client sampling (CS), data sampling (DS) and local training (LT). While the first two are reasonably well understood, the third component, whose role is to reduce the number of communication rounds needed to train the model, resisted all attempts at a satisfactory theoretical explanation. Malinovsky et al. (2022) identified four distinct generations of LT methods based on the quality of the provided theoretical communication complexity guarantees. Despite a lot of progress in this area, none of the existing works were able to show that it is theoretically better to employ multiple local gradient-type steps (i.e., to engage in LT) than to rely on a single local gradient-type step only in the important heterogeneous data regime. In a recent breakthrough embodied in their ProxSkip method and its theoretical analysis, Mishchenko et al. (2022) showed that LT indeed leads to provable communication acceleration for arbitrarily heterogeneous data, thus jump-starting the 5th generation of LT methods. However, while these latest generation LT methods are compatible with DS, none of them support CS. We resolve this open problem in the affirmative. In order to do so, we had to base our algorithmic development on new algorithmic and theoretical foundations.

Original languageEnglish (US)
Pages1055-1092
Number of pages38
StatePublished - 2023
Event26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023 - Valencia, Spain
Duration: Apr 25 2023Apr 27 2023

Conference

Conference26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023
Country/TerritorySpain
CityValencia
Period04/25/2304/27/23

Bibliographical note

Publisher Copyright:
Copyright © 2023 by the author(s)

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Can 5th Generation Local Training Methods Support Client Sampling? Yes!'. Together they form a unique fingerprint.

Cite this