Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2004.05813 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912577048543232 |
|---|---|
| author | Chakraborty, Somnath Narayanan, Hariharan |
| author_facet | Chakraborty, Somnath Narayanan, Hariharan |
| contents | Suppose that we are given independent, identically distributed samples $x_l$ from a mixture $μ$ of no more than $k$ of $d$-dimensional spherical gaussian distributions $μ_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} Δ$ for some $c \leq Δ$, 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 $δ< \frac{Δ\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}δ)$. Such a bound on the sample and computational complexity was previously unknown when $ω(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 $Θ(\sqrt{d})$ in $d$ dimensions, when $d$ is $Θ( \log k)$ is at least $poly(k, \frac{1}δ)$, showing that our result is tight in this case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2004_05813 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Learning Mixtures of Spherical Gaussians via Fourier Analysis Chakraborty, Somnath Narayanan, Hariharan Data Structures and Algorithms Machine Learning Optimization and Control Suppose that we are given independent, identically distributed samples $x_l$ from a mixture $μ$ of no more than $k$ of $d$-dimensional spherical gaussian distributions $μ_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} Δ$ for some $c \leq Δ$, 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 $δ< \frac{Δ\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}δ)$. Such a bound on the sample and computational complexity was previously unknown when $ω(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 $Θ(\sqrt{d})$ in $d$ dimensions, when $d$ is $Θ( \log k)$ is at least $poly(k, \frac{1}δ)$, showing that our result is tight in this case. |
| title | Learning Mixtures of Spherical Gaussians via Fourier Analysis |
| topic | Data Structures and Algorithms Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2004.05813 |