Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
From MaRDI portal
Publication:5352733
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.
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
Cited in
(only showing first 100 items - show all)- 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 optimisation with event-triggered communication in networked systems
- Graph-dependent implicit regularisation for distributed stochastic subgradient descent
- Convergence of distributed gradient-tracking-based optimization algorithms with random graphs
- Distributed optimization for degenerate loss functions arising from over-parameterization
- A distributed continuous-time modified Newton-Raphson algorithm
- Adaptive backstepping for distributed optimization
- Distributed linear regression by averaging
- Distributed multi-UAV trajectory optimization over directed networks
- GADMM: fast and communication efficient framework for distributed machine learning
- Relative tempo of distributed averaging on networks
- Tracking-ADMM for distributed constraint-coupled optimization
- Cooperative convex optimization with subgradient delays using push-sum distributed dual averaging
- 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
- Event-triggered zero-gradient-sum distributed convex optimisation over networks with time-varying topologies
- Distributed multi-step subgradient projection algorithm with adaptive event-triggering protocols: a framework of multiagent systems
- Distributed nonsmooth convex optimization over Markovian switching random networks with two step-sizes
- Distributed Saddle-Point Subgradient Algorithms With Laplacian Averaging
- Distributed average tracking for uncertain directed multiagent networks
- Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization
- Asymptotic properties of primal-dual algorithm for distributed stochastic optimization over random networks with imperfect communications
- Regularized dual gradient distributed method for constrained convex optimization over unbalanced directed graphs
- Composite optimization for the resource allocation problem
- Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate.
- Parallel subgradient algorithm with block dual decomposition for large-scale optimization
- Communication-Efficient Distributed Eigenspace Estimation
- Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization
- Distributed stochastic gradient tracking methods
- Decentralized consensus algorithm with delayed and stochastic gradients
- Multi-cluster distributed optimization via random sleep strategy
- Mass-spring-damper networks for distributed optimization in non-Euclidean spaces
- A dual approach for optimal algorithms in distributed optimization over networks
- A differentially private distributed optimization method for constrained optimization
- Communication-efficient distributed estimation for high-dimensional large-scale linear regression
- A unitary distributed subgradient method for multi-agent optimization with different coupling sources
- Generalized Nash equilibrium seeking algorithm design for distributed multi-cluster games
- A multi-scale method for distributed convex optimization with constraints
- Distributed optimization of multi-integrator agent systems with mixed neighbor interactions
- Differentially private distributed optimization for multi-agent systems via the augmented Lagrangian algorithm
- Global convergence rate of proximal incremental aggregated gradient methods
- Distributed constraint-coupled optimization via primal decomposition over random time-varying graphs
- Noise-to-state exponentially stable distributed convex optimization on weight-balanced digraphs
- Surplus-based accelerated algorithms for distributed optimization over directed networks
- Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
- Communication-computation tradeoff in distributed consensus optimization for MPC-based coordinated control under wireless communications
- Incremental gradient-free method for nonsmooth distributed optimization
- Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
- Distributed algorithms with finite data rates that solve linear equations
- Communication-efficient algorithms for decentralized and stochastic optimization
- An adaptive online learning algorithm for distributed convex optimization with coupled constraints over unbalanced directed graphs
- A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW)
- Distributed subgradient method for multi-agent optimization with quantized communication
- Distributed optimal in-network resource allocation algorithm design via a control theoretic approach
- A distributed fixed-time optimization algorithm for multi-agent systems
- Distributed solver for linear matrix inequalities: an optimization perspective
- Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks
- Distributed optimization with information-constrained population dynamics
- Geometrical convergence rate for distributed optimization with time-varying directed graphs and uncoordinated step-sizes
- Distributed proximal-gradient method for convex optimization with inequality constraints
- Gradient‐free method for distributed multi‐agent optimization via push‐sum algorithms
- Distributed primal-dual stochastic subgradient algorithms for multi-agent optimization under inequality constraints
- Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method
- Communication-efficient distributed statistical inference
- Distributed online bandit optimization under random quantization
- Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems
- Unifying mirror descent and dual averaging
- Distributed consensus-based multi-agent convex optimization via gradient tracking technique
- Asynchronous gossip-based gradient-free method for multiagent optimization
- Optimal convergence rates for convex distributed optimization in networks
- Distributed convex optimization with coupling constraints over time-varying directed graphs
- Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
- Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks
- Decentralized multi-agent optimization based on a penalty method
- Distributed Nash equilibrium seeking in networked graphical games
- Large-scale multivariate sparse regression with applications to UK Biobank
- Gradient-free method for nonsmooth distributed optimization
- A decentralized multi-objective optimization algorithm
- Convergence rate analysis of distributed optimization with projected subgradient algorithm
- Exponential convergence of a distributed algorithm for solving linear algebraic equations
- Fast inexact decomposition algorithms for large-scale separable convex optimization
- Distributed constrained optimization via continuous-time mirror design
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Approximate dual averaging method for multiagent saddle-point problems with stochastic subgradients
- Decentralized gradient algorithm for solution of a linear equation
- Primal recovery from consensus-based dual decomposition for distributed convex optimization
- Distributed multi-agent optimization subject to nonidentical constraints and communication delays
- Parallel alternating direction method of multipliers
- Distributed constrained optimization for multi-agent systems over a directed graph with piecewise stepsize
- 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
- Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication
- Path-following gradient-based decomposition algorithms for separable convex optimization
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Distributed multi-agent optimization with state-dependent communication
- Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme
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)
