論文の概要: Learning Mixtures of Spherical Gaussians via Fourier Analysis

• arxiv url: http://arxiv.org/abs/2004.05813v2
• Date: Sat, 11 Jul 2020 09:08:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-14 00:28:07.577079
• Title: Learning Mixtures of Spherical Gaussians via Fourier Analysis
• Title（参考訳）: フーリエ解析による球状ガウスの混合学習
• Authors: Somnath Chakraborty, Hariharan Narayanan
• Abstract要約: 標本と計算複雑性の有界性は、$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)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
• 参考スコア（独自算出の注目度）: 0.5381004207943596
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suppose that we are given independent, identically distributed samples $x_l$ from a mixture $\mu$ of no more than $k$ of $d$-dimensional spherical gaussian distributions $\mu_i$ with variance $1$, such that the minimum $\ell_2$ distance between two distinct centers $y_l$ and $y_j$ is greater than $\sqrt{d} \Delta$ for some $c \leq \Delta $, where $c\in (0,1)$ is a small positive universal constant. We develop a randomized algorithm that learns the centers $y_l$ of the gaussians, to within an $\ell_2$ distance of $\delta < \frac{\Delta\sqrt{d}}{2}$ and the weights $w_l$ to within $cw_{min}$ with probability greater than $1 - \exp(-k/c)$. The number of samples and the computational time is bounded above by $poly(k, d, \frac{1}{\delta})$. Such a bound on the sample and computational complexity was previously unknown when $\omega(1) \leq d \leq O(\log k)$. When $d = O(1)$, this follows from work of Regev and Vijayaraghavan. These authors also show that the sample complexity of learning a random mixture of gaussians in a ball of radius $\Theta(\sqrt{d})$ in $d$ dimensions, when $d$ is $\Theta( \log k)$ is at least $poly(k, \frac{1}{\delta})$, showing that our result is tight in this case.
• Abstract（参考訳）: 独立に同じ分布のサンプルである$x_l$が$k$$$d$-次元球面ガウス分布の$\mu_i$の混合から$x_l$を与えられると仮定すると、$c\in (0, 1)$が小さな正の普遍定数であるとき、$y_l$と$y_j$の間の最小の$\ell_2$の距離が$\sqrt{d} \Delta$より大きいような分散の$$$$である。 我々は、ガウス人の中心である$y_l$を学習するランダム化アルゴリズムを開発し、$\delta < \frac{\delta\sqrt{d}}{2}$ から$\ell_2$ の範囲内までと、その重みは $w_l$ から $cw_{min}$ 以内であり、確率は 1 - \exp(-k/c)$ 以上である。 サンプルの数と計算時間は、$poly(k, d, \frac{1}{\delta})$で制限される。 このようなサンプルのバウンドと計算複雑性は、これまでは$\omega(1) \leq d \leq o(\log k)$ で知られていなかった。 d = O(1)$ の場合、これはRegev と Vijayaraghavan の仕事に従う。 これらの著者は、半径$\Theta(\sqrt{d})$ in $d$ dimensions, if $d$ is $\Theta( \log k)$ is least $poly(k, \frac{1}{\delta})$ でガウスのランダムな混合を学習するサンプルの複雑さも示しており、この場合、我々の結果は厳密であることを示している。

関連論文リスト

• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
  1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。 目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
  論文  参考訳（メタデータ） (2024-03-14T15:04:45Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• 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)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures [36.91281862322494]
  EMアルゴリズムは、$tildeOBig(minBigfrac1(1-2delta_*)sqrtfracdn,frac1|theta_*|sqrtfracdn,left(fracdnright)1/4BigBig)$を$OBig(frac1|theta_*|2Big以下で適応的に達成することを示した。
  論文  参考訳（メタデータ） (2021-03-29T14:28:17Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• 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)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)
• Sample Amplification: Increasing Dataset Size even when Learning is Impossible [15.864702679819544]
  未知のディストリビューションから引き出されたデータである$D$が、このデータセットを増幅し、さらに大きなサンプルセットを$D$から抽出したように見えるように出力することは、どの程度まで可能か? この問題は次のように定式化する: $left(n, n + Theta(fracnsqrtk)right)$アンプが存在するが、小さな定数全変動距離への分布を学習するには$Theta(d)$サンプルが必要である。
  論文  参考訳（メタデータ） (2019-04-26T21:42:44Z)

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

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