Simultaneous Perturbation-Based Stochastic Approximation For Quantile Optimization

We study a gradient-based algorithm for solving differentiable quantile optimization problems under a black-box scenario. The algorithm finds improved solutions along the descent direction of the quantile objective function, which is approximated at each step using a simultaneous perturbation technique that involves the difference quotient of the output random variables. Compared to existing quantile optimization methods, our algorithm has a two-timescale stochastic approximation structure and uses only three observations of the output random variable per iteration without requiring knowledge of the underlying system model. We show the local convergence of the algorithm and establish a finite-time bound on the convergence rate of the algorithm. Numerical results are also presented to illustrate the algorithm.