論文の概要: A super-polynomial lower bound for learning nonparametric mixtures
- arxiv url: http://arxiv.org/abs/2203.15150v1
- Date: Mon, 28 Mar 2022 23:53:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-30 13:33:48.518635
- Title: A super-polynomial lower bound for learning 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 a super-polynomial lower bound on the sample complexity
of learning the component distributions in such models. Namely, we are given
i.i.d. samples from $f$ where $$ f=\sum_{i=1}^k w_i f_i, \quad\sum_{i=1}^k
w_i=1, \quad w_i>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_i)\cap \text{supp}(\nu_j)=\emptyset$. Our main result shows
that $\Omega((\frac{1}{\varepsilon})^{C\log\log \frac{1}{\varepsilon}})$
samples are required for estimating each $f_i$. The proof relies on a fast rate
for approximation with Gaussians, which may be of independent interest. This
result has important implications for the hardness of learning more general
nonparametric latent variable models that arise in machine learning
applications.
- Abstract（参考訳）: 有限混合系で非パラメトリック分布を学習する問題について検討し、そのモデルにおける成分分布を学習するサンプル複雑性の超多項下界を確立する。
すなわち、$f$ where$f=\sum_{i=1}^k w_i f_i, \quad\sum_{i=1}^k w_i=1, \quad w_i>0 $$ のサンプルが与えられる。
f_i$の仮定がなければ、この問題は正しくない。
成分 $f_i$ を識別するために、各$f_i$ はガウスの畳み込みとコンパクトに支持された密度 $\nu_i$ と $\text{supp}(\nu_i)\cap \text{supp}(\nu_j)=\emptyset$ と書けると仮定する。
我々の主な結果は、$\Omega((\frac{1}{\varepsilon})^{C\log \frac{1}{\varepsilon}})$サンプルが各$f_i$を推定するために必要であることを示している。
この証明はガウスの近似の速さに依存しており、これは独立興味を持つかもしれない。
この結果は、機械学習アプリケーションで発生するより一般的な非パラメトリック潜在変数モデルを学ぶことの難しさに重要な意味を持つ。
関連論文リスト
- A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。