Active Learning via Regression Beyond Realizability

Atul Ganju; Karthik Sridharan; Shashaank Aiyer; Ved Sriraman

REVIEW 3 major objections 4 minor 36 references

Active Learning via Regression Beyond Realizability

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that surrogate-based active learning can shed the realizability assumption: for convex model classes satisfying a margin-alignment condition, an improper epoch algorithm matches the label complexity of prior realizable…

desk verdict A genuine step beyond realizability in surrogate-based active learning, but the main assumption is mis-quantified as written: the paper's own non-realizable example fails it unless the probability is over the query-induced distribution. read the letter →

arxiv 2506.00316 v1 pith:XZKQWSU3 submitted 2025-05-31 cs.LG math.STstat.MLstat.TH

Atul Ganju , Shashaank Aiyer , Ved Sriraman , Karthik Sridharan This is my paper

classification cs.LGmath.STstat.MLstat.TH MSC 68Q3262H30

keywords activelearningsurrogateriskminimizationrealizabilitymulticlassclassificationconvexfunctionclassesdisagreementcoefficientTsybakovnoiseimproper

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that surrogate-based active learning for multiclass classification does not require the realizability assumption, the assumption that the optimal surrogate predictor belongs to the learner's function class. Instead, it shows that if the function class $\mathcal{F}$ is convex and satisfies a margin-alignment condition (Assumption 2), an epoch-based algorithm that fits a fresh model to each queried region and outputs an improper classifier can match, and in some respects improve on, the sample and label complexity rates previously obtained under realizability by [HY19] and [ZN22]. The alignment condition says that on every distribution the algorithm induces by restricting queries to a region, the best-in-class predictor's confidence gap is at least a nondecreasing function $\psi$ of the Bayes predictor's gap; this is strictly weaker than realizability and, the paper shows via Example 1, can hold when the problem is far from approximately realizable. The paper's main theorem bounds excess classification risk and label queries in terms of the offline regression oracle's rate, the function $\psi$, the margin mass of the Bayes predictor, and the value-function disagreement coefficient. A passive corollary extends the same idea, bounding classification excess risk by surrogate excess risk under a bias-alignment condition, which is what opens the door to the active result.

What carries the argument

The argument rests on four pieces. First, Assumption 2: for every query-induced region $Q\subseteq \mathcal{X}$, the best-in-class function $f^*_Q$ on the restricted distribution $D_Q$ has gap $$\operatorname{gap}(\$\varphi$(f^*_Q(x)), c)\ge \psi(\operatorname{gap}(\$\varphi$(f_\eta(x)), c))$$ for each class $c$, almost surely; this is the replacement for realizability. Second, convexity of $\mathcal{F}$ combined with a $\beta_\Phi$-strongly convex, $L_\Phi$-smooth surrogate $\ell_\Phi(v,y)=\Phi(v)-v[y]$: convexity lets the paper control $\|f-f^*\|^2_{D_X}$ by the surrogate excess risk, so the classification excess risk bound of Proposition 2 goes through. Third, the value-function disagreement coefficient $\theta_{\mathrm{val}}(\mathcal{F},\gamma)$ from [FRSLX20], which controls the probability that the maintained version set still contains disagreeing functions. Fourth, an improper epoch-based algorithm (Algorithm 1): each epoch fits a model from the full class on the queried data, builds a version set of functions consistent with that fit, stops querying where the version set is in consensus, and returns the earliest-epoch consensus classifier, defaulting to the last fit otherwise.

What would settle it

Compute, for a convex class F and distribution D, the best-in-class function f*_Q on a region Q reachable by the algorithm's query rule, and check whether gap($\varphi$(f*_Q(x)), c) < psi(gap($\varphi$(f_eta(x)), c)) on a set of positive D_X-measure, or whether h_{f*_Q} disagrees with h_{f_eta} there; then Assumption 2 fails, and the theorem's guarantees, which require f*_m in F_m, cannot apply. One concrete way is the hypercube Example 1: verify the claimed psi(x) = $d^{{-1/2}}$ x on all symmetric query subsets {±e_i : i in S}; if any reachable subset violates it, the counterexample is explicit.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is that the realizability assumption in surrogate-based active learning can be replaced by a strictly weaker condition without sacrificing rates. Concretely, Theorem 4.2 states that for any convex function class $\mathcal{F}$ satisfying Assumption 2, Algorithm 1 returns a classifier with excess risk bounded by $$\tilde O\!\left(\inf_\gamma \left\{ \frac{L_\Phi \beta_\$Phi^{{-1}}$ \mathrm{comp}\,\sup_{a\in(\gamma,1]} a/\$psi^{2}$(a)}{n} + \gamma P[\operatorname{margin}(\eta(x))\le \gamma]\right\}\right)$$ and label complexity bounded by $$\tilde O\!\left(\inf_\gamma \left\{ \frac{L_\$Phi^{2}$ \beta_\$Phi^{{-1}}$ \mathrm{comp}\,\theta_{\mathrm{val}}}{\$psi^{2}$(\gamma)} + n P[\operatorname{margin}(\eta(x))\le \gamma]\right\}\right),$$ matching or beating the realizability-based rates of prior surrogate active learners. Under Tsybakov noise with $\psi(x)=x$, this gives label complexity $N=\tilde O(\mathrm{comp}\,\theta_{\mathrm{val}}^{\beta/(\beta+2)}\epsilon^{-2/(\beta+1)})$, with a strictly better dependence on the disagreement coefficient than both [HY19] and [ZN22]. The proof's key structural fact is that convexity makes the excess surrogate risk control the $\mathbb{L}_2(D_X)$ distance to the best-in-class function, so the surrogate minimizer on each query-restricted distribution stays inside the maintained version set even when it is not the Bayes predictor.

Load-bearing premise

The load-bearing premise is Assumption 2: on every subpopulation the algorithm can create by restricting its querying to a region, the best-in-class predictor must be at least psi(x) as confident as the Bayes predictor, and in particular must make the same prediction as Bayes, so if any reachable query region breaks this alignment, the proof that the true best-in-class function stays in the maintained version set collapses.

Editorial extensions

If this is right

If the paper is right, convexity plus a margin-alignment condition is enough to inherit the full benefit of surrogate-based active learning: sample complexity $n=\tilde O(\mathrm{comp}\,\epsilon^{-(\beta+2)/(\beta+1)})$ and label complexity $N=\tilde O(\mathrm{comp}\,\theta_{\mathrm{val}}^{\beta/(\beta+2)}\epsilon^{-2/(\beta+1)})$ under Tsybakov noise with $\psi(x)=x$.
The improper output, an early-consensus stitching of epoch-wise fits, is essential: previous version-space algorithms such as those of [HY19] and [ZN22] provably break in non-realizable settings, whereas Algorithm 1 keeps their rates under Assumption 2.
The passive prerequisite (Proposition 1 / Proposition 2) also stands alone: excess classification risk is controlled by excess surrogate risk without realizability, which is a necessary step for the active guarantee and is of independent use for misspecified regression-based classification.
The alignment condition is not merely technical: Example 1 gives a linear class on the hypercube that is far from approximately realizable yet satisfies Assumption 2 with $\psi(x)=d^{-1/2}x$, showing the regime is nonempty.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

We read the paper's real demand as asymmetric: the fitted regressor may be confident where Bayes is uncertain, but it may not be uncertain where Bayes is confident; this asymmetry is likely the practical content of Assumption 2 and could be checked empirically on real misspecified model classes by estimating best-in-class margins on query-restricted data.
The epoch-wise improper aggregation suggests a template for other interactive decision problems with regression oracles, such as contextual bandits, selective sampling, and imitation learning, where realizability fails: fit local estimates on restricted distributions and stitch them by earliest confident epoch, paying the disagreement coefficient rather than a realizability penalty.
A natural stress test the paper does not run is to instantiate Algorithm 1 on a real high-dimensional linear or kernel classifier under label noise and compare its query counts with a version-space learner; if the gap-alignment condition holds approximately, the improper learner should keep its label advantage as misspecification grows, which would test whether the assumption, not just the rates,

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my read. The core idea is solid and genuinely new: the epoch-based improper algorithm, the all-query-region margin assumption, and the explicit non-realizable example together give the first surrogate-based active learning guarantee under something strictly weaker than realizability. The rates match HY19 and ZN22, and the passive extension in Proposition 1 is a clean, useful building block. The proof structure is mostly standard, and the use of LRS15 and the concentration lemmas as black boxes is fine; there is no circularity. Credit where due: this is a real contribution, not a repackaging.

The soft spots are real but uneven. The big one is Assumption 2. As stated, it requires the inequality to hold almost surely under the original D_X for every query region Q. The proof only needs it on the query region X_m, and Example 1 only verifies it for x in Q. Under the literal statement the example fails: for a proper symmetric Q, f*_Q has zero weight on coordinates outside Q, so |f*_Q(x) - 1/2| = 0 there, while |eta(x) - 1/2| = 1/2 and the RHS is d^{-1/2}/2 > 0. That is a load-bearing quantifier error, not a typo. The fix is to state the probability over D_Q (or condition on x in Q); then the proof likely goes through and the example works. But it must be corrected and re-verified, and the theorem depends on it entirely.

The abstract also promises that prior methods "can be shown to fail" in non-realizable settings, but the body never gives that demonstration—it only explains why their analyses break down. That is overclaiming and should be either proved or softened.

Minor: Lemma 5 has a constant-level factor-of-two slip. It does not affect the rates, so I would not block on it, but it should be fixed. The verification of Assumption 2 only on a toy example is a limitation, but for a theory paper that is acceptable if the assumption is clearly motivated.

Who is this for: anyone working on active learning theory, surrogate losses, or the realizability barrier in regression reductions. A serious referee should engage with it, but the quantifier issue in Assumption 2 must be fixed before the main claims hold as written. My recommendation: send it to a good theory venue, ask for a corrected assumption and example, the missing failure proof or a softened abstract, and the Lemma 5 constant.

Referee Report

3 major / 4 minor

Summary. The manuscript proposes an active learning framework for multiclass classification based on surrogate risk minimization that avoids the realizability assumption. It introduces Assumption 2, a bias-monotonicity condition linking the best-in-class function on every query-induced subdistribution to the Bayes predictor, and gives an epoch-based improper algorithm that fits a surrogate model to queried data per epoch and aggregates the resulting classifiers. The main theoretical results are a passive bound (Propositions 1 and 2) converting surrogate excess risk to classification excess risk under this condition, and an active guarantee (Theorem 4.2) bounding excess risk and label complexity, with a Tsybakov-noise instantiation (Corollary 1). The paper also claims that prior surrogate-based active learning algorithms fail in non-realizable settings satisfying the new assumption.

Significance. If the main theorem and its supporting lemmas are correct, this is a substantial step: it would provide a surrogate-based active learning guarantee under a condition weaker than realizability, with rates matching the realizable-setting bounds of HY19 and ZN22, and it introduces an improper aggregation scheme and a value-based disagreement coefficient analysis. The proofs are largely self-contained, with explicit concentration lemmas and a concrete non-realizable example intended to separate the assumption from approximate realizability. The paper is honest about the convexity requirement and provides a counterexample when convexity is absent. However, the significance is conditional: the quantifier in Assumption 2 and the proof of Lemma 7 are load-bearing issues that must be resolved before the claimed separation and label-complexity rates are established.

major comments (3)

[Section 4, Assumption 2, and Example 1 (Section C.2)] As written, Assumption 2 quantifies the probability over the original marginal D_X for every subset Q⊆X: P_{x∼D_X}[gap(φ(f*_Q(x)), c) ≥ ψ(gap(φ(f_η(x)), c))] = 1. In Example 1, for any proper query region Q of the symmetric form {±e_i : i∈S}, the optimal function f*_Q on D_Q saturates the norm constraint on the coordinates in Q and therefore satisfies f*_Q(x) = 1/2 for all x outside Q, while |η(x)−1/2| = 1/2 on those points. Consequently the asserted event fails on a set of positive D_X-measure unless Q = X, so Example 1 does not satisfy Assumption 2 as stated. The proof of Theorem 4.2 uses the condition only for x ∈ X_m, i.e., for the query-induced subdistribution D_Q, so the intended quantifier appears to be P_{x∼D_Q} or a pointwise condition on Q. The definition and the verification of Example 1 must be corrected and re-verified; as printed, the paper's only non-realizable example is not covered by its own assumption.
[Section A.4, Lemma 7] The proof of Lemma 7 replaces the supremum over f′∈F_m of the empirical distance to \hat f_m by 4β^{-1}comp + C, but the construction of F_m in Algorithm 1 (line 11) bounds that supremum only by B/k_m with B = C log^3(n) comp(F,δ,n,K). Only the specific function f*_m is shown (in Lemma 6) to satisfy the smaller bound, so the asserted bound for arbitrary f∈F_m does not follow from the displayed argument. Moreover, even if the displayed summation bound were valid, substituting it into Lemma 2 introduces an additional factor of 2 in the expectation, yielding (64β^{-1}comp + 9C)/k_m rather than the stated (32β^{-1}comp + 9C)/k_m. Since Lemma 5 and the label-complexity bound in Theorem 4.2 rely on Lemma 7, the label-complexity claim is not established as written.
[Abstract and Section 4, 'Our Algorithm vs. Prior Methods'] The abstract asserts that the algorithmic approaches of [HY19, ZN22] 'can be shown to fail in non-realizable settings where our assumption is satisfied,' but no such theorem or counterexample is provided in the body. The manuscript only observes that those analyses require realizability, and Table 1 compares rates under different assumptions. Provide a concrete counterexample or a formal statement exhibiting the failure of prior methods, or soften the claim to the supported statement that prior analyses do not extend to the non-realizable setting.

minor comments (4)

[Section 4, Theorem 4.2 and Corollary 1] The text repeatedly refers to 'the offline regression oracle in Theorem 2.1', but no Theorem 2.1 appears; the oracle is defined in Definition 2.1, and its rate is given in Lemma 8. The cross-references should be fixed.
[Section C.1, Claim 1] The hypothesis 'satisfies Theorem 2.2 for parameter γ' should refer to the Massart noise condition (Definition 2.2); as written, Theorem 2.2 does not exist.
[Section A.2, Lemma 1 proof] The inequality sqrt(−2 log(δ/M)/E[k_m]) ≤ 1/2 + log(M/δ)/E[k_m] is described as following from AM-GM; it follows from the elementary bound sqrt(ab) ≤ (a+b)/2, so the attribution should be corrected.
[Algorithm 1, line 2] The epoch schedule is written 'τ_m = 2m−1', which is ambiguous; if the intended geometric schedule is τ_m = 2^m−1, the typographical rendering should be fixed.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: target bounds are never assumed; Assumption 2 is an explicit (if mis-stated) domain condition, and self-citations are used only as black-box complexity oracles.

full rationale

I traced the chain leading to Theorem 4.2. The proof does not fit any parameter to the announced excess risk or label count; comp is the oracle rate supplied by Definition 2.1, and the theorem's bound is a reduction of active classification error to passive surrogate excess risk plus margin mass and disagreement. Lemmas 1, 2, 6 and 7 are standard concentration and version-space arguments; Lemma 5 uses the value-function disagreement coefficient. No equation in the paper sets the target bound equal to an input by definition, and no fitted quantity is renamed as a prediction. The citations most likely to be self-citations, [LRS15] and [SSSW23], are used only to state the regression oracle's excess-risk rate and concentration inequalities; those results are parameter-free with stated assumptions that do not include the target active-learning bound, so under the rules they count as independent support and do not raise the circularity score. One non-circular defect should nevertheless be flagged: Assumption 2 is printed with probability over D_X for every Q, but Example 1 verifies only 'for all x in Q' that |f*_Q(x)-1/2| >= psi(|eta(x)-1/2|). For x outside Q the example's own formula w*_Q[i]=0 gives f*_Q(x)=1/2 while psi(1/2)=d^{-1/2}/2>0, so the printed assumption is not demonstrated on a set of positive D_X measure. This is a correctness gap in the separation example, not a circular step: the theorem's logic would go through unchanged if the intended quantification is over D_Q or conditioned on Q. Apart from the minor self-citations, the derivation is self-contained, so the circularity score is 2, not higher.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters were fitted to data; the only assumption constants are standard. The margin function psi is a structural function assumed to exist, not a fitted number. The main load is carried by Assumption 2, which is an explicit but very strong domain assumption.

assumptions (5)

domain assumption Assumption 2: for every query-induced subset Q and every class c, gap(phi(f*_Q(x)), c) >= psi(gap(phi(f_eta(x)), c)) almost surely.
Central structural condition replacing realizability; it also forces the best-in-class classifier on every truncated distribution to match the Bayes classifier. Hard to verify; only a toy example (Example 1) is provided. Location: Section 4, Assumption 2.
domain assumption Convexity of the model class F.
Used to prove that excess surrogate risk controls squared distance to f* (Lemma 9) and in Propositions 1 and 2. Location: Section 3, proof of Proposition 1; Section D.
standard math The surrogate potential Phi is beta_Phi-strongly convex and L_Phi-smooth, with link phi = grad Phi.
Standard surrogate framework from Agarwal 2013; yields a Lipschitz link function and the strong-convexity inequalities used throughout. Location: Section 2.
domain assumption An offline regression oracle achieves excess surrogate risk at most comp(F, delta, n, K)/n.
Black-box algorithmic primitive; concrete rates are only provided for squared loss with pseudo-dimension or covering numbers in Section B.2. Location: Definition 2.1.
domain assumption Tsybakov or Massart noise condition on the marginal distribution.
Distributional assumption used in Corollary 1 and Claim 1 to convert margin events into rates. Location: Definitions 2.2 and 2.3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Active Learning via Regression Beyond Realizability." pith.science (2026). https://pith.science/paper/XZKQWSU3

@misc{pith2026250600316,
  author       = {Pith},
  title        = {Pith review of: Active Learning via Regression Beyond Realizability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XZKQWSU3}},
  note         = {Machine review of arXiv:2506.00316}
}

abstract

We present a new active learning framework for multiclass classification based on surrogate risk minimization that operates beyond the standard realizability assumption. Existing surrogate-based active learning algorithms crucially rely on realizability$\unicode{x2014}$the assumption that the optimal surrogate predictor lies within the model class$\unicode{x2014}$limiting their applicability in practical, misspecified settings. In this work we show that under conditions significantly weaker than realizability, as long as the class of models considered is convex, one can still obtain a label and sample complexity comparable to prior work. Despite achieving similar rates, the algorithmic approaches from prior works can be shown to fail in non-realizable settings where our assumption is satisfied. Our epoch-based active learning algorithm departs from prior methods by fitting a model from the full class to the queried data in each epoch and returning an improper classifier obtained by aggregating these models.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

36 extracted references · 34 canonical work pages

[1]

Selective sampling algorithms for cost-sensitive multiclass prediction

Alekh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning , volume 28 of Proceedings of Machine Learning Research , pages 1220--1228, Atlanta, Georgia, USA, 17--19 Jun 2013. PMLR

work page 2013
[2]

Tsybakov

Jean-Yves Audibert and Alexandre B. Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics , 35(2), April 2007

work page 2007
[3]

Agnostic active learning

Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Proceedings of the 23rd International Conference on Machine Learning , pages 65--72, 2006

work page 2006
[4]

Bartlett, Michael I

Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association , 101(473):138--156, 2006

work page 2006
[5]

Bousquet

O. Bousquet. Concentration Inequalities and Empirical Processes Theory Applied to the Analysis of Learning Algorithms . PhD thesis, Biologische Kybernetik, 2002

work page 2002
[6]

Castro and Robert D

Rui M. Castro and Robert D. Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory , 54(5):2339--2353, 2008

work page 2008
[7]

Analysis of a greedy active learning strategy

Sanjoy Dasgupta. Analysis of a greedy active learning strategy. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems , volume 17. MIT Press, 2004

work page 2004
[8]

Coarse sample complexity bounds for active learning

Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. In Y. Weiss, B. Sch\" o lkopf, and J. Platt, editors, Advances in Neural Information Processing Systems , volume 18. MIT Press, 2005

work page 2005

Show all 36 references

[9]

Foster and Alexander Rakhlin

Dylan J. Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In Proceedings of the 37th International Conference on Machine Learning , pages 3199--3210, 2020

2020
[10]

Foster and Alexander Rakhlin

Dylan J. Foster and Alexander Rakhlin. Foundations of reinforcement learning and interactive decision making, 2023

2023
[11]

Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu

Dylan J. Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective. ArXiv , abs/2010.03104:6, 2020

2010 arXiv
[12]

Sebastian Seung, Eli Shamir, and Naftali Tishby

Yoav Freund, H. Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine Learning , 28(2-3):133--168, 1997

1997
[13]

A bound on the label complexity of agnostic active learning

Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th International Conference on Machine Learning ( ICML 2007) , pages 353--360, 2007

2007
[14]

Adaptive rates of convergence in active learning

Steve Hanneke. Adaptive rates of convergence in active learning. In Proceedings of the 22nd Annual Conference on Learning Theory ( COLT 2009) , pages 249--264, 2009

2009
[15]

Rates of convergence in active learning

Steve Hanneke. Rates of convergence in active learning. The Annals of Statistics , 39(1):333--361, 2011

2011
[16]

Theory of disagreement-based active learning

Steve Hanneke. Theory of disagreement-based active learning. Foundations and Trends® in Machine Learning , 7(2-3):131--309, 2014

2014
[17]

Nonparametric active learning, part 1: Smooth regression functions, 2017

Steve Hanneke. Nonparametric active learning, part 1: Smooth regression functions, 2017

2017
[18]

Decision theoretic generalizations of the pac model for neural net and other learning applications

David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and Computation , 100(1):78--150, 1992

1992
[19]

Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenkis dimension

David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenkis dimension. Journal of Combinatorial Theory, Series A , 69(2):217--232, 1995

1995
[20]

Daniel J. Hsu. Algorithms for Active Learning . PhD thesis, University of California, San Diego, 2010

2010
[21]

Minimax analysis of active learning

Steve Hanneke and Liu Yang. Minimax analysis of active learning. Journal of Machine Learning Research , 16(109):3487--3602, 2015

2015
[22]

Surrogate losses in passive and active learning

Steve Hanneke and Liu Yang. Surrogate losses in passive and active learning. Electronic Journal of Statistics , 13(2), January 2019

2019
[23]

Active learning for cost-sensitive classification, 2021

Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daume III, and John Langford. Active learning for cost-sensitive classification, 2021

2021
[24]

Rademacher complexities and bounding the excess risk in active learning

Vladimir Koltchinskii. Rademacher complexities and bounding the excess risk in active learning. Journal of Machine Learning Research , 11:2457--2485, 2010

2010
[25]

Nuances in margin conditions determine gains in active learning, 2022

Samory Kpotufe, Gan Yuan, and Yunfan Zhao. Nuances in margin conditions determine gains in active learning, 2022

2022
[26]

Active learning in the non-realizable case

Matti Kääriäinen. Active learning in the non-realizable case. In Algorithmic Learning Theory, 17th International Conference, ALT 2006 , volume 4264 of Lecture Notes in Computer Science , pages 63--77. Springer, 2006

2006
[27]

Bartlett, and Robert C

Wee Sun Lee, Peter L. Bartlett, and Robert C. Williamson. The importance of convexity in learning with squared loss. IEEE Transactions on Information Theory , 44(5):1974--1980, 1998

1974
[28]

Adaptivity to noise parameters in nonparametric active learning, 2017

Andrea Locatelli, Alexandra Carpentier, and Samory Kpotufe. Adaptivity to noise parameters in nonparametric active learning, 2017

2017
[29]

Learning with square loss: Localization through offset rademacher complexity

Tengyuan Liang, Alexander Rakhlin, and Karthik Sridharan. Learning with square loss: Localization through offset rademacher complexity. In Proceedings of The 28th Conference on Learning Theory , pages 1260--1285, 2015

2015
[30]

Plug-in approach to active learning

Stanislav Minsker. Plug-in approach to active learning. Journal of Machine Learning Research , 13:67--90, 2012

2012
[31]

Risk bounds for statistical learning

Pascal Massart and \'E lodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics , 34(5), October 2006

2006
[32]

Convergence of Stochastic Processes

David Pollard. Convergence of Stochastic Processes . Springer-Verlag, New York, 1984

1984
[33]

Tsybakov

Alexander Rakhlin, Karthik Sridharan, and Alexandre B. Tsybakov. Empirical entropy, minimax regret and minimax risk. Bernoulli , 23(2), May 2017

2017
[34]

Selective sampling and imitation learning via online regression

Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Selective sampling and imitation learning via online regression. In Advances in Neural Information Processing Systems , 2023

2023
[35]

Tsybakov

Alexander B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics , 32(1):135--166, 2004

2004
[36]

Efficient active learning with abstention, 2022

Yinglun Zhu and Robert Nowak. Efficient active learning with abstention, 2022

2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Selective sampling algorithms for cost-sensitive multiclass prediction

Alekh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning , volume 28 of Proceedings of Machine Learning Research , pages 1220--1228, Atlanta, Georgia, USA, 17--19 Jun 2013. PMLR

work page 2013

[2] [2]

Tsybakov

Jean-Yves Audibert and Alexandre B. Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics , 35(2), April 2007

work page 2007

[3] [3]

Agnostic active learning

Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Proceedings of the 23rd International Conference on Machine Learning , pages 65--72, 2006

work page 2006

[4] [4]

Bartlett, Michael I

Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association , 101(473):138--156, 2006

work page 2006

[5] [5]

Bousquet

O. Bousquet. Concentration Inequalities and Empirical Processes Theory Applied to the Analysis of Learning Algorithms . PhD thesis, Biologische Kybernetik, 2002

work page 2002

[6] [6]

Castro and Robert D

Rui M. Castro and Robert D. Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory , 54(5):2339--2353, 2008

work page 2008

[7] [7]

Analysis of a greedy active learning strategy

Sanjoy Dasgupta. Analysis of a greedy active learning strategy. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems , volume 17. MIT Press, 2004

work page 2004

[8] [8]

Coarse sample complexity bounds for active learning

Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. In Y. Weiss, B. Sch\" o lkopf, and J. Platt, editors, Advances in Neural Information Processing Systems , volume 18. MIT Press, 2005

work page 2005