# HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation

arXiv: https://arxiv.org/abs/1802.04876 · HTML: https://mlsanity.com/paper/1802.04876/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2018.

## Built on by (most cited first, 13 of 13)

- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization](https://mlsanity.com/paper/2401.09346/) (2024)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation](https://mlsanity.com/paper/2410.15057/) (2024)
- [Asymptotic Analysis of Sample-averaged Q-learning](https://mlsanity.com/paper/2410.10737/) (2024)
- [Statistical Inference for Differentially Private Stochastic Gradient Descent](https://mlsanity.com/paper/2507.20560/) (2025)
- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient Descent](https://mlsanity.com/paper/2310.11065/) (2023)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression](https://mlsanity.com/paper/2604.10814/) (2026)
- [Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction](https://mlsanity.com/paper/2604.21203/) (2026)

## Abstract (arXiv)

Stochastic gradient descent (SGD) is an immensely popular approach for online learning in settings where data arrives in a stream or data sizes are very large. However, despite an ever-increasing volume of work on SGD, much less is known about the statistical inferential properties of SGD-based predictions. Taking a fully inferential viewpoint, this paper introduces a novel procedure termed HiGrad to conduct statistical inference for online learning, without incurring additional computational cost compared with SGD. The HiGrad procedure begins by performing SGD updates for a while and then splits the single thread into several threads, and this procedure hierarchically operates in this fashion along each thread. With predictions provided by multiple threads in place, a t-based confidence interval is constructed by decorrelating predictions using covariance structures given by a Donsker-style extension of the Ruppert--Polyak averaging scheme, which is a technical contribution of independent interest. Under certain regularity conditions, the HiGrad confidence interval is shown to attain asymptotically exact coverage probability. Finally, the performance of HiGrad is evaluated through extensive simulation studies and a real data example. An R package texttthigrad has been developed to implement the method.