論文の概要: On the tightness of information-theoretic bounds on generalization error of learning algorithms

• arxiv url: http://arxiv.org/abs/2303.14658v1
• Date: Sun, 26 Mar 2023 08:59:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-28 18:20:08.382368
• Title: On the tightness of information-theoretic bounds on generalization error of learning algorithms
• Title（参考訳）: 学習アルゴリズムの一般化誤差に対する情報理論境界の厳密性について
• Authors: Xuetong Wu, Jonathan H. Manton, Uwe Aickelin, Jingge Zhu
• Abstract要約: まず、平方根が必ずしもスローレートを含まないことを示し、この境界を用いて高速な速度結果が得られることを示す。 高速一般化誤差に必要な臨界条件を同定し,$(eta,c)$-central条件と呼ぶ。
• 参考スコア（独自算出の注目度）: 5.081241420920605
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent line of works, initiated by Russo and Xu, has shown that the generalization error of a learning algorithm can be upper bounded by information measures. In most of the relevant works, the convergence rate of the expected generalization error is in the form of $O(\sqrt{\lambda/n})$ where $\lambda$ is some information-theoretic quantities such as the mutual information or conditional mutual information between the data and the learned hypothesis. However, such a learning rate is typically considered to be ``slow", compared to a ``fast rate" of $O(\lambda/n)$ in many learning scenarios. In this work, we first show that the square root does not necessarily imply a slow rate, and a fast rate result can still be obtained using this bound under appropriate assumptions. Furthermore, we identify the critical conditions needed for the fast rate generalization error, which we call the $(\eta,c)$-central condition. Under this condition, we give information-theoretic bounds on the generalization error and excess risk, with a fast convergence rate for specific learning algorithms such as empirical risk minimization and its regularized version. Finally, several analytical examples are given to show the effectiveness of the bounds.
• Abstract（参考訳）: russoとxuによって始められた最近の一連の研究は、学習アルゴリズムの一般化誤差が情報尺度によって上限を上回ることができることを示した。 関連するほとんどの研究において、期待される一般化誤差の収束率は$O(\sqrt{\lambda/n})$の形で、$\lambda$はデータと学習された仮説の間の相互情報や条件的相互情報のような情報理論的な量である。 しかし、このような学習率は、多くの学習シナリオで$o(\lambda/n)$の ``fast rate" と比較すると、一般的に ``slow" と見なされる。 本研究では,まず,正方根が必ずしも低速であるとは限らないことを示し,適切な仮定の下では,このバウンドを用いて高速速度結果が得られることを示す。 さらに,$(\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)

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

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