Recent theoretical advances in decentralized distributed convex optimization

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 (75)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Harnessing Smoothness to Accelerate Distributed Optimization
• Derivative-free optimization methods
• Local SGD Converges Fast and Communicates Little
• Distributed Random Projection Algorithm for Convex Optimization
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Accelerated Distributed Nesterov Gradient Descent
• A Universal Catalyst for First-Order Optimization
• Distributionally Robust Logistic Regression
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Distributed Learning with Compressed Gradient Differences
• Parametric estimation. Finite sample theory
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Natural Compression for Distributed Deep Learning
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• On Biased Compression for Distributed Learning
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• Is Local SGD Better than Minibatch SGD?
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• SGD: General Analysis and Improved Rates
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Multi-consensus Decentralized Accelerated Gradient Descent
• Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
• Linearly Converging Error Compensated SGD
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• Direct Acceleration of SAGA using Sampled Negative Momentum
• On the Complexity of Approximating Wasserstein Barycenter
• Algorithms for stochastic optimization with functional or expectation constraints
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Optimal Algorithms for Distributed Optimization
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
• Universal gradient descent
• Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
• Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimization
• Projected Gradient Method for Decentralized Optimization over Time-Varying Networks
• The Complexity of Making the Gradient Small in Stochastic Convex Optimization
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• A Generic Acceleration Framework for Stochastic Composite Optimization
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
• Accelerated meta-algorithm for convex optimization
• Universal fast gradient method for stochastic composit optimization problems
• 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
• Gradient-free prox-methods with inexact oracle for stochastic convex optimization problems on a simplex
• Acceleration in Distributed Optimization under Similarity
• Revisiting EXTRA for Smooth Distributed Optimization
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization
• Improved Complexity Bounds in Wasserstein Barycenter Problem
• Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization
• Decentralized Algorithms for Wasserstein Barycenters
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• On the upper bound for the mathematical expectation of the norm of a vector uniformly distributed on the sphere and the phenomenon of concentration of uniform measure on the sphere
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
• On a Combination of Alternating Minimization and Nesterov's Momentum
• Distributed Optimization Over Dependent Random Networks
• Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation
• Towards Optimal Running Times for Optimal Transport
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• Gradient Sliding for Composite Optimization
• Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs
• Parallel and Distributed algorithms for ML problems
• Mirror-prox sliding methods for solving a class of monotone variational inequalities

Cited by in corpus (9)

• 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
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters
• 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