mlsanityData to 14 Oct 2026

Statistical Inference for Online Algorithms

arXiv 2505.17300 ↗First posted 22 May 2025stat.ML cs.LG stat.COcited by 2

Not on the map. Why?

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.

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

38 of 71 references.

References · 38

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  3. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
  4. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  5. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  6. 2022Adam Can Converge Without Any Modification On Update Rulescited by 114
  7. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  8. 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 80
  9. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  10. 2018A Unified Analysis of Stochastic Momentum Methods for Deep Learningcited by 55
  11. 2016Asymptotic Optimality in Stochastic Optimizationcited by 38
  12. 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
26 more
  1. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 35
  2. 2022On Almost Sure Convergence Rates of Stochastic Gradient Methodscited by 35
  3. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
  4. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  5. 2021Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scalingcited by 28
  6. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  7. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  8. 2020Statistical Inference for Online Decision Making via Stochastic Gradient Descentcited by 17
  9. 2021Global Convergence and Stability of Stochastic Gradient Descentcited by 17
  10. 2018A Unified Analysis of AdaGrad with Weighted Aggregation and Momentum Accelerationcited by 15
  11. 2023Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applicationscited by 15
  12. 2021Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methodscited by 14
  13. 2023Asymptotic normality and optimality in nonsmooth stochastic approximationcited by 14
  14. 2019On Constructing Confidence Region for Model Parameters in Stochastic Gradient Descent via Batch Meanscited by 13
  15. 2023Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimatorcited by 13
  16. 2022Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimalitycited by 12
  17. 2022Gradient Descent in the Absence of Global Lipschitz Continuity of the Gradientscited by 11
  18. 2024High Confidence Level Inference is Almost Free using Parallel Stochastic Optimizationcited by 10
  19. 2024An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizescited by 10
  20. 2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 10
  21. 2023Weighted Averaged Stochastic Gradient Descent: Asymptotic Normality and Optimalitycited by 8
  22. 2023Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methodscited by 7
  23. 2021The HulC: Confidence Regions from Convex Hullscited by 6
  24. 2020Asymptotic Analysis of Conditioned Stochastic Gradient Descentcited by 4
  25. 2024A quantitative Robbins-Siegmund theoremcited by 4
  26. 2019First order expansion of convex regularized estimatorscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCAcited by 3
  2. 2026Statistical Inference on Gradient Flowscited by 1