SpiderBoost: A Class of Faster Variance-reduced Algorithms for Nonconvex Optimization

Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, Vahid Tarokh

Abstract

SARAH and SPIDER are two recently developed stochastic variance-reduced algorithms, and SPIDER has been shown to achieve a near-optimal first-order oracle complexity in smooth nonconvex optimization. However, SPIDER uses an accuracy-dependent stepsize that slows down the convergence in practice, and cannot handle objective functions that involve nonsmooth regularizers. In this paper, we propose SpiderBoost as an improved scheme, which allows to use a much larger constant-level stepsize while maintaining the same near-optimal oracle complexity, and can be extended with proximal mapping to handle composite optimization (which is nonsmooth and nonconvex) with provable convergence guarantee. In particular, we show that proximal SpiderBoost achieves an oracle complexity of $\mathcal{O}(\min\{n^{1/2}\epsilon^{-2},\epsilon^{-3}\})$ in composite nonconvex optimization, improving the state-of-the-art result by a factor of $\mathcal{O}(\min\{n^{1/6},\epsilon^{-1/3}\})$. We further develop a novel momentum scheme to accelerate SpiderBoost for composite optimization, which achieves the near-optimal oracle complexity in theory and substantial improvement in experiments.

Introduction

In large-scale machine learning, optimization is the primary engine. While Stochastic Gradient Descent (SGD) is the standard workhorse, its high variance often necessitates Variance Reduction (VR) techniques to improve speed and precision. The SPIDER algorithm was a major theoretical breakthrough, achieving near-optimal complexity for nonconvex problems. However, SPIDER faced a significant "speed limit": to guarantee convergence, it required a tiny, accuracy-dependent stepsize that made it slow in real-world applications. This paper introduces SpiderBoost, a framework that removes these constraints, allowing for much larger stepsizes and broader applications without losing theoretical optimality.

The SpiderBoost Framework

The core innovation of SpiderBoost lies in its convergence analysis. By analyzing the progress of the algorithm over an entire "inner loop" (an epoch) rather than step-by-step, the authors proved that a much larger constant stepsize (e.g., $\eta = 1/2L$) can be used while maintaining the same near-optimal complexity as SPIDER.

Algorithm 1 (SpiderBoost) and Algorithm 2 (Prox-SpiderBoost) pseudocode.

The framework introduces three key algorithms:

  • SpiderBoost: The base algorithm for smooth nonconvex optimization.
  • Prox-SpiderBoost: Incorporates proximal mapping to handle composite optimization problems involving nonsmooth regularizers (like $\ell_1$ penalties).
  • Prox-SpiderBoost-M: Adds a novel momentum scheme designed for the proximal setting, using a diminishing momentum coefficient to stabilize the variance-reduced estimator and accelerate convergence.

Theoretical and Practical Advantages

SpiderBoost achieves a Stochastic First-order Oracle (SFO) complexity of $O(n + \sqrt{n}\epsilon^{-2})$, matching the theoretical lower bound for first-order nonconvex optimization. For composite tasks, Prox-SpiderBoost improves the best known SFO complexity result by a factor of $O(\min\{n^{1/6}, \epsilon^{-1/3}\})$.

Practically, the constant stepsize prevents the "saturation" effect seen in SPIDER, where the algorithm would often oscillate or stall around a certain accuracy level. SpiderBoost continues to converge rapidly even as high precision is reached.

Experimental Results

The researchers evaluated their algorithms using the a9a and w8a datasets from the LIBSVM library, testing nonconvex problems such as Logistic Regression with nonconvex regularizers and Robust Linear Regression.

Convergence comparison between SPIDER and SpiderBoost on a9a and w8a datasets.

As illustrated in the experiments, SpiderBoost (red) consistently outperforms SPIDER (black). While SPIDER's fixed tiny stepsize leads to early plateaus, SpiderBoost maintains a steep trajectory toward the minimum. Furthermore, the momentum-enhanced Prox-SpiderBoost-M consistently outperformed other popular algorithms like Prox-SVRG and Prox-SAGA across various benchmarks.

Conclusion

SpiderBoost provides a robust solution to the stepsize limitations of previous variance-reduction methods. By enabling constant-level stepsizes and extending to composite optimization, it offers a theoretically optimal and practically superior framework for modern machine learning tasks. Future work includes scaling these methods to massive deep learning architectures like large-scale CNNs and Transformers.

Summary updated

Abstract

SARAH and SPIDER are two recently developed stochastic variance-reduced algorithms, and SPIDER has been shown to achieve a near-optimal first-order oracle complexity in smooth nonconvex optimization. However, SPIDER uses an accuracy-dependent stepsize that slows down the convergence in practice, and cannot handle objective functions that involve nonsmooth regularizers. In this paper, we propose SpiderBoost as an improved scheme, which allows to use a much larger constant-level stepsize while maintaining the same near-optimal oracle complexity, and can be extended with proximal mapping to handle composite optimization (which is nonsmooth and nonconvex) with provable convergence guarantee. In particular, we show that proximal SpiderBoost achieves an oracle complexity of $\mathcal{O}(\min\{n^{1/2}\epsilon^{-2},\epsilon^{-3}\})$ in composite nonconvex optimization, improving the state-of-the-art result by a factor of $\mathcal{O}(\min\{n^{1/6},\epsilon^{-1/3}\})$. We further develop a novel momentum scheme to accelerate SpiderBoost for composite optimization, which achieves the near-optimal oracle complexity in theory and substantial improvement in experiments.
BibTeX
@inproceedings{wang2019spiderboost,
  author = {Zhe Wang and Kaiyi Ji and Yi Zhou and Yingbin Liang and Vahid Tarokh},
  title = {{SpiderBoost: A Class of Faster Variance-reduced Algorithms for Nonconvex Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=-xdNA5bN4l},
}
Figure