High Confidence Level Inference is Almost Free using Parallel Stochastic
  Optimization
Wanrong Zhu Zhipeng Lou Ziyang Wei Wei Biao Wu
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.