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.
Introduction
In modern machine learning, the abundance of unlabeled data stands in stark contrast to the scarcity of high-quality, human-annotated labels. To bridge this gap, practitioners often turn to self-training (or pseudo-labeling), a semi-supervised technique where a model is iteratively refined using its own predictions on unlabeled data. While this approach has driven breakthroughs in domains like computer vision and natural language processing (e.g., Noisy Student, BERT), its theoretical foundations have remained elusive.
This paper provides a rigorous analysis of self-training, demonstrating that for a broad class of mixture models, self-training can transform a "weak" initial learner into a "strong" Bayes-optimal classifier using a sample complexity that is highly efficient in terms of labeled data.
Problem Formulation
The study focuses on a binary classification problem where data is generated from a mixture of two symmetric, unimodal distributions. These distributions are assumed to be isotropic and rotationally symmetric, satisfying concentration and anti-concentration properties common to log-concave distributions. This framework generalizes beyond simple Gaussian mixtures to include a wide variety of real-world-like data geometries.
The objective is to reach the Bayes-optimal classifier, the theoretical limit of accuracy for the given distribution, using as few labeled samples as possible.
The Iterative Self-Training Algorithm
The authors analyze a specific, practical implementation of self-training characterized by three main phases:
- Initialization: A "weak learner" $\boldsymbol{\beta}_{\mathrm{pl}}$ is obtained via standard supervised gradient descent on a small labeled dataset.
- Pseudo-labeling: For each batch of unlabeled data, the current model generates labels based on its own predictions: $\hat{y} = \mathrm{sgn}(\langle \boldsymbol{\beta}_t, \mathbf{x} \rangle)$.
- Weight-Normalized Gradient Descent: The model updates its weights using these pseudo-labels. A critical component of this process is weight normalization, which keeps the norm of the weight vector constant, and temperature scaling, which stabilizes training. The analysis reveals that normalization is the "secret sauce" that prevents the gradient descent process from diverging, ensuring the model focuses on the direction of the optimal separator.
Key Theoretical Insights
The Threshold of Success
The paper identifies a universal constant, $C_{\mathrm{err}}$. If the initial weak learner achieves an error rate below this threshold, self-training is guaranteed to converge toward the Bayes-optimal solution. If the initial error exceeds this constant, the model risks amplifying its own noise rather than learning the underlying structure.
Sample Complexity and Precision
A major contribution of this work is the characterization of the trade-off between labeled and unlabeled data:
- Labeled Data: Only $O(d)$ labeled samples are required to reach the $C_{\mathrm{err}}$ threshold. Notably, this requirement is independent of the final desired precision $\varepsilon$.
- Unlabeled Data: To achieve a precision of $\varepsilon$ relative to the Bayes-optimal error, the algorithm requires $\tilde{O}(d/\varepsilon^2)$ unlabeled samples.
This implies that one can achieve near-perfect classification by simply increasing the volume of cheap, unlabeled data, provided a baseline level of performance is established with a fixed amount of labeled data.
Geometric Convergence
The authors prove that during the self-training process, the angle between the current classifier and the optimal classifier shrinks at a geometric rate. This provides a clear mathematical explanation for the rapid convergence often observed in empirical self-training applications.
Conclusion and Future Work
This research provides one of the first theoretical guarantees that standard, gradient-based self-training can achieve optimal performance in mixture models with a constant number of labeled examples relative to precision. While the current proof is limited to linear separators and specific mixture structures, it establishes a foundational framework for understanding semi-supervised learning.
Future research directions include extending these proofs to non-convex optimization landscapes and non-linear classifiers, such as deep neural networks, to further bridge the gap between statistical theory and modern deep learning practice.
Summary updated