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 (only showing first 100 items - show all)

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

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