論文の概要: Better-than-KL PAC-Bayes Bounds
- arxiv url: http://arxiv.org/abs/2402.09201v2
- Date: Thu, 4 Apr 2024 11:22:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-05 19:33:50.154385
- Title: Better-than-KL PAC-Bayes Bounds
- Title（参考訳）: 改良KL PAC-Bayes境界
- Authors: Ilja Kuzborskij, Kwang-Sung Jun, Yulian Wu, Kyoungseok Jang, Francesco Orabona,
- Abstract要約: 我々は,新しいKLの分岐と密接な結びつきを達成できることを実証した。
我々の結果は、既存のPAC-Bayes境界と非KL分岐は、KLよりも厳密に優れていることが分かっていないという点において、第一種である。
- 参考スコア（独自算出の注目度）: 23.87003743389573
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let $f(\theta, X_1),$ $ \dots,$ $ f(\theta, X_n)$ be a sequence of random elements, where $f$ is a fixed scalar function, $X_1, \dots, X_n$ are independent random variables (data), and $\theta$ is a random parameter distributed according to some data-dependent posterior distribution $P_n$. In this paper, we consider the problem of proving concentration inequalities to estimate the mean of the sequence. An example of such a problem is the estimation of the generalization error of some predictor trained by a stochastic algorithm, such as a neural network where $f$ is a loss function. Classically, this problem is approached through a PAC-Bayes analysis where, in addition to the posterior, we choose a prior distribution which captures our belief about the inductive bias of the learning problem. Then, the key quantity in PAC-Bayes concentration bounds is a divergence that captures the complexity of the learning problem where the de facto standard choice is the KL divergence. However, the tightness of this choice has rarely been questioned. In this paper, we challenge the tightness of the KL-divergence-based bounds by showing that it is possible to achieve a strictly tighter bound. In particular, we demonstrate new high-probability PAC-Bayes bounds with a novel and better-than-KL divergence that is inspired by Zhang et al. (2022). Our proof is inspired by recent advances in regret analysis of gambling algorithms, and its use to derive concentration inequalities. Our result is first-of-its-kind in that existing PAC-Bayes bounds with non-KL divergences are not known to be strictly better than KL. Thus, we believe our work marks the first step towards identifying optimal rates of PAC-Bayes bounds.
- Abstract（参考訳）: 例えば、$f(\theta, X_1),$ $ \dots,$ $ f(\theta, X_n)$ をランダム要素の列とし、$f$ を固定スカラー関数、$X_1, \dots, X_n$ を独立確率変数(データ)、$\theta$ をデータ依存後続分布 $P_n$ に従って分布するランダムパラメータとする。
本稿では,シーケンスの平均値を推定するために,集中度不等式を示す問題について考察する。
そのような問題の例として、f$が損失関数であるニューラルネットワークのような確率的アルゴリズムで訓練された予測器の一般化誤差の推定がある。
古典的には、この問題はPAC-Bayes分析を通じてアプローチされ、後部に加えて、学習問題の帰納バイアスについての信念を捉えた事前分布を選択する。
次に、PAC-Bayes濃度境界の鍵量は、事実上の標準選択がKL分散である学習問題の複雑さを捉える分岐である。
しかし、この選択の厳しさが疑問視されることはめったにない。
本稿では,KL-発散境界の厳密性に挑戦し,より厳密な境界を達成可能であることを示す。
特に,Zhang et al (2022)にインスパイアされた,新しい高確率PAC-Bayes境界と,より優れたKL分岐を実証する。
我々の証明は、ギャンブルアルゴリズムの後悔分析の最近の進歩と、その濃度不等式の導出に触発されたものである。
我々の結果は、既存のPAC-Bayes境界と非KL分岐は、KLよりも厳密に優れていることが分かっていないという点において、第一種である。
したがって、我々の研究は、PAC-Bayes境界の最適率を特定するための第一歩だと信じている。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - PAC-Bayes-Chernoff bounds for unbounded losses [1.9799527196428246]
我々は,新しいPAC-Bayesオラクルを導入する。
この結果は、Clam'er-Chernoff 境界の PAC-Bayesian 版として理解することができる。
我々は,多くのPAC-Bayes境界における自由パラメータの正確な最適化が自然に可能であることを示す。
論文 参考訳（メタデータ） (2024-01-02T10:58:54Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Tighter PAC-Bayes Bounds Through Coin-Betting [31.148069991567215]
我々は,PAC-Bayes境界の証明戦略を洗練し,より厳密な保証を実現する方法を示す。
PAC-Bayes濃度の不等式は,全ての試料サイズを同時に保持するコインベッティング法に基づいて導出する。
論文 参考訳（メタデータ） (2023-02-12T01:16:27Z) - New Lower Bounds for Private Estimation and a Generalized Fingerprinting
Lemma [10.176795938619417]
統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。
フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
論文 参考訳（メタデータ） (2022-05-17T17:55:10Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳（メタデータ） (2022-04-06T13:50:33Z) - 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) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。
我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。
CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-10-15T17:34:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。