On the convergence of decentralized gradient descent

DOI10.1137/130943170MaRDI QIDQ2821798zbMATH OpenOpenAlexFDO

Authors Kun Yuan, Qing Ling, Wotao Yin

Publication date 23 September 2016

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

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

zbMATH Keywords

consensusdecentralizeddistributedgradient descentoptimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonlinear programming (90C30)

Abstract: Consider the consensus problem of minimizing $f(x)=su{m}_{i=1}^n{f}_i(x)$ where each $f_i$ is only known to one individual agent $i$ out of a connected network of $n$ agents. All the agents shall collaboratively solve this problem and obtain the solution subject to data exchanges restricted to between neighboring agents. Such algorithms avoid the need of a fusion center, offer better network load balance, and improve data privacy. We study the decentralized gradient descent method in which each agent $i$ updates its variable $x_{(i)}$, which is a local approximate to the unknown variable $x$, by combining the average of its neighbors' with the negative gradient step $-alphaabla{f}_i(x_{(i)})$. The iteration is ${\displaystyle }$x_{(i)}(k+1) gets sum_{ ext{neighbor} j ext{of} i} w_{ij} x_{(j)}(k) - alpha abla f_i(x_{(i)}(k)),quad ext{for each agent} i,${\displaystyle }$ where the averaging coefficients form a symmetric doubly stochastic matrix $W=[w_{ij}]inmathbb{R}^{nimesn}$. We analyze the convergence of this iteration and derive its converge rate, assuming that each $f_i$ is proper closed convex and lower bounded, $abla{f}_i$ is Lipschitz continuous with constant $L_{f_i}$, and stepsize $alpha$ is fixed. Provided that $alpha<O(1/L_h)$ where $L_h=ma{x}_i{L}_{f_i}$, the objective error at the averaged solution, $f(frac1nsu{m}_i{x}_{(i)}(k))-f^{\ast }$, reduces at a speed of $O(1/k)$ until it reaches $O(alpha)$. If $f_i$ are further (restricted) strongly convex, then both $frac1nsu{m}_i{x}_{(i)}(k)$ and each $x_{(i)}(k)$ converge to the global minimizer $x^{\ast }$ at a linear rate until reaching an $O(alpha)$-neighborhood of $x^{\ast }$. We also develop an iteration for decentralized basis pursuit and establish its linear convergence to an $O(alpha)$-neighborhood of the true unknown sparse signal.

Recommendations

• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Decentralized consensus algorithm with delayed and stochastic gradients
• DSA: decentralized double stochastic averaging gradient algorithm
• Optimal convergence rates for convex distributed optimization in networks
• A randomized incremental primal-dual method for decentralized consensus optimization

Cites work

• Analysis and generalizations of the linearized Bregman method
• Augmented _1 and nuclear-norm models with a globally linearly convergent algorithm
• Bregman Iterative Algorithms for \ell₁-Minimization with Applications to Compressed Sensing
• Consensus and Cooperation in Networked Multi-Agent Systems
• Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
• Convex analysis and monotone operator theory in Hilbert spaces
• Decentralized Dynamic Optimization Through the Alternating Direction Method of Multipliers
• Decentralized Jointly Sparse Optimization by Reweighted $\ell_{q}$ Minimization
• Decentralized Sparse Signal Recovery for Compressive Sleeping Wireless Sensor Networks
• Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Distributed Basis Pursuit
• Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity
• Distributed stochastic subgradient projection algorithms for convex optimization
• Distributed Subgradient Methods for Multi-Agent Optimization
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• Error forgetting of Bregman iteration
• Exact Regularization of Convex Programs
• Fast Distributed Gradient Methods
• Fast linearized Bregman iteration for compressive sensing and sparse denoising
• Fastest Mixing Markov Chain on a Graph
• Group-Lasso on Splines for Spectrum Cartography

Cited in

(89)

• Distributed consensus-based multi-agent convex optimization via gradient tracking technique
• On the linear convergence of two decentralized algorithms
• Projected subgradient based distributed convex optimization with transmission noises
• Convergence results of a nested decentralized gradient method for non-strongly convex problems
• An accelerated distributed gradient method with local memory
• Blended dynamics approach to distributed optimization: sum convexity and convergence rate
• A unitary distributed subgradient method for multi-agent optimization with different coupling sources
• Improving the convergence of distributed gradient descent via inexact average consensus
• Distributed constrained optimization for multi-agent systems over a directed graph with piecewise stepsize
• Correction-based diffusion LMS algorithms for distributed estimation
• Distributed algorithms for computing a fixed point of multi-agent nonexpansive operators
• Primal-dual stochastic distributed algorithm for constrained convex optimization
• Online learning over a decentralized network through ADMM
• Subgradient averaging for multi-agent optimisation with different constraint sets
• A distributed methodology for approximate uniform global minimum sharing
• Differentially private distributed optimization for multi-agent systems via the augmented Lagrangian algorithm
• EFIX: exact fixed point methods for distributed optimization
• Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization
• DSA: decentralized double stochastic averaging gradient algorithm
• ARock: an algorithmic framework for asynchronous parallel coordinate updates
• Revisiting EXTRA for Smooth Distributed Optimization
• On Nonconvex Decentralized Gradient Descent
• Decentralized consensus algorithm with delayed and stochastic gradients
• A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
• Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
• scientific article; zbMATH DE number 7626728 (Why is no real title available?)
• scientific article; zbMATH DE number 7626753 (Why is no real title available?)
• scientific article; zbMATH DE number 7626754 (Why is no real title available?)
• On the Divergence of Decentralized Nonconvex Optimization
• Distributed smooth optimisation with event-triggered proportional-integral algorithms
• Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
• Efficient and reliable overlay networks for decentralized federated learning
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• An Improved Convergence Analysis for Decentralized Online Stochastic Non-Convex Optimization
• Distributed algorithms with finite data rates that solve linear equations
• Second-order guarantees of distributed gradient algorithms
• Decentralized dictionary learning over time-varying digraphs
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Newton-like method with diagonal correction for distributed optimization
• Adaptive online distributed optimization in dynamic environments
• Event and Its Application in Algebraic Structures
• Discussion of the paper ‘A review of distributed statistical inference’
• A decentralized algorithm for spectral analysis
• An accelerated exact distributed first-order algorithm for optimization over directed networks
• High-dimensional \(M\)-estimation for Byzantine-robust decentralized learning
• A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
• A divide-and-conquer algorithm for distributed optimization on networks
• A decentralized smoothing quadratic regularization algorithm for composite consensus optimization with non-Lipschitz singularities
• Neurodynamic approaches for multi-agent distributed optimization
• Learning Coefficient Heterogeneity over Networks: A Distributed Spanning-Tree-Based Fused-Lasso Regression
• Understanding a Class of Decentralized and Federated Optimization Algorithms: A Multirate Feedback Control Perspective
• DIMIX: Diminishing Mixing for Sloppy Agents
• Dynamics based privacy preservation in decentralized optimization
• A variance-reduced stochastic gradient tracking algorithm for decentralized optimization with orthogonality constraints
• Distributed optimal frequency control under communication packet loss in multi-agent electric energy systems
• Event-triggered primal-dual design with linear convergence for distributed nonstrongly convex optimization
• Network Gradient Descent Algorithm for Decentralized Federated Learning
• Golden ratio proximal gradient ADMM for distributed composite convex optimization
• Using Witten Laplacians to Locate Index-1 Saddle Points
• Recent theoretical advances in decentralized distributed convex optimization
• Distributed sequential estimation procedures
• A code-based distributed gradient descent scheme for decentralized convex optimization
• Byzantine-resilient decentralized network learning
• Optimal gradient tracking for decentralized optimization
• A selective review on statistical methods for massive data computation: distributed computing, subsampling, and minibatch techniques
• On the geometric convergence of Byzantine-resilient distributed optimization algorithms
• An accelerated decentralized stochastic optimization algorithm with inexact model
• A decentralized proximal gradient tracking algorithm for composite optimization on Riemannian manifolds
• Decentralized Learning of Quantile Regression: A Smoothing Approach
• Decentralized projected Riemannian gradient method for smooth optimization on compact submanifolds embedded in the Euclidean space
• On the convergence analysis of the decentralized projected gradient descent method
• Review of mathematical optimization in federated learning
• On the convergence result of the gradient-push algorithm on directed graphs with constant stepsize
• Network alternating direction method of multipliers for ultrahigh-dimensional decentralised federated learning
• Fast and Robust Low-Rank Learning over Networks: A Decentralized Matrix Quantile Regression Approach
• Distributed inexact Newton method with adaptive step sizes
• On graphs with finite-time consensus and their use in gradient tracking
• Differentially private and communication-efficient distributed nonconvex optimization algorithms
• Sparse factorization of the square all-ones matrix of arbitrary order
• Distributed gradient descent method with edge-based event-driven communication for non-convex optimization
• A penalty-based method for communication-efficient decentralized bilevel programming
• Robust and efficient sparse learning over networks: a decentralized surrogate composite quantile regression approach
• Statistical inference for decentralized federated learning
• An improved convergence guarantee for the gradient-push algorithm with a constant stepsize
• Local adapt-then-combine algorithms for distributed nonsmooth optimization: achieving provable communication acceleration
• A first-order algorithm for decentralised min-max problems
• Analysis of DGD for decentralized high-dimensional statistical models: beyond the least squares
• Clipped stochastic gradient tracking for locally smooth functions
• Decentralized EM algorithm for Gaussian mixtures under data heterogeneity and partial labeling

This page was built for publication: On the convergence of decentralized gradient descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2821798)