論文の概要: Efficient Online Conformal Selection with Limited Feedback
- arxiv url: http://arxiv.org/abs/2605.14953v1
- Date: Thu, 14 May 2026 15:22:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-15 21:45:34.910115
- Title: Efficient Online Conformal Selection with Limited Feedback
- Title（参考訳）: 限定フィードバックによる効率的なオンラインコンフォーマル選択
- Authors: Sreenivas Gollapudi, Kostas Kollias, Kamesh Munagala, Ali Sinop,
- Abstract要約: 我々は、エージェントが最低限の選択肢のサブセットを選択して、少なくとも1つの成功が特定されるようにしなければならない共形選択の問題に対処する。
適応型コンフォーマル推論(ACI)更新ルールは、適切な制御パラメータや双対変数に適用された場合、逆向きに有効かつ効率的であることを示す。
- 参考スコア（独自算出の注目度）: 14.326282143930769
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of conformal selection, where an agent must select a minimal subset of options to ensure that at least one ``success'' is identified with a pre-specified target probability $φ$. While traditional online conformal prediction focuses on maintaining validity for the observed sequence, minimizing the resource cost (efficiency) of such selections, especially under limited feedback, remains a significant challenge. In this work, we consider settings with the most limited ``bandit'' feedback, and demonstrate that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable, is both adversarially valid, ensuring the success target is met on average for any input sequence (and hence under distribution shifts), and stochastically efficient, achieving sublinear efficiency regret for $i.i.d.$ inputs against an appropriate stochastic benchmark. We show such guarantees under canonical models capturing bandit and semi-bandit feedback to the agent via a unifying algorithmic technique, and analytic framework involving Lyapunov functions. Our approach handles more complex settings than prior work, while requiring significantly less feedback, and our results provide a new theoretical bridge between efficient online learning with limited feedback and distribution-free uncertainty quantification.
- Abstract（参考訳）: エージェントが少なくとも1つの ``success'' が予め指定されたターゲット確率 $φ$ と同一視されることを保証するために、最小限のオプションのサブセットを選択する必要がある。
従来のオンラインコンフォメーション予測は、観測されたシーケンスの妥当性を維持することに重点を置いているが、そのような選択のリソースコスト(効率)を、特に限られたフィードバックの下で最小化することは、依然として大きな課題である。
本稿では,最も制限された ``bandit'' フィードバックで設定を検討し,適切な制御パラメータや双対変数に適用した場合,ACI (Adaptive Conformal Inference) 更新ルールが逆向きに有効であることを示す。
このような保証は、Lyapunov関数を含む一元化アルゴリズムと分析フレームワークを用いて、エージェントに対する帯域幅と半帯域幅のフィードバックをキャプチャする標準的なモデルの下で示される。
提案手法は, 従来の作業よりも複雑な設定を扱うが, フィードバックが著しく少なく, より効率的なオンライン学習と, 分散のない不確実性定量化との間には, 新たな理論的橋渡しを提供する。
関連論文リスト
- Reasoning Is Not Free: Robust Adaptive Cost-Efficient Routing for LLM-as-a-Judge [4.511996087821266]
Reasoning-capable large language model (LLM) は、最近自動判断器として採用されている。
本研究では,明示的推論により,構造化された検証を必要とするタスクの判断精度が大幅に向上することを示す。
本稿では、推論と非推論の判断を選択可能なロバスト適応コスト効率ルーティング(RACER)を提案する。
論文 参考訳（メタデータ） (2026-05-11T16:30:20Z) - On the Optimality of Tracking Fisher Information in Adaptive Testing with Stochastic Binary Responses [3.491999371287298]
逐次二進応答から連続能力パラメータを推定する問題について検討する。
本稿では,フィッシャー情報を最大化するための質問を適応的に選択する簡単なアルゴリズムを提案する。
我々は,このフィッシャー追跡戦略が,固定信頼と固定予算の双方において最適な性能を達成することを証明した。
論文 参考訳（メタデータ） (2025-10-09T07:10:00Z) - COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
COINは、統計的に有効な閾値を校正し、質問毎に1つの生成された回答をフィルタリングする不確実性保護選択フレームワークである。
COINはキャリブレーションセット上で経験的誤差率を推定し、信頼区間法を適用して真誤差率に高い確率上界を確立する。
リスク管理におけるCOINの堅牢性,許容回答を維持するための強いテストタイムパワー,キャリブレーションデータによる予測効率を実証する。
論文 参考訳（メタデータ） (2025-06-25T07:04:49Z) - Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。
過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。
報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
論文 参考訳（メタデータ） (2024-05-26T05:38:50Z) - Introduction to Online Control [31.67032731719622]
オンラインの非確率制御では、コスト関数と仮定された力学モデルからの摂動の両方が敵によって選択される。
目標は、ベンチマーククラスの政策から見て、最高の政策に対して低い後悔を得ることだ。
論文 参考訳（メタデータ） (2022-11-17T16:12:45Z) - Budgeted Classification with Rejection: An Evolutionary Method with
Multiple Objectives [0.0]
予算付きシーケンシャル分類器(BSC)プロセスは、部分的特徴取得と評価ステップのシーケンスを通じて入力を行う。
これにより、不要な特徴取得を防止するための入力の効率的な評価が可能になる。
本稿では,信頼度に基づく拒否オプション付き逐次分類器を構築するための問題固有遺伝的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-01T22:05:16Z) - Error-based Knockoffs Inference for Controlled Feature Selection [49.99321384855201]
本手法では, ノックオフ特徴量, エラーベース特徴重要度統計量, ステップダウン手順を一体化して, エラーベースのノックオフ推定手法を提案する。
提案手法では回帰モデルを指定する必要はなく,理論的保証で特徴選択を処理できる。
論文 参考訳（メタデータ） (2022-03-09T01:55:59Z) - Linear Stochastic Bandits over a Bit-Constrained Channel [37.01818450308119]
我々は,ビット制約チャネル上に線形バンドレットの新たな定式化を導入する。
サーバの目標は、未知のモデルパラメータの推定値に基づいてアクションを取ることで、累積的後悔を最小限に抑えることである。
未知のモデルが$d$-dimensionalである場合、チャネル容量は$O(d)$ bits suffices で順序最適後悔を実現する。
論文 参考訳（メタデータ） (2022-03-02T15:54:03Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。
この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。
目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
論文 参考訳（メタデータ） (2020-07-01T14:24:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。