Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with an Inexact Prox
Dec 6, 2022
Speakers
Abdurakhmon Sadiev
Speaker · 0 followers
Dmitry Kovalev
Speaker · 0 followers
Peter Richtárik
Speaker · 0 followers
About
Inspired by a recent breakthrough of Mishchenko et al. [2022], who for the first time showed that local gradient steps can lead to provable communication acceleration, we propose an alternative algorithm which obtains the same communication acceleration as their method (ProxSkip). Our approach is very different, however: it is based on the celebrated method of Chambolle and Pock [2011], with several nontrivial modifications: i) we allow for an inexact computation of the prox operator of a certain smooth strongly convex function via a suitable gradient-based method (e.g., GD or Fast GD), ii) we perform a careful modification of the dual update step in order to retain linear convergence. Our general results offer the new state-of-the-art rates for the class of strongly convex-concave saddle-point problems with bilinear coupling characterized by the absence of smoothness in the dual function. When applied to federated learning, we obtain a theoretically better alternative to ProxSkip: our method requires fewer local steps (𝒪(κ^1/3) or 𝒪(κ^1/4), compared to 𝒪(κ^1/2) of ProxSkip), and performs a deterministic number of local steps instead. Like ProxSkip, our method can be applied to optimization over a connected network, and we obtain theoretical improvements here as well.Inspired by a recent breakthrough of Mishchenko et al. [2022], who for the first time showed that local gradient steps can lead to provable communication acceleration, we propose an alternative algorithm which obtains the same communication acceleration as their method (ProxSkip). Our approach is very different, however: it is based on the celebrated method of Chambolle and Pock [2011], with several nontrivial modifications: i) we allow for an inexact computation of the prox operator of a certai…
Organizer
NeurIPS 2022
Account · 954 followers
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
Understanding A Class of Decentralized and Federated Optimization Algorithms: A Multi-Rate Feedback Control Perspective
Watch later
Xinwei Zhang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Multi-Modal Conditional GAN: Data Synthesis in the Medical Domain
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Deterministically Constrained Stochastic Optimization
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A gradient sampling method with complexity guarantees for Lipschitz functions in low and high dimensions
Watch later
Damek Davis, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Towards Modeling Complete Potentials in Crystal Materials
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
CEBaB: Estimating the Causal Effects of Real-World Concepts on NLP Model Behavior
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%