論文の概要: 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}ペナルティを生じることを証明した。
これにより、ランダムな分類ノイズとマスアートノイズの分離が確立され、複数の情報源からの学習に特有の基本的な障壁が浮かび上がる。
関連論文リスト
- Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。
一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。
一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
論文 参考訳（メタデータ） (2026-02-24T06:15:59Z) - Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations [0.723486289593299]
2018年、アシュティアーニらは、分布クラスの構造的性質として、元々リトルストーンとウォーマス (1986) によるエンハンブル圧縮性を再編成した。
我々は、必要かつ十分な条件のセットを条件として、摂動サンプルからでも、サンプル圧縮可能なファミリーが学習可能であることを確証する。
論文 参考訳（メタデータ） (2025-06-07T01:11:50Z) - 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) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - 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) - The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
この仮定から逸脱すると、実際により良い統計的推定結果が得られることが示される。
特に、最適な雑音分布は、データと異なり、また、別の家族からさえも異なる。
論文 参考訳（メタデータ） (2022-03-02T13:59:20Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。