論文の概要: Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise

• arxiv url: http://arxiv.org/abs/2602.21039v1
• Date: Tue, 24 Feb 2026 16:00:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.826168
• Title: Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise
• Title（参考訳）: マルチディストリビューション学習はPAC学習と同じくらい簡単か:境界ラベル雑音によるシャープレート
• Authors: Rafael Hanashiro, Abhishek Shetty, Patrick Jaillet,
• Abstract要約: k$分布の学習は、各分布が別々に学習されない限り、一定の雑音レベル下であっても、$k/2$で遅い速度でスケーリングすることを示した。 重要な技術的貢献は、ほぼ最適性を証明する統計的コストをキャプチャする構造化仮説テストフレームワークである。
• 参考スコア（独自算出の注目度）: 26.182166506085114
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Towards understanding the statistical complexity of learning from heterogeneous sources, we study the problem of multi-distribution learning. Given $k$ data sources, the goal is to output a classifier for each source by exploiting shared structure to reduce sample complexity. We focus on the bounded label noise setting to determine whether the fast $1/ε$ rates achievable in single-task learning extend to this regime with minimal dependence on $k$. Surprisingly, we show that this is not the case. We demonstrate that learning across $k$ distributions inherently incurs slow rates scaling with $k/ε^2$, even under constant noise levels, unless each distribution is learned separately. A key technical contribution is a structured hypothesis-testing framework that captures the statistical cost of certifying near-optimality under bounded noise-a cost we show is unavoidable in the multi-distribution setting. Finally, we prove that when competing with the stronger benchmark of each distribution's optimal Bayes error, the sample complexity incurs a \textit{multiplicative} penalty in $k$. This establishes a \textit{statistical} separation between random classification noise and Massart noise, highlighting a fundamental barrier unique to learning from multiple sources.
• Abstract（参考訳）: 異種源からの学習の統計的複雑さを理解するために,多分布学習の課題について検討する。 k$のデータソースが与えられたら、サンプルの複雑さを減らすために共有構造を利用することで、各ソースの分類器を出力する。 単一タスク学習において達成可能な1/ε$の高速なレートが、$k$への依存を最小限に抑えながら、この体制に拡張できるかどうかを判断するために、境界ラベルのノイズ設定に焦点をあてる。 意外なことに、これはそうではない。 我々は,各分布が別々に学習されない限り,一定の雑音レベル下であっても,$k/ε^2$でスケールする速度を本質的に低下させることを示した。 重要な技術的貢献は、有界雑音下でのほぼ最適性を証明する統計的コストをキャプチャする構造化仮説テストフレームワークである。 最後に、各分布の最適ベイズ誤差のより強いベンチマークと競合する場合、サンプルの複雑さは$k$でtextit{multiplicative}ペナルティを生じることを証明した。 これにより、ランダムな分類ノイズとマスアートノイズの分離が確立され、複数の情報源からの学習に特有の基本的な障壁が浮かび上がる。

関連論文リスト

• Contextual Learning for Stochastic Optimization [1.0819408603463425]
  最適化によってモチベーションを得て,文脈値分布のサンプルから学習する問題を導入する。 各サンプルは、コンテキスト$x$と、対応する実値分布$D_x$から引き出されたランダム変数からなる。
  論文  参考訳（メタデータ） (2025-05-22T16:01:49Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Pitfalls of Gaussians as a noise distribution in NCE [22.23473249312549]
  ノイズコントラスト推定(NCE)は,比例定数までパラメータ化された確率密度関数を学習するための一般的な手法である。 我々は、$q$の選択がNCEの計算効率と統計効率に大きな影響を及ぼすことを示した。
  論文  参考訳（メタデータ） (2022-10-01T04:42:56Z)
• Label-Noise Learning with Intrinsically Long-Tailed Data [65.41318436799993]
  本稿では,本質的な長期データを用いたラベルノイズ学習のための学習フレームワークを提案する。 具体的には, 2段階の2次元試料選択法(TABASCO)を提案する。
  論文  参考訳（メタデータ） (2022-08-21T07:47:05Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。 我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。 すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
  論文  参考訳（メタデータ） (2022-05-12T14:40:18Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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