First-order optimization methods like SGD and Adam are the undisputed workhorses of modern deep learning. They are computationally cheap, requiring only the gradient (the slope) of the loss landscape to make progress. However, first-order methods are fundamentally blind to the local geometry of the landscape. When navigating highly unconditioned "ravines" or landscapes with strongly correlated variables, first-order methods can oscillate wildly or stall completely.
Second-order methods, such as Newton's method, solve this by leveraging the Hessian matrix $\mathbf{H}$—the matrix of second derivatives that describes the local curvature. By multiplying the gradient by the inverse Hessian ($\mathbf{H}^{-1}$), an optimizer can perfectly scale its steps to match the landscape, taking a direct path to the minimum.
The catch is the Curse of the Full Hessian. For a model with $N$ parameters, the Hessian is an $N \times N$ matrix. If a model has just 1 million parameters, its Hessian contains 1 trillion entries. Storing this matrix requires gigabytes of memory, and inverting it takes $O(N^3)$ operations. For modern deep learning architectures, materializing the full Hessian is completely impossible.
The research direction explored here overcomes this bottleneck through a powerful realization: we almost never need to see the entire Hessian matrix explicitly. Instead, we only need to know how the Hessian acts on a specific vector, or we need a lightweight summary of its diagonal. By treating the Hessian as an implicit operator rather than an explicit table of numbers, we can extract second-order benefits at a first-order computational cost.
The Core Insight: Hessian-Vector Products
The fundamental mathematical building block of matrix-free curvature estimation is the Hessian-vector product (Hvp), denoted as $\mathbf{H}\mathbf{v}$, where $\mathbf{v}$ is an arbitrary vector of the same dimension as our parameter space.
As Zhou et al. demonstrate with their regularized Newton method, interacting with the Hessian exclusively through Hvps drops the memory footprint from quadratic ($O(N^2)$) to linear ($O(N)$). This representational shift allows second-order optimization to scale gracefully to high-dimensional problems. Similarly, the library laplax leverages matrix-free curvature representations to scale Bayesian uncertainty quantification to large neural networks, bypassing the prohibitive memory costs of storing full second-order derivative matrices.
But how do we compute $\mathbf{H}\mathbf{v}$ without computing $\mathbf{H}$ first? There are two primary ways to achieve this: automatic differentiation and finite-difference approximations.
Finite Differences: Curvature from Two Points
By definition, the Hessian is the derivative of the gradient. Therefore, the product $\mathbf{H}\mathbf{v}$ is simply the directional derivative of the gradient $\nabla f(\theta)$ along the vector $\mathbf{v}$. We can approximate this using a simple first-order finite difference:
$$\mathbf{H}\mathbf{v} \approx \frac{\nabla f(\theta + \epsilon \mathbf{v}) - \nabla f(\theta)}{\epsilon}$$
To understand why this works intuitively, imagine standing on a hillside. To feel the curvature in direction $\mathbf{v}$, you don't need a full topographic map of the mountain. You simply look at the slope where you are standing ($\nabla f(\theta)$), take a tiny step of size $\epsilon$ in the direction of $\mathbf{v}$, look at the new slope ($\nabla f(\theta + \epsilon \mathbf{v})$), and see how much it changed.
This elegant trick requires exactly two gradient evaluations and zero matrix storage. Klochkov et al. show that computing Hvps via finite differences allows influence functions to scale robustly to 7-billion-parameter language models using standard backpropagation passes.
This mechanism is highly versatile:
- Generative Modeling: Pang et al. replace sequential automatic differentiation steps with independent, parallelizable finite-difference function evaluations to accelerate the training of energy-based models.
- Adversarial Robustness: Ge et al. use finite differences to approximate the gradient of a gradient norm, guiding adversarial examples toward flat local maxima to boost their transferability across different models.
- Meta-Learning: Kedia et al. apply a first-order finite difference to estimate the gradient of the dot product between two batch gradients, achieving linear memory scaling for single-task regularization.
Curvature from the History of Updates
Instead of actively stepping sideways to measure curvature, we can also extract curvature passively by looking at the steps the optimizer already took during normal training.
As an optimizer moves through a loss landscape, it naturally collects a sequence of positions $\theta_t, \theta_{t+1}$ and gradients $\nabla f(\theta_t), \nabla f(\theta_{t+1})$. The difference between successive gradients ($\nabla f(\theta_{t+1}) - \nabla f(\theta_t)$) relative to the difference in positions ($\theta_{t+1} - \theta_t$) provides a running measurement of local curvature along the trajectory.
Position Space: θ_t ───────────────> θ_{t+1} (Step taken)
│ │
▼ ▼
Gradient Space: ∇f(θ_t) ──────────────> ∇f(θ_{t+1}) (Change in slope)
└───────────┬───────────┘
▼
Successive Difference
Approximates Local Curvature
This is the core mechanism behind Quasi-Newton methods like L-BFGS. Guo et al. outline how stochastic quasi-Newton methods store a small history of these recent gradient and position changes to implicitly represent the loss surface's curvature without quadratic memory costs.
This history-driven approach can be utilized in several ways:
- Adaptive Optimization: Yue et al. introduce AGD, an optimizer that uses successive gradient differences to approximate the diagonal of the Hessian matrix on the fly, providing second-order preconditioning at the computational cost of a first-order optimizer.
- MCMC Sampling: In Markov Chain Monte Carlo sampling, Sutton et al. use this history-driven curvature estimation to adaptively tune the mass matrix of Hamiltonian Monte Carlo, achieving second-order sampling efficiency at first-order computational costs.
Statistical and Structural Proxies
When even finite differences or history tracking are too noisy, researchers turn to statistical or structural approximations that substitute the Hessian with cheaper mathematical twins.
The Gradient Outer Product
One common proxy is the outer product of gradients (closely related to the Fisher Information Matrix or the gradient covariance matrix). At a local minimum, the variance of individual sample gradients reflects the underlying shape of the loss basin.
Hoffman leverages this by approximating the average negative Hessian of a target distribution using the outer product of gradients to automatically tune Generalized Hamiltonian Monte Carlo without manual intervention. Similarly, Behrens et al. employ the gradient covariance matrix of training samples as a computationally efficient proxy for the Hessian to analyze the geometry of a network's decision boundary and predict generalization.
Stochastic Perturbations
Alternatively, we can smooth the landscape to estimate curvature. Yu et al. use Gaussian smoothing of gradients—applying random stochastic perturbations to the parameters—to estimate second-order curvature through simple inner products of gradient vectors, completely bypassing the need for explicit Hessian-vector products in bilevel optimization.
Broad Downstream Applications
By making curvature computationally tractable, matrix-free second-order methods unlock capabilities across machine learning that were previously blocked by the $O(N^2)$ wall.
Network Pruning
To prune weights from a neural network without destroying its performance, we need to know which weights are least sensitive to perturbations. Wang et al. use Hessian-gradient products to identify and preserve weights critical for maintaining gradient flow at initialization. For structured pruning, Peng et al. capture complex channel correlations using first-order gradients to solve a massive quadratic pruning problem efficiently.
Influence Functions
Influence functions tell us how a model's predictions would change if a specific training point were removed—a calculation that fundamentally requires multiplying by the inverse Hessian. Lee et al. use inverse Hessian-vector products to efficiently optimize data augmentation networks. To trace the origins of societal bias in word embeddings, Zemel simplifies this calculation by treating the Hessian as block-diagonal, allowing independent updates to individual word vectors and making bias tracing computationally feasible.
Bilevel and Implicit Models
Training models that contain nested optimization loops (such as meta-learning or implicit fixed-point layers) requires differentiating through an optimization path, which introduces higher-order derivatives.
Wiseman et al. utilize fast finite-difference Hvps to avoid the high memory costs of unrolling gradients in semi-amortized VAEs. For implicit models, Geng bypasses the exact Jacobian inverse entirely, replacing it with a lightweight first-order approximation that provides a sufficient ascent direction. Finally, in security analysis, Muñoz-González et al. use Hvps to compute back-gradients for data-poisoning attacks against deep networks without storing long parameter histories.