論文の概要: How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions

• arxiv url: http://arxiv.org/abs/2212.06422v1
• Date: Tue, 13 Dec 2022 08:14:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-14 15:50:30.900005
• Title: How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions
• Title（参考訳）: 独立はどのように一般化に役立つか? ERMの製品分布における試料複合体
• Authors: Tao Lin
• Abstract要約: 経験的リスク最小化(ERM)は製品分布を学習するために指数的なサンプル数を必要とするが,製品分布に特化して設計されたアルゴリズムが必要であることを示す。 これにより、製品配布自体が学習問題を容易なものにしないという結論が導かれる。
• 参考スコア（独自算出の注目度）: 5.553167334488855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While many classical notions of learnability (e.g., PAC learnability) are distribution-free, utilizing the specific structures of an input distribution may improve learning performance. For example, a product distribution on a multi-dimensional input space has a much simpler structure than a correlated distribution. A recent paper [GHTZ21] shows that the sample complexity of a general learning problem on product distributions is polynomial in the input dimension, which is exponentially smaller than that on correlated distributions. However, the learning algorithm they use is not the standard Empirical Risk Minimization (ERM) algorithm. In this note, we characterize the sample complexity of ERM in a general learning problem on product distributions. We show that, even though product distributions are simpler than correlated distributions, ERM still needs an exponential number of samples to learn on product distributions, instead of a polynomial. This leads to the conclusion that a product distribution by itself does not make a learning problem easier -- an algorithm designed specifically for product distributions is needed.
• Abstract（参考訳）: 多くの古典的な学習可能性の概念(例えば、PAC学習可能性)は分布自由であるが、入力分布の特定の構造を利用すると学習性能が向上する。 例えば、多次元入力空間上の積分布は相関分布よりもはるかに単純な構造を持つ。 最近の論文[GHTZ21]では,製品分布における一般学習問題のサンプル複雑性は入力次元の多項式であり,相関分布よりも指数関数的に小さいことが示されている。 しかし、彼らが使用する学習アルゴリズムは、標準的な経験的リスク最小化(ERM)アルゴリズムではない。 本稿では,製品分布の一般学習問題において,ERMのサンプル複雑性を特徴付ける。 製品分布は相関分布よりも単純であるにもかかわらず、ermは多項式ではなく、製品分布について学ぶために指数関数的なサンプル数を必要とすることを示した。 これにより、製品分布自体が学習問題を容易化しないという結論が導かれる。

関連論文リスト

• Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods [14.819629773624348]
  混合線形プログラミング(MILP)は最適化問題をモデル化するための基本的なツールである。 このアプローチの人気は高まっているが、同様のMILPインスタンスのディストリビューションを提供する共通のリポジトリがない。 ML誘導MILP法を進化させるための問題分散ライブラリであるDistributedal MIPLIBを紹介する。
  論文  参考訳（メタデータ） (2024-06-11T05:25:38Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Domain Generalization by Functional Regression [3.209698860006188]
  本稿では,機能回帰問題としての領域一般化について考察する。 我々の概念は、入力の辺分布から入力の対応する条件分布への線形演算子を学習するための新しいアルゴリズムに導かれる。
  論文  参考訳（メタデータ） (2023-02-09T16:07:21Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  粒子フィルタリングは複素系の優れた非線形推定を計算するために用いられる。 粒子フィルタは様々なシナリオにおいて良好な推定値が得られることを示す。
  論文  参考訳（メタデータ） (2021-10-06T16:58:34Z)
• Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
  フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。 本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
  論文  参考訳（メタデータ） (2021-07-12T17:00:59Z)
• Examining and Combating Spurious Features under Distribution Shift [94.31956965507085]
  我々は、最小限の統計量という情報理論の概念を用いて、ロバストで刺激的な表現を定義し、分析する。 入力分布のバイアスしか持たない場合でも、モデルはトレーニングデータから急激な特徴を拾い上げることができることを証明しています。 分析から着想を得た結果,グループDROは,グループ同士の相関関係を直接考慮しない場合に失敗する可能性が示唆された。
  論文  参考訳（メタデータ） (2021-06-14T05:39:09Z)
• An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization [53.592597682854944]
  リスクを最小化するプレイヤーと新しいテストを示す敵の間のオンラインゲームとしてサブグループの一般化を再放送する。 両課題に対してERMは極小最適であることを示す。
  論文  参考訳（メタデータ） (2021-02-25T19:06:48Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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