Convergence-Rate-Guided Algorithm Design of Expected Improvement for Continuous Simulation Optimization

arXiv:2610.18434v1 Announce Type: cross Abstract: Expected improvement (EI) based on stochastic kriging (SK) surrogate is widely used in continuous simulation optimization, but unknown heteroscedastic noise on simulation output makes three basic design choices consequential: the incumbent used to define improvement, the replication level at each sampled point, and the terminal recommendation. Existing methods typically either assume the noise levels are known or choose these components separately through heuristic rules or empirical calibration. We instead derive a high-probability upper bound on the simple regret and systematically choose the three components within general rule classes to tighten this bound. We first establish a finite-sample confidence bound for the SK predictor with unknown and estimated noise levels as a foundation for the three design choices. We then analyze general posterior-quantile families for both the incumbent and the terminal recommendation. For the incumbent, minimizing the regret bound selects a lower quantile coefficient that matches the coefficient in the SK predictor confidence bound. For the terminal recommendation, minimizing the same bound instead selects the sampled point with the best upper posterior quantile under the same coefficient. These opposite quantile choices reflect the different roles of search and implementation in simulation optimization. Intermediate simulations are exploratory with an optimistic incumbent, while the terminal recommendation is implemented in the real system and is therefore relatively conservative about the remaining posterior uncertainty. Under mild conditions satisfied by common kernels, minimizing a tractable kernel-specific bound yields $\Theta(\log T)$ replications. To our knowledge, this is the first simple-regret guarantee for a continuous-domain EI-type simulation optimization method that learns unknown heteroscedastic variances through replications.

Abstract:Expected improvement based on stochastic kriging (SK) surrogate is widely used in continuous simulation optimization, but unknown heteroscedastic noise makes three basic design choices consequential: the incumbent to define improvement, replication allocation, and final recommendation. Existing methods typically either assume the noise levels are known or choose these components separately through heuristic rules or empirical calibration. We instead derive a high-probability upper bound on the simple regret and systematically choose the three components within general rule classes to tighten this bound. We first establish a finite-sample confidence bound for the SK predictor as a foundation for the three design choices. Within general posterior-quantile rule classes, tightening the regret certificate selects a lower-quantile incumbent and an upper-quantile recommendation among sampled designs. The opposing quantiles reflect the different roles of exploratory experiments and the final implemented decision. Under mild conditions satisfied by common kernels, minimizing a tractable kernel-specific bound yields a logarithmic replication order. Based on these design choices, the resulting simple regret matches the existing results under known homoscedastic noise up to logarithmic factors. To our knowledge, this is the first simple-regret guarantee of this form for a continuous-domain EI-type simulation optimization method that learns unknown heteroscedastic variances through replications.

Machine Learning (stat.ML); Machine Learning (cs.LG)

arXiv:2610.18434 [stat.ML]

(or arXiv:2610.18434v2 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2610.18434 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Convergence-Rate-Guided Algorithm Design of Expected Improvement for Continuous Simulation Optimization

Related coverage