Quantile Optimization via Multiple-Timescale Local Search for Black-Box Functions

Jiaqiao Hu (), Meichen Song () and Michael C. Fu ()
Additional contact information
Jiaqiao Hu: Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, Stony Brook, New York 11794
Meichen Song: Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, Stony Brook, New York 11794
Michael C. Fu: Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742; and Institute for Systems Research, University of Maryland, College Park, Maryland 20742

Operations Research, 2025, vol. 73, issue 3, 1535-1557

Abstract: 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 2 d + 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.

Keywords: Simulation; black-box optimization; quantile; local search; stochastic approximation; finite differences; simultaneous perturbation (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0534 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:3:p:1535-1557

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().