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 Cerr>0 such that if a pseudolabeler boldsymbolβpl can achieve classification error at most Cerr, then for any varepsilon>0, an iterative self-training algorithm initialized at boldsymbolβ0 := boldsymbolβpl using pseudolabels hat y = sgn(langle boldsymbolβt, xrangle) and using at most tilde O(d/varepsilon2) unlabeled examples suffices to learn the Bayes-optimal classifier up to varepsilon 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 boldsymbolβpl with classification error Cerr using only O(d) labeled examples (i.e., independent of varepsilon). Together our results imply that mixture models can be learned to within varepsilon of the Bayes-optimal accuracy using at most O(d) labeled examples and tilde O(d/varepsilon2) unlabeled examples by way of a semi-supervised self-training algorithm.