An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization

Luo Luo, Haishan Ye

Abstract

This paper addresses the challenge of decentralized nonconvex optimization, where a network of $m$ agents collaborates to minimize a global objective function without a central coordinator. We introduce DEAREST+ (DEcentralized probAbilistic Recursive gradiEnt deScenT), a novel stochastic algorithm that integrates variance reduction, gradient tracking, and multi-consensus techniques. By utilizing a multinomial sampling strategy, DEAREST+ is the first algorithm to achieve optimal complexity bounds for both communication and computation in this setting, matching established lower bounds. Our analysis demonstrates that DEAREST+ effectively leverages global smoothness parameters, overcoming the performance bottlenecks associated with local smoothness in traditional decentralized methods.

Introduction

In decentralized optimization, $m$ agents are connected via a communication graph. Each agent $i$ possesses a local objective function $f_i(x)$, which is itself an average of $n$ individual data points (a finite-sum). The collective goal is to minimize the global function $f(x) = \frac{1}{m}\sum_{i=1}^m f_i(x)$. This framework is essential for modern privacy-preserving machine learning and large-scale sensor networks where data cannot be centralized due to bandwidth or privacy constraints.

A persistent challenge in this field is the "efficiency gap." Most existing algorithms rely on local smoothness parameters—the maximum rate of change of an individual agent's gradient. However, local smoothness can be significantly larger than the global smoothness of the averaged function. Relying on these pessimistic local estimates leads to sub-optimal performance. Furthermore, until recently, the lack of tight theoretical lower bounds made it difficult to determine if existing algorithms could be further improved.

The DEAREST+ Framework

To bridge this gap, we propose DEAREST+. The algorithm is built upon four pillars of modern optimization:

  1. Gradient Tracking: This mechanism allows agents to estimate the global gradient by sharing information with immediate neighbors, effectively reducing the "consensus error" that arises from data heterogeneity across the network.
  2. Probabilistic Recursive Gradients (PAGE): Rather than computing a full gradient at every iteration—which is computationally prohibitive—DEAREST+ utilizes a probabilistic update. It usually performs a cheap update based on a small batch of data, only occasionally computing a full gradient to maintain accuracy.
  3. Chebyshev Acceleration: To accelerate the spread of information across the network, we employ multi-consensus rounds using Chebyshev acceleration, which optimizes the communication efficiency relative to the network's spectral gap.
  4. Multinomial Sampling: This is the "secret sauce" of DEAREST+. Unlike traditional methods that assign a fixed batch size to every agent, DEAREST+ uses a multinomial distribution to select which agents perform computations. This strategy allows the network to behave like a single-machine mini-batch system, enabling the algorithm to be governed by global smoothness ($L$) rather than the more restrictive local smoothness.

Theoretical Contributions and Optimality

We provide a rigorous convergence analysis using a constructed Lyapunov function that simultaneously tracks function value, gradient estimation error, and consensus error. Our results show that DEAREST+ requires at most:

  • Computation (IFO Calls): ${\mathcal O}(mn+\sqrt{mn}L\varepsilon^{-2})$
  • Communication Rounds: ${\mathcal O}({L\varepsilon^{-2}}/{\sqrt{1-\lambda_2(W)}})$

These complexities match the theoretical lower bounds for decentralized nonconvex finite-sum optimization. Notably, DEAREST+ is the first algorithm to achieve this near-optimal status. Furthermore, under the Polyak-Lojasiewicz (PL) condition—a common assumption for certain nonconvex problems—the algorithm achieves linear convergence to the global optimum.

Empirical Results

We validated DEAREST+ against state-of-the-art competitors like D-GET and DESTRESS using both synthetic "hard instances" and real-world datasets:

  • Wikipedia Math Essential: A dataset with $mn = 1,056$ samples and $d = 730$ features.
  • RCV1.binary: A large-scale text categorization dataset with $N = 20,096$ samples and $d = 47,236$ features.

In experiments involving nonconvex regularized logistic regression, DEAREST+ consistently outperformed existing methods. It reached lower gradient norms (indicating higher solution precision) with fewer data passes and fewer communication rounds, particularly as the number of local functions $n$ increased.

Conclusion

DEAREST+ represents a significant advancement in decentralized optimization by providing a unified, optimal framework for nonconvex finite-sum problems. By shifting the focus from local to global smoothness and employing sophisticated variance reduction, it sets a new benchmark for both theoretical and empirical performance. Future work will explore extending these near-optimal guarantees to time-varying network topologies and broader classes of functions satisfying the Kurdyka-Lojasiewicz inequality.

Summary updated

Abstract

This paper studies the decentralized nonconvex optimization problem $\min_{x\in{\mathbb R}^d} f(x)\triangleq \frac{1}{m}\sum_{i=1}^m f_i(x)$, where $f_i(x)\triangleq \frac{1}{n}\sum_{j=1}^n f_{i,j}(x)$ is the local function on the $i$-th agent of the network. We propose a novel stochastic algorithm called DEcentralized probAbilistic Recursive gradiEnt deScenT (\DEAREST), which integrates the techniques of variance reduction, gradient tracking and multi-consensus. We construct a Lyapunov function that simultaneously characterizes the function value, the gradient estimation error and the consensus error for the convergence analysis. Based on this measure, we provide a concise proof to show DEAREST requires at most ${\mathcal O}(mn+\sqrt{mn}L\varepsilon^{-2})$ incremental first-order oracle (IFO) calls and ${\mathcal O}({L\varepsilon^{-2}}/{\sqrt{1-\lambda_2(W)}}\,)$ communication rounds to find an $\varepsilon$-stationary point in expectation, where $L$ is the smoothness parameter and $\lambda_2(W)$ is the second-largest eigenvalue of the gossip matrix $W$. We can verify both of the IFO complexity and communication complexity match the lower bounds. To the best of our knowledge, DEAREST is the first optimal algorithm for decentralized nonconvex finite-sum optimization.
BibTeX
@misc{luo2022optimal,
  author = {Luo Luo and Haishan Ye},
  title = {{An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization}},
  year = {2022},
  eprint = {2210.13931},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.13931},
}
Figure