Decentralized Accelerated Proximal Gradient Descent

Haishan Ye, Ziang Zhou, Luo Luo, Tong ZhangNeurIPS 2020 · OpenReview

Introduction

Decentralized optimization is a cornerstone of modern machine learning, signal processing, and control systems. In these setups, a network of agents—such as sensors or edge devices—collaborates to minimize a global objective function without relying on a central server. This paper tackles the decentralized composite optimization problem, where the objective function consists of a smooth loss function distributed across agents and a shared non-smooth regularization term (e.g., an L1 penalty used for sparse models like Lasso).

While many decentralized algorithms exist, handling the non-smooth term efficiently is notoriously difficult. Existing proximal gradient methods (like PG-EXTRA or NIDS) often suffer from sub-linear convergence rates or sub-optimal communication overhead. Some newer algorithms achieve linear convergence but require a strict, unrealistic assumption: that every single agent's local data distribution forms a strongly convex function.

To overcome these limitations, the authors introduce Decentralized Accelerated Proximal Gradient Descent (DAPG). By elegantly combining Nesterov's acceleration, gradient tracking, and multi-consensus techniques, DAPG achieves optimal computational complexity and near-optimal communication complexity, significantly outperforming existing state-of-the-art methods—especially on ill-conditioned problems.

The DAPG Algorithm

To approximate the efficiency of a centralized accelerated solver, DAPG integrates three core techniques:

  1. Nesterov's Acceleration: Utilized to speed up the convergence rate of the gradient descent process.
  2. Gradient Tracking: Agents communicate to track the global gradient, correcting the "drift" caused by differences in their local datasets.
  3. Multi-Consensus (FastMix): Instead of a single communication step per gradient calculation, agents perform multiple rapid communication steps (gossip) to tightly bound the consensus error between nodes.

While multi-consensus was historically viewed as "communication-unfriendly," the authors prove that when paired with gradient tracking, it actually drives down the total number of communications needed to reach convergence. The algorithm reformulates the decentralized problem into an aggregated function and uses these techniques to ensure local variables rapidly converge to their centralized counterparts.

Key Insights

  • Global vs. Local Convexity: One of the most significant theoretical wins of DAPG is that it does not require individual local functions to be convex. As long as the global aggregated function is strongly convex, the algorithm achieves a fast convergence rate. This makes it highly applicable to real-world machine learning tasks where local data is often non-convex or poorly distributed.
  • Dependence on Global Condition Number: The complexity of DAPG scales with the global condition number ($\kappa_g$) rather than the local condition number ($\kappa_\ell$). Because local datasets can be highly skewed, $\kappa_\ell$ can be infinitely larger than $\kappa_g$. By depending only on $\kappa_g$, DAPG avoids massive slowdowns in heterogeneous networks.
  • Synergy of Tracking and Consensus: The paper demonstrates a counter-intuitive principle: doing more communication per iteration (via FastMix) leads to less overall communication over the lifespan of the training process, because the algorithm takes far fewer iterations to converge overall.

Empirical Results

The authors evaluated their algorithm on a sparse logistic regression task using standard benchmark datasets ('w8a' and 'a9a') from the LIBSVM repository.

Theoretical Optimality: DAPG establishes an optimal computational complexity of $\mathcal{O}(\sqrt{\kappa_g} \log(1/\epsilon))$ and a near-optimal communication complexity of $\mathcal{O}(\frac{\sqrt{\kappa_g}}{1-\lambda_2(W)} \log(\dots) \log(1/\epsilon))$. This is a massive theoretical improvement over prior state-of-the-art methods like NIDS, which scale linearly with the local condition number $\kappa_\ell$.

Empirical Dominance: In experiments against DPA, PG-EXTRA, and NIDS, DAPG required vastly fewer gradient computations and communication rounds to reach the same accuracy.

Convergence comparison of DAPG against baselines across varying levels of ill-conditioning.

Robustness to Ill-Conditioning: As seen in the performance graphs, the empirical advantages of DAPG become most pronounced when the L2 regularization parameter ($\sigma_2$) is small, creating a highly ill-conditioned problem. While baseline algorithms flatlined or converged slowly, DAPG maintained a steep, fast convergence curve.

Limitations and Future Work

While the computational complexity is strictly optimal, the communication complexity is described as "near-optimal," matching the theoretical lower bound up to a logarithmic factor dependent on network and function parameters.

These theoretical foundations are primed for application in sensor networks and multi-robot systems. Extending this framework to handle fully stochastic gradients (rather than full batch local gradients) or directed/time-varying communication graphs represent natural next steps for the field.

Summary updated

Abstract

Decentralized optimization has wide applications in machine learning, signal processing, and control. In this paper, we study the decentralized composite optimization problem with a non-smooth regularization term. Many proximal gradient based decentralized algorithms have been proposed in the past. However, these algorithms do not achieve near optimal computational complexity and communication complexity. In this paper, we propose a new method which establishes the optimal computational complexity and a near optimal communication complexity. Our empirical study shows that the proposed algorithm outperforms existing state-of-the-art algorithms.
BibTeX
@inproceedings{ye2020decentralized,
  author = {Haishan Ye and Ziang Zhou and Luo Luo and Tong Zhang},
  title = {{Decentralized Accelerated Proximal Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=g5VxfWKJks},
}
Figure