In classical statistics, quantifying uncertainty is often as important as the prediction itself. For a linear model, we can compute confidence intervals by inverting the Hessian matrix of the loss function. However, as models scale to millions or billions of parameters, this "second-order" approach becomes a computational impossibility. Storing a Hessian matrix for a modern neural network would require petabytes of memory, and inverting it would take lifetimes.
A growing body of research suggests a way out: we can perform rigorous statistical inference using only the "first-order" information already produced during training—specifically, stochastic gradients and the trajectory of the optimization process itself.
The Optimization Path as a Statistical Sample
The most intuitive way to bypass the Hessian is to realize that Stochastic Gradient Descent (SGD) does not just find a minimum; it explores the landscape around that minimum.
Liu Liu, Tianyang Li, and Constantine Caramanis demonstrate in Statistical Inference Using SGD that the iterates of SGD with a fixed step size eventually behave like samples from a distribution centered at the true parameter. By averaging segments of this trajectory, they can estimate confidence intervals with the same accuracy as the "Bootstrap"—a gold-standard resampling method—but at a fraction of the cost.
This idea is extended to "fully online" settings by Xi Chen and Wei Biao Wu. In Online Covariance Matrix Estimation in Stochastic Gradient Descent, they show that one can recursively estimate the covariance of the model parameters in real-time. By using a time-varying batch scheme, they achieve $O(d^2)$ complexity, making uncertainty quantification as efficient as the optimization itself.
Simulating Curvature with Finite Differences
If we cannot store the Hessian, can we still use its properties? The Hessian describes how the gradient changes. Therefore, we can approximate the product of a Hessian and a vector (HVP) by looking at the difference between two gradients at slightly different points.
Anastasios Kyrillidis and colleagues apply this in Approximate Newton-based statistical inference using only stochastic gradients. By using finite differences to approximate HVPs, they perform Newton-like statistical inference without ever explicitly forming the second-derivative matrix. Similarly, Ilja Kuzborskij and Yasin Abbasi-Yadkori use Conjugate Gradient algorithms combined with HVPs in Pointwise confidence estimation in the non-linear ℓ2-regularized least squares to calculate pointwise variance for non-linear models. This allows them to provide high-probability bounds that naturally widen when the model encounters unfamiliar data.
Perhaps the most elegant application of this "perturbation" logic is RegVar, introduced by James McInerney and Nathan Kallus. In Variation Due to Regularization Tractably Recovers Bayesian Deep Learning Uncertainty, they show that the shift in a model's prediction when a tiny amount of regularization is added is mathematically equivalent to the Laplace approximation of Bayesian uncertainty. This allows for "deep" uncertainty estimates in models as large as GPT-3 by simply comparing two slightly different training runs.
Structured Approximations for High-Resolution Data
In tasks like image segmentation, the dimensionality is so high that even $O(d^2)$ methods fail. Here, researchers use "diagonal" approximations—treating each parameter or pixel as independent to keep the math linear ($O(d)$).
Marco Miani, Søren Hauberg, and their team developed Laplacian Autoencoders and Laplacian Segmentation Networks to bring Bayesian reliability to computer vision. In Laplacian Segmentation Networks, Kilian Zepf and co-authors use "diagonal backpropagation" to estimate uncertainty in medical images. This approach scales linearly with pixel count, allowing U-Nets to flag out-of-distribution samples that standard models might confidently misclassify.
Cheap Resampling and Parallel Execution
When trajectory analysis isn't enough, resampling remains an option—if done "cheaply." Traditional bootstrapping requires hundreds of model retrainings. Henry Lam and Zitong Wang propose in Resampling Stochastic Gradient Descent Cheaply for Efficient Uncertainty Quantification that as few as three parallel SGD runs can provide valid confidence intervals.
This parallel approach is echoed by Jinlong Lei in Variance-Reduced Accelerated First-order Methods, who proves that accelerated methods like Nesterov's follow a predictable Normal distribution. By running these algorithms in parallel and using "batch-means" analysis, researchers can construct reliable confidence regions without ever touching a Hessian.
Why It Works: The Information is Already There
The unifying insight across these papers is that the information required for statistical inference—the local geometry of the loss surface—is implicitly encoded in the first-order signals we use for training. Whether it is the "noise" in the SGD iterates, the sensitivity of the model to regularization, or the way gradients change over small distances, these signals provide a scalable proxy for the second-order derivatives that were once thought to be essential. By tapping into these existing signals, we can build models that not only predict but also know when they are likely to be wrong.