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.
Addressing the Practical Flaws of SPIDER
In large-scale machine learning, nonconvex optimization problems—characterized by rugged landscapes with numerous local minima—are common. While Stochastic Gradient Descent (SGD) is widely used, it suffers from high variance due to its single-sample updates. Recent variance reduction methods like SPIDER reached theoretical lower bounds for stochastic first-order (SFO) complexity. However, SPIDER faces two significant practical hurdles:
- The Accuracy-Dependent Stepsize: To guarantee convergence, SPIDER requires a tiny stepsize that scales with the target accuracy $\epsilon$. This "speed limiter" makes the algorithm prohibitively slow in practice.
- Incompatibility with Nonsmoothness: SPIDER cannot natively handle composite problems where a nonsmooth penalty, such as $l_1$ regularization for sparsity, is added to the objective function.
Proposed Methods
The authors introduce three iterations of their approach to solve these issues:
- SpiderBoost: Employs the same recursive gradient estimator as SPIDER but utilizes a much larger constant stepsize ($\eta = 1/2L$). It performs standard gradient descent steps rather than normalized ones.
- Prox-SpiderBoost: Extends the framework to composite optimization using proximal mapping, allowing the algorithm to handle nonsmooth components efficiently.
- Prox-SpiderBoost-M: Integrates a novel momentum scheme. Unlike traditional momentum that often doubles computational costs per step, this scheme uses a "coupled update" sharing a single proximal term.
Key Insights and Theoretical Breakthroughs
The technical innovation enabling a larger stepsize lies in a shift in convergence analysis. Rather than analyzing single iterations, the authors examined cumulative progress over an entire inner loop. This tighter analysis proved stability even with significantly larger steps.
Furthermore, the momentum version achieves efficiency through coupling. By designing updates for internal variables ($x$ and $y$) to depend on the same proximal calculation, the algorithm provides acceleration benefits without the typical 2x computational overhead. This bridges the gap between theoretical optimality and practical runtime.
Experimental Results
The algorithms were benchmarked using standard LIBSVM datasets: a9a (32,561 samples) and w8a (49,749 samples) for logistic and robust linear regression tasks.
Key findings include:
- Theoretical Superiority: Prox-SpiderBoost improves the state-of-the-art SFO complexity for composite nonconvex optimization by a factor of $\mathcal{O}(\min\{n^{1/6}, \epsilon^{-1/3}\})$.
- Practical Speedup: SpiderBoost converged significantly faster than SPIDER. As shown in the figures, SPIDER often "saturated"—oscillating around a point without further progress—while SpiderBoost maintained a rapid descent.
- Momentum Performance: Prox-SpiderBoost-M consistently outperformed high-performance competitors like SVRG, Katyusha, and ASVRG, often being several times faster in nonsmooth $l_1$-regularized tests.
Limitations and Future Work
While the stepsize is constant, the algorithm still requires tuning parameters like epoch length ($q$) and batch size ($|S|$), typically set to $\sqrt{n}$. Automating these choices is a key area for future work. Additionally, extending these boosted variance reduction techniques to decentralized optimization or adversarial min-max problems remains a promising research direction.
Summary updated