Non-Asymptotic Confidence Bounds for Recursive Quantile Estimation
Likai Chen, Georg Keilbar, Wei Biao Wu; 24(91):1−25, 2023.
Abstract
This study explores the use of the stochastic gradient descent (SGD) algorithm with Polyak-Ruppert averaging for recursive estimation of quantiles. The algorithm provides a computationally and memory efficient alternative to the standard empirical estimator. The focus of this research is to analyze the non-asymptotic behavior by presenting exponentially decreasing tail probability bounds, assuming mild assumptions on the smoothness of the density functions. This novel non-asymptotic result is derived from a bound on the moment generating function of the SGD estimate. The findings are applied to the problem of best arm identification in a multi-armed stochastic bandit setting with quantile preferences.
[abs]