In machine learning, second-order optimization methods like Newton's method are the gold standard for convergence speed. By leveraging the Hessian matrix—the matrix of second derivatives—these algorithms can navigate complex loss landscapes, safely step through saddle points, and adapt to ill-conditioned geometry. Beyond optimization, the Hessian's properties reveal deep insights into model generalization, data memorization, and privacy risks.
However, computing the full Hessian matrix is notoriously expensive. For a model with $d$ parameters, the Hessian contains $d \times d$ entries. When $d$ is in the millions or billions, explicitly calculating, storing, or inverting this matrix becomes completely impossible.
To bypass this bottleneck, a powerful paradigm has emerged: randomized Hessian approximation. Instead of computing the exact high-dimensional matrix, we can use random projections, data subsampling, and stochastic trace estimation to capture the essential curvature of the loss landscape at a fraction of the cost.
The Core Intuition: Effective Dimensionality
Why can we get away with approximating a matrix as massive as the Hessian? The answer lies in its spectrum. In deep neural networks and large-scale optimization problems, the Hessian is rarely full-rank. Instead, its eigenvalues decay rapidly: a few dominant directions capture most of the curvature, while the vast majority of directions are nearly flat.
As Lacotte et al. demonstrate, second-order optimization methods can maintain rapid convergence rates by scaling their computational complexity to this underlying effective dimension rather than the massive ambient dimension of the parameter space. By projecting the Hessian into a lower-dimensional subspace using random matrices, we can compress the problem while preserving its critical geometric features.
Mechanism 1: Stochastic Trace Estimation (Hutchinson's Trick)
Often, we do not need the full Hessian matrix to understand the loss landscape; we only need its trace (the sum of its diagonal entries or eigenvalues). The trace provides a scalar measure of the average curvature or "sharpness" of the local landscape.
To compute the trace without ever building the matrix, we use Hutchinson's estimator. The core mathematical trick relies on choosing a random vector $v$ whose components have zero mean and unit variance (such as a Rademacher or standard Gaussian vector). Because the expectation of the outer product $\mathbb{E}[vv^T]$ equals the identity matrix $I$, we can rewrite the trace of the Hessian $H$ as an expectation:
$$\text{Tr}(H) = \text{Tr}(H \mathbb{E}[vv^T]) = \mathbb{E}[\text{Tr}(Hvv^T)] = \mathbb{E}[v^T H v]$$
This identity means we can estimate the trace by computing the quadratic form $v^T H v$ for a few random vectors $v$.
Crucially, we can compute the vector product $Hv$ without knowing $H$ itself. By applying a finite-difference approximation to the gradient $\nabla f(x)$, we can evaluate $Hv$ using just two gradient computations:
$$H v \approx \frac{\nabla f(x + \epsilon v) - \nabla f(x)}{\epsilon}$$
This simple mechanism makes second-order landscape analysis scalable to massive models:
- Landscape Regularization: Abourayya et al. and Yang et al. use Hutchinson's method to efficiently calculate flatness-aware regularizers, steering models toward wide, generalizable minima during training.
- Adaptive Optimization: Lee et al. integrate stochastic trace estimation to scale gradients adaptively during network quantization, while Chen et al. apply it to regularize over-parameterized models under the Polyak-Łojasiewicz condition.
- Data Diagnostics: Garg et al. and Ravikumar et al. show that computing the input loss curvature via stochastic trace estimation serves as a highly efficient proxy for identifying memorized data points and evaluating privacy vulnerabilities.
Mechanism 2: Hessian Sketching for Optimization
When the goal is optimization rather than landscape analysis, we must solve the Newton step equation $H \Delta x = -g$. To do this efficiently, we can use Hessian Sketching.
We introduce a random sketching matrix $S \in \mathbb{R}^{m \times d}$, where the sketch size $m$ is much smaller than the parameter dimension $d$. By computing the step using the sketched matrix $S H S^T$ or sketching the underlying data matrix, we compress the dimensionality of the linear system.
Wang et al. established a unifying framework showing that applying a Hessian sketch to a primal optimization problem is mathematically equivalent to performing random projection in its dual space. To maximize efficiency, researchers often sketch both the Hessian and the gradient simultaneously. For instance, Wang et al. developed an Iterative Double Sketching framework that dramatically lowers the per-iteration cost of least-squares optimization while maintaining strong convergence guarantees.
To accelerate the sketching process itself, algorithms frequently employ structured random projections like the Subspaced Randomized Hadamard Transform (SRHT). As Li et al. demonstrate in the context of federated learning, using structured sketches compresses high-dimensional curvature information so effectively that communication overhead drops from quadratic to linear relative to model size.
Low-Rank and Spectral Approximations
Another facet of sketching involves building explicit low-rank approximations of the Hessian operator. Rather than random projections alone, methods like the Nyström approximation or randomized Singular Value Decomposition (SVD) are used to isolate the dominant eigenspace.
Zhao et al. introduced NysADMM, which integrates a Nyström-based preconditioner into the ADMM framework. This randomized low-rank approximation flattens the Hessian's spectrum, accelerating convergence uniformly regardless of how ill-conditioned the original data is. Similarly, Li et al. leverage randomized SVD to capture essential curvature information during dataset distillation, and Xu et al. utilize randomized spectral sketching to make gradient projection metrics computationally feasible in a single forward pass during large language model annealing.
Mechanism 3: Subsampling and Row Sampling
Because the empirical Hessian is typically a sum of individual Hessians computed over a dataset ($H = \frac{1}{N} \sum_{i=1}^N H_i$), we can also treat data selection as a form of randomized sketching. Instead of projecting across the parameter space, we sample across the data dimension.
Alain et al. proved that data subsampling can accurately preserve the dominant eigenvalues and spectral properties of the full Hessian, allowing optimizers to safely take larger steps in downward-sloping saddle directions. This strategy is highly effective across diverse domains; for example, Cui et al. utilize a stochastic row-sampling strategy to efficiently train machine learning potentials in computational chemistry, avoiding the cubic complexity of full molecular Hessian evaluations.
By combining data subsampling with randomized linear algebra, frameworks like the one proposed by Marteau-Ferey et al. provide global convergence guarantees for ill-conditioned, self-concordant losses, and Lee et al. demonstrate that empirical risk minimization can be solved in roughly the time it takes to perform a single matrix multiplication.
Summary
Randomized Hessian approximation works because the geometric complexity of machine learning models is highly concentrated. By using Hutchinson's trick to compute traces via directional derivatives, or using sketching matrices to compress optimization steps down to their effective dimensions, these techniques unlock the mathematical power of second-order methods without paying their prohibitive computational price.
Key Foundational Work
Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence (2017) — contributed 2 concept elements to this direction.
Approximate Newton Methods and Their Local Convergence (2017) — contributed 1 concept elements to this direction.
Newton-type methods for non-convex optimization under inexact Hessian information (2017) — contributed 1 concept elements to this direction.