One-sentence Summary

Researchers from Granica Computing, Inc. develop a statistical theory for data selection under weak supervision, demonstrating that selecting a subset of size $n < N$n<N from $N$N unlabeled samples via a surrogate model and training with regularized empirical risk minimization can outperform full-sample training, while showing that popular strategies such as unbiased reweighted subsampling or influence function-based subsampling can be substantially suboptimal.

Key Contributions

• A theoretical and empirical analysis of selecting labeled subsets from unlabeled examples using a surrogate model shows that data selection can outperform full-sample training, with subsets as small as 0.4 of the data yielding lower test error.

• For convex M-estimators, low-dimensional and high-dimensional asymptotic analyses establish that unbiased reweighted subsampling and influence-function-based selection can be substantially suboptimal, while biased selection can improve expected-risk curvature and optimal probabilities depend nontrivially on the subsampling fraction n/N.

• The analysis identifies uncertainty-based subsampling as an effective practical rule and shows that better surrogate models do not always improve plug-in selection. Real and synthetic experiments further indicate that optimal choices can favor harder or easier examples depending on the low-dimensional or high-dimensional regime.

Introduction

Labeling is labor-intensive, and data selection-based learning addresses this cost by selecting a small informative subset from a fixed unlabeled pool, labeling it, and then training through weighted empirical risk minimization. This setting matters for pool-based active learning, where the goal is to retain near full-sample accuracy with far fewer labels. Prior approaches such as Bayesian uncertainty sampling, gradient or loss heuristics, leverage scores, influence functions, and margin-based selection are often tied to specific assumptions, problem formulations, or small subsampling regimes, and many theoretical treatments enforce unbiased weights proportional to the inverse of the selection probability. These restrictions can make selection suboptimal, especially when the retained sample is a constant fraction of the data and the usefulness of each point depends on the target selection rate. The authors leverage a unified analysis of biased and unbiased weighted ERM across low- and high-dimensional asymptotics, showing that fraction-aware, surrogate-based selection rules can improve over standard unbiased schemes, that uncertainty can guide effective selection, and that good subsampling can sometimes outperform full-sample training.

Method

The proposed method is a label-free selective empirical risk minimization framework. Its core design is to separate the expensive labeling and full training process into a lightweight surrogate prediction stage, a data scoring and subsampling stage, and a final reduced-data training stage. Given a large unlabeled pool $\boldsymbol{x}_1,\ldots,\boldsymbol{x}_N$x1​,…,xN​, the method assumes access to a surrogate probability kernel $\mathrm{P}_{\mathrm{su}}(\mathrm{d}y|\boldsymbol{x})$Psu​(dy∣x). The surrogate may either approximate the true conditional distribution of the labels or be a weaker predictive model. The final model is trained on a subset of size $n < N$n<N chosen using only the feature vectors and surrogate outputs, not the true labels.

The selection process is encoded through random variables $S_i(\boldsymbol{x}_i) \geq 0$Si​(xi​)≥0, which depend on $\boldsymbol{x}_i$xi​, the surrogate prediction $\mathrm{P}_{\mathrm{su}}(\cdot|\boldsymbol{x}_i)$Psu​(⋅∣xi​), and independent randomness across samples. The final estimator minimizes the selectively weighted empirical risk

Here $\lambda\Omega(\boldsymbol{\theta})$λΩ(θ) is a regularizer. The subsampling budget is enforced in expectation through

A central design choice is whether the selection scheme is unbiased. An unbiased scheme satisfies

In this case, the weights compensate for the sampling probabilities, effectively preserving the expected risk. In the classical fixed-dimension regime, the optimal unbiased scheme is determined by a conditional influence-function-type score. Define the conditional gradient covariance and Hessian

The optimal unbiased sampling probability has the form

where

The constant $c(\gamma)$c(γ) enforces the target subsampling fraction $\gamma = n/N$γ=n/N. Equivalently, under the surrogate prediction, the algorithm selects samples whose expected squared influence under the surrogate is large. For generalized linear models, this score reduces to a natural geometric score involving the model curvature and the surrogate-conditional uncertainty. In linear regression, for example, the score becomes proportional to a population leverage score.

The method further studies biased non-reweighting schemes, which are simpler in practice because the selected samples are used with weight one. In this design, the selection rule is defined only by a probability $\pi(\boldsymbol{x})$π(x), so that

This avoids modifying the training objective and therefore integrates more directly into standard machine-learning pipelines. However, because no reweighting is applied, the effective Hessian and gradient covariance are no longer those of the full population distribution. Instead, they are computed under the selected distribution:

where $\mathbb{E}_{\pi}$Eπ​ denotes expectation under the distribution induced by $\pi$π. The optimal biased selection rule uses a thresholded score

The optimal non-reweighting probability selects examples with large $Z(\boldsymbol{x};\pi)$Z(x;π) subject to the target sample size. This yields a greedy selection rule based on difficult or informative samples, but the score itself is coupled to the final selected distribution. As a result, the optimal subset depends nontrivially on the target fraction $\gamma$γ, and selecting the most uncertain or highest-score examples is not always the best strategy.

The same principle is extended to a high-dimensional setting where the feature dimension $p$p, pool size $N$N, and subset size $n$n diverge together. For generalized linear models with responses depending on a one-dimensional projection $\langle \boldsymbol{\theta}_0,\boldsymbol{x}\rangle$⟨θ0​,x⟩, the surrogate model is summarized by two quantities: alignment with the true projection direction and norm of the orthogonal error component. The asymptotic test error is characterized by a saddle-point problem involving the loss, the selection rule, and the surrogate-dependent statistics. This makes it possible to compare selection rules that emphasize hard examples, uncertain examples, or more balanced uncertainty scores without requiring exact knowledge of the true labels.

A practical consequence of the framework is that data selection is not only a computational shortcut. The authors show that selecting a smaller, more informative subset can improve final accuracy relative to training on the full dataset. This is possible because biased selection can change the effective curvature of the expected risk. Unbiased selection preserves the original population curvature, while biased selection can favor regions of the feature space that improve statistical efficiency. The method is therefore designed as a surrogate-driven filtering workflow: a small weak or strong surrogate model is first trained, conditional predictions or uncertainty scores are computed on the unlabeled pool, a subset is selected according to a biased or unbiased scoring rule, and the final model is trained on the selected subset with regularized empirical risk minimization.

The empirical behavior of the method reflects the design. A weak surrogate can still produce an effective selection rule, biased selection can outperform unbiased reweighting, and the selected subset can yield lower test error than using all available examples. As shown in the figure below:

In the depicted setting, the pipeline uses image embeddings and a simple final classifier. The scoring module may emphasize hard examples through an exponent parameter, while the training module optimizes a ridge-regularized loss. The comparison illustrates that the quality of the final model depends not only on the amount of data used, but also on the interaction among surrogate strength, selection bias, regularization, and target subsampling fraction.

Experiment

The evaluation combines theoretical low- and high-dimensional asymptotics with synthetic simulations and a real-data autonomous-vehicle classification task, testing uncertainty-based one-parameter subsampling for logistic regression. The experiments validate the asymptotic predictions, showing that biased subsampling can be more accurate than unbiased schemes and that sample utility depends on the sampling fraction rather than surrogate quality alone. Across settings, uncertainty-driven selection often approaches or exceeds full-sample performance even with small fractions, though optimal bias toward easy or hard examples varies with dimension, model misspecification, and budget.