Tracked Influence: Bias-Free Bilevel Scores for Batch Active Learning

Active learning tries to reach a target accuracy with as few labeled examples as possible by letting the model choose which examples to send to an annotator. One principled way to choose is to treat it as a nested problem. The inner problem trains the model on the labeled set. The outer problem asks which new examples, once labeled and added, would most reduce held-out loss. This is the bilevel view taken by GLISTER and Semi-Supervised Batch Active Learning Via Bilevel Optimization.

The view has an embarrassing empirical record. Active Learning is a Strong Baseline for Data Subset Selection found that plain margin sampling, repeated over several rounds, beats the bilevel selectors that explicitly optimize validation loss. That paper left open why this happens. Our proposal tests one specific explanation. The bilevel selectors in active learning compute their scores with the crude derivative estimates that the stochastic bilevel optimization literature has since learned to avoid. That literature can estimate the derivative of the outer objective without bias, and without paying extra samples for it.

Core Claim

The score that says "how much would labeling $x$ reduce held-out loss" is a hypergradient: a derivative of the outer objective taken through the inner training problem. Concretely, it is an inner product between the gradient on candidate $x$ and an inverse-Hessian-vector product $v$. GLISTER drops the inverse Hessian entirely by taking one Taylor step, which amounts to setting $v$ to the plain validation gradient. Borsos et al. freeze the network into a kernel surrogate instead. Both choices introduce systematic bias.

The single-loop bilevel methods SOBA/SABA, MA-SOBA and AmIGO take a third route. They keep $v$ as an extra variable and update it with one cheap stochastic step per training step, warm-started across iterations. Under strong convexity they show this matches the sample complexity of single-level SGD. We will carry this auxiliary variable through active-learning training, so that a nearly unbiased selection score is always available at almost no cost and no retraining is needed to compute it.

The claim we test is twofold. First, tracked-influence scores, combined with a light diversity step, should beat margin sampling and BADGE in labels needed to reach a target accuracy. Second, the gain should disappear when the tracker is replaced by GLISTER's identity-Hessian approximation. If that ablation does not reproduce the gap, the "bias explains Park et al." hypothesis is wrong, and we will report that result.

Mechanism

Let $\theta$ be the network weights trained on the labeled set $L$. Let $\ell(\theta; x, y)$ be the per-example loss, $H$ the Hessian of the training loss on $L$, and $\lambda > 0$ a damping constant. Let $L_{\text{val}}$ be the loss on a small labeled holdout. During ordinary training on $L$, we also update a vector $v$ (sized like the chosen parameter block) with minibatch Hessian-vector products:

$$v \leftarrow v - \eta\big[(H_B + \lambda I)\,v - \nabla_\theta L_{\text{val},B}(\theta)\big],$$

Here $H_B$ and $\nabla_\theta L_{\text{val},B}$ are minibatch estimates and $\eta$ is a step size. This is the linear-system variable of SOBA. The damping $\lambda$ makes the system it solves strongly convex even though network training is not.

The score of an unlabeled candidate $x$ is its predicted effect on held-out loss, averaged over the model's own predicted label distribution, because the true label is unknown:

$$s(x) = \mathbb{E}_{\hat y \sim p_\theta(\cdot\mid x)}\big[\nabla_\theta \ell(\theta; x, \hat y)\big]^{\top} v .$$

Large positive $s(x)$ means that labeling $x$ is predicted to lower validation loss. To select a batch, we run $k$-means++ seeding over per-example gradient embeddings, as BADGE does, but weight each candidate's seeding probability by $\max(s(x), 0)$. The score therefore decides how useful an example is, and the embedding geometry prevents redundant picks.

Scope matters for the cost argument. If $v$ covers only the final linear layer, the damped Hessian is small enough to invert exactly, so tracking buys nothing. The method only earns its keep when $v$ spans a larger block, such as the last residual stage or a full small network, where exact solves are too expensive each round.

The holdout $L_{\text{val}}$ comes from the annotation budget. We reserve a fixed random fraction of each acquired batch, between 10 and 20 percent and tuned once, for the holdout. This resolves GLISTER's reliance on a clean external validation set. Every method in the comparison is charged for the same labels. Methods that do not need a holdout get those labels as extra training data.

Research Program

The work has three parts.

The first is building the selector as a drop-in module for a standard pool-based active learning loop. The loop warm-starts both $\theta$ and $v$ across rounds, in the spirit of AmIGO's amortization and of the incremental fine-tuning used in O-MedAL.

The second is a limited theoretical analysis in the regime where the theory applies: a linear or kernel model on frozen features, where the inner problem is strongly convex. There, the selection score is a linear function of $v$. The tracking-error bounds already proved for SOBA and MA-SOBA therefore translate directly into a bound on score error. This yields a condition under which tracked scores rank candidates the same way exact influence does: the gap between candidate scores must exceed the tracking error. We do not claim a new query-complexity rate for deep networks. The open questions about proper versus improper learners raised by Agnostic Active Learning Is Always Better Than Passive Learning are out of scope.

The third part, the main deliverable, is a controlled empirical study. It is designed to separate three possible sources of any gain: the bias correction, the diversity step, and the retraining protocol.

Baselines

The naive reference point is uniform random acquisition with the same model, budget schedule and warm-start retraining. On CIFAR-10 with a 5,000-label budget, RAMBO reports 74.7% for random selection and 77.3% for its own method, which gives a calibration target for our setup.

The strongest existing competitors are multi-round margin sampling, as championed by Park et al., and BADGE. Margin sampling is included because it is the method bilevel selectors have empirically lost to. Park et al. report that, on the subset-selection version of the task, it stays within 0.5% of full-data accuracy for up to 50% selection on CIFAR-10. BADGE is included because it shares our gradient-embedding diversity step and differs only in using gradient magnitude rather than predicted validation effect. No reported result was found on Lacuna for BADGE accuracy at a specific CIFAR-10 or SVHN budget, so we will run it ourselves.

We also run GLISTER-ACTIVE as the representative bilevel selector, re-selecting every round rather than every 20 epochs so that staleness is not a confound. On Speech Commands we include the Borsos et al. bilevel MixMatch method, which reports about 90% accuracy with 200 labels.

Fairness rules apply to every method: the same architecture, the same per-round budget and number of rounds, the same retraining protocol, the same total label count including holdout labels, and a hyperparameter search of equal size (a fixed number of trials, for example 8) on a separate seed.

Two ablations isolate the key ingredient. The identity-Hessian ablation sets $v = \nabla_\theta L_{\text{val}}$, which is GLISTER's score inside our pipeline. The exact-influence ablation replaces tracking with a conjugate-gradient solve run to convergence at each round. A third ablation drops the score weighting, which reduces the method to BADGE plus a holdout.

To count as beating the baselines, our method must reduce the labels needed to reach a fixed accuracy target relative to the best of margin and BADGE, with the gap exceeding the seed-to-seed spread over at least five seeds. It must do so on at least two benchmarks, at wall-clock cost no more than about 20% above BADGE.

Why not just…?

Why not just use margin sampling or BADGE, since they already win? This is the main threat, and it may hold. Park et al.'s evidence shows that simple multi-round heuristics beat GLISTER. That evidence does not show they beat a bilevel score with the bias removed, because no such score was tested. The identity-Hessian ablation answers the question directly. If tracked influence beats margin and BADGE while identity-Hessian does not, the bias account is supported. If both lose, we conclude that the bilevel objective itself is the wrong target in this regime, which would also explain Park et al.'s finding.

Why not just compute exact influence at each round with conjugate gradient? This is a real alternative, and it is the right point of comparison for the tracker. We report it both at matched compute and when run to convergence. If tracked and exact influence give the same label efficiency, the tracker's contribution is purely computational. That is still useful for large pools and repeated rounds, but it is a smaller claim, and we will state it that way.

Why not restrict influence to the last layer and invert the Hessian exactly? GLISTER and BADGE both use last-layer gradients, and at that size the inverse is cheap. We will run exact last-layer influence as a baseline. Tracking only matters if influence through deeper layers selects better examples. If deeper influence adds nothing, the method collapses to a simple exact computation, and we will say so.

Why not just use the pseudo-label outer objective of Borsos et al. and avoid spending labels on a holdout? Pseudo-labels from an early model are least reliable exactly where the selection decisions matter most. We test this by running the pseudo-label variant of our score alongside the holdout variant on Speech Commands, where Borsos et al. report their result.

Proposed Experiments

The benchmarks are CIFAR-10, CIFAR-100 and SVHN with ResNet-18, using rounds of 1,000 labels up to 10,000. Speech Commands V2 uses budgets from 50 to 500 labels, matching the Borsos et al. regime. As a stress test where uncertainty heuristics are known to chase noise, we add CIFAR-10 and MNIST with 30% injected label noise. This follows GLISTER's noisy-label evaluation and the hyper-cleaning experiments run with SUSTAIN and MA-SOBA.

The primary metric is labels to reach 90% and 95% of full-data accuracy. Secondary metrics are area under the accuracy-versus-labels curve and wall-clock time per round.

Three checks decide the outcome:

  1. Identity-Hessian gap. The gap between tracked influence and the identity-Hessian ablation should be positive and largest early, when the Hessian is far from identity.
  2. Score fidelity. On frozen-feature linear models, the rank correlation between tracked and exact scores should follow the tracking error, as the convex analysis predicts.
  3. Noise robustness. Under label noise, tracked influence should degrade less than margin sampling. Uncertainty sampling keeps querying noisy regions, whereas validation-driven influence should assign them low value.

Failing the first check falsifies the core claim regardless of headline accuracy.