EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization

DOI10.1137/14096668XzbMath1328.90107arXiv1404.6264OpenAlexW1571416372MaRDI QIDQ5254995

Wei Shi, Gang Wu, Qing Ling, Wotao Yin

Publication date: 11 June 2015

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

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

zbMATH Keywords

linear convergencegradient methoddecentralized optimizationconsensus optimization

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Decentralized ADMM with compressed and event-triggered communication ⋮ Consensus control of second-order stochastic discrete-time multi-agent systems without velocity transmission ⋮ A gradient‐free distributed optimization method for convex sum of nonconvex cost functions ⋮ Distributed solving linear algebraic equations with switched fractional order dynamics ⋮ 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 fixed step distributed proximal gradient push‐pull algorithm based on integral quadratic constraint ⋮ Resilient consensus‐based distributed optimization under deception attacks ⋮ Distributed continuous‐time constrained convex optimization with general time‐varying cost functions ⋮ Distributed convex optimization as a tool for solving \(f\)-consensus problems ⋮ Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization ⋮ A divide-and-conquer algorithm for distributed optimization on networks ⋮ Linear convergence rate analysis of a class of exact first-order distributed methods for weight-balanced time-varying networks and uncoordinated step sizes ⋮ A decentralized smoothing quadratic regularization algorithm for composite consensus optimization with non-Lipschitz singularities ⋮ Decentralized online convex optimization with compressed communications ⋮ Distributed forward-backward methods for ring networks ⋮ Neurodynamic approaches for multi-agent distributed optimization ⋮ Nonlinear Consensus+Innovations under Correlated Heavy-Tailed Noises: Mean Square Convergence Rate and Asymptotics ⋮ Linear convergence of distributed estimation with constraints and communication delays ⋮ Dynamics based privacy preservation in decentralized optimization ⋮ Gradient-tracking based differentially private distributed optimization with enhanced optimization accuracy ⋮ A variance-reduced stochastic gradient tracking algorithm for decentralized optimization with orthogonality constraints ⋮ Event-triggered primal-dual design with linear convergence for distributed nonstrongly convex optimization ⋮ Online distributed dual averaging algorithm for multi-agent bandit optimization over time-varying general directed networks ⋮ Golden ratio proximal gradient ADMM for distributed composite convex optimization ⋮ Distributed projection‐free algorithm for constrained aggregative optimization ⋮ Nabla fractional distributed optimization algorithms over undirected/directed graphs ⋮ Towards accelerated rates for distributed optimization over time-varying networks ⋮ Recent theoretical advances in decentralized distributed convex optimization ⋮ 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 ⋮ Blended dynamics approach to distributed optimization: sum convexity and convergence rate ⋮ Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent ⋮ Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions ⋮ On the Divergence of Decentralized Nonconvex Optimization ⋮ Distributed smooth optimisation with event-triggered proportional-integral algorithms ⋮ Optimal distributed stochastic mirror descent for strongly convex optimization ⋮ Primal-dual algorithm for distributed constrained optimization ⋮ Zeroth-order algorithms for stochastic distributed nonconvex optimization ⋮ Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation ⋮ Gradient-free distributed optimization with exact convergence ⋮ Distributed optimization for a class of uncertain MIMO nonlinear multi-agent systems with arbitrary relative degree ⋮ Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization over Random Networks with Imperfect Communications ⋮ 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 ⋮ Distributed model predictive control for linear systems under communication noise: algorithm, theory and implementation ⋮ A new Zeno-free event-triggered scheme for robust distributed optimal coordination ⋮ Subgradient averaging for multi-agent optimisation with different constraint sets ⋮ Distributed constraint-coupled optimization via primal decomposition over random time-varying graphs ⋮ A distributed methodology for approximate uniform global minimum sharing ⋮ Distributed fixed point method for solving systems of linear algebraic equations ⋮ Differentially private distributed optimization for multi-agent systems via the augmented Lagrangian algorithm ⋮ Improving the convergence of distributed gradient descent via inexact average consensus ⋮ 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 ⋮ 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 ⋮ Distributed mirror descent algorithm over unbalanced digraphs based on gradient weighting technique ⋮ An accelerated exact distributed first-order algorithm for optimization over directed networks ⋮ A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization ⋮ Zeroth-order feedback optimization for cooperative multi-agent systems ⋮ Multi-cluster distributed optimization via random sleep strategy ⋮ Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization ⋮ Distributed nonconvex constrained optimization over time-varying digraphs ⋮ Distributed Algorithms with Finite Data Rates that Solve Linear Equations ⋮ Linear Time Average Consensus and Distributed Optimization on Fixed Graphs ⋮ EFIX: exact fixed point methods for distributed optimization ⋮ Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs ⋮ 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 ⋮ Distributed subgradient method for multi-agent optimization with quantized communication ⋮ Distributed Deterministic Asynchronous Algorithms in Time-Varying Graphs Through Dykstra Splitting ⋮ Online supervised learning with distributed features over multiagent system ⋮ Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme ⋮ Revisiting EXTRA for Smooth Distributed Optimization ⋮ Initialization-free privacy-guaranteed distributed algorithm for economic dispatch problem ⋮ Distributed optimization over directed graphs with row stochasticity and constraint regularity ⋮ Distributed consensus-based multi-agent convex optimization via gradient tracking technique ⋮ Distributed nonsmooth convex optimization over Markovian switching random networks with two step-sizes ⋮ Decentralized Consensus Algorithm with Delayed and Stochastic Gradients ⋮ Distributed convex optimization with coupling constraints over time-varying directed graphs ⋮ Distributed constrained optimization problem of heterogeneous linear multi-agent systems with communication delays ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fejér-monotone hybrid steepest descent method for affinely constrained and composite convex minimization tasks ⋮ An Optimal Algorithm for Decentralized Finite-Sum Optimization ⋮ Distributed stochastic gradient tracking methods ⋮ Random Gradient Extrapolation for Distributed and Stochastic Optimization ⋮ Forward-Backward-Half Forward Algorithm for Solving Monotone Inclusions ⋮ 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 ⋮ Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method ⋮ Decentralized and privacy-preserving low-rank matrix completion ⋮ Fast proximity-gradient algorithms for structured convex optimization problems

Cites Work

• Unnamed Item
• Distributed stochastic subgradient projection algorithms for convex optimization
• Distributed average consensus with least-mean-square deviation
• A new method for a class of linear variational inequalities
• Fast linear iterations for distributed averaging
• On the Convergence of Decentralized Gradient Descent
• Augmented $\ell_1$ and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
• Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
• Explicit Convergence Rate of a Distributed Alternating Direction Method of Multipliers
• Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms
• Fast Distributed Gradient Methods
• Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
• Decentralized Sparse Signal Recovery for Compressive Sleeping Wireless Sensor Networks
• Distributed Sparse Linear Regression
• Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity
• Group-Lasso on Splines for Spectrum Cartography
• Decentralized Jointly Sparse Optimization by Reweighted $\ell_{q}$ Minimization
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Fastest Mixing Markov Chain on a Graph
• Distributed Subgradient Methods for Multi-Agent Optimization
• A Collaborative Training Algorithm for Distributed Learning
• Convergence Rate Analysis of Several Splitting Schemes
• On Distributed Convex Optimization Under Inequality and Equality Constraints
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

This page was built for publication: EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization