Source-linked AI summary
Towards optimal selection schedules for online active learning
Hugo Cui, Francesca Mignacco, Francesco Mori
TL;DR
When labels are costly, online learners need to decide which incoming samples to query and when. This paper characterizes and optimizes margin-based query schedules for linear classifiers in a high-dimensional realizable Gaussian setting, and reports that optimal schedules can differ by objective and model.
Problem
The paper asks how to schedule costly label queries in online classification to minimize final error or cumulative mistakes and query costs.
Source: Introduction · pp. 1–2Method
The authors analyze myopic and horizon-optimized margin-based query schedules for linear classifiers under realizable Gaussian design in the high-dimensional regime.
Source: Introduction · p. 2, §1 · p. 4, §2 · p. 6Results
Horizon-optimized schedules outperform random, myopic, and inner-margin strategies for budgeted final error, while cumulative-cost schedules are inner-margin and outperform random and myopic policies.
Source: Introduction · p. 2Takeaways & Limitations
Optimal selection rules can be intermediate-margin or inner-margin, and naive readout-margin policies can be suboptimal for two-layer neural networks.
Source: Introduction · p. 2, Conclusions · p. 12The analysis primarily concerns linear classifiers under isotropic Gaussian data and restricts query policies to functions of the sample margin.
Source: Limitations and perspectives · p. 12
Abstract
from arXiv · showhide
We consider the problem of online linear classification, where a stream of unlabeled samples is available, and annotation is costly. We investigate the optimal query policy, that prescribes whether and when a sample should be labeled and used for a training step, or instead discarded, so as to minimize a given objective. We focus on the realizable case, under Gaussian design, in the high-dimensional regime where data dimension and number of unlabeled samples grow proportionally. We consider two objectives: 1) the generalization error under a labeling budget, and 2) a cumulative cost function where mistakes have unit cost and queries cost $\Delta$. We first show that the myopic policies that greedily minimize at all times the increment in the objective correspond to either small or intermediate-margin policies, that prescribe the selection of samples whose margins fall within certain intervals that shrink with time. Within this class, we numerically ascertain the optimal schedules for the selection thresholds that minimize the final values of the objectives. Taking inspiration from the myopic policy for the cumulative cost, we design a very simple query policy schedule that we compare to other proposed heuristics, on synthetic data and real medical image datasets. Finally, we discuss myopic policies for two-layer neural networks, and exemplify how naive margin-based policies can cease to be optimal.
Introduction
The paper asks how to schedule label queries in high-dimensional online active learning when labels are costly. It characterizes margin-based schedules for two objectives and shows that the optimal form can depend on the objective and model.
Introduction
- The analysis targets optimal schedules among margin-based policies in the realizable, high-dimensional Gaussian setting, for final error under a query budget or cumulative mistake-and-query cost.Prior work typically fixes a query-policy form; this paper distinguishes myopic rules from schedules numerically optimized across training time.Source: Introduction · p. 2
- Horizon-optimized threshold schedules achieve lower final generalization error than random, myopic, and inner-margin strategies under a labeling budget.The myopic policy is intermediate-margin.Source: Introduction · p. 2
- For unit-cost mistakes and query cost Δ, the horizon-optimized inner-margin schedule outperforms myopic and random policies, with gains growing as Δ increases.The authors also propose a simple heuristic inspired by the myopic rule and compare it on synthetic data and real medical image datasets.Source: Introduction · p. 2
- For two-layer neural networks, myopic cumulative-cost policies can use the full preactivation vector, while naive inner-margin rules on the readout are suboptimal.Source: Introduction · p. 2
Related works
- Unlike analyses that assume a specific selection-policy form, this work derives myopic policies and finds that optimal schedules can retain intermediate-margin samples as well as inner-margin samples.The related-work discussion positions the analysis as complementary to online active-learning results on label complexity and selective-sampling results on cumulative cost.Source: Related works · pp. 3–4
1 Problem setup
The setup is online realizable linear classification: each Gaussian sample can be queried for a label and used for training, or predicted without querying. The paper compares policies using either final error under a query budget or cumulative mistake-and-query cost.
1 Problem setup
- A stream of unlabeled Gaussian samples arrives sequentially in the realizable setting, with an unknown ground-truth vector that separates the classes.Source: §1 · p. 4
- At each round, the learner either queries an expert for the label and may update its weights, or predicts and risks a mistake.Training uses batch-size-one stochastic gradient descent with the Adatron rule under the stated squared hinge loss.Source: §1 · p. 4
- The selection schedule makes query decisions from the current model margin, allowing stochastic, time-varying policies as well as deterministic inner-margin rules.An inner-margin rule queries samples within a threshold distance of the decision boundary.Source: §1 · p. 4
- The paper studies final generalization error subject to a labeling budget and cumulative cost with unit-cost mistakes and queries weighted by Δ.The first objective concerns final performance; the second accumulates costs over training.Source: §1 · p. 5
- Myopic policies minimize the expected immediate change in the objective, but can miss future benefits of querying; the analysis restricts to Δ < 1/2.For Δ > 1/2, the myopic learner never queries, even though a final-cost-minimizing strategy could query.Source: §1 · p. 5
2 Closed-form description of the training dynamics
The paper reduces high-dimensional learning dynamics to deterministic scalar ODEs for summary statistics, then uses control methods to optimize selection schedules. The resulting description supports computation of both cost objectives, although the numerical schedule optimization is non-convex.
2 Closed-form description of the training dynamics
- Reducing high-dimensional SGD dynamics to scalar ODEs for a small set of summary statistics makes control-theoretic schedule optimization tractable.The statistics concentrate in the proportional high-dimensional limit and evolve according to deterministic ODEs.Source: §2 · p. 6
- The ODE dynamics depend on the summary statistics and the selection policy, while the associated cost metrics can be expressed through those statistics.The cumulative cost depends on the statistics over the preceding training interval.Source: §2 · p. 6
- The theoretical ODE prediction matches a numerical simulation at d = 1000 and tracks the squared weight norm and overlap with the ground truth.Source: §2 · p. 6
- Piecewise-constant margin thresholds are optimized by direct single shooting with automatic-differentiation gradients, but the non-convex schedules are not guaranteed global optima.Despite that caveat, the resulting schedules consistently outperform the considered benchmarks.Source: §2 · p. 6
3 Minimizing the final error
The section studies policies for minimizing final generalization error under a query budget, comparing a myopic rule with a horizon-optimized intermediate-margin schedule. The optimized schedule achieves the lowest final error among the reported benchmarks, especially at small query budgets.
3.1 Myopic policy p◦
- For a wide range of parameters, the budget-constrained myopic rule selects an intermediate band of margins, with thresholds given by roots of S_t(ω) + ν = 0.The multiplier ν enforces the total query budget.Source: §3.1 · p. 7
- Intermediate margins can be more economical to query: small-margin mistakes receive small updates, while large-margin samples are rarely misclassified.The myopic policy is deterministic almost surely because the instantaneous objective is linear in selection probability.Source: §3.1 · p. 7
3.2 Horizon-optimized intermediate-margin policy p⋆
- The horizon-optimized rule uses control theory to optimize intermediate-margin thresholds across training times for minimum terminal error.Both schedules narrow their selection intervals as classification improves, but the optimized schedule restricts the interval from the start, whereas the myopic rule initially queries a broader range and exhausts the budget before the horizon ends.Source: §3.2 · p. 8
- The horizon-optimized intermediate-margin schedule achieves the lowest final error; constant intermediate-margin selection also outperforms inner-margin policies at small and moderate query budgets.All benchmark parameters are optimized for final error.Source: §3.2 · p. 8
4 Minimizing the cumulative cost
For cumulative-cost minimization, horizon-optimized schedules outperform myopic and random policies by investing in queries early, while the myopic rule selects small-margin samples using a shrinking threshold. The section also compares a simple shrinking-threshold heuristic with prior methods and shows that optimal policies for two-layer networks may depend on the full preactivation vector rather than only the output.
4 Minimizing the cumulative cost
- For cumulative cost, both myopic and horizon-optimized policies are inner-margin rules: small-margin samples are queried because their higher likelihood of error outweighs their smaller updates.By contrast, small-margin samples are discarded when minimizing final error under a labeling budget.Source: §4 · p. 8
4.1 Myopic policy p◦
- The myopic cumulative-cost policy is a deterministic inner-margin rule with a shrinking threshold, and its cost grows sublinearly while query complexity grows logarithmically.The threshold shrinks asymptotically over training.Source: §4.1 · pp. 8–9
4.2 Horizon-optimized intermediate-margin policy p⋆
- The horizon-optimized schedule achieves lower final cost than the myopic schedule, the best random policy, and constant strategies by investing in queries early, with the gap over myopic growing with query price Δ.At large Δ, the myopic rule queries too little because it ignores how queries reduce future mistakes.Source: §4.2 · p. 10
4.3 Experiments
- The K/t inner-margin heuristic compares favorably with the cited sampling baselines, while the theoretically prescribed K◦ value deteriorates at larger query costs Δ.The K/t threshold induces an early query-heavy exploration phase followed by more predictions and a sharp increase in mistakes; the qualitative pattern also appears on pneumonia X-rays.Source: §4.3 · p. 11
4.4 Comments for two-layer neural networks
- For two-layer networks, the myopic policy depends on the full preactivation vector, and its selected regions can barely overlap those from naive thresholding on the network output.The illustration uses a GeLU network with two hidden neurons.Source: Figure 4 · p. 11, §4.4 · p. 12
Conclusions
The paper characterizes margin-based selection schedules for online linear classifiers in a high-dimensional realizable Gaussian setting and numerically identifies schedules minimizing final error under a budget or cumulative cost. It also identifies limits to the scope of the analysis and points to extensions involving richer data distributions, policies, and task settings.
Conclusions
- In the high-dimensional realizable Gaussian setup, optimal schedules often reduce to deterministic inner- or intermediate-margin rules with shrinking thresholds, and numerical optimization identifies schedules minimizing final error or cumulative cost.The theoretical characterization is for linear classifiers; the paper also illustrates that two-layer-network policies can take a more complex form.Source: Conclusions · p. 12
Limitations and perspectives
- The theoretical results primarily concern linear classifiers under an isotropic Gaussian data distribution, and the analysis restricts policies to functions of the sample margin.The paper identifies structured input distributions, more intricate policies, and multi-task budget allocation as directions for further study.Source: Limitations and perspectives · p. 12
AI use statement
The authors used generative AI to assist with numerical code for specified figures and with an initial appendix draft and minor stylistic rewriting; they state that they reviewed the AI-assisted work and take responsibility for the final content.
AI use statement
- Generative AI assisted with numerical code for Figs. 1–2, 5, and 6, an initial App. B draft, and minor rewriting; the authors say they verified the code and reviewed the work.They state that AI was not used to develop theoretical models, formulate mathematical claims, design methodology, or interpret results.Source: AI use statement · p. 13
A Derivation of the ODEs
The appendix derives limiting ODEs for online SGD by tracking order parameters and averaging the one-step dynamics under the Gaussian design. It explains why fluctuations vanish in the proportional high-dimensional limit and reports agreement between the ODE predictions and a finite-dimensional simulation.
A Derivation of the ODEs
- In the proportional limit with macroscopic time t=i/d, the appendix derives dynamics for the order parameters that track alignment with the teacher and squared weight norm.The generalization error depends on the weights through the correlation m/√q.Source: A Derivation of the ODEs · p. 18
- For losses with derivative bounded by C(1+|z|), one-step increments scale as d^-1 and accumulated centered fluctuations vanish as d grows, leaving deterministic limiting dynamics.The limiting ODEs follow from conditional mean increments, averaging the query decision through the selection probability.Source: A Derivation of the ODEs · pp. 18–19
- Under the fixed policy |ω|<1, the overlap m increases and the normalized squared norm q decreases, raising their correlation and reducing generalization error.The ODE curves closely match a single SGD trajectory at d=1000.Source: Figure 5 · p. 19, A Derivation of the ODEs · p. 20
- The appendix also derives cumulative-cost dynamics by averaging one-step cost increments over fresh inputs and query decisions, with Q_t and M_t representing limiting query and mistake counts.The cumulative cost is rescaled as R_k=(M_k+ΔQ_k)/d.Source: A Derivation of the ODEs · p. 20
B Control methods
The appendix casts policy selection as a low-dimensional optimal control problem over ODE dynamics, then derives myopic rules and numerical procedures for optimizing schedules under query budgets or cumulative cost.
B.1 Myopic policies
- A Lagrange multiplier ν turns the budgeted greedy rule into a deterministic query decision: query when S_t(ω) + ν < 0, with ν tuned by bisection to meet the query rate.Without the budget price, the Adatron rule would query every sample and violate the budget.Source: §B.1 · p. 21
B.2 Quadrature on the selected intervals
- Selected margin intervals are integrated with Gauss–Legendre quadrature; the analytic integrand supports geometric error reduction, and 48 nodes are used.The quadrature also makes the discretized ODE differentiable with respect to interval endpoints.Source: §B.2 · pp. 21–22
B.3 Piecewise-constant schedules
- Schedules are piecewise constant across equal time blocks, with fixed interval radii per block and ODE integration by forward Euler.The optimization uses 50 control blocks and 500 time steps, then recomputes reported quantities with 2,000 steps.Source: §B.3 · p. 22
B.4 Enforcing the query budget
- A quadratic penalty only approximately enforces the query budget, so interval widths are rescaled by bisection before recomputing the error.The rescaling is chosen to restore the target query rate.Source: §B.4 · p. 22
B.5 Optimization
- The finite-dimensional schedule is optimized by single shooting with reverse-mode gradients and L-BFGS-B, using multiple initializations because local minima occur.The best local optimum found is reported.Source: §B.5 · p. 23
C.1 Linear classifier
- For cumulative-cost minimization, the myopic policy is query-free when Δ > 1/2 and otherwise uses an adaptive margin rule.Its threshold depends on the model weights and the time-varying summary statistics m_t and q_t.Source: §C.1 · pp. 23–24
C.2 Large-time asymptotics
- For learning rate η = 2, q_t remains constant, and the large-time analysis finds that the myopic threshold κ*_t shrinks asymptotically.The analysis uses a self-consistent equation for the asymptotic behavior.Source: §C.2 · p. 25
C.3 Derivation of Remark 4.2
The linear-classifier analysis links a shrinking myopic threshold to logarithmic cumulative-cost growth. For two-layer networks, it derives the cost increment conditional on the network weights under stated rank assumptions.
C.3 Derivation of Remark 4.2
- A 1/t threshold decay yields sublinear cumulative cost: the myopic rule’s regret, query count, and mistake count grow logarithmically, while test error decays exponentially with query count.A constant threshold instead produces a linear increase in cumulative cost, for any positive margin threshold.Source: §C.3 · p. 26
C.4 Two-layer neural network
- For the two-layer network, the myopic cost derivation conditions on full-rank W and assumes β is not in rowsp(W).These conditions are used in the derivation leading to the policy expression in Result 4.4.Source: §C.4 · pp. 26–27
D.1 Benchmarked strategies
The appendix details benchmark implementations and dataset preparation, and reports that tuning the shrinking-threshold baseline matters on real datasets. It also notes that logistic-loss updates change cumulative-cost growth behavior relative to Adatron/Perceptron updates.
D.1 Benchmarked strategies
- The tuned shrinking-threshold inner-margin policy performs comparatively well across probed settings, while the theory-prescribed threshold performs poorly on real datasets because it queries too often.The tuned policy’s hyperparameter is selected by grid search; the theory-prescribed version requires no tuning.Source: §D.1 · p. 29
D.2 Preprocessing of the datasets
- The Covid-19 diagnosis dataset is balanced to 7,232 images, with 40 × 40 pixels per image and a 7,132-sample stream after holding out 100 samples.The preprocessing passage specifies that the no-infection class is downsampled and the other non-Covid classes are discarded.Source: §D.2 · pp. 29–30
D.3 Training of the 2-layer neural network
- The two-layer network uses fixed all-ones readout weights, Gaussian-initialized weights W, and 2,000 unselected logistic-loss updates with GeLU in dimension 500.The training setup uses unit learning rate η = 1.Source: §D.3 · p. 30
E Logistic loss
- Using logistic loss in SGD instead of Adatron/Perceptron updates leads to quantitatively different behavior, notably in cumulative-cost growth rates.The appendix highlights this contrast because logistic loss is more common in day-to-day machine-learning practice.Source: E Logistic loss · p. 30
E.1 Myopic policy for the cumulative cost
For logistic loss, Conjecture E.1 predicts that the myopic policy’s threshold approaches a nonzero limit, with test error decaying asymptotically. Under the conjecture, cumulative cost, mistakes, and queries remain sublinear, but no longer grow logarithmically.
E.1 Myopic policy for the cumulative cost
- The myopic threshold is conjectured to approach a nonzero limit for logistic loss, unlike the 1/t decay for Adatron.The paper reports numerical observations of the predicted scaling and leading asymptotic term across a broad range of Δ and η.Source: §E.1 · pp. 30–31
- Under the myopic policy, test error is predicted to decay asymptotically.The supplied passage states this asymptotic behavior but does not provide the decay rate.Source: §E.1 · p. 31
- Cumulative cost, mistakes, and queries are conjectured to grow sublinearly but as a power law rather than logarithmically.The logarithmic-growth comparison is with the Adatron loss.Source: §E.1 · p. 31
E.2 Derivation of Conj. E.1
The derivation studies the myopic policy’s summary-statistic dynamics under a self-consistent asymptotic ansatz with a positive limiting parameter. The paper reports numerical observations supporting the predicted asymptotics across a broad range of Δ and η.
E.2 Derivation of Conj. E.1
- The derivation follows the summary-statistic ODEs under the myopic policy and assumes a positive limit z to determine the threshold’s asymptotic behavior.Under the ansatz, the threshold converges to a limit.Source: §E.2 · p. 31
- Figure 10 compares single-run test error for d = 100 with the theoretical prediction for the t → ∞ asymptotics.Solid lines are single runs; dashed lines are the theoretical prediction.Source: Figure 10 · p. 32
- Numerical observations support the predicted quantitative asymptotics across a broad range of Δ and η.The derivation establishes that, if the assumed convergences hold, the self-consistency equation must admit a positive solution.Source: §E.2 · p. 34