Communication-efficient algorithms for decentralized and stochastic optimization

DOI10.1007/S10107-018-1355-4MaRDI QIDQ2297648zbMATH OpenOpenAlexWikidataFDO

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

communication efficientcomplexitydecentralized machine learningdecentralized optimizationnonsmooth functionsprimal-dual methodstochastic programming

Mathematics Subject Classification ID

Numerical methods based on nonlinear programming (49M37) Stochastic programming (90C15) Convex programming (90C25) 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

• A first-order primal-dual algorithm for convex problems with applications to imaging
• A Proximal Gradient Algorithm for Decentralized Composite Optimization
• 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
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Distributed asynchronous incremental subgradient methods
• Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Distributed Optimization Over Time-Varying Directed Graphs
• Distributed stochastic subgradient projection algorithms for convex optimization
• 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 Distributed Gradient Methods
• Gradient sliding for composite optimization
• Harnessing Smoothness to Accelerate Distributed Optimization
• 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?)
• 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 \(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 Convergence Rate of Incremental Aggregated Gradient Algorithms
• On the ergodic convergence rates of a first-order primal-dual algorithm
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Optimal primal-dual methods for a class of saddle point problems
• 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
• 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

(52)

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

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)