Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
From MaRDI portal
Abstract: This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining Push-DIGing algorithm. The Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit estimates for the convergence rates. When the graph is undirected it shows that DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings.
Recommendations
- A Geometrically Converging Dual Method for Distributed Optimization Over Time-Varying Graphs
- Geometrical convergence rate for distributed optimization with time-varying directed graphs and uncoordinated step-sizes
- Optimal Distributed Convex Optimization on Slowly Time-Varying Graphs
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed convex optimization with coupling constraints over time-varying directed graphs
- Distributed nonconvex constrained optimization over time-varying digraphs
- Distributed Online Convex Optimization on Time-Varying Directed Graphs
- scientific article; zbMATH DE number 6936839
- Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information
- Distributed Continuous-Time Algorithms for Time-Varying Constrained Convex Optimization
Cites work
- A new class of distributed optimization algorithms: application to regression of distributed data
- A Proximal Gradient Algorithm for Decentralized Composite Optimization
- Asynchronous Broadcast-Based Convex Optimization Over a Network
- Average Consensus on Arbitrary Strongly Connected Digraphs With Time-Varying Topologies
- Consensus-based distributed support vector machines
- Convergence rate for consensus with delays
- Convergence rate of incremental subgradient algorithms
- Cooperative distributed multi-agent optimization
- Discrete-time dynamic average consensus
- Distributed algorithms for aggregative games on graphs
- Distributed asynchronous computation of fixed points
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- Distributed asynchronous incremental subgradient methods
- Distributed average consensus with least-mean-square deviation
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed Sparse Linear Regression
- Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity
- Distributed stochastic subgradient projection algorithms for convex optimization
- Distributed strategies for generating weight-balanced and doubly stochastic digraphs
- Distributed Subgradient Methods for Multi-Agent Optimization
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- DSA: decentralized double stochastic averaging gradient algorithm
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- ExtraPush for convex smooth decentralized optimization over directed networks
- Fast Convergence Rates for Distributed Non-Bayesian Learning
- Fast Distributed Gradient Methods
- Fast linear iterations for distributed averaging
- First-order methods of smooth convex optimization with inexact oracle
- Geometric bounds for eigenvalues of Markov chains
- Harnessing Smoothness to Accelerate Distributed Optimization
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 3513598 (Why is no real title available?)
- scientific article; zbMATH DE number 1834589 (Why is no real title available?)
- Incremental proximal methods for large scale convex optimization
- Incremental stochastic subgradient algorithms for convex optimization
- Incremental subgradient methods for nondifferentiable optimization
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- On Distributed Averaging Algorithms and Quantization Effects
- On Distributed Convex Optimization Under Inequality and Equality Constraints
- On the Convergence Rate of Incremental Aggregated Gradient Algorithms
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- On the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms
- Product of Random Stochastic Matrices and Distributed Averaging
- Random Walks on Regular and Irregular Graphs
- Stochastic first-order methods with random constraint projection
- Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
- The electrical resistance of a graph captures its commute and cover times
Cited in
(only showing first 100 items - show all)- A fast proximal gradient algorithm for decentralized composite optimization over directed networks
- Distributed optimization over directed graphs with row stochasticity and constraint regularity
- Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method
- Distributed convex optimization with coupling constraints over time-varying directed graphs
- Distributed stochastic gradient tracking methods
- On the linear convergence of two decentralized algorithms
- Distributed decision-coupled constrained optimization via proximal-tracking
- Fully asynchronous policy evaluation in distributed reinforcement learning over networks
- Distributed gradient tracking methods with finite data rates
- Convergence results of a nested decentralized gradient method for non-strongly convex problems
- Multi-agent reinforcement learning: a selective overview of theories and algorithms
- Distributed composite optimization for multi-agent systems with asynchrony
- On arbitrary compression for decentralized consensus and stochastic optimization over directed networks
- An accelerated distributed gradient method with local memory
- Triggered gradient tracking for asynchronous distributed optimization
- Distributed adaptive Newton methods with global superlinear convergence
- Exponential convergence of distributed optimization for heterogeneous linear multi-agent systems over unbalanced digraphs
- Distributed ergodic algorithms for mixed equilibrium problems: absent of cut property
- Decentralized proximal splitting algorithms for composite constrained convex optimization
- Distributed least squares solver for network linear equations
- A unitary distributed subgradient method for multi-agent optimization with different coupling sources
- Improving the convergence of distributed gradient descent via inexact average consensus
- Tracking-ADMM for distributed constraint-coupled optimization
- Linear convergence of primal-dual gradient methods and their performance in distributed optimization
- Network flows that solve least squares for linear equations
- Convergence of distributed gradient-tracking-based optimization algorithms with random graphs
- Distributed constrained optimization problem of heterogeneous linear multi-agent systems with communication delays
- Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity
- Exact spectral-like gradient method for distributed optimization
- Stability analysis of distributed convex optimization under persistent attacks: a hybrid systems approach
- Communication-efficient algorithms for decentralized and stochastic optimization
- Distributed multi-step subgradient optimization for multi-agent system
- Distributed nonconvex constrained optimization over time-varying digraphs
- A distributed methodology for approximate uniform global minimum sharing
- Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
- Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization
- Proximal nested primal-dual gradient algorithms for distributed constraint-coupled composite optimization
- Revisiting EXTRA for Smooth Distributed Optimization
- Linear time average consensus and distributed optimization on fixed graphs
- Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
- Robust asynchronous stochastic gradient-push: asymptotically optimal and network-independent performance for strongly convex functions
- GADMM: fast and communication efficient framework for distributed machine learning
- On the convergence of exact distributed generalisation and acceleration algorithm for convex optimisation
- Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
- Distributed primal-dual optimisation method with uncoordinated time-varying step-sizes
- On the Divergence of Decentralized Nonconvex Optimization
- Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
- DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization
- Distributed algorithms with finite data rates that solve linear equations
- Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate.
- Recent advances in optimization and game theoretic control for networked systems
- Second-order guarantees of distributed gradient algorithms
- scientific article; zbMATH DE number 7307473 (Why is no real title available?)
- An Optimal Algorithm for Decentralized Finite-Sum Optimization
- A distributed ADMM-like method for resource sharing over time-varying networks
- Optimal convergence rates for convex distributed optimization in networks
- A dual approach for optimal algorithms in distributed optimization over networks
- Distributed optimization with inexact oracle
- A Small Gain Analysis of Single Timescale Actor Critic
- Trust-region based stochastic variational inference for distributed and asynchronous networks
- An event-triggering algorithm for decentralized stochastic optimization over networks
- An accelerated exact distributed first-order algorithm for optimization over directed networks
- A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- A distributed optimization algorithm over Markov switching topology under adversarial attack
- Augmented Lagrangian tracking for distributed optimization with equality and inequality coupling constraints
- Multi-agent based optimal equilibrium selection with resilience constraints for traffic flow
- A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
- A resilient distributed optimization strategy against false data injection attacks
- Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information
- A fixed step distributed proximal gradient push‐pull algorithm based on integral quadratic constraint
- Resilient consensus‐based distributed optimization under deception attacks
- Game-theoretical approach for task allocation problems with constraints
- Distributed delayed dual averaging for distributed optimization over time-varying digraphs
- Distributed convex optimization as a tool for solving \(f\)-consensus problems
- A Fenchel dual gradient method enabling regularization for nonsmooth distributed optimization over time-varying networks
- Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
- Distributed cooperative reinforcement learning for multi‐agent system with collision avoidance
- Linear convergence rate analysis of a class of exact first-order distributed methods for weight-balanced time-varying networks and uncoordinated step sizes
- Distributed online convex optimization with multiple coupled constraints: a double accelerated push-pull algorithm
- Decentralized optimization over slowly time-varying graphs: algorithms and lower bounds
- Linear convergence of distributed estimation with constraints and communication delays
- Multi-agent natural actor-critic reinforcement learning algorithms
- DIMIX: Diminishing Mixing for Sloppy Agents
- Dynamics based privacy preservation in decentralized optimization
- A Unified Framework for Continuous-Time Unconstrained Distributed Optimization
- Network Gradient Descent Algorithm for Decentralized Federated Learning
- Golden ratio proximal gradient ADMM for distributed composite convex optimization
- Towards accelerated rates for distributed optimization over time-varying networks
- Recent theoretical advances in decentralized distributed convex optimization
- Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
- Distributed constrained optimization algorithms with linear convergence rate over time-varying unbalanced graphs
- Confidence region for distributed stochastic optimization problem via stochastic gradient tracking method
- Distributed algorithms of solving linear matrix equations via double-layered networks
- Sampled-data-based disturbance compensation distributed optimization control for a class of multi-agent systems
- A decentralized Nesterov gradient method for stochastic optimization over unbalanced directed networks
- Distributed predefined-time constrained social cost minimization problem under the partial information setting
- Distributed event-triggered algorithm for unconstrained convex optimisation over weight-balanced directed networks
- Optimal gradient tracking for decentralized optimization
- Distributed multi-agent optimisation via coordination with second-order nearest neighbours
This page was built for publication: Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4602346)
