論文の概要: Towards Fundamental Limits for Active Multi-distribution Learning

• arxiv url: http://arxiv.org/abs/2506.17607v1
• Date: Sat, 21 Jun 2025 06:08:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-24 19:06:36.498184
• Title: Towards Fundamental Limits for Active Multi-distribution Learning
• Title（参考訳）: アクティブマルチディストリビューション学習の基礎的限界に向けて
• Authors: Chicheng Zhang, Yihan Zhou,
• Abstract要約: 我々は,多分布学習のための新しいアルゴリズムを開発し,ラベルの複雑さを向上する。 実現可能な設定のバウンダリは情報理論的に最適であり、設定の$knu/varepsilon2$項は適切な学習者にとって基本的なものであることを示す。
• 参考スコア（独自算出の注目度）: 16.639855803241524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-distribution learning extends agnostic Probably Approximately Correct (PAC) learning to the setting in which a family of $k$ distributions, $\{D_i\}_{i\in[k]}$, is considered and a classifier's performance is measured by its error under the worst distribution. This problem has attracted a lot of recent interests due to its applications in collaborative learning, fairness, and robustness. Despite a rather complete picture of sample complexity of passive multi-distribution learning, research on active multi-distribution learning remains scarce, with algorithms whose optimality remaining unknown. In this paper, we develop new algorithms for active multi-distribution learning and establish improved label complexity upper and lower bounds, in distribution-dependent and distribution-free settings. Specifically, in the near-realizable setting we prove an upper bound of $\widetilde{O}\Bigl(\theta_{\max}(d+k)\ln\frac{1}{\varepsilon}\Bigr)$ and $\widetilde{O}\Bigl(\theta_{\max}(d+k)\Bigl(\ln\frac{1}{\varepsilon}+\frac{\nu^2}{\varepsilon^2}\Bigr)+\frac{k\nu}{\varepsilon^2}\Bigr)$ in the realizable and agnostic settings respectively, where $\theta_{\max}$ is the maximum disagreement coefficient among the $k$ distributions, $d$ is the VC dimension of the hypothesis class, $\nu$ is the multi-distribution error of the best hypothesis, and $\varepsilon$ is the target excess error. Moreover, we show that the bound in the realizable setting is information-theoretically optimal and that the $k\nu/\varepsilon^2$ term in the agnostic setting is fundamental for proper learners. We also establish instance-dependent sample complexity bound for passive multidistribution learning that smoothly interpolates between realizable and agnostic regimes~\citep{blum2017collaborative,zhang2024optimal}, which may be of independent interest.
• Abstract（参考訳）: マルチディストリビューション学習は、$k$の分布の族である$\{D_i\}_{i\in[k]}$が考慮され、その誤差によって分類器のパフォーマンスが測定される設定まで、確率的確率的近似(PAC)学習を延長する。 この問題は、協調学習、公正性、堅牢性に応用されているため、近年多くの関心を集めている。 受動型マルチディストリビューション学習のサンプルの複雑さの比較的完全な図面にもかかわらず、能動型マルチディストリビューション学習の研究は依然として乏しいままであり、最適性は未知である。 本稿では,分布依存型および分布自由な環境下で,多分布学習のための新しいアルゴリズムを開発し,ラベルの複雑さを高次と低次に向上させる。 具体的には、ほぼ実現可能な設定で、$\widetilde{O}\Bigl(\theta_{\max}(d+k)\ln\frac{1}{\varepsilon}\Bigr)$と$\widetilde{O}\Bigl(\theta_{\max}(d+k)\Bigl(\ln\frac{1}{\varepsilon}+\frac{\nu^2}{\varepsilon^2}\Bigr)+\frac{k\nu}{\varepsilon^2}\Bigr)$の上限を証明する。 さらに、実現可能なセッティングのバウンダリが情報理論的に最適であること、そして、アグノスティックセッティングの$k\nu/\varepsilon^2$項が適切な学習者にとって基本であることを示す。 また、インスタンス依存型サンプル複雑性を、実現可能と不可知のレジームを円滑に補間する受動的多分布学習に限定して確立する。

関連論文リスト

• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。 一定の正則性特性を満たす有限範囲の良好なMIMに着目する。 ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
  論文  参考訳（メタデータ） (2025-02-13T17:37:42Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• 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)
• The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
  マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。 PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。 本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
  論文  参考訳（メタデータ） (2023-07-22T18:02:53Z)
• Agnostic Multi-Group Active Learning [24.97598179536084]
  能動的学習の観点から,この問題の変種を考察し,学習者がコレクションの各分布からどの例をラベル付けするかを判断する権限を付与する。 我々の主な課題は、不一致に基づくアクティブラーニングのような標準的なアクティブラーニング技術が、マルチグループラーニングの目的に直接適用されないことである。 既存のアルゴリズムを改良し、多群学習の非依存的な定式化のための一貫した能動的学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-06-02T21:24:13Z)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。 我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T03:20:40Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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