論文の概要: 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つのサンプルであっても, しばしば非空の信頼境界を生成する, 境界からの信頼系列を数値的に計算する効率的なアルゴリズムを提案する。

関連論文リスト

• How to Shrink Confidence Sets for Many Equivalent Discrete Distributions? [17.52590726972374]
  機械学習問題における置換等価性を利用する。 信頼集合のサイズは$O/sqrtn_k)$と$O/max_kin K n_k)$で縮小することを示す。
  論文  参考訳（メタデータ） (2024-07-22T14:19:19Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Restless Linear Bandits [5.00389879175348]
  未知の$mathbbRd$-valued stationary $varphi$-mixing sequence of parameters $(theta_t,t in mathbbN)$ が存在すると仮定される。 指数混合率が$theta_t$の場合、LinMix-UCBと呼ばれる楽観的なアルゴリズムが提案される。
  論文  参考訳（メタデータ） (2024-05-17T14:37:39Z)
• Better-than-KL PAC-Bayes Bounds [23.87003743389573]
  我々は,新しい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)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• 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)

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

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