English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Learning a Gaussian mixture model (GMM) is a fundamental problem in machinelearning, learning theory, and statistics. One notion of learning a GMM isproper learning: here, the goal is to find a mixture of $k$ Gaussians$\mathcal{M}$ that is close to the density $f$ of the unknown distribution fromwhich we draw samples. The distance between $\mathcal{M}$ and $f$ is typicallymeasured in the total variation or $L_1$-norm.  We give an algorithm for learning a mixture of $k$ univariate Gaussians thatis nearly optimal for any fixed $k$. The sample complexity of our algorithm is$\tilde{O}(\frac{k}{\epsilon^2})$ and the running time is $(k \cdot\log\frac{1}{\epsilon})^{O(k^4)} + \tilde{O}(\frac{k}{\epsilon^2})$. It iswell-known that this sample complexity is optimal (up to logarithmic factors),and it was already achieved by prior work. However, the best known timecomplexity for proper learning a $k$-GMM was$\tilde{O}(\frac{1}{\epsilon^{3k-1}})$. In particular, the dependence between$\frac{1}{\epsilon}$ and $k$ was exponential. We significantly improve thisdependence by replacing the $\frac{1}{\epsilon}$ term with a $\log\frac{1}{\epsilon}$ while only increasing the exponent moderately. Hence, forany fixed $k$, the $\tilde{O} (\frac{k}{\epsilon^2})$ term dominates ourrunning time, and thus our algorithm runs in time which is nearly-linear in thenumber of samples drawn. Achieving a running time of $\textrm{poly}(k,\frac{1}{\epsilon})$ for proper learning of $k$-GMMs has recently been statedas an open problem by multiple researchers, and we make progress on thisquestion.  Moreover, our approach offers an agnostic learning guarantee: our algorithmreturns a good GMM even if the distribution we are sampling from is not amixture of Gaussians. To the best of our knowledge, our algorithm is the firstagnostic proper learning algorithm for GMMs.

A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k