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
• Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods
• 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
• Communication-Efficient Distributed Eigenspace Estimation
• Title not available (Why is that?)
• 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
• Distributed stochastic gradient tracking methods
• Distributed Saddle-Point Subgradient Algorithms With Laplacian Averaging
• Adaptive backstepping for distributed optimization
• 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
• 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
• Relative tempo of distributed averaging on networks
• Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization
• Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent
• 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
• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
• 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
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
• Parallel subgradient algorithm with block dual decomposition for large-scale optimization
• Generalized Nash equilibrium seeking algorithm design for distributed multi-cluster games
• Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization over Random Networks with Imperfect Communications
• Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate
• 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
• An accelerated exact distributed first-order algorithm for optimization over directed networks
• Distributed adaptive online learning for convex optimization with weight decay
• Linear convergence of distributed estimation with constraints and communication delays
• Networked Parallel Algorithms for Robust Convex Optimization via the Scenario Approach
• Consensus-based distributed optimisation of multi-agent networks via a two level subgradient-proximal algorithm
• Distributed optimization with inexact oracle
• Stochastic mirror descent for convex optimization with consensus constraints
• Distributed mirror descent algorithm over unbalanced digraphs based on gradient weighting technique
• Distributed optimal frequency control under communication packet loss in multi-agent electric energy systems
• Online distributed dual averaging algorithm for multi-agent bandit optimization over time-varying general directed networks
• Distributed multi-agent optimisation via coordination with second-order nearest neighbours
• Distributed finite-time optimisation algorithm for second-order multi-agent systems subject to mismatched disturbances
• Distributed one-pass online AUC maximization
• Localization and approximations for distributed non-convex optimization
• Golden ratio proximal gradient ADMM for distributed composite convex optimization
• A communication-efficient method for ℓ₀ regularization linear regression models
• Distributed primal-dual optimisation method with uncoordinated time-varying step-sizes
• Distributed projection‐free algorithm for constrained aggregative optimization
• A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
• Continuous-Time Convergence Rates in Potential and Monotone Games
• Distributed Optimization Over Weight-Balanced Digraphs with Event-Triggered Communication
• Synchronous distributed ADMM for consensus convex optimization problems with self-loops
• Differentially private distributed online learning over time‐varying digraphs via dual averaging
• Distributed dual subgradient methods with averaging and applications to grid optimization
• Distributed dual averaging algorithm for multi-agent optimization with coupled constraints.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays
• Distributed Bregman-Distance Algorithms for Min-Max Optimization
• On the geometric convergence of Byzantine-resilient distributed optimization algorithms
• Who started this rumor? Quantifying the natural differential privacy of gossip protocols
• Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
• Distributed zeroth-order optimization: convergence rates that match centralized counterpart
• Confidence region for distributed stochastic optimization problem via stochastic gradient tracking method
• Distributed constrained optimization with periodic dynamic quantization
• Momentum-based distributed gradient tracking algorithms for distributed aggregative optimization over unbalanced directed graphs
• Distributed delayed dual averaging for distributed optimization over time-varying digraphs
• Event-triggered zero-gradient-sum distributed optimisation algorithm with time-varying communication delays
• Distributed optimization under edge agreements: a continuous-time algorithm
• 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)

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)