論文の概要: The sample complexity of multi-distribution learning
- arxiv url: http://arxiv.org/abs/2312.04027v2
- Date: Mon, 29 Jan 2024 02:17:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-30 20:55:54.728508
- Title: The sample complexity of multi-distribution learning
- Title(参考訳): 複数分散学習のサンプル複雑性
- Authors: Binghui Peng
- Abstract要約: サンプル複雑性$widetildeO((d+k)epsilon-2) cdot (k/epsilon)o(1)$は、Awasthi, Haghtalab, Zhao の COLT 2023 開放問題を解く。
- 参考スコア(独自算出の注目度): 17.45683822446751
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-distribution learning generalizes the classic PAC learning to handle
data coming from multiple distributions. Given a set of $k$ data distributions
and a hypothesis class of VC dimension $d$, the goal is to learn a hypothesis
that minimizes the maximum population loss over $k$ distributions, up to
$\epsilon$ additive error. In this paper, we settle the sample complexity of
multi-distribution learning by giving an algorithm of sample complexity
$\widetilde{O}((d+k)\epsilon^{-2}) \cdot (k/\epsilon)^{o(1)}$. This matches the
lower bound up to sub-polynomial factor and resolves the COLT 2023 open problem
of Awasthi, Haghtalab and Zhao [AHZ23].
- Abstract(参考訳): 複数分布学習は、複数の分布から来るデータを扱う古典的なpac学習を一般化する。
データ分散のセットとVC次元の仮説クラスが$d$であることを考えると、その目標は、最大人口損失を$k$の分布で最大で$\epsilon$加法誤差まで最小化する仮説を学習することである。
本稿では、サンプル複雑性のアルゴリズムを$\widetilde{O}((d+k)\epsilon^{-2}) \cdot (k/\epsilon)^{o(1)}$とすることで、マルチディストリビューション学習のサンプル複雑性を解明する。
これは下界のポリノミカル因子と一致し、Awasthi, Haghtalab, Zhao [AHZ23] の COLT 2023 の開問題を解く。
関連論文リスト
- Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。
これは文学の下位境界に到達した最初のアルゴリズムと分析である。
論文 参考訳(メタデータ) (2023-10-13T03:08:59Z) - 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) - A Finite Sample Complexity Bound for Distributionally Robust Q-learning [16.88062487980405]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。
ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。
これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文 参考訳(メタデータ) (2023-02-26T01:15:32Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [87.09946206044332]
社会的・現実世界の考察は、協調的、集団的分布的堅牢性、公正な連合学習など、多分野の学習パラダイムを生み出している。
本稿では、これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
私たちのアルゴリズムの設計と分析は、プレイヤーの安価なワンオフサンプルやより高価な再利用可能なサンプルへのアクセスをトレードオフできるミラー・ダイスンの拡張によって実現されます。
論文 参考訳(メタデータ) (2022-10-22T19:07:26Z) - Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文 参考訳(メタデータ) (2021-08-17T21:11:20Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳(メタデータ) (2020-12-31T18:24:41Z) - Faster PAC Learning and Smaller Coresets via Smoothed Analysis [25.358415142404752]
PAC学習は通常、$n$アイテムから小さなサブセット(varepsilon$-sample/net)を計算することを目的としています。
スムーズな解析から着想を得て、クエリに対する強調誤差(最悪のケースではなく)を近似する自然な一般化を提案する。
論文 参考訳(メタデータ) (2020-06-09T18:25:34Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳(メタデータ) (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。