Optimal algorithms for smooth and strongly convex distributed optimization in networks

Abstract

In this paper, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized and decentralized communications over a network. For centralized (i.e. master/slave) algorithms, we show that distributing Nesterov's accelerated gradient descent is optimal and achieves a precision $\epsilon >0$ in time $O(\sqrt{{\kappa }_g}(1+\Delta \tau )\ln (1/\epsilon ))$, where ${\kappa }_g$ is the condition number of the (global) function to optimize, $\Delta$ is the diameter of the network, and $\tau$ (resp. $1$) is the time needed to communicate values between two neighbors (resp. perform local computations). For decentralized algorithms based on gossip, we provide the first optimal algorithm, called the multi-step dual accelerated (MSDA) method, that achieves a precision $\epsilon >0$ in time $O(\sqrt{{\kappa }_l}(1+\frac{\tau }{\sqrt{\gamma }})\ln (1/\epsilon ))$, where ${\kappa }_l$ is the condition number of the local functions and $\gamma$ is the (normalized) eigengap of the gossip matrix used for communication between nodes. We then verify the efficiency of MSDA against state-of-the-art methods for two problems: least-squares regression and classification by logistic regression.

18 pages (v2: fixed mathematical expressions in the abstract)

References in corpus (2)

• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs

Cited by in corpus (95)

• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Multi-consensus Decentralized Accelerated Gradient Descent
• Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• Decentralized Deep Learning with Arbitrary Communication Compression
• On the Complexity of Approximating Wasserstein Barycenter
• Improved Convergence Rates for Distributed Resource Allocation
• Recent theoretical advances in decentralized distributed convex optimization
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• Optimal Algorithms for Distributed Optimization
• Consensus Control for Decentralized Deep Learning
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
• Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
• Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
• A Push-Pull Gradient Method for Distributed Optimization in Networks
• Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms
• Communication trade-offs for synchronized distributed SGD with large step size
• Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
• Projected Gradient Method for Decentralized Optimization over Time-Varying Networks
• Distributed Stochastic Multi-Task Learning with Graph Regularization
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
• Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimization
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Distributed Proximal Splitting Algorithms with Rates and Acceleration
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• Distributed Saddle-Point Problems Under Similarity
• Straggler-Resilient Distributed Machine Learning with Dynamic Backup Workers
• Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• Robust and Communication-Efficient Collaborative Learning
• On Primal-Dual Approach for Distributed Stochastic Convex Optimization over Networks
• Acceleration in Distributed Optimization under Similarity
• Revisiting EXTRA for Smooth Distributed Optimization
• Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
• On stochastic mirror descent with interacting particles: convergence properties and variance reduction
• A Distributed Optimization Algorithm over Time-Varying Graphs with Efficient Gradient Evaluations
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• A Survey of Distributed Optimization Methods for Multi-Robot Systems
• Dual-Free Stochastic Decentralized Optimization with Variance Reduction
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization
• PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction
• The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
• On Consensus-Optimality Trade-offs in Collaborative Deep Learning
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
• Decentralized Composite Optimization with Compression
• Differentially Private Distributed Computation via Public-Private Communication Networks
• Adaptive Serverless Learning
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Distributed Zeroth-Order Stochastic Optimization in Time-varying Networks
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• Accelerating Gossip SGD with Periodic Global Averaging
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
• An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• A general framework for decentralized optimization with first-order methods
• Asynchrony and Acceleration in Gossip Algorithms
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs
• Optimal Complexity in Decentralized Training
• A Unified Contraction Analysis of a Class of Distributed Algorithms for Composite Optimization
• Decentralized Learning with Lazy and Approximate Dual Gradients
• On linear convergence of two decentralized algorithms
• Optimal Gradient Tracking for Decentralized Optimization
• Parallel and Distributed algorithms for ML problems
• Towards Tight Communication Lower Bounds for Distributed Optimisation
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
• A Chebyshev-Accelerated Primal-Dual Method for Distributed Optimization
• Decentralized Feature-Distributed Optimization for Generalized Linear Models
• ${\text{A}}^2{\text{CiD}}^2$: Accelerating Asynchronous Communication in Decentralized Deep Learning
• Newton Method over Networks is Fast up to the Statistical Precision
• Achieving Acceleration in Distributed Optimization via Direct Discretization of the Heavy-Ball ODE