Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization

DOI10.1137/20M138956XMaRDI QIDQ6116247zbMATH OpenOpenAlexFDO

Authors Guanghui Lan, Yuyuan Ouyang, Yi Zhou

Publication date 11 August 2023

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.00143

zbMATH Keywords

communication complexitydecentralized optimizationgradient complexitygradient slidingmultiagent optimizationsaddle point problemssampling complexity

Mathematics Subject Classification ID

Numerical methods based on nonlinear programming (49M37) Large-scale problems in mathematical programming (90C06) Stochastic programming (90C15) Convex programming (90C25) Decentralized systems (93A14)

Abstract: One fundamental problem in decentralized multi-agent optimization is the trade-off between gradient/sampling complexity and communication complexity. We propose new algorithms whose gradient and sampling complexities are graph topology invariant while their communication complexities remain optimal. For convex smooth deterministic problems, we propose a primal dual sliding (PDS) algorithm that computes an $epsilon$-solution with $O((ildeL/epsilon{)}^{1/2})$ gradient and $O((ildeL/epsilon{)}^{1/2}+|mathcalA|/epsilon)$ communication complexities, where $ildeL$ is the smoothness parameter of the objective and $mathcalA$ is related to either the graph Laplacian or the transpose of the oriented incidence matrix of the communication network. The results can be improved to $O((ildeL/mu{)}^{1/2}log(1/epsilon))$ and $O((ildeL/mu{)}^{1/2}log(1/epsilon)+|mathcalA|/epsilo{n}^{1/2})$ respectively with $mu$-strong convexity. We also propose a stochastic variant, the primal dual sliding (SPDS) algorithm for problems with stochastic gradients. The SPDS algorithm utilizes the mini-batch technique and enables the agents to perform sampling and communication simultaneously. It computes a stochastic $epsilon$-solution with $O((ildeL/epsilon{)}^{1/2}+(sigma/epsilon{)}^2)$ sampling complexity, which can be improved to $O((ildeL/mu{)}^{1/2}log(1/epsilon)+sigm{a}^2/epsilon)$ with strong convexity. Here $sigm{a}^2$ is the variance. The communication complexities of SPDS remain the same as that of the deterministic case. All the aforementioned gradient and sampling complexities match the lower complexity bounds for centralized convex smooth optimization and are independent of the network structure. To the best of our knowledge, these gradient and sampling complexities have not been obtained before for decentralized optimization over a constraint feasible set.

Recommendations

• Communication-efficient algorithms for decentralized and stochastic optimization
• A randomized incremental primal-dual method for decentralized consensus optimization
• Optimal convergence rates for convex distributed optimization in networks
• Distributed stochastic gradient tracking methods
• Fast decentralized nonconvex finite-sum optimization with recursive variance reduction

Cites work

• A proximal stochastic gradient method with progressive variance reduction
• Accelerated gradient sliding for structured convex optimization
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• An optimal randomized incremental gradient method
• Communication-Censored ADMM for Decentralized Consensus Optimization
• Communication-efficient algorithms for decentralized and stochastic optimization
• Consensus-based distributed support vector machines
• Coordination of groups of mobile autonomous agents using nearest neighbor rules
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• Decentralized Learning With Lazy and Approximate Dual Gradients
• Decentralized Proximal Gradient Algorithms With Linear Convergence Rates
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization
• Distributed nonconvex constrained optimization over time-varying digraphs
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Distributed Optimization Over Time-Varying Directed Graphs
• Distributed Subgradient Methods for Multi-Agent Optimization
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Fast Convergence Rates for Distributed Non-Bayesian Learning
• Fastest Mixing Markov Chain on a Graph
• First-order and stochastic optimization methods for machine learning
• Gradient sliding for composite optimization
• Graph implementations for nonsmooth convex programs
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Non-Euclidean restricted memory level method for large-scale convex optimization
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
• Penalty-based method for decentralized optimization over time-varying graphs
• Revisiting EXTRA for Smooth Distributed Optimization
• Second-order guarantees of distributed gradient algorithms
• Smooth minimization of non-smooth functions
• Stochastic Proximal Gradient Consensus Over Random Networks

Cited in

(4)

• Communication-efficient algorithms for decentralized and stochastic optimization
• Optimal Methods for Convex Risk-Averse Distributed Optimization
• Decentralized Multi-Task Stochastic Optimization With Compressed Communications
• Optimal gradient tracking for decentralized optimization

This page was built for publication: Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116247)