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

Spencer Frei, Difan Zou, Zixiang Chen, Quanquan Gu

Introduction

Self-training, a semi-supervised learning paradigm where a model iteratively labels its own data to refine its parameters, has become a cornerstone of modern machine learning. Despite its widespread empirical success in domains ranging from natural language processing to computer vision, a rigorous mathematical understanding of its efficacy has remained elusive. A common concern is the potential for error amplification: if a model is imperfect, why doesn't it simply become more confident in its own mistakes?

This paper provides a theoretical breakthrough by proving that for a broad class of data distributions, self-training can transform a mediocre "weak learner" into a "strong learner" using primarily unlabeled data. The authors demonstrate that under specific conditions, the model corrects its initial errors and converges toward the Bayes-optimal classifier.

Problem Formulation

The study focuses on a binary classification problem within a generative mixture model. The data is assumed to come from two clusters (modes) that are rotationally symmetric and sub-exponential (e.g., Gaussians or log-concave distributions). Formally, the data is defined as $x|y \sim z + y\mu$, where $z$ represents noise and $\mu$ is the mean parameter. A key requirement is that the distributions satisfy anti-concentration properties, ensuring that data points are not excessively clustered near the decision boundary, which facilitates the gradient descent process.

Methodology: The Two-Stage Algorithm

The proposed approach consists of a two-stage algorithm designed to leverage both limited labeled data and abundant unlabeled data.

  1. Phase 1 (Supervised Initialization): Standard Stochastic Gradient Descent (SGD) is performed on a small set of labeled data to obtain an initial classifier, denoted as $\beta_{pl}$.
  2. Phase 2 (Iterative Self-training): This initial classifier is used to generate pseudolabels for a large batch of unlabeled data. The model is then updated using weight-normalized gradient descent on either logistic or exponential loss.
Algorithm 1: Self-training with pseudolabels and weight normalization.

The weight normalization step (Step 6 in Algorithm 1) is critical. By normalizing the weights at each iteration, the algorithm prevents the model from merely increasing its confidence (magnitude) without improving the actual decision boundary.

Theoretical Results

The authors establish several key theoretical guarantees for the self-training algorithm:

  • The "Weak to Strong" Threshold: There exists a universal error constant $C_{err}$. If the initial labeled data provides a classifier with an error rate below this threshold, self-training is guaranteed to converge to the optimal solution. This implies that the starting model only needs to be "not bad" rather than "good."
  • Sample Complexity: The amount of labeled data required is $O(d)$, where $d$ is the dimensionality. Notably, this requirement is independent of the desired final precision $\epsilon$. To reach an error within $\epsilon$ of the optimum, the algorithm requires $\tilde{O}(d/\epsilon^2)$ unlabeled samples.
  • Bayes-Optimality: The algorithm is proven to converge to the Bayes-optimal classifier, the theoretical limit of accuracy for the given distribution.
  • Proxy PL Inequality: The researchers prove a "proxy Polyak-Łojasiewicz (PL) inequality," showing that even with potentially incorrect pseudolabels, the average gradient direction consistently points toward the true mean of the data clusters.

Conclusion and Future Work

This work provides a formal justification for self-training in mixture models, showing that unlabeled data can effectively "finish" the training started by a small labeled set. While the results are currently restricted to linear classifiers and specific mixture assumptions, they offer a foundational step toward understanding more complex semi-supervised learning in deep neural networks. Future research may focus on improving unlabeled sample complexity and extending these proofs to non-linear architectures.

Summary updated

Abstract

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{err}}>0$ such that if a pseudolabeler $\boldsymbol{\beta}_{\mathrm{pl}}$ can achieve classification error at most $C_{\mathrm{err}}$, then for any $\varepsilon>0$, an iterative self-training algorithm initialized at $\boldsymbol{\beta}_0 := \boldsymbol{\beta}_{\mathrm{pl}}$ using pseudolabels $\hat y = \mathrm{sgn}(\langle \boldsymbol{\beta}_t, \mathbf{x}\rangle)$ and using at most $\tilde O(d/\varepsilon^2)$ 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{\beta}_{\mathrm{pl}}$ with classification error $C_{\mathrm{err}}$ 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/\varepsilon^2)$ unlabeled examples by way of a semi-supervised self-training algorithm.
BibTeX
@inproceedings{frei2022self,
  author = {Spencer Frei and Difan Zou and Zixiang Chen and Quanquan Gu},
  title = {{Self-training Converts Weak Learners to Strong Learners in Mixture Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=ONIU0BJAI7R},
}
Figure