Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling
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 , 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 simulation evaluations, where is the dimension, the smoothness, and 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
| Method | Recovery (%) | Unclassified (%) | |
|---|---|---|---|
| SASORI-Opt | |||
| SASORI-Joint-Free | |||
| SASORI-Reg | |||
| GP-UCB | |||
| Sobol-GP |
| Method | Recovery (%) | Unclassified (%) | |
|---|---|---|---|
| SASORI-Opt | |||
| SASORI-Joint-Free | |||
| SASORI-Reg | |||
| GP-UCB | |||
| Sobol-GP |
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| Setting | Branin-2 | Hartmann-3 |
|---|---|---|
| Domain | ||
| Objective | ||
| Largest tolerance | ||
| Evaluation tolerances | ||
| Fixed length scale | ||
| Joint-Free region quota |
| Method | Algorithm output: | All observations: |
|---|---|---|
| Opt | ||
| Joint-Free | ||
| Reg | ||
| GP-UCB | ||
| Sobol-GP |
| Method | |||
|---|---|---|---|
| Opt | |||
| Joint-Free | |||
| Reg | |||
| GP-UCB | |||
| Sobol-GP |
| Method | Minutes |
|---|---|
| Opt | |
| Joint-Free | |
| Reg | |
| GP-UCB | |
| Sobol-GP |
| Method | Algorithm output: | All observations: |
|---|---|---|
| Opt | ||
| Joint-Free | ||
| Reg | ||
| GP-UCB | ||
| Sobol-GP |
| Method | |||
|---|---|---|---|
| Opt | |||
| Joint-Free | |||
| Reg | |||
| GP-UCB | |||
| Sobol-GP |
| Method | Minutes |
|---|---|
| Opt | |
| Joint-Free | |
| Reg | |
| GP-UCB | |
| Sobol-GP |
Stochastic Optimization
Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.
See all 222 papers