B1429
Title: Recursive quantile estimation: Non-asymptotic confidence bounds
Authors: Likai Chen - Washington University in Saint Louis (United States) [presenting]
Georg Keilbar - Humboldt-University of Berlin (Germany)
Wei Biao Wu - University of Chicago (United States)
Abstract: The recursive estimation of quantiles is considered using the stochastic gradient descent (SGD) algorithm with Polyak-Ruppert averaging. The algorithm offers a computationally and memory-efficient alternative to the usual empirical estimator. The focus is on studying the non-asymptotic behavior by providing exponentially decreasing tail probability bounds under mild assumptions on the smoothness of the density functions. This novel non-asymptotic result is based on a bound of the moment-generating function of the SGD estimate. We apply our result to the problem of best-arm identification in a multi-armed stochastic bandit setting under quantile preferences.
