Second-order optimization methods like Newton’s method offer a compelling promise: by using the Hessian (the matrix of second derivatives), they can navigate complex loss landscapes far more efficiently than gradient descent. However, in the "stochastic" regime of modern machine learning—where we compute updates using small batches of data—the Hessian becomes incredibly noisy and expensive to compute.
A growing body of research addresses this by adapting Variance Reduction (VR)—a technique originally designed to stabilize gradients—to the second-order setting. By combining periodic high-fidelity curvature snapshots with efficient incremental updates, these methods achieve the fast convergence of Newton-like algorithms with the sample efficiency required for large-scale learning.
The Core Mechanism: Snapshot and Correction
The fundamental challenge in stochastic second-order optimization is that a Hessian computed on a small batch is often a poor approximation of the true curvature. Standard approaches like Stochastic Cubic Regularized Newton (SCRN) mitigate this with regularization, but still suffer from high variance.
The research direction pioneered by authors like Dongruo Zhou, Pan Xu, and Quanquan Gu introduces a "semi-stochastic" framework. As detailed in Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method, the process follows a nested loop structure:
- The Snapshot (Outer Loop): Periodically, the algorithm computes a full Hessian (or a very large batch) at a reference point. This serves as an "anchor" of high-fidelity information.
- The Correction (Inner Loop): In subsequent steps, the algorithm uses small batches to estimate only the change in the Hessian relative to that anchor.
This correction significantly reduces the variance of the curvature estimate. Because the Hessian typically changes more slowly than the gradient, the "anchor" remains useful for many iterations, allowing for sub-linear scaling with respect to the dataset size $N$.
From Static to Recursive Updates
While early methods like SVRC (Wang et al.) used a fixed reference point for an entire epoch, newer iterations have moved toward recursive strategies.
In Stochastic Recursive Variance-Reduced Cubic Regularization Methods, Zhou et al. demonstrate that updating the Hessian and gradient estimates incrementally at every step—rather than resetting them periodically—leads to even tighter complexity bounds. This "recursive" approach keeps the variance lower throughout the entire optimization trajectory, enabling the algorithm to find second-order stationary points (local minima) with fewer total samples.
Bridging Optimization and Bayesian Inference
A recent and surprising development in this field links these variance reduction techniques to Bayesian principles. Nico Daheim, Thomas Möllenhoff, and Mohammad Emtiyaz Khan show in SVRG and Beyond via Posterior Correction that variance reduction can be viewed as a form of Posterior Correction (PoCo).
By modeling the model's uncertainty as a Gaussian distribution, they prove that correcting the Hessian is equivalent to refining the covariance of that distribution. This theoretical bridge has led to practical new optimizers like IVON-PoCo, which apply these second-order corrections to stabilize the training of massive models like GPT-2, where traditional variance reduction often fails.
Why It Works: Escaping Saddle Points
The primary advantage of these methods over standard SGD is their ability to handle non-convex landscapes. While SGD can get "stuck" near saddle points where the gradient is zero but the surface is not a minimum, second-order methods use curvature information to identify directions of negative curvature and "roll" out of the saddle.
By using variance reduction to make these curvature estimates reliable and computationally affordable, methods like SNPE (Jiang et al.) achieve superlinear convergence rates. They effectively provide the "best of both worlds": the global exploration capabilities of stochastic methods and the surgical precision of Newton's method.