論文の概要: An Information-Theoretic Approach to Generalization Theory
- arxiv url: http://arxiv.org/abs/2408.13275v1
- Date: Tue, 20 Aug 2024 10:08:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-27 20:20:40.606485
- Title: An Information-Theoretic Approach to Generalization Theory
- Title(参考訳): 一般化理論への情報理論的アプローチ
- Authors: Borja Rodríguez-Gálvez, Ragnar Thobaben, Mikael Skoglund,
- Abstract要約: 学習アルゴリズムと学習データ間の依存度を定量化する情報理論境界を解析する。
一定のプライバシーパラメータを持つ場合であっても,最大リークが制限されたアルゴリズムにより一般化が保証されることを示す。
- 参考スコア(独自算出の注目度): 27.87324770020133
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the in-distribution generalization of machine learning algorithms. We depart from traditional complexity-based approaches by analyzing information-theoretic bounds that quantify the dependence between a learning algorithm and the training data. We consider two categories of generalization guarantees: 1) Guarantees in expectation: These bounds measure performance in the average case. Here, the dependence between the algorithm and the data is often captured by information measures. While these measures offer an intuitive interpretation, they overlook the geometry of the algorithm's hypothesis class. Here, we introduce bounds using the Wasserstein distance to incorporate geometry, and a structured, systematic method to derive bounds capturing the dependence between the algorithm and an individual datum, and between the algorithm and subsets of the training data. 2) PAC-Bayesian guarantees: These bounds measure the performance level with high probability. Here, the dependence between the algorithm and the data is often measured by the relative entropy. We establish connections between the Seeger--Langford and Catoni's bounds, revealing that the former is optimized by the Gibbs posterior. We introduce novel, tighter bounds for various types of loss functions. To achieve this, we introduce a new technique to optimize parameters in probabilistic statements. To study the limitations of these approaches, we present a counter-example where most of the information-theoretic bounds fail while traditional approaches do not. Finally, we explore the relationship between privacy and generalization. We show that algorithms with a bounded maximal leakage generalize. For discrete data, we derive new bounds for differentially private algorithms that guarantee generalization even with a constant privacy parameter, which is in contrast to previous bounds in the literature.
- Abstract(参考訳): 機械学習アルゴリズムの分布内一般化について検討する。
我々は,学習アルゴリズムと学習データ間の依存度を定量化する情報理論境界を解析することによって,従来の複雑性に基づくアプローチから逸脱する。
1)予測における保証:これらの境界は平均的な場合のパフォーマンスを測定する。
ここでは、アルゴリズムとデータ間の依存は、しばしば情報測度によって捉えられる。
これらの測度は直観的な解釈を提供するが、アルゴリズムの仮説クラスの幾何学を見落としている。
本稿では、ワッサーシュタイン距離を用いて幾何学を組み込む境界と、アルゴリズムと個々のダタム、およびトレーニングデータのアルゴリズムとサブセット間の依存を捉えた境界を導出する構造化された体系的手法を紹介する。
2) PAC-ベイジアン保証: これらの境界は高い確率で性能レベルを測定する。
ここでは、アルゴリズムとデータの依存度は、しばしば相対エントロピーによって測定される。
我々はシーガー=ラングフォードとカトニの境界の間の接続を確立し、前者はギブスの後部によって最適化されていることを明らかにした。
様々な種類の損失関数に対して,新しい,より厳密な境界を導入する。
そこで本研究では,確率的文のパラメータを最適化する新しい手法を提案する。
これらの手法の限界を研究するために,従来の手法ではそうでなくても,情報理論的境界の大部分が失敗する反例を示す。
最後に、プライバシと一般化の関係について検討する。
有界な最大リークを持つアルゴリズムが一般化されることを示す。
離散データに対しては,従来の文献のバウンダリとは対照的に,プライバシーパラメータが一定であっても一般化を保証する,微分プライベートアルゴリズムの新たなバウンダリを導出する。
関連論文リスト
- Slicing Mutual Information Generalization Bounds for Neural Networks [14.48773730230054]
我々は、ディープラーニングアルゴリズムに適した、より厳密な情報理論の一般化バウンダリを導入する。
我々の境界は、標準MI境界よりも有意な計算的および統計的優位性を提供する。
パラメータがランダムな部分空間に正確に横たわる必要がないアルゴリズムに解析を拡張します。
論文 参考訳(メタデータ) (2024-06-06T13:15:37Z) - Information Theoretic Lower Bounds for Information Theoretic Upper
Bounds [14.268363583731848]
コンベックス最適化の文脈における出力モデルと経験的一般化の関係について検討する。
本研究は,真のリスク最小化には相互情報が必要であることを明らかにする。
既存の情報理論の一般化境界は、SGDや正規化などのアルゴリズムの能力を捉えるのに不足している。
論文 参考訳(メタデータ) (2023-02-09T20:42:36Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-31T19:14:30Z) - 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) - Generalization Bounds for Data-Driven Numerical Linear Algebra [24.961270871124217]
データ駆動アルゴリズムは、トレーニングされた入力サンプルから学習することで、未知のアプリケーション固有の分布からの入力に内部構造やパラメータを適用することができる。
いくつかの最近の研究は、数値線形代数における問題にこのアプローチを適用し、性能において顕著な経験的利得を得た。
本研究では、Gupta と Roughgarden が提案するデータ駆動アルゴリズム選択のためのPAC学習フレームワークにおいて、これらのアルゴリズムの一般化境界を証明する。
論文 参考訳(メタデータ) (2022-06-16T02:23:45Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳(メタデータ) (2021-05-23T19:21:55Z) - Privacy Analysis of Online Learning Algorithms via Contraction
Coefficients [5.333582981327498]
差分プライバシー保証は、$f$-divergencesの強いデータ処理の不等式から導かれる収縮係数の直接適用によって決定できることを示す。
また、このフレームワークは、トレーニングデータセットをワンパスで実装できるバッチ学習アルゴリズムに調整可能であることも示しています。
論文 参考訳(メタデータ) (2020-12-20T22:02:15Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Tighter Generalization Bounds for Iterative Differentially Private
Learning Algorithms [95.73230376153872]
本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。
我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。
次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
論文 参考訳(メタデータ) (2020-07-18T09:12:03Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。