Abstract
Our goal is to improve variance reducing stochastic methods through better control variates. We propose a modification of SVRG, termed SVRG2, which uses the Hessian to track gradients over time rather than recomputing them from scratch. By incorporating second-order information into control variates via a first-order Taylor expansion, we achieve faster theoretical and empirical convergence, particularly near the optimum. We further introduce efficient low-rank approximations to maintain computational feasibility in high-dimensional settings.
Introduction
Stochastic Gradient Descent (SGD) is a staple of modern machine learning, but its performance is often hampered by high variance because it estimates the true gradient using only a small subset of data. Variance reduction techniques like SVRG and SAGA address this by using "control variates"—essentially stale gradients computed at a previous parameter value—to correct the current estimate.
The core challenge is that these stale gradients become increasingly inaccurate as the model parameters move. This loss of correlation leads to higher variance and slower convergence. Traditionally, this is mitigated by recomputing the full gradient frequently, which is computationally expensive. This paper asks: Can we use second-order information (the Hessian) to "update" our stale gradients without recomputing them from scratch?
Methodology: SVRG2 and Hessian Tracking
The authors propose SVRG2, a modification of the popular SVRG algorithm. Instead of using a fixed stale gradient $g_i(\bar{\theta})$ as a control variate, SVRG2 uses a first-order Taylor expansion: $g_i(\bar{\theta}) + H_i(\bar{\theta})(\theta_t - \bar{\theta})$. Here, the Hessian $H_i$ "tracks" how the gradient changes as the current parameters $\theta_t$ move away from the reference point $\bar{\theta}$.
Efficient Approximations
Since computing and storing full $d \times d$ Hessians is prohibitively expensive ($O(d^2)$), the authors introduce several efficient approximations:
- Diagonal Approximations: Using only the diagonal of the Hessian or a "robust secant" approach.
- Low-Rank Approximations: They propose "Curvature Matching" (CM) and "Action Matching" (AM). These methods project the Hessian onto a small $k$-dimensional subspace, keeping the computational cost linear in the number of features $d$.
Crucially, unlike standard second-order methods that use the Hessian to "recondition" the problem (change its geometry), this work uses the Hessian solely to reduce the variance of the gradient estimate. This makes the algorithm much more robust to Hessian approximations because it does not require matrix inversion.
Experimental Results
The methods were evaluated on several standard binary classification datasets from the LIBSVM repository, including a9a, covtype, mushrooms, phishing, w8a, and rcv1-train.
Convergence Performance
In terms of "passes through the data," SVRG2 and its tracking variants consistently outperform standard SVRG. This is clearly visible in the suboptimality plots, where tracking methods reach lower error levels significantly faster than the baseline.
Wall-Clock Efficiency and Stepsize Robustness
While the tracking updates add some overhead, the low-rank "Action Matching" variants (AMgauss and AMprev) proved to be the most efficient in terms of actual time taken, successfully balancing faster convergence with the cost of Hessian-vector products. Furthermore, incorporating Hessian information allows the algorithms to remain stable with larger stepsizes compared to standard SVRG, facilitating faster progress per iteration.
Conclusion
This work demonstrates that using the Hessian for tracking rather than preconditioning provides a robust path to variance reduction. By closing the "smoothness gap"—making convergence depend on average rather than maximum smoothness—SVRG2 offers a significant improvement over first-order methods. Future research will explore extending this tracking framework to other variance-reduced methods like SAGA and investigating the potential of using the Hessian for both tracking and preconditioning simultaneously.
Summary updated