Communication-efficient algorithms for decentralized and stochastic optimization

DOI10.1007/S10107-018-1355-4zbMATH Open1437.90125OpenAlexW2963855576WikidataQ128829704 ScholiaQ128829704MaRDI QIDQ2297648FDOQ2297648

Authors Yanyan Li

Publication date 20 February 2020

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

complexitystochastic programmingdecentralized optimizationprimal-dual methodnonsmooth functionscommunication efficientdecentralized machine learning

Mathematics Subject Classification ID

Convex programming (90C25) Numerical methods based on nonlinear programming (49M37) Stochastic programming (90C15) Decentralized systems (93A14)

Abstract: We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. We first propose a decentralized primal-dual method which can find an $epsilon$-solution both in terms of functional optimality gap and feasibility residual in $O(1/epsilon)$ inter-node communication rounds when the objective functions are convex and the local primal subproblems are solved exactly. Our major contribution is to present a new class of decentralized primal-dual type algorithms, namely the decentralized communication sliding (DCS) methods, which can skip the inter-node communications while agents solve the primal subproblems iteratively through linearizations of their local objective functions. By employing DCS, agents can still find an $epsilon$-solution in $O(1/epsilon)$ (resp., $O(1/sqrtepsilon)$) communication rounds for general convex functions (resp., strongly convex functions), while maintaining the $O(1/epsilo{n}^2)$ (resp., $O(1/epsilon)$) bound on the total number of intra-node subgradient evaluations. We also present a stochastic counterpart for these algorithms, denoted by SDCS, for solving stochastic optimization problems whose objective function cannot be evaluated exactly. In comparison with existing results for decentralized nonsmooth and stochastic optimization, we can reduce the total number of inter-node communication rounds by orders of magnitude while still maintaining the optimal complexity bounds on intra-node stochastic subgradient evaluations. The bounds on the subgradient evaluations are actually comparable to those required for centralized nonsmooth and stochastic optimization.

Recommendations

• Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
• A randomized incremental primal-dual method for decentralized consensus optimization
• Optimal convergence rates for convex distributed optimization in networks
• Decentralized online convex optimization with compressed communications
• On arbitrary compression for decentralized consensus and stochastic optimization over directed networks

Cites work

• scientific article; zbMATH DE number 3148887 (Why is no real title available?)
• scientific article; zbMATH DE number 3912096 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• A Proximal Gradient Algorithm for Decentralized Composite Optimization
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• An accelerated linearized alternating direction method of multipliers
• An optimal method for stochastic composite optimization
• An optimal randomized incremental gradient method
• Asynchronous Broadcast-Based Convex Optimization Over a Network
• Complexity of Variants of Tseng's Modified F-B Splitting and Korpelevich's Methods for Hemivariational Inequalities with Applications to Saddle-point and Convex Optimization Problems
• Convergence Rate of Distributed ADMM Over Networks
• Coordination of groups of mobile autonomous agents using nearest neighbor rules
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization
• Distributed Optimization Over Time-Varying Directed Graphs
• Distributed Subgradient Methods for Multi-Agent Optimization
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Distributed asynchronous incremental subgradient methods
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Distributed stochastic subgradient projection algorithms for convex optimization
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Fast Distributed Gradient Methods
• Gradient sliding for composite optimization
• Harnessing Smoothness to Accelerate Distributed Optimization
• Incremental proximal methods for large scale convex optimization
• Incremental stochastic subgradient algorithms for convex optimization
• Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• On Distributed Convex Optimization Under Inequality and Equality Constraints
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
• On the ergodic convergence rates of a first-order primal-dual algorithm
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Optimal primal-dual methods for a class of saddle point problems
• Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Robust Stochastic Approximation Approach to Stochastic Programming
• Stochastic Proximal Gradient Consensus Over Random Networks
• Validation analysis of mirror descent stochastic approximation method

Cited in

(43)

• Random gradient extrapolation for distributed and stochastic optimization
• On arbitrary compression for decentralized consensus and stochastic optimization over directed networks
• A review of decentralized optimization focused on information flows of decomposition algorithms
• Balancing Communication and Computation in Distributed Optimization
• Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
• Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
• The communication complexity for decentralized evaluation of functions
• Distributed multi-agent optimisation via coordination with second-order nearest neighbours
• DSA: decentralized double stochastic averaging gradient algorithm
• Balancing communication and computation in gradient tracking algorithms for decentralized optimization
• Decentralized Multi-Task Stochastic Optimization With Compressed Communications
• Distributed Sparse Composite Quantile Regression in Ultrahigh Dimensions
• Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
• More communication-efficient distributed sparse learning
• Optimal Methods for Convex Risk-Averse Distributed Optimization
• On the communication complexity of Lipschitzian optimization for the coordinated model of computation
• Adaptive consensus: a network pruning approach for decentralized optimization
• Decentralized optimization over tree graphs
• On the linear convergence of two decentralized algorithms
• Optimal gradient tracking for decentralized optimization
• Optimal convergence rates for convex distributed optimization in networks
• Decentralized multi-agent optimization based on a penalty method
• Distributed stochastic gradient tracking methods
• Operator splitting methods for decentralized optimization
• Decentralized ADMM with compressed and event-triggered communication
• Exact penalties for decomposable convex optimization problems
• Stochastic first-order methods for convex and nonconvex functional constrained optimization
• A dual approach for optimal algorithms in distributed optimization over networks
• Recent theoretical advances in decentralized distributed convex optimization
• Revisiting EXTRA for Smooth Distributed Optimization
• A randomized incremental primal-dual method for decentralized consensus optimization
• scientific article; zbMATH DE number 6982986 (Why is no real title available?)
• Decentralized online convex optimization with compressed communications
• Distributed Decoding From Heterogeneous 1-Bit Compressive Measurements
• Robust asynchronous stochastic gradient-push: asymptotically optimal and network-independent performance for strongly convex functions
• Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
• Communication-efficient and privacy-preserving large-scale federated learning counteracting heterogeneity
• Distributed aggregative optimization with quantized communication
• On the Divergence of Decentralized Nonconvex Optimization
• Distributed communication-sliding mirror-descent algorithm for nonsmooth resource allocation problem
• On decentralized nonsmooth optimization
• scientific article; zbMATH DE number 7307473 (Why is no real title available?)
• Incremental without replacement sampling in nonconvex optimization

This page was built for publication: Communication-efficient algorithms for decentralized and stochastic optimization

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