Source-linked AI summary
Batch Active Learning at Scale
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, Sanjiv Kumar
TL;DR
Large-batch active learning must reduce labeling and training costs without losing too much adaptivity or selecting redundant examples. Cluster-Margin combines low-confidence selection with clustering-based diversification, scales to 100K–1M batches, and shows improved label efficiency against baselines while receiving an initial theoretical analysis.
Problem
Large batch sizes amplify reduced adaptivity and redundant sampling while requiring algorithms that do not become computational bottlenecks.
Method
Cluster-Margin selects low-margin examples, clusters the unlabeled pool with HAC, and uses round-robin sampling to diversify each batch.
Results
40% of the labels were needed by Cluster-Margin compared with the next-best method to achieve the same target performance in the best Open Images result.
Takeaways & Limitations
Cluster-Margin supports efficient sampling for very large batches and also performs well in smaller batch settings used by recent benchmarks.
Takeaways & Limitations
Extending the theoretical analysis to more general settings remains an important future direction.
Abstract
from arXiv · showhide
The ability to train complex and highly effective models often requires an abundance of training data, which can easily become a bottleneck in cost, time, and computational resources. Batch active learning, which adaptively issues batched queries to a labeling oracle, is a common approach for addressing this problem. The practical benefits of batch sampling come with the downside of less adaptivity and the risk of sampling redundant examples within a batch -- a risk that grows with the batch size. In this work, we analyze an efficient active learning algorithm, which focuses on the large batch setting. In particular, we show that our sampling method, which combines notions of uncertainty and diversity, easily scales to batch sizes (100K-1M) several orders of magnitude larger than used in previous studies and provides significant improvements in model training efficiency compared to recent baselines. Finally, we provide an initial theoretical analysis, proving label complexity guarantees for a related sampling method, which we show is approximately equivalent to our sampling method in specific settings.
1 Introduction
Batch active learning reduces retraining and labeling-oracle overhead by querying in batches, but large batches worsen redundancy, reduce adaptivity, and create scalability challenges. This paper introduces Cluster-Margin for batches far larger than prior studies and evaluates its efficiency and theoretical connections.
- Batch active learning reduces the frequency of model updates and labeling-oracle calls, trading lower overhead for reduced adaptivity and more redundant examples within batches.
- Large datasets motivate batch sizes one to two orders of magnitude larger than the thousands of points evaluated in previous work.
- Cluster-Margin combines uncertainty and diversity by clustering the least-confident examples with HAC and sampling across clusters.
- 40% of the labels were needed by Cluster-Margin compared with the next-best method to reach the same target performance in the best Open Images result.
- The paper also reports competitive performance on CIFAR10, CIFAR100, and SVHN and label-complexity guarantees for a related margin-based clustering sampler.
2 Algorithm
Cluster-Margin first embeds and clusters the unlabeled pool, then selects low-confidence examples while using round-robin sampling to diversify each batch. Its one-time clustering design supports efficient large-batch sampling.
- Sampling steps: Cluster-Margin measures uncertainty with the margin between the two largest predicted class probabilities, where lower scores indicate less confidence.
- Clustering step: HAC is run once on embeddings of the entire unlabeled pool as preprocessing, generating clusters reused across sampling iterations.
- Sampling steps: The algorithm selects the km lowest-margin examples, sorts their clusters by size, and samples one example at a time in round-robin order until kt examples are chosen.
- Sampling steps: Sampling starts with the smallest clusters because they represent sparse regions of the embedded distribution and can provide more diverse points.
3 Empirical Evaluation
The evaluation compares Cluster-Margin and established active-learning baselines across very large Open Images batches and smaller image-classification datasets. Cluster-Margin achieves the strongest overall results, especially at 100K and 1M batch sizes, while also performing competitively on smaller datasets.
- Baselines considered: Margin Sampling selects examples with the smallest difference between the first- and second-most probable class probabilities.BADGE instead applies k-MEANS++ to gradient embeddings, while Approximate CoreSet applies greedy k-center to penultimate-layer embeddings.
- Experimental setup: Open Images v6 is a multi-label dataset with 19,957 possible classes and partial annotations, so methods sample image-class pairs.Only a subset of classes is annotated for each image, with approximately six classes annotated per image on average.
- Open Images experiments: Cluster-Margin significantly outperforms all methods on Open Images, reaching pooled AP above 0.76 with approximately 920K labels versus Margin Sampling’s 1.3M.This corresponds to a 29% reduction in labels in the 100K-batch setting.
- Open Images experiments: Cluster-Margin requires only 37% of Margin Sampling’s labels at 1M batches and 71% at 100K batches to reach the same performance.The Margin baseline isolates the effect of diversifying low-confidence examples through clustering.
- Smaller-dataset experiments: On CIFAR10 and CIFAR100, Cluster-Margin outperforms all baselines, while on SVHN it performs similarly to Margin Sampling and above the other methods.CoreSet does not exceed Random Sampling on these datasets, possibly because the experiments use the greedy 2-approximation for k-center.
4 Theoretical Motivation
The paper analyzes Cluster-MarginV, a theory-friendly variant that combines margin-based uncertainty sampling with volume-based diversity selection. Its guarantees improve over Margin sampling under specified settings, with stronger gains in low-dimensional embeddings and large batches, while the general equivalence to Cluster-Margin remains unresolved.
- Cluster-MarginV: Cluster-MarginV first samples uniformly within the margin of a hypothesis consistent with collected labels, then selects a diverse subset using a volume-based sampler.The queried subset is obtained through diversity-enforcing subsampling of points in the low-margin region.
- Label complexity: β = d/ log(k) for a specific hypothesis class and optimal volume-based sampler, suggesting larger improvements when embedding dimension d is small or batch size k is large.The bound applies under the stated hypothesis-class and sampler conditions.
- Label complexity: Replacing uniform low-margin sampling with a β-efficient volume-based sampler improves label complexity by a factor β.The guarantee is established for Cluster-MarginV and is connected to Cluster-Margin in specific settings.
- Label complexity: A low-dimensional embedding can yield label complexity d/ log(k) times smaller than the Margin Algorithm, especially when d is small and k is large.The theoretical comparison is with the Margin Algorithm of Balcan and Long (2013).
- Connection to Cluster-Margin: For one-dimensional uniformly distributed points, the volume-based strategy parallels Cluster-Margin with distance threshold ϵ = 1/k and achieves β = O(1/ log(k)).The volume-based method creates k equal-size clusters and selects their centers, while Cluster-Margin samples randomly from k small clusters.
- Connection to Cluster-Margin: The general equivalence between volume-based samplers and Cluster-Margin remains an open future direction.The paper establishes only an initial connection under specific settings.
5 Conclusion
The paper introduces Cluster-Margin for efficient large-batch active learning and reports effectiveness across very large and small batch settings. It also develops an initial volume-based theoretical analysis to clarify the method’s functioning.
- Conclusion: Cluster-Margin efficiently samples very large batches for training large machine learning models.The algorithm remains effective for batch sizes several orders of magnitude larger than those considered in prior literature.
- Conclusion: Cluster-Margin also performs well in small-batch settings used by recent benchmarks.The conclusion reports effectiveness across both large and commonly adopted small batch sizes.
- Conclusion: The paper provides an initial theoretical analysis based on a volume-based sampling mechanism.This analysis is presented as part of the explanation for Cluster-Margin’s functioning.
A Extended Experiments
The extended experiments section supplies omitted dataset statistics for CIFAR10, CIFAR100, and SVHN.
- Extended experiments: Table 3 reports additional statistics for the CIFAR10, CIFAR100, and SVHN datasets.These statistics were omitted from the paper’s main body.
A.1 Baseline Scalability
The baseline scalability experiments modify BADGE and CoreSet through partitioning when needed, while Margin and Random scale without partitioning. BADGE’s partitioning preserves comparable accuracy on the tested CIFAR10 and SVHN settings.
- Baseline scalability: BADGE partitions the unlabeled pool into m random subsets, runs independently with batch size k/m, and combines the selected samples.The study compares one and ten partitions on CIFAR10 and SVHN.
- Baseline scalability: Comparable accuracy is observed for BADGE with one versus ten partitions on CIFAR10 and SVHN.BADGE with one partition is not reported for CIFAR100 because it could not scale to that dataset.
- Baseline scalability: The same partitioning scheme is applied to CoreSet only for Open Images with 1M batch sizes.Margin and Random scale to all datasets without using partitioning.
A.2 Cluster-Margin Scalability
Cluster-Margin’s preprocessing can be made substantially more scalable by clustering only a small seed set and assigning the remaining embeddings to nearby centroids, without reducing performance at 100K or 1M batch sizes.
- Preprocessing scalability: Cluster-Margin requires HAC on the entire pool as preprocessing, motivating independent techniques to accelerate this step.The full-pool HAC preprocessing can be difficult for large datasets.
- Preprocessing scalability: Multi-round HAC avoids loading a complete graph into memory by repeatedly clustering centroids from the preceding round.Each round builds a nearest-neighbor graph over the prior round’s cluster centroids.
- Cluster assignment: Cluster assignment runs HAC on seed-set embeddings, then assigns the remaining embeddings to their nearest cluster centroid.The seed set contains roughly 275K images, or 3.1% of the full image set; the remaining 96.9% are assigned afterward.
- Cluster assignment: At 100K and 1M batch sizes, cluster assignment performs at least as well as full-pool HAC while reducing clustering from O(n^2 log n) to O(|P|^2 log |P| + |C_P||X \ P|).The reduced runtime uses the seed set and nearest-centroid assignments, with |C_P| ≤ |P|.
B Extended Theoretical Motivation
The theoretical analysis studies Cluster-MarginV under realizable, isotropic log-concave settings and establishes its error and label-complexity guarantees through a margin-region sampling argument.
- Algorithm and setting: Cluster-MarginV is specified as an iterative algorithm that samples low-margin points and uses a volume-based sampler before querying their labels.The pseudocode repeatedly finds a consistent hypothesis, samples within a low-margin region, selects a subset, and updates the labeled set.
- Algorithm and setting: The guarantee assumes realizable labels and an isotropic log-concave distribution in the embedding space.Under these assumptions, the theorem concerns learning a linear separator.
- Guarantees: After n = ⌈log2(1/(cϵ))⌉ iterations, Cluster-MarginV returns with probability 1 − δ a linear separator of error at most ϵ.The theorem sets margin widths and sample sizes according to the stated constants and parameters.
- Guarantees: Cluster-MarginV has label complexity O(β(d + log(1/δ) + log log(1/ϵ)) log(1/ϵ)), improving over the original Margin Algorithm by a β factor.The comparison is made under the same assumptions as the theorem.
- Proof strategy: The proof bounds the error region by splitting it into a low-margin component P1 and its complement P2, then analyzing both separately.The P2 component uses a known margin theorem, while P1 is controlled through uniform sampling and VC bounds.
B.1 Proof of Theorem 4.2
The proof analyzes a volume-based sampler for one-dimensional threshold functions by comparing quantile-based sampling with uniform sampling through the maximum gaps they leave unresolved.
- Setup: The one-dimensional setting uses i.i.d. points with cumulative distribution F and threshold functions on [0, 1], assuming k = o(√n).The sampler selects points closest to the k quantiles of F.
- Quantile sampling: Quantile sampling chooses k points nearest the quantiles F^-1(i/k), and is β-efficient with β = O(1/log k).The sampler minimizes the unresolved threshold intervals associated with successive selected points.
- Uniform comparison: Uniformly sampled points leave a largest transformed-coordinate gap of expected size Θ(log k/k), yielding β = O(1/log k).The transformed coordinates y_i = F(x_i) are i.i.d. uniform on [0, 1].
- Version-space analysis: The proof relates version-space diameter to intervals between successive sampled points, since labels cannot distinguish thresholds inside an unsampled interval.For threshold functions, disagreement distance is measured by the corresponding CDF gap.
- Bound: Taking ϵ = o(1) gives β ≤ (d/log k)(1 + o(1)) for the analyzed sampler comparison.This bounds the ratio between the bounded and uniform-sampling diameters.
B.2 Proof of Theorem 4.3
The proof shows that the β = O(1/log k) efficiency factor for quantile-based sampling is sharp, including in higher dimensions.
- Sharpness: In one dimension, choosing k percentile points is optimal because the sampler’s diameter is determined by the maximal gap between successive points.No alternative choice of k points can improve the resulting factor in this setting.
- Sharpness: The efficiency factor β = O(1/log k) is sharp in one dimension and extends to a lower bound β = Ω(1/log k) in all dimensions.The higher-dimensional lower bound follows by embedding the one-dimensional setting in a distribution supported on a one-dimensional interval.