Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

DOI10.1109/TAC.2011.2161027zbMath1369.90156arXiv1005.2012OpenAlexW3101665129MaRDI QIDQ5352733

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)

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

Mathematics Subject Classification ID

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

Related Items

A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW), Stochastic mirror descent dynamics and their convergence in monotone variational inequalities, Distributed solver for linear matrix inequalities: an optimization perspective, Adaptive backstepping for distributed optimization, Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent, GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning, 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, Distributed multi-task classification: a decentralized online learning approach, Consensus-based modeling using distributed feature construction with ILP, Decentralized gradient algorithm for solution of a linear equation, Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization, Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems, Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization over Random Networks with Imperfect Communications, Large-scale multivariate sparse regression with applications to UK Biobank, Stochastic mirror descent method for distributed multi-agent optimization, A distributed conjugate gradient online learning method over networks, A unitary distributed subgradient method for multi-agent optimization with different coupling sources, 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 constraint-coupled optimization via primal decomposition over random time-varying graphs, Differentially private distributed optimization for multi-agent systems via the augmented Lagrangian algorithm, Incremental gradient-free method for nonsmooth distributed optimization, Exponential convergence of a distributed algorithm for solving linear algebraic equations, Convergence rate analysis of distributed optimization with projected subgradient algorithm, Distributed constrained optimization for multi-agent systems over a directed graph with piecewise stepsize, Regularized dual gradient distributed method for constrained convex optimization over unbalanced directed graphs, Distributed optimal in-network resource allocation algorithm design via a control theoretic approach, Tracking-ADMM for distributed constraint-coupled optimization, Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication, Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties, Generalized Nash equilibrium seeking algorithm design for distributed multi-cluster games, Multi-cluster distributed optimization via random sleep strategy, Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks, Linear Time Average Consensus and Distributed Optimization on Fixed Graphs, Distributed average tracking for uncertain directed multiagent networks, Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs, Event-triggered zero-gradient-sum distributed consensus optimization over directed networks, Distributed multi-agent optimization subject to nonidentical constraints and communication delays, Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization, A distributed fixed-time optimization algorithm for multi-agent systems, Distributed multi-agent optimization with state-dependent communication, Distributed subgradient method for multi-agent optimization with quantized communication, Distributed constrained optimization via continuous-time mirror design, Approximate dual averaging method for multiagent saddle-point problems with stochastic subgradients, Inexact dual averaging method for distributed multi-agent optimization, Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint, Asynchronous gossip-based gradient-free method for multiagent optimization, Networked Parallel Algorithms for Robust Convex Optimization via the Scenario Approach, Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme, Cooperative convex optimization with subgradient delays using push-sum distributed dual averaging, 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, Distributed consensus-based multi-agent convex optimization via gradient tracking technique, Distributed nonsmooth convex optimization over Markovian switching random networks with two step-sizes, Convergence of distributed gradient-tracking-based optimization algorithms with random graphs, Decentralized Consensus Algorithm with Delayed and Stochastic Gradients, Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods, Distributed convex optimization with coupling constraints over time-varying directed graphs, A distributed hierarchical algorithm for multi-cluster constrained optimization, Distributed Nash equilibrium seeking in networked graphical games, Path-following gradient-based decomposition algorithms for separable convex optimization, Parallel alternating direction method of multipliers, Distributed optimization with information-constrained population dynamics, Communication-computation tradeoff in distributed consensus optimization for MPC-based coordinated control under wireless communications, Gradient-free method for nonsmooth distributed optimization, Distributed stochastic gradient tracking methods, Fast inexact decomposition algorithms for large-scale separable convex optimization, Relative tempo of distributed averaging on networks, A decentralized multi-objective optimization algorithm, Noise-to-State Exponentially Stable Distributed Convex Optimization on Weight-Balanced Digraphs, Mass-spring-damper networks for distributed optimization in non-Euclidean spaces, Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method, Distributed linear regression by averaging, Distributed multi-UAV trajectory optimization over directed networks, Communication-efficient algorithms for decentralized and stochastic optimization, Distributed convex optimisation with event-triggered communication in networked systems, On the Convergence of Decentralized Gradient Descent, Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication, Distributed optimization for degenerate loss functions arising from over-parameterization, A distributed continuous-time modified Newton-Raphson algorithm, On Convergence Rate of Distributed Stochastic Gradient Algorithm for Convex Optimization with Inequality Constraints, An adaptive online learning algorithm for distributed convex optimization with coupled constraints over unbalanced directed graphs, A multi-scale method for distributed convex optimization with constraints, On stochastic mirror descent with interacting particles: convergence properties and variance reduction, Parallel subgradient algorithm with block dual decomposition for large-scale optimization, Geometrical convergence rate for distributed optimization with time-varying directed graphs and uncoordinated step-sizes, Distributed coordination for nonsmooth convex optimization via saddle-point dynamics, 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, Surplus-based accelerated algorithms for distributed optimization over directed networks, Distributed online bandit optimization under random quantization, Unnamed Item, Distributed Bregman-Distance Algorithms for Min-Max Optimization, Primal recovery from consensus-based dual decomposition for distributed convex optimization, Distributed primal-dual optimisation method with uncoordinated time-varying step-sizes, Event-triggered zero-gradient-sum distributed optimisation algorithm with time-varying communication delays, Online learning over a decentralized network through ADMM, Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators With Massive Data, Optimal Algorithms for Non-Smooth Distributed Optimization in Networks, Distributed multi-step subgradient projection algorithm with adaptive event-triggering protocols: a framework of multiagent systems, Decentralized multi-agent optimization based on a penalty method, Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays, Continuous-Time Convergence Rates in Potential and Monotone Games, Composite optimization for the resource allocation problem, Unifying mirror descent and dual averaging, Distributed optimization of multi-integrator agent systems with mixed neighbor interactions, Distributed mirror descent algorithm over unbalanced digraphs based on gradient weighting technique, An accelerated exact distributed first-order algorithm for optimization over directed networks, Optimal control of discrete‐time nonlinear heterogeneous multi‐agent systems via a distributed DISOPE algorithm, A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization, Distributed one-pass online AUC maximization, A communication-efficient method for ℓ₀ regularization linear regression models, Differentially private distributed online learning over time‐varying digraphs via dual averaging, Distributed delayed dual averaging for distributed optimization over time-varying digraphs, A differentially private distributed optimization method for constrained optimization, Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization, Distributed optimization under edge agreements: a continuous-time algorithm, Distributed Algorithms with Finite Data Rates that Solve Linear Equations, Linear convergence of distributed estimation with constraints and communication delays, Communication-efficient distributed estimation for high-dimensional large-scale linear regression, 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, Localization and approximations for distributed non-convex optimization, Golden ratio proximal gradient ADMM for distributed composite convex optimization, Distributed projection‐free algorithm for constrained aggregative optimization, Synchronous distributed ADMM for consensus convex optimization problems with self-loops, Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate, Distributed Optimization Over Weight-Balanced Digraphs with Event-Triggered Communication, Unnamed Item, Unnamed Item, Distributed primal–dual stochastic subgradient algorithms for multi‐agent optimization under inequality constraints, Communication-Efficient Distributed Eigenspace Estimation, An Optimal Algorithm for Decentralized Finite-Sum Optimization, DISTRIBUTED PROXIMAL-GRADIENT METHOD FOR CONVEX OPTIMIZATION WITH INEQUALITY CONSTRAINTS, Communication-Efficient Distributed Statistical Inference, Distributed Subgradient-Free Stochastic Optimization Algorithm for Nonsmooth Convex Functions over Time-Varying Networks, Event-triggered zero-gradient-sum distributed convex optimisation over networks with time-varying topologies, Consensus-based distributed optimisation of multi-agent networks via a two level subgradient-proximal algorithm, EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization, A dual approach for optimal algorithms in distributed optimization over networks, Gradient‐free method for distributed multi‐agent optimization via push‐sum algorithms, Distributed optimization with inexact oracle