Efficient Decentralized Stochastic Gradient Descent Method for Nonconvex Finite-Sum Optimization Problems

Wenkang Zhan, Gang Wu, Hongchang GaoAAAI 2022 · DOI

Abstract

Decentralized optimization is a cornerstone of modern distributed machine learning, yet it is often hampered by high sample and communication complexities. We present EDSGD (Efficient Decentralized Stochastic Gradient Descent), a novel algorithm designed for nonconvex finite-sum optimization. By integrating hybrid variance reduction with gradient tracking, EDSGD achieves state-of-the-art complexity without requiring costly full gradient (FG) computations.

Addressing the Decentralized Bottleneck

In decentralized learning environments, multiple workers collaborate to train a model by communicating only with their immediate neighbors. While this avoids the bottlenecks of a central server, it introduces significant challenges in convergence speed and efficiency. Existing methods for "finite-sum" problems—where each worker has a fixed local dataset—often rely on periodic "Full Gradient" (FG) calculations. Processing an entire local dataset at once is prohibitively expensive as data scales. Conversely, methods that avoid FG often suffer from high variance in their gradient estimates, leading to slow or unstable convergence.

EDSGD addresses these issues by being "FG-free." It utilizes a sophisticated gradient estimator that maintains high accuracy on every iteration without the need for full-pass computations, bridging the gap between computational efficiency and theoretical convergence speed.

The EDSGD Framework

The core of EDSGD lies in two synergistic mechanisms that allow it to bypass the limitations of traditional stochastic methods:

  1. Hybrid Variance Reduction: The algorithm merges the strengths of SPIDER (efficient tracking of iterative changes) and SAGA (utilization of historical gradient information). This hybrid approach allows for low-variance updates without the computational overhead of periodic full-pass computations.
  2. Gradient Tracking: To ensure all workers converge toward a global optimum rather than local ones, EDSGD uses a tracking variable to estimate the average gradient across the entire network. This is particularly effective in sparse networks where information propagation is slower.
Theoretical complexity comparison of EDSGD against state-of-the-art decentralized methods.

The mathematical foundation of EDSGD is supported by a new Lyapunov function, which proves that the algorithm consistently moves toward a stationary point. As shown in the complexity analysis above, EDSGD achieves a sample complexity of $O(K^{1/2}n^{1/2}/((1-\lambda)\epsilon^2))$, scaling efficiently with both the number of workers ($K$) and the dataset size ($n$). Notably, it maintains this efficiency without the requirement for full gradient evaluations (marked 'X' in the FG column).

Experimental Results

The researchers evaluated EDSGD on a decentralized nonconvex logistic regression task using six standard benchmark datasets: a9a, w8a, ijcnn1, cod-rna, covtype, and MiniBooNE. These datasets range in size from approximately 32,000 to over 580,000 instances, providing a robust test for scalability and dimensionality.

Convergence performance (objective value) of EDSGD across six benchmark datasets.

In head-to-head comparisons with five major baselines—DSGD, DSGDM, HSGD, DGET, and GT-SARAH—EDSGD consistently reached lower objective values significantly faster. On the covtype dataset, for example, EDSGD reached a stable solution in nearly half the number of gradient evaluations required by its closest competitors. Furthermore, the gradient norm dropped more sharply across all tests, confirming the algorithm's stability and precision in finding stationary points.

Conclusion and Future Directions

EDSGD provides a theoretically sound and empirically superior approach to decentralized nonconvex optimization. By eliminating the need for full gradient computations, it removes a major computational bottleneck in large-scale distributed learning.

However, some challenges remain. The algorithm's performance can be sensitive to hyperparameter tuning, particularly the learning rate and variance reduction parameters. Additionally, while the current theory assumes a static network, future work could extend EDSGD to time-varying topologies, making it even more robust for real-world edge computing and mobile applications where connections are often intermittent.

Summary updated

BibTeX
@inproceedings{zhan2022efficient,
  author = {Wenkang Zhan and Gang Wu and Hongchang Gao},
  title = {{Efficient Decentralized Stochastic Gradient Descent Method for Nonconvex Finite-Sum Optimization Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i8.20884},
}
Figure