Abstract
We propose AMSVRG (Accelerated efficient Mini-batch SVRG), an optimization method for minimizing finite sums of smooth convex functions. By integrating Nesterov’s Accelerated Gradient Descent (AGD) with Stochastic Variance Reduced Gradient (SVRG) and employing a strategically increasing mini-batch size, AMSVRG achieves state-of-the-art convergence rates. It is particularly effective for general convex problems and "optimal strongly convex" functions, outperforming standard stochastic methods in regimes with low regularization.
The Challenge of Finite Sum Optimization
In machine learning, Empirical Risk Minimization (ERM) typically involves minimizing a finite sum of functions representing individual data points. While Stochastic Gradient Descent (SGD) is the standard tool for these problems, its inherent variance leads to slow, sublinear convergence.
Variance reduction techniques like SVRG and SAGA provide linear convergence but often require the objective to be strongly convex. Many practical problems, such as Lasso or logistic regression with low regularization, do not meet this strict requirement. AMSVRG addresses this gap, providing acceleration and variance reduction for a broader class of convex functions and a relaxed condition known as "optimal strong convexity."
The AMSVRG Method
AMSVRG combines three critical elements to achieve its performance:
- Acceleration: A three-sequence update rule based on Nesterov’s acceleration (convex combination, gradient descent, and mirror descent steps).
- Variance Reduction: Periodic full-gradient "snapshots" to correct stochastic noise, following the SVRG framework.
- Increasing Mini-batches: A dynamic mini-batch size that grows within each stage. This stabilizes the accelerated path against stochastic noise as the algorithm nears the optimum.
The theoretical advantages of this approach are summarized in the table below, showing how AMSVRG matches or exceeds the complexity of existing state-of-the-art algorithms across various convexity conditions.
Experimental Results
The algorithm was evaluated on benchmark datasets (mnist, covtype, and rcv1) using $L_2$-regularized logistic regression. The experiments specifically tested performance as the regularization parameter $\lambda$ decreased toward zero, a regime where standard methods often struggle.
As shown in the empirical plots, AMSVRG (particularly variants R1 and R3) demonstrates significantly faster convergence than SVRG and SAGA, especially when $\lambda$ is very small ($10^{-7}$ or $0$). This confirms the algorithm's ability to maintain acceleration even in the absence of strong convexity.
Key Insights and Limitations
- Optimal Strong Convexity: AMSVRG is specifically designed to exploit conditions where functions grow quadratically relative to the set of optimal solutions, rather than a single point.
- Noise Management: The increasing mini-batch size is the "secret sauce" that allows acceleration to remain stable despite the noise inherent in stochastic gradients.
- Scalability: The mini-batch structure makes AMSVRG naturally suited for parallelization on multi-core systems.
- Future Work: Challenges remain in automating parameter tuning (such as initial mini-batch size) and optimizing the algorithm for extremely sparse datasets where accelerated updates can increase computational density by "filling in" sparse vectors.
Summary updated