論文の概要: PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate
bounds that handle general VC classes
- arxiv url: http://arxiv.org/abs/2106.09683v1
- Date: Thu, 17 Jun 2021 17:35:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-18 16:01:18.905032
- Title: PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate
bounds that handle general VC classes
- Title（参考訳）: PAC-Bayes, MAC-Bayes and Conditional Mutual Information: 一般VCクラスを扱う高速なレート境界
- Authors: Peter Gr\"unwald, Thomas Steinke, Lydia Zakynthinou
- Abstract要約: 条件付きPAC-Bayesianと相互情報(MI)の一般化境界を統一的に導出する。
一般VCクラスに対して非自明な PAC-Bayes と MI-スタイルのバウンダリが得られるが、最近、標準的な PAC-Bayesian/MI バウンダリでは不可能であることが示されている。
- 参考スコア（独自算出の注目度）: 17.544630217945333
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a novel, unified derivation of conditional PAC-Bayesian and mutual
information (MI) generalization bounds. We derive conditional MI bounds as an
instance, with special choice of prior, of conditional MAC-Bayesian (Mean
Approximately Correct) bounds, itself derived from conditional PAC-Bayesian
bounds, where `conditional' means that one can use priors conditioned on a
joint training and ghost sample. This allows us to get nontrivial PAC-Bayes and
MI-style bounds for general VC classes, something recently shown to be
impossible with standard PAC-Bayesian/MI bounds. Second, it allows us to get
faster rates of order $O \left(({\text{KL}}/n)^{\gamma}\right)$ for $\gamma >
1/2$ if a Bernstein condition holds and for exp-concave losses (with
$\gamma=1$), which is impossible with both standard PAC-Bayes generalization
and MI bounds. Our work extends the recent work by Steinke and Zakynthinou
[2020] who handle MI with VC but neither PAC-Bayes nor fast rates, the recent
work of Hellstr\"om and Durisi [2020] who extend the latter to the PAC-Bayes
setting via a unifying exponential inequality, and Mhammedi et al. [2019] who
initiated fast rate PAC-Bayes generalization error bounds but handle neither MI
nor general VC classes.
- Abstract（参考訳）: 条件付きPAC-Bayesianと相互情報(MI)の一般化境界を統一的に導出する。
条件付きmi境界を,条件付きmac-bayesian(約正しい)境界(条件付きpac-bayesian bounds)から派生した条件付きmac-bayesian(約正しい)境界(条件付きmi-bayesian bounds)の特別な選択の例として導出する。
これにより、一般的なvcクラスに対して、非自明なpac-bayesとmiスタイルの境界を得ることができます。
第二に、ベルンシュタイン条件が成立し($\gamma=1$で)exp-concave損失がある場合、$O \left(({\text{KL}}/n)^{\gamma}\right)$ for $\gamma > 1/2$は、標準的なPAC-Bayes一般化とMI境界の両方では不可能である。
我々の研究は、MIをVCで扱うSteinkeとZakynthinou [2020]の最近の研究を拡張し、PAC-Bayesも高速レートもなし、Hellstr\"omとDurisi [2020]の最近の研究は、指数的不等式を統一してPAC-Bayesセッティングに拡張している。
高速なPAC-Bayes一般化誤差境界を開始したが、MIも一般VCクラスも扱わない[2019]。
関連論文リスト
- Misclassification excess risk bounds for PAC-Bayesian classification via convexified loss [0.0]
PAC-Bayesian境界は、機械学習で新しい学習アルゴリズムを設計するための貴重なツールである。
本稿では、一般化の観点から、PAC-ベイズ境界に頼るのではなく、予想における相対的境界を利用する方法を示す。
論文 参考訳（メタデータ） (2024-08-16T11:41:06Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - A unified recipe for deriving (time-uniform) PAC-Bayes bounds [31.921092049934654]
PAC-ベイジアン一般化境界を導出するための統一的枠組みを提案する。
私たちの境界は任意の時効値(すなわち、時間ユニフォーム)であり、すべての停止時間を保持することを意味する。
論文 参考訳（メタデータ） (2023-02-07T12:11:59Z) - Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。
まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。
第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
論文 参考訳（メタデータ） (2023-02-06T02:52:36Z) - PAC Verification of Statistical Algorithms [0.10878040851637999]
本研究では,PAC学習目標を満たす仮説(機械学習モデル)を対話的証明を用いて検証する,PAC検証の設定を開発する。
我々は、$mathbbR$を超える間隔の和のPAC検証のためのプロトコルを提案し、そのタスクの提案したプロトコルを改善し、より低い境界の$d$への依存と一致させる。
最終結果は,クエリの制約を満たす統計的アルゴリズムの検証のためのプロトコルである。
論文 参考訳（メタデータ） (2022-11-28T23:57:27Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳（メタデータ） (2021-07-03T23:17:26Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - How Tight Can PAC-Bayes be in the Small Data Regime? [39.15172162668061]
PAC-Bayesとテストセット境界は、小さなデータセットに対して作成できる。
PAC-Bayes境界は、よく用いられるチャーノフテストセット境界と驚くほど競合することを示した。
最もシャープなテストセット境界は、我々が考慮しているPAC-Bayes境界よりも、一般化誤差のより良い保証につながる。
論文 参考訳（メタデータ） (2021-06-07T12:11:32Z) - A Limitation of the PAC-Bayes Framework [32.24251308425503]
我々はPAC-Bayesフレームワークの制限を提示する。
PAC-Bayes解析には適さない簡単な学習課題を実演する。
論文 参考訳（メタデータ） (2020-06-24T06:36:00Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。
正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文 参考訳（メタデータ） (2020-06-22T17:53:54Z) - Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。
我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
論文 参考訳（メタデータ） (2020-02-29T02:02:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。