STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning
Dec 6, 2021
Speakers
Prashant Khanduri
Speaker · 0 followers
Pranay Sharma
Speaker · 0 followers
Haibo Yang
Speaker · 0 followers
Mingyi Hong
Speaker · 0 followers
Pramod Varshney
Speaker · 0 followers
About
Federated Learning (FL) refers to the paradigm where multiple worker nodes (WNs) build a joint model by using local data. Despite extensive research, for a generic non-convex FL problem, it is not clear, how to choose the WNs' and the server's update directions, the minibatch sizes, and the local update frequency, so that the WNs use the minimum number of samples and communication rounds to achieve the desired solution. This work addresses the above question and considers a class of stochastic algorithms where the WNs perform a few local updates before communication. We show that when both the WN's and the server's directions are chosen based on certain stochastic momentum estimator, the algorithm requires 𝒪̃(ϵ^-3/2) samples and 𝒪̃(ϵ^-1) communication rounds to compute an ϵ-stationary solution. To the best of our knowledge, this is the first FL algorithm that achieves such near-optimal sample and communication complexities simultaneously. Further, we show that there is a trade-off curve between local update frequencies and local minibatch sizes, on which the above sample and communication complexities can be maintained. Finally, we show that for the classical FedAvg (a.k.a. Local SGD, which is a momentum-less special case of the STEM), a similar trade-off curve exists, albeit with worse sample and communication complexities. Our insights on this trade-off provides guidelines for choosing the four important design elements for FL algorithms, the update frequency, directions, and minibatch sizes to achieve the best performance.Federated Learning (FL) refers to the paradigm where multiple worker nodes (WNs) build a joint model by using local data. Despite extensive research, for a generic non-convex FL problem, it is not clear, how to choose the WNs' and the server's update directions, the minibatch sizes, and the local update frequency, so that the WNs use the minimum number of samples and communication rounds to achieve the desired solution. This work addresses the above question and considers a class of stochastic a…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Zero Knowledge Arguments for Verifiable Sampling
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A Graph Perspective on Neural Network Dynamics
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Handling Long-tailed Feature Distribution in AdderNets
Watch later
Minjing Dong, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Advanced Topics in Model Predictive Control
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
On the Impossibility of Fairness-Aware Learning from Corrupted Data
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%