posted on 2024-03-25, 14:02authored bySamuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Peter Richtárik, Sebastian StichSebastian Stich
We consider distributed optimization over several devices, each sending incremental model updates to a central server. This setting is considered, for instance, in federated learning. Various schemes have been designed to compress the model updates in order to reduce the overall communication cost. However, existing methods suffer from a significant slowdown due to additional variance ω>0
coming from the compression operator and as a result, only converge sublinearly. What is needed is a variance reduction technique for taming the variance introduced by compression. We propose the first methods that achieve linear convergence for arbitrary compression operators. For strongly convex functions with condition number κ, distributed among n machines with a finite-sum structure, each worker having less than m components, we also (i) give analysis for the weakly convex and the non-convex cases and (ii) verify in experiments that our novel variance reduced schemes are more efficient than the baselines. Moreover, we show theoretically that as the number of devices increases, higher compression levels are possible without this affecting the overall number of communications in comparison with methods that do not perform any compression. This leads to a significant reduction in communication cost. Our general analysis allows to pick the most suitable compression for each problem, finding the right balance between additional variance and communication savings. Finally, we also (iii) give analysis for arbitrary quantized updates.
History
Primary Research Area
Trustworthy Information Processing
Journal
Optimization Methods and Software
Volume
38
Page Range
91-106
Publisher
Taylor & Francis
Open Access Type
Green
Sub Type
Article
BibTeX
@article{Horváth:Kovalev:Mishchenko:Richtárik:Stich:2023,
title = "Stochastic distributed learning with gradient quantization and double-variance reduction",
author = "Horváth, Samuel" AND "Kovalev, Dmitry" AND "Mishchenko, Konstantin" AND "Richtárik, Peter" AND "Stich, Sebastian",
year = 2023,
month = 1,
journal = "Optimization Methods and Software",
number = "1",
pages = "91--106",
publisher = "Taylor & Francis",
issn = "1029-4937",
doi = "10.1080/10556788.2022.2117355"
}