CS Paper Radar

Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations

Yuhe Sui, Yingzhi Tang

cs.AI ·submitted 2026-10-10 15:23 UTC · v1

Abstract

Choosing a few robust algorithms or schedules can require evaluating every candidate under many adverse scenarios, even though an agent only needs to identify the winners. A predictor may suggest those winners, but cannot rule out a surprise in an unevaluated scenario. We introduce Certified Adaptive Selection (CAS), which returns the exact top-$k$ set as soon as remaining uncertainty cannot change it. CAS keeps guaranteed lower and upper bounds on Expected Shortfall (ES), the average loss in the worst scenarios. Its stopping test compares the worst admissible selected candidate with the best admissible excluded one; for information-disjoint Cartesian intervals this one-cut test is necessary and sufficient. Prediction has a separate role: selecting the next outcome to evaluate, never authorizing the decision. For empirical ES with exact unit-cost queries, we compute in polynomial time the fewest evaluations that could have proved the realized decision in hindsight. Our prediction-guided agent CAS-PG is exact for every predictor, including adversarial ones. On two public algorithm-selection matrices, CAS-PG certifies the exact top three after 630 of 3150 and 981 of 2200 replayed queries, or $1.14$ and $1.18$ times that hindsight minimum. Without historical outcomes, its transcript-only variant requires $1.28$ and $1.37$ times the minimum, outperforming the tested non-predictive certified policies. Separately, a prediction-free CAS policy avoids $93.0\%$ of exact recourse solves in synthetic energy scheduling. One certificate thus supports several acquisition policies and separately proved risk/cost extensions: prediction changes the work, not the justified choice.

Closest papers

Nearest neighbours by meaning across the whole index.

Available Guardrails: Certifying Selective Prediction across ML Systems

cs.LG ·2026-09-18 ·Parivesh Priye, Yufeng Wang, Haibin Ling, Michael Chaykowsky
similarity 0.64
Abstract

A selective predictor acts as a safety gate: it returns an output only when the prediction appears sufficiently trustworthy. Deployments increasingly require this reliability to be certified at a target precision for every reporting unit of interest, such as a tool, policy label, or patient subgroup. The main difficulty is often not whether a granted certificate is valid, but whether finite calibration data can produce one at all. As the gate becomes safer or more fine-grained, some units may receive too little evidence to certify. We make this notion of availability computable through classical exact-binomial inversion and formulate reporting-partition selection, under a fixed group order, as a dynamic program that exposes the trade-off among safety, granularity, and served traffic. The resulting frontier reveals a large population opportunity that finite-sample estimation nearly erases: a truth-informed planner gains $0.157$ mean coverage over support balancing, whereas a naive estimator recovers only $0.005$, making recovery from finite data the central challenge. Constructing candidate partitions on one planning split and selecting among them on another recovers part of this gap, improving mean coverage over support balancing by $0.060$, with the direction reproduced in $59$ of $60$ model effects across three intent-routing datasets and two architectures. A complementary validity-preserving lever, reallocating the familywise error budget across reporting units, recovers additional coverage both with population quantities and noisy estimates. The same frontier recurs, with predictor-specific ceilings, across LLM tool-calling, content moderation, lesion classification, and recommendation. Certified availability is therefore a plannable deployment resource that determines when a safety gate can be certified, at what granularity, and over how much traffic.

0.21

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

cs.LG ·2026-09-30 ·Ami Tavory, Noa Cohen
publishedtheory similarity 0.64
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

MLE-World: Predicting Machine Learning Experiment Outcomes with a Learned World Model

cs.LG cs.AI ·2026-10-27 ·Brian Ko, Han Wang, Hejia Geng, Li Erran Li, Sherry Yang
similarity 0.64
Abstract

AI research agents can propose, execute, and improve programs that solve machine learning tasks. However, executing each candidate program requires training and evaluating ML models, limiting how many candidates an agent can explore at each step. We introduce MLE-World, a world model finetuned from Qwen3.5-4B that predicts a program's terminal output (error traces, training logs, and validation scores) from its code and data description without executing it, together with a confidence score estimating the prediction's correctness. Because a prediction costs one inference call rather than a training run, MLE-World makes test time scaling (TTS) affordable for these agents. We build five TTS policies, guided by MLE-World, that compare several candidates per step by their predicted outputs: Sequential revision, Best-of-N, Pairwise judging, Fusion, and a UCB style rule that also adds an exploration bonus from this confidence score. Since predictions can be wrong, we run a candidate for real only when its confidence score is low. On 17 MLE-bench Lite tasks, MLE-World matches the real terminal output on 77.9% of held out programs, versus 41.1% for much larger prompted models. MLE-World guided TTS achieves up to 22.1% higher observed mean performance than the agent without a world model, with less real execution. Project webpage: https://mle-world.github.io/.

0.31

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

cs.LG stat.ML ·2026-10-21 ·Yashaswini Kaluguri, Nikhil Karamchandani
theory similarity 0.63
Abstract

We propose a novel stochastic cascading bandit setup where probing an ordered shortlist of $K$ out of $L$ arms incurs position-dependent costs, and the learner observes only noisy feedback regarding each arm's true output. We identify a sub-class of noise models for which the optimal shortlist can be found by sorting arms according to a per-arm score: such a score exists for both selection and ordering when the channel has no false positives, and for ordering alone (but not selection) when measurements are costless; however in general neither selection nor ordering is separable once noise and cost are both present. For the case where both selection and ordering scores exist, we provide a UCB-based algorithm with $O((L-K)\log T)$ instance-dependent regret over a time horizon $T$, which matches an algorithm-agnostic lower bound (up to constant factors). For the more challenging scenario where scores don't exist, we develop a new algorithmic template, DP-UCB, that embeds optimism directly inside an exact dynamic program, yielding $O\big(LK\log T\big)$ regret. Finally, we validate our theoretical results through extensive numerical evaluations and simulations over both synthetic and real-world datasets.

0.08

PruneShift: A Framework for Evaluating Decision Reliability in Structured Pruning

cs.LG cs.NE ·2026-08-30 ·Hao Ye, Gaopeng Zhang
similarity 0.63
Abstract

Structured pruning uses surrogate objectives because direct task evaluation over every feasible mask is too expensive. Most evaluations report average surrogate error or rank correlation on broadly sampled masks. These summaries do not directly test the mask chosen by the surrogate. We introduce PruneShift, an evaluation framework that separates broad predictive fidelity, fidelity near selector outputs, and the quality of the selected pruning decision. We first prove that Spearman and Kendall agreement can approach one while normalized selection regret remains maximal. We then derive sufficient conditions based on uniform error, selector suboptimality, decision margin, density ratio, and comparison mass. The analysis also yields a finite pool certificate with an explicit excess cost bound. Four studies test different links in this argument. External TextbookQA confirmation is heterogeneous: 7 of 20 simultaneous intervals favor the surrogate-selected mask, 6 favor its fixed comparator, and 7 cross zero. On a fixed Natural Questions pool, strict improvement holds in one of four settings. A controlled QQP experiment supports the proposed coverage mechanism in all 16 prespecified endpoints, although the sufficient bounds are conservative. Finally, a restricted OSSCAR reconstruction study on OPT-125M shows better local than broad fidelity in 68 of 75 primary endpoints. Independent fixed-mask confirmation is inconclusive in 24 of 25 endpoints and favors the comparator in one. These results show why predictive fit, decision reliability, and pruning method quality require separate evidence.

0.33

Prediction with Expert Advice under Heavy-Tailed Losses

cs.LG stat.ML ·2026-10-10 ·Yuki Shibukawa, Shinji Ito
hot direction similarity 0.62
Abstract · 49 pages

We study prediction with expert advice over $T$ rounds with $K$ experts under heavy-tailed losses whose $(1+ε)$-moment is bounded by $θ>0$ for some $ε\in(0,1]$. In this setting, existing algorithms designed for the case $ε=1$ can be suboptimal when $ε<1$, suffering an additional polynomial dependence on $K$. We characterize the minimax pseudo-regret rate as $Θ((θT)^{\frac{1}{1+ε}}(\log K)^{\fracε{1+ε}})$ and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either $ε$ or $θ$, we propose Adaptive Heavy-Tailed FTRL, which uses robust data-dependent scale adaptation together with truncation. We further develop Adaptive Heavy-Tailed OMD, which likewise requires neither $ε$ nor $θ$ and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when $ε$ and $θ$ are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.

0.30

Risk-Averse Decision-Focused Learning: Minimizing CVaR of Regret

cs.LG cs.AI ·2026-11-14 ·Jayanta Mandi, Senne Berden, Victor Bucarey, Concepcion Dominguez, Tias Guns
similarity 0.62
Abstract

Many combinatorial optimization (CO) problems involve parameters that are uncertain when the problem must be solved. In such settings, the parameters have to be predicted from correlated contextual information before a solution can be computed. \emph{Decision-focused learning} (DFL) addresses this by training the predictive model to produce predictions that optimize downstream decision quality. Most existing DFL methods are risk-neutral and minimize the expected regret. In high-stakes applications this can lead to undesirable outcomes, because decision-makers must also account for the tail risk of decision quality. Prior risk-sensitive approaches typically model uncertainty explicitly and solve a stochastic or robust optimization problem at inference time, which increases computational complexity. We instead propose a DFL framework that achieves risk-sensitive behavior while retaining point predictions and deterministic optimization at inference time. Starting from the dual representation of the Conditional Value-at-Risk (CVaR) and adding entropy regularization, we derive a smooth surrogate for the CVaR of regret. Its gradient induces an instance-dependent reweighting within each minibatch that emphasizes high-risk outcomes, so the approach can turn existing surrogate-loss DFL methods, including the SPO+ loss, into risk-sensitive variants. When instantiated with SPO+, the resulting objective admits a generalization bound on the CVaR of the true regret. Experiments on knapsack, portfolio, shortest-path, and energy-aware scheduling problems show substantial reductions in tail regret when the uncertain parameters exhibit heterogeneous tail behavior.

0.11

Accelerating Linear Bandits with Persistent Candidate Sets

cs.LG ·2026-10-09 ·Bingkui Tong, Daria Korovaitceva, Marina Sheshukova, Sergey Samsonov, Junpei Komiyama
theory similarity 0.62
Abstract

Exhaustive optimistic scoring can make action selection costly in linear bandits with a large fixed set of $K$ actions, requiring $\mathcal{O}(K)$ score evaluations per round. We introduce Persistent Candidate LinUCB (\textsc{PC-LinUCB}), which maintains $k$ active actions and samples $q$ challengers uniformly from the remaining $K-k$ actions at each round. By scoring only these $k+q$ candidates, \textsc{PC-LinUCB} reduces the number of score evaluations per round to $\mathcal{O}(k+q)$. We establish problem-independent and problem-dependent high-probability regret bounds consisting of a standard linear-bandit learning term and an additive discovery cost of order $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an $Ω\left((K-k)/q\right)$ regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that \textsc{PC-LinUCB} substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.

0.20