Catch-Up Lag in Cold-Start Active Learning: Switching Instead of Averaging

Active learning lets a model choose which unlabeled examples a human should label next. When only a handful of labels exist, the strongest systems hedge between a simple model that is reliable from the first label and a richer model that becomes better later. On attributed graphs, for example, they mix label propagation, which only spreads labels along edges, with a feature-aware logistic regression. They combine the two with Bayesian model averaging: each model's weight is proportional to how well it has explained every label seen so far. Grünwald showed that this rule is systematically slow. The simple model builds an early lead in accumulated evidence, so the averaged predictor keeps trusting it long after the richer model has started predicting new data better. He called this the catch-up phenomenon.

Our claim is that catch-up lag is worse in active learning than in the passive settings where it was studied, because it feeds back on itself. The lagging model does not only make the predictions. It also picks the next queries, and so it gathers labels that suit its own view of the problem and slow the evidence that would overturn it. We propose replacing evidence-weighted averaging inside the acquisition loop with a switching distribution, a prior over sequences of models that allows the best model to change partway through the label stream. We will measure how much faster this hands control to the right model. We will also measure how sensitive the result is to the one new knob, the prior probability of switching, and to a deliberately misspecified simple model. The deliverable is a drop-in change to cold-start graph active learning, along with a clear empirical answer on whether principled switching beats cheaper heuristics such as recency-weighted scoring.

Core Claim and What Is New

Three lines of work meet here without having been combined.

The first supplies the method. The Catch-Up Phenomenon in Bayesian Inference proves that a switching distribution achieves both model-selection consistency and the minimax predictive rate at roughly the cost of ordinary Bayesian inference, but only for passive observation. Context Tree Switching shows that a simple decaying switch rate of $1/n$ works well in practice for sequence prediction.

The second supplies the regime and the gap. Active Learning on Attributed Graphs via Graph Cognizant Logistic Regression and Preemptive Query Generation (GEEM) handles the one-to-two-label cold start by evidence-weighting label propagation against Simplified Graph Convolution (SGC), a fast feature-plus-graph logistic regression. It does so with exactly the averaging rule that Grünwald shows lags. It never measures that lag. Using bayesian priors to combine classifiers for adaptive filtering bridges a simple and a complex classifier differently, using the simple model as the prior mean of the complex one. It assumes that anchor is correct.

The third supplies the constraint. Robustness of Bayesian Pool-Based Active Learning Against Prior Misspecification proves that active learning is robust to a wrong prior when the selection utility is Lipschitz in the prior, meaning it changes by a bounded amount when the prior changes. Hard model selection is not Lipschitz. This tells us to keep switching soft, as a mixture over model sequences, rather than a hard swap at a threshold.

The closest existing work is Bayesian Active Meta-Learning under Prior Misspecification. Its method, sOED-ML, switches between two acquisition objectives when a credible lower bound crosses a decaying threshold. That work differs from ours in three ways. It switches what the learner seeks, not which predictive model is in charge. It switches with a hard threshold. And it is evaluated only on simulated participants. We switch between predictive model classes, softly, on real benchmark graphs. Our central measured quantity is the interaction between acquisition and catch-up, which none of these papers measures.

Research Program

The mechanism is small. Each candidate model $m$ (label propagation, SGC, and optionally a small graph network) is scored on every new label before it is trained on that label. This is prequential scoring: the model's predictive probability $p_m(y_t)$ for the label of the $t$-th query, computed from the first $t-1$ labels. Model weights are updated with a fixed-share approximation to Grünwald's switching distribution:

$$w_{t+1}(m) \propto (1-\alpha_t)\, w_t(m)\, p_m(y_t) + \frac{\alpha_t}{M-1} \sum_{m' \neq m} w_t(m')\, p_{m'}(y_t),$$

Here $M$ is the number of candidate models and $\alpha_t$ is the switching probability at step $t$. Its default is $\alpha_t = 1/t$, following Context Tree Switching. Setting $\alpha_t = 0$ recovers GEEM's averaging exactly, so the comparison is clean.

The mixture weights then enter acquisition in two places. They form the predictive distribution used by expected error minimization, and the per-model look-ahead terms are mixed with them. A fraction of queries (we will test 0% and 10%) can be drawn uniformly at random. This addresses a real problem. Actively chosen points are not representative, so prequential scores computed on them can favor whichever model the acquisition rule was built around. Scoring models only on the random queries gives an unbiased check.

The program has three parts.

The first is measurement. We define transition lag as the number of queries between two points: when SGC's running prequential loss on fresh labels first drops below label propagation's, and when SGC's weight first exceeds one half. We compare this lag between passive (random) acquisition and active acquisition. The feedback hypothesis predicts a longer lag under active acquisition when averaging is used, and little difference under switching.

The second is sensitivity. We sweep a constant $\alpha$ over three orders of magnitude, compare it against the $1/t$ schedule, and report how the area under the learning curve varies. We also compute the cumulative Jensen–Shannon sensitivity measure of Detecting and diagnosing prior and likelihood sensitivity with power-scaling on the model-weight posterior, obtained by power-scaling the switching prior. We report whether it crosses that paper's 0.05 threshold. That paper notes that power-scaling cannot detect a prior that is centered in the wrong place, only one that is too sharp or too flat. So we test location-type misspecification directly in the next part.

The third is misspecification. We corrupt the simple model by rewiring a controlled fraction of edges, which makes label propagation confidently wrong. We then measure how quickly each weighting rule abandons it. We run a parallel test in the Zhang et al. setting by shifting the Rocchio prior mean away from the true class centroid.

Baselines

The naive reference points are random acquisition with SGC alone and uncertainty sampling with SGC alone. These show what any cold-start hedging buys at all. GEEM's cold-start literature reports that complex-model active learning often loses to random selection over the first ten queries, so random selection is a meaningful floor.

The strongest existing method is GEEM, and its preemptive variant PreGEEM, with Bayesian evidence weighting between label propagation and SGC, as in Active Learning on Attributed Graphs via Graph Cognizant Logistic Regression and Preemptive Query Generation. We will reimplement it with identical models, priors, candidate subsampling for the look-ahead, query budgets (1 to 30 labels), and random seeds. The only difference will be the weighting rule. That paper reports gains over AGE and ANRMAB on Cora, Citeseer, Pubmed, Amazon-Photo, and Amazon-Computers, but only in figures. We found no reported numeric result on Lacuna for GEEM accuracy on these graphs, so we will report the reproduced GEEM curve as the reference to beat.

The key ablation is the same pipeline with $\alpha_t = 0$, which is pure averaging. Any gain must come from that one parameter. A second ablation applies switching weights to prediction but keeps averaging weights for acquisition. This isolates whether the benefit flows through query choice, which is the feedback claim, or only through better predictions.

For the adaptive-filtering testbed, the reference is Logistic_Rocchio. Using bayesian priors to combine classifiers for adaptive filtering reports T11SU of 0.52 on TREC-11 Reuters, against 0.46 for Rocchio and 0.49 for logistic regression. T11SU is the TREC linear utility measure, which rewards delivered relevant documents and penalizes delivered irrelevant ones. We will reproduce that number before testing a switching variant.

Beating the baselines means a statistically reliable improvement in area under the accuracy curve over the first 30 queries, across seeds, on at least four of five graphs. It also means a shorter transition lag, and no loss once more than 30 labels are available.

Why not just…?

Why not just weight models by their loss over a recent sliding window? This is the real threat. Recency weighting also forgets the simple model's early lead, and it is cheap. Its weakness is that the window size is an unanchored hyperparameter. Too short a window makes the weights jump with every noisy label, which is the non-Lipschitz behavior that Robustness of Bayesian Pool-Based Active Learning Against Prior Misspecification warns against. Too long a window brings the lag back. We will include sliding-window weighting and exponentially discounted evidence as baselines with the same tuning budget as $\alpha$. If either matches switching at equal sensitivity, we will report that the gain comes from forgetting in general and not from the switching prior specifically.

Why not just switch at a fixed label count, say after five labels? A fixed schedule needs per-graph tuning that cannot be done without validation labels, and the cold start has none. It is also exactly the hard step function that the Lipschitz analysis flags as fragile. We will tune the oracle-best switch point per dataset in hindsight and report it as an upper bound on what a schedule could achieve. If switching approaches that bound without hindsight, the case is made.

Why not just bridge with a prior, using label-propagation predictions as the prior mean for SGC, as Zhang et al. do? This is a continuous handoff and a strong competitor. But it inherits the anchor's errors, and the speed of the handoff is fixed by the prior variance rather than by the data. Our edge-rewiring experiment tests this directly. If the prior-bridged model recovers from a corrupted anchor as fast as switching does, we will treat prior bridging as the simpler method and report it as such.

Proposed Experiments and Decisive Checks

The main experiment runs every weighting rule on Cora, Citeseer, Pubmed, Amazon-Photo, and Amazon-Computers, with budgets of 1 to 30 labels and 20 seeds. We report accuracy curves, area under the curve, and transition lag. The adaptive-filtering replication on TREC-11 Reuters tests whether the effect extends beyond graphs.

The first decisive check is the feedback hypothesis. Under averaging, transition lag should be measurably longer with active acquisition than with random acquisition. The prediction-only ablation should capture less of the gain than full switching. If active and passive lag are the same, the proposal's distinctive claim fails. What remains is only an application of Grünwald's result.

The second decisive check is robustness. Across the $\alpha$ sweep, the spread in area under the curve for switching should be smaller than the gap between switching and averaging. Under edge rewiring, switching should abandon the corrupted label-propagation model within fewer queries than averaging, prior bridging, or sliding windows tuned to the same budget.