# Quantile Optimization via Multiple Timescale Local Search for Black-box Functions

arXiv: https://arxiv.org/abs/2308.07607 · HTML: https://mlsanity.com/paper/2308.07607/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2023.

## Built on by (most cited first, 4 of 4)

- [A New Stochastic Approximation Method for Gradient-based Simulated Parameter Estimation](https://mlsanity.com/paper/2503.18319/) (2025)
- [Pure Exploration via Frank-Wolfe Self-Play](https://mlsanity.com/paper/2509.19901/) (2025)
- [Stochastic Approximation Methods for Distortion Risk Measure Optimization](https://mlsanity.com/paper/2510.04563/) (2025)
- [Long-Run Conditional Value-at-Risk Reinforcement Learning](https://mlsanity.com/paper/2603.09734/) (2026)

## Abstract (arXiv)

We consider quantile optimization of black-box functions that are estimated with noise. We propose two new iterative three-timescale local search algorithms. The first algorithm uses an appropriately modified finite-difference-based gradient estimator that requires 2d + 1 samples of the black-box function per iteration of the algorithm, where d is the number of decision variables (dimension of the input vector). For higher-dimensional problems, this algorithm may not be practical if the black-box function estimates are expensive. The second algorithm employs a simultaneous-perturbation-based gradient estimator that uses only three samples for each iteration regardless of problem dimension. Under appropriate conditions, we show the almost sure convergence of both algorithms. In addition, for the class of strongly convex functions, we further establish their (finite-time) convergence rate through a novel fixed-point argument. Simulation experiments indicate that the algorithms work well on a variety of test problems and compare well with recently proposed alternative methods.