Related work. Stochastic approximation has been explored in the context of CVaR estimation in [1]}, [2]}. Recursive estimation of quantiles, variances and medians has been considered earlier in [3]}, [4]}, [5]}. UBSR was introduced in [6]}, and non-recursive estimation schemes for UBSR were proposed in [7]}. A paper closely related to our work from UBSR estimation viewpoint is [8]}, which uses a recursive estimation technique. The authors establish asymptotic convergence of their algorithm, and a `central limit theorem' showing the asymptotic Gaussianity of the scaled estimation error. In contrast, we establish non-asymptotic, i.e., finite-sample bounds for the performance of our recursive estimation method, under similar technical assumptions as [8]}, [7]}. [11]}, [12]} consider finite-sample analysis of zeroth order stochastic approximation, but they assume zero-mean noise on the function measurements, which is not the case for UBSR optimization considered here. Other related papers include [13]}, [14]} which consider stochastic approximation of an abstract objective function where the function measurements are biased, and the bias can be controlled through a batch size. In a recent paper [15]}, the authors use the estimation scheme from [7]} to establish concentration inequalities for UBSR estimation.
