論文の概要: Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations
- arxiv url: http://arxiv.org/abs/2610.14996v1
- Date: Sat, 10 Oct 2026 15:23:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-15 21:06:15.140842
- Title: Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations
- Title（参考訳）: すべてのスコアではなく、決定を認定する - 少数の評価からトップk選択を実践する
- Abstract要約: 認定適応選択(Certified Adaptive Selection)は、不確実性を保ったまま変更できなくなると、正確なk$セットを返す。
その停止試験は、最悪の許容可能な候補を最も許容可能な候補と比較する。
精度の高いクエリを持つ経験的ESでは、後見で実現された決定を証明できる最少の評価を計算できる。
- 参考スコア（独自算出の注目度）: 1.675857332621569
- License: http://creativecommons.org/licenses/by/4.0/
- 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.
- Abstract（参考訳）: いくつかの堅牢なアルゴリズムやスケジュールを選択するには、エージェントが勝者を特定するだけでよいにも関わらず、多くの有害なシナリオの下ですべての候補を評価する必要がある。
予測者はこれらの勝者を提案するかもしれないが、未評価のシナリオではサプライズを除外することはできない。
Certified Adaptive Selection (CAS)を導入します。
CASは、最悪のシナリオにおける平均的な損失である期待されたショートフォール(ES)において、下位と上位の境界を保証している。
その停止テストは、最悪の許容可能な選択候補と、最も許容可能な除外候補を比較します。
予測には別の役割がある。次の結果を選択して評価し、決定を承認することはない。
厳密な単価クエリを持つ経験的ESでは、多項式時間で計算し、後見で実現された決定を証明できる最少の評価を行う。
我々の予測誘導エージェントCAS-PGは、敵を含む全ての予測器に対して正確である。
2つの公開アルゴリズム選択行列において、CAS-PGは3150の630と2200のリプレイクエリの981の後、正確な上位3つを認証する。
歴史的結果がなければ、その書き起こしのみの変種は最小の1.28ドルと1.37ドルを必要とする。
別として、予測のないCASポリシーは、合成エネルギースケジューリングにおける正確なrecourseの93.0\%の解決を回避している。
したがって、1つの証明書はいくつかの取得ポリシーをサポートし、リスク/コストの拡張を別々に証明する。
関連論文リスト
- The Arbitrary-Placement Problem in Entropy-Minimizing Selection, and a Residual-Entropy Formulation [0.0]
D = -mathrmKL(p_AVert p_) - $, $$はスコアによる分布と信頼プロファイルが同じ候補を好むかどうかを測定する。
境界ケースは基本的な安全性を確立している: 均一な信頼の下では、Dleq0$は自動的に$Dleq0である。
論文 参考訳（メタデータ） (2026-10-05T07:44:26Z) - CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees [1.7545090618311434]
マシンが学習した予測は、オフラインNPハード最適化を高速化するが、予測者にその問題を解決するために何をすべきかを尋ねる。
CASP (Certificate-Augmented Solution Pruning) は代わりに、どの部分の検索空間を無視するかを尋ね、サウンドタイム検証器がチェックした後のみ、各回答を受け入れる。
トレーニングされた予測器では、未検証プルーニングは配布シフト時の最適値の最大26%を失うが、検証された同じ予測のデプロイでは、何も失われることはない。
論文 参考訳（メタデータ） (2026-07-16T04:02:15Z) - Empirical Bayes Conformal Prediction for Vision and Language Models [20.40115871314124]
コンフォーマル予測(CP)は、現代のビジョンと言語モデルに対して、分布のないカバレッジを提供する。
標準CP は 1 つの実現法を使い、平均列キャリブレートの変種は点推定に滑らかな多重実現法を用いる。
実験的なベイズ共形予測フレームワークについて述べる。これは$r$-valuesを用いて、スコアの変動性を不確実な非整合性スコアに変換する。
論文 参考訳（メタデータ） (2026-05-22T03:17:14Z) - Smooth Partial Lotteries for Stable Randomized Selection [61.86327960322782]
多くの組織では、評価スコアに基づいて選択をランダム化する部分的な宝くじを採用している。
既存の抽選デザインは本質的に不安定であり、単一の候補のスコアへの小さな変更は、選択確率の大きな変化を引き起こす可能性がある。
部分的な宝くじの設計原理として滑らかさを提案し、候補に対するレビュースコアから選択確率へのマッピングにおいて、リプシッツ条件として定式化する。
論文 参考訳（メタデータ） (2026-05-19T16:22:51Z) - The Secretary Problem with Predictions and a Chosen Order [19.836223305384696]
藤井と吉田が最近導入した秘書問題(2023年)の学習強化版について検討した。
予測が正確であれば、アルゴリズムは最適に近い秘書を選ぶべきであるが、不正確な予測の下では、有界競争比を保証すべきである。
我々は,従来のランダム秩序秘書問題(ROSP)において,候補が一様にランダムな順序で到着する問題と,意思決定者が予測値に基づいて到着順序を選択することができるようなより自然な学習強化モデルを考える。
論文 参考訳（メタデータ） (2026-01-12T12:34:49Z) - Monitoring State Transitions in Markovian Systems with Sampling Cost [65.4151496405543]
自然なアプローチは、予想される予測損失がクエリコスト以下で、クエリがなければいつ発生するかを予測する、欲張りのポリシーである。
最適(OPT)戦略は状態依存のしきい値ポリシである。
遷移確率が未知の場合、我々は、グレディポリシーの予測勾配降下(PSGD)に基づく学習変種を提案する。
論文 参考訳（メタデータ） (2025-10-25T15:07:37Z) - A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
本稿では,各項目の品質の間隔推定に基づくランダム化意思決定の枠組みを提案する。
最適化に基づく最適化手法であるMERITを導入する。
MERITが既存のアプローチで保証されていない望ましい公理特性を満たすことを証明している。
論文 参考訳（メタデータ） (2025-06-23T19:59:30Z) - Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
コンフォーマル予測(CP)は、任意のモデルの出力を、真のラベルを(調整可能な)高い確率でカバーすることを保証した予測セットに変換する。
我々は,MCサンプルが著しく低い場合でも,より小さな集合を生成する頑健な共形予測を提案する。
論文 参考訳（メタデータ） (2025-03-07T08:41:53Z) - Fair Secretaries with Unfair Predictions [12.756552522270198]
予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。
私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
論文 参考訳（メタデータ） (2024-11-15T00:23:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。