Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

DOI10.1109/TAC.2011.2161027zbMATH Open1369.90156arXiv1005.2012OpenAlexW3101665129MaRDI QIDQ5352733FDOQ5352733

Authors: John C. Duchi, Alekh Agarwal, Martin J. Wainwright 

Publication date: 8 September 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. It arises in various application domains, including distributed tracking and localization, multi-agent co-ordination, estimation in sensor networks, and large-scale optimization in machine learning. We develop and analyze distributed algorithms based on dual averaging of subgradients, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our method of analysis allows for a clear separation between the convergence of the optimization algorithm itself and the effects of communication constraints arising from the network structure. In particular, we show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network. The sharpness of this prediction is confirmed both by theoretical lower bounds and simulations for various networks. Our approach includes both the cases of deterministic optimization and communication, as well as problems with stochastic optimization and/or communication.

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

Recommendations

• Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization
• A dual approach for optimal algorithms in distributed optimization over networks
• Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
• Optimal convergence rates for convex distributed optimization in networks
• Dual Averaging Push for Distributed Convex Optimization Over Time-Varying Directed Graph
• Distributed delayed dual averaging for distributed optimization over time-varying digraphs
• Distributed optimization over networks
• Inexact dual averaging method for distributed multi-agent optimization
• Accelerated Distributed Dual Averaging Over Evolving Networks of Growing Connectivity
• Dual averaging with adaptive random projection for solving evolving distributed optimization problems

Mathematics Subject Classification ID

Convex programming (90C25) Multi-objective and goal programming (90C29) Programming involving graphs or networks (90C35) Distributed algorithms (68W15)

Cited In (only showing first 100 items - show all)

• Surplus-based accelerated algorithms for distributed optimization over directed networks
• Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
• Graph-dependent implicit regularisation for distributed stochastic subgradient descent
• Communication-efficient distributed estimation for high-dimensional large-scale linear regression
• Differentially private distributed optimization for multi-agent systems via the augmented Lagrangian algorithm
• Distributed multi-step subgradient projection algorithm with adaptive event-triggering protocols: a framework of multiagent systems
• Distributed constraint-coupled optimization via primal decomposition over random time-varying graphs
• GADMM: fast and communication efficient framework for distributed machine learning
• Communication-Efficient Distributed Eigenspace Estimation
• A differentially private distributed optimization method for constrained optimization
• Communication-computation tradeoff in distributed consensus optimization for MPC-based coordinated control under wireless communications
• Convergence of distributed gradient-tracking-based optimization algorithms with random graphs
• Event-triggered zero-gradient-sum distributed convex optimisation over networks with time-varying topologies
• Decentralized consensus algorithm with delayed and stochastic gradients
• Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate.
• Distributed stochastic gradient tracking methods
• Distributed Saddle-Point Subgradient Algorithms With Laplacian Averaging
• Adaptive backstepping for distributed optimization
• Asymptotic properties of primal-dual algorithm for distributed stochastic optimization over random networks with imperfect communications
• Multi-cluster distributed optimization via random sleep strategy
• Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization
• Distributed linear regression by averaging
• Distributed multi-UAV trajectory optimization over directed networks
• Mass-spring-damper networks for distributed optimization in non-Euclidean spaces
• Global convergence rate of proximal incremental aggregated gradient methods
• Distributed model predictive control for linear systems under communication noise: algorithm, theory and implementation
• Cluster-based distributed augmented Lagrangian algorithm for a class of constrained convex optimization problems
• Subgradient averaging for multi-agent optimisation with different constraint sets
• Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
• Relative tempo of distributed averaging on networks
• Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization
• A dual approach for optimal algorithms in distributed optimization over networks
• A unitary distributed subgradient method for multi-agent optimization with different coupling sources
• Distributed optimization for degenerate loss functions arising from over-parameterization
• A distributed continuous-time modified Newton-Raphson algorithm
• Cooperative convex optimization with subgradient delays using push-sum distributed dual averaging
• Distributed optimization of multi-integrator agent systems with mixed neighbor interactions
• Tracking-ADMM for distributed constraint-coupled optimization
• Regularized dual gradient distributed method for constrained convex optimization over unbalanced directed graphs
• Noise-to-state exponentially stable distributed convex optimization on weight-balanced digraphs
• Distributed convex optimisation with event-triggered communication in networked systems
• Composite optimization for the resource allocation problem
• Distributed nonsmooth convex optimization over Markovian switching random networks with two step-sizes
• Distributed average tracking for uncertain directed multiagent networks
• A multi-scale method for distributed convex optimization with constraints
• Incremental gradient-free method for nonsmooth distributed optimization
• Parallel subgradient algorithm with block dual decomposition for large-scale optimization
• Generalized Nash equilibrium seeking algorithm design for distributed multi-cluster games
• On arbitrary compression for decentralized consensus and stochastic optimization over directed networks
• Prescribed-time distributed optimization for time-varying objective functions: a perspective from time-domain transformation
• An Optimal Algorithm for Decentralized Finite-Sum Optimization
• Distributed convex optimization with coupling constraints over time-varying directed graphs
• Primal recovery from consensus-based dual decomposition for distributed convex optimization
• An adaptive online learning algorithm for distributed convex optimization with coupled constraints over unbalanced directed graphs
• Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems
• Asynchronous gossip-based gradient-free method for multiagent optimization
• Online learning over a decentralized network through ADMM
• Optimal control of discrete‐time nonlinear heterogeneous multi‐agent systems via a distributed DISOPE algorithm
• Communication-efficient algorithms for decentralized and stochastic optimization
• A distributed conjugate gradient online learning method over networks
• A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW)
• Decentralized gradient algorithm for solution of a linear equation
• Distributed quasi-monotone subgradient algorithm for nonsmooth convex optimization over directed graphs
• Distributed optimization over directed graphs with row stochasticity and constraint regularity
• Network-decentralised optimisation and control: an explicit saturated solution
• Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method
• Linear time average consensus and distributed optimization on fixed graphs
• Decentralized multi-agent optimization based on a penalty method
• Distributed constrained optimization for multi-agent systems over a directed graph with piecewise stepsize
• Distributed subgradient method for multi-agent optimization with quantized communication
• Fast inexact decomposition algorithms for large-scale separable convex optimization
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• Communication-efficient distributed statistical inference
• Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks
• Distributed multi-agent optimization with state-dependent communication
• Event-triggered zero-gradient-sum distributed consensus optimization over directed networks
• Distributed coordination for nonsmooth convex optimization via saddle-point dynamics
• Distributed proximal-gradient method for convex optimization with inequality constraints
• Reprint of ``A distributed algorithm for efficiently solving linear equations and its applications (Special issue JCW)
• Dual averaging with adaptive random projection for solving evolving distributed optimization problems
• Path-following gradient-based decomposition algorithms for separable convex optimization
• Consensus-based modeling using distributed feature construction with ILP
• Distributed multi-task classification: a decentralized online learning approach
• Gradient-free method for nonsmooth distributed optimization
• A decentralized multi-objective optimization algorithm
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• Inexact dual averaging method for distributed multi-agent optimization
• Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators With Massive Data
• Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication
• On stochastic mirror descent with interacting particles: convergence properties and variance reduction
• Distributed solver for linear matrix inequalities: an optimization perspective
• Stochastic mirror descent method for distributed multi-agent optimization
• Distributed online bandit optimization under random quantization
• Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme
• On the convergence of decentralized gradient descent
• Distributed optimal in-network resource allocation algorithm design via a control theoretic approach
• On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints
• A distributed fixed-time optimization algorithm for multi-agent systems

This page was built for publication: Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

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