Fugu-MT 論文翻訳(概要): The sample complexity of multi-distribution learning

論文の概要: 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 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 [17.96094201655567]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文参考訳（メタデータ） (2023-02-26T01:15:32Z)
Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文参考訳（メタデータ） (2023-02-20T23:29:43Z)
On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文参考訳（メタデータ） (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)
Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文参考訳（メタデータ） (2020-05-13T16:44:12Z)
SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。実験では最先端のアルゴリズムよりも優れています。
論文参考訳（メタデータ） (2020-02-22T01:03:33Z)

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