論文の概要: A Fourier Approach to Mixture Learning

• arxiv url: http://arxiv.org/abs/2210.02415v1
• Date: Wed, 5 Oct 2022 17:35:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-06 13:44:01.294635
• Title: A Fourier Approach to Mixture Learning
• Title（参考訳）: 混合学習のためのフーリエアプローチ
• Authors: Mingda Qiao, Guru Guruganesh, Ankit Singh Rawat, Kumar Avinava Dubey, Manzil Zaheer
• Abstract要約: d = O(log k/loglog k)$ dimensions under separation $d/sqrtlog k (modulo factor)。 我々の結果は、分布のフーリエスペクトルの穏やかな条件の下で、非ガウス分布の混合を学習するために容易に拡張できる。
• 参考スコア（独自算出の注目度）: 47.54965202881905
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the problem of learning mixtures of spherical Gaussians. Given samples from mixture $\frac{1}{k}\sum_{j=1}^{k}\mathcal{N}(\mu_j, I_d)$, the goal is to estimate the means $\mu_1, \mu_2, \ldots, \mu_k \in \mathbb{R}^d$ up to a small error. The hardness of this learning problem can be measured by the separation $\Delta$ defined as the minimum distance between all pairs of means. Regev and Vijayaraghavan (2017) showed that with $\Delta = \Omega(\sqrt{\log k})$ separation, the means can be learned using $\mathrm{poly}(k, d)$ samples, whereas super-polynomially many samples are required if $\Delta = o(\sqrt{\log k})$ and $d = \Omega(\log k)$. This leaves open the low-dimensional regime where $d = o(\log k)$. In this work, we give an algorithm that efficiently learns the means in $d = O(\log k/\log\log k)$ dimensions under separation $d/\sqrt{\log k}$ (modulo doubly logarithmic factors). This separation is strictly smaller than $\sqrt{\log k}$, and is also shown to be necessary. Along with the results of Regev and Vijayaraghavan (2017), our work almost pins down the critical separation threshold at which efficient parameter learning becomes possible for spherical Gaussian mixtures. More generally, our algorithm runs in time $\mathrm{poly}(k)\cdot f(d, \Delta, \epsilon)$, and is thus fixed-parameter tractable in parameters $d$, $\Delta$ and $\epsilon$. Our approach is based on estimating the Fourier transform of the mixture at carefully chosen frequencies, and both the algorithm and its analysis are simple and elementary. Our positive results can be easily extended to learning mixtures of non-Gaussian distributions, under a mild condition on the Fourier spectrum of the distribution.
• Abstract（参考訳）: 球状ガウスの混合物を学習する問題を再検討する。 混合 $\frac{1}{k}\sum_{j=1}^{k}\mathcal{n}(\mu_j, i_d)$ からのサンプルが与えられた場合、目標は$\mu_1, \mu_2, \ldots, \mu_k \in \mathbb{r}^d$ を小さな誤差まで推定することである。 この学習問題の難しさは、すべての手段間の最小距離として定義される分離$\Delta$によって測定できる。 Regev と Vijayaraghavan (2017) は、$\Delta = \Omega(\sqrt{\log k})$ 分離によって、この手段は $\mathrm{poly}(k, d)$ サンプルを用いて学習できることを示したが、超多項式的に、$\Delta = o(\sqrt{\log k})$ と $d = \Omega(\log k)$ が要求される。 これにより、$d = o(\log k)$ という低次元のレギュレーションが生まれる。 本研究では,$d = O(\log k/\log k)$ dimensions under separation $d/\sqrt{\log k}$ (modulo doublely logarithmic factor) で効率よく平均を学習するアルゴリズムを提案する。 この分離は$\sqrt{\log k}$よりも厳密に小さく、必要であることが示されている。 Regev と Vijayaraghavan (2017) の結果とともに、球状ガウス混合に対して効率的なパラメータ学習が可能である臨界分離しきい値のほとんどを導いた。 より一般的に、我々のアルゴリズムは時間$\mathrm{poly}(k)\cdot f(d, \Delta, \epsilon)$で実行され、従ってパラメータ$d$、$\Delta$および$\epsilon$で固定パラメータを抽出可能である。 本手法は, 混合液のフーリエ変換を注意深く選択した周波数で推定し, アルゴリズムと解析は単純かつ初等的である。 我々の正の結果は、分布のフーリエスペクトルの穏やかな条件の下で、非ガウス分布の学習混合物に容易に拡張できる。

関連論文リスト

• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
  シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。 適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
  論文  参考訳（メタデータ） (2024-11-08T17:10:38Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• 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)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Multimeasurement Generative Models [7.502947376736449]
  我々は、密度$p_X$ in $mathbbRd$を未知分布からサンプリングする問題を学習とサンプリングの問題を$p_mathbfY$ in $mathbbRMd$とする。
  論文  参考訳（メタデータ） (2021-12-18T02:11:36Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
  標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。 これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
  論文  参考訳（メタデータ） (2020-04-13T08:06:29Z)

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

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