# High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 52 references that are in the map.
- First posted on arXiv 17 Jan 2024.

## Builds on (most cited first, 23 of 23)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [An Efficient Framework for Clustered Federated Learning](https://mlsanity.com/paper/2006.04088/) (2020)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [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)
- [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)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Statistical inference using SGD](https://mlsanity.com/paper/1705.07477/) (2017)
- [Statistical Inference for Online Decision Making via Stochastic Gradient Descent](https://mlsanity.com/paper/2010.07341/) (2020)
- [Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods](https://mlsanity.com/paper/2102.03389/) (2021)
- [HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation](https://mlsanity.com/paper/1802.04876/) (2018)
- [Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming](https://mlsanity.com/paper/2205.13687/) (2022)
- [Acceleration of stochastic gradient descent with momentum by averaging: finite-sample rates and asymptotic normality](https://mlsanity.com/paper/2305.17665/) (2023)
- [Weighted Averaged Stochastic Gradient Descent: Asymptotic Normality and Optimality](https://mlsanity.com/paper/2307.06915/) (2023)
- [ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm](https://mlsanity.com/paper/2008.12690/) (2020)
- [Covariance Estimators for the ROOT-SGD Algorithm in Online Learning](https://mlsanity.com/paper/2212.01259/) (2022)
- [TDOA-based Localization via Stochastic Gradient Descent Variants](https://mlsanity.com/paper/1807.04824/) (2018)

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

- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [Federated Learning of Quantile Inference under Local Differential Privacy](https://mlsanity.com/paper/2509.21800/) (2025)
- [Statistical Inference for Stochastic Gradient Descent: Beyond Finite Variance](https://mlsanity.com/paper/2605.26000/) (2026)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization](https://mlsanity.com/paper/2604.04218/) (2026)
- [Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction](https://mlsanity.com/paper/2604.21203/) (2026)
- [A Viscosity Semigroup Framework for Stable Image Reconstruction](https://mlsanity.com/paper/2606.20620/) (2026)
- [Finite-Sample Distribution Theory and Efficient Large-Scale Inference for Online Quantile Regression](https://mlsanity.com/paper/2610.05869/) (2026)

## Abstract (arXiv)

Uncertainty quantification for estimation through stochastic optimization solutions in an online setting has gained popularity recently. This paper introduces a novel inference method focused on constructing confidence intervals with efficient computation and fast convergence to the nominal level. Specifically, we propose to use a small number of independent multi-runs to acquire distribution information and construct a t-based confidence interval. Our method requires minimal additional computation and memory beyond the standard updating of estimates, making the inference process almost cost-free. We provide a rigorous theoretical guarantee for the confidence interval, demonstrating that the coverage is approximately exact with an explicit convergence rate and allowing for high confidence level inference. In particular, a new Gaussian approximation result is developed for the online estimators to characterize the coverage properties of our confidence intervals in terms of relative errors. Additionally, our method also allows for leveraging parallel computing to further accelerate calculations using multiple cores. It is easy to implement and can be integrated with existing stochastic algorithms without the need for complicated modifications.