論文の概要: Generalization Guarantees via Algorithm-dependent Rademacher Complexity

• arxiv url: http://arxiv.org/abs/2307.02501v1
• Date: Tue, 4 Jul 2023 18:37:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-07 16:42:07.686127
• Title: Generalization Guarantees via Algorithm-dependent Rademacher Complexity
• Title（参考訳）: アルゴリズム依存ラデマッハ錯体による一般化保証
• Authors: Sarah Sachs, Tim van Erven, Liam Hodgkinson, Rajiv Khanna, Umut Simsekli
• Abstract要約: 本稿では,アルゴリズムおよびデータ依存仮説クラスの経験的ラデマッハ複雑性である一般化誤差を制御する尺度を提案する。 有限フラクタル次元に基づく新しい境界を得るが、これは (a) 従来のフラクタル型境界を連続的な仮説クラスから有限的な仮説クラスに拡張し、 (b) 相互情報項を避ける。
• 参考スコア（独自算出の注目度）: 33.408679482592426
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithm- and data-dependent generalization bounds are required to explain the generalization behavior of modern machine learning algorithms. In this context, there exists information theoretic generalization bounds that involve (various forms of) mutual information, as well as bounds based on hypothesis set stability. We propose a conceptually related, but technically distinct complexity measure to control generalization error, which is the empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class. Combining standard properties of Rademacher complexity with the convenient structure of this class, we are able to (i) obtain novel bounds based on the finite fractal dimension, which (a) extend previous fractal dimension-type bounds from continuous to finite hypothesis classes, and (b) avoid a mutual information term that was required in prior work; (ii) we greatly simplify the proof of a recent dimension-independent generalization bound for stochastic gradient descent; and (iii) we easily recover results for VC classes and compression schemes, similar to approaches based on conditional mutual information.
• Abstract（参考訳）: アルゴリズムとデータ依存の一般化境界は、現代の機械学習アルゴリズムの一般化挙動を説明するために必要である。 この文脈では、(様々な形の)相互情報を含む情報理論の一般化境界と、仮説集合の安定性に基づく境界が存在する。 本稿では、アルゴリズムとデータ依存仮説クラスの経験的ラデマッハ複雑性である一般化誤差を制御するための概念的だが技術的に異なる複雑性尺度を提案する。 Rademacher複雑性の標準的な性質と、このクラスの便利な構造を組み合わせることで、我々は、 (i)有限フラクタル次元に基づく新たな境界を得る。 (a)従来のフラクタル次元型境界を連続から有限の仮説クラスに拡張し、 b) 先行業務において必要とされた相互情報用語を避けること (II) 確率勾配降下に対する最近の次元独立一般化の証明を大幅に単純化する。 (iii)条件付き相互情報に基づくアプローチと同様に,vcクラスや圧縮スキームの結果の復元が容易である。

関連論文リスト

• Slicing Mutual Information Generalization Bounds for Neural Networks [14.48773730230054]
  我々は、ディープラーニングアルゴリズムに適した、より厳密な情報理論の一般化バウンダリを導入する。 我々の境界は、標準MI境界よりも有意な計算的および統計的優位性を提供する。 パラメータがランダムな部分空間に正確に横たわる必要がないアルゴリズムに解析を拡張します。
  論文  参考訳（メタデータ） (2024-06-06T13:15:37Z)
• The Computational Complexity of Concise Hypersphere Classification [49.57441416941195]
  本稿では,二元データに対する超球分類問題の複雑性理論による最初の研究である。 パラメータ化複雑性のパラダイムを用いて、入力データに存在する可能性のある構造特性の影響を分析する。
  論文  参考訳（メタデータ） (2023-12-12T09:33:03Z)
• A unified framework for information-theoretic generalization bounds [8.04975023021212]
  本稿では,学習アルゴリズムにおける情報理論の一般化境界を導出するための一般的な手法を提案する。 主な技術的ツールは、測度の変化と、$L_psi_p$ Orlicz空間におけるヤングの不等式の緩和に基づく確率的デコリレーション補題である。
  論文  参考訳（メタデータ） (2023-05-18T15:36:20Z)
• Information Theoretic Lower Bounds for Information Theoretic Upper Bounds [14.268363583731848]
  コンベックス最適化の文脈における出力モデルと経験的一般化の関係について検討する。 本研究は,真のリスク最小化には相互情報が必要であることを明らかにする。 既存の情報理論の一般化境界は、SGDや正規化などのアルゴリズムの能力を捉えるのに不足している。
  論文  参考訳（メタデータ） (2023-02-09T20:42:36Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  本稿では,データセットからのインスタンスのバッチを進化状態にエンコードするエネルギー制約拡散モデルを提案する。 任意のインスタンス対間の対拡散強度に対する閉形式最適推定を示唆する厳密な理論を提供する。 各種タスクにおいて優れた性能を有する汎用エンコーダバックボーンとして,本モデルの適用性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-01-23T15:18:54Z)
• 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)
• Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems [5.099537069575897]
  非負・正の行列とテンソル完備問題を定義・解決するための新しい一貫性に基づくアプローチを導入する。 単一特性/制約: 単位スケールの一貫性を保ち、解の存在を保証し、比較的弱いサポート仮定の下では、一意性を示す。
  論文  参考訳（メタデータ） (2022-04-04T19:42:46Z)
• Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms [12.020634332110147]
  我々は、レート歪曲理論のレンズを通して、新しい一般化が有界であることを証明している。 我々の結果は、一般化に関するより統一された視点をもたらし、将来の研究方向性を開拓する。
  論文  参考訳（メタデータ） (2022-03-04T18:12:31Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Dimension Free Generalization Bounds for Non Linear Metric Learning [61.193693608166114]
  我々はスパース体制と非スパース体制という2つの体制に対して一様一般化境界を提供する。 解の異なる新しい性質を頼りにすることで、次元自由一般化保証を提供することができることを示す。
  論文  参考訳（メタデータ） (2021-02-07T14:47:00Z)

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

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