stat.MLNov 10, 2026

Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling

Authors: Yilin Zheng, Haowei Wang, Wenjia Wang, Szu Hui Ng

Organizations: National University of Singapore, Singapore

Abstract

Simulation optimization typically returns a single estimated optimal point. When decisions also depend on criteria evaluated independently of simulation, such as resource cost, the decision maker instead needs the set of designs whose expected performance lies within a tolerance of the optimum, often choosing the tolerance only after seeing the tradeoffs. We study how to identify these near-optimal regions on a continuous design space, simultaneously for all tolerances up to a prescribed maximum TT, with region estimation error at most ηη. We show that region identification is not a by-product of optimization. Specifically, when α>να>ν, any procedure, even one given the optimal design in advance, needs at least Ω(η−(2+d/ν)min⁡{1,KTd/α})Ω\bigl(η^{-(2+d/ν)}\min\{1,KT^{d/α}\}\bigr) simulation evaluations, where dd is the dimension, νν the smoothness, and (K,α)(K,α) the covering parameters that describe the geometry of the near-optimal designs. We propose SASORI, which returns an estimated optimal point and the regions for all tolerances from the same evaluations, matching this lower bound up to logarithmic factors. SASORI also achieves the optimal tradeoff between region estimation error and cumulative regret, and reduces to a minimax-optimal simulation optimization procedure at zero tolerance. Numerical experiments illustrate the effectiveness of our proposed method.

Figures & tables

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Oct 13, 2026

Principled Design of Expected Improvement for Continuous Simulation Optimization

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.
Apr 27, 2026

Stochastic simultaneous optimistic optimization

We study the problem of global maximization of a function f given a finite number of evaluations perturbed by noise. We consider a very weak assumption on the function, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global maxima. Compared to previous works on bandits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.
Oct 28, 2026

Robust Active Learning for More Efficient and Reliable Paths to Optimal Design

Simulation-driven design optimization requires active learning strategies that efficiently combine models with different computational costs and levels of fidelity. We introduce Multifidelity Cost-Aware Screening (MF-CAS), which enables the joint selection of sampling location and fidelity using a surrogate that provides decomposed uncertainty intervals rather than a complete predictive probability distribution. MF-CAS exploits the contribution of each fidelity to the high-fidelity uncertainty together with its computational cost to determine whether a candidate should first be evaluated at low fidelity or directly progressed towards high fidelity. The method is assessed on the constrained 14-dimensional hydrodynamic optimization of the DTMB 5415 hull under a deliberately limited computational budget. MF-CAS achieves an approximately 9.0% resistance reduction, compared with 6.7% for the best baseline optimisation method, demonstrating that incorporating fidelity-resolved uncertainty directly into the joint location-fidelity decision can substantially improve multifidelity active learning efficiency.