Certified exact top k selection reduces evaluation work using predictions
Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations
Artificial Intelligence
Summary
Choosing the best options often means checking every alternative under many tough situations, which can be slow and costly. The authors present Certified Adaptive Selection (CAS), a method that stops evaluating once it's certain it has found the best options, saving unnecessary tests. CAS uses predictions to decide which scenarios to check next but never lets predictions decide the final choice, ensuring accuracy. Their approach speeds up finding top choices with fewer checks and works well even if predictions are poor.
What this means in practice
- •For algorithm developers: Reduce the number of test scenarios needed to identify the best performing algorithms with a guarantee of exact top choice correctness.
- •For energy schedulers: Avoid computationally expensive exact recourse problem solving during scheduling by using a prediction-free certified top selection approach.
Authors
Yuhe Sui, Yingzhi Tang
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.