CS Paper Radar

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

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

cs.LG stat.ML ·submitted 2026-11-10 03:03 UTC · v1
theory

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 $T$, 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 $Ω\bigl(η^{-(2+d/ν)}\min\{1,KT^{d/α}\}\bigr)$ simulation evaluations, where $d$ is the dimension, $ν$ the smoothness, and $(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.

Closest papers

Nearest neighbours by meaning across the whole index.

Principled Design of Expected Improvement for Continuous Simulation Optimization

cs.LG stat.ML ·2026-10-13 ·Songhao Wang, Jianglin Xia, Haowei Wang, Szu Hui Ng
theory similarity 0.65
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.

0.27

Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime

cs.LG stat.ML ·2026-10-05 ·Yujie Liu, Vincent Y. F. Tan, Yunbei Xu
theory similarity 0.64
Abstract

We study the sampling allocation of LinUCB in the small-gap regime, where the reward gaps are of order at most $n^{-1/2}$ over the decision horizon $n$. This scaling captures the hard instances underlying worst-case regret lower bounds, for which LinUCB is known to be near optimal up to logarithmic factors in $n$. Using a mean-field perspective, we characterize this allocation through the empirical sampling distribution, a macroscopic object that averages the effect of adaptive decisions over the horizon, and identify its limit as $n\to\infty$. We establish that in this regime, the empirical sampling distribution induced by LinUCB converges to the set of D-optimal designs. This central result reveals that, in the small-gap regime, LinUCB not only achieves near optimal minimax regret but also allocates samples in a way that is asymptotically efficient for learning the reward parameter, thereby connecting regret-driven online learning with information-efficient experimental design. Building on the optimal design limit, we obtain two useful consequences. First, we refine the asymptotic regret analysis of LinUCB in the small-gap regime by characterizing its leading-order constant in the limit. Second, we show that, despite LinUCB's adaptive sampling strategy, the regularized least-squares estimator satisfies a central-limit-type theorem in the small-gap regime, thereby enabling valid statistical inference for the reward parameter.

0.27

Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

cs.LG stat.ML ·2026-10-14 ·Haowei Wang, Yilin Zheng
theoryhot direction similarity 0.59
Abstract

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $ν$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-ν/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $Ω(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $Θ(N^{-ν/d})$ for both discrete and continuous implementations.

0.28

Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs

cs.LG math.OC ·2026-10-13 ·Justin Dumouchelle, Shunyu Yao, Beste Basciftci, Thiago Serra
benchmark similarity 0.58
Abstract

Chance-constrained stochastic programs (CCSPs) require solutions that satisfy uncertain constraints with high probability. Standard approaches either embed scenarios directly into optimization by considering sample average approximation (SAA)-based reformulations, growing prohibitively expensive and often failing to find feasible solutions; or employ conservative reformulations that guarantee feasibility but sacrifice objective quality by design. We propose ACCESS (Adaptive Chance-Constrained Exploration via Structured Sampling), a structured sampling framework that decouples optimization from feasibility evaluation. First, high-quality candidate solutions are generated by solving many inexpensive single-scenario subproblems, avoiding sampling directly in the constrained high-dimensional solution space. Second, feasibility is assessed separately via large-scale batched simulation over a massive number of scenarios, which is naturally amenable to GPU parallelism. That reduces the search from a high-dimensional solution space to a two-dimensional parameter space controlling conservatism and scenario diversity; while concentrating on candidates near the feasibility boundary, where high-quality feasible solutions lie. We also introduce a variant, ACCESS($δ$), which provides certified feasibility guarantees with probability $1-δ$. Experiments across three benchmark classes and five scenario distributions show that ACCESS matches or exceeds the best objective found by any method in nearly every setting, while ACCESS($δ$) is empirically feasible on every instance. The conservative reformulations remain several percent worse in objective, and SAA is frequently infeasible while taking an order of magnitude longer on the harder benchmarks.

0.17

Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling

cs.LG math.OC ·2026-09-05 ·Ioannis Kontoyiannis, Sean Meyn
similarity 0.56
Abstract

This paper addresses a fundamental question in non-convex optimization: \textit{How should a stochastic optimizer allocate computation between global exploration and local exploitation?} We study this question in continuous time, using Langevin dynamics for global exploration and deterministic gradient flow for local exploitation. The simplest algorithm in this class is the best-state Langevin--gradient method: several Langevin trajectories explore the objective landscape, the best state encountered is retained, and a single gradient trajectory then refines this state to high terminal accuracy. Our main objective is to characterize the computational work required to achieve a prescribed accuracy with prescribed confidence. We develop low-temperature approximations for this probably approximately correct (PAC) work--accuracy tradeoff, both for the best-state method and for related Langevin schemes. Global exploration is governed by energy barriers, through spectral-gap and Eyring--Kramers asymptotics. The resulting approximations expose the competing effects of temperature, computational budget, and the number of exploratory trajectories, and quantify their dependence on the confidence parameter. In contrast, terminal accuracy is largely separated from global exploration: once a suitable region of attraction has been reached, gradient flow requires only $O(\log(1/\varepsilon))$ additional work to reach accuracy at least $\varepsilon$. Numerical experiments on challenging objectives serve to compare algorithms and to test the quantitative predictions of the asymptotic theory. They identify regimes in which the low-temperature approximations provide useful guidance, as well as regimes exhibiting substantial temperature sensitivity and potentially significant high-dimensional limitations.

0.20

High-Probability Regret Bounds for Feel-Good Thompson Sampling

cs.IT stat.MLcs.LG ·2026-10-14 ·Xuheng Li, Qingyue Zhao, Quanquan Gu
similarity 0.56
Abstract · 22 pages

Feel-good Thompson sampling (FGTS) augments the posterior of vanilla Thompson sampling with an exploration term that favors reward functions with high predicted optimal values. This modification achieves minimax-optimal regret up to logarithmic factors in linear contextual bandits, but existing analyses of its two standard variants establish regret guarantees in expectation. In this paper, we derive the first high-probability regret bounds for both cumulative and current-step FGTS in contextual bandits with general realizable function approximation. Our bounds depend on the corresponding decoupling coefficients and the prior mass near the true reward function. In the $d$-dimensional linear setting, both variants satisfy $\mathrm{Regret}(T)=O\big(d\sqrt T\log(2T)+\sqrt T\log(1/δ)\big)$ with probability at least $1-δ$, where $T$ is the time horizon. This bound matches the dimension and horizon dependence of algorithms based on the upper confidence bounds, up to logarithmic factors. Relative to the expected-regret guarantees, the cost of controlling the regret with high probability is confined to additive terms with at most linear dependence on $\log(1/δ)$. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

0.19

Reduced-Space Multi-Fidelity Bayesian Optimization of Process Simulation Models

cs.LG math.OC ·2026-09-15 ·Niki Triantafyllou, Andrea Bernardi, Maria M. Papathanasiou
publishedhot direction similarity 0.56
Abstract · Accepted at the 20th Learning and Intelligent Optimization Conference (LION 20), 2026. Corrected author version. This version corrects a typ…

Optimizing industrial process flowsheets is often computationally prohibitive due to the high cost of rigorous simulations and the curse of dimensionality inherent in complex design spaces. To address these challenges, we present a reduced-space multi-fidelity Bayesian optimization (RS-MFBO) framework designed for high-dimensional, expensive black-box functions. The approach integrates Global Sensitivity Analysis (GSA) for dimensionality reduction with a fidelity-augmented Gaussian process that captures correlations between low-cost approximations and expensive high-fidelity evaluations. A cost-aware acquisition strategy, augmented with cooldown and promotion mechanisms, adaptively guides the allocation of samples across fidelities. The framework is validated on two distinct industrial process simulators: a plasmid DNA bioprocess in SuperPro Designer and a green fuel synthesis plant in Aspen HYSYS. Results across diverse economic and physical objectives demonstrate that the proposed method substantially reduces the number of high-fidelity simulator evaluations while maintaining competitive optimization performance compared to single-fidelity baselines. These results highlight RS-MFBO as a scalable, simulator-agnostic approach for cost-constrained black-box optimization.

0.39

Amortized Thompson Sampling and Efficient Information-Directed Sampling for Simulator-Based Design

cs.LG ·2026-10-23 ·Michal Kobiela, Michael U. Gutmann
similarity 0.55
Abstract

Thompson sampling is a widely used strategy for sequential decision-making under uncertainty, offering a principled way to balance exploration and exploitation. This strategy involves maximizing a target objective under a single sample drawn from the current belief over unknown quantities. Conventionally, this optimization is performed once the belief has been inferred from data, and it becomes computationally burdensome when many Thompson samples are required, especially in continuous action spaces. In this work, we introduce an approach that amortizes this process ahead of time, before any data is collected, so that an approximation of the full Thompson sampling distribution is available immediately once observations arrive. We employ this approach to solve the multi-round setting, involving sequential data acquisition and Thompson-sample recommendation across rounds. Beyond accelerating Thompson sampling, our approach enables efficient estimation of expected information gain about the optimal action. This can be used to select more informative Thompson samples or to obtain maximally informative designs with optimization. Combining this estimate of expected information gain with immediate regret supports information-directed sampling (IDS), which can outperform Thompson sampling by explicitly balancing these two quantities. We demonstrate our approach on two simulator-based design problems in synthetic biology, where the simulators have intractable likelihoods.

0.21