Strength from Weakness: Fast Learning Using Weak Supervision

Joshua Robinson, Stefanie Jegelka, Suvrit Sra

In many critical domains—such as medicine or scientific research—obtaining high-quality "strong" labels is prohibitively expensive or requires rare expertise. To compensate, practitioners often turn to "weak" labels: noisy data, coarse categories (e.g., labeling a "Golden Retriever" simply as a "dog"), or related proxy tasks.

While we know empirically that pretraining on weak labels helps, the theoretical "why" has historically been murky. Standard supervised learning theory suggests that generalization error typically decreases at a "slow" rate of $O(1/\sqrt{n})$, where $n$ is the number of samples. This paper provides a theoretical framework proving that pretraining on abundant weak data can fundamentally change how fast a model learns, accelerating the generalization rate on a small, strongly labeled dataset to the "fast" rate of $O(1/n)$.

The Pretrain-Finetune Framework

To understand under what conditions large amounts of weak data can provably help us learn a better model than strong labels alone, the authors analyze a two-step Pretrain-Finetune meta-algorithm:

  1. Pretraining: Learn a feature embedding $g$ using a large dataset of $m$ weak labels.
  2. Finetuning: Train a strong predictor $f$ on top of those features using a small dataset of $n$ strong labels.
Schema for the pretrain-finetune approach, showing how weak data informs the embedding used for the strong task.

To bridge the theoretical gap between these two tasks, the researchers introduce two key pillars:

  • Shared Mutual Embedding: They assume both tasks share an underlying latent representation that makes the strong task "easy" to solve.
  • The Central Condition: This is a technical condition from learning theory that characterizes "easy" problems where the loss function is well-behaved enough to allow for fast $O(1/n)$ convergence.

The authors' main contribution is proving that even if we only have an estimate of the embedding (learned from weak data), the central condition can still be approximately satisfied, leading to accelerated learning.

Breaking the Speed Limit: Key Theoretical Insights

The most significant finding of the paper is the "Fast Rate" Breakthrough. Weak supervision can push a model into a fast rate regime: if you have enough weak data (specifically $m = \Omega(n^2)$ for discrete labels), the error on the strong task drops as $O(1/n)$ rather than the usual $O(1/\sqrt{n})$.

Furthermore, this learning rate isn't a binary switch between slow and fast. It exhibits smooth interpolation, scaling as $O(n^{-\gamma})$, where $\gamma$ ranges from $0.5$ to $1.0$ depending on the quantity and quality of the weak labels.

Interestingly, the generalization bound for the strong task depends on the complexity of the strong predictor, but is largely independent of the complexity of the weak feature map. This provides a strong theoretical justification for using massive, complex models for pretraining even when the final target dataset is tiny.

Empirical Evidence

The researchers validated their theory across several computer vision and NLP benchmarks, including CIFAR-10, CIFAR-100, MNIST, SVHN, and TREC (a natural language dataset for question categorization). They tested both noisy label simulations (mimicking human error) and coarse label experiments.

The empirical results closely match the theoretical predictions. By plotting error against the number of strong labels on a log-log scale, the "learning rate" $\gamma$ is represented by the slope of the line.

Generalization error demonstrating accelerated learning rates. As weak data increases, the learning rate γ steepens significantly, reaching 1.52 in this coarse-label configuration.
  • Noisy Labels: On CIFAR-10, the learning rate $\gamma$ improved from 0.44 (no weak data) to 0.92 (with $m = \Omega(n^2)$ weak labels), nearly reaching the ideal fast rate of 1.0.
  • Coarse Labels: For MNIST, the effect was even more pronounced, with $\gamma$ reaching 1.52 in some configurations, significantly outperforming standard supervised learning.
  • Consistency: The trend held across vision and text, showing that the "strength from weakness" effect is a general property of the pretrain-finetune paradigm.

Limitations and Future Work

While the results are promising, the current framework assumes the marginal distribution of features $P(X)$ is the same for both weak and strong tasks. It doesn't yet account for "domain shift," where the weak data comes from a fundamentally different source than the strong data.

Additionally, the theory relies on the existence of a shared embedding that makes the strong task satisfy the "central condition." If the tasks are entirely unrelated, weak supervision won't provide this acceleration.

Future directions suggested by the authors include extending this framework to multi-task learning and investigating "label budgets"—developing principled ways to decide exactly how much to spend on a few expert labels versus many cheap, noisy ones.

Summary updated

Abstract

We study generalization properties of weakly supervised learning, that is, learning where only a few "strong" labels (the actual target for prediction) are present but many more "weak" labels are available. In particular, we show that pretraining using weak labels and finetuning using strong can accelerate the learning rate for the strong task to the fast rate of O(1/n), where n is the number of strongly labeled data points. This acceleration can happen even if, by itself, the strongly labeled data admits only the slower O(1/\sqrt{n}) rate. The acceleration depends continuously on the number of weak labels available, and on the relation between the two tasks. Our theoretical results are reflected empirically across a range of tasks and illustrate how weak labels speed up learning on the strong task.
BibTeX
@inproceedings{robinson2020strength,
  author = {Joshua Robinson and Stefanie Jegelka and Suvrit Sra},
  title = {{Strength from Weakness: Fast Learning Using Weak Supervision}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=S1GnP-Enqk},
}
Figure