Fugu-MT 論文翻訳(概要): CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

論文の概要: CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

arxiv url: http://arxiv.org/abs/2607.14545v1
Date: Thu, 16 Jul 2026 04:02:15 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-17 17:01:32.981466
Title: CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
Title（参考訳）: CASP: 検証証明とバウンドロスPAC保証による学習強化オフライン近似
Abstract要約: マシンが学習した予測は、オフラインNPハード最適化を高速化するが、予測者にその問題を解決するために何をすべきかを尋ねる。 CASP (Certificate-Augmented Solution Pruning) は代わりに、どの部分の検索空間を無視するかを尋ね、サウンドタイム検証器がチェックした後のみ、各回答を受け入れる。トレーニングされた予測器では、未検証プルーニングは配布シフト時の最適値の最大26%を失うが、検証された同じ予測のデプロイでは、何も失われることはない。
参考スコア（独自算出の注目度）: 1.7545090618311434
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from $\tilde O(\varepsilon^{-2}\log K)$ samples ($K$ the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread $R$, none below $Ω(R/\varepsilon^2)$. Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to $26%$ of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.
Abstract（参考訳）: マシンが学習した予測は、オフラインNPハードの最適化を高速化するが、予測者にその問題を解決するために何をすべきかを尋ね、最悪の場合の保証を全て無視する未確認の予測をコミットする。代わりに、CASP (Certificate-Augmented Solution Pruning) は、どの部分の探索空間を無視するかを尋ね、音多項式時間検証器がチェックした後にのみ各回答を受け入れるので、正確性は予測品質に依存しない。我々はこの設計の学習理論を発展させる。検証器は誘導損失クラスを一様有界にするので、証明書パラメータは$\tilde O(\varepsilon^{-2}\log K)$ sample(K$ the maximum instance size)から学習できる。信頼の検証によってノイズの予測が標準のmin-combinerを支配し、私たちが計算したマージンは閉じた形で計算され、その予測はLPを考慮すれば有用である。 5つの問題の実験は理論の量的予測をテストする。トレーニングされた予測器では、未検証プルーニングは配布シフト時の最適値の最大26%を失うが、検証された同じ予測のデプロイでは、何も失われることはない。

関連論文リスト

Replicable Conformal Prediction [0.3058685580689604]
2人のアナリストが毎回、独立したサンプルで同じ予測モデルを調整します。 2つのキャリブレーションが同じオブジェクトを生成することを確認できない。一つのランダムなシードを共有し、キャリブレーションされた閾値を粗い共有グリッドまで丸めれば、緊張は解消される。
論文参考訳（メタデータ） (2026-08-23T17:47:40Z)
$TCP_α$: Margin-Controlled Confidence estimation for reliable Music Information Retrieval [7.679660052685777]
ディープニューラルネットワークは、しばしば過信であり、誤った予測にも高い信頼を割り当てる。既存のターゲットは、重複する信頼値を正しい予測と間違った予測に割り当てる一方、決定境界付近のエラーは正しい予測と区別できない信頼スコアを受け取る。提案するTCP_$は,不特定サンプルに対してマージン制御されたペナルティを導入することで,これらの制限を解消する新しい信頼度ターゲットである。
論文参考訳（メタデータ） (2026-08-20T17:58:50Z)
How to Verify Consistency of Probabilistic Claims [49.47758039235095]
予測モデルの一貫性を証明するために,対話型PCPを構築する。添加音の小さなギャップがBへの依存を除去することを示す。我々は,対話型PCPを,自身の一貫性を証明するための予測モデルに向けた第一歩だと考えている。
論文参考訳（メタデータ） (2026-08-11T17:41:39Z)
Online Conformal Prediction Beyond Feedback [28.843690637682915]
安全クリティカルなアプリケーションに機械学習モデルをデプロイする際には、不確実性定量化が不可欠である。オンライン共形予測(OCP)は、任意のブラックボックス分類器と非i.d.データストリームに対して理論的に原理化された不確実性定量化を提供する。我々は,Cesa-Bianchi,Lugosi,Stoltz (2004) のラベル効率予測器を用いて,クエリを用いたOCPQ(OCPQ)を開発した。
論文参考訳（メタデータ） (2026-08-07T11:58:48Z)
Distribution-informed Online Conformal Prediction [53.674678995825666]
更新ルールに基礎となるデータパターンを組み込んだオンラインコンフォメーション予測アルゴリズムである Conformal Optimistic Prediction (COP) を提案する。 COPは予測可能なパターンが存在する場合により厳密な予測セットを生成し、見積もりが不正確な場合でも有効なカバレッジ保証を保持する。我々は,COPが有効なカバレッジを実現し,他のベースラインよりも短い予測間隔を構築できることを証明した。
論文参考訳（メタデータ） (2025-12-08T17:51:49Z)
ZIP-RC: Optimizing Test-Time Compute via Zero-Overhead Joint Reward-Cost Prediction [57.799425838564]
ZIP-RCは、モデルに報酬とコストのゼロオーバーヘッド推論時間予測を持たせる適応推論手法である。 ZIP-RCは、同じまたはより低い平均コストで過半数投票よりも最大12%精度が向上する。
論文参考訳（メタデータ） (2025-12-01T09:44:31Z)
Classification with Reject Option: Distribution-free Error Guarantees via Conformal Prediction [1.1380162891529535]
我々は、二項分類におけるリジェクションオプションによる機械学習のアプローチを定式化する。結果の誤差率に関する理論的保証を提供する。エラー・リジェクト曲線は、エラーレートとリジェクトレートの間のトレードオフを示している。
論文参考訳（メタデータ） (2025-06-26T23:04:25Z)
COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
COINは、統計的に有効な閾値を校正し、質問毎に1つの生成された回答をフィルタリングする不確実性保護選択フレームワークである。 COINはキャリブレーションセット上で経験的誤差率を推定し、信頼区間法を適用して真誤差率に高い確率上界を確立する。リスク管理におけるCOINの堅牢性,許容回答を維持するための強いテストタイムパワー,キャリブレーションデータによる予測効率を実証する。
論文参考訳（メタデータ） (2025-06-25T07:04:49Z)
Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
コンフォーマル予測(CP)は、任意のモデルの出力を、真のラベルを(調整可能な)高い確率でカバーすることを保証した予測セットに変換する。我々は,MCサンプルが著しく低い場合でも,より小さな集合を生成する頑健な共形予測を提案する。
論文参考訳（メタデータ） (2025-03-07T08:41:53Z)
On Computationally Efficient Multi-Class Calibration [9.032290717007065]
プロジェクトのキャリブレーションは、下流の意思決定者全員に強い保証を与えます。これは、ラベルに割り当てられた確率を$T$にまとめることで予測される確率が、完全に校正されたバイナリ予測器に近いことを保証している。
論文参考訳（メタデータ） (2024-02-12T17:25:23Z)
Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
トップk予測は、マシンラーニング・アズ・ア・サービス、レコメンダ・システム、Web検索など、多くの現実世界のアプリケーションで使用されている。我々の研究はランダム化平滑化に基づいており、入力をランダム化することで、証明可能なロバストな分類器を構築する。例えば、攻撃者がテスト画像の5ピクセルを任意に摂動できる場合に、ImageNet上で69.2%の認定トップ3精度を達成する分類器を構築することができる。
論文参考訳（メタデータ） (2020-11-15T21:34:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。