A common recipe for small-data problems is to run inputs through a pretrained neural network, freeze the resulting vectors, and train a classical classifier on them, such as a random forest, gradient-boosted trees, or a support vector machine (SVM). We call these "hybrid" classifiers. When labels are expensive, a second question follows: which few examples should be labeled? Work on data selection repeatedly finds that clever selection beats random picking only at tiny budgets, and that random catches up soon after. That body of work almost always measures this on neural models trained end to end. This proposal makes two claims about hybrid classifiers. First, a selector helps most when it covers the space in the same geometry the downstream classifier uses to carve it. Trees cut along individual coordinates, while kernel SVMs measure distance. Second, the budget at which random sampling catches up can be predicted before labeling, by counting how many distinct decision regions the classifier needs.
Concretely, we would build a label-free selector that mimics tree partitions and compare it against a distance-based selector, with both tree ensembles and SVMs downstream. We would then test whether a coupon-collector estimate of the "catch-up budget" matches the observed curves. If both claims hold, practitioners get a usable rule. Select in the classifier's own geometry, and stop bothering once the budget passes a number they can compute from a small pilot.
Core Claim
Selection pays off only while the labeled set is too small to land at least one example in every region of embedding space that the downstream classifier needs to separate. Random sampling fills those regions on its own once the budget is large enough, which is why advantages vanish. The regions depend on the classifier. For a tree ensemble they are axis-aligned boxes. For an RBF-kernel SVM (one that separates classes using a Gaussian similarity between points) they are neighborhoods in a whitened distance. Two predictions follow. The first is a crossover interaction: tree-shaped coverage should beat distance-shaped coverage under trees, and the reverse should hold under SVMs. The second is a predictable catch-up budget. If the classifier needs $K$ regions and the rarest holds a fraction $p_{\min}$ of the pool, random sampling hits all of them with high probability at roughly
$$N^* \approx \frac{\log K}{p_{\min}},$$
the standard coupon-collector bound for unequal probabilities. $N^*$ is the labeled-set size beyond which selection and random sampling should be statistically indistinguishable. Below it, selection should help. Above it, it should not.
Grounding in Prior Work
The diminishing-returns pattern is well documented. In micro-benchmarking, Yauney et al. show that Anchor Points wins at 10–25 examples but random sampling matches it near 250. For few-shot support sets, Pecher et al. show their combined selector regresses toward random by 30–40 shots. In multilingual transfer, Kumar et al. find selection gains fade toward 1,000 samples. For targeted instruction tuning, Nayak et al. find random catches up at larger budgets. These papers motivate the proposal: they establish the phenomenon. However, all of them measure it on end-to-end neural learners, and none offers a way to predict where the crossover falls.
The closest connecting work is Kar and Jain. They select landmark points with a greedy diversity rule (DSELECT), embed data by similarity to those landmarks, and train a linear SVM. They report a 5–6% gain over random landmarks at 30–50 landmarks that disappears at larger pools. Their work differs from ours in three ways. They select landmarks that define features, not labeled training points. They use one downstream classifier with fixed similarity kernels. They never ask whether the selector's geometry should depend on the classifier.
Small-GAN supplies part of our method. It runs k-center greedy coverage on randomly projected Inception embeddings, cheaply, and notes that gains fade as batches grow. Its downstream learner is a GAN trained by SGD.
TAROT supplies a correction we reuse: whitening embeddings, because a few dominant dimensions distort Euclidean distances. It also detects its own saturation point by watching optimal-transport distance. Its evaluations are all end-to-end fine-tuning.
On the hybrid side, three papers motivate the regime, and none selects its training data. Reinders et al. train a random forest on CNN features with about 15 examples per class, and their only filter is an accelerometer threshold. Pang et al. replace a CNN's softmax with XGBoost for protein localization and note degradation on sparse classes such as centrosome and endosome. Our $p_{\min}$ term is meant to capture exactly that degradation. Badjatiya et al. feed LSTM embeddings to gradient-boosted trees for hate speech.
Two results constrain the design. Nayak et al. find gradient-based scores track neural loss well, with Spearman correlation above 0.9. But a tree or SVM head has no such loss, so we do not build on gradient selection. Kumar et al. find that moderate rather than extreme points work best. This fits the concern that k-center chases outliers, so our selectors include a density floor.
Research Program
We would build two label-free selectors over a frozen embedding pool, matched in budget and in outlier handling.
The tree-shaped selector grows a forest of totally random, unsupervised axis-aligned trees on the pool. These trees split on randomly chosen coordinates at random thresholds, which mimics the boxes a tree ensemble will later use. The selector then picks points that cover the forest's populated leaves. It works greedily, choosing the point that covers the most not-yet-covered leaves across trees, and skips leaves below a density floor so that isolated outliers are not favored.
The distance-shaped selector runs k-center greedy on whitened, randomly projected embeddings, following Sinha et al. and Feng et al., with the same density floor.
Both selectors are then crossed with three downstream classifiers: random forest, XGBoost, and RBF SVM. A linear probe and end-to-end fine-tuning serve as neural references.
To predict the catch-up budget, we train each classifier on a small random pilot set (for example 20 labeled points per class) and read off its regions. For trees we use the leaves actually reached by pool points. For SVMs we cluster pool points by their nearest support vector. We then estimate $K$ and $p_{\min}$ from pool occupancy and compute $N^*$. Finally, we fit the observed crossover from full learning curves and compare it to the prediction.
Baselines
The naive reference is uniform random sampling at each budget. It is run with 20 seeds per budget, so that every comparison is a paired difference with a confidence interval rather than a single curve. Any selector that cannot beat random at budgets below the predicted $N^*$ has failed. Class-stratified random sampling is reported alongside as an oracle reference, because it uses labels the other selectors do not see.
The strongest existing competitor is distance-based coverage: k-center greedy on whitened embeddings, as in Small-GAN with TAROT's whitening. Two variants run with it, k-medoids and DSELECT. This family is the strongest because it is cheap and diversity-driven, and it is the established winner at tiny budgets. All variants get the same embeddings, budgets, density floor, and a matched hyperparameter search for the downstream classifier (identical grid, nested cross-validation on the selected set only). Beating it means a statistically significant gain under tree classifiers at budgets below $N^*$, pooled across datasets, with the reverse or a tie under SVMs.
For a targeted reference, we also run TAROT's optimal-transport selection using the public codebase, given a small held-out target sample.
The key ablation removes the matching. It runs the tree-shaped selector with leaves defined by randomly rotated trees, which cut along oblique directions rather than single coordinates. If performance stays unchanged, axis alignment is not the ingredient. A second ablation removes the density floor.
On reported numbers: Badjatiya et al. report weighted F1 0.930 for LSTM features plus GBDT on the full Waseem–Hovy data. Pang et al. report accuracy 0.78 and F1 0.80 on Hum-mPloc 3.0 with all training data. Kar and Jain report the 5–6% DSELECT gain at 30–50 landmarks. These are full-data ceilings, not budgeted selection results. No reported result was found on Lacuna for any sample-selection method on these hybrid benchmarks at small budgets, so the budgeted baselines must be run here.
Why not just…?
Why not just sample randomly? For budgets beyond $N^*$, we expect random sampling to be right, and the proposal says so explicitly. The contribution there is telling practitioners where that point is. Below it, the evidence from Kar and Jain and Kumar et al. says random sampling loses. The paired-seed learning curves will show whether that holds for hybrid heads.
Why not just run k-center or k-means on the embeddings? This is the real threat. If whitened k-center matches the tree-shaped selector under random forests and XGBoost, the geometry-matching claim is false. The 2×2 interaction test settles this directly. We would then report the catch-up-budget law with k-center as the recommended selector rather than argue for our own.
Why not just fine-tune end to end, or use a linear probe? Reinders et al. and Taubert et al. report end-to-end heads overfitting at these sample sizes. We nonetheless run fine-tuning and a linear probe at every budget. If either dominates the hybrid heads, the question of selecting for hybrids becomes moot in that regime, and we will say so.
Why not use gradient-based selection like LESS? Its strength rests on correlation with neural loss, per Nayak et al., and trees and SVMs do not optimize that loss. It also costs backward passes over the pool. We include TAROT as the representative of this family rather than assume it fails.
Proposed Experiments
The benchmarks come from the file.
The protein localization sets used by Pang et al. are Hum-mPloc 3.0, BaCelLo, and Hoglund. On these we use CNN sequence features, metric accuracy and F1, and they stress the rare-class term $p_{\min}$.
The Waseem–Hovy hate speech set has 16,000 tweets, which we embed with an LSTM or sentence encoder and score with macro F1.
GTSRB's 39,209 images serve as an image pool with frozen CNN features. Meta-Album few-shot image tasks, from Pecher et al., provide many small problems for fitting the catch-up law.
The UCI sets Isolet, Letters, Pen-digits, and Satellite act as a non-neural control, where features are raw tabular columns.
Budgets sweep from 1 to 200 labeled examples per class. We stop at 1,000 total, because that is past where every prior saturation point in the file falls.
There are three decisive checks.
The first is the interaction test. A mixed-effects model of accuracy on selector × classifier × budget, with dataset as a random effect, must show tree-shaped coverage ahead under trees and distance coverage ahead or tied under SVMs, at budgets below $N^*$.
The second is the catch-up-budget law. The pilot-based $N^*$ must predict the observed crossover within a factor of two on at least most dataset–classifier pairs. It must also beat a naive predictor that uses the number of classes alone. If it does no better than class count, the region argument adds nothing.
The third is a noise stress test. We inject 10–20% label noise into the pool and check whether the density floor protects tree and SVM heads from k-center's preference for outliers. This tests whether the "moderation" finding of Kumar et al. carries over to hybrid classifiers.
Together these say when selection is worth doing for frozen-embedding classifiers, and which geometry to select in.
References
- How Reliable is Language Model Micro-Benchmarking?
- Automatic Combination of Sample Selection Strategies for Few-Shot Learning
- "Diversity and Uncertainty in Moderation" are the Key to Data Selection for Multilingual Few-shot Transfer
- A Critical Look at Targeted Instruction Selection: Disentangling What Matters (and What Doesn’t)
- Similarity-based Learning via Data Driven Embeddings
- Small-GAN: Speeding up GAN Training using Core-Sets
- TAROT: Targeted Data Selection via Optimal Transport
- Object Recognition from very few Training Examples for Enhancing Bicycle Maps
- A Novel Protein Subcellular Localization Method With CNN-XGBoost Model for Alzheimer's Disease
- Deep Learning for Hate Speech Detection in Tweets
- RNA contact prediction by data efficient deep learning