Recent theoretical advances in decentralized distributed convex optimization
arXiv:2011.13259 · doi:10.1007/978-3-031-00832-0_8
Abstract
In the last few years, the theory of decentralized distributed convex optimization has made significant progress. The lower bounds on communications rounds and oracle calls have appeared, as well as methods that reach both of these bounds. In this paper, we focus on how these results can be explained based on optimal algorithms for the non-distributed setup. In particular, we provide our recent results that have not been published yet and that could be found in details only in arXiv preprints.
46 pages; a survey paper
References in corpus (24)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
- High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
- Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
- Linearly Converging Error Compensated SGD
- Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
- Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
- The Complexity of Making the Gradient Small in Stochastic Convex Optimization
- A Decentralized Proximal Point-type Method for Saddle Point Problems
- ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
- Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
- Distributed Saddle-Point Problems Under Similarity
- Local SGD: Unified Theory and New Efficient Methods
- Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks
- Acceleration in Distributed Optimization under Similarity
- Improved Complexity Bounds in Wasserstein Barycenter Problem
- Decentralized Algorithms for Wasserstein Barycenters
- Distributed Optimization Over Dependent Random Networks
- Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
- Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
- Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs
- Mirror-prox sliding methods for solving a class of monotone variational inequalities
- Parallel and Distributed algorithms for ML problems
Cited by in corpus (8)
- Randomized gradient-free methods in convex optimization
- ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
- Decentralized convex optimization over time-varying graphs: a survey
- About some works of Boris Polyak on convergence of gradient methods and their development
- Parallel and Distributed algorithms for ML problems
- Decentralized Feature-Distributed Optimization for Generalized Linear Models
- One-Point Feedback for Composite Optimization with Applications to Distributed and Federated Learning
- Newton Method over Networks is Fast up to the Statistical Precision