# Statistical Inference for Online Algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 71 references that are in the map.
- First posted on arXiv 22 May 2025.

## Builds on (most cited first, 30 of 38)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Adam Can Converge Without Any Modification On Update Rules](https://mlsanity.com/paper/2208.09632/) (2022)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [A Unified Analysis of Stochastic Momentum Methods for Deep Learning](https://mlsanity.com/paper/1808.10396/) (2018)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [On exponential convergence of SGD in non-convex over-parametrized learning](https://mlsanity.com/paper/1811.02564/) (2018)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling](https://mlsanity.com/paper/2106.03156/) (2021)
- [Aiming towards the minimizers: fast convergence of SGD for overparametrized problems](https://mlsanity.com/paper/2306.02601/) (2023)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [Statistical Inference for Online Decision Making via Stochastic Gradient Descent](https://mlsanity.com/paper/2010.07341/) (2020)
- [Global Convergence and Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2110.01663/) (2021)
- [A Unified Analysis of AdaGrad with Weighted Aggregation and Momentum Acceleration](https://mlsanity.com/paper/1808.03408/) (2018)
- [Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications](https://mlsanity.com/paper/2312.02828/) (2023)
- [Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods](https://mlsanity.com/paper/2102.03389/) (2021)
- [Asymptotic normality and optimality in nonsmooth stochastic approximation](https://mlsanity.com/paper/2301.06632/) (2023)
- [On Constructing Confidence Region for Model Parameters in Stochastic Gradient Descent via Batch Means](https://mlsanity.com/paper/1911.01483/) (2019)
- [Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator](https://mlsanity.com/paper/2306.02205/) (2023)
- [Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality](https://mlsanity.com/paper/2207.04173/) (2022)
- [Gradient Descent in the Absence of Global Lipschitz Continuity of the Gradients](https://mlsanity.com/paper/2210.02418/) (2022)
- [High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization](https://mlsanity.com/paper/2401.09346/) (2024)

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

- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [Statistical Inference on Gradient Flows](https://mlsanity.com/paper/2606.01257/) (2026)

## Abstract (arXiv)

The construction of confidence intervals and hypothesis tests for functionals is a cornerstone of statistical inference. Traditionally, the most efficient procedures - such as the Wald interval or the Likelihood Ratio Test - require both a point estimator and a consistent estimate of its asymptotic variance. However, when estimators are derived from online or sequential algorithms, computational constraints often preclude multiple passes over the data, complicating variance estimation. In this article, we propose a computationally efficient, rate-optimal wrapper method (HulC) that wraps around any online algorithm to produce asymptotically valid confidence regions bypassing the need for explicit asymptotic variance estimation. The method is provably valid for any online algorithm that yields an asymptotically normal estimator. We evaluate the practical performance of the proposed method primarily using Stochastic Gradient Descent (SGD) with Polyak-Ruppert averaging. Furthermore, we provide extensive numerical simulations comparing the performance of our approach (HulC) when used with other online algorithms, including implicit-SGD and ROOT-SGD.