CS Paper Radar

Cost-Aware Stopping for Freeze-Thaw Bayesian Optimization: When Does One-Step Lookahead Suffice?

Long Vu, Jongseong Brad Choi, Binoy Ravindran, Zhoulai Fu

cs.LG math.OCstat.ML ·submitted 2026-10-30 17:36 UTC · v1
theory

Abstract

Freeze-thaw Bayesian optimization (BO) evaluates candidates in resumable increments but usually stops at a budget or convergence test. We maximize a budget-free utility, the best observed score minus a cost per increment, with a one-step lookahead: advance the candidate with the largest expected improvement (EI) under a fixed surrogate, and stop once no EI exceeds the cost. This rule, EI stopping, never falls below stopping immediately in expected utility, yet it can stop too early. We construct a certificate, a lower bound on the value of two-step lookahead, that proves such a stop premature, and repeating this correction never lowers expected utility under the surrogate. Under the surrogate, EI stops are premature on average at low costs and lose little at high costs. On three hyperparameter optimization benchmarks, a pre-registered test finds EI stopping noninferior to the correction in most high-cost settings, while the correction gains at low costs on two of the three; more information sharing in the surrogate raises EI stopping's utility. On the surrogates of two published methods, EI stopping trades lower scores for fewer training increments. EI stopping is a simple cost-aware reference whose utility depends on the surrogate.

Closest papers

Nearest neighbours by meaning across the whole index.

Prequential E-Values for Selected-GP Near-Optimality Certificates

cs.LG ·2026-09-30 ·Ami Tavory, Noa Cohen
publishedtheory similarity 0.67
Abstract · 9 pages, 2 figures. Accepted at the NeurIPS 2026 Workshop on E-Values: From Statistics to ML

When optimizing an expensive black-box function sequentially, as in hyperparameter optimization, we may want to stop once the best evaluated value is certified within $\varepsilon$ of the global optimum. Such a certificate needs two ingredients: a lower confidence bound for the selected value and an upper confidence envelope over the domain, typically supplied by a Gaussian process (GP). GP-UCB-style stopping rules are valid when the kernel and constants defining this envelope are fixed before the run, but the practical temptation is to tune the envelope from the same adaptive evaluations and then certify as if it had been fixed. We use prequential e-values to make this selection auditable: starting from a predeclared set of fully specified GP/RKHS envelopes, each candidate is tested by its own one-step-ahead e-process, contradicted candidates are deleted, and certification uses the largest upper bound among the survivors. With a valid selected-point lower bound and one declared candidate having valid latent coverage and noise calibration, the rule is anytime-valid. On a 512-seed noisy RBF stress sweep, it roughly halves false-certification risk at comparable power versus fit-then-certify. Relative to random fixed GP precommitment on smooth $d=3,4$ objectives, each additional false certificate is accompanied by 3.0 and 13.5 additional correct certificates, respectively.

0.33

Work While They Sleep: Exploiting Evaluation Latency for Fully Bayesian Optimization

cs.LG cs.AIstat.ML ·2026-10-06 ·Gustavo Sutter, Alejandro Comas-Leon, David Holzmüller, Hao Wang, Luis Ricardez-Sandoval +2 more
similarity 0.62
Abstract

Black-box optimization problems are ubiquitous across science and engineering, often dealing with expensive objective functions. This objective latency has two consequences during optimization: (i) the objective evaluation dominates execution time, and (ii) sample-efficient algorithms are crucial to accelerate development and avoid wasting resources. Bayesian optimization (BO) methods are the \textit{de facto} choice of planners for suggesting the next point to try. Standard BO fits the surrogate model's hyperparameters with a point estimate. Alternatively, a fully Bayesian approach uses model averaging to account for uncertainty over the hyperparameters, leading to better uncertainty estimates---useful in the low-data regime that is pervasive in BO. However, it is often prohibitively expensive and thus rarely used. In this work, we propose ELF-BO, an algorithm that uses the objective evaluation latency to headstart the computation of the next suggestion, allowing for fully Bayesian optimization without incurring substantial decision-time costs. This is done by sampling from the hyperparameter posterior \emph{while} the objective is being evaluated, only requiring reweighting of the samples once the objective value is observed. Across synthetic functions and real-world applications, we show that ELF-BO matches the performance of fully Bayesian methods while only incurring decision latency on par with or better than standard BO. Thus, ELF-BO makes fully Bayesian optimization practical in real-world use cases.

0.14

The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization

cs.LG math.OCstat.ML ·2026-11-02 ·Long Vu, Jongseong Brad Choi, Binoy Ravindran, Zhoulai Fu
similarity 0.61
Abstract

A staged search must decide which candidate to advance next and when to stop. Some observations only inform later decisions; others can be kept as results. We formulate these choices as a staged Pandora's box with a designated set of collectable stages. For independent finite-stage candidates with bounded readings and positive bounded own-history costs, an exact covered-call recursion gives the reservation index, the optimal value and the loss of every advance or stop; advancing an index-maximal candidate while its index exceeds the incumbent is optimal. The representation recovers classical single-stage search, nested inspection and the all-collectable Markov setting, and prices changes in the problem: enlarging the collectable set or lowering costs raises the value by an explicit covered-call overshoot. Resumption can be valuable even when future reward laws do not change, but has no value for deterministic readings. With information sharing across candidates, no rule using only their separate remaining-reading laws is universally optimal, and making an intermediate reading collectable can change which candidate is inspected first. Under a coherent joint path law with own-history costs, an approximate-planning bound controls the recomputed index's regret by changes in untouched candidates' local values; a common-component specialization bounds those changes through predictive total-variation dispersion. Exact finite-law experiments check the representation, the loss accounting and the bounds.

0.19

Knowing When to Stop: Bayesian Optimal Stopping for LLM Evaluations

cs.AI ·2026-08-14 ·Toby D. Pilditch
benchmark similarity 0.60
Abstract

LLM evaluations often use fixed sampling budgets, testing every item the same number of times even after estimates are precise. We introduce optstop, a precision-based adaptive stopping framework that treats evaluation as a sequential measurement problem: keep sampling where uncertainty remains high, and stop where estimates are precise or stable enough. The framework builds on hierarchical Bayesian inference, supports binary, ordinal, and continuous outcomes, and keeps every benchmark item eligible for sampling, without requiring a calibrated item bank. It runs live or retrospectively, and includes a safeguard that samples more cautiously as measured performance approaches zero, where rare successes matter most. In an illustrative 200-item, 10-epoch evaluation, it removes 57%-97% of planned trials across nine validation settings, with overall conclusions equivalent to the full run. These results show that LLM evaluation compute can be allocated by uncertainty rather than by fixed repetition counts, with the magnitude of savings depending on evaluation design.

0.38

Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules

cs.LG math.OCmath.STstat.ML ·2026-08-26 ·Liviu Aolaritei, Lucas Lévy, Francis Bach, Michael I. Jordan
similarity 0.59
Abstract

Stochastic gradient descent (SGD) is typically analyzed at a deterministic horizon chosen before the algorithm is run, even though practical stopping decisions are made adaptively by inspecting the evolving trajectory. This mismatch creates a fundamental certification problem: fixed-time guarantees do not generally remain valid at data-dependent stopping times, while deterministic horizons derived from worst-case bounds can be highly conservative. We address this problem for strongly convex stochastic optimization by constructing fully observable, trajectory-adaptive upper confidence sequences for the squared distance of the last iterate to the optimizer and the suboptimality of a weighted average. These bounds hold simultaneously over time, attain the optimal $1/t$ decay rate up to iterated-logarithmic factors in the worst case, and adapt to the realized stochastic gradients, allowing SGD to stop as soon as a prescribed accuracy is certified without sacrificing statistical validity. Our approach treats the evolving SGD trajectory as a sequential experiment whose observations provide evidence about the unknown optimization error. To formalize this perspective, we develop new recursive confidence-sequence techniques and a general time-uniform empirical Bernstein inequality for adapted processes with time-varying conditional means and predictable ranges that may grow without bound. We further extend these confidence-sequence constructions to minibatch SGD, with the empirical Bernstein bounds exploiting the realized second-moment structure within each minibatch. Numerical experiments show that the resulting stopping rules can require several orders of magnitude fewer iterations than natural deterministic horizons.

0.18

Knowing When to Stop Thinking: A Dissection of Expected Free Energy as a Test-Time Compute Controller for Latent World-Model Planning

cs.RO ·2026-10-20 ·Tong Zhang, Zhiyuan Shi, Yun Peng, Tao Xie
similarity 0.58
Abstract

A planner using a learned world model can improve its predicted outcome while choosing a worse action. We study when expected free energy (EFE) can help decide how much computation to spend on a plan. An EFE-inspired objective combines goal distance with disagreement among stochastic predictions. We test candidate scoring, stopping, and online predictor updates separately. Stopping when elite cost stalls reduces refinement on tasks whose success plateaus with depth, with mean success close to fixed-depth references. At the larger tested weights, rewarding disagreement lowers success with a frozen model. Penalizing it helps at some task and weight settings but harms others. When training data omit a region needed to reach the goal, online updates recover part of the resulting loss. The tested cost-stall rule can fail when further optimization exploits model errors, because predicted cost keeps falling after task success peaks. Cost progress can guide computation on a plateau, but protecting performance after a peak requires information about the consequences of the chosen actions.

0.10

Sequential Anytime Valid Tests for Efficient Inference-Time Alignment

cs.LG ·2026-11-19 ·Vishesh Kumar Singh, Sayak Ray Chowdhury
similarity 0.58
Abstract

Inference-time alignment methods, such as Best-of-N (BoN), improve language model outputs by generating multiple candidates per prompt and selecting among them using a reward model. Much of this cost is wasted: a fixed budget is applied to every prompt, although the computation required by prompts varies widely. Adaptive methods halt once sampled answers appear settled, but their thresholds are tuned heuristics with no statistical control over early-stopping errors. We instead seek an anytime-valid stopping rule that takes an error tolerance $α$ as input and halts only once an answer is certified to hold a majority ($θ_a > 1/2$) under the generator's distribution. We aggregate candidates by final answer with a reward-weighted self-consistency (RWSC) score and treat stopping as a sequential test over the resulting clusters. Applying Wald's sequential probability ratio test to these clusters yields SPRT-RWSC, which performs well empirically, but its guarantee fails because the leading answer shifts during sampling, and the run is continuously monitored. Our main contribution, e-RWSC, replaces Wald's test with a betting supermartingale (an e-process) for every answer the policy produces, bounding the probability of ever certifying a non-dominant answer by $α$, uniformly over time and across all answers. The RWSC scores drive the bets, so they affect only how quickly a dominant answer $a^\star$ is certified, not validity; certification takes $O(\log(1/α)/d_{\mathrm{KL}}(θ_{a^\star}\|1/2))$ samples. Experiments across several language models, datasets, and reward models confirm the predicted $1/d_{\mathrm{KL}}$ scaling of cost and show that accuracy improves over baselines at substantially lower token cost.

0.17

Query Performance Tuning with Optimal Exploration of Optimizer Cost Model Parameter Space

cs.DB ·2026-10-02 ·Wentao Wu, Xiaoying Wang, Vivek Narasayya, Surajit Chaudhuri
similarity 0.58
Abstract

Modern query optimizers use analytical cost models to estimate the cost of a given query plan. Such cost models are typically functions of a set of "cost units" that specify unit CPU cost when processing a row or unit IO cost when accessing a disk page. These cost units are traditionally viewed as platform-dependent constants, that is, they require a one-shot calibration when a database is deployed on a hardware/software platform, but are fixed afterward regardless of the query being optimized for. Some very recent work has taken a different perspective by viewing these cost units as tunable parameters that we call "cost model parameters (CMPs)" in this paper. However, so far there is no approach that offers any optimality guarantee for the tuning results. We present a new approach to systematically explore the query plan space spanned by the CMPs and find the best plan in terms of execution time. Compared to alternative exploration approaches that use random search (RS) or Bayesian optimization (BO), our new approach is deterministic and, therefore, avoids the undesirable instability that is inevitable when applying RS or BO. Moreover, it is guaranteed to find all candidate plans in the query plan space without suffering from the overhead of an exhaustive enumeration. We also present a set of optimization techniques to reduce the overall evaluation time spent on executing the candidate plans found, a factor that is often overlooked by previous work but is critical from a practical point of view. Experimental evaluation on top of PostgreSQL and Microsoft SQL Server demonstrates the efficacy of tuning the CMPs, which can find query plans that are orders of magnitude faster in execution time than the ones found by RS or BO.

0.24