On the Convergence Properties of a K-step Averaging Stochastic Gradient Descent Algorithm for Nonconvex Optimization

Fan Zhou, Guojing CongIJCAI 2018 · DOI

TL;DR

This paper introduces K-AVG, a novel synchronous stochastic gradient descent (SGD) algorithm that improves upon traditional parallel SGD by introducing a "K-step delay" for averaging. They demonstrate that K-AVG offers better scalability and allows for larger step sizes than asynchronous SGD (ASGD) for nonconvex optimization problems, leading to faster convergence and improved accuracy in experiments.

What Problem Does This Paper Address?

Training large-scale machine learning models often requires distributed computing to handle massive datasets and complex models. Stochastic Gradient Descent (SGD) is a cornerstone optimization algorithm, but its sequential nature makes it slow for such tasks. Parallel and distributed versions of SGD, like synchronous SGD (sSGD) and asynchronous SGD (ASGD), have been developed to speed up training. However, sSGD can suffer from communication overhead due to frequent synchronization, while ASGD, despite reducing communication, can lead to convergence issues due to gradient staleness and requires very small learning rates for theoretical guarantees, which are often impractical. This paper aims to bridge this gap by proposing a new synchronous approach, K-AVG, that balances communication efficiency with convergence guarantees for nonconvex objectives.

Methods

The core of this paper is the introduction and analysis of the K-step Averaging Stochastic Gradient Descent (K-AVG) algorithm. K-AVG is a synchronous algorithm where multiple "learners" (e.g., GPUs) compute their gradients and update their local parameters for K steps. After these K local updates, the parameters are averaged across all learners through a global reduction, and this averaged parameter is then used to update all learners. This "K-step delay" is the key innovation.

The authors provide theoretical convergence analysis for K-AVG under standard assumptions for nonconvex optimization, including Lipschitz continuity of the gradient and bounded variance of stochastic gradients. They derive upper bounds on the expected average squared gradient norms and establish convergence rates. A significant part of their analysis focuses on understanding the impact of the parameter K (the delay) and the number of processors P on convergence and scalability.

Datasets

The experiments were conducted using the CIFAR-10 dataset. This dataset is described as containing 50,000 training images and 10,000 test images, with each image belonging to one of 10 possible labels.

Key Insights and Ideas

  • The "K-step delay" is crucial: Contrary to the intuition that more frequent synchronization (smaller K) is always better, the paper shows that an optimal K often exists and can be greater than 1, especially for nonconvex problems. This delay allows for more computation between communication steps, improving efficiency.
  • K-AVG offers better scalability than ASGD: The theoretical analysis and experimental results demonstrate that K-AVG scales better with the number of processors (P) compared to ASGD, which can suffer from performance degradation as P increases.
  • Larger step sizes are possible with K-AVG: K-AVG's averaging mechanism acts as a form of variance reduction, allowing for larger learning rates than typically feasible with ASGD, which can lead to faster convergence.
  • Optimal K is not always 1: The paper challenges the common assumption that K=1 (hard synchronous SGD) is optimal. They show that for nonconvex problems, a larger K can be beneficial, and the optimal K depends on factors like the initial distance to the solution and the Lipschitz constant of the objective function.

Key Results

  • Improved Test Accuracy: In experiments on CIFAR-10 with two neural network architectures (vgg and nin), K-AVG consistently achieved better test accuracies than two popular ASGD implementations (Downpour and EAMSGD).
  • Significant Speedups: K-AVG demonstrated considerable speedups over ASGD implementations, especially as the number of learners (P) increased. For example, with 128 GPUs, K-AVG was up to 2.6 times faster than ASGD.
  • Scalability: K-AVG showed better scaling with the number of learners (P) compared to ASGD. While ASGD accuracies degraded significantly at P=128, K-AVG maintained high accuracies.
  • Optimal K Analysis: Experiments revealed that the optimal K for K-AVG is often not 1. For the "vgg" network, Kopt ranged from 2 to 32, and for "nin," it was often 1 but sometimes higher (e.g., K=8 showed a slight improvement). The optimal K was found to be sensitive to the number of learners (P) and the specific network architecture.

Limitations and Future Work

  • Unknown Optimal K: The paper acknowledges that the optimal value of K (K) depends on unknown quantities like the Lipschitz constant (L), the variance bound (M), and the initial distance to the optimum (F(w1) - F). This makes finding a concrete K* in practice challenging.
  • Hyperparameter Tuning: While K-AVG offers more flexibility in step sizes and K, finding the optimal combination of these hyperparameters might still require careful tuning.
  • Future Work: The authors suggest that their analytical explanation of Kopt's dependence on other parameters can serve as a guide for practitioners. Further exploration into more adaptive strategies for choosing K or developing methods to estimate Kopt more directly would be valuable. The paper also hints at the potential for K-AVG to be applied to other optimization problems beyond image recognition.

Summary updated

BibTeX
@inproceedings{zhou2018convergence,
  author = {Fan Zhou and Guojing Cong},
  title = {{On the Convergence Properties of a K-step Averaging Stochastic Gradient Descent Algorithm for Nonconvex Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/447},
}
Figure