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.
Paper
Full text
Simultaneous Perturbation-Based Stochastic Approximation For Quantile Optimization
Semantic Scholar · Mathematics · 2023
Abstract
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.