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

We provide an algorithm for properly learning mixtures of twosingle-dimensional Gaussians without any separability assumptions. Given$\tilde{O}(1/\varepsilon^2)$ samples from an unknown mixture, our algorithmoutputs a mixture that is $\varepsilon$-close in total variation distance, intime $\tilde{O}(1/\varepsilon^5)$. Our sample complexity is optimal up tologarithmic factors, and significantly improves upon both Kalai et al., whosealgorithm has a prohibitive dependence on $1/\varepsilon$, and Feldman et al.,whose algorithm requires bounds on the mixture parameters and dependspseudo-polynomially in these parameters.  One of our main contributions is an improved and generalized algorithm forselecting a good candidate distribution from among competing hypotheses.Namely, given a collection of $N$ hypotheses containing at least one candidatethat is $\varepsilon$-close to an unknown distribution, our algorithm outputs acandidate which is $O(\varepsilon)$-close to the distribution. The algorithmrequires ${O}(\log{N}/\varepsilon^2)$ samples from the unknown distribution and${O}(N \log N/\varepsilon^2)$ time, which improves previous such results (suchas the Scheff\'e estimator) from a quadratic dependence of the running time on$N$ to quasilinear. Given the wide use of such results for the purpose ofhypothesis selection, our improved algorithm implies immediate improvements toany such use.

Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians