Self-Training Converts Weak Learners to Strong Learners in Mixture Models
summary
Shows that self-training with pseudo-labelers turns a classifier that has constant error below a fixed C_error constant into one within ε of the Bayes optimal on a two‑component isotropic log‑concave mixture. Algorithm uses weight‑normalized SGD with batch size Θ(1/ε), runtime Θ(d/ε) and requires Θ(d/ε^2) unlabeled examples; initialization needs a pseudo‑labeler with error < C_error, which supervised logistic GD on O(1) labeled samples achieves when cluster means have constant separation.
AI-written summary · about
chapters (7)
- 0:00Intro
- 1:26Self-training algorithms
- 2:06Mixture model setup
- 3:03Algorithm: self-training with online batch SGD
- 5:29Attaining a pseudolabeler with constant error
- 9:44Proof idea: treat pseudolabel errors as noise, use ideas from learning halfspaces w/ noise
- 11:25Optimization details
related talks
42mRobust Mixture Learning when Outliers Overwhelm Small Groups
45mUnderstanding Contrastive Learning and Self-training
43mBeyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active Learning
01h 07mLarge-Scale Private Learning, Part II
23mLearning with Limited Labels & Weak Supervision
53mDesigning Robust Learners
37mEfficient Algorithms for Reliable Machine Learning
01h 12mRecent Progress in High-Dimensional Learning