論文の概要: 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条件と呼ばれる高速レート一般化エラーに必要な臨界条件を特定する。
この条件下では,経験的リスク最小化や正規化バージョンのような特定の学習アルゴリズムに対する収束速度が速い一般化誤差と過剰リスクに関する情報理論的な境界を与える。
最後に、境界の有効性を示すいくつかの分析例が与えられる。
関連論文リスト
- Towards Understanding the Generalizability of Delayed Stochastic
Gradient Descent [63.43247232708004]
非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。
既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。
我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
論文 参考訳(メタデータ) (2023-08-18T10:00:27Z) - An Information-Theoretic Analysis for Transfer Learning: Error Bounds
and Applications [5.081241420920605]
本稿では,伝達学習アルゴリズムの一般化誤差と過剰リスクに関する情報理論解析を行う。
我々の結果は、おそらく予想通り、Kulback-Leiblerの発散$D(mu||mu')$がキャラクタリゼーションにおいて重要な役割を果たすことを示唆している。
そこで本研究では,ソースデータとターゲットデータの重み付けを適応的に調整するInfoBoostアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-07-12T08:20:41Z) - On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
残余条件付き相互情報(loo-CMI)の新しい尺度に基づく教師付き学習アルゴリズムのための情報理論の一般化境界を導出する。
他のCMI境界とは対照的に、我々のloo-CMI境界は容易に計算でき、古典的なout-out-out-cross-validationのような他の概念と関連して解釈できる。
ディープラーニングのシナリオにおいて予測された一般化ギャップを評価することにより,境界の質を実証的に検証する。
論文 参考訳(メタデータ) (2022-07-01T17:58:29Z) - 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) - Information-Theoretic Generalization Bounds for Iterative
Semi-Supervised Learning [81.1071978288003]
特に,情報理論の原理を用いて,反復型SSLアルゴリズムのエミュレータ一般化誤差の振る舞いを理解することを目的とする。
我々の理論的結果は、クラス条件分散があまり大きくない場合、一般化誤差の上限は反復数とともに単調に減少するが、すぐに飽和することを示している。
論文 参考訳(メタデータ) (2021-10-03T05:38:49Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳(メタデータ) (2021-06-06T19:08:53Z) - 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) - Information-theoretic analysis for transfer learning [5.081241420920605]
本稿では,一般化誤差と転帰学習アルゴリズムの過大なリスクに関する情報理論解析を行う。
我々の結果は、おそらく予想通り、Kulback-Leiblerの発散$D(mu||mu')$が一般化誤差を特徴づける重要な役割を果たすことを示唆している。
論文 参考訳(メタデータ) (2020-05-18T13:23:20Z) - Generalization Error Bounds via $m$th Central Moments of the Information
Density [14.147617330278662]
本稿では,ランダム化学習アルゴリズムの一般化誤差に対するバウンダリを導出する一般手法を提案する。
我々の手法は、平均一般化誤差の有界値と、その尾の確率の有界値を得るのに利用できる。
論文 参考訳(メタデータ) (2020-04-20T09:23:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。