論文の概要: Towards a Unified Information-Theoretic Framework for Generalization
- arxiv url: http://arxiv.org/abs/2111.05275v1
- Date: Tue, 9 Nov 2021 17:09:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-10 15:10:29.126378
- Title: Towards a Unified Information-Theoretic Framework for Generalization
- Title（参考訳）: 一般化のための統一情報理論フレームワークを目指して
- Authors: Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, Daniel M. Roy
- Abstract要約: まず、このフレームワークを用いて、任意の学習アルゴリズムに対して非自明な(しかし、準最適)境界を表現できることを実証する。
我々は、CMIフレームワークが、ハーフスペースを学習するためのSVM(Support Vector Machines)の予測されるリスクに最適な境界をもたらすことを証明した。
- 参考スコア（独自算出の注目度）: 43.23033319683591
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we investigate the expressiveness of the "conditional mutual
information" (CMI) framework of Steinke and Zakynthinou (2020) and the prospect
of using it to provide a unified framework for proving generalization bounds in
the realizable setting. We first demonstrate that one can use this framework to
express non-trivial (but sub-optimal) bounds for any learning algorithm that
outputs hypotheses from a class of bounded VC dimension. We prove that the CMI
framework yields the optimal bound on the expected risk of Support Vector
Machines (SVMs) for learning halfspaces. This result is an application of our
general result showing that stable compression schemes Bousquet al. (2020) of
size $k$ have uniformly bounded CMI of order $O(k)$. We further show that an
inherent limitation of proper learning of VC classes contradicts the existence
of a proper learner with constant CMI, and it implies a negative resolution to
an open problem of Steinke and Zakynthinou (2020). We further study the CMI of
empirical risk minimizers (ERMs) of class $H$ and show that it is possible to
output all consistent classifiers (version space) with bounded CMI if and only
if $H$ has a bounded star number (Hanneke and Yang (2015)). Moreover, we prove
a general reduction showing that "leave-one-out" analysis is expressible via
the CMI framework. As a corollary we investigate the CMI of the
one-inclusion-graph algorithm proposed by Haussler et al. (1994). More
generally, we show that the CMI framework is universal in the sense that for
every consistent algorithm and data distribution, the expected risk vanishes as
the number of samples diverges if and only if its evaluated CMI has sublinear
growth with the number of samples.
- Abstract（参考訳）: 本研究では,Steinke と Zakynthinou (2020) の「条件相互情報(CMI)」フレームワークの表現性について検討し,それを応用して,実現可能な設定における一般化境界を証明する統一的フレームワークを提供する予定である。
まず、このフレームワークを用いて、有界VC次元のクラスから仮説を出力する学習アルゴリズムに対して、非自明な(しかし、準最適)境界を表現できることを実証する。
我々は、CMIフレームワークが、ハーフスペースを学習するためのSVM(Support Vector Machines)の予測されるリスクに最適な境界をもたらすことを証明した。
この結果は、安定な圧縮スキーム Bousquet al. (2020) of size $k$ が一様有界 CMI of order $O(k)$ であることを示す一般的な結果の応用である。
さらに、VCクラスの固有学習の制限は、適切な学習者の存在と一定のCMIの存在に矛盾することを示し、これは、Steinke と Zakynthinou (2020) のオープンな問題に対する否定的な解決を意味する。
さらに、クラス$H$の経験的リスク最小化器(ERMs)のCMIを研究し、有界なCMIで全ての一貫した分類器(バージョン空間)を出力することは、$H$が有界な星数を持つ場合に限る(Hanneke and Yang (2015))。
さらに、CMIフレームワークを介して「リーブ・ワン・アウト」解析が表現可能であることを示す。
概説として、Haussler et al. (1994) が提唱した 1-inclusion-graph アルゴリズムの CMI について検討する。
より一般に、CMIフレームワークは、全ての一貫したアルゴリズムとデータ分布に対して、その評価されたCMIがサンプル数とサブ線形成長を持つ場合に限り、期待されるリスクが分散するという意味で普遍的であることを示す。
関連論文リスト
- Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization [36.28082578445787]
我々は,円錐曲線最適化(SCO)の文脈における記憶と学習の相互作用について検討する。
我々は,Steinke と Zakynthinou が提唱した条件付き相互情報(CMI)の枠組みを用いた記憶の定量化(2020年)
L2$ Lipschitz-bounded set and under strong convexity, every learner with a excess error have CMI bounded by $Omega (1/varepsilon2)$ and $Omega (1/varepsilon)$。
論文 参考訳（メタデータ） (2024-02-14T17:17:30Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Tight Guarantees for Interactive Decision Making with the
Decision-Estimation Coefficient [51.37720227675476]
我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。
我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。
この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
論文 参考訳（メタデータ） (2023-01-19T18:24:08Z) - GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP,
and Beyond [101.5329678997916]
対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。
本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。
低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
論文 参考訳（メタデータ） (2022-11-03T16:42:40Z) - Evaluated CMI Bounds for Meta Learning: Tightness and Expressiveness [14.147617330278662]
評価CMI(e-CMI)を用いたメタ学習のための新しい一般化境界を提案する。
e-CMI フレームワークは、$sqrt の数学カル C(mathcal H)/(nhat n) + 数学カル C(mathcal F)/n $, ここで $mathcal C(cdot)$ は仮説クラスの複雑性測度を表す。
論文 参考訳（メタデータ） (2022-10-12T18:10:59Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳（メタデータ） (2022-08-17T18:49:53Z) - 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) - Understanding Generalization via Leave-One-Out Conditional Mutual
Information [37.49575289458763]
アルゴリズムの条件付き相互情報(CMI)の退行変種は、有界損失関数を持つ学習アルゴリズムの平均一般化誤差を制御する。
0-1の損失でゼロ経験的リスクを達成するアルゴリズム(補間アルゴリズム)を学習するために、我々は、残余CMIと古典的残余誤差推定との明示的な接続を提供する。
論文 参考訳（メタデータ） (2022-06-29T17:57:37Z) - Reasoning About Generalization via Conditional Mutual Information [26.011933885798506]
我々は、Mutual Information (CMI) を用いて、入力がどの程度の精度で認識できるかを定量化する。
CMIのバウンダリは,VC次元,圧縮スキーム,差分プライバシー,その他の手法から得られることを示す。
次に、有界な CMI は様々な種類の一般化を意味することを示す。
論文 参考訳（メタデータ） (2020-01-24T18:13:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。