Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs

DOI10.1137/16M1084316zbMath1387.90189arXiv1607.03218OpenAlexW2963649943MaRDI QIDQ4602346

Angelia Nedić, Wei Shi, Alex Olshevsky

Publication date: 10 January 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

linear convergencedistributed optimizationsmall gain theoremtime-varying graphsinexact gradient

Mathematics Subject Classification ID

Convex programming (90C25) Nonlinear programming (90C30)

Related Items

Distributed adaptive Newton methods with global superlinear convergence, Optimal Algorithms for Non-Smooth Distributed Optimization in Networks, 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, 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 Divergence of Decentralized Nonconvex Optimization, Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation, 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, A distributed methodology for approximate uniform global minimum sharing, Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs, Improving the convergence of distributed gradient descent via inexact average consensus, DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization, A fast proximal gradient algorithm for decentralized composite optimization over directed networks, Tracking-ADMM for distributed constraint-coupled optimization, Linear convergence of primal-dual gradient methods and their performance in distributed optimization, 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, 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 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 nonconvex constrained optimization over time-varying digraphs, Distributed online convex optimization with multiple coupled constraints: a double accelerated push-pull algorithm, Distributed Algorithms with Finite Data Rates that Solve Linear Equations, 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, 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, Network flows that solve least squares for linear equations, Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization, Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate, Proximal nested primal-dual gradient algorithms for distributed constraint-coupled composite optimization, Recent advances in optimization and game theoretic control for networked systems, Second-Order Guarantees of Distributed Gradient Algorithms, Towards accelerated rates for distributed optimization over time-varying networks, Recent theoretical advances in decentralized distributed convex optimization, Distributed Deterministic Asynchronous Algorithms in Time-Varying Graphs Through Dykstra Splitting, Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks, Revisiting EXTRA for Smooth Distributed Optimization, Distributed optimization over directed graphs with row stochasticity and constraint regularity, Convergence of distributed gradient-tracking-based optimization algorithms with random graphs, Distributed convex optimization with coupling constraints over time-varying directed graphs, Distributed constrained optimization problem of heterogeneous linear multi-agent systems with communication delays, An Optimal Algorithm for Decentralized Finite-Sum Optimization, Distributed stochastic gradient tracking methods, Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity, Exact spectral-like gradient method for distributed optimization, On the linear convergence of two decentralized algorithms, Stability analysis of distributed convex optimization under persistent attacks: a hybrid systems approach, Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method, A Distributed ADMM-like Method for Resource Sharing over Time-Varying Networks, Communication-efficient algorithms for decentralized and stochastic optimization, 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, Geometrical convergence rate for distributed optimization with time-varying directed graphs and uncoordinated step-sizes, Distributed multi-step subgradient optimization for multi-agent system, Convergence results of a nested decentralized gradient method for non-strongly convex problems, Unnamed Item, 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, A dual approach for optimal algorithms in distributed optimization over networks, Triggered gradient tracking for asynchronous distributed optimization, 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, Distributed optimization with inexact oracle

Uses Software

• ExtraPush

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Distributed strategies for generating weight-balanced and doubly stochastic digraphs
• First-order methods of smooth convex optimization with inexact oracle
• Distributed stochastic subgradient projection algorithms for convex optimization
• Incremental proximal methods for large scale convex optimization
• Geometric bounds for eigenvalues of Markov chains
• Distributed average consensus with least-mean-square deviation
• Discrete-time dynamic average consensus
• Convergence rate for consensus with delays
• The electrical resistance of a graph captures its commute and cover times
• Fast linear iterations for distributed averaging
• Incremental Subgradient Methods for Nondifferentiable Optimization
• Stochastic First-Order Methods with Random Constraint Projection
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Distributed Algorithms for Aggregative Games on Graphs
• A new class of distributed optimization algorithms: application to regression of distributed data
• Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
• Distributed Optimization Over Time-Varying Directed Graphs
• Fast Distributed Gradient Methods
• Average Consensus on Arbitrary Strongly Connected Digraphs With Time-Varying Topologies
• Product of Random Stochastic Matrices and Distributed Averaging
• Incremental Stochastic Subgradient Algorithms for Convex Optimization
• Distributed asynchronous computation of fixed points
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Fast Convergence Rates for Distributed Non-Bayesian Learning
• Distributed Sparse Linear Regression
• Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• A Proximal Gradient Algorithm for Decentralized Composite Optimization
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• Harnessing Smoothness to Accelerate Distributed Optimization
• Extrapush for Convex Smooth Decentralized Optimization Over Directed Networks
• Random Walks on Regular and Irregular Graphs
• On the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms
• Distributed Subgradient Methods for Multi-Agent Optimization
• On Distributed Averaging Algorithms and Quantization Effects
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• Asynchronous Broadcast-Based Convex Optimization Over a Network
• On Distributed Convex Optimization Under Inequality and Equality Constraints
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling