betaFeedback

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 dd of the samples is comparable to the total number nn 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 nn unlabeled samples, under a total query budget γn\gamma n, with γ∈(0,1]\gamma\in(0, 1]. 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 Δ>0\Delta> 0. 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 Δ\Delta.

  • 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.

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 O~(dlog⁡1/ϵ)\widetilde{O}(d\log1/\epsilon) label complexity required to reach accuracy 1−ϵ1-\epsilon. The present work complements these results in the high-dimensional Gaussian setting, and investigates, given a number nn of unlabeled instances and a query budget γn\gamma n, 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 Δ\Delta, 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 d≫1d \gg1 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 n≃dn \simeq d 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 nn unlabeled samples (xi)i∈[n](x_i)_{i \in[n]}, drawn i.i.d. from a dd-dimensional Gaussian distribution N(0d,Id/d)\mathcal{N}(0_d, I_d/d), is sequentially observed by the learner. At each round i∈[n]i \in[n], the learner can

  • Query an expert to annotate the sample, thereby obtaining the associated label yiy_i. We consider the realizable setting, where there exists an (unknown) ground truth vector β∈Rd\beta\in\mathbb{R}^d with ∥β∥2=d\lVert\beta\rVert^2=d that perfectly separates the data, namely yj=sign⁡(⟨β,xj⟩)y_j = \operatorname{sign}(\langle\beta,x_j\rangle) for all j∈[n]j \in[n]. With the full covariate-label pair (xi,yi)(x_i,y_i) now available, the learner may then perform a gradient update on the weights wiw_i of a linear classifier

wi+1=wi−ηℓ′(⟨wi,xi⟩yi)yixi,(1)w_{i+1}=w_i-\eta\ell'(\langle w_i,x_i\rangle y_i)y_ix_i, \tag*{(1)}

with learning rate η>0\eta> 0 and loss ℓ:R→R+\ell:\mathbb{R}\to\mathbb{R}_+. 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 sign⁡(⟨wi,xi⟩)\operatorname{sign}(\langle w_i,x_i\rangle) for the unknown label yiy_i of sample xix_i, at the risk of making a mistake whenever sign⁡(⟨wi,xi⟩)≠yi\operatorname{sign}(\langle w_i,x_i\rangle)\ne y_i.

In line with prior works on active binary classification [15, 4, 9, 46], we focus on the 00-threshold squared hinge loss ℓ(z)=12min⁡(z,0)2\ell(z)=\frac{1}{2}\min(z,0)^2, 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 1/i1/i 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 i∈[n]i \in[n], the choice of the learner can be encoded by a binary variable σi∈{0,1}\sigma_i \in\{0,1\}, with the learner choosing to query the label (resp. issue a prediction) if and only if σi=1\sigma_i=1 (resp. σi=0\sigma_i=0). In the case of linear classifiers, it is natural to base this choice on the margin (output) ⟨wi,xi⟩\langle w_i,x_i\rangle of the model for the running sample xix_i. We thus model σi\sigma_i as a Bernoulli variable of law B(pi(⟨wi,xi⟩))\mathcal{B}(p_i(\langle w_i,x_i\rangle)), where the sequence (pi)i∈[n](p_i)_{i\in[n]} of functions pi:R→[0,1]p_i:\mathbb{R}\to[0,1] 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 pip_i takes values in {0,1}\{0,1\}. A particularly well-known instance of such deterministic rules are hard inner-margin rules pi(⋅)=1[∣⋅∣≤κ]p_i(\cdot)=\mathbb{1}[\lvert\cdot\rvert\le\kappa] [47, 48], which prescribe to label samples whenever they fall within a certain distance κ\kappa 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 πi(⋅)\pi_i(\cdot). 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

εg,i=P[⟨wi,x⟩y<0],(2)\varepsilon_{g,i} = \mathbb{P}\left[\langle w_i,x\rangle y < 0\right], \tag*{(2)}

at the final round i=ni=n. In the above display, the probability bears over test samples x,yx,y from the same distribution as the stream of training samples. We investigate policies minimizing εg,n\varepsilon_{g,n} with a constraint on the total number QnQ_n of queried samples:

Qn≡∑i=1nσi=⌊γn⌋,(3)Q_n \equiv\sum_{i=1}^{n}\sigma_i = \lfloor\gamma n \rfloor, \tag*{(3)}

where γ∈(0,1]\gamma\in(0,1] 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 Δ\Delta, the cumulative cost at round kk is

Rk=1d(Mk+ΔQk).(4)R_k = \frac{1}{d}(M_k + \Delta Q_k). \tag*{(4)}

The cumulative number of queries QkQ_k is defined in (3) and the cumulative number of mistakes is given by

Mk=∑i=1k(1−σi)1[⟨wi,xi⟩yi<0].(5)M_k = \sum_{i=1}^{k}(1-\sigma_i)\mathbb{1}[\langle w_i,x_i\rangle y_i < 0]. \tag*{(5)}

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 pε,i∗p^{*}_{\varepsilon,i}, pR,i∗p^{*}_{R,i}, respectively minimizing the average error E[εg,n]\mathbb{E}[\varepsilon_{g,n}] under a labeling budget γ∈(0,1]\gamma\in(0,1] or the average total cumulative cost E[Rn]\mathbb{E}[R_n]. From prior works in online learning in the high-dimensional regime n≃dn \simeq d (Saad and Solla, 1995a,b; Goldt et al., 2019), one expects that for a given policy the random variables εg,n\varepsilon_{g,n} and RnR_n concentrate around their expectations as n,d→∞n,d \to\infty. 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 (t,ω)(t,\omega) plane for the final-error minimization. Colored regions indicate pt(⋅)=1p_t(\cdot)=1. The myopic rule pε,t∘(⋅)p^\circ_{\varepsilon,t}(\cdot) (8) is shown in blue. The horizon-optimized intermediate-margin schedule pε,t⋆(⋅)=1[at⋆≤∣⋅∣≤bt⋆]p^\star_{\varepsilon,t}(\cdot)=\mathbb{1}[a^\star_t\leq|\cdot|\leq b^\star_t] (9), with at⋆a^\star_t and bt⋆b^\star_t set to minimize the final error, is shown in yellow. Parameters: γ=0.4\gamma=0.4, η=0.5\eta=0.5, m0=0m_0=0, q0=0.15q_0=0.15, tF=20t_F=20. (right) Final generalization error εg,tF\varepsilon_{g,t_F} vs. query budget γ\gamma. Parameters: η=0.5\eta=0.5, m0=0m_0=0, q0=0.15q_0=0.15, tF=20t_F=20. Lines represent theoretical predictions while symbols mark single-trajectory SGD simulations at d=1000d=1000. 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 pε,iεp^{\varepsilon}_{\varepsilon,i} (resp. pR,iRp^{R}_{R,i}) minimizes E[εg,i+1−εg,i]\mathbb{E}[\varepsilon_{g,i+1}-\varepsilon_{g,i}] (resp. E[Ri+1−Ri]\mathbb{E}[R_{i+1}-R_i]), where the expectation bears on the sample (xi,yi)(x_i,y_i) and the query decision σi\sigma_i. 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 Δ>1/2\Delta> 1/2 a myopic learner never queries, since random-chance error is 1/2<Δ1/2 < \Delta. However, a strategy that minimizes the final cost RnR_n could in principle query even at Δ>1/2\Delta> 1/2. For simplicity, we focus on Δ<1/2\Delta< 1/2 throughout.

Closed-form description of the training dynamics

In the high-dimensional regime d≫1d \gg1, 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 wiw_i denote the weights of the learner after ii steps of the online SGD dynamics in (1). In the limit d,i→∞d,i \to\infty with t=i/d=Od(1)t=i/d=\mathcal{O}_d(1), the scalar summary statistics

mt=⟨wtd,β⟩d,qt=⟨wtd,wtd⟩dm_t = \frac{\langle w_{t d}, \beta\rangle}{d}, \qquad q_t = \frac{\langle w_{t d}, w_{t d}\rangle}{d}

concentrate in probability to the solution at time tt of the following deterministic ODEs

dmtdt=fm(mt,qt;pt),dqtdt=fq(mt,qt;pt),(6)\frac{\mathrm{d}m_t}{\mathrm{d}t}=f_m(m_t,q_t;p_t), \qquad\frac{\mathrm{d}q_t}{\mathrm{d}t}=f_q(m_t,q_t;p_t), \tag*{(6)}

where fmf_m and fqf_q are functions of mtm_t and qtq_t and functionals of the selection policy ptp_t. The expressions of fmf_m and fqf_q are given in Appendix § 11. We refer to tt as the training time and tF=n/dt_F=n/d as the time horizon.

Figure 5 in App. § 11 shows that this theoretical prediction matches a single instance of numerical simulations already at d=1000d=1000. The ODEs capture the time evolution of the squared norm qtq_t of the weights and their overlap mtm_t with the ground truth vector β\beta. 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 tt, e.g. Rt=RtdR_t=R_{td}.

Figure 5. Summary statistics mm and qq as a function of training time tt, for the constant policy pt(ω)=1∣ω∣<1p_t(\omega)=\mathbf{1}_{|\omega|<1}. Lines are obtained by numerically integrating the ODEs (6), while symbols mark numerical simulations of a single SGD trajectory at d=1000d=1000. Parameters: η=0.5\eta=0.5, m0=0m_0=0, q0=0.15q_0=0.15, tF=10t_F=10.

Remark 2.2. The cost metrics in Eq. (2) and (4) can be expressed as explicit functions of the summary statistics mtm_t and qtq_t. The generalization error is εg,t=1πarccos⁡(mtqt)\varepsilon_{g,t}=\frac{1}{\pi}\arccos\left(\frac{m_t}{\sqrt{q_t}}\right). Similarly, the cumulative cost RtR_t (4) can be expressed as a function of the summary statistics mt′m_{t'} and qt′q_{t'} for t′∈[0,t]t'\in[0,t], 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 ptp_t that minimize the final generalization error εg,tF\varepsilon_{g,t_F} over a given time-horizon tFt_F, subject to the following continuous-time constraint on the total number of queries (cf. Eq. (3))

1tF∫0tFE[pt(ωt)] dt=γ,(7)\frac{1}{t_F}\int_0^{t_F}\mathbb{E}[p_t(\omega_t)]\,\mathrm{d}t=\gamma, \tag*{(7)}

where E[⋅]\mathbb{E}[\cdot] is the expected value w.r.t. ωt∼N(0,qt)\omega_t\sim\mathcal{N}(0,q_t).

Myopic policy

As a first step, we investigate the myopic policy that greedily maximizes at each step the decrease in generalization error −dεg,t/dt-\mathrm{d}\varepsilon_{g,t}/\mathrm{d}t. This analysis will serve as a basis for designing the horizon-optimized policy that minimizes the terminal error εg,tF\varepsilon_{g,t_F}. 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 ν\nu, enforcing (7) (see App. § 12).

Result 3.1 (Myopic policy under query budget). The myopic policy is given by

pε,t∘(⋅)=1[St(⋅)+ν<0],p^\circ_{\varepsilon,t}(\cdot)=\mathbb{1}\left[S_t(\cdot)+\nu<0\right],

where St(⋅)S_t(\cdot) is given in Eq. (21) of App. § 12 and ν>0\nu>0 is chosen to enforce Eq. (7). For a wide range of parameters this results in the intermediate-margin policy

pε,t∘(⋅)=1[at≤∣⋅∣≤bt],(8)p^\circ_{\varepsilon,t}(\cdot)=\mathbb{1}\left[a_t\leq|\cdot|\leq b_t\right], \tag*{(8)}

where the threshold values ata_t and btb_t are the positive roots of St(ω)+ν=0S_t(\omega)+\nu=0 (see Figure 6).

Figure 6. Selection policies in the (t,ω)(t,\omega) plane for final-error (top row) and cumulative-cost (bottom row) minimization. The colored regions indicate pt(ω)=1p_t(\omega)=1. Parameters: η=0.5\eta=0.5, m0=0m_0=0, q0=0.15q_0=0.15, tF=20t_F=20.

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 ∣ω∣|\omega| 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 ∣ω∣|\omega| 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 pε,t⋆p_{\varepsilon,t}^{\star}

Motivated by the functional form of the myopic policy in Res. 3.1, we use control theory to identify the policy pε,t⋆p_{\varepsilon,t}^{\star} minimizing the final generalization error εg,tF\varepsilon_{g,t_F} 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

pε,t⋆(⋅)=1[at⋆≤∣⋅∣≤bt⋆],(9)p_{\varepsilon,t}^{\star}(\cdot) = \mathbb{1}[a_t^{\star} \leq|\cdot| \leq b_t^{\star}], \tag*{(9)}

where the optimal thresholding schedule is given by

(at⋆,bt⋆)=arg⁡min⁡{at,bt} εg,tF,subject to xref‘(7)‘.(10)(a_t^{\star},b_t^{\star}) = \underset{\{a_t,b_t\}}{\arg\min}\ \varepsilon_{g,t_F},\quad\text{subject to } {xref}`(7)`. \tag*{(10)}

The minimization in Eq. (10) bears on 0≤at≤bt0 \leq a_t \leq b_t for t∈[0,tF]t \in[0,t_F], resulting in the schedule in Figure 1.

Figure 1 (left) compares the myopic policy pε,t∘p_{\varepsilon,t}^{\circ} (8), in blue, with the horizon-optimized intermediate-margin policy pε,t⋆p_{\varepsilon,t}^{\star} (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 tFt_F.

Figure 1 (right) shows the final generalization error as a function of the query budget for pε,t∘p_{\varepsilon,t}^{\circ} and pε,t⋆p_{\varepsilon,t}^{\star}. As benchmarks, we include the (time and margin independent) random policy p=γp=\gamma, the constant intermediate-margin policy p(⋅)=1[a⋆≤∣⋅∣≤b⋆]p(\cdot)=\mathbb{1}[a^{\star}\leq|\cdot|\leq b^{\star}], and the inner-margin policy pt(⋅)=1[∣⋅∣≤κt⋆]p_t(\cdot)=\mathbb{1}[|\cdot|\leq\kappa_t^{\star}], with either a constant threshold κ⋆\kappa^{\star} or a schedule κt⋆\kappa_t^{\star}. All free parameters are optimized to minimize εg,tF\varepsilon_{g,t_F}. The optimal intermediate-margin schedule achieves the lowest final error, with the largest gains at small query budget γ\gamma. Even with constant thresholds, intermediate-margin selection outperforms constant and time-dependent inner-margin policies at small and moderate budgets γ\gamma. 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 RtF\mathcal{R}_{t_F} (4). We show that both the myopic policy and the horizon-optimized intermediate-margin policy are inner-margin rules. Indeed, samples with small ∣ω∣|\omega| 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 pR,t∘p_{\mathcal{R},t}^{\circ}

The following Result, derived in App. § 13, shows that the myopic policy pR,t∘p_{\mathcal{R},t}^{\circ} minimizing the instantaneous increase d/dtRt\mathrm{d}/\mathrm{d}t\mathcal{R}_t 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 pR,t∘p^\circ_{R,t} for the cumulative cost). The myopic policy pR,t∘p^\circ_{R,t} is given by

pR,t∘(⋅)=1[∣⋅∣≤κt∘],(11)p^\circ_{R,t}(\cdot)=\mathbb{1}[|\cdot|\le\kappa_t^\circ], \tag*{(11)}

where the margin κt∘\kappa_t^\circ reads

κt∘=qt∘2(qt∘/(mt∘)2−1)∣erf⁡−1(2Δ−1)∣,\kappa_t^\circ=\sqrt{q_t^\circ}\sqrt{2(q_t^\circ/(m_t^\circ)^2-1)}\left|\operatorname{erf}^{-1}(2\Delta-1)\right|,

with qt∘,mt∘q_t^\circ,m_t^\circ satisfying self-consistently the equations (6) with policy pt=pR,t∘p_t=p^\circ_{R,t}. As t→∞t\to\infty, for η=2\eta=2, the threshold κt∘\kappa_t^\circ shrinks asymptotically as

κt∘=q0 c(Δ)t+o(1t),(12)\kappa_t^\circ=\frac{\sqrt{q_0}\,c(\Delta)}{t}+o\left(\frac{1}{t}\right), \tag*{(12)}

where c(Δ)>0c(\Delta)>0 is given in Eq. (26) in App. § 13.

As in § 5, we find a deterministic policy because the instantaneous objective is linear in ptp_t. 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 pR,t∘p^\circ_{R,t} characterized in Result 4.1, for η=2\eta=2, the cumulative cost Rt∘R_t^\circ, number of mistakes Mt∘M_t^\circ and number of queries Qt∘Q_t^\circ scale logarithmically with training time:

Rt∘,Mt∘,Qt∘≍ln⁡t.R_t^\circ,M_t^\circ,Q_t^\circ\asymp\ln t.

The error scales as εg,t∘≍1/t\varepsilon_{g,t}^\circ\asymp1/t, and thus decays exponentially with the number of queries Qt∘Q_t^\circ. These scalings match for example those reported in [19, 54, 55].

Horizon-optimized intermediate-margin policy

We now turn to the horizon-optimized policy pR,t⋆p^{\star}_{\mathcal{R},t} 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

pR,t⋆(⋅)=1[at⋆≤∣⋅∣≤bt⋆],p^{\star}_{\mathcal{R},t}(\cdot) = \mathbf{1}[a^{\star}_t \leq|\cdot| \leq b^{\star}_t],

where the optimal thresholding schedule is given by

(at⋆,bt⋆)=argmin⁡{at,bt}RtF.(a^{\star}_t,b^{\star}_t) = \operatorname*{argmin}_{\{a_t,b_t\}} \mathcal{R}_{t_F}.

For all parameter values considered, we obtain at⋆=0a^{\star}_t = 0, 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 (t,ω)(t,\omega) plane for cumulative-cost minimization. Colored regions indicate pt(⋅)=1p_t(\cdot)=1. The myopic rule pR,t∘(⋅)p^\circ_{R,t}(\cdot), greedily maximizing the cost decrease at each time, is shown in blue. The horizon-optimized inner-margin schedule pR,t⋆(⋅)=1[∣⋅∣≤bt]p^\star_{R,t}(\cdot)=\mathbb{1}[|\cdot|\le b_t], with btb_t set to minimize the final cumulative cost, is shown in yellow. Parameters: Δ=0.3\Delta=0.3, η=0.5\eta=0.5, m0=0m_0=0, q0=0.15q_0=0.15, tF=20t_F=20. (right) Cumulative cost RtFR_{t_F} vs. the query price Δ\Delta. Parameters: η=0.5\eta=0.5, m0=0m_0=0, q0=0.15q_0=0.15, tF=20t_F=20. Lines represent theoretical predictions while symbols mark single-trajectory SGD simulations at d=1000d=1000. 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 pt(⋅)=pp_t(\cdot) = p and all constant strategies. All free parameters, including pp, are chosen to minimize RtF\mathcal{R}_{t_F}. The horizon-optimized schedule outperforms the myopic one, with a gap growing with Δ\Delta. The myopic rule queries only when it lowers the cost immediately, ignoring that each query also reduces future mistakes. At large Δ\Delta 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 pt(⋅)=1[∣⋅∣≤K/t]p_t(\cdot)=\mathbb{1}[|\cdot|\le K/t], with a threshold shrinking at a 1/t1/t 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 pt(⋅)p_t(\cdot). 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 pt(⋅)=1[∣⋅∣≤κt]p_t(\cdot)=\mathbb{1}[|\cdot|\le\kappa_t] 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 RtR_t for these different policies, presenting only the choice of hyperparameter that minimizes in hindsight the terminal cost RtFR_{t_F}. The heuristic pt(⋅)=1[∣⋅∣≤K/t]p_t(\cdot)=\mathbb{1}[|\cdot|\le K/t] inspired from the t→∞t\to\infty asymptotics of Result 4.1 –brown lines in Figure 3– compares favorably against the aforementioned baselines, and results in overall small cumulative cost RtR_t. The performance for the particular prescription K∘=q0 c(Δ)K^\circ=\sqrt{q_0}\,c(\Delta) for the hyperparameter KK, which can be read from the theoretical expression (12), is on the other hand found to deteriorate at larger costs Δ\Delta, as illustrated in Figure 7 and Figure 9 in App. D.

Figure 3. Cumulative cost Rt\mathcal{R}_t and number of queries Qt\mathcal{Q}_t versus mistakes Mt\mathcal{M}_t (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 d=200d = 200 (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 K/tK/t threshold, with tunable bandwidth KK. The query cost was set to Δ=0.2\Delta= 0.2. Hyperparameters were tuned in hindsight to minimize RtF\mathcal{R}_{t_F}, among a grid of 50 values. The black curve represents the simple thresholding strategy pt∘(⋅)=1[∣⋅∣≤K∘/t]p_t^{\circ}(\cdot) = \mathbf{1}[|\cdot| \leq K^{\circ}/t], where K∘≈2.52K^{\circ} \approx2.52 is the asymptotically optimal value prescribed by (12) for q0=0.1q_0 = 0.1, η=2\eta= 2, Δ=0.2\Delta= 0.2. Shades mark one standard deviation over 5 trials, with the dataset reshuffled at each run.

Figure 7. Same as Figure 3 (right), for Δ=0.1\Delta=0.1, 0.40.4.

Figure 9. Same as Figure 3 (left), for Δ=0.1,0.4\Delta= 0.1, 0.4.

This observation stands in coherence with the discussion of the previous subsection that the performance of the myopic policy comparatively degrades at larger Δ\Delta, see Figure 2 (right). A finer examination of the joint evolution of MtM_t, QtQ_t (Figure 3, inset) reveals that the shrinking threshold K/tK/t incentivizes a first phase of exploration, with a sharp increase of the number of queries QtQ_t, followed by a phase of exploitation where the model attempts more predictions, as signaled by a sharp increase in mistakes MtM_t. 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 Δ=0.2\Delta=0.2, 0.40.4.

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 RtR_t (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-rr two-layer neural network f(⋅)=v⊤g(W⋅)f(\cdot)=v^\top g(W\cdot) with weights v∈Rrv\in\mathbb{R}^r, W∈Rr×dW\in\mathbb{R}^{r\times d}, and activation function gg acting entry-wise. We again consider training this model on the classification task described in § 3, using online SGD (1). Note that when r=Θd(1)r=\Theta_d(1) as n≍dn\asymp d 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 pt:Rr→[0,1]p_t : \mathbb{R}^r \to[0,1] that take as argument for a given input xx the whole array of pre-activations WxWx, rather than the sole output f(x)f(x). 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 f(x)f(x)? The next Result, derived in App. § 13, answers this question negatively.

Result 4.4 (Myopic policy for two-layer networks). Conditional on the weights v,Wv, W at time tt, supposing WW is full rank and β∉rowsp⁡(W)\beta\notin\operatorname{rowsp}(W), the myopic policy for the cumulative cost at time tt is given by

pR,t∘(⋅)=1[Φ(−sign⁡(vTg(⋅))MTQ−11−MTQ−1M)≥Δ],(13)p_{\mathcal{R},t}^{\circ}(\cdot) = \mathbb{1}\left[\Phi\left(\frac{-\operatorname{sign}(v^{\mathsf{T}}g(\cdot))M^{\mathsf{T}}Q^{-1}}{\sqrt{1-M^{\mathsf{T}}Q^{-1}M}}\right) \ge\Delta\right], \tag*{(13)}

where M:=Wβ/d∈RrM := W\beta/d \in\mathbb{R}^r and Q:=WWT/d∈Rr×rQ := WW^{\mathsf{T}}/d \in\mathbb{R}^{r \times r}. Φ(⋅)\Phi(\cdot) is the normal cumulative distribution function.

While the optimal policy is still found to be deterministic, it no longer depends on the pre-activation WxWx through the sole output vTg(Wx)v^{\mathsf{T}}g(Wx). 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 1[∣vTg(⋅)∣≤κ]\mathbb{1}[|v^{\mathsf{T}}g(\cdot)| \le\kappa]. Figure 4 shows, for a g=GeLU⁡g = \operatorname{GeLU} network with r=2r = 2 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 WxWx selected by the myopic policy pR,t∘p^\circ_{R,t} (13) (blue) for Δ=0.46\Delta=0.46 and a naive inner-margin threshold on the network output pt(⋅)=1[∣v⊤g(⋅)∣≤0.35]p_t(\cdot)=\mathbb{1}[|v^\top g(\cdot)|\le0.35] (yellow). The weights WW in (13) were extracted from a GeLU-activated two-layer neural network with r=2r=2 hidden neurons, trained without data selection on the logistic loss for 1000 steps, at d=500d=500 and η=1\eta=1. The untrained readout is v=(1,1)⊤v=(1,1)^\top. 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) ∣⟨wi,xi⟩∣|\langle w_i, x_i\rangle|. 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 mm and qq given in Eq. (6) of the main text, tracking the learning dynamics of online SGD:

wi+1=wi−ησiℓ′(⟨wi,xi⟩yi)yixi,(14)w_{i+1}=w_i-\eta\sigma_i\ell'\left(\langle w_i,x_i\rangle y_i\right)y_i x_i, \tag*{(14)}

with learning rate η>0\eta>0. The teacher β∈Rd\beta\in\mathbb{R}^d is fixed throughout the training, with ∥β∥22=d\lVert\beta\rVert_2^2=d, and the labels are yi=sign⁡(⟨β,xi⟩)y_i=\operatorname{sign}(\langle\beta,x_i\rangle). At each step ii, the selection process is encoded by the Bernoulli variable σi∼B(pi(⟨wi,xi⟩))\sigma_i\sim\mathcal{B}(p_i(\langle w_i,x_i\rangle)). In the following, we will consider differentiable losses ℓ:R→R+\ell:\mathbb{R}\to\mathbb{R}_+ of the signed margin, highlighting the Adatron rule with ℓ(z)=12min⁡(z,0)2\ell(z)=\frac{1}{2}\min(z,0)^2 as a special case.

In the online setup, at each step ii a fresh sample xi∼N(0d,Id/d)x_i\sim\mathcal{N}(0_d,I_d/d) is considered, independent of the weights wiw_i. Therefore, conditional on wiw_i, the margins (ωi∗,ωi)=(⟨β,xi⟩,⟨wi,xi⟩)(\omega_i^*,\omega_i)=(\langle\beta,x_i\rangle,\langle w_i,x_i\rangle) are also jointly Gaussian with zero mean and second moments given by:

E[(ωi∗)2]=⟨β,β⟩d=1,E[ωi2]=⟨wi,wi⟩d=:qi,E[ωi∗ωi]=⟨β,wi⟩d=:mi,(15)\mathbb{E}\left[(\omega_i^*)^2\right]=\frac{\langle\beta,\beta\rangle}{d}=1,\qquad \mathbb{E}\left[\omega_i^2\right]=\frac{\langle w_i,w_i\rangle}{d}=:q_i,\qquad \mathbb{E}\left[\omega_i^*\omega_i\right]=\frac{\langle\beta,w_i\rangle}{d}=:m_i, \tag*{(15)}

where the expectations are over xix_i, conditional on wiw_i. We have defined the order parameters mim_i (alignment with the teacher) and qiq_i (squared norm of the weights), which fully determine the joint conditional margin distribution

(ω∗,ω)∼N([00],[1mmq]).(\omega^*,\omega)\sim\mathcal{N}\left( \begin{bmatrix}0\\0\end{bmatrix}, \begin{bmatrix}1&m\\m&q\end{bmatrix} \right).

The generalization error depends on the weights only through the margins (ω∗,ω)(\omega^*,\omega) and can thus be expressed solely in terms of the correlation coefficient m/qm/\sqrt{q}

εg=P[ωω∗<0]=1πarccos⁡(mq).(16)\varepsilon_g=\mathbb{P}[\omega\omega^*<0]=\frac{1}{\pi}\arccos\left(\frac{m}{\sqrt{q}}\right). \tag*{(16)}

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

mi+1−mi=−ηdσiℓ′(ωiyi)yiωi∗,qi+1−qi=−2ηdσiℓ′(ωiyi)yiωi+η2dσi(ℓ′(ωiyi))2⟨xi,xi⟩,(17)m_{i+1}-m_i=-\frac{\eta}{d}\sigma_i\ell'(\omega_i y_i)y_i\omega_i^*,\qquad q_{i+1}-q_i=-\frac{2\eta}{d}\sigma_i\ell'(\omega_i y_i)y_i\omega_i+\frac{\eta^2}{d}\sigma_i(\ell'(\omega_i y_i))^2\langle x_i,x_i\rangle, \tag*{(17)}

where we have used that σi∈{0,1}\sigma_i\in\{0,1\}, hence σi2=σi\sigma_i^2=\sigma_i. The quadratic term in the increment of qq must be retained, since it contributes at the same order in 1/d1/d as the linear term.

We take the proportional infinite-dimensional limit d,n→∞d,n\to\infty with tF=n/dt_F=n/d fixed and consider the macroscopic time t=i/d∈[0,tF]t=i/d\in[0,t_F], where each increment is of order dt=1/d\mathrm{d}t=1/d. The learning rate η\eta is also held fixed. The input norm satisfies E[⟨xi,xi⟩]=1\mathbb{E}[\langle x_i,x_i\rangle]=1 and Var⁡(⟨xi,xi⟩)=2/d\operatorname{Var}(\langle x_i,x_i\rangle)=2/d, and hence it converges in probability:

⟨xi,xi⟩→d→∞P1.\langle x_i,x_i\rangle\xrightarrow[d\to\infty]{\mathbb{P}}1.

For an isotropic Gaussian initialization w0∼N(0,qinitId)w_0\sim\mathcal{N}(0,q_{\mathrm{init}}I_d) independent of the teacher, the initial order parameters also concentrate as d→∞d\to\infty. Indeed, averaging over the initialization and using ∥β∥2=d\lVert\beta\rVert^2=d,

E[m0]=0,Var⁡(m0)=qinitd,E[q0]=qinit,Var⁡(q0)=2qinit2d.\mathbb{E}[m_0]=0,\qquad\operatorname{Var}(m_0)=\frac{q_{\mathrm{init}}}{d},\qquad\mathbb{E}[q_0]=q_{\mathrm{init}},\qquad\operatorname{Var}(q_0)=\frac{2q_{\mathrm{init}}^2}{d}.

Consequently, (m0,q0)→d→∞P(0,qinit)(m_0,q_0)\xrightarrow[d\to\infty]{\mathbb{P}}(0,q_{\mathrm{init}}), providing deterministic initial conditions for the limiting dynamics.

To control the increments during training, we consider losses that satisfy ∣ℓ′(z)∣≤C(1+∣z∣)|\ell'(z)|\le C(1+|z|) for all z∈Rz\in\mathbb{R}, with a finite constant C>0C>0 independent of zz and dd. This encompasses squared hinge, square, and logistic losses. The increments in Eq. (17) scale as d−1d^{-1}. Over i=dti=dt steps at fixed tt, their conditional means generate a finite drift, while the centered fluctuations are uncorrelated across steps and have cumulative standard deviation of order d−1/2d^{-1/2}, vanishing as d→∞d\to\infty. Here, conditioning is on the training history before step ii, and the averages are over the fresh input xix_i and query decision σi\sigma_i.

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 σi\sigma_i replaces it by pi(ωi)p_i(\omega_i), while input-norm concentration allows to replace ⟨xi,xi⟩\langle x_i,x_i\rangle by one. Dividing the resulting mean increments by dt=1/d\mathrm{d}t=1/d, the order parameters dynamics (17) concentrate in probability to their deterministic limit

dmdt=fm(mt,qt;pt)=−ηE[pt(ω)ℓ′(ωy)yω∗],dqdt=fq(mt,qt;pt)=−2ηE[pt(ω)ℓ′(ωy)yω]+η2E[pt(ω)(ℓ′(ωy))2].(18)\begin{aligned} \frac{\mathrm{d}m}{\mathrm{d}t}&=f_m(m_t,q_t;p_t)=-\eta\mathbb{E}\left[p_t(\omega)\ell'(\omega y)y\omega^*\right],\\ \frac{\mathrm{d}q}{\mathrm{d}t}&=f_q(m_t,q_t;p_t)=-2\eta\mathbb{E}\left[p_t(\omega)\ell'(\omega y)y\omega\right]+\eta^2\mathbb{E}\left[p_t(\omega)(\ell'(\omega y))^2\right]. \tag*{(18)} \end{aligned}

At a fixed training time tt, we write m=mtm=m_t and q=qtq=q_t. Since the policy depends only on the margin ω\omega, it is convenient to first average over the conditional teacher margin ω∗∣ω∼N(μ,s2)\omega^*\mid\omega\sim\mathcal{N}(\mu,s^2), where μ=(m/q)ω\mu=(m/q)\omega and s=1−m2/qs=\sqrt{1-m^2/q}. Denoting the standard normal density (resp. cumulative distribution function) as GG (resp. Φ\Phi), the marginal density of ω\omega as PqP_q, and its standardized conditional mean as ζ\zeta,

G(x)=e−x2/22π,Φ(x)=∫−∞xG(u) du,Pq(ω)=e−ω2/(2q)2πq,ζ=μs=mωq(q−m2),G(x)=\frac{e^{-x^2/2}}{\sqrt{2\pi}},\qquad\Phi(x)=\int_{-\infty}^{x}G(u)\,\mathrm{d}u,\qquad P_q(\omega)=\frac{e^{-\omega^2/(2q)}}{\sqrt{2\pi q}},\qquad\zeta=\frac{\mu}{s}=\frac{m\omega}{\sqrt{q(q-m^2)}},

the three moments appearing in Eq. (18) are given by

E[(ℓ′(ωy))2∣ω]=Φ(ζ)ℓ′(ω)2+Φ(−ζ)ℓ′(−ω)2,E[ℓ′(ωy)yω∣ω]=ω[Φ(ζ)ℓ′(ω)−Φ(−ζ)ℓ′(−ω)],E[ℓ′(ωy)yω∗∣ω]=ℓ′(ω)(μΦ(ζ)+sG(ζ))−ℓ′(−ω)(μΦ(−ζ)−sG(ζ)).(19)\begin{aligned} \mathbb{E}\left[(\ell'(\omega y))^2\mid\omega\right]&=\Phi(\zeta)\ell'(\omega)^2+\Phi(-\zeta)\ell'(-\omega)^2,\\ \mathbb{E}\left[\ell'(\omega y)y\omega\mid\omega\right]&=\omega\left[\Phi(\zeta)\ell'(\omega)-\Phi(-\zeta)\ell'(-\omega)\right],\\ \mathbb{E}\left[\ell'(\omega y)y\omega^*\mid\omega\right]&=\ell'(\omega)\left(\mu\Phi(\zeta)+sG(\zeta)\right)-\ell'(-\omega)\left(\mu\Phi(-\zeta)-sG(\zeta)\right). \tag*{(19)} \end{aligned}

For any function h(ω,ω∗)h(\omega,\omega^*), the corresponding term in (18) factorizes as

E[pt(ω)h(ω,ω∗)]=∫−∞∞dω Pq(ω)pt(ω)E[h(ω,ω∗)∣ω].\mathbb{E}\left[p_t(\omega)h(\omega,\omega^*)\right]=\int_{-\infty}^{\infty}\mathrm{d}\omega\,P_q(\omega)p_t(\omega)\mathbb{E}\left[h(\omega,\omega^*)\mid\omega\right].

All three moments in (19) are even in ω\omega, so every policy that we derive in the following can be written as a condition on ∣ω∣|\omega| alone.

For the Adatron rule, ℓ′(z)=min⁡(z,0)\ell'(z)=\min(z,0), so yℓ′(ωy)=ω1{ωω∗<0}y\ell'(\omega y)=\omega\mathbf{1}_{\{\omega\omega^*<0\}} and (ℓ′(ωy))2=ω21{ωω∗<0}(\ell'(\omega y))^2=\omega^2\mathbf{1}_{\{\omega\omega^*<0\}}. Each nonzero update increases the overlap mm, therefore, starting from m0=0m_0=0, we have m≥0m\geq0 nondecreasing throughout training. Using the conditional misclassification probability P[ωω∗<0∣ω]=Φ(−∣ζ∣)\mathbb{P}[\omega\omega^*<0\mid\omega]=\Phi(-|\zeta|) for ω≠0\omega\neq0, Eq. (18) becomes

fm(mt,qt;pt)=η∫−∞∞dω Pqt(ω)pt(ω)[st∣ω∣G(ζt)−mtqtω2Φ(−∣ζt∣)],fq(mt,qt;pt)=η(η−2)∫−∞∞dω Pqt(ω)pt(ω)ω2Φ(−∣ζt∣).(20)\begin{aligned} f_m(m_t,q_t;p_t) &= \eta\int_{-\infty}^{\infty} \mathrm{d}\omega\,P_{q_t}(\omega)p_t(\omega)\left[s_t|\omega|G(\zeta_t)-\frac{m_t}{q_t}\omega^2\Phi(-|\zeta_t|)\right],\\ f_q(m_t,q_t;p_t) &= \eta(\eta-2)\int_{-\infty}^{\infty} \mathrm{d}\omega\,P_{q_t}(\omega)p_t(\omega)\omega^2\Phi(-|\zeta_t|). \tag*{(20)} \end{aligned}

The self-overlap qtq_t is nonincreasing for 0<η<20<\eta<2 and remains constant for η=2\eta=2 in the limiting dynamics.

Figure 5 compares the ODE predictions (20) with numerical simulations of a single SGD trajectory at d=1000d=1000 under the fixed policy pt(ω)=1{∣ω∣<1}p_t(\omega)=\mathbf{1}_{\{|\omega|<1\}}. During training, the overlap mtm_t increases while the normalized squared weight norm qtq_t decreases, increasing their correlation mt/qtm_t/\sqrt{q_t} 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 Rk=(Mk+ΔQk)/d\mathcal{R}_k=(\mathcal{M}_k+\Delta Q_k)/d (see Eq. (4) of the main text) by averaging its one-step increments over the fresh input xix_i and query decision σi\sigma_i, conditional on the training history before step ii. We recall that Qk=∑i=1kσiQ_k=\sum_{i=1}^{k}\sigma_i denotes the cumulative number of queries, and Mk=∑i=1k(1−σi)1[ωiyi<0]\mathcal{M}_k=\sum_{i=1}^{k}(1-\sigma_i)\mathbf{1}_{[\omega_i y_i<0]} the cumulative number of mistakes. Since dd samples arrive per unit of macroscopic time, with a slight abuse of notation here we denote by QtQ_t and Mt\mathcal{M}_t the deterministic limits of Qk/dQ_k/d, Mk/d\mathcal{M}_k/d at k=⌊dt⌋k=\lfloor dt\rfloor, while Rt=R⌊dt⌋\mathcal{R}_t=\mathcal{R}_{\lfloor dt\rfloor} as in the main text. Their time evolution is given by

Qt=∫0tdt′∫−∞∞dω Pqt′(ω)pt′(ω),Q_t=\int_0^t\mathrm{d}t'\int_{-\infty}^{\infty}\mathrm{d}\omega\,P_{q_{t'}}(\omega)p_{t'}(\omega),
Mt=∫0tdt′∫−∞∞dω Pqt′(ω)[1−pt′(ω)]Φ(−∣ζt′∣),\mathcal{M}_t=\int_0^t\mathrm{d}t'\int_{-\infty}^{\infty}\mathrm{d}\omega\,P_{q_{t'}}(\omega)[1-p_{t'}(\omega)]\Phi(-|\zeta_{t'}|),
Rt=Mt+ΔQt.\mathcal{R}_t=\mathcal{M}_t+\Delta Q_t.

The constraint that a fraction γ\gamma of the samples is queried becomes

QtFtF=1tF∫0tFdt∫−∞∞dω Pqt(ω)pt(ω)=γ.\frac{Q_{t_F}}{t_F}=\frac{1}{t_F}\int_0^{t_F}\mathrm{d}t\int_{-\infty}^{\infty}\mathrm{d}\omega\,P_{q_t}(\omega)p_t(\omega)=\gamma.

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 (mt,qt)(m_t,q_t), the control is the policy ptp_t, and the objective is either the final error εg,tF\varepsilon_{g,t_F} under the budget (7), or the cumulative cost RtF\mathcal{R}_{t_F}. 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 fmf_m and fqf_q are linear in ptp_t, so the rate of change of the error is linear in ptp_t as well. We can write it as

dεgdt=E[pt(ω)St(ω)],St(ω)=∂εg∂m∂fm∂pt(ω)+∂εg∂q∂fq∂pt(ω).(21)\frac{\mathrm{d}\varepsilon_g}{\mathrm{d}t}=\mathbb{E}\left[p_t(\omega)S_t(\omega)\right],\qquad S_t(\omega)=\frac{\partial\varepsilon_g}{\partial m}\frac{\partial f_m}{\partial p_t(\omega)}+\frac{\partial\varepsilon_g}{\partial q}\frac{\partial f_q}{\partial p_t(\omega)}. \tag*{(21)}

where ∂εg/∂m=−1/(πq−m2)\partial\varepsilon_g/\partial m=-1/(\pi\sqrt{q-m^2}) and ∂εg/∂q=m/(2πqq−m2)\partial\varepsilon_g/\partial q=m/(2\pi q\sqrt{q-m^2}) follow from (16). We recall that E\mathbb{E} denotes the expected value with respect to ω∼N(0,q)\omega\sim\mathcal{N}(0,q). The function St(ω)S_t(\omega) measures how much querying a sample at margin ω\omega changes dεg/dtd\varepsilon_g/dt. Samples with St(ω)<0S_t(\omega)<0 reduce the error, and the others do not. A greedy policy that minimizes (21) at each time would therefore query every ω\omega with St(ω)<0S_t(\omega)<0. For the Adatron rule, however, StS_t is negative for all ω>0\omega>0. The greedy policy then queries every sample and violates the budget (7).

To enforce the budget, we introduce a Lagrange multiplier ν≥0\nu\geq0. This is a single scalar for the whole trajectory, and it acts as a fixed price per query. The instantaneous objective E[pt(ω)(St(ω)+ν)]\mathbb{E}[p_t(\omega)(S_t(\omega)+\nu)] is linear in ptp_t. Therefore, optimizing over arbitrary selection probabilities yields a deterministic myopic schedule almost surely: a sample at margin ω\omega is queried only if St(ω)+ν<0S_t(\omega)+\nu<0, that is, only if the error reduction it brings outweighs the price of the query, giving the policy of Result 3.1. We tune ν\nu by bisection so that the realized query rate equals γ\gamma.

Quadrature on the selected intervals

All the policies we consider select a union of intervals in ∣ω∣|\omega|, and the integrands in fmf_m and fqf_q are even in ω\omega. For an intermediate-margin policy pt(ω)=1[at≤∣ω∣≤bt]p_t(\omega)=\mathbb{1}[a_t\leq|\omega|\leq b_t], every expectation is therefore an ordinary integral over the selected interval:

E[pt(ω)X(ω)]=2∫atbtdω Pq(ω)X(ω),Pq(ω)=e−ω2/2q2πq.\mathbb{E}[p_t(\omega)X(\omega)] = 2\int_{a_t}^{b_t} \mathrm{d}\omega\,P_q(\omega)X(\omega), \qquad P_q(\omega)=\frac{e^{-\omega^2/2q}}{\sqrt{2\pi q}}.

where XX stands for any of the conditional moments of App. A. We compute these integrals with an nn-point Gauss–Legendre rule, rescaled from [−1,1][-1,1] to [at,bt][a_t,b_t]:

ωj=at+bt2+bt−at2ξj,E[pt(ω)X(ω)]≃(bt−at)∑j=1nWjPq(ωj)X(ωj),(22)\omega_j=\frac{a_t+b_t}{2}+\frac{b_t-a_t}{2}\xi_j,\qquad\mathbb{E}[p_t(\omega)X(\omega)]\simeq(b_t-a_t)\sum_{j=1}^{n}W_jP_q(\omega_j)X(\omega_j), \tag*{(22)}
StrategyPolicy pt(ω)p_t(\omega)Variables optimized (Fig. 1)Variables optimized (Fig. 2)
Myopic1[St(ω)+ν<0]\mathbf{1}[S_t(\omega)+\nu<0]one scalar ν\nu, so that the query rate equals γ\gammanothing
Inner margin, constant1[∣ω∣≤κ]\mathbf{1}[|\omega|\le\kappa]nothing: the budget fixes κ\kappaone scalar κ\kappa
Inner margin, schedule1[∣ω∣≤κt]\mathbf{1}[|\omega|\le\kappa_t]time-dependent κt\kappa_ttime-dependent κt\kappa_t
Intermediate margin, constant1[a≤∣ω∣≤b]\mathbf{1}[a\le|\omega|\le b]one scalar aa, with bb fixed by the budget at each aatwo scalars a,ba,b
Intermediate margin, schedule1[at≤∣ω∣≤bt]\mathbf{1}[a_t\le|\omega|\le b_t]time-dependent ata_t and btb_ttime-dependent ata_t and btb_t
Randompp, independent of ω\omega and ttnothing: the budget forces p=γp=\gammaone scalar pp

caption: Policy families compared in Figs. 1 (right) and 2 (right).

:::

where {ξj}\{\xi_j\} and {Wj}\{W_j\} are the standard Gauss–Legendre nodes and weights on [−1,1][-1,1]. This choice has two advantages. First, it is very accurate. The integrand PqtXP_{q_t}X is analytic on [at,bt][a_t,b_t], so the quadrature error decreases geometrically with nn and we use n=48n=48. Second, and more importantly, it makes the discretized ODE in Eq. (22) differentiable with respect to the policy parameter ata_t and btb_t.

Piecewise-constant schedules

For simplicity, we approximate the schedules to be piecewise constant in time. We split the horizon into NcN_c equal blocks and keep the radii fixed within each block:

at=ak,bt=bkfor t∈[(k−1)tFNc,ktFNc),k=1,…,Nc.a_t=a_k,\quad b_t=b_k \quad\text{for } t\in\left[\frac{(k-1)t_F}{N_c},\frac{kt_F}{N_c}\right),\quad k=1,\ldots,N_c.

The control is then a vector of 2Nc2N_c numbers, or NcN_c numbers for inner-margin policies, where ak≡0a_k\equiv0. We integrate the ODEs (6) with forward Euler on NsN_s time steps, with NsN_s a multiple of NcN_c. The time integrals in (7) and in RtFR_{t_F} are computed with the trapezoidal rule on the same grid. During optimization we use Nc=50N_c=50 and Ns=500N_s=500. All reported quantities are then recomputed with Ns=2000N_s=2000.

Enforcing the query budget

During optimization, we impose the budget (7) through a quadratic penalty:

L=εg,tF+ρ(1tF∫0tFE[pt(ω)] dt−γ)2,ρ=300.\mathcal{L}=\varepsilon_{g,t_F}+\rho\left(\frac{1}{t_F}\int_0^{t_F}\mathbb{E}[p_t(\omega)]\,\mathrm{d}t-\gamma\right)^2,\qquad\rho=300.

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 ss,

bk↦ak+s(bk−ak),b_k\mapsto a_k+s\left(b_k-a_k\right),

with ss chosen by bisection so that the query rate equals γ\gamma. 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 γ\gamma or Δ\Delta. 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 Rt\mathcal{R}_t (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 pR,t∘(⋅)p^\circ_{R,t}(\cdot) that greedily minimizes the local increment in cost dRt/dt\mathrm{d}\mathcal{R}_t/\mathrm{d}t. At a given step tt, the latter reads

dRtdt=ΔE[pt(ω)]+E[(1−pt(ω))1[ωω∗<0]].\frac{\mathrm{d}\mathcal{R}_t}{\mathrm{d}t}=\Delta\mathbb{E}\left[p_t(\omega)\right]+\mathbb{E}\left[(1-p_t(\omega))\mathbf{1}_{[\omega\omega^*<0]}\right].

where the expectation bears over

ω,ω∗∼N(02,[qtmtmt1]).\omega,\omega^*\sim\mathcal{N}\left(0_2,\begin{bmatrix}q_t&m_t\\m_t&1\end{bmatrix}\right).

For a given ω∈R\omega\in\mathbb{R}, taking a functional derivative with respect to pt(ω)p_t(\omega),

δδpt(ω)dRtdt=e−ω22qt2πqt[Δ−E[1[ωω∗<0]∣ω]]=e−ω22qt2πqt[Δ−Φ(−mt/qt∣ω∣1−mt2/qt)].\begin{aligned} \frac{\delta}{\delta p_t(\omega)}\frac{\mathrm{d}\mathcal{R}_t}{\mathrm{d}t} &=\frac{e^{-\frac{\omega^2}{2q_t}}}{\sqrt{2\pi q_t}}\left[\Delta-\mathbb{E}\left[\mathbf{1}_{[\omega\omega^*<0]}\mid\omega\right]\right]\\ &=\frac{e^{-\frac{\omega^2}{2q_t}}}{\sqrt{2\pi q_t}}\left[\Delta-\Phi\left(\frac{-m_t/q_t|\omega|}{\sqrt{1-m_t^2/q_t}}\right)\right]. \end{aligned}

The sign of the derivative is dictated by the term in brackets. If the latter is positive, then the risk increment dRt/dt\mathrm{d}\mathcal{R}_t/\mathrm{d}t is minimal at pt(ω)=0p_t(\omega)=0. If conversely the bracketed term is negative, then the dRt/dt\mathrm{d}\mathcal{R}_t/\mathrm{d}t is minimal for pt(ω)=1p_t(\omega)=1. The myopic policy for the cumulative risk is thus

pR,t∘(ω)=1[Φ(−mt/qt∣ω∣1−mt2/qt)≥Δ].p^\circ_{R,t}(\omega)=\mathbf{1}\left[\Phi\left(\frac{-m_t/q_t|\omega|}{\sqrt{1-m_t^2/q_t}}\right)\geq\Delta\right].

If Δ>1/2\Delta>1/2, 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 Δ≤1/2\Delta\leq1/2 on the other hand, pR,t∘p^\circ_{R,t} reduces to an adaptive margin-based policy of the form

pR,t∘(ω)=1[∣ω∣≤κt∘].p^\circ_{R,t}(\omega)=\mathbf{1}\left[|\omega|\leq\kappa^\circ_t\right].

with

κt∘=qt∘2(qt/mt2−1)∣erf⁡−1(2Δ−1)∣.(23)\kappa_t^\circ=\sqrt{q_t^\circ}\sqrt{2\left(q_t/m_t^2-1\right)}\left|\operatorname{erf}^{-1}(2\Delta-1)\right|. \tag*{(23)}

This recovers equations 4.1 of Res. 4.1. The expression of the threshold κt∘\kappa_t^\circ thus depends on the model weights as time tt, as encapsulated by the summary statistics mtm_t, qtq_t. When the model is trained with the Adatron rule with η=2\eta=2, and guided at each round by the pR,t∘p_{R,t}^\circ, an analysis of the ODEs (6) allows to precisely ascertain the asymptotic behavior of κt∘\kappa_t^\circ in the limit of large training times t→∞t\to\infty. This is the objective of the following subsection.

Large-time asymptotics

We now turn to examining the t→∞t\to\infty behavior of the threshold κt∘\kappa_t^\circ (23) when the summary statistics qt∘q_t^\circ, mt∘m_t^\circ are self-consistently governed by the ODEs (6) under policy schedule pR,t∘p_{R,t}^\circ, with η=2\eta=2. Let us show in self-consistent fashion that

κt∘≳1t.\kappa_t^\circ\gtrsim\frac{1}{t}.

We accordingly denote κt∘=Aq0t+o(1/t)\kappa_t^\circ=\frac{A\sqrt{q_0}}{t}+o(1/t), and aim at determining self-consistently the leading coefficient AA. Denoting γt∘=mt∘/qt∘\gamma_t^\circ=m_t^\circ/\sqrt{q_t^\circ}, we also assume that κt∘/2q0(1−γt∘)\kappa_t^\circ/\sqrt{2q_0(1-\gamma_t^\circ)} admits a non-zero limit as t→∞t\to\infty, which will be subsequently verified self-consistently. We accordingly introduce zz such that

κt∘2q0(1−γt∘)→t→∞z,(24)\frac{\kappa_t^\circ}{\sqrt{2q_0(1-\gamma_t^\circ)}}\xrightarrow[t\to\infty]{}z, \tag*{(24)}

again to be determined self-consistently. Under these assumptions, the ODE governing the time evolution of the summary statistics mt∘m_t^\circ (6) simplifies as

dmt∘dt=4∫0∞e−12(ω⋆)22π∫−∞∞e−12g22π1[∣mt∘ω⋆+2qt∘(1−γt∘)g∣≤κt∘]1[−(mt∘ω⋆+2qt∘(1−γt∘)g)≥0]∣mt∘ω⋆+2qt∘(1−γt∘)g∣ω⋆ dω⋆dg=−4∫0∞e−12(ω⋆)22πω⋆∫−κt∘+mt∘ω⋆2qt∘(1−γt∘)−κt∘−mt∘ω⋆2qt∘(1−γt∘)e−12g22π(mt∘ω⋆+2qt∘(1−γt∘)g)dω⋆dg≈−4mt∘∫0∞e−12(ω⋆)22π(ω⋆)2[Φ(−mt∘ω⋆2qt∘(1−γt∘))−Φ(−z−mt∘ω⋆2qt∘(1−γt∘))]dω⋆+42qt∘π(1−γt∘)32[1−e−z22+2πzΦ(−z)]≈q0ϕ(z)(1−γt∘)32,\begin{aligned} \frac{\mathrm{d}m_t^\circ}{\mathrm{d}t} &=4\int_0^\infty\frac{e^{-\frac{1}{2}(\omega^\star)^2}}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\frac{e^{-\frac{1}{2}g^2}}{\sqrt{2\pi}}\mathbf{1}\left[\left|m_t^\circ\omega^\star+\sqrt{2q_t^\circ(1-\gamma_t^\circ)}g\right|\le\kappa_t^\circ\right]\\ &\qquad\mathbf{1}\left[-\left(m_t^\circ\omega^\star+\sqrt{2q_t^\circ(1-\gamma_t^\circ)}g\right)\ge0\right]\left|m_t^\circ\omega^\star+\sqrt{2q_t^\circ(1-\gamma_t^\circ)}g\right|\omega^\star\,\mathrm{d}\omega^\star\mathrm{d}g\\ &=-4\int_0^\infty\frac{e^{-\frac{1}{2}(\omega^\star)^2}}{\sqrt{2\pi}}\omega^\star\int_{-\frac{\kappa_t^\circ+m_t^\circ\omega^\star}{\sqrt{2q_t^\circ(1-\gamma_t^\circ)}}}^{\frac{-\kappa_t^\circ-m_t^\circ\omega^\star}{\sqrt{2q_t^\circ(1-\gamma_t^\circ)}}}\frac{e^{-\frac{1}{2}g^2}}{\sqrt{2\pi}}\left(m_t^\circ\omega^\star+\sqrt{2q_t^\circ(1-\gamma_t^\circ)}g\right)\mathrm{d}\omega^\star\mathrm{d}g\\ &\approx-4m_t^\circ\int_0^\infty\frac{e^{-\frac{1}{2}(\omega^\star)^2}}{\sqrt{2\pi}}(\omega^\star)^2\left[\Phi\left(\frac{-m_t^\circ\omega^\star}{\sqrt{2q_t^\circ(1-\gamma_t^\circ)}}\right)-\Phi\left(-z-\frac{m_t^\circ\omega^\star}{\sqrt{2q_t^\circ(1-\gamma_t^\circ)}}\right)\right]\mathrm{d}\omega^\star\\ &\qquad+4\sqrt{\frac{2q_t^\circ}{\pi}}(1-\gamma_t^\circ)^{\frac{3}{2}}\left[1-e^{-\frac{z^2}{2}}+\sqrt{2\pi}z\Phi(-z)\right]\\ &\approx\sqrt{q_0}\phi(z)(1-\gamma_t^\circ)^{\frac{3}{2}}, \end{aligned}

where we introduced

ϕ(z)=42π(−∫0∞x2[Φ(−x/2)−Φ(−z−x/2)]dx+4π[1−e−z22+2πzΦ(−z)]).\phi(z)=\frac{4}{\sqrt{2\pi}}\left(-\int_0^\infty x^2\left[\Phi(-x/\sqrt{2})-\Phi(-z-x/\sqrt{2})\right]\mathrm{d}x+\sqrt{\frac{4}{\pi}}\left[1-e^{-\frac{z^2}{2}}+\sqrt{2\pi}z\Phi(-z)\right]\right).

On the other hand, for a learning rate η=2\eta= 2 (an assumption also made e.g. by Dasgupta et al. [4]), the squared norm qt∘q_t^\circ remains constant along training. Then, it follows from the identity

d(1−γt∘)dt=−1q0dmt∘dt=−ϕ(z)(1−γt∘)32\frac{\mathrm{d}(1-\gamma_t^\circ)}{\mathrm{d}t}=-\frac{1}{\sqrt{q_0}}\frac{\mathrm{d}m_t^\circ}{\mathrm{d}t}=-\phi(z)(1-\gamma_t^\circ)^{\frac{3}{2}}

that 1−γt∘1-\gamma_t^\circ scales as

1−γt∘≃4ϕ(z)t2(25)1-\gamma_t^\circ\simeq\frac{4}{\phi(z)t^2} \tag*{(25)}

when t→∞t\to\infty. As a corollary, the test error thus admits the following asymptotic behavior

ϵg=1πarccos⁡(γt∘)=8π∣ϕ(z)∣t+o(1t).\epsilon_g=\frac{1}{\pi}\arccos(\gamma_t^\circ)=\frac{\sqrt{8}}{\pi\lvert\phi(z)\rvert t}+o\left(\frac{1}{t}\right).

Finally, returning to (24), one deduces that zz satisfies the self-consistent equation

A∣ϕ(z)∣8=z,\frac{A\lvert\phi(z)\rvert}{\sqrt{8}}=z,

which provides a first self-consistent equation bearing on zz.

Having determined the asymptotics of mt∘,qt∘m_t^\circ,q_t^\circ, one is now in a position to ascertain the limiting behavior of κt∘\kappa_t^\circ, and in doing so close the equations on AA. From (23) and (25), κt∘\kappa_t^\circ asymptotically shrinks as

κt∘≃4q0∣erf⁡−1(2Δ−1)∣∣ϕ(z)∣t,\kappa_t^\circ\simeq\frac{4\sqrt{q_0}\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert}{\lvert\phi(z)\rvert t},

from which one deduces A=4∣erf⁡−1(2Δ−1)∣/∣ϕ(z)∣A=4\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert/\lvert\phi(z)\rvert. Returning to the self-consistent equation (24), the latter simplifies and gives in closed form

z=2∣erf⁡−1(2Δ−1)∣.z=\sqrt{2}\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert.

for the myopic rule. Finally, we find

κt∘≃q0c(Δ)1t,\kappa_t^\circ\simeq\sqrt{q_0}c(\Delta)\frac{1}{t},

with

c(Δ)=4∣erf⁡−1(2Δ−1)∣∣ϕ(2∣erf⁡−1(2Δ−1)∣)∣.(26)c(\Delta)=\frac{4\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert}{\left\lvert\phi\left(\sqrt{2}\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert\right)\right\rvert}. \tag*{(26)}

Derivation of Remark 4.2

The expected regret increment is thus at large time given at leading order by

E[dRt∘dt]=ΔE[pt(ω)]+E[(1−pt(ω))1[ωω⋆<0]]=[2Φ(κt∘q0)−1]Δ+21−γ12π∫0∞Φ(−2∣erf⁡−1(2Δ−1)∣−x2)dx≃2πΔ4∣erf⁡−1(2Δ−1)∣∣ϕ(2∣erf⁡−1(2Δ−1)∣)∣t+42π∫0∞Φ(−2∣erf⁡−1(2Δ−1)∣−x2)dx1∣ϕ(2∣erf⁡−1(2Δ−1)∣)∣t.\begin{aligned} \mathbb{E}\left[\frac{\mathrm{d}\mathcal{R}_t^\circ}{\mathrm{d}t}\right]=\Delta\mathbb{E}\left[p_t(\omega)\right]+\mathbb{E}\left[(1-p_t(\omega))\mathbf{1}[\omega\omega^\star<0]\right] \\ &=\left[2\Phi\left(\frac{\kappa_t^\circ}{\sqrt{q_0}}\right)-1\right]\Delta+2\sqrt{1-\gamma}\frac{1}{\sqrt{2\pi}}\int_0^\infty\Phi\left(-\sqrt{2}\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert-\frac{x}{\sqrt{2}}\right)\mathrm{d}x \\ &\simeq\sqrt{\frac{2}{\pi}}\Delta\frac{4\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert}{\left\lvert\phi\left(\sqrt{2}\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert\right)\right\rvert t} +\frac{4}{\sqrt{2\pi}}\int_0^\infty\Phi\left(-\sqrt{2}\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert-\frac{x}{\sqrt{2}}\right)\mathrm{d}x\frac{1}{\left\lvert\phi\left(\sqrt{2}\left\lvert\operatorname{erf}^{-1}(2\Delta-1)\right\rvert\right)\right\rvert t}. \end{aligned}

Thus, the regret only augments logarithmically for the myopic rule, as

Rt∘=32πΔ∣erf⁡−1(2Δ−1)∣+42π∫0∞Φ(−2∣erf⁡−1(2Δ−1)∣−x/2) dx∣ϕ(2∣erf⁡−1(2Δ−1)∣)∣ln⁡(t)+o(ln⁡(t)).\mathcal{R}^{\circ}_{t}=\frac{\sqrt{\frac{32}{\pi}}\Delta\left|\operatorname{erf}^{-1}(2\Delta-1)\right|+\frac{4}{\sqrt{2\pi}}\int_{0}^{\infty}\Phi\left(-\sqrt{2}\left|\operatorname{erf}^{-1}(2\Delta-1)\right|-x/\sqrt{2}\right)\,\mathrm{d}x}{\left|\phi\left(\sqrt{2}\left|\operatorname{erf}^{-1}(2\Delta-1)\right|\right)\right|}\ln(t)+o(\ln(t)).

Remark C.1. The 1/t1/t 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, pt(⋅)=1[∣⋅∣≤κ]p_t(\cdot)=\mathbb{1}[\lvert\cdot\rvert\le\kappa] with κ\kappa constant in time, one instead observes a linear in time increase

Rt=[2Φ(κq0)−1]Δt+o(t),\mathcal{R}_{t}=\left[2\Phi\left(\frac{\kappa}{\sqrt{q_{0}}}\right)-1\right]\Delta t+o(t),

no matter the margin κ>0\kappa>0.

As an additional remark, note that the number of queried samples scales logarithmically with time, as the policy gets more stringent.

Qt∘=2π4∣erf⁡−1(2Δ−1)∣ϕ(2∣erf⁡−1(2Δ−1)∣)ln⁡(t)+o(ln⁡(t)).Q^{\circ}_{t}=\sqrt{\frac{2}{\pi}}\frac{4\left|\operatorname{erf}^{-1}(2\Delta-1)\right|}{\phi\left(\sqrt{2}\left|\operatorname{erf}^{-1}(2\Delta-1)\right|\right)}\ln(t)+o(\ln(t)).

To leading order,

εg,t∘=exp⁡{−ϕ(2∣erf⁡−1(2Δ−1)∣)2π4∣erf⁡−1(2Δ−1)∣Qt∘+o(ln⁡(t))}.\varepsilon^{\circ}_{g,t}=\exp\left\{-\frac{\phi\left(\sqrt{2}\left|\operatorname{erf}^{-1}(2\Delta-1)\right|\right)}{\sqrt{\frac{2}{\pi}}4\left|\operatorname{erf}^{-1}(2\Delta-1)\right|}Q^{\circ}_{t}+o(\ln(t))\right\}.

Namely, the myopic policy pR,t∘(⋅)p^{\circ}_{R,t}(\cdot) 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

Mt∘=42π∫0∞dx Φ(−2∣erf⁡−1(2Δ−1)∣−x/2)∣ϕ(2∣erf⁡−1(2Δ−1)∣)∣ln⁡t+o(ln⁡(t)),\mathcal{M}^{\circ}_{t}=\frac{\frac{4}{\sqrt{2\pi}}\int_{0}^{\infty}\mathrm{d}x\,\Phi\left(-\sqrt{2}\left|\operatorname{erf}^{-1}(2\Delta-1)\right|-x/\sqrt{2}\right)}{\left|\phi\left(\sqrt{2}\left|\operatorname{erf}^{-1}(2\Delta-1)\right|\right)\right|}\ln t+o(\ln(t)),

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 tt, conditional on the network weights v,Wv,W at that time (with the latter assumed full rank), the average increment in cost reads

dRtdt=ΔE[pt(ω)]+E[(1−pt(ω))1[vTg(Ω)ω∗<0]],\frac{\mathrm{d}\mathcal{R}_{t}}{\mathrm{d}t}=\Delta\mathbb{E}\left[p_t(\omega)\right]+\mathbb{E}\left[(1-p_t(\omega))\mathbb{1}\left[v^{\mathsf{T}}g(\Omega)\omega^{*}<0\right]\right],

where the expectation bears over

(Ωω∗)∼N(0r+1,[QMMT1]).\begin{pmatrix} \Omega\\ \omega^{*} \end{pmatrix} \sim\mathcal{N}\left(0_{r+1},\begin{bmatrix}Q & M\\ M^{\mathsf{T}} & 1\end{bmatrix}\right).

with Q=WWT/dQ = WW^{\mathsf{T}}/d, M=Wβ/dM = W\beta/d. For a given Ω∈Rr\Omega\in\mathbb{R}^{r}, taking a functional derivative with respect to pt(Ω)p_t(\Omega),

δδpt(Ω)dRtdt=e−ΩTQ−1Ω2(2π)rdet⁡{Q}[Δ−E[1[vTg(Ω)ω∗<0]∣Ω]]=e−ΩTQ−1Ω2(2π)rdet⁡{Q}[Δ−Φ(−sign⁡(vTg(Ω))MTQ−1Ω1−MTQ−1M)].\begin{aligned} \frac{\delta}{\delta p_t(\Omega)}\frac{\mathrm{d}R_t}{\mathrm{d}t} = \frac{e^{-\frac{\Omega^{\mathsf{T}}Q^{-1}\Omega}{2}}}{\sqrt{(2\pi)^r\det\{Q\}}} \left[ \Delta-\mathbb{E}\left[\mathbb{1}\left[v^{\mathsf{T}}g(\Omega)\omega^{*}<0\right]\mid\Omega\right] \right] \\ &= \frac{e^{-\frac{\Omega^{\mathsf{T}}Q^{-1}\Omega}{2}}}{\sqrt{(2\pi)^r\det\{Q\}}} \left[ \Delta-\Phi\left( \frac{-\operatorname{sign}(v^{\mathsf{T}}g(\Omega))M^{\mathsf{T}}Q^{-1}\Omega} {\sqrt{1-M^{\mathsf{T}}Q^{-1}M}} \right) \right]. \end{aligned}

We note that the assumption β∉rowsp⁡(W)\beta\notin\operatorname{rowsp}(W) ensures 1−MTQ−1M>01-M^{\mathsf{T}}Q^{-1}M>0. Thus,

p˙t∘(Ω)=1[Φ(−sign⁡(vTg(Ω))MTQ−1Ω1−MTQ−1M)≥Δ],\dot{p}_t^{\circ}(\Omega) = \mathbb{1}\left[ \Phi\left( \frac{-\operatorname{sign}(v^{\mathsf{T}}g(\Omega))M^{\mathsf{T}}Q^{-1}\Omega} {\sqrt{1-M^{\mathsf{T}}Q^{-1}M}} \right) \geq\Delta \right],

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 O(dtF)O(d t_{\mathrm{F}}) runtime.

b-sampling (b-spl) [8] proposes a margin-based selection rule with (constant-in-time) acquisition probability

pt(⋅)=bb+∣⋅∣,p_t(\cdot) = \frac{b}{b + |\cdot|},

for a given choice of bandwidth b>0b > 0. 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 N=50N = 50 values for the parameter bb, evenly spread on a logarithmic grid between 10−2,1010^{-2}, 10, was performed, and only the trajectory corresponding to the value minimizing the terminal cumulative cost RtF\mathcal{R}_{t_{\mathrm{F}}} was plotted.

Adaptive b-sampling (ada-b-spl) [8] is an adaptive version of b-sampling, which prescribes to increase the bandwidth bb as the square-root of the cumulative number of mistakes on queried samples, namely

pt(⋅)=β1+M~tβ1+M~t+∣⋅∣,p_t(\cdot) = \frac{\beta\sqrt{1+\widetilde{\mathcal{M}}_t}}{\beta\sqrt{1+\widetilde{\mathcal{M}}_t} + |\cdot|},

with

M~t=∑i=1tdσi1[⟨wi,xi⟩yi<0],\widetilde{\mathcal{M}}_t = \sum_{i=1}^{t d} \sigma_i \mathbf{1}[\langle w_i,x_i\rangle y_i < 0],

for a given choice of tunable hyperparameter β>0\beta> 0. The value leading to minimal RtF\mathcal{R}_{t_{\mathrm{F}}} over a logarithmic grid of size 50 between 10−2,1010^{-2}, 10 was plotted.

Logistic sampling (log.-spl) ([46]) instead proposes a constant-in-time exponential (rather than sigmoid) ansatz for the acquisition probability

pt(⋅)=e−γ∣⋅∣,p_t(\cdot) = e^{-\gamma|\cdot|},

with hyperparameter γ>0\gamma> 0, again leveraging the Perceptron training rule. The value leading to minimal RtF\mathcal{R}_{t_F} over a logarithmic grid of size 50 between 10−210^{-2}, 10 was plotted.

Active Perceptron (AL-Perc) ([4]) corresponds to an Adatron rule with learning rate η=2\eta= 2, and a hard inner-margin threshold policy

pt(⋅)=1[∣⋅∣≤st],p_t(\cdot) = \mathbb{1}[|\cdot| \le s_t],

where the threshold sts_t is initialized at 1/d1/\sqrt{d}, and divided by 2 every time a streak of R∈NR \in\mathbb{N} 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 RR 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 p∈[0,1]p \in[0, 1], irrespective of the sample. 50 values of p∈[0.01,1]p \in[0.01, 1] 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 (K/tK/t-inner-margin) corresponds to a inner-margin policy

pt(⋅)=1[∣⋅∣≤K/t],p_t(\cdot) = \mathbb{1}[|\cdot| \le K/t],

with tunable hyperparameter KK. In Figure 3, Figure 7, Figure 8, Figure 9, a grid-search over N=50N = 50 values for the parameter KK, evenly spread on a logarithmic grid between 10−210^{-2}–50, was performed, and only the trajectory corresponding in hindsight to the value minimizing the terminal cumulative cost RtF\mathcal{R}_{t_F} was plotted.

Inner-margin with theory-prescribed threshold (K∘/tK^\circ/t-inner-margin) Note that Res. 4.1, Eq. (12) affords a particular prescription for the parameter KK above. The black lines in Figure 3, Figure 7, Figure 8, Figure 9 correspond to this particular value K=K∘K = K^\circ. For instance, for Δ=0.2\Delta= 0.2, q0=0.1q_0 = 0.1, η=2\eta= 2, K∘≈2.52K^\circ\approx2.52. 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 KK is tuned. The particular prescription K∘K^\circ (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 40×4040 \times40 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 n=7132n = 7132 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 40×4040 \times40 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 n=5763n = 5763 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 v,Wv, W, from which Figure 4 was then produced, using the expression of Result 4.4. The readout weights vv were initialized, and kept fixed throughout training, to the all-ones vector v=(1,1)⊤v = (1, 1)^{\top}. The weights WW were initialized with i.i.d standard Gaussian entries, then updated n=2000n = 2000 times with the online gradient update

Wi+1=Wi−ηℓ′(v⊤g(Wixi+1),sign⁡(⟨β,xi+1⟩))(v⊙g′(Wixi+1))xi+1⊤W_{i+1} = W_i - \eta\ell'\left(v^{\top} g(W_i x_{i+1}), \operatorname{sign}(\langle\beta, x_{i+1}\rangle)\right) \left(v \odot g'(W_i x_{i+1})\right)x_{i+1}^{\top}

with unit learning rate η=1\eta= 1, on the logistic loss ℓ(z,y)=ln⁡(1+exp⁡{−yz})\ell(z,y) = \ln(1 + \exp\{-yz\}), and without any data selection. The activation g(⋅)g(\cdot) was taken to be GeLU. Simulations were conducted in dimension d=500d = 500.

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 pR,t∘p^\circ_{R,t} for the cumulative cost (4), characterized for the Adatron rule in Result 4.1, for the case of the logistic loss. While pR,t∘p^\circ_{R,t} still takes the form (11), since the latter only depend on the loss through the current-time summary statistics values mt,qtm_t, q_t, the asymptotic behavior of the threshold κt∘\kappa^\circ_t differs. The following conjecture surmises that the latter tends to a non-zero limit in the large-time limit t→∞t \to\infty, as opposed to the 1/t1/t decay for Adatron.

Conjecture E.1 (Myopic policy for the cumulative cost, logistic loss). Let ℓ\ell be the logistic loss ℓ(z)=ln⁡(1+exp⁡{−z})\ell(z)=\ln(1+\exp\{-z\}). If the equation

∫u=0∞∫v=−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−v222π[ℓ′(u+zv)(2zv−ηℓ′(u+zv))]dudv=0(27)\int_{u=0}^{\infty}\int_{v=-\frac{\sqrt{2}z\left|\operatorname{erf}^{-1}(2\Delta-1)\right|-u}{z}}^{\frac{\sqrt{2}z\left|\operatorname{erf}^{-1}(2\Delta-1)\right|-u}{z}}\frac{e^{-\frac{v^2}{2}}}{2\pi}\left[\ell'(u+zv)\left(2zv-\eta\ell'(u+zv)\right)\right]\mathrm{d}u\mathrm{d}v=0 \tag*{(27)}

admits a positive solution z∗>0z^*>0, then the threshold κt∘\kappa_t^\circ (23) admits a non-zero limit

κt∘→t→∞2z∗∣erf⁡−1(2Δ−1)∣.\kappa_t^\circ\xrightarrow{t\to\infty} \sqrt{2}z^*\left|\operatorname{erf}^{-1}(2\Delta-1)\right|.

Furthermore, when the policy pR,t∘p_{\mathcal{R},t}^\circ is employed, the test error decays asymptotically as

ε˙g,t=(z∗/π−3η∫u=0∞∫v=−2z∗∣erf⁡−1(2Δ−1)∣−uz∗2z∗∣erf⁡−1(2Δ−1)∣−uz∗e−v222π[ℓ′(u+z∗v)(2(u+z∗v)−ηℓ′(u+z∗v))]dudv)13t−13+o(t−13).\dot{\varepsilon}_{g,t}=\left(\frac{z^*/\pi}{-3\eta\int_{u=0}^{\infty}\int_{v=-\frac{\sqrt{2}z^*\left|\operatorname{erf}^{-1}(2\Delta-1)\right|-u}{z^*}}^{\frac{\sqrt{2}z^*\left|\operatorname{erf}^{-1}(2\Delta-1)\right|-u}{z^*}}\frac{e^{-\frac{v^2}{2}}}{2\pi}\left[\ell'(u+z^*v)\left(2(u+z^*v)-\eta\ell'(u+z^*v)\right)\right]\mathrm{d}u\mathrm{d}v}\right)^{\frac{1}{3}}t^{-\frac{1}{3}}+o\left(t^{-\frac{1}{3}}\right).

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 Δ,η\Delta,\eta (see Figure 10), leading us to surmise that Conj. E.1 holds more broadly.

Figure 10. Test error ϵg,t\epsilon_{g,t} as a function of training time, with online SGD with logistic loss, under the myopic policy pR,t∘p^\circ_{R,t} (11). Solid lines represent single runs in dimension d=100d=100, dashed lines represent the theoretical prediction for the t→∞t \to\infty 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 Rt∘R_t^\circ, number of mistakes Mt∘M_t^\circ, and number of queries Qt∘Q_t^\circ scale as Rt∘,Mt∘,Qt∘≍t2/3R_t^\circ,M_t^\circ,Q_t^\circ\asymp t^{2/3}.

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 κt∘\kappa_t^\circ (23), one needs to study the dynamics of the summary statistics mt∘,qt∘m_t^\circ,q_t^\circ, as governed by the ODEs (6) controlled by the myopic policy pR,t∘p_{\mathcal{R},t}^\circ (11). In the likeness of App. C, we make a series of ansatz, which will be subsequently verified in self-consistent fashion. We assume

mt∘,qt∘→t→∞∞,m_t^\circ,q_t^\circ\xrightarrow{t\to\infty}\infty,

together with

γt∘→t→∞1,2(1−γt∘)qt∘→t→∞z,\gamma_t^\circ\xrightarrow{t\to\infty}1,\qquad\sqrt{2(1-\gamma_t^\circ)q_t^\circ}\xrightarrow{t\to\infty}z,

where we introduced the limit z>0z>0, to be determined self-consistently. Under these assumptions, the threshold κt∘\kappa_t^\circ then converges to the limit

κt∘→t→∞2z∣erf⁡−1(2Δ−1)∣.\kappa_t^\circ\xrightarrow{t\to\infty}\sqrt{2}z\left|\operatorname{erf}^{-1}(2\Delta-1)\right|.

It thus remains to ascertain zz. On the one hand, the ODE for mt∘m_t^\circ simplifies as

dmt∘dt=−2η∫0∞e−12(ω∗)22π∫−κt∘/qt∘−ω∗2(1−γt∘)κt∘/qt∘−ω∗2qt∘(1−γt∘)e−12g22πℓ′(mt∘ω∗+2qt∘(1−γt∘)g)ω∗dω∗dg≈−2ηqt∘∫0∞e−12qt∘(ω∗)22π∫−κt∘−ω∗2qt∘(1−γt∘)κt∘−ω∗2qt∘(1−γt∘)e−12g22πℓ′(ω∗+2qt∘(1−γt∘)g)ω∗dω∗dg≈−2ηq∫0∞∫−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−12v22π[ℓ′(u+zv)u]dudv.\begin{aligned} \frac{\mathrm{d}m_t^\circ}{\mathrm{d}t} &=-2\eta\int_0^\infty\frac{e^{-\frac{1}{2}(\omega^\ast)^2}}{\sqrt{2\pi}}\int_{\frac{-\kappa_t^\circ/\sqrt{q_t^\circ}-\omega^\ast}{\sqrt{2(1-\gamma_t^\circ)}}}^{\frac{\kappa_t^\circ/\sqrt{q_t^\circ}-\omega^\ast}{\sqrt{2q_t^\circ(1-\gamma_t^\circ)}}}\frac{e^{-\frac{1}{2}g^2}}{\sqrt{2\pi}}\ell'\left(m_t^\circ\omega^\ast+\sqrt{2q_t^\circ(1-\gamma_t^\circ)}g\right)\omega^\ast\mathrm{d}\omega^\ast\mathrm{d}g\\ &\approx-2\frac{\eta}{q_t^\circ}\int_0^\infty\frac{e^{-\frac{1}{2q_t^\circ}(\omega^\ast)^2}}{\sqrt{2\pi}}\int_{\frac{-\kappa_t^\circ-\omega^\ast}{\sqrt{2q_t^\circ(1-\gamma_t^\circ)}}}^{\frac{\kappa_t^\circ-\omega^\ast}{\sqrt{2q_t^\circ(1-\gamma_t^\circ)}}}\frac{e^{-\frac{1}{2}g^2}}{\sqrt{2\pi}}\ell'\left(\omega^\ast+\sqrt{2q_t^\circ(1-\gamma_t^\circ)}g\right)\omega^\ast\mathrm{d}\omega^\ast\mathrm{d}g\\ &\approx-\frac{2\eta}{q}\int_0^\infty\int_{\frac{-\sqrt{2z}\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2z}\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}\frac{e^{-\frac{1}{2}v^2}}{2\pi}\left[\ell'(u+zv)u\right]\mathrm{d}u\mathrm{d}v. \end{aligned}

By the same token

dqt∘dt≈−2ηq[∫0∞∫−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−12v22π[ℓ′(u+zv)(2(u+zv)−ηℓ′(u+zv))]dudv]\frac{\mathrm{d}q_t^\circ}{\mathrm{d}t}\approx-\frac{2\eta}{\sqrt{q}}\left[\int_0^\infty\int_{\frac{-\sqrt{2z}\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2z}\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}\frac{e^{-\frac{1}{2}v^2}}{2\pi}\left[\ell'(u+zv)\left(2(u+zv)-\eta\ell'(u+zv)\right)\right]\mathrm{d}u\mathrm{d}v\right]

Thus,

mt∘=(−6η∫0∞∫−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−v2/22π[ℓ′(u+zv)u] dv du)13t13+o(t13).m_t^\circ= \left(-6\eta\int_{0}^{\infty} \int_{\frac{-\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}} \frac{e^{-v^2/2}}{2\pi}\left[\ell'(u+zv)u\right]\,\mathrm{d}v\,\mathrm{d}u\right)^{\frac{1}{3}}t^{\frac{1}{3}}+o\left(t^{\frac{1}{3}}\right).
qt∘≍(−3η∫0∞∫−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−v2/22π[ℓ′(u+zv)(2(u+zv)−ηℓ′(u+zv))] dv du)23t23+o(t23).q_t^\circ\asymp\left(-3\eta\int_{0}^{\infty} \int_{\frac{-\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}} \frac{e^{-v^2/2}}{2\pi}\left[\ell'(u+zv)\left(2(u+zv)-\eta\ell'(u+zv)\right)\right]\,\mathrm{d}v\,\mathrm{d}u\right)^{\frac{2}{3}}t^{\frac{2}{3}}+o\left(t^{\frac{2}{3}}\right).

From the above and the observation that εg,t∘≲1−γ/π\varepsilon_{g,t}^{\circ}\lesssim\sqrt{1-\gamma/\pi}, one deduces

εg,t∘≲z/π(−3η∫0∞∫−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−v2/22π[ℓ′(u+zv)(2(u+zv)−ηℓ′(u+zv))] dv du)13t−13.\varepsilon_{g,t}^{\circ}\lesssim\frac{z/\pi}{\left(-3\eta\int_{0}^{\infty} \int_{\frac{-\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}} \frac{e^{-v^2/2}}{2\pi}\left[\ell'(u+zv)\left(2(u+zv)-\eta\ell'(u+zv)\right)\right]\,\mathrm{d}v\,\mathrm{d}u\right)^{\frac{1}{3}}}t^{-\frac{1}{3}}.

One is now in a position to determine self-consistently zz. For all the above to be consistent, one has, on the one hand

dγt∘dt=−ddt(z22qt∘)=z22(qt∘)2dqt∘dt≍t−53.(28)\frac{\mathrm{d}\gamma_t^\circ}{\mathrm{d}t}=-\frac{\mathrm{d}}{\mathrm{d}t}\left(\frac{z^2}{2q_t^\circ}\right)=\frac{z^2}{2(q_t^\circ)^2}\frac{\mathrm{d}q_t^\circ}{\mathrm{d}t}\asymp t^{-\frac{5}{3}}. \tag*{(28)}

On the other hand, from the definition of γt∘\gamma_t^\circ, one also has

dγt∘dt=−η2(qt∘)3/2∫0∞∫−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−v2/22π[ℓ′(u+zv)u] dv du+mt∘η(qt∘)2∫0∞∫−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−v2/22π[ℓ′(u+zv)(2(u+zv)−ηℓ′(u+zv))] dv du≈η(qt∘)3/2∫u=0∞∫v=−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−v2/22π[ℓ′(u+zv)(2zv−ηℓ′(u+zv))] dv du+o((qt∘)−3/2).(29)\begin{aligned} \frac{\mathrm{d}\gamma_t^\circ}{\mathrm{d}t}=-\eta\frac{2}{(q_t^\circ)^{3/2}}\int_{0}^{\infty}\int_{\frac{-\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}\frac{e^{-v^2/2}}{2\pi}\left[\ell'(u+zv)u\right]\,\mathrm{d}v\,\mathrm{d}u \\ &+\frac{m_t^\circ\eta}{(q_t^\circ)^2}\int_{0}^{\infty}\int_{\frac{-\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}\frac{e^{-v^2/2}}{2\pi}\left[\ell'(u+zv)\left(2(u+zv)-\eta\ell'(u+zv)\right)\right]\,\mathrm{d}v\,\mathrm{d}u \\ &\approx\frac{\eta}{(q_t^\circ)^{3/2}}\int_{u=0}^{\infty}\int_{v=\frac{-\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}\frac{e^{-v^2/2}}{2\pi}\left[\ell'(u+zv)\left(2zv-\eta\ell'(u+zv)\right)\right]\,\mathrm{d}v\,\mathrm{d}u+o\left((q_t^\circ)^{-3/2}\right). \tag*{(29)} \end{aligned}

Unless the double integral is zero, this scales as (qt∘)−3/2≍t−1(q_t^\circ)^{-3/2}\asymp t^{-1}. Since equations (28) and (29) are equal, the right hand side of the latter must vanish at leading t−1t^{-1} order. This provides the following condition

∫u=0∞∫v=−2z∣erf⁡−1(2Δ−1)∣−uz2z∣erf⁡−1(2Δ−1)∣−uze−v2/22π[ℓ′(u+zv)(2zv−ηℓ′(u+zv))] du dv=0.(30)\int_{u=0}^{\infty}\int_{v=\frac{-\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}^{\frac{\sqrt{2}z\lvert\operatorname{erf}^{-1}(2\Delta-1)\rvert-u}{z}}\frac{e^{-v^2/2}}{2\pi}\left[\ell'(u+zv)\left(2zv-\eta\ell'(u+zv)\right)\right]\,\mathrm{d}u\,\mathrm{d}v=0. \tag*{(30)}

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 Δ\Delta, η\eta.

References

  1. [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. [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. [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. [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. [5]Steve Hanneke. Theory of active learning. Foundations and Trends in Machine Learning, 7(2-3):127–292, 2014.
  6. [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. [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. [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. [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. [10]JK Anlauf and M Biehl. The adatron: an adaptive perceptron algorithm. EPL (Europhysics Letters), 10 (7):687–692, 1989.
  11. [11]Theodore Samuel Motzkin and Isaac Jacob Schoenberg. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6:393–404, 1954.
  12. [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. [13]Wolfgang Kinzel and Pal Rujan. Improving a network generalization ability by selecting examples. EPL (Europhysics Letters), 13(5):473–477, 1990.DOI
  14. [14]TLH Watkin and A Rau. Selecting examples for perceptrons. Journal of Physics A: Mathematical and General, 25(1):113–121, 1992.DOI
  15. [15]Andreas Engel and Christian van den Broeck. Statistical mechanics of learning, volume 1. Cambridge University Press Cambridge, 2001.
  16. [16]Magnus Rattray and David Saad. Globally optimal on-line learning rules. Advances in Neural Information Processing Systems, 10, 1997.
  17. [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.
  18. [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
  19. [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
  20. [21]Jialin Yu and Moïse Blanchard. Distribution-free sequential prediction with abstentions. arXiv preprint arXiv:2602.17918, 2026.arxiv.org/abs/2602.17918
  21. [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
  22. [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
  23. [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
  24. [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
  25. [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
  26. [29]Magnus Rattray and David Saad. Analysis of on-line training with optimal learning rates. Physical Review E, 58(5):6379, 1998.DOI
  27. [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
  28. [32]Francesco Mori and Francesca Mignacco. Analytic theory of dropout regularization. Physical Review E, 112(4):045301, 2025.arxiv.org/abs/2505.07792
  29. [33]Francesca Mignacco and Francesco Mori. A statistical physics framework for optimal learning. PNAS nexus, 5(6):pgag182, 2026.DOI
  30. [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
  31. [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
  32. [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
  33. [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
  34. [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.
  35. [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
  36. [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
  37. [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
  38. [42]Hai-Jun Zhou. Active online learning in the binary perceptron problem. Communications in Theoretical Physics, 71(2):243, 2019.DOI
  39. [43]JMR Parrondo and Christian van den Broeck. Error vs. rejection curve for the perceptron. EPL (Europhysics Letters), 22(5):319–324, 1993.
  40. [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
  41. [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.
  42. [46]D Sculley. Online active learning methods for fast label-efficient spam filtering. In CEAS, volume 7, page 143, 2007.
  43. [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.
  44. [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
  45. [49]Davide Cacciarelli and Murat Kulahci. Active learning for data streams: a survey. Machine Learning, 113 (1):185–239, 2024.DOI
  46. [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
  47. [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
  48. [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
  49. [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
  50. [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
  51. [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.
  52. [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
  53. [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
  54. [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
  55. [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
  56. [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
  57. [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
  58. [63]Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17, 2004.

Paper details

vlnc:W_nzehcchx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents