High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization
This provides a cost-effective solution for practitioners needing reliable confidence intervals in online settings, though it is incremental as it builds on existing stochastic algorithms.
The paper tackles the problem of uncertainty quantification for online stochastic optimization by introducing a method to construct confidence intervals with minimal computational overhead, achieving approximately exact coverage with an explicit convergence rate.
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.