論文の概要: Fast Rate Information-theoretic Bounds on Generalization Errors
- arxiv url: http://arxiv.org/abs/2303.14658v2
- Date: Thu, 31 Oct 2024 09:16:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-01 16:58:38.008737
- Title: Fast Rate Information-theoretic Bounds on Generalization Errors
- Title（参考訳）: 一般化誤差の高速情報理論境界
- Authors: Xuetong Wu, Jonathan H. Manton, Uwe Aickelin, Jingge Zhu,
- Abstract要約: 学習アルゴリズムの一般化誤差は、学習アルゴリズムの学習データにおける損失と、目に見えないテストデータにおける損失との違いを指す。
一般化誤差に関する様々な情報理論境界が文献で導出されている。
本稿では,これらの境界の厳密性について,それらの収束速度の標本サイズ依存性の観点から検討する。
- 参考スコア（独自算出の注目度）: 8.102199960821165
- License:
- Abstract: The generalization error of a learning algorithm refers to the discrepancy between the loss of a learning algorithm on training data and that on unseen testing data. Various information-theoretic bounds on the generalization error have been derived in the literature, where the mutual information between the training data and the hypothesis (the output of the learning algorithm) plays an important role. Focusing on the individual sample mutual information bound by Bu et al., which itself is a tightened version of the first bound on the topic by Russo et al. and Xu et al., this paper investigates the tightness of these bounds, in terms of the dependence of their convergence rates on the sample size $n$. It has been recognized that these bounds are in general not tight, readily verified for the exemplary quadratic Gaussian mean estimation problem, where the individual sample mutual information bound scales as $O(\sqrt{1/n})$ while the true generalization error scales as $O(1/n)$. The first contribution of this paper is to show that the same bound can in fact be asymptotically tight if an appropriate assumption is made. In particular, we show that the fast rate can be recovered when the assumption is made on the excess risk instead of the loss function, which was usually done in existing literature. A theoretical justification is given for this choice. The second contribution of the paper is a new set of generalization error bounds based on the $(\eta, c)$-central condition, a condition relatively easy to verify and has the property that the mutual information term directly determines the convergence rate of the bound. Several analytical and numerical examples are given to show the effectiveness of these bounds.
- Abstract（参考訳）: 学習アルゴリズムの一般化誤差は、学習アルゴリズムの学習データにおける損失と、目に見えないテストデータにおける損失との違いを指す。
一般化誤差に関する様々な情報理論境界は、トレーニングデータと仮説(学習アルゴリズムの出力)の相互情報が重要な役割を果たす文献に導出されている。
本稿では,Russo et al と Xu et al のトピックに対する最初の境界の厳密版である Bu et al による個々のサンプル相互情報に着目し,それらの収束速度がサンプルサイズ$n$に依存していることから,これらの境界の厳密性について検討する。
これらの境界は一般に厳密ではないことが認識され、例の二次ガウス平均推定問題に対して容易に検証され、サンプルの相互情報境界は$O(\sqrt{1/n})$、真の一般化誤差は$O(1/n)$となる。
この論文の最初の貢献は、適切な仮定が成立すれば、同じ境界が実際には漸近的に厳密であることを示すことである。
特に,損失関数の代わりに過大なリスクを仮定した場合,その速さを回復できることを示す。
この選択には理論上の正当性が与えられる。
この論文の第二の貢献は、$(\eta, c)$-central条件に基づく新しい一般化誤差境界であり、これは比較的容易に検証でき、相互情報項が境界の収束率を直接決定する性質を持つ。
これらの境界の有効性を示すいくつかの解析的および数値的な例が与えられる。
関連論文リスト
- Tighter Information-Theoretic Generalization Bounds from Supersamples [27.14107452619853]
本稿では,学習アルゴリズムのための情報理論の新たな一般化境界について述べる。
提示される境界は平方根境界、高速レート境界を含み、分散と鋭さに基づく境界を含む。
理論的あるいは経験的に、これらの境界は、同じスーパーサンプル設定で知られているすべての情報理論境界よりも厳密であることを示す。
論文 参考訳（メタデータ） (2023-02-05T17:06:27Z) - How Does Pseudo-Labeling Affect the Generalization Error of the
Semi-Supervised Gibbs Algorithm? [73.80001705134147]
擬似ラベル付き半教師付き学習(SSL)におけるGibsアルゴリズムによる予測一般化誤差(ゲンエラー)を正確に評価する。
ゲンエラーは、出力仮説、擬ラベルデータセット、ラベル付きデータセットの間の対称性付きKL情報によって表現される。
論文 参考訳（メタデータ） (2022-10-15T04:11:56Z) - On the Generalization for Transfer Learning: An Information-Theoretic Analysis [8.102199960821165]
一般化誤差と転帰学習アルゴリズムの過大なリスクを情報理論で解析する。
我々の結果は、おそらく予想通り、Kulback-Leibler divergenceD(mu|mu')$がキャラクタリゼーションにおいて重要な役割を果たすことを示唆している。
次に、$phi$-divergence や Wasserstein 距離といった他の発散点と結びついた相互情報を一般化する。
論文 参考訳（メタデータ） (2022-07-12T08:20:41Z) - Fast Rate Generalization Error Bounds: Variations on a Theme [5.081241420920605]
期待一般化誤差の収束速度は O(sqrtlambda/n) の形で表されることを示す。
我々は、(eta,c)-central 条件と呼ぶ高速な一般化誤差に必要な重要な条件を同定する。
この条件下では、特定の学習アルゴリズムに対するO(lambda/n)の収束率を用いて、一般化誤差と過剰リスクに関する情報理論境界を与える。
論文 参考訳（メタデータ） (2022-05-06T10:39:48Z) - RATT: Leveraging Unlabeled Data to Guarantee Generalization [96.08979093738024]
ラベルのないデータを利用して一般化境界を生成する手法を紹介します。
境界が0-1経験的リスク最小化に有効であることを証明します。
この作業は、見えないラベル付きデータが利用できない場合でも、ディープネットの一般化を証明するためのオプションを実践者に提供します。
論文 参考訳（メタデータ） (2021-05-01T17:05:29Z) - Super fast rates in structured prediction [88.99819200562784]
連続的な問題が連続的な値を予測しているときに、離散的な問題が本質的に離散的なアウトプットを予測しているという事実を活用する方法を示す。
まず、近接する隣人に基づく予測器について説明し、二項分類で知られている確率を、構造的予測の枠組み内の任意の離散問題に一般化する。
次に、カーネルリッジの回帰について検討し、問題の硬さを特徴付けるパラメータによって、n-1/4$の既知のレートを任意に高速化する。
論文 参考訳（メタデータ） (2021-02-01T10:50:04Z) - Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
多くの機械学習アプリケーションは、2つの競合する目標を達成する表現を学習する。
ミニマックスゲーム理論の定式化は、精度と不変性の基本的なトレードオフを表す。
分類と回帰の双方において,この一般的かつ重要な問題を情報論的に解析する。
論文 参考訳（メタデータ） (2020-12-19T15:24:04Z) - The Role of Mutual Information in Variational Classifiers [47.10478919049443]
クロスエントロピー損失を訓練した符号化に依存する分類器の一般化誤差について検討する。
我々は、一般化誤差が相互情報によって境界付けられた状態が存在することを示す一般化誤差に境界を導出する。
論文 参考訳（メタデータ） (2020-10-22T12:27:57Z) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。
テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。
以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
論文 参考訳（メタデータ） (2020-06-22T21:12:31Z) - Generalization Error Bounds via $m$th Central Moments of the Information
Density [14.147617330278662]
本稿では,ランダム化学習アルゴリズムの一般化誤差に対するバウンダリを導出する一般手法を提案する。
我々の手法は、平均一般化誤差の有界値と、その尾の確率の有界値を得るのに利用できる。
論文 参考訳（メタデータ） (2020-04-20T09:23:49Z) - Robust Generalization via $\alpha$-Mutual Information [24.40306100502023]
R'enyi $alpha$-DivergencesとSibsonの$alpha$-Mutual Informationを使って、同じ事象の2つの確率測度を接続するバウンド。
結果は、学習アルゴリズムの一般化誤差の境界から、適応データ分析のより一般的なフレームワークまで幅広い応用がある。
論文 参考訳（メタデータ） (2020-01-14T11:28:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。