Self-training Converts Weak Learners to Strong Learners in Mixture Models

We consider a binary classification problem when the data comes from a mixture of two rotationally symmetric distributions satisfying concentration and anti-concentration properties enjoyed by log-concave distributions among others. We show that there exists a universal constant $C_{\mathrm{e}\mathrm{r}\mathrm{r}}>0$ such that if a pseudolabeler ${\mathit{\beta }}_{\mathrm{p}\mathrm{l}}$ can achieve classification error at most $C_{\mathrm{e}\mathrm{r}\mathrm{r}}$, then for any $\epsilon >0$, an iterative self-training algorithm initialized at $\boldsymbol{\beta}0 := \boldsymbol{\beta}{$\mathrm{p}\mathrm{l}$}$usingpseudolabels$\hat y = $\mathrm{s}\mathrm{g}\mathrm{n}$(\langle \boldsymbol{\beta}_t, $\mathbf{x}$\rangle)$ and using at most $\tilde{O}(d\mathrm{/}{\epsilon }^2)$ unlabeled examples suffices to learn the Bayes-optimal classifier up to $\epsilon$ error, where $d$ is the ambient dimension. That is, self-training converts weak learners to strong learners using only unlabeled examples. We additionally show that by running gradient descent on the logistic loss one can obtain a pseudolabeler ${\mathit{\beta }}_{\mathrm{p}\mathrm{l}}$ with classification error $C_{\mathrm{e}\mathrm{r}\mathrm{r}}$ using only $O(d)$ labeled examples (i.e., independent of $\epsilon$). Together our results imply that mixture models can be learned to within $\epsilon$ of the Bayes-optimal accuracy using at most $O(d)$ labeled examples and $\tilde{O}(d\mathrm{/}{\epsilon }^2)$ unlabeled examples by way of a semi-supervised self-training algorithm.