論文の概要: Tighter PAC-Bayes Bounds Through Coin-Betting
- arxiv url: http://arxiv.org/abs/2302.05829v1
- Date: Sun, 12 Feb 2023 01:16:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 18:14:56.473671
- Title: Tighter PAC-Bayes Bounds Through Coin-Betting
- Title(参考訳): 太いPAC-Bayesがコインベッティングでバウンド
- Authors: Kyoungseok Jang, Kwang-Sung Jun, Ilja Kuzborskij, Francesco Orabona
- Abstract要約: 我々は,PAC-Bayes境界の証明戦略を洗練し,より厳密な保証を実現する方法を示す。
PAC-Bayes濃度の不等式は,全ての試料サイズを同時に保持するコインベッティング法に基づいて導出する。
- 参考スコア(独自算出の注目度): 31.148069991567215
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of estimating the mean of a sequence of random
elements $f(X_1, \theta)$ $, \ldots, $ $f(X_n, \theta)$ where $f$ is a fixed
scalar function, $S=(X_1, \ldots, X_n)$ are independent random variables, and
$\theta$ is a possibly $S$-dependent parameter. An example of such a problem
would be to estimate the generalization error of a neural network trained on
$n$ examples where $f$ is a loss function. Classically, this problem is
approached through concentration inequalities holding uniformly over compact
parameter sets of functions $f$, for example as in Rademacher or VC type
analysis. However, in many problems, such inequalities often yield numerically
vacuous estimates. Recently, the \emph{PAC-Bayes} framework has been proposed
as a better alternative for this class of problems for its ability to often
give numerically non-vacuous bounds. In this paper, we show that we can do even
better: we show how to refine the proof strategy of the PAC-Bayes bounds and
achieve \emph{even tighter} guarantees. Our approach is based on the
\emph{coin-betting} framework that derives the numerically tightest known
time-uniform concentration inequalities from the regret guarantees of online
gambling algorithms. In particular, we derive the first PAC-Bayes concentration
inequality based on the coin-betting approach that holds simultaneously for all
sample sizes. We demonstrate its tightness showing that by \emph{relaxing} it
we obtain a number of previous results in a closed form including Bernoulli-KL
and empirical Bernstein inequalities. Finally, we propose an efficient
algorithm to numerically calculate confidence sequences from our bound, which
often generates nonvacuous confidence bounds even with one sample, unlike the
state-of-the-art PAC-Bayes bounds.
- Abstract(参考訳): ランダム要素の平均値を推定する問題は、$f(X_1, \theta)$$, \ldots, $$f(X_n, \theta)$ ここで、$f$は固定スカラー関数、$S=(X_1, \ldots, X_n)$は独立確率変数、$\theta$はおそらく$S$依存パラメータである。
そのような問題の例として、$f$ が損失関数である$n$ でトレーニングされたニューラルネットワークの一般化エラーを推定することがある。
古典的には、この問題はラデマッハやvc型分析のような関数のコンパクトなパラメータ集合に対して一様に保たれる濃度不等式によって解決される。
しかし、多くの問題において、そのような不等式はしばしば数値的に空虚な推定をもたらす。
最近では、数値的に空でない境界をしばしば与える能力のために、このクラスの問題に対してより良い代替として \emph{PAC-Bayes} フレームワークが提案されている。
本稿では,pac-bayes境界の証明戦略を洗練し,emph{even tighter}保証を達成する方法を示す。
我々のアプローチは、オンラインギャンブルアルゴリズムの残念な保証から、最も厳密な時間一様濃度の不等式を導出する 'emph{coin-betting} フレームワークに基づいている。
特に,全ての試料サイズを同時に保持するコインベッティング法に基づいて,最初のPAC-Bayes濃度の不等式を導出した。
その厳密さは、ベルヌーイ-kl や経験的ベルンシュタインの不等式を含む閉形式で多くの先行結果が得られることを示している。
最後に, 最先端のPAC-Bayes境界とは異なり, 1つのサンプルであっても, しばしば非空の信頼境界を生成する, 境界からの信頼系列を数値的に計算する効率的なアルゴリズムを提案する。
関連論文リスト
- Better-than-KL PAC-Bayes Bounds [25.60887308549318]
我々は,新しいKLの分岐と密接な結びつきを達成できることを実証した。
我々の結果は、既存のPAC-Bayes境界と非KL分岐は、KLよりも厳密に優れていることが分かっていないという点において、第一種である。
論文 参考訳(メタデータ) (2024-02-14T14:33:39Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳(メタデータ) (2024-01-11T07:45:09Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳(メタデータ) (2023-06-03T04:00:47Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - Adversarially Robust Learning with Tolerance [8.658596218544774]
本稿では,距離摂動集合に対する寛容逆PAC学習の問題点について考察する。
自然摂動・平滑アルゴリズムの変種であるPACは、$gamma$-tolerant adversarial setにおいて、VC次元が$v$の任意の仮説クラス$mathcalH$を学習する。
また,2次元に線形依存したサンプル境界を求める学習手法を提案する。
論文 参考訳(メタデータ) (2022-03-02T03:50:16Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳(メタデータ) (2021-10-25T02:53:24Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Confidence sequences for sampling without replacement [39.98103047898974]
私たちは$thetastar$に対して信頼性シーケンスを設計するための一連のツールを提示します。
CS は、(C_n)_n=1N$ の信頼集合の列で、サイズが小さく、高い確率で$thetastar$ を同時に含む。
次に、WoRサンプリングのためのHoeffding-およびExperiical-Bernstein-type time-uniform CSと固定時間信頼区間を示す。
論文 参考訳(メタデータ) (2020-06-08T04:30:25Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。