Introduction
In modern machine learning, the core optimization task often involves minimizing a "finite sum" of loss functions across $n$ training examples. While Stochastic Gradient Descent (SGD) is widely used, its convergence is hindered by the persistent variance in gradient estimates. Recent variance reduction techniques like SVRG and SAGA have significantly improved convergence rates, particularly for strongly convex problems. However, these methods often fall short in non-strongly convex regimes—common in scenarios with minimal regularization—where they lack the "acceleration" needed for optimal performance.
The AMSVRG Algorithm
This paper introduces AMSVRG (Accelerated Mini-batch Stochastic Variance Reduced Gradient), a unified algorithm designed to provide both variance reduction and Nesterov-style acceleration for both strongly and non-strongly convex problems. AMSVRG integrates three critical components:
- SVRG-based Variance Reduction: Periodically computing full gradients at "snapshot" points to stabilize local mini-batch updates.
- Linear Coupling for Acceleration: Utilizing a modern interpretation of Nesterov’s acceleration that couples gradient descent and mirror descent, making the algorithm easier to analyze and implement.
- Dynamic Mini-batching: Employing a strategy where mini-batch sizes can increase to optimize the computational trade-off between per-iteration cost and progress toward the optimum.
To address the practical challenge of when to transition between stages, the authors propose three restart heuristics (R1, R2, and R3), with R3 (combining fixed iterations with a gradient polarity check) proving particularly robust.
Theoretical Analysis
AMSVRG provides a unified theoretical framework that matches or exceeds the complexity of existing state-of-the-art methods.
As shown in the table above, AMSVRG achieves a complexity of $\tilde{O}(n + \min\{L/\epsilon, n\sqrt{L/\epsilon}\})$ for general convex problems. This is a significant improvement over SAG and SAGA, which scale as $O((n+L)/\epsilon)$. In the strongly convex case, it achieves the optimal accelerated rate of $\tilde{O}(n + \min\{\kappa, n\sqrt{\kappa}\})$.
Empirical Evaluation
The algorithm was tested on three major benchmarks: MNIST (digit recognition), Covtype (forest cover prediction), and RCV1 (newswire classification). The experiments utilized $L_2$-regularized logistic regression, specifically examining how performance changes as the regularization parameter $\lambda$ approaches zero.
The results demonstrate that AMSVRG consistently outperforms SVRG and SAGA, especially in regimes with weak regularization ($\lambda \to 0$). While standard variance reduction methods struggle as the "bowl" shape of the objective function flattens, AMSVRG’s acceleration maintains rapid progress toward the global minimum. On MNIST and Covtype, the R1 and R3 heuristics were most effective, while R2 excelled on the RCV1 dataset.
Conclusion and Limitations
AMSVRG represents a significant step toward a "one-size-fits-all" stochastic optimizer for finite-sum problems. By combining acceleration with variance reduction, it offers superior theoretical guarantees and practical speedups in weakly regularized settings. However, challenges remain regarding hyperparameter tuning (e.g., learning rate and mini-batch parameters) and the technical assumption of bounded iterates in the general convex proof. Future work may explore the parallelization of mini-batch evaluations to further enhance performance in distributed computing environments.
Summary updated