We provide an algorithm for properly learning mixtures of two single-dimensional Gaussians without any separability assumptions. Our sample complexity is optimal up to optimal logarithmic factors. Our algorithm significantly improves upon both Kalai et. al., whose algorithm has a prohibitive dependence on $1/\varepsilon.
We provide an algorithm for properly learning mixtures of two
single-dimensional Gaussians without any separability assumptions. Given
samples from an unknown mixture, our algorithm
outputs a mixture that is -close in total variation distance, in
time . Our sample complexity is optimal up to
logarithmic factors, and significantly improves upon both Kalai et al., whose
algorithm has a prohibitive dependence on , and Feldman et al.,
whose algorithm requires bounds on the mixture parameters and depends
pseudo-polynomially in these parameters.
One of our main contributions is an improved and generalized algorithm for
selecting a good candidate distribution from among competing hypotheses.
Namely, given a collection of hypotheses containing at least one candidate
that is -close to an unknown distribution, our algorithm outputs a
candidate which is -close to the distribution. The algorithm
requires samples from the unknown distribution and
time, which improves previous such results (such
as the Scheff\'e estimator) from a quadratic dependence of the running time on
to quasilinear. Given the wide use of such results for the purpose of
hypothesis selection, our improved algorithm implies immediate improvements to
any such use.