Managing Stochastic Noise in Second-Order Optimization

140 concepts109 papers1 proposal

First-order optimization methods like Stochastic Gradient Descent (SGD) and Adam navigate loss landscapes using only local slope information. While robust to the noise introduced by mini-batch sampling, they are blind to the underlying curvature, often struggling in highly non-linear or "ill-conditioned" regions. Second-order methods (such as Newton and Quasi-Newton algorithms) promise to solve this by incorporating the Hessian matrix, allowing them to adapt to the landscape's geometry and accelerate convergence.

However, as noted by James Martens et al., traditional second-order techniques lack robustness in stochastic training environments. When we transition from full-batch to mini-batch training, we introduce structured observation noise that scales with the empirical covariance of the data (Filip de Roos et al.). While first-order methods naturally smooth out this noise over many iterations, second-order methods are highly sensitive to it, frequently leading to erratic updates or catastrophic divergence.

Why Curvature Estimation Amplifies Noise

To understand why second-order methods struggle under stochastic noise, we must look at the dimensionality of the information being estimated. A gradient vector contains $d$ elements, representing the slope along each parameter dimension. In contrast, a Hessian matrix contains $d^2$ elements, capturing how those slopes change relative to one another.

As Chaoxu Zhou et al. explain, estimating curvature in stochastic environments is inherently noisier because the number of components in a Hessian approximation grows quadratically. This massive increase in dimensionality requires significantly more stable information to maintain a reliable estimate.

First-Order (Gradient):  [ ∙ ∙ ∙ ∙ ∙ ]  -> d elements (Linear noise growth)

Second-Order (Hessian):  [ ∙ ∙ ∙ ∙ ∙ ]
                         [ ∙ ∙ ∙ ∙ ∙ ]
                         [ ∙ ∙ ∙ ∙ ∙ ]  -> d² elements (Quadratic noise growth)
                         [ ∙ ∙ ∙ ∙ ∙ ]
                         [ ∙ ∙ ∙ ∙ ∙ ]

Furthermore, practical second-order algorithms rarely compute the exact Hessian. Quasi-Newton methods like L-BFGS approximate curvature by tracking the differences between consecutive gradient vectors:

$$y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$$

In a deterministic setting, $y_k$ cleanly isolates the change in geometry. But in a stochastic setting, the model evaluates $\nabla f(x_{k+1})$ and $\nabla f(x_k)$ on different random mini-batches. As Raghu Bollapragada points out, the resulting difference $y_k$ becomes dominated by sampling noise rather than the true underlying geometry of the loss landscape.

The Breakdown of the Secant Equation

This sampling noise directly attacks the mathematical foundation of quasi-Newton optimization: the secant equation. To guarantee that an optimizer takes a step downward (a descent direction), the approximated Hessian matrix must remain positive definite.

In stochastic regimes, gradient noise frequently violates the strict conditions required to maintain this property (Tiande Guo). When the secant equation is fed noisy gradient differences, the curvature estimate can easily lose positive definiteness. Once this occurs, the algorithm can no longer guarantee valid descent directions, causing the training trajectory to become highly unstable (Erik Berglund et al.).

Additionally, Frank E. Curtis notes that this stochastic variance destroys the "self-correcting" properties that typically allow deterministic quasi-Newton methods to recover from poor local curvature approximations.

The Surprising Asymmetry of Noise Tolerance

Despite these vulnerabilities, recent theoretical insights reveal a critical asymmetry in how noise impacts optimization. While it seems intuitive that an optimizer would require equally clean gradients and Hessians, the system is fundamentally more tolerant to noise in its second derivatives than its first derivatives.

Artem Agafonov et al. demonstrated that gradient noise and Hessian noise propagate through optimization algorithms at entirely different rates:

  • Gradient Noise: Impacts the convergence rate at a scale of $\mathcal{O}(1/\sqrt{T})$.
  • Hessian Noise: Decays significantly faster, at a scale of $\mathcal{O}(1/T^2)$.

This mathematical asymmetry means that while noisy gradients can permanently slow down or derail convergence, the optimization framework can tolerate highly inaccurate, noisy Hessian estimates without degrading the final convergence rate. This insight provides a theoretical justification for using much smaller batch sizes to estimate second-order curvature than to estimate first-order gradients, drastically reducing computational overhead.

Paradigms for Denoising Curvature

To exploit the benefits of second-order optimization without falling victim to gradient variance, modern research focuses on several key stabilization mechanisms.

Hessian Averaging

Instead of treating each mini-batch Hessian estimate as an isolated snapshot, algorithms can maintain a running average of past curvature estimates. As shown by Sen Na et al., this running average effectively "denoises" the second-order information over time, allowing stochastic Newton methods to achieve fast superlinear convergence without requiring massive batch sizes.

Batch Overlapping and Progressive Batching

To fix the issue of noisy gradient differences in quasi-Newton updates, Albert S. Berahas et al. introduced a multi-batch approach that calculates updates using the explicit overlap between consecutive data subsets. By evaluating both gradients on a shared set of samples, the sampling noise cancels out, ensuring that $y_k$ reflects true geometric changes. Complementing this, progressive batching strategies dynamically increase the mini-batch size as training progresses, naturally suppressing noise as the model nears the minimum (Raghu Bollapragada).

Soft Constraints and Damping

Rather than forcing the Hessian approximation to strictly satisfy a noisy secant equation, "soft" quasi-Newton methods relax this constraint. By softening the optimization objective, the algorithm guarantees positive definiteness even when subjected to highly volatile gradient evaluations (Erik Berglund et al.). Similarly, incorporating explicit damping factors and variance-reduction techniques prevents the optimizer from overreacting to sudden spikes in local noise (Donald Goldfarb et al.).

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 114 papers
  2. Version 1 · 2026-10-04 · 218 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_gradient_noise_sensitivity_f9abfdb0,
  title = {stochastic gradient noise sensitivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-gradient-noise-sensitivity/rdr_f9abfdb0f36641ae8cbcbf5162565f75},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_stochastic_gradient_noise_sensitivity_f9abfdb0_v2,
  title = {stochastic gradient noise sensitivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-gradient-noise-sensitivity/rdr_f9abfdb0f36641ae8cbcbf5162565f75/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake