Selecting Queries by Where Two Co-Trained Models Disagree: First-Order Bilevel Active Learning

Active learning spends a small labeling budget on the most useful unlabeled examples. The most principled way to define "useful" is a bilevel problem, a nested optimization in which an outer objective scores how well a model generalizes and an inner objective trains that model on the chosen examples. Pick the examples whose inclusion makes the trained model generalize best. The difficulty is cost. Exact versions require differentiating through training, which means second-order derivatives (Hessians) or retraining the network from scratch for every candidate set. First-order bilevel methods avoid this. They replace the nested problem with a penalized single-level problem that needs only ordinary gradients, and they have scaled data reweighting to 30-billion-parameter models. So far they have only been used to reweight data that is already labeled. They have not been used to decide what to label.

This proposal applies value-function penalty methods, the first-order bilevel formulation that keeps track of how well the inner problem can be solved, to pool-based active learning. The gradient with respect to each unlabeled point's selection weight then takes a simple form: it is the disagreement, measured as a KL divergence, between two networks trained side by side. One network is pulled toward good held-out performance. The other is simply trained on the current data. The resulting method keeps both networks warm across labeling rounds, so it never retrains from scratch. It has a principled stopping and diversity behavior, because a point's score drops once the plain-training network absorbs it. It can also be tested directly against the cheaper heuristic it resembles.

Core Claim

Write $x \in [0,1]^N$ for soft selection weights over the $N$ unlabeled pool points, constrained to the capped simplex $\Delta_B = \{x : \sum_i x_i = B\}$ for a budget of $B$ queries. Write $y$ for the parameters of the network the outer objective cares about, $z$ for a second network that tracks the inner optimum, and $\gamma$ for the penalty strength. The inner loss is

$$f(x,w) = \ell_{L}(w) + \sum_i x_i\,\mathrm{CE}\big(q_i,\, p_w(u_i)\big).$$

Here $\ell_L$ is the supervised loss on the training folds of the current labeled set. $p_w(u_i)$ is network $w$'s predicted class distribution on pool point $u_i$. $q_i = \mathrm{stopgrad}\,p_y(u_i)$ is a hallucinated soft label, meaning a guessed label taken from $y$'s current beliefs. The penalized problem is

$$\min_{x \in \Delta_B,\; y} \; F(y) + \gamma\big[f(x,y) - \min_z f(x,z)\big].$$

The outer objective $F$ depends on $y$ alone, never on $x$. Beyond Value Functions identifies this as exactly the regime where value-free single-loop methods (PBGD-Free) lose their gradient signal and may fail to converge. All selection signal must therefore flow through the penalty, which is why we keep the value function and track $z$ explicitly.

Differentiating the penalty in $x_i$, by Danskin's theorem as in Yao et al., gives $\gamma[\mathrm{CE}(q_i,p_y) - \mathrm{CE}(q_i,p_z)] = -\gamma\,\mathrm{KL}(p_y(u_i)\,\|\,p_z(u_i))$. Projected gradient descent on $x$ therefore raises the weight of points where the outer-steered model and the plain-training model disagree most.

The bilevel structure matters in one specific way. As $x_i$ grows, $z$ trains on point $i$ with label $q_i$, and the disagreement there shrinks. Its neighbors' disagreement shrinks too, so the scores show diminishing returns within a batch. Borsos et al. obtained this kind of diversity from a combinatorial greedy search over a neural-tangent-kernel linearization. Here it falls out of continuous single-loop updates on the real network.

The claim has two parts. First, this score can be computed at roughly twice the cost of training one network, without Hessians, unrolled training, or per-round retraining. Second, it beats both its static counterpart (a one-shot two-model disagreement score) and strong semi-supervised baselines under a statistically rigorous protocol. If the static counterpart matches it, the bilevel framing adds nothing, and the experiments are designed to reveal that.

Research Program

Outer objective without a clean validation set. The method needs an outer objective $F$ that does not assume a clean validation set. GLISTER (GLISTER) and probabilistic coreset selection (Probabilistic Bilevel Coreset Selection) both assume such a set exists, which active learning does not provide. Borsos et al. instead use semi-supervised pseudo-labels on the entire pool, and those pseudo-labels inherit cold-start confirmation bias.

We build $F$ from labels we have actually paid for, by cross-fitting. The current labeled set $L$ is split into $K$ folds. Both networks train on $K-1$ folds, and $F$ is the loss on the held-out fold, with folds rotating across iterations. Because $L$ was chosen actively, it is a biased sample of the pool. We therefore reweight the held-out loss by a density ratio between pool and labeled set, estimated in a frozen pretrained feature space. We also add an augmentation-consistency term on $U$ that needs no labels.

At the very first round $L$ is too small for this. Following the cold-start finding of ActiveFT, we seed it with ActiveFT's geometric selection. We treat this seeding as a fixed component and do not claim it as a contribution.

Optimizer. Each step takes one or a few gradient steps on $z$ toward $\arg\min f(x,\cdot)$, one step on $y$ on the penalized objective, and one projected step on $x$ onto $\Delta_B$, which costs a sort. After each round the top-$B$ coordinates of $x$ are queried. Their hallucinated labels $q_i$ are replaced with true labels, those points move into $L$, $x$ is reset on the remaining pool, and $y$ and $z$ continue from their current weights.

The penalty $\gamma$ is annealed upward, following the penalty-balancing concern in the first-order literature. We report sensitivity across a decade of values rather than a single tuned setting.

Analysis. We will characterize when the KL score is a faithful hypergradient. When $z$ lags its optimum, the score is biased toward points $z$ has not yet fit. We will measure this bias by comparing against a version that runs $z$ to convergence at checkpoints.

We will also study the choice of hallucinated label source: $q$ taken from $y$ (our default), from $z$, or from their average. The sign derivation above shows the choice is not cosmetic. Taking $q$ from $z$ makes every point's score nonpositive, which inverts the selection rule.

Baselines

Naive reference points. The do-nothing reference is uniform random querying with the same backbone and training recipe. The stronger naive reference is random querying combined with self-supervised pretraining and semi-supervised training. Rethinking deep active learning reports that on CIFAR-10 with 100 labels, adding pretraining and label propagation to random sampling gives roughly a 15% accuracy gain, larger than the differences among standard active learning methods. Every method in our study, ours included, is therefore run on top of the same pretrained backbone and the same semi-supervised loss. Beating this baseline means a positive area under the accuracy-versus-labels curve, with a confidence interval excluding zero over 50 seeds.

Strongest heuristic. The strongest existing heuristic for mid-sized batches is BADGE (Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds). It clusters per-point last-layer gradients computed under predicted labels, so it trades off uncertainty and diversity without tuning. The file has no reported scalar result on Lacuna for BADGE on CIFAR. At very large batches, Cluster-Margin (Batch Active Learning at Scale) is stronger. On Open Images v6 it reached pooled average precision 0.76 with about 920K labels, 29% fewer than the next baseline. We include Cluster-Margin for our largest-batch setting only.

Strongest bilevel competitors. These are GLISTER-ACTIVE, run with our cross-fitted held-out fold as its validation set so that neither method gets a privileged clean set, and the NTK bilevel method of Borsos et al. The latter reports about 90% accuracy with 200 labels on Speech Commands V2, and we replicate that setting.

For single-round low-budget fine-tuning, the reference is ActiveFT. It reports 26.1% accuracy on CIFAR-100 at a 1% budget, against 14.9% for random sampling and 17.6% for K-Means.

Ablations. The ablation that isolates our key ingredient is static disagreement. We train $y$ and $z$ identically, compute $\mathrm{KL}(p_y\|p_z)$ once per round, and take the top $B$. This removes only the coupling through which selected points change $z$. A second ablation keeps everything but drops the value function: $z$ is removed and $x$ is updated only through $y$, PBGD-Free style. The flatness analysis predicts this collapses.

Fairness. All methods get identical backbones, augmentation, semi-supervised loss, labeled-set sizes per round, and an equal hyperparameter search budget of 20 configurations, tuned on held-out seeds. We report wall-clock time alongside accuracy.

Why not just…?

Why not just use query-by-committee with two networks? This is the most serious threat, because our score is a two-model disagreement. The difference is that our committee members are not exchangeable. One is steered by held-out labeled loss. The other absorbs the soft-selected points during selection, which suppresses redundant queries within a batch. The static-disagreement ablation tests exactly this. If it matches the full method within seed noise on the CDALBench suite, we will report that the first-order bilevel derivation is mainly a justification for a cheap committee heuristic, which is a smaller but still useful result.

Why not just do random sampling with semi-supervised training? Siméoni et al. show this often beats sophisticated acquisition. That is why it is our main baseline rather than a footnote, and why our outer objective includes the same consistency loss. Their evidence is concentrated at tiny budgets. Our prediction is that gains appear in the middle of the curve, once the labeled set is large enough for cross-fitting to give a meaningful outer signal. If that prediction fails, the method is not worth its cost.

Why not just use BADGE? BADGE already mixes uncertainty and diversity cheaply, but its rule is fixed. It never asks whether a point would improve held-out loss, and it re-clusters from scratch each round. A head-to-head comparison under matched compute settles which matters more. Our hypothesis is that the outer signal helps most on CDALBench's Honeypot dataset, where boundary noise traps pure uncertainty scores.

Why not just use GLISTER? GLISTER is a bilevel selector, but it is greedy, refreshed only periodically, and dependent on a validation set. Running it with our cross-fitted fold separates two questions: how much of our gain comes from the outer objective, and how much from single-loop continuous optimization.

Proposed Experiments

The primary testbed is CDALBench (A Cross-Domain Benchmark for Active Learning), covering tabular, image (including CIFAR-10 with SimCLR features), text, and its two synthetic stress tests. We use its 50-run protocol and its anytime area-under-curve metric. That paper shows rankings can invert with only three seeds and that its Greedy Oracle beats existing methods by at least 5% on average. We report the fraction of that oracle gap our method closes, which gives a scale for interpreting results that does not depend on any particular baseline.

Secondary settings are CIFAR-10 and CIFAR-100 with a pretrained backbone in the multi-round regime, Speech Commands V2 to compare directly with Borsos et al., and CIFAR-10 with injected label noise to see whether the held-out outer signal steers away from corrupted regions.

The decisive checks are three. The full method must beat the static-disagreement ablation and random-plus-semi-supervised training over 50 seeds. Removing the value function must hurt as the flatness analysis predicts. Total compute must stay within a small constant factor, which we expect to be about 2–3×, of training a single network over all rounds, measured against BADGE and GLISTER wall-clock under identical hardware.