First-order optimization methods like Stochastic Gradient Descent (SGD) are the workhorses of deep learning, but they struggle on ill-conditioned loss landscapes—valleys where the surface is highly steep in some directions and gently sloping in others. Second-order methods, such as Quasi-Newton algorithms (BFGS and L-BFGS), solve this by estimating local curvature (the Hessian matrix) to scale updates appropriately across different dimensions.
However, translating these methods to a stochastic setting introduces a fundamental breakdown.
The Curvature Dilemma in Stochastic Optimization
In a deterministic setting, Quasi-Newton methods approximate the Hessian by tracking how the gradient changes across parameter updates. They rely on the secant equation, which uses the difference between two consecutive gradients:
$$y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$$
When we transition to large-scale machine learning, we must use stochastic mini-batches instead of the full dataset. If we naively compute the gradients using two different random mini-batches, $B_k$ and $B_{k+1}$, our gradient difference becomes:
$$y_k = g(x_{k+1}; B_{k+1}) - g(x_k; B_k)$$
By expanding this equation, we can see exactly why it fails:
$$y_k = \underbrace{\left[ g(x_{k+1}; B_{k+1}) - g(x_k; B_{k+1}) \right]}_{\text{True Geometric Curvature}} + \underbrace{\left[ g(x_k; B_{k+1}) - g(x_k; B_k) \right]}_{\text{Sampling Noise}}$$
The second term represents the variance introduced purely by changing the data samples. In practice, this sampling noise completely overwhelms the true geometric curvature signal, causing the Hessian approximation to degrade, destabilize, or diverge entirely. To fix this, researchers have developed mechanisms to ensure sample consistency, isolating the true geometry of the loss surface from data-dependent noise.
The Identical Batch Solution
The most direct way to isolate geometric curvature from stochastic noise is to enforce absolute sample consistency. If we evaluate both gradients at $x_k$ and $x_{k+1}$ using the exact same mini-batch $B_k$, the sampling noise term drops to zero.
This elegant mechanism was leveraged by Nicol N. Schraudolph et al. in A Stochastic Quasi-Newton Method for Online Convex Optimization to develop online variants of BFGS. By computing gradient differences on identical data samples, the data-dependent noise cancels out perfectly, allowing the optimization trajectory to be guided by the underlying geometry of the objective function rather than sample-specific variance.
The necessity of this consistency is a recurring theme across stochastic second-order frameworks:
- Optimization Stability: Alejandro Ribeiro et al. implemented this two-point evaluation strategy in RES: Regularized Stochastic BFGS Algorithm to ensure that the observed difference in gradients is strictly a result of the parameter update rather than variance introduced by different data samples.
- Probabilistic Sampling: In the domain of Markov Chain Monte Carlo (MCMC), Umut Simsekli et al. demonstrated in Stochastic Quasi-Newton Langevin Monte Carlo that maintaining data consistency across gradient pairs is essential to prevent batch-induced noise from degrading the quality of the approximated Hessian.
- Step-Size Tuning: Beyond standard optimization, this concept can also be used to dynamically tune hyperparameters. Camille Castera et al. in Second-Order Step-Size Tuning of SGD for Non-Convex Optimization processed the same mini-batch twice at different parameter positions within a single iteration to isolate geometric curvature, using it to automatically fine-tune SGD step sizes via a stochastic Barzilai-Borwein method.
Overlap-Based Curvature Estimation
While evaluating identical batches provides a clean mathematical cancellation of noise, it introduces a practical bottleneck: it requires extra gradient evaluations or prevents the algorithm from utilizing fresh data at every step. In distributed or streaming environments, forcing full sample identity across iterations can be highly restrictive.
To solve this, researchers introduced the concept of overlap-based curvature estimation. Instead of requiring fully identical batches, the algorithm ensures that consecutive batches share a significant subset of data, and computes the curvature update exclusively on this intersection.
Iteration k: [--- Batch B_k ---]
Iteration k+1: [--- Batch B_k+1 ---]
|_____|
Overlapping Subset
(Curvature computed only on this intersection)
Albert S. Berahas et al. pioneered this in A Multi-Batch L-BFGS Method for Machine Learning. In their framework, the primary optimization step can move forward using a new batch of data, but the curvature correction pairs are calculated using gradients derived only from the overlapping subset of the consecutive batches. This allows the method to maintain stable second-order approximations without sacrificing the ability to ingest fresh data. The authors extended this concept to distributed and asynchronous settings in A robust multi-batch L-BFGS method for machine learning, showing that computing updates on the overlapping subset makes the algorithm resilient to changes in batch composition across unreliable nodes.
This strategy is highly effective across various scales of optimization:
- Progressive Batching: Raghu Bollapragada et al. utilized overlapping data batches in A Progressive Batching L-BFGS Method for Machine Learning, demonstrating that ensuring a substantial data overlap drastically reduces sampling noise in the resulting Hessian approximation.
- Asynchronous Systems: In large-scale non-convex optimization, Umut Simsekli et al. in Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization and Umut Şimşekli et al. in Asynchronous stochastic Quasi-Newton MCMC for non-convex optimization supplementary document split data subsamples into standard and overlapping segments. By evaluating gradients on the overlapping portion across consecutive iterations, they maintained mathematically consistent curvature estimates despite the stochastic nature of asynchronous mini-batch selection.
Decoupled and Large-Batch Stabilization
An alternative way to achieve stochastic curvature stability is to decouple the gradient updates from the curvature updates entirely, adjusting their respective batch sizes and evaluation frequencies.
As detailed in a comprehensive review by Tiande Guo et al. in An Overview of Stochastic Quasi-Newton Methods for Large-Scale Machine Learning, decoupled curvature estimation uses smaller, frequent mini-batches to compute the descent direction, but larger, less frequent batches to compute the Hessian approximations. This separation ensures that the second-order updates are insulated from the high-frequency noise of standard stochastic sampling.
This approach builds on foundational insights from Hessian-free optimization. James Martens demonstrated in Deep learning via Hessian-free optimization that curvature-stable mini-batching requires significantly larger data samples during the second-order calculation phase to prevent the optimization trajectory from being derailed by stochastic noise.
Taking this concept to its logical conclusion, Hiroyuki Kasai et al. integrated variance reduction into this paradigm in Riemannian stochastic quasi-Newton algorithm with variance reduction and its convergence analysis. Instead of updating the Hessian approximation at every stochastic step, the authors update it at the epoch level using full-gradient estimates from a Stochastic Variance Reduced Gradient (SVRG) framework. This periodic synchronization prevents the accumulation of noise in the quasi-Newton memory, ensuring that the search direction remains geometrically reliable throughout the entire optimization process.
Key Foundational Work
A Stochastic Quasi-Newton Method for Online Convex Optimization (2007) — contributed 2 concept elements to this direction.
Deep learning via Hessian-free optimization (2010) — contributed 1 concept elements to this direction.