Abstract
Creating large-scale high-quality labeled datasets is a major bottleneck in supervised machine learning workflows. Threshold-based auto-labeling (TBAL), where validation data obtained from humans is used to find a confidence threshold above which the data is machine-labeled, reduces reliance on manual annotation. TBAL is emerging as a widely-used solution in practice. Given the long shelf-life and diverse usage of the resulting datasets, understanding when the data obtained by such auto-labeling systems can be relied on is crucial. This is the first work to analyze TBAL systems and derive sample complexity bounds on the amount of human-labeled validation data required for guaranteeing the quality of machine-labeled data. Our results provide two crucial insights. First, reasonable chunks of unlabeled data can be automatically and accurately labeled by seemingly bad models. Second, a hidden downside of TBAL systems is potentially prohibitive validation data usage. Together, these insights describe the promise and pitfalls of using such systems. We validate our theoretical guarantees with extensive experiments on synthetic and real datasets.
Introduction
The "data bottleneck" remains a primary obstacle in modern supervised machine learning. While models with billions of parameters are now common, training them requires millions of high-quality labels—a process that is both expensive and slow when relying solely on human annotators.
To mitigate this, practitioners frequently employ Threshold-based Auto-labeling (TBAL). In this paradigm, a model labels its own data when its prediction confidence exceeds a specific threshold. While integrated into commercial tools like Amazon SageMaker Ground Truth, TBAL has lacked a rigorous mathematical foundation. This research provides the first theoretical framework for TBAL, exploring the relationship between validation data requirements and labeling reliability.
Methodology
The study analyzes a standard iterative TBAL workflow consisting of four main stages:
- Training: A model is initially trained on a small "seed" set of human-labeled data.
- Threshold Estimation: Using a separate human-labeled validation set, the system identifies a confidence threshold where the predicted error is guaranteed to be below a user-defined tolerance ($\epsilon_a$).
- Auto-labeling: Data points with confidence scores exceeding this threshold are automatically labeled and added to the dataset.
- Iteration: Remaining "hard" points are selected via active learning for human labeling, and the cycle repeats.
The core contribution is a sample complexity bound derived using Rademacher complexity. This bound quantifies the exact number of validation points required to ensure that the auto-labeling error remains within the desired threshold.
Experimental Evaluation
The theoretical framework was validated using both synthetic and real-world datasets:
- Synthetic: Unit-Ball (high-dimensional), Circles, and XOR datasets, specifically chosen to test models that are "misspecified" or simpler than the underlying data distribution.
- Real-world: Tiny-ImageNet, IMDB Reviews (sentiment analysis), CIFAR-10, and MNIST.
Key Insights: The "Bad Model" Paradox and the Validation Tax
A central finding of this work is that a model with poor global accuracy can still function as an effective auto-labeler. For instance, a linear model applied to non-linear "Circle" data may have a 50% global error rate but maintain 99% accuracy within specific "pockets of certainty." TBAL successfully identifies these regions.
However, this benefit comes with a "Validation Tax." To mathematically guarantee high-quality labels, the required amount of human-labeled validation data scales with $O(1/\epsilon_a^2)$. For very low error tolerances, the validation set size can paradoxically exceed the size of the training set.
Results and Discussion
- Theoretical Tightness: Experiments on the "Unit-Ball" dataset confirmed that practical worst-case error rates closely track the derived theoretical bounds.
- Coverage Advantages: On the XOR dataset, TBAL successfully labeled nearly 100% of the data with less than 1% error, whereas standard Active Learning (AL) combined with selective classification could only safely label 25%.
- UCB Importance: The use of an Upper Confidence Bound (UCB) during threshold estimation is vital; without it, systems tend to underestimate error, leading to noisy datasets.
Limitations and Future Directions
The effectiveness of TBAL is highly dependent on model calibration. If a model is overconfident yet incorrect—a common issue in deep learning—TBAL may fail to find safe auto-labeling regions, as seen in experiments with CIFAR-10. Future research should explore how these bounds evolve with dynamic hypothesis spaces in deep neural networks and investigate "Active Testing" to reduce the high cost of validation data.
Summary updated