論文の概要: The Sample Complexity of Multi-Distribution Learning for VC Classes

• arxiv url: http://arxiv.org/abs/2307.12135v1
• Date: Sat, 22 Jul 2023 18:02:53 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-25 17:48:03.927786
• Title: The Sample Complexity of Multi-Distribution Learning for VC Classes
• Title（参考訳）: VC授業におけるマルチディストリビューション学習の複雑さ
• Authors: Pranjal Awasthi, Nika Haghtalab, Eric Zhao
• Abstract要約: マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。 PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。 本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
• 参考スコア（独自算出の注目度）: 25.73730126599202
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-distribution learning is a natural generalization of PAC learning to settings with multiple data distributions. There remains a significant gap between the known upper and lower bounds for PAC-learnable classes. In particular, though we understand the sample complexity of learning a VC dimension d class on $k$ distributions to be $O(\epsilon^{-2} \ln(k)(d + k) + \min\{\epsilon^{-1} dk, \epsilon^{-4} \ln(k) d\})$, the best lower bound is $\Omega(\epsilon^{-2}(d + k \ln(k)))$. We discuss recent progress on this problem and some hurdles that are fundamental to the use of game dynamics in statistical learning.
• Abstract（参考訳）: マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に自然な一般化である。 PAC学習クラスにおける既知の上境界と下限の間には大きなギャップが残っている。 特に、$k$分布上のVC次元dクラスを$O(\epsilon^{-2} \ln(k)(d + k) + \min\{\epsilon^{-1} dk, \epsilon^{-4} \ln(k) d\})$と学習する際のサンプルの複雑さは理解しているが、最良の下限は$\Omega(\epsilon^{-2}(d + k \ln(k)))$である。 本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるハードルについて論じる。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• The sample complexity of multi-distribution learning [17.45683822446751]
  サンプル複雑性$widetildeO((d+k)epsilon-2) cdot (k/epsilon)o(1)$は、Awasthi, Haghtalab, Zhao の COLT 2023 開放問題を解く。
  論文  参考訳（メタデータ） (2023-12-07T03:53:17Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Private and polynomial time algorithms for learning Gaussians and beyond [13.947461378608525]
  本稿では,$(varepsilon, delta)$differentially private (DP) 統計的推定を非私的推定に還元する枠組みを提案する。 我々は、(制限のない)ガウスの堅牢な学習のための$(varepsilon, delta)$-DPアルゴリズムを初めて提供する。
  論文  参考訳（メタデータ） (2021-11-22T16:25:51Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
  適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。 双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
  論文  参考訳（メタデータ） (2020-05-24T18:11:57Z)

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

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