WorksMathematics
Towards optimal selection schedules for online active learning
Abstract
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 . 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
Many breakthroughs in modern deep learning were achieved by training models on ever-accruing volumes of data. Yet, there exist important domains of application where labeled data is scarce. Examples include medical diagnosis [1], rare languages [2] or molecular modeling [3], where data annotation requires either a human expert, or expensive ab-initio simulations, resulting in prohibitive labeling costs. In such scenarios, it is thus essential to carefully select which samples, among a stream of unlabeled data, should be labeled.
In the present manuscript, we consider the online setting, where unlabeled data points are viewed sequentially. For each sample, the model can decide either to output a prediction, and incur a cost in case of mistake, or to query the label from a (e.g., human) expert, paying the associated annotation cost, and use the thus labeled instance to perform a gradient step, furthering its training. For example, in medical applications, a diagnosis must be issued by the model to every patient, unless it is determined further examinations need to be performed first by an expert. Querying such additional examinations is however typically costly, and thus must be done sparingly. If performed however, such examinations provide an additional data point that can improve the model accuracy, thereby reducing the frequency of future expert queries. How then to choose which labels to query, and when?
Many selection policies were proposed in the literature on online active learning [4, 5] and selective sampling [6, 7, 8, 9], some of which were shown to achieve the optimal rates of mistakes, queries or accuracy. These works, however, typically fix the form of the query policy in advance and analyze its performance. Here, we take a complementary approach and ask what the optimal policy schedule is. We consider the classical problem of online binary linear classification in the realizable case with the Adatron learning rule [10, 11], under Gaussian design, in the high-dimensional limit where the dimension of the samples is comparable to the total number of unlabeled data [12, 13, 14, 15, 16]. Using techniques from statistical physics and control theory, we precisely ascertain the optimal query policy schedule among a class of margin-based policies that minimizes, down to the constant, a given cost objective — either the generalization error under a labeling budget, or the cumulative number of mistakes and queries.
More precisely, we distinguish between myopic policies, which greedily minimize at all times the instantaneous increment in the objective, and horizon-optimized schedules, obtained by numerically optimizing the selection policies across all training times to minimize the objective at the end of training. Two classes of margin-based policies will prove of particular interest: inner-margin policies, which query only samples within a threshold distance of the decision boundary, and intermediate-margin policies, which query samples whose distance lies between two thresholds, thus discarding both the closest and the farthest samples. Our main contributions are:
We first study policies that minimize the generalization error given unlabeled samples, under a total query budget , with . We show that the myopic strategy is of the intermediate-margin type. Within this class, we then compute the horizon-optimized threshold schedules, which achieve a lower final generalization error than random, myopic, and inner-margin strategies.
We then consider the setting where mistakes have unit cost and queries cost . We derive an exact expression for the myopic policy, showing that it is an inner-margin rule with shrinking threshold. We propose a simple selection heuristic inspired therefrom, and compare its performance with other baselines on synthetic data and real medical image datasets. In the same setting, the horizon-optimized schedule is again an inner-margin rule, with higher query rate early in training, outperforming both the myopic and the random policies, with gains that grow with .
Finally, we study myopic policies for cumulative-cost minimization in two-layer neural networks, allowing them to take as an argument the full vector of preactivations. We exemplify how inner-margin policies naively applied to the network readout are suboptimal.
The code used in the manuscript can be found in the following repository.
Related works
Stream-based active learning. A now mature body of works has studied the label complexity of online active learning, ascertaining the minimal number of queries necessary to achieve a given accuracy [18, 5] (Freund and Schapire 1997). The realizable case where the two classes lie in distinct half-spaces, in particular, has been the object of refined analyses. Dasgupta et al. [4]; Yan and Zhang (2017) construct active learning algorithms achieving the optimal label complexity required to reach accuracy . The present work complements these results in the high-dimensional Gaussian setting, and investigates, given a number of unlabeled instances and a query budget , the minimal generalization error achievable, down to the constant, within a class of margin-based query policies.
Selective sampling. In problems where the learner needs to output a prediction after viewing each sample, one aims at minimizing the cumulative number of mistakes over training, rather than the final accuracy [6, 7, 20, 21, 22]. Formally, a selective sampling algorithm must determine at each iteration whether to issue a prediction, or instead query the label, with the goal of minimizing the overall number of mistakes and queries. The latter can be controlled for a variety of algorithms, as studied in [6, 7]. Some of these guarantees however become vacuous in high-dimensional settings. In the present work, in the case where mistakes have unit cost and queries have cost , we precisely characterize the myopic policy for the cumulative cost, and ascertain its large-time asymptotic behavior down to the constant.
Optimal schedules for high-dimensional online learning. In contrast to most works on online active or selective learning, which offer theoretical guarantees for a specific algorithm, this paper investigates the optimal query strategy. Formally, this amounts to ascertaining the optimal schedule of selection policies, such that the learning process driven thereby realizes minimal cost or error, while respecting a query budget. The large dimensionality of the space in which the process is embedded, however, seemingly poses significant barriers to the application of standard control-theoretic approaches. For Gaussian data nevertheless, the training dynamics (including instantaneous accuracy and mistake rates) can be succinctly described by a finite set of scalar ordinary differential equations (ODEs) (Saad and Solla, 1995a,b; Biehl and Schwarze, 1995; Goldt et al., 2019; Arous et al., 2021; Collins-Woodfin et al., 2024), on which standard variational and control analyses can be applied. This route allows for a precise characterization of optimal hyperparameter schedules, including learning rate [16, 29, 30], task ordering (Mori et al., 2025) or dropout [32, 33]. A generalization to functional hyperparameter schedules was exposed in Rattray and Saad [16]. We draw from this conceptual framework to find optimal selection policies for active half-space learning in high dimensions.
Active learning half-spaces in high dimensions. The question of active half-space learning in the proportional high-dimensional regime has received a long and sustained attention, notably in the pool-based setting [34, 35, 36, 37, 38, 39], focusing on inner-margin policies. Derényi et al. [40] study the converse problem where samples farthest from the ground-truth separator are retained, providing a characterization of the optimal threshold. The online setting was first studied by Seung et al. [41]; Kinzel and Rujan [13]; Watkin and Rau [14]; Zhou [42], in the case where the learner is allowed to design and synthesize specific samples at each step and query the accompanying label. Kinzel and Rujan [13]; Watkin and Rau [14] in particular study the prescription of designing samples orthogonal to the running weights, which corresponds to an inner-margin policy with vanishing threshold. Parrondo and van den Broeck [43] conversely consider the case where large-margin samples are retained, while Jung and Opper [44] study gradient-based selections. Closer to our work, Mai et al. [45] derive a sharp characterization of online stream-based active learning with repeated retrainings, and determine the optimal batch size for a two-step procedure. All the above works, however, assume a specific functional form for the selection policy. Here, we derive myopic policies analytically and numerically compute horizon-optimized candidates within the same functional class. While in certain settings these policies indeed correspond to inner-margin policies, as studied in prior works, we find that they can also prescribe the retention of samples at intermediate margins. The present manuscript also offers a precise characterization of the optimal schedule of such selection functions over the course of training.
Problem setup
Online active classification. We consider the problem of active online learning with a linear classifier, under Gaussian design. A stream of unlabeled samples , drawn i.i.d. from a -dimensional Gaussian distribution , is sequentially observed by the learner. At each round , the learner can
Query an expert to annotate the sample, thereby obtaining the associated label . We consider the realizable setting, where there exists an (unknown) ground truth vector with that perfectly separates the data, namely for all . With the full covariate-label pair now available, the learner may then perform a gradient update on the weights of a linear classifier
with learning rate and loss . Note that this training process corresponds to stochastic gradient descent (SGD) at batch size 1.
Alternatively, the learner may choose to not pay the cost of querying an expert, and instead issue a prediction for the unknown label of sample , at the risk of making a mistake whenever .
In line with prior works on active binary classification [15, 4, 9, 46], we focus on the -threshold squared hinge loss , for which the gradient update (1) reduces to the celebrated Adatron rule [10, 11]. The latter has been repeatedly leveraged in active learning analyses for its favorable convergence properties: in the passive case, the Adatron rule achieves a fast decay in generalization error [15] while in the active setting, it can lead to exponential decay with the number of labeled instances [4]. For extensions to the logistic loss, see App. E.
Selection policy. At every round , the choice of the learner can be encoded by a binary variable , with the learner choosing to query the label (resp. issue a prediction) if and only if (resp. ). In the case of linear classifiers, it is natural to base this choice on the margin (output) of the model for the running sample . We thus model as a Bernoulli variable of law , where the sequence of functions denotes the schedule of selection policies according to which the learner makes decisions. Note that we thus allow the policy to vary in time, and to be stochastic. Interestingly, the optimal policies derived below will correspond to deterministic selections, where takes values in . A particularly well-known instance of such deterministic rules are hard inner-margin rules [47, 48], which prescribe to label samples whenever they fall within a certain distance of the decision boundary, with the intuition that the closest samples are the hardest to classify for the current model, hence the most informative. Many other margin-based policies tailored to online Adatron or perceptron learning were proposed in the literature, see for instance Dasgupta et al. [4]; Sculley [46]; Cesa-Bianchi et al. [8], and Cacciarelli and Kulahci [49] for a survey.
Cost metrics. The present manuscript aims at ascertaining the optimal policy schedule . There exist two natural notions of cost with respect to which policies may be compared. The first is the final generalization error, defined as the misclassification error
at the final round . In the above display, the probability bears over test samples from the same distribution as the stream of training samples. We investigate policies minimizing with a constraint on the total number of queried samples:
where is the labeling budget. The final generalization error is the metric most often adopted in the active learning literature, and describes situations where the model is audited only post-training, when solely its final performance matters. To give an analogy in human learning, the same setup describes the situation of a student, whose performance at exercise sessions is inconsequential, provided they perform well at the final exam.
Selective sampling is, instead, concerned with controlling the cumulative number of errors and queries over training. If mistakes have unit cost while queries have relative cost , the cumulative cost at round is
The cumulative number of queries is defined in (3) and the cumulative number of mistakes is given by
For instance, in the case of medical diagnostics, a diagnosis needs to be presented to each patient, posing the challenge to properly balance the costs of a wrong diagnosis and that of asking for expensive human expertise.
Myopic and horizon-optimized rules. Our analysis thus sets out to describe the horizon-optimized policies , , respectively minimizing the average error under a labeling budget or the average total cumulative cost . From prior works in online learning in the high-dimensional regime (Saad and Solla, 1995a,b; Goldt et al., 2019), one expects that for a given policy the random variables and concentrate around their expectations as . Heuristically, policies resulting in small costs in expectation are thus also anticipated to display good performance on individual trials, as we illustrate in Figure 1 (right) and 2 (right).
Figure 1. (left) Selection policies in the plane for the final-error minimization. Colored regions indicate . The myopic rule (8) is shown in blue. The horizon-optimized intermediate-margin schedule (9), with and set to minimize the final error, is shown in yellow. Parameters: , , , , . (right) Final generalization error vs. query budget . Parameters: , , , . Lines represent theoretical predictions while symbols mark single-trajectory SGD simulations at . For details on the policies see Table 1.
We also consider myopic policies, which at each round minimize the expected change of the objective, conditional on the model weights at the beginning of the round. Formally, the myopic policy (resp. ) minimizes (resp. ), where the expectation bears on the sample and the query decision . Because they ignore the effect of the current choice on future rounds, myopic policies can prove suboptimal whenever queries that seem costly early in training pay off later on. For instance, for a myopic learner never queries, since random-chance error is . However, a strategy that minimizes the final cost could in principle query even at . For simplicity, we focus on throughout.
Closed-form description of the training dynamics
In the high-dimensional regime , identifying optimal selection strategies is hampered by the curse of dimensionality. We circumvent this challenge by reducing the high-dimensional SGD dynamics in Eq. (1) to scalar ODEs bearing on a small set of summary statistics, also known as order parameters in statistical physics [23]. Following Mignacco and Mori [33], we then apply standard control-theoretic methods to this low-dimensional description to find the optimal selection schedules.
Result 2.1 (Exact ODEs for the learning dynamics). Let denote the weights of the learner after steps of the online SGD dynamics in (1). In the limit with , the scalar summary statistics
concentrate in probability to the solution at time of the following deterministic ODEs
where and are functions of and and functionals of the selection policy . The expressions of and are given in Appendix § 11. We refer to as the training time and as the time horizon.
Figure 5 in App. § 11 shows that this theoretical prediction matches a single instance of numerical simulations already at . The ODEs capture the time evolution of the squared norm of the weights and their overlap with the ground truth vector . In the remainder of the paper, we work within this continuous-time description and, with a slight abuse of notation, index all quantities introduced in § 3 by , e.g. .
Figure 5. Summary statistics and as a function of training time , for the constant policy . Lines are obtained by numerically integrating the ODEs (6), while symbols mark numerical simulations of a single SGD trajectory at . Parameters: , , , .
Remark 2.2. The cost metrics in Eq. (2) and (4) can be expressed as explicit functions of the summary statistics and . The generalization error is . Similarly, the cumulative cost (4) can be expressed as a function of the summary statistics and for , see App. § 11.
Since the cost metrics are determined by the summary statistics, which evolve according to the low-dimensional deterministic dynamics in Eq. (6), we can use control-theoretic methods to find optimal training strategies. When considering inner or intermediate-margin policies, we parametrize the selection thresholds as piecewise constant in time and optimize them by direct single shooting, using exact gradients obtained by automatic differentiation through the discretized ODEs in JAX (see App. § 12). The resulting problem is non-convex, so the schedules we obtain are not guaranteed to be global optima. Nevertheless, they consistently outperform all the benchmarks we consider.
Minimizing the final error
We first look for selection policies that minimize the final generalization error over a given time-horizon , subject to the following continuous-time constraint on the total number of queries (cf. Eq. (3))
where is the expected value w.r.t. .
Myopic policy
As a first step, we investigate the myopic policy that greedily maximizes at each step the decrease in generalization error . This analysis will serve as a basis for designing the horizon-optimized policy that minimizes the terminal error . Note however that such myopic policy would not satisfy the global constraint in Eq. (7). As a consequence, we introduce a modified myopic policy that depends on a single Lagrange multiplier , enforcing (7) (see App. § 12).
Result 3.1 (Myopic policy under query budget). The myopic policy is given by
where is given in Eq. (21) of App. § 12 and is chosen to enforce Eq. (7). For a wide range of parameters this results in the intermediate-margin policy
where the threshold values and are the positive roots of (see Figure 6).
Figure 6. Selection policies in the plane for final-error (top row) and cumulative-cost (bottom row) minimization. The colored regions indicate . Parameters: , , , .
Interestingly, while inner-margin selection policies are most commonly studied in the literature, Res. 3.1 shows that selecting samples with intermediate margins can be more beneficial. We can interpret this policy by noting that the weight update (1) from the Adatron rule is proportional to the margin for misclassified samples. Samples with small margins therefore produce updates that are too small to justify spending the query budget on them. Conversely, at large samples are rarely misclassified, so a query there would also be uneconomical. Furthermore, although stochastic policies are allowed, the myopic policy is deterministic almost surely, because the instantaneous objective is linear in the selection probability (see App. § 12).
Horizon-optimized intermediate-margin policy
Motivated by the functional form of the myopic policy in Res. 3.1, we use control theory to identify the policy minimizing the final generalization error within the class of intermediate-margin rules (for details, see App. § 12).
Result 3.2 (Horizon-optimized policy under query budget). The horizon-optimized intermediate-margin policy is
where the optimal thresholding schedule is given by
The minimization in Eq. (10) bears on for , resulting in the schedule in Figure 1.
Figure 1 (left) compares the myopic policy (8), in blue, with the horizon-optimized intermediate-margin policy (9), in yellow. Both schedules reduce the selection interval as training progresses and classification improves at smaller margins. However, the horizon-optimized schedule can exploit the full training horizon to restrict the selection interval from the beginning, whereas the myopic one starts by querying a much broader range of margins, that early in training yield substantial immediate improvements, but it exhausts the labeling budget before reaching .
Figure 1 (right) shows the final generalization error as a function of the query budget for and . As benchmarks, we include the (time and margin independent) random policy , the constant intermediate-margin policy , and the inner-margin policy , with either a constant threshold or a schedule . All free parameters are optimized to minimize . The optimal intermediate-margin schedule achieves the lowest final error, with the largest gains at small query budget . Even with constant thresholds, intermediate-margin selection outperforms constant and time-dependent inner-margin policies at small and moderate budgets . We note that this observed sub-optimality of inner-margin selections echoes the findings of Hacohen et al. [50]; Hacohen and Weinshall [51]; Kolossov et al. [35]; Cui and Lu [39]; Tifrea et al. [52] in the pool-based setting.
Minimizing the cumulative cost
In this section, we now turn to studying policies minimizing the cumulative cost (4). We show that both the myopic policy and the horizon-optimized intermediate-margin policy are inner-margin rules. Indeed, samples with small produce small weight updates and are thus discarded when the objective is the final error under a budget. However, these are also the samples the model is most likely to misclassify. If mistakes made during training are costly, querying them avoids a likely error, and this benefit outweighs the small size of the resulting update.
Myopic policy
The following Result, derived in App. § 13, shows that the myopic policy minimizing the instantaneous increase in cost (4) corresponds to a deterministic inner-margin policy (Tong and Koller, [47]; Roth and Small, [48]) with shrinking threshold.
Result 4.1 (Myopic policy for the cumulative cost). The myopic policy is given by
where the margin reads
with satisfying self-consistently the equations (6) with policy . As , for , the threshold shrinks asymptotically as
As in § 5, we find a deterministic policy because the instantaneous objective is linear in . This simple policy notably induces a sub-linear growth for cost metrics, and logarithmic label complexity, as formalized in the following remark.
Remark 4.2. Under the myopic policy characterized in Result 4.1, for , the cumulative cost , number of mistakes and number of queries scale logarithmically with training time:
The error scales as , and thus decays exponentially with the number of queries . These scalings match for example those reported in [19, 54, 55].
Horizon-optimized intermediate-margin policy
We now turn to the horizon-optimized policy for the cumulative cost, again focusing on the class of intermediate-margin strategies, as for Res. 3.2.
Result 4.3 (Horizon-optimized policy for the cumulative cost). We again optimize an intermediate-margin policy
where the optimal thresholding schedule is given by
For all parameter values considered, we obtain , so that the horizon-optimized strategy collapses onto an inner-margin policy. This collapse is shown in Figure 2 (right) and largely extends to time independent policies.
Figure 2. (left) Selection policies in the plane for cumulative-cost minimization. Colored regions indicate . The myopic rule , greedily maximizing the cost decrease at each time, is shown in blue. The horizon-optimized inner-margin schedule , with set to minimize the final cumulative cost, is shown in yellow. Parameters: , , , , . (right) Cumulative cost vs. the query price . Parameters: , , , . Lines represent theoretical predictions while symbols mark single-trajectory SGD simulations at . Constant and optimal intermediate-margin families collapse to the inner-margin strategies once optimized. For details on the policies see Table 1.
Figure 2 (right) shows that time-dependent schedules achieve lower cost than the best random policy and all constant strategies. All free parameters, including , are chosen to minimize . The horizon-optimized schedule outperforms the myopic one, with a gap growing with . The myopic rule queries only when it lowers the cost immediately, ignoring that each query also reduces future mistakes. At large it therefore queries too little, whereas the horizon-optimized schedule invests in queries early in training that pay off later on.
Experiments
The particularly compact asymptotic form (12) for the myopic threshold (11) naturally inspires the simple heuristic policy schedule , with a threshold shrinking at a rate. We compare the performance of this policy against other margin-based rules for online Adatron/Perceptron learning proposed in the literature. Cesa-Bianchi et al. [8] –blue lines in Figure 3– (resp. Sculley [46] –green lines in Figure 3–) propose a sigmoid (resp. exponential) functional ansatz for the selection probability . Orange lines represent a variant of the former rule, with adaptive bandwidth (Cesa-Bianchi et al., [8]). Dasgupta et al. [4] –red lines in Figure 3– on the other hand rely on a hard inner-margin selection rule with an adaptive threshold that halves after every streak of consecutive correct predictions. Details on these algorithms and their implementation are collected within App. D. Figure 3 (left) illustrates the time evolution of the cumulative cost for these different policies, presenting only the choice of hyperparameter that minimizes in hindsight the terminal cost . The heuristic inspired from the asymptotics of Result 4.1 –brown lines in Figure 3– compares favorably against the aforementioned baselines, and results in overall small cumulative cost . The performance for the particular prescription for the hyperparameter , which can be read from the theoretical expression (12), is on the other hand found to deteriorate at larger costs , as illustrated in Figure 7 and Figure 9 in App. D.
Figure 3. Cumulative cost and number of queries versus mistakes (inset) for the first-order and adaptive b-sampling algorithms [8] (blue, orange), the logistic sampling algorithm [46] (green) and the active perceptron algorithm [4] (red), for binary classification on isotropic Gaussian data in dimension (left), and the pneumonia diagnosis task on chest X-ray images [53] (right). Purple curves mark a random (constant, margin-independent) strategy. Brown curves represent an inner margin policy with shrinking threshold, with tunable bandwidth . The query cost was set to . Hyperparameters were tuned in hindsight to minimize , among a grid of 50 values. The black curve represents the simple thresholding strategy , where is the asymptotically optimal value prescribed by (12) for , , . Shades mark one standard deviation over 5 trials, with the dataset reshuffled at each run.
Figure 7. Same as Figure 3 (right), for , .
Figure 9. Same as Figure 3 (left), for .
This observation stands in coherence with the discussion of the previous subsection that the performance of the myopic policy comparatively degrades at larger , see Figure 2 (right). A finer examination of the joint evolution of , (Figure 3, inset) reveals that the shrinking threshold incentivizes a first phase of exploration, with a sharp increase of the number of queries , followed by a phase of exploitation where the model attempts more predictions, as signaled by a sharp increase in mistakes . This qualitative behavior can still be observed for real data that does not satisfy the Gaussian assumption, as shown in Figure 3 (right) for the task of pneumonia diagnosis from chest X-ray images (Kermany et al., [53]), and in Figure 8 in App. D for Covid-19 diagnosis (Chowdhury et al., [56]; Rahman et al., [57]).
Figure 8. Same as Figure 3, for the Covid-19 diagnosis task from chest X-ray scans Chowdhury et al. [56]; Rahman et al. [57], for , .
Comments for two-layer neural networks
The findings of § 6 make it tempting to wonder whether output-thresholding strategies are generically well-adapted to control the cumulative cost (4). This final section nuances this picture, and shows that this intuition ceases to hold for more complex learning models. Consider for instance the width- two-layer neural network with weights , , and activation function acting entry-wise. We again consider training this model on the classification task described in § 3, using online SGD (1). Note that when as diverge, the resulting training dynamics are again captured by a limiting set of low-dimensional ODEs (Saad and Solla, [23]; Golft et al., [26]). For such models, it is natural to consider the larger class of selection policies that take as argument for a given input the whole array of pre-activations , rather than the sole output . We note that policies bearing exclusively over the output in fact correspond to special instances of the former class. Is the myopic policy for the cumulative cost still of the form of a hard-thresholding (11) on the output ? The next Result, derived in App. § 13, answers this question negatively.
Result 4.4 (Myopic policy for two-layer networks). Conditional on the weights at time , supposing is full rank and , the myopic policy for the cumulative cost at time is given by
where and . is the normal cumulative distribution function.
While the optimal policy is still found to be deterministic, it no longer depends on the pre-activation through the sole output . In fact, the regions in pre-activation space that the (oracle) policy (13) prescribes to select can significantly differ from those selected by a naive output-thresholding strategy of the form . Figure 4 shows, for a network with hidden neurons trained without data selection on the logistic loss for 1000 steps, that the two regions (respectively in blue and yellow) might in fact barely overlap.
Figure 4. Preactivations selected by the myopic policy (13) (blue) for and a naive inner-margin threshold on the network output (yellow). The weights in (13) were extracted from a GeLU-activated two-layer neural network with hidden neurons, trained without data selection on the logistic loss for 1000 steps, at and . The untrained readout is . The decision boundary of the network is represented in dashed lines.
Conclusions
We investigate data selection schedules for online active learning with linear classifiers. In the high-dimensional realizable Gaussian setup, we precisely characterize the margin-based selection policy schedules that minimize at each round the increment in error or cost of mistakes and queries, down to the constant. In many instances, we find that optimal strategies coincide with deterministic inner- or intermediate-margin selection rules with shrinking thresholds. Within these classes of policies, we further numerically determine the optimal threshold schedules that minimize the final error under a labeling budget or the cumulative cost. Finally, we exemplify how optimal selection policies for two-layer neural networks can take a more complex form. We believe that a precise investigation of the latter constitutes an interesting avenue for future research.
Limitations and perspectives
The theoretical contributions of the present work primarily describe linear classifiers, and moreover rest on strong assumptions, notably that of an isotropic Gaussian data distribution. It would be interesting to extend our analysis to models in which the input distribution itself encodes task-relevant structure, such as the hidden manifold model [58] or class-dependent Gaussian mixtures (Riffenburgh et al., 2021), in order to investigate how this additional information affects query selection. Furthermore, we restricted ourselves to query policies that are functions of the sample margin (equivalently, model output) . While this class encompasses many heuristics in the literature [8, 46], there exist functionally more intricate policies that do not fall therein, such as the second-order rule of Cesa-Bianchi et al. [8] (Figure 3). Finally, while we focused on a single stationary task, a promising direction would be to investigate how to allocate a limited labeling budget across tasks in multi-task settings. Building on Mori et al. (2025), this could clarify how task similarity and interference affect optimal labeling strategies at different stages of learning.
Acknowledgements
H. Cui is grateful to Richard Combes and Moïse Blanchard for introducing him to the selective sampling problem. F. Mignacco is grateful to the Center for Brain Science at Harvard University for its hospitality during her visit, when this work was conducted. F. Mori was supported by the Center of Mathematical Sciences and Applications (CMSA) at Harvard University. F. Mignacco was supported by the Human Frontier Science Program (award number: LT0049/2023-L).
AI use statement
In this work, we used generative AI tools to assist with the implementation of methods, specifically in developing the numerical code used to produce Figure 1–Figure 2, 5 and 6. We did not use generative AI tools to develop theoretical models or conceptual frameworks, formulate mathematical claims, provide critical ingredients for proving mathematical claims, assist in the writing of proofs, propose or refine hypotheses, design or provide feedback on research methodology or experiments, clean or reformat datasets, support qualitative or thematic data analysis, or interpret results. Generating synthetic datasets and assisting with translation were not applicable to this work.
Additionally, we used generative AI tools to draft an initial version of App. § 12 and for minor rewriting and stylistic improvements to the manuscript. We reviewed all AI-assisted work and, in particular, verified and tested the AI-assisted code for correctness. We take responsibility for the final content of this work, including all text, claims, and artifacts produced with the aid of generative AI.
Derivation of the ODEs
In this appendix, we derive the ordinary differential equations (ODEs) for the order parameters and given in Eq. (6) of the main text, tracking the learning dynamics of online SGD:
with learning rate . The teacher is fixed throughout the training, with , and the labels are . At each step , the selection process is encoded by the Bernoulli variable . In the following, we will consider differentiable losses of the signed margin, highlighting the Adatron rule with as a special case.
In the online setup, at each step a fresh sample is considered, independent of the weights . Therefore, conditional on , the margins are also jointly Gaussian with zero mean and second moments given by:
where the expectations are over , conditional on . We have defined the order parameters (alignment with the teacher) and (squared norm of the weights), which fully determine the joint conditional margin distribution
The generalization error depends on the weights only through the margins and can thus be expressed solely in terms of the correlation coefficient
Therefore, in order to track the generalization error over training, it is sufficient to track the dynamics of the order parameters. Substituting the update rules (14) into the definitions (15) gives the exact increments
where we have used that , hence . The quadratic term in the increment of must be retained, since it contributes at the same order in as the linear term.
We take the proportional infinite-dimensional limit with fixed and consider the macroscopic time , where each increment is of order . The learning rate is also held fixed. The input norm satisfies and , and hence it converges in probability:
For an isotropic Gaussian initialization independent of the teacher, the initial order parameters also concentrate as . Indeed, averaging over the initialization and using ,
Consequently, , providing deterministic initial conditions for the limiting dynamics.
To control the increments during training, we consider losses that satisfy for all , with a finite constant independent of and . This encompasses squared hinge, square, and logistic losses. The increments in Eq. (17) scale as . Over steps at fixed , their conditional means generate a finite drift, while the centered fluctuations are uncorrelated across steps and have cumulative standard deviation of order , vanishing as . Here, conditioning is on the training history before step , and the averages are over the fresh input and query decision .
The limiting dynamics are therefore determined by the conditional mean increments, following the standard ODE approach to online learning Saad and Solla [23]; Biehl and Schwarze [25]; Engel and van den Broeck [15] (see, e.g., Goldt et al. [26]; Arous et al. [27] for a more rigorous treatment). Averaging over replaces it by , while input-norm concentration allows to replace by one. Dividing the resulting mean increments by , the order parameters dynamics (17) concentrate in probability to their deterministic limit
At a fixed training time , we write and . Since the policy depends only on the margin , it is convenient to first average over the conditional teacher margin , where and . Denoting the standard normal density (resp. cumulative distribution function) as (resp. ), the marginal density of as , and its standardized conditional mean as ,
the three moments appearing in Eq. (18) are given by
For any function , the corresponding term in (18) factorizes as
All three moments in (19) are even in , so every policy that we derive in the following can be written as a condition on alone.
For the Adatron rule, , so and . Each nonzero update increases the overlap , therefore, starting from , we have nondecreasing throughout training. Using the conditional misclassification probability for , Eq. (18) becomes
The self-overlap is nonincreasing for and remains constant for in the limiting dynamics.
Figure 5 compares the ODE predictions (20) with numerical simulations of a single SGD trajectory at under the fixed policy . During training, the overlap increases while the normalized squared weight norm decreases, increasing their correlation and thereby reducing the generalization error. The close agreement between the theoretical curves and simulation points shows that the ODEs accurately capture this evolution already at finite dimension.
Similarly, we derive the dynamics of the (rescaled) cumulative cost (see Eq. (4) of the main text) by averaging its one-step increments over the fresh input and query decision , conditional on the training history before step . We recall that denotes the cumulative number of queries, and the cumulative number of mistakes. Since samples arrive per unit of macroscopic time, with a slight abuse of notation here we denote by and the deterministic limits of , at , while as in the main text. Their time evolution is given by
The constraint that a fraction of the samples is queried becomes
Control methods
The ODEs of Result 2.1 reduce the search for a selection policy to a low-dimensional optimal control problem. The state is , the control is the policy , and the objective is either the final error under the budget (7), or the cumulative cost . This appendix describes how we solve this problem. We first derive the myopic policy, then explain how we discretize and optimize time-dependent schedules.
Myopic policies
Both and are linear in , so the rate of change of the error is linear in as well. We can write it as
where and follow from (16). We recall that denotes the expected value with respect to . The function measures how much querying a sample at margin changes . Samples with reduce the error, and the others do not. A greedy policy that minimizes (21) at each time would therefore query every with . For the Adatron rule, however, is negative for all . The greedy policy then queries every sample and violates the budget (7).
To enforce the budget, we introduce a Lagrange multiplier . This is a single scalar for the whole trajectory, and it acts as a fixed price per query. The instantaneous objective is linear in . Therefore, optimizing over arbitrary selection probabilities yields a deterministic myopic schedule almost surely: a sample at margin is queried only if , that is, only if the error reduction it brings outweighs the price of the query, giving the policy of Result 3.1. We tune by bisection so that the realized query rate equals .
Quadrature on the selected intervals
All the policies we consider select a union of intervals in , and the integrands in and are even in . For an intermediate-margin policy , every expectation is therefore an ordinary integral over the selected interval:
where stands for any of the conditional moments of App. A. We compute these integrals with an -point Gauss–Legendre rule, rescaled from to :
| Strategy | Policy | Variables optimized (Fig. 1) | Variables optimized (Fig. 2) |
| Myopic | one scalar , so that the query rate equals | nothing | |
| Inner margin, constant | nothing: the budget fixes | one scalar | |
| Inner margin, schedule | time-dependent | time-dependent | |
| Intermediate margin, constant | one scalar , with fixed by the budget at each | two scalars | |
| Intermediate margin, schedule | time-dependent and | time-dependent and | |
| Random | , independent of and | nothing: the budget forces | one scalar |
caption: Policy families compared in Figs. 1 (right) and 2 (right).
:::
where and are the standard Gauss–Legendre nodes and weights on . This choice has two advantages. First, it is very accurate. The integrand is analytic on , so the quadrature error decreases geometrically with and we use . Second, and more importantly, it makes the discretized ODE in Eq. (22) differentiable with respect to the policy parameter and .
Piecewise-constant schedules
For simplicity, we approximate the schedules to be piecewise constant in time. We split the horizon into equal blocks and keep the radii fixed within each block:
The control is then a vector of numbers, or numbers for inner-margin policies, where . We integrate the ODEs (6) with forward Euler on time steps, with a multiple of . The time integrals in (7) and in are computed with the trapezoidal rule on the same grid. During optimization we use and . All reported quantities are then recomputed with .
Enforcing the query budget
During optimization, we impose the budget (7) through a quadratic penalty:
A penalty does not enforce the constraint exactly, so the optimized schedule can slightly overspend or underspend the budget. We correct this afterwards by rescaling all interval widths by a common factor ,
with chosen by bisection so that the query rate equals . We then recompute the error for the corrected schedule.
Optimization
We solve the resulting finite-dimensional problem by direct single shooting: for a given control vector, we simulate the whole trajectory, evaluate the objective, and update the controls. The forward simulation is implemented in JAX, which provides exact gradients with respect to the control vector by reverse-mode automatic differentiation through the discretized trajectory. We minimize with L-BFGS-B, using box constraints on the controls. The objective has several local minima, so we run each optimization from a few initializations, and we warm-start from the previous solution when sweeping or . We report the best local optimum found.
Myopic schedules for the cumulative cost
We detail in this Appendix the derivations of the myopic policy for the cumulative cost objective (4), for a linear classifier (Res. 4.1) and a two-layer neural network (Res. 4.4).
Linear classifier
We first ascertain the policy schedule that greedily minimizes the local increment in cost . At a given step , the latter reads
where the expectation bears over
For a given , taking a functional derivative with respect to ,
The sign of the derivative is dictated by the term in brackets. If the latter is positive, then the risk increment is minimal at . If conversely the bracketed term is negative, then the is minimal for . The myopic policy for the cumulative risk is thus
If , the optimal rule never makes a query, since even a random classifier that always attempts a prediction will achieve, on average, smaller cost increment. If on the other hand, reduces to an adaptive margin-based policy of the form
with
This recovers equations 4.1 of Res. 4.1. The expression of the threshold thus depends on the model weights as time , as encapsulated by the summary statistics , . When the model is trained with the Adatron rule with , and guided at each round by the , an analysis of the ODEs (6) allows to precisely ascertain the asymptotic behavior of in the limit of large training times . This is the objective of the following subsection.
Large-time asymptotics
We now turn to examining the behavior of the threshold (23) when the summary statistics , are self-consistently governed by the ODEs (6) under policy schedule , with . Let us show in self-consistent fashion that
We accordingly denote , and aim at determining self-consistently the leading coefficient . Denoting , we also assume that admits a non-zero limit as , which will be subsequently verified self-consistently. We accordingly introduce such that
again to be determined self-consistently. Under these assumptions, the ODE governing the time evolution of the summary statistics (6) simplifies as
where we introduced
On the other hand, for a learning rate (an assumption also made e.g. by Dasgupta et al. [4]), the squared norm remains constant along training. Then, it follows from the identity
that scales as
when . As a corollary, the test error thus admits the following asymptotic behavior
Finally, returning to (24), one deduces that satisfies the self-consistent equation
which provides a first self-consistent equation bearing on .
Having determined the asymptotics of , one is now in a position to ascertain the limiting behavior of , and in doing so close the equations on . From (23) and (25), asymptotically shrinks as
from which one deduces . Returning to the self-consistent equation (24), the latter simplifies and gives in closed form
for the myopic rule. Finally, we find
with
Derivation of Remark 4.2
The expected regret increment is thus at large time given at leading order by
Thus, the regret only augments logarithmically for the myopic rule, as
Remark C.1. The decay of the threshold plays a key role in ensuring the sub-linear growth of the cumulative cost. One can show along identical lines that if a non-adaptive threshold is used, with constant in time, one instead observes a linear in time increase
no matter the margin .
As an additional remark, note that the number of queried samples scales logarithmically with time, as the policy gets more stringent.
To leading order,
Namely, the myopic policy makes the test error decay exponentially with the number of queries. This scaling is comparable to those proved for instance by Dasgupta et al. [4], for another selection policy. Finally, the cumulative number of mistakes also grows logarithmically as
which concludes the derivation of Remark 4.2.
Two-layer neural network
We now turn to the derivation of Result 4.4, which borrows identical steps to that of Result 4.1. At a given step , conditional on the network weights at that time (with the latter assumed full rank), the average increment in cost reads
where the expectation bears over
with , . For a given , taking a functional derivative with respect to ,
We note that the assumption ensures . Thus,
which recovers (13) of Result 4.4.
Experimental details
Benchmarked strategies
We provide additional details on the implementation of the selection policies represented in Figure 3, Figure 7, which have been proposed in the literature for the problem considered in the present work, namely online active binary classification with a linear classifier trained with Adatron/Perceptron updates [10, 60]. Let us note that all these algorithms exhibit comparable runtime.
b-sampling (b-spl) [8] proposes a margin-based selection rule with (constant-in-time) acquisition probability
for a given choice of bandwidth . As specified in the original work, the Perceptron rule was used to update the model weights, instead of the Adatron rule. For each one of Figure 3, Figure 7, Figure 8, Figure 9 a grid-search over values for the parameter , evenly spread on a logarithmic grid between , was performed, and only the trajectory corresponding to the value minimizing the terminal cumulative cost was plotted.
Adaptive b-sampling (ada-b-spl) [8] is an adaptive version of b-sampling, which prescribes to increase the bandwidth as the square-root of the cumulative number of mistakes on queried samples, namely
with
for a given choice of tunable hyperparameter . The value leading to minimal over a logarithmic grid of size 50 between was plotted.
Logistic sampling (log.-spl) ([46]) instead proposes a constant-in-time exponential (rather than sigmoid) ansatz for the acquisition probability
with hyperparameter , again leveraging the Perceptron training rule. The value leading to minimal over a logarithmic grid of size 50 between , 10 was plotted.
Active Perceptron (AL-Perc) ([4]) corresponds to an Adatron rule with learning rate , and a hard inner-margin threshold policy
where the threshold is initialized at , and divided by 2 every time a streak of consecutive correct predictions is achieved. It thus resembles the myopic policy (12) of Result 4.1, in that it involves a shrinking margin. 50 values of the patience parameter between 1 and 101 were simulated, and the value leading to minimal terminal cumulative cost plotted. Note that the pseudo-code of the original paper Dasgupta et al. [4] does not explicitly prescribe to reset the streak count after every threshold-halving, but the subsequent work of Monteleoni and Kaariainen [61] does. We implement the latter prescription.
Passive baseline (random) We finally include the baseline of a random selection policy, which queries a sample with constant prediction , irrespective of the sample. 50 values of were simulated, and the value minimizing the terminal cost retained and plotted. Updates are performed using the Perceptron rule.
In addition to these classical baselines, we implement the following policies, taking inspiration from the characterization of the myopic policy of Res. 4.1.
Inner-margin with shrinking threshold (-inner-margin) corresponds to a inner-margin policy
with tunable hyperparameter . In Figure 3, Figure 7, Figure 8, Figure 9, a grid-search over values for the parameter , evenly spread on a logarithmic grid between –50, was performed, and only the trajectory corresponding in hindsight to the value minimizing the terminal cumulative cost was plotted.
Inner-margin with theory-prescribed threshold (-inner-margin) Note that Res. 4.1, Eq. (12) affords a particular prescription for the parameter above. The black lines in Figure 3, Figure 7, Figure 8, Figure 9 correspond to this particular value . For instance, for , , , . In contrast to all other baselines, this policy is hyperparameter-free, and calls for no tuning.
We note that the inner-margin policy performs comparatively well against all studied baselines in all probed settings, provided the hyperparameter is tuned. The particular prescription (23) on the other hand performs poorly on real datasets, and is found to query too often.
Preprocessing of the datasets
Covid 19 dataset ([56, 57]) The original dataset includes 3616 chest X-ray scans from Covid-positive patients, and 17549 scans from patients with no infection, non-Covid infection, pneumonia. For simplicity, the latter two classes were discarded, and the class of no infection was downsampled to 3616 images to balance the dataset, yielding a total of 7232 samples. Each image was resized to pixel. A held-out dataset was constituted from 100 samples, and used to fit the scikit-learn [62] StandardScaler. The latter was then used to transform the remaining images, which corresponds to the total stream length. At each round, the sample is normalized to unit norm before being presented to the model and policy.
Chest-Xray scans dataset [53] The dataset includes 5863 chest X-ray scans from patients with(out) pneumonia. The two classes were not balanced. Each image was resized to pixel. A held-out dataset was constituted from 100 samples, and used to fit the scikit-learn [62] StandardScaler. The latter was then used to transform the remaining images, which corresponds to the total stream length. At each round, the sample is normalized to unit norm before being presented to the model and policy.
Training of the 2-layer neural network
We now detail the training procedure followed to obtain the network weights , from which Figure 4 was then produced, using the expression of Result 4.4. The readout weights were initialized, and kept fixed throughout training, to the all-ones vector . The weights were initialized with i.i.d standard Gaussian entries, then updated times with the online gradient update
with unit learning rate , on the logistic loss , and without any data selection. The activation was taken to be GeLU. Simulations were conducted in dimension .
Logistic loss
The main text focuses on the Adatron online training procedure [10, 15], which can be viewed as a variant of the classical Perceptron rule [60]. While these losses are classically considered in many works on online active classification [63, 8, 46, 9], losses such as the logistic loss are more commonly leveraged in day-to-day machine learning practice. The present Appendix is devoted to expanding the discussion of the main text the latter, highlighting in particular the difference with Adatron/Perceptron rules. In fact, the use of the logistic loss in the SGD updates (1) instead of the Adatron/Perceptron loss leads to a quantitatively different behavior, notably in terms of growth rates of the cumulative cost. This is the object of the present Appendix.
Myopic policy for the cumulative cost
We revisit the analysis of the myopic rule for the cumulative cost (4), characterized for the Adatron rule in Result 4.1, for the case of the logistic loss. While still takes the form (11), since the latter only depend on the loss through the current-time summary statistics values , the asymptotic behavior of the threshold differs. The following conjecture surmises that the latter tends to a non-zero limit in the large-time limit , as opposed to the decay for Adatron.
Conjecture E.1 (Myopic policy for the cumulative cost, logistic loss). Let be the logistic loss . If the equation
admits a positive solution , then the threshold (23) admits a non-zero limit
Furthermore, when the policy is employed, the test error decays asymptotically as
As will be detailed in the following subsection, Eq. (27) is in fact a necessary condition for the following two asymptotic statements to be self-consistent. Heuristically, we numerically observe the predicted scaling and leading asymptotic term across a broad range of values for (see Figure 10), leading us to surmise that Conj. E.1 holds more broadly.
Figure 10. Test error as a function of training time, with online SGD with logistic loss, under the myopic policy (11). Solid lines represent single runs in dimension , dashed lines represent the theoretical prediction for the asymptotics of Conjecture E.1.
An immediate corollary of Conj. E.1 is that although the cumulative cost (4), number of mistakes (5) and number of queries (3) still admit sub-linear growth, the latter is no longer logarithmic, but power-law.
Remark E.2 (Cumulative cost scaling). The cumulative cost , number of mistakes , and number of queries scale as .
This power-law is to be contrasted to the much milder logarithmic growth induced by the Adatron loss, as summarized in Rem. 4.2.
Derivation of Conj. E.1
In order to derive the asymptotic scaling of (23), one needs to study the dynamics of the summary statistics , as governed by the ODEs (6) controlled by the myopic policy (11). In the likeness of App. C, we make a series of ansatz, which will be subsequently verified in self-consistent fashion. We assume
together with
where we introduced the limit , to be determined self-consistently. Under these assumptions, the threshold then converges to the limit
It thus remains to ascertain . On the one hand, the ODE for simplifies as
By the same token
Thus,
From the above and the observation that , one deduces
One is now in a position to determine self-consistently . For all the above to be consistent, one has, on the one hand
On the other hand, from the definition of , one also has
Unless the double integral is zero, this scales as . Since equations (28) and (29) are equal, the right hand side of the latter must vanish at leading order. This provides the following condition
We have thus established that if there exists a regime where the above assumed convergences are realized, then Eq. (30) necessarily admits a positive solution. We numerically observe that the quantitative asymptotics of Conj. E.1 hold for a broad section of values for , .
References
- [1]Ying Liu. Active learning with support vector machine applied to gene expression data for cancer classification. Journal of chemical information and computer sciences, 44(6):1936–1941, 2004.pubmed.ncbi.nlm.nih.gov/15554662
- [2]Nataliia Kholodna, Sahib Julka, Mohammad Khodadadi, Muhammed Nurullah Gumus, and Michael Granitzer. Llms in the loop: Leveraging large language model annotations for active learning in low-resource languages. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 397–412. Springer, 2024.arxiv.org/abs/2404.02261
- [3]Noah Felis and Wilke Dononelli. Falcon: fast active learning for machine learning potentials in atomistic and ab initio molecular dynamics simulations. npj Computational Materials, 12(1):1, 2025.
- [4]Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron-based active learning. In International conference on computational learning theory, pages 249–263. Springer, 2005.DOI
- [5]Steve Hanneke. Theory of active learning. Foundations and Trends in Machine Learning, 7(2-3):127–292, 2014.
- [6]William Réveillard, Vasileios Saketos, Alexandre Proutiere, and Richard Combes. Minimizing human intervention in online classification. arXiv preprint arXiv:2510.23557, 2025.arxiv.org/abs/2510.23557
- [7]Steve Hanneke and Liu Yang. Toward a general theory of online selective sampling: Trading off mistakes and queries. In International Conference on Artificial Intelligence and Statistics, pages 3997–4005. PMLR, 2021.
- [8]Nicolo Cesa-Bianchi, Claudio Gentile, and Luca Zaniboni. Worst-case analysis of selective sampling for linear-threshold algorithms. Advances in neural information processing systems, 17, 2004.
- [9]Nicolo Cesa-Bianchi, Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In Proceedings of the 26th annual international conference on machine learning, pages 121–128, 2009.
- [10]JK Anlauf and M Biehl. The adatron: an adaptive perceptron algorithm. EPL (Europhysics Letters), 10 (7):687–692, 1989.
- [11]Theodore Samuel Motzkin and Isaac Jacob Schoenberg. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6:393–404, 1954.
- [12]H Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In Proceedings of the fifth annual workshop on Computational learning theory, pages 287–294, 1992a.
- [13]Wolfgang Kinzel and Pal Rujan. Improving a network generalization ability by selecting examples. EPL (Europhysics Letters), 13(5):473–477, 1990.DOI
- [14]TLH Watkin and A Rau. Selecting examples for perceptrons. Journal of Physics A: Mathematical and General, 25(1):113–121, 1992.DOI
- [15]Andreas Engel and Christian van den Broeck. Statistical mechanics of learning, volume 1. Cambridge University Press Cambridge, 2001.
- [16]Magnus Rattray and David Saad. Globally optimal on-line learning rules. Advances in Neural Information Processing Systems, 10, 1997.
- [18]Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine learning, 28(2):133–168, 1997.
- [19]Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30, 2017.arxiv.org/abs/1702.05581
- [20]Aditya Gangrade, Anil Kag, Ashok Cutkosky, and Venkatesh Saligrama. Online selective classification with limited feedback. Advances in Neural Information Processing Systems, 34:14529–14541, 2021.arxiv.org/abs/2110.14243
- [21]Jialin Yu and Moïse Blanchard. Distribution-free sequential prediction with abstentions. arXiv preprint arXiv:2602.17918, 2026.arxiv.org/abs/2602.17918
- [22]Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetty. Adversarial resilience in sequential prediction via abstention. Advances in Neural Information Processing Systems, 36:8027–8047, 2023.arxiv.org/abs/2306.13119
- [23]David Saad and Sara A Solla. Exact solution for on-line learning in multilayer neural networks. Physical Review Letters, 74(21):4337, 1995a.pubmed.ncbi.nlm.nih.gov/10058475
- [25]Michael Biehl and Holm Schwarze. Learning by on-line gradient descent. Journal of Physics A: Mathematical and general, 28(3):643–656, 1995.DOI
- [26]Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborová. Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. Advances in neural information processing systems, 32, 2019.DOI
- [27]Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22(106):1–51, 2021.arxiv.org/abs/2003.10409
- [29]Magnus Rattray and David Saad. Analysis of on-line training with optimal learning rates. Physical Review E, 58(5):6379, 1998.DOI
- [30]Blake Bordelon and Francesco Mori. Theory of optimal learning rate schedules and scaling laws for a random feature model. arXiv preprint arXiv:2602.04774, 2026.arxiv.org/abs/2602.04774
- [32]Francesco Mori and Francesca Mignacco. Analytic theory of dropout regularization. Physical Review E, 112(4):045301, 2025.arxiv.org/abs/2505.07792
- [33]Francesca Mignacco and Francesco Mori. A statistical physics framework for optimal learning. PNAS nexus, 5(6):pgag182, 2026.DOI
- [34]Hugo Cui, Luca Saglietti, and Lenka Zdeborová. Large deviations in the perceptron model and consequences for active learning. Machine Learning: Science and Technology, 2(4):045001, 2021.arxiv.org/abs/1912.03927
- [35]Germain Kolossov, Andrea Montanari, and Pulkit Tandon. Towards a statistical theory of data selection under weak supervision. arXiv preprint arXiv:2309.14563, 2023.arxiv.org/abs/2309.14563
- [36]Elvis Dohmatob, Mohammad Pezeshki, and Reyhane Askari-Hemmat. Why less is more (sometimes): A theory of data curation. arXiv preprint arXiv:2511.03492, 2025.arxiv.org/abs/2511.03492
- [37]Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 35:19523–19536, 2022.arxiv.org/abs/2206.14486
- [38]Reyhane Askari-Hemmat, Mohammad Pezeshki, Elvis Dohmatob, Florian Bordes, Pietro Astolfi, Melissa Hall, Jakob Verbeek, Michal Drozdzal, and Adriana Romero-Soriano. Improving the scaling laws of synthetic data with deliberate practice. arXiv preprint arXiv:2502.15588, 2025.
- [39]Hugo Cui and Yue M Lu. Asymptotic theory of iterated empirical risk minimization, with applications to active learning. In International Conference on Machine Learning, pages 21885–21949. PMLR, 2026.arxiv.org/abs/2601.23031
- [40]Imre Dérényi, Tamás Geszti, and Géza Györgyi. Generalization in the programed teaching of a perceptron. Physical Review E, 50(4):3192, 1994.pubmed.ncbi.nlm.nih.gov/9962364
- [41]Hyunjune Sebastian Seung, Haim Sompolinsky, and Naftali Tishby. Statistical mechanics of learning from examples. Physical review A, 45(8):6056, 1992b.pubmed.ncbi.nlm.nih.gov/9907706
- [42]Hai-Jun Zhou. Active online learning in the binary perceptron problem. Communications in Theoretical Physics, 71(2):243, 2019.DOI
- [43]JMR Parrondo and Christian van den Broeck. Error vs. rejection curve for the perceptron. EPL (Europhysics Letters), 22(5):319–324, 1993.
- [44]Georg Jung and Manfred Opper. Selection of examples for a linear classifier. Journal of Physics A: Mathematical and General, 29(7):1367–1380, 1996.DOI
- [45]Xiaoyi Mai, Salman Avestimehr, Antonio Ortega, and Mahdi Soltanolkotabi. On the effectiveness of active learning by uncertainty sampling in classification of high-dimensional gaussian mixture data. In ICASSP 2022-2022 IEEE international conference on acoustics, speech and signal processing (ICASSP), pages 4238–4242. IEEE, 2022.
- [46]D Sculley. Online active learning methods for fast label-efficient spam filtering. In CEAS, volume 7, page 143, 2007.
- [47]Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 2(Nov):45–66, 2001.
- [48]Dan Roth and Kevin Small. Margin-based active learning for structured output spaces. In European conference on machine learning, pages 413–424. Springer, 2006.DOI
- [49]Davide Cacciarelli and Murat Kulahci. Active learning for data streams: a survey. Machine Learning, 113 (1):185–239, 2024.DOI
- [50]Guy Hacohen, Avihu Dekel, and Daphna Weinshall. Active learning on a budget: Opposite strategies suit high and low budgets. arXiv preprint arXiv:2202.02794, 2022.arxiv.org/abs/2202.02794
- [51]Guy Hacohen and Daphna Weinshall. How to select which active learning strategy is best suited for your specific problem and budget. Advances in Neural Information Processing Systems, 36:13395–13407, 2023.arxiv.org/abs/2306.03543
- [52]Alexandru Tifrea, Jacob Clarysse, and Fanny Yang. Margin-based sampling in high dimensions: When being active is less efficient than staying passive. In International Conference on Machine Learning, pages 34222–34262. PMLR, 2023.arxiv.org/abs/2212.00772
- [53]Daniel S Kermany, Michael Goldbaum, Wenjia Cai, Carolina CS Valentim, Huiying Liang, Sally L Baxter, Alex McKeown, Ge Yang, Xiaokang Wu, Fangbing Yan, et al. Identifying medical diagnoses and treatable diseases by image-based deep learning. cell, 172(5):1122–1131, 2018.DOI
- [54]Boshuang Huang, Sudeep Salgia, and Qing Zhao. Disagreement-based active learning in online settings. IEEE Transactions on Signal Processing, 70:1947–1958, 2022.arxiv.org/abs/1904.09056
- [55]Giovanni Cavallanti, Nicolo Cesa-Bianchi, and Claudio Gentile. Linear classification and selective sampling under low noise conditions. Advances in neural information processing systems, 21, 2008.
- [56]Muhammad Elh Chowdhury, Tawsifur Rahman, Amit Khandakar, Rashid Mazhar, Muhammad Abdul Kadir, Zaid Bin Mahbub, Khandakar Reajul Islam, Muhammad Salman Khan, Atif Iqbal, Nasser Al Emadi, et al. Can ai help in screening viral and covid-19 pneumonia? Ieee Access, 8:132665–132676, 2020.DOI
- [57]Tawsifur Rahman, Amith Khandakar, Yazan Qiblawey, Anas Tahir, Serkan Kiranyaz, Saad Bin Abul Kashem, Mohammad Tariqul Islam, Somaya Al Maadeed, Susu M Zuhagier, Muhammad Salman Khan, et al. Exploring the effect of image enhancement techniques on covid-19 detection using chest x-ray images. Computers in biology and medicine, 132:104319, 2021.DOI
- [58]Sebastian Goldt, Marc Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Physical Review X, 10(4):041044, 2020.DOI
- [60]Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.pubmed.ncbi.nlm.nih.gov/13602029
- [61]Claire Monteleoni and Matti Kaariaiainen. Practical online active learning for classification. In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2007.DOI
- [62]F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011.arxiv.org/abs/1201.0490
- [63]Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17, 2004.









