Fugu-MT 論文翻訳(概要): Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures

論文の概要: Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures

arxiv url: http://arxiv.org/abs/2203.15150v3
Date: Tue, 4 Jul 2023 17:26:07 GMT
ステータス: 処理完了
システム内更新日: 2023-07-07 00:36:47.657770
Title: Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures
Title（参考訳）: 単純非パラメトリック混合学習の硬さに関する厳密な境界
Authors: Bryon Aragam, Wai Ming Tai
Abstract要約: 有限混合系における非パラメトリック分布の学習問題について検討する。このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
参考スコア（独自算出の注目度）: 9.053430799456587
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of learning nonparametric distributions in a finite mixture, and establish tight bounds on the sample complexity for learning the component distributions in such models. Namely, we are given i.i.d. samples from a pdf $f$ where $$ f=w_1f_1+w_2f_2, \quad w_1+w_2=1, \quad w_1,w_2>0 $$ and we are interested in learning each component $f_i$. Without any assumptions on $f_i$, this problem is ill-posed. In order to identify the components $f_i$, we assume that each $f_i$ can be written as a convolution of a Gaussian and a compactly supported density $\nu_i$ with $\text{supp}(\nu_1)\cap \text{supp}(\nu_2)=\emptyset$. Our main result shows that $(\frac{1}{\varepsilon})^{\Omega(\log\log \frac{1}{\varepsilon})}$ samples are required for estimating each $f_i$. The proof relies on a quantitative Tauberian theorem that yields a fast rate of approximation with Gaussians, which may be of independent interest. To show this is tight, we also propose an algorithm that uses $(\frac{1}{\varepsilon})^{O(\log\log \frac{1}{\varepsilon})}$ samples to estimate each $f_i$. Unlike existing approaches to learning latent variable models based on moment-matching and tensor methods, our proof instead involves a delicate analysis of an ill-conditioned linear system via orthogonal functions. Combining these bounds, we conclude that the optimal sample complexity of this problem properly lies in between polynomial and exponential, which is not common in learning theory.
Abstract（参考訳）: 有限混合系における非パラメトリック分布の学習問題について検討し、そのようなモデルにおける成分分布の学習におけるサンプル複雑性の厳密な境界を確立する。すなわち、pdf$f$から、$$f=w_1f_1+w_2f_2, \quad w_1+w_2=1, \quad w_1,w_2>0$$のサンプルが与えられる。 f_i$の仮定がなければ、この問題は正しくない。成分 $f_i$ を識別するために、各$f_i$ はガウスの畳み込みとコンパクトに支持された密度 $\nu_i$ と $\text{supp}(\nu_1)\cap \text{supp}(\nu_2)=\emptyset$ と書けると仮定する。主な結果は、$(\frac{1}{\varepsilon})^{\Omega(\log\log \frac{1}{\varepsilon})}$サンプルが各$f_i$を推定するために必要であることを示している。この証明は、独立利害関係にあるガウシアンとの近似速度が速い量的タウバーの定理に依存している。これは厳密であることを示すために、各$f_i$を推定するために$(\frac{1}{\varepsilon})^{o(\log\log \frac{1}{\varepsilon})}$サンプルを使用するアルゴリズムも提案する。モーメントマッチングとテンソル法に基づく潜在変数モデルを学習する既存のアプローチとは異なり、我々の証明は直交関数による不条件線形系の微妙な解析を伴う。これらの境界を組み合わせることで、この問題の最適サンプル複雑性は多項式と指数関数の間にあると結論づけ、これは学習理論では一般的ではない。

関連論文リスト

Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文参考訳（メタデータ） (2024-06-03T17:56:58Z)
A Fourier Approach to Mixture Learning [46.995354373649675]
d = O(log k/loglog k)$ dimensions under separation $d/sqrtlog k (modulo factor)。我々の結果は、分布のフーリエスペクトルの穏やかな条件の下で、非ガウス分布の混合を学習するために容易に拡張できる。
論文参考訳（メタデータ） (2022-10-05T17:35:46Z)
Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文参考訳（メタデータ） (2022-09-09T23:35:25Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文参考訳（メタデータ） (2021-08-17T21:11:20Z)
Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文参考訳（メタデータ） (2020-10-07T01:43:07Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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