Introduction
This paper introduces Acc-Prox-SVRG, a novel optimization algorithm that combines Nesterov’s acceleration with stochastic variance reduction (SVRG) in a mini-batch setting. By strategically balancing these two techniques, the method achieves a lower theoretical complexity and faster practical convergence than either Accelerated Proximal Gradient (APG) or Prox-SVRG alone.
The Optimization Challenge
In machine learning, practitioners frequently encounter "regularized risk minimization" problems. These take the form $f(x) = g(x) + h(x)$, where $g(x)$ is a smooth average of many individual loss functions (such as the error on each training image) and $h(x)$ is a potentially non-differentiable penalty (like an $L_1$ penalty for sparsity).
Existing optimization tools present a distinct trade-off:
- Proximal Gradient Descent (PGD): Highly stable but computationally expensive because it evaluates every single data point in every step.
- Stochastic Proximal Gradient Descent (SPGD): Fast per step because it evaluates one data point at a time, but suffers from high variance ("noise"), leading to slow overall convergence.
- Prox-SVRG: Reduces the noise and variance to speed up stochastic methods, but lacks "momentum" or acceleration.
- Accelerated Proximal Gradient (APG): Uses Nesterov’s acceleration to speed up deterministic methods but still requires expensive full-batch gradients.
The authors tackle the challenge of creating a "best-of-both-worlds" algorithm that is both stochastic (cheap steps) and accelerated (fast convergence).
The Acc-Prox-SVRG Algorithm
The authors propose Acc-Prox-SVRG (Accelerated Mini-Batch Proximal Stochastic Variance Reduced Gradient). The algorithm operates in distinct stages to maximize efficiency:
- Variance Reduction: At the start of each stage, the algorithm calculates a full gradient at a "snapshot" point. During the stage, it uses small mini-batches to estimate the gradient but corrects them using the snapshot to keep the variance low.
- Nesterov’s Acceleration: Within each stage, it applies an APG-like update rule. It uses a momentum parameter ($\beta_k$) to "overshoot" slightly in the direction of progress, which theoretically speeds up convergence.
- Mini-batching: Unlike standard SVRG, which often uses a single sample, this method uses a mini-batch of size $b$. The authors provide a theoretical framework to determine the optimal $b$ to minimize total computational complexity.
Experimental Setup & Datasets
The algorithm was evaluated on three standard large-scale datasets for $L_1$-regularized multi-class logistic regression.
These datasets vary significantly in their number of features and classes, providing a robust testbed for the algorithm's scalability and performance.
Theoretical Insights & Empirical Results
The Complexity Trade-off
The paper highlights that APG and Prox-SVRG are in a trade-off relationship based on the "condition number" ($\kappa = L/\mu$) and the number of samples ($n$). APG depends more heavily on $\sqrt{\kappa}$, while SVRG depends more on $n$. The key insight is that by choosing an appropriate mini-batch size $b$, one can bridge these two complexities. The authors prove that Acc-Prox-SVRG can achieve a complexity of $O((n + \frac{n\kappa}{n+\sqrt{\kappa}}) \log(1/\epsilon))$, which is superior to the individual rates of its predecessors. Furthermore, because the method uses mini-batches, the gradient evaluations within each batch can be performed in parallel, making it highly suitable for distributed computing environments.
Empirical Performance
In practical experiments, Acc-Prox-SVRG consistently outperformed Prox-SVRG and APG (labeled as AGD in the figures).
The results demonstrate superiority in reducing both the "objective gap" (how far the current solution is from the optimum) and test error rates across all three datasets. Even when the mini-batch size isn't perfectly tuned, the method remains highly competitive with state-of-the-art solvers.
Limitations and Future Work
While highly effective, the algorithm has a few limitations:
- Hyperparameter Sensitivity: The performance is sensitive to the choice of mini-batch size $b$ and the number of iterations per stage $m$. If $b$ is overestimated, the algorithm can perform worse than simpler methods.
- Parameter Tuning: The optimal learning rate $\eta$ and momentum $\beta_k$ depend on knowing the Lipschitz constant $L$ and the strong convexity parameter $\mu$, which are often difficult to estimate in practice.
- Future Directions: The current paper focuses on convex problems. However, many modern machine learning problems (such as deep learning) feature non-convex landscapes. Extending these accelerated variance reduction techniques to non-convex settings remains a major and promising area for future research.
Summary updated