Multi-Consensus Decentralized Accelerated Gradient Descent

Haishan YeLuo LuoZiang ZhouTong Zhang

article2023JMLR71 citations

Resolves a key open problem in decentralized optimization by introducing accelerated gradient algorithms that achieve optimal computation and near-optimal communication complexities governed by the global rather than local condition number, even without locally convex agent functions.

Listen

Decentralized optimization is critical for modern large-scale machine learning, wireless communications, and sensor networks where data is distributed across multiple interconnected devices without a central server. In these settings, network nodes must collaborate to solve complex problems while keeping local data private and minimizing computational overhead. However, existing decentralized methods face significant performance bottlenecks because their communication efficiency historically depended on local data variability rather than the overall global problem difficulty, leading to slow convergence in heterogeneous environments.

The main objective of the article is to design decentralized optimization algorithms that simultaneously achieve optimal computational speed and near-optimal communication efficiency for smooth and composite convex problems. The article demonstrates how combining accelerated gradient steps with multi-consensus communication and gradient-tracking techniques solves long-standing theoretical and practical limitations in decentralized learning.

To evaluate this framework, the authors performed rigorous theoretical proofs establishing upper convergence bounds and conducted extensive empirical simulations. The experimental setup used synthetic and real-world benchmark datasets across 100 interconnected nodes under varying network connectivity levels. The testing examined standard logistic regression, regularized models, and scenarios where individual node functions were non-convex while the collective network goal remained strongly convex.

The analysis yielded three core findings. First, the proposed algorithms achieve optimal computation complexity and near-optimal communication complexity governed by the global condition number rather than the local condition number, answering an open theoretical question. Second, the algorithms maintain fast linear convergence even when local functions on individual nodes are non-convex, provided the overall global objective remains strongly convex. Third, the empirical evaluations confirmed that the proposed methods, named Mudag and ProxMudag, consistently outperformed state-of-the-art decentralized algorithms, achieving lower computational runtime and significantly fewer communication rounds across various network topologies.

These findings have major implications for distributed computing infrastructure. By decoupling communication performance from local data disparities, organizations can deploy decentralized machine learning across highly heterogeneous devices without suffering massive network delays or excessive bandwidth costs. Furthermore, removing the requirement that each node's local function be convex broadens the applicability of decentralized frameworks to complex machine learning pipelines, such as principal component analysis sub-problems, with minimal performance loss.

Organizations operating distributed computing or edge-device networks should consider adopting multi-consensus accelerated gradient methods to reduce bandwidth congestion and compute time. When deploying these algorithms, practitioners should select the single-consensus version for smooth objectives and the dual-consensus proximal version when dealing with non-differentiable regularization terms. Further empirical testing on large-scale physical hardware and edge-computing pilots is recommended before full-scale deployment.

While the mathematical derivations provide high confidence in the theoretical bounds, the results rely on the assumption of connected, undirected networks operating under synchronized communication rounds. Real-world practitioners should account for potential asynchronous delays, packet loss, and time-varying network graphs that could influence communication efficiency in live edge-network environments.

Center for Intelligent Decision-Making and Machine Learning Computer Science & Mathematics Department of Computing Fudan University Hong Kong Polytechnic University School of Data Science School of Management The Hong Kong University of Science and Technology Xi'an Jiaotong University multi-consensus decentralized accelerated gradient descent decentralized optimization consensus optimization

arXiv: 2005.00797

Paper: Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling, John Duchi et al. (2010). Establishes the foundational theoretical framework for distributed convex optimization over networks and reveals how spectral graph properties govern consensus and convergence rates.
Paper: ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!, Konstantin Mishchenko et al. (2022). Demonstrates how combining local gradient computations with skipped communication steps achieves provable communication acceleration in distributed optimization.
Book: Convex Optimization: Algorithms and Complexity, Sébastien Bubeck (2015). Provides the essential complexity bounds, oracle lower limits, and acceleration principles for first-order convex optimization underlying accelerated decentralized methods.
Paper: Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent, Xiangru Lian et al. (2017). Analyzes the computational complexity and communication bottlenecks of neighbor-to-neighbor decentralized optimization algorithms against centralized architectures.

Paper: Improved Gradient Descent Lower Bounds Beyond Nesterov, Yuhan Ye et al. (2026). Investigates fundamental convergence lower bounds for first-order gradient algorithms beyond classical Nesterov acceleration settings.
Paper: Adaptive Proximal Gradient Method for Convex Optimization, Yura Malitsky et al. (2024). Extends first-order convex optimization by adaptively estimating local curvature parameters without requiring prior knowledge of global smoothness constants.

Cover for Multi-Consensus Decentralized Accelerated Gradient Descent

Abstract

This paper considers the decentralized convex optimization problem, which has a wide range of applications in large-scale machine learning, sensor networks, and control theory. We propose novel algorithms that achieve optimal computation complexity and near optimal communication complexity. Our theoretical results give affirmative answers to the open problem on whether there exists an algorithm that can achieve a communication complexity (nearly) matching the lower bound depending on the global condition number instead of the local one. Furthermore, the linear convergence of our algorithms only depends on the strong convexity of global objective and it does not require the local functions to be convex. The design of our methods relies on a novel integration of well-known techniques including Nesterov’s acceleration, multi-consensus and gradient-tracking. Empirical studies show the outperformance of our methods for machine learning applications.

Keywords

multi-consensus decentralized accelerated gradient descent decentralized optimization consensus optimization accelerated proximal gradient descent multi-agent optimization gradient tracking composite optimization primal-dual algorithm linear convergence rate

1. Introduction
2. Related Work
3. Preliminaries
4. Multi-Consensus Decentralized Accelerated Gradient Descent
4.1 Algorithms and Main Ideas
4.2 Main Results
5. Convergence Analysis
6. Experiments
6.1 The Setting of Networks
6.2 Experiments on ℓ 2-Regularized Logistic Regression
6.3 Experiments on Sparse Logistic Regression
7. Conclusion
Acknowledgments
Appendix A. Useful Lemmas
Appendix B. Proof of Lemmas in Section 5
B.1 Collection of Lemmas
B.2 Proof of Lemma 9
B.3 Proof of Lemma 10
B.4 Proof of Lemma 11
Appendix C. Convergence Analysis of Algorithm 1
References

Knowls

Knowl 1 — Mudag for smooth decentralized optimization
algorithm
Mudag solves the decentralized smooth problem $\min_{x\in\mathbb{R}^d} f(x)=\frac{1}{m}\sum_{i=1}^m f_i(x)$ using one accelerated gradient-tracking update and one multi-consensus operation per iteration. Let $X_t,Y_t\in\mathbb{R}^{m\times d}$ collect the local agent variables by rows, let $\nabla F(Y_t)$ collect the rows $\nabla f_i(Y_t^{(i,:)})$ , let $x_0\in\mathbb{R}^d$ be the common initialization, and let $\operatorname{FastMix}(\cdot,K)$ be the $K$ -step consensus operator defined by the accelerated gossip recurrence. Given stepsize $\eta>0$ , momentum parameter $\alpha\in(0,1)$ , and consensus length $K$ , the method is:
Input: common vector $x_0$ , stepsize $\eta$ , momentum $\alpha$ , consensus length $K$ , and number of iterations $T$
Initialize $X_0=\mathbf{1}x_0^\top$ and $Y_0=X_0$
Compute $X_1=\operatorname{FastMix}(Y_0-\eta\nabla F(Y_0),K)$
Set $Y_1=X_1+\frac{1-\alpha}{1+\alpha}(X_1-X_0)$
for $t=1,\ldots,T-1$
$X_{t+1}=\operatorname{FastMix}(Y_t+(X_t-Y_{t-1})-\eta(\nabla F(Y_t)-\nabla F(Y_{t-1})),K)$
$Y_{t+1}=X_{t+1}+\frac{1-\alpha}{1+\alpha}(X_{t+1}-X_t)$
end for
Output: $X_T$
The difference $\nabla F(Y_t)-\nabla F(Y_{t-1})$ supplies history-based gradient tracking, while the momentum update supplies Nesterov acceleration. The method uses one multi-consensus call per outer iteration and does not require any individual $f_i$ to be convex.
Knowl 2 — ProxMudag for composite decentralized optimization
algorithm
ProxMudag extends the accelerated gradient-tracking construction to $h(x)=f(x)+r(x)$ , where $r:\mathbb{R}^d\to\mathbb{R}\cup\{+\infty\}$ is convex and may be nondifferentiable. For a row-stacked matrix $Z\in\mathbb{R}^{m\times d}$ , define $R(Z)=\frac{1}{m}\sum_{i=1}^m r(Z^{(i,:)})$ and
$\operatorname{prox}_{\eta m,R}(Z)=\arg\min_{U\in\mathbb{R}^{m\times d}}\left\{R(U)+\frac{1}{2m\eta}\|U-Z\|_F^2\right\}.$
The operator acts independently on rows: $\operatorname{prox}_{\eta m,R}(Z)^{(i,:)}=\operatorname{prox}_{\eta,r}(Z^{(i,:)})$ , where $\operatorname{prox}_{\eta,r}(z)=\arg\min_u\{r(u)+\|u-z\|^2/(2\eta)\}$ . With $X_t,Y_t,S_t\in\mathbb{R}^{m\times d}$ , $S_t$ tracking the aggregate gradient, stepsize $\eta$ , momentum $\alpha$ , and consensus length $K$ , ProxMudag is:
Input: common vector $x_0$ , stepsize $\eta$ , momentum $\alpha$ , consensus length $K$ , and number of iterations $T$
Initialize $X_0=\mathbf{1}x_0^\top$ , $Y_0=X_0$ , and $S_0=\nabla F(X_0)$
for $t=0,\ldots,T-1$
     $X_{t+1}=\operatorname{prox}_{\eta m,R}(Y_t-\eta S_t)$
     $Y_{t+1}=\operatorname{FastMix}(X_{t+1}+\frac{1-\alpha}{1+\alpha}(X_{t+1}-X_t),K)$
     $S_{t+1}=\operatorname{FastMix}(S_t+\nabla F(Y_{t+1})-\nabla F(Y_t),K)$
end for
Output: $X_T$
ProxMudag performs two multi-consensus calls per outer iteration: one for the accelerated primal variable and one for gradient tracking. It only assumes strong convexity of the global smooth part $f$ , not convexity of every local function $f_i$ .
Knowl 3 — Global-condition-number convergence of Mudag
theoretical result
Suppose $f(x)=\frac{1}{m}\sum_{i=1}^m f_i(x)$ is $L$ -smooth and $\mu$ -strongly convex, each local $f_i$ is $M$ -smooth, and $W$ is a valid symmetric gossip matrix with second-largest eigenvalue $\lambda_2(W)$ . Set Mudag's parameters to $\eta=1/L$ and $\alpha=\sqrt{\mu\eta}$ . Define the global condition number $\kappa_g=L/\mu$ and choose
$K=\frac{\sqrt{2}}{\sqrt{2}-1}\sqrt{\frac{1}{1-\lambda_2(W)}}\log\left(\frac{\sqrt{14}}{\rho}\right), \qquad \rho\leq \frac{1}{4^3\cdot 9\cdot 288}\left(\frac{L}{M}\right)^4\kappa_g^{-3}.$
For the averaged iterate $\bar x_T=\frac{1}{m}\sum_{i=1}^m X_T^{(i,:)}$ , Mudag satisfies
$f(\bar x_T)-f(x^*)\leq\left(1-\frac{\alpha}{2}\right)^T\left[f(\bar x_0)-f(x^*)+\frac{\mu}{2}\|\bar x_0-x^*\|^2+\frac{\mu}{288m}\sum_{i=1}^m\|\nabla f_i(\bar x_0)-\nabla f(\bar x_0)\|^2\right],$
where $x^*$ minimizes $f$ . To obtain $f(\bar x_T)-f(x^*)\leq\varepsilon$ and $\|X_T-\mathbf{1}(x^*)^\top\|_F^2=O(m\varepsilon/\mu)$ , Mudag needs
$T=O\left(\sqrt{\kappa_g}\log\frac{1}{\varepsilon}\right)$
local gradient computations and
$Q=O\left(\sqrt{\frac{\kappa_g}{1-\lambda_2(W)}}\log\left(\frac{M\kappa_g}{L}\right)\log\frac{1}{\varepsilon}\right)$
communication rounds. Thus, computation depends on the global condition number rather than a local condition number, and communication is within a logarithmic factor of the decentralized lower bound $\Omega(\sqrt{\kappa_g/(1-\lambda_2(W))}\log(1/\varepsilon))$ . The authors note that the extra logarithmic factor may be removable, since it arises from a potentially loose intermediate bound.
Knowl 4 — Global-condition-number convergence of ProxMudag
theoretical result
Suppose $f(x)=\frac{1}{m}\sum_{i=1}^m f_i(x)$ is $L$ -smooth and $\mu$ -strongly convex, each $f_i$ is $M$ -smooth, and $r$ is convex but possibly nondifferentiable. Let $h=f+r$ , let $x^*$ minimize $h$ , and run ProxMudag with $\eta=1/(2L)$ and $\alpha=\sqrt{\mu\eta}$ . Choose
$K=\frac{\sqrt{2}}{\sqrt{2}-1}\sqrt{\frac{1}{1-\lambda_2(W)}}\log\left(\frac{\sqrt{14}}{\rho}\right), \qquad \rho\leq \frac{1}{5.5\times 10^8}\left(\frac{L}{M}\right)^6\kappa_g^{-3/2},$
where $\kappa_g=L/\mu$ . For the averaged iterates $\bar X_T=\frac{1}{m}\sum_i X_T^{(i,:)}$ , the method satisfies
$h(\bar X_T)-h(x^*)\leq\left(1-\frac{\alpha}{2}\right)^T\left[h(\bar X_0)-h(x^*)+\frac{\mu}{2}\|\bar X_0-x^*\|^2+\frac{52L}{m}\sum_{i=1}^m\|\nabla f_i(\bar X_0)-\nabla f(\bar X_0)\|^2\right].$
To obtain $h(\bar X_T)-h(x^*)\leq\varepsilon$ and $\|X_T-\mathbf{1}(x^*)^\top\|_F^2=O(m\varepsilon/\mu)$ , ProxMudag uses
$T=O\left(\sqrt{\kappa_g}\log\frac{1}{\varepsilon}\right)$
local gradient computations and
$Q=O\left(\sqrt{\frac{\kappa_g}{1-\lambda_2(W)}}\log\left(\frac{M\kappa_g}{L}\right)\log\frac{1}{\varepsilon}\right)$
communication rounds. This establishes the same global-condition-number dependence for decentralized composite optimization despite the proximal, potentially nondifferentiable regularizer.
Knowl 5 — Accelerated multi-consensus operator
model/method
For a connected undirected network, let $W\in\mathbb{R}^{m\times m}$ be symmetric, satisfy $0\preceq W\preceq I_m$ , $W\mathbf{1}=\mathbf{1}$ , and have $\operatorname{null}(I_m-W)=\operatorname{span}(\mathbf{1})$ . The paper's accelerated consensus operator FastMix takes a matrix $X^0\in\mathbb{R}^{m\times d}$ , a nonnegative integer $K$ , and
$\eta_w=\frac{1}{1+\sqrt{1-\lambda_2(W)^2}},$
then sets $X^{-1}=X^0$ and iterates
$X^{k+1}=(1+\eta_w)WX^k-\eta_wX^{k-1},\qquad k=0,\ldots,K-1.$
It outputs $X^K$ . If $\bar X=\frac{1}{m}\mathbf{1}^\top X^0$ , FastMix preserves the exact average, $\frac{1}{m}\mathbf{1}^\top X^K=\bar X$ , and contracts disagreement according to
$\|X^K-\mathbf{1}\bar X\|_F\leq\sqrt{14}\left[1-\left(1-\frac{1}{\sqrt{2}}\right)\sqrt{1-\lambda_2(W)}\right]^K\|X^0-\mathbf{1}\bar X\|_F.$
This accelerated consensus primitive allows Mudag and ProxMudag to approximate centralized accelerated (proximal) gradient descent while retaining the exact average of each communicated matrix.
Knowl 6 — Exact averaged accelerated-gradient structure
theoretical result
Let $\bar X_t=\frac{1}{m}\mathbf{1}^\top X_t$ and $\bar Y_t=\frac{1}{m}\mathbf{1}^\top Y_t$ . For ProxMudag, define the local generalized gradient
$G_t^{(i,:)}=\frac{1}{\eta}\left(Y_t^{(i,:)}-\operatorname{prox}_{\eta,r}\left(Y_t^{(i,:)}-\eta S_t^{(i,:)}\right)\right), \qquad \bar G_t=\frac{1}{m}\sum_{i=1}^m G_t^{(i,:)}.$
If $\bar S_t=\frac{1}{m}\mathbf{1}^\top S_t$ and $\bar g_t=\frac{1}{m}\sum_i\nabla f_i(Y_t^{(i,:)})$ , the exact average-preservation property of FastMix and the initialization $S_0=\nabla F(Y_0)$ give $\bar S_t=\bar g_t$ for every iteration. Consequently, the averaged ProxMudag iterates obey
$\bar X_{t+1}=\bar Y_t-\eta\bar G_t, \qquad \bar Y_{t+1}=\bar X_{t+1}+\frac{1-\alpha}{1+\alpha}(\bar X_{t+1}-\bar X_t).$
For Mudag, the corresponding identities are
$\bar X_{t+1}=\bar Y_t-\eta\bar g_t, \qquad \bar Y_{t+1}=\bar X_{t+1}+\frac{1-\alpha}{1+\alpha}(\bar X_{t+1}-\bar X_t), \qquad \bar S_t=\bar g_t.$
Thus, the averaged algorithms have the same accelerated gradient or accelerated proximal-gradient form as centralized methods; the remaining analysis controls the disagreement of local primal variables and the error of the tracked gradients. The global smoothness and strong-convexity assumptions make these average updates converge even when individual local objectives are nonconvex.
Knowl 7 — Optimization and network assumptions
assumption
The decentralized objective is
$\min_{x\in\mathbb{R}^d}h(x),\qquad h(x)=f(x)+r(x),\qquad f(x)=\frac{1}{m}\sum_{i=1}^m f_i(x),$
where agent $i$ accesses only $f_i$ . The aggregate function $f$ is assumed $L$ -smooth and $\mu$ -strongly convex, while $r$ is convex and may be nondifferentiable. Each local function $f_i$ is differentiable and $M_i$ -smooth, with $M=\max_i M_i$ ; individual $f_i$ need not be convex. When local strong convexity is available, with parameters $\nu_i$ and $\nu=\min_i\nu_i$ , the paper defines $\kappa_g=L/\mu$ , $\hat\kappa_g=M/\mu$ , and $\kappa_\ell=M/\nu$ . The key results require only $\kappa_g$ and logarithmic dependence on $M/L$ .

The agents communicate over a connected undirected network represented by a symmetric matrix $W$ satisfying $0\preceq W\preceq I_m$ , $W\mathbf{1}=\mathbf{1}$ , and $\operatorname{null}(I_m-W)=\operatorname{span}(\mathbf{1})$ . The quantity $1-\lambda_2(W)$ , where $\lambda_2(W)$ is the second-largest eigenvalue, measures the network spectral gap. Each agent stores a local copy of the decision variable and can communicate only with its neighbors through multiplication by $W$ or through the accelerated FastMix recurrence.
Knowl 8 — Experimental design for smooth and composite learning
experimental setup
The experiments use $m=100$ agents and random undirected networks in which each pair is connected with probability $p$ . The gossip matrix is constructed as $W=I-L_{\mathrm{graph}}/\lambda_1(L_{\mathrm{graph}})$ , where $L_{\mathrm{graph}}$ is the weighted graph Laplacian and $\lambda_1$ is its largest eigenvalue. The two network settings have spectral gaps $1-\lambda_2(W)=0.05$ and $0.81$ .

Each local logistic-regression objective is
$f_i(x)=\frac{1}{n}\sum_{j=1}^{n}\log\left(1+\exp\left(-b_{ij}\langle a_{ij},x\rangle\right)\right)+\frac{\sigma_i}{2}\|x\|^2,$
with $a_{ij}\in\mathbb{R}^d$ and $b_{ij}\in\{-1,1\}$ . For the real-world a9a data, $n=325$ and $d=123$ . Smooth experiments use four regularization settings: $\sigma_i=10^{-3}$ for every agent; $\sigma_i=10^{-4}$ for every agent; $\sigma_i=-10^{-1}$ for agents $1,\ldots,m-1$ and $\sigma_m=10$ ; and $\sigma_i=-10^{-2}$ for agents $1,\ldots,m-1$ and $\sigma_m=1$ . The last two settings make most local objectives nonconvex while keeping the global objective strongly convex. Mudag is compared with centralized AGD, EXTRA, NIDS, Acc-DNGD, and APM-C, using tuned stepsizes and initialization at zero.

For sparse logistic regression, the objective is $h(x)=\frac{1}{m}\sum_i f_i(x)+\gamma\|x\|_1$ . Experiments use the network gap $0.05$ , convex local objectives, datasets a9a and w8a, with $(n,d)=(325,123)$ for a9a and $(497,300)$ for `w8a $. They use$ \gamma=10^{-4} $and uniform$ \sigma_i=10^{-3} $or$ 10^{-4} $, and compare ProxMudag with PG-EXTRA, NIDS, and D2P2. ProxMudag is tested with$ K=1,2,3$.
Knowl 9 — Empirical performance of Mudag under convex and nonconvex local objectives
empirical result
On the regularized logistic-regression tasks, Mudag has nearly the same gradient-computation cost as centralized accelerated gradient descent when every local $f_i$ is strongly convex, supporting the predicted $O(\sqrt{\kappa_g}\log(1/\varepsilon))$ computation rate. Its communication cost is nearly the centralized baseline when the network gap is $0.81$ and is approximately six times that baseline when the gap is $0.05$ , matching the predicted dependence on $1/\sqrt{1-\lambda_2(W)}$ . Across the tested strongly convex settings, Mudag uses less computation and communication than the other decentralized methods, with larger advantages for smaller regularization parameters.

When most local objectives are nonconvex but the global objective remains strongly convex, the plotted convergence curves show that Mudag's computation cost is essentially unchanged relative to the all-convex case, as predicted by its dependence on $\kappa_g$ rather than local convexity parameters. Its communication cost increases slightly because negative local regularizers increase $M/L$ ; this is consistent with the theory's logarithmic $\log(M\kappa_g/L)$ factor. The competing decentralized methods deteriorate substantially under the same local nonconvexity, whereas Mudag continues to converge rapidly.
Knowl 10 — Empirical performance of ProxMudag for sparse logistic regression
empirical result
For the composite objective $h(x)=\frac{1}{m}\sum_{i=1}^m f_i(x)+\gamma\|x\|_1$ on the sparse a9a and w8a logistic-regression tasks, ProxMudag outperforms PG-EXTRA, NIDS, and D2P2 in both gradient computations and communication rounds for all tested settings. The advantage is especially pronounced when the uniform local regularization parameter decreases from $\sigma_i=10^{-3}$ to $\sigma_i=10^{-4}$ , because the resulting condition number makes accelerated dependence on $\sqrt{\kappa_g}$ substantially better than methods depending on $\kappa_\ell$ or $\sqrt{\kappa_\ell}$ . ProxMudag converges effectively with each tested consensus length $K\in\{1,2,3\}$ ; increasing $K$ generally improves consensus per iteration but adds communication, while even the tested choices retain the method's strong communication advantage over the comparison algorithms.

Coverage note — No substantial contributed material was omitted; proof-only lemmas and detailed comparisons to prior methods were omitted because they support the stated algorithms and bounds without adding separate load-bearing contributions.

References

1.Sulaiman A. Alghunaim, Kun Yuan, and Ali H. Sayed. A linearly convergent proximal gradient algorithm for decentralized optimization. NeurIPS, 2019.
2.Sulaiman A. Alghunaim, Ernest Ryu, Kun Yuan, and Ali H. Sayed. Decentralized proximal gradient algorithms with linear convergence rates. IEEE Transactions on Automatic Control, 2020.
3.Zeyuan Allen-Zhu. Katyusha X: Simple momentum method for stochastic sum-of-nonconvex optimization. In ICML, 2018.
4.Albert S. Berahas, Raghu Bollapragada, Nitish Shirish Keskar, and Ermin Wei. Balancing communication and computation in distributed optimization. IEEE Transactions on Automatic Control, 64 (8):3141–3155, 2018.
5.Francesco Bullo, Jorge Cortes, and Sonia Martinez. Distributed control of robotic networks: a mathematical approach to motion coordination algorithms, volume 27. Princeton University Press, 2009.
6.Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):1–27, 2011.
7.Paolo Di Lorenzo and Gesualdo Scutari. Distributed nonconvex optimization over networks. In Workshop on CAMSAP, 2015.
8.Paolo Di Lorenzo and Gesualdo Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016.
9.Tomaso Erseghe, Davide Zennaro, Emiliano Dall’Anese, and Lorenzo Vangelista. Fast consensus by the alternating direction multipliers method. IEEE Transactions on Signal Processing, 59(11):5523–5537, 2011.
10.Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford. Robust shift-and-invert preconditioning: Faster and more sample efficient algorithms for eigenvector computation. In ICML, 2016.
11.Mingyi Hong, Davood Hajinezhad, and Ming-Min Zhao. Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks. In ICML, 2017.
12.Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge university press, 2012.
13.Dusan Jakovetic. A unification and generalization of exact distributed first-order methods. IEEE Transactions on Signal and Information Processing over Networks, 5(1):31–46, 2018.
14.Dusan Jakovetic, Joao Xavier, and José M.F. Moura. Fast distributed gradient methods. IEEE Transactions on Automatic Control, 59(5):1131–1146, 2014.
15.Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1–2):1–210, 2021.
16.Usman A. Khan, Soummya Kar, and Jose M.F. Moura. Diland: An algorithm for distributed sensor localization with noisy distance measurements. IEEE Transactions on Signal Processing, 58(3):1940–1947, 2009.
17.Dmitry Kovalev, Adil Salim, and Peter Richtarik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. In NeurIPS, 2020.
18.Guanghui Lan, Soomin Lee, and Yi Zhou. Communication-efficient algorithms for decentralized and stochastic optimization. Mathematical Programming, 180(1-2):237–284, 2020.
19.Boyue Li, Shicong Cen, Yuxin Chen, and Yuejie Chi. Communication-efficient distributed optimization in networks with gradient tracking and variance reduction. Journal of Machine Learning Research, 21:1–51, 2020a.
20.Huan Li and Zhouchen Lin. Revisiting EXTRA for smooth distributed optimization. SIAM Journal on Optimization, 30(3):1795–1821, 2020.
21.Huan Li and Zhouchen Lin. Accelerated gradient tracking over time-varying graphs for decentralized optimization. arXiv preprint arXiv:2104.02596, 2021.
22.Huan Li, Cong Fang, Wotao Yin, and Zhouchen Lin. Decentralized accelerated gradient methods with increasing penalty parameters. IEEE transactions on Signal Processing, 68:4855–4870, 2020b.
23.Zhi Li, Wei Shi, and Ming Yan. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, 67(17):4494–4506, 2019.
24.Ji Liu and A. Stephen Morse. Accelerated linear iterations for distributed averaging. Annual Reviews in Control, 35(2):160–165, 2011.
25.Cassio G. Lopes and Ali H. Sayed. Diffusion least-mean squares over adaptive networks: Formulation and performance analysis. IEEE Transactions on Signal Processing, 56(7):3122–3136, 2008.
26.Aryan Mokhtari and Alejandro Ribeiro. DSA: Decentralized double stochastic averaging gradient algorithm. Journal of Machine Learning Research, 17(1):2165–2199, 2016.
27.Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009.
28.Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597–2633, 2017.
29.Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
30.Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 5(3):1245–1260, 2017.
31.Guannan Qu and Na Li. Accelerated distributed Nesterov gradient descent. IEEE Transactions on Automatic Control, 2019.
32.Michael Rabbat and Robert Nowak. Distributed optimization in sensor networks. In IPSN, 2004.
33.Alejandro Ribeiro. Ergodic stochastic optimization algorithms for wireless communication and networking. IEEE Transactions on Signal Processing, 58(12):6369–6386, 2010.
34.Kevin Scaman, Francis Bach, Sebastien Bubeck, Yin Tat Lee, and Laurent Massoulie. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In ICML, 2017.
35.Kevin Scaman, Francis Bach, Sebastien Bubeck, Laurent Massoulie, and Yin Tat Lee. Optimal algorithms for non-smooth distributed optimization in networks. In NeurIPS, 2018.
36.Kevin Scaman, Francis Bach, Sebastien Bubeck, Yin Lee, and Laurent Massoulie. Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, 20:1–31, 2019.
37.Wei Shi, Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin. On the linear convergence of the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(7):1750–1761, 2014.
38.Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. A proximal gradient algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing, 63(22):6013–6023, 2015a.
39.Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944–966, 2015b.
40.Zhuoqing Song, Lei Shi, Shi Pu, and Ming Yan. Optimal gradient tracking for decentralized optimization. Mathematical Programming, pages 1–53, 2023.
41.Ying Sun, Gesualdo Scutari, and Amir Daneshmand. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. SIAM Journal on Optimization, 32(2):354–385, 2022.
42.Hakan Terelius, Ufuk Topcu, and Richard M. Murray. Decentralized multi-agent optimization via dual decomposition. IFAC proceedings volumes, 44(1):11245–11251, 2011.
43.Konstantinos I. Tsianos, Sean Lawlor, and Michael G. Rabbat. Consensus-based distributed optimization: Practical issues and applications in large-scale machine learning. In Allerton, 2012.
44.Cesar A Uribe, Soomin Lee, Alexander Gasnikov, and Angelia Nedic. A dual approach for optimal algorithms in distributed optimization over networks. In ITA Workshop, 2020.
45.Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65–78, 2004.
46.Jinming Xu, Shanying Zhu, Yeng Chai Soh, and Lihua Xie. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. In CDC, 2015.
47.Jinming Xu, Ye Tian, Ying Sun, and Gesualdo Scutari. Distributed algorithms for composite optimization: unified framework and convergence analysis. IEEE Transactions on Signal Processing, 69:3555–3570, 2021.
48.Haishan Ye, Ziang Zhou, Luo Luo, and Tong Zhang. Decentralized accelerated proximal gradient descent. In NeurIPS, 2020.
49.Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835–1854, 2016.
50.Minghui Zhu and Sonia Martínez. Discrete-time dynamic average consensus. Automatica, 46(2):322–329, 2010.

Citation

MLA

Ye, H., et al. “Multi-Consensus Decentralized Accelerated Gradient Descent”. Journal of Machine Learning Research, vol. 24, no. 306, 2023, pp. 1–0, https://www.jmlr.org/papers/v24/22-1210.html.

APA

Ye, H., Luo, L., Zhou, Z., & Zhang, T. (2023). Multi-Consensus Decentralized Accelerated Gradient Descent. Journal of Machine Learning Research, 24(306), 1–50. https://www.jmlr.org/papers/v24/22-1210.html

Chicago

Ye, H., L. Luo, Z. Zhou, and T. Zhang. 2023. “Multi-Consensus Decentralized Accelerated Gradient Descent”. Journal of Machine Learning Research 24 (306): 1–50. https://www.jmlr.org/papers/v24/22-1210.html.

Harvard

Ye, H. et al. (2023) “Multi-Consensus Decentralized Accelerated Gradient Descent”, Journal of Machine Learning Research, 24(306), pp. 1–50. Available at: https://www.jmlr.org/papers/v24/22-1210.html.

Vancouver

1. Ye H, Luo L, Zhou Z, Zhang T (2023) Multi-Consensus Decentralized Accelerated Gradient Descent. Journal of Machine Learning Research 24:1–50

BibTeX

@article{JMLR:v24:22-1210,
  author  = {Haishan Ye and Luo Luo and Ziang Zhou and Tong Zhang},
  title   = {Multi-Consensus Decentralized Accelerated Gradient Descent},
  journal = {Journal of Machine Learning Research},
  year    = {2023},
  volume  = {24},
  number  = {306},
  pages   = {1--50},
  url     = {http://jmlr.org/papers/v24/22-1210.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Multi-Consensus Decentralized Accelerated Gradient Descent

Abstract

Keywords

Table of Contents

Knowls

Knowl 1 — Mudag for smooth decentralized optimization

Knowl 2 — ProxMudag for composite decentralized optimization

Knowl 3 — Global-condition-number convergence of Mudag

Knowl 4 — Global-condition-number convergence of ProxMudag

Knowl 5 — Accelerated multi-consensus operator

Knowl 6 — Exact averaged accelerated-gradient structure

Knowl 7 — Optimization and network assumptions

Knowl 8 — Experimental design for smooth and composite learning

Knowl 9 — Empirical performance of Mudag under convex and nonconvex local objectives

Knowl 10 — Empirical performance of ProxMudag for sparse logistic regression

References

Citation

BibTeX

Access the Paper