Pith. sign in

REVIEW 3 major objections 5 minor 39 references

Active Learning of General Halfspaces: Label Queries vs Membership Queries

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read Pool-based active label queries give no advantage over passive learning for halfspaces unless the pool is exponentially large; membership queries then achieve near-optimal query complexity.

desk verdict Strong lower bound, promising MQ algorithm, but the extreme-threshold branch of the proof has a systematic square-root error that needs fixing. read the letter →

arxiv 2501.00508 v1 pith:VBTCPEF2 submitted 2024-12-31 cs.LG

Ilias Diakonikolas , Daniel M. Kane , Mingchen Ma This is my paper · ORCID
classification cs.LG MSC 68Q3268T05
keywords activelearningmembershipquerieshalfspacesGaussianmarginalsagnosticlabelcomplexityqueryChowparameters
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 asks how much query access helps when learning general (potentially biased) halfspaces—signed linear classifiers $\mathrm{sign}(w\cdot x+t)$—under the standard Gaussian distribution, allowing arbitrary label noise. It establishes a sharp divide between two query models. In the classical pool-based active model, where the learner may only request labels of previously sampled points, no algorithm can do substantially better than passive learning unless the unlabeled pool is exponentially large: any learner needs $\tilde{\Omega}(d/(p\log m))$ label queries to achieve error $p/2$ on a $p$-biased halfspace, where $m$ is the pool size. With membership queries, where the learner can ask the label of any point in space, a computationally efficient algorithm achieves error $O(\mathrm{opt})+\epsilon$ using only $\tilde{O}(\min\{1/p,1/\epsilon\}+d\,\mathrm{polylog}(1/\epsilon))$ membership queries, even in the agnostic setting. Together these results show that the type of interaction—choosing arbitrary points versus choosing from a finite unlabeled sample—changes the query complexity of learning halfspaces qualitatively.

What carries the argument

The lower bound is carried by a decision-tree counting argument combined with the near-orthogonality of high-dimensional Gaussian sample points. For any $k$-tuple of pool points, with high probability their normalized Gram matrix is close to $dI$ when $k=O(d/(\log m)(t^*)^4)$; a random halfspace of bias $p$ labels all $k$ points negative with probability at most $(O(p\log(1/p)))^k$. Since an algorithm that finds $k$ negative examples in $r$ label queries has at most $\binom{r}{k}$ successful decision-tree paths, $r$ must be $\tilde{\Omega}(k/p)$ before success is possible, which yields the label-complexity lower bound. The upper bound runs on a different mechanism: estimate the bias $p$, grid-search the offset $t^*$, find a warm-start direction $w_0$ by querying one random negative example and using smoothed labels, then refine $(w,t)$ by projected gradient descent on a localized estimate of the Chow parameter vector $\mathbb{E}_{z\sim N(0,I)}[z\,h(z)]$, with a $(v,s,\sigma)$-rejection procedure keeping noise below the signal; candidate hypotheses are combined by a tournament. The workhorse identity (Fact 3.3) is that a Gaussian halfspace $h(x)=\mathrm{sign}(w\cdot x+t)$ has Chow parameter $\sqrt{2/\pi}\exp(-t^2/2)\,w$, so direction estimates can be read off from label queries whose cost depends on the threshold.

What would settle it

Run the initialization on a synthetic halfspace with a known $\epsilon$-noisy labeling, and measure how often a random negative example is both near the boundary and has smoothed-label disagreement at most $5\epsilon/p$; Lemma 3.5 says at least half, and a sub-constant rate would break the repetition guarantee. For the lower bound, simulate a proposed active learner on $m=\mathrm{poly}(d/\epsilon)$ Gaussian examples and count label queries required to reach error below $p/2$ on a random $p$-biased halfspace; the theorem predicts $\tilde{\Omega}(d/(p\log m))$ is necessary.

Watch

Extended reading notes

Core claim

The paper's central claim is that pool-based active label queries provide essentially no asymptotic advantage over passive learning for general halfspaces under Gaussian marginals, while membership queries provide near-optimal query efficiency even in the agnostic (nasty-noise) setting. Theorem 1.1 states that any active learner making fewer than $\tilde{\Omega}(d/(p\log m))$ label queries over $m$ i.i.d. Gaussian examples fails, with constant probability, to reach error $p/2$ for a $p$-biased halfspace; in particular, beating the passive label complexity $\tilde{O}(d/\epsilon)$ requires a pool of $2^{\mathrm{poly}(d)}$ unlabeled examples. Theorem 1.2 gives a polynomial-time membership-query algorithm that, with $M=\tilde{O}(\min\{1/p,1/\epsilon\}+d\,\mathrm{polylog}(1/\epsilon))$ queries, outputs a halfspace of error $O(\mathrm{opt})+\epsilon$ for every labeling function, where $\mathrm{opt}$ is the 0-1 loss of the optimal halfspace. The lower bound is information-theoretic and applies to every algorithm; the upper bound is constructive, agnostic, and runs in polynomial time. The two results together constitute a strong separation between the label-query and membership-query models for this class.

Load-bearing premise

The load-bearing premise is that a random negative example is, with at least constant probability, simultaneously close to the decision boundary and only mildly corrupted by label noise (Lemma 3.5), because the initialization's success and the polylog repetition in Algorithm 1 collapse if this event is sub-constant.

Editorial extensions

If this is right

  • If the lower bound is right, no pool-based active learner—regardless of computation—can avoid the passive $\tilde{\Omega}(d/\epsilon)$ label complexity for general halfspaces unless its unlabeled pool has size exponential in $d$.
  • If the upper bound is right, membership queries yield the first computationally efficient agnostic learner for general Gaussian halfspaces with query complexity $\tilde{O}(d\,\mathrm{polylog}(1/\epsilon))$ up to the unavoidable $\min\{1/p,1/\epsilon\}$ exploration term.
  • A direct corollary is a strong separation between query models: membership queries achieve $\tilde{O}(\min\{1/p,1/\epsilon\}+d\,\mathrm{polylog}(1/\epsilon))$, while label queries over an $m$-point pool require $\tilde{\Omega}(d/(p\log m))$.
  • If a small-class oracle supplies a random negative example, the same algorithm runs with only $\tilde{O}(d\,\mathrm{polylog}(1/\epsilon))$ membership queries, showing the $1/p$ term is an exploration cost rather than a learning cost.
  • The query complexity is nearly optimal in the agnostic setting, matching the $\Omega(d\log(1/\epsilon))$ information bound and the $\Omega((1/p)^{1-o(1)})$ small-class exploration bound.

Reading between the lines

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

  • A plausible broader lesson is that for high-dimensional Gaussian problems the value of interactivity lies in synthesizing new query points, not in selectively labeling an existing pool; replacing pool access with membership access changes the query complexity by an exponential factor in the pool size needed.
  • The lower bound's near-orthogonality mechanism suggests the same $\tilde{\Omega}(d/(p\log m))$ barrier should hold for any isotropic high-dimensional distribution whose samples are nearly pairwise orthogonal with high probability, while low-dimensional or strongly correlated data may restore the advantage of active label selection.
  • The paper leaves open whether the $\min\{1/p,1/\epsilon\}$ term can be removed without a small-class oracle under intermediate noise models such as bounded noise or margin conditions, and whether the upper bound can be tightened to the information-theoretic $d\log(1/\epsilon)$.
  • A practical testable corollary is that on Gaussian-like data with heavy label noise, algorithms that query labels at smoothed perturbations of one informative negative example should require far fewer labels than algorithms restricted to labeling points from the observed pool.
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.

Referee Report

3 major / 5 minor

Summary. The paper studies active learning of general (not necessarily homogeneous) halfspaces under the standard Gaussian distribution, comparing pool-based label queries with membership queries. The main negative result (Theorem 1.1) is an information-theoretic lower bound stating that any active learner over a pool of m unlabeled examples needs ~Omega(d/(p log m)) label queries to learn a p-biased halfspace to error p/2, so nontrivial improvements over passive learning require exponentially large pools. The main positive result (Theorem 1.2) is a computationally efficient agnostic membership-query learner with query complexity ~O(min{1/p, 1/eps} + d polylog(1/eps)) and error O(opt)+eps. The upper bound is built from a randomized localization / gradient-descent refinement of a warm start, together with a smoothed-label initialization procedure; the extreme-threshold case is deferred to Appendix D. The paper also claims near-optimality of the membership-query complexity via an informal reduction to HKL20.

Significance. If the results are correct, the paper resolves a natural open question by showing a strong separation between label-query and membership-query models for general halfspheres under Gaussian marginals, and it provides an essentially optimal agnostic MQ learner with polynomial time. The lower-bound argument via decision trees and Yao's principle is a genuine information-theoretic contribution, and the upper-bound machinery adapts known localization and smoothed-label techniques in a nontrivial way. The paper is also careful to rely on prior work (DKS18, DKTZ22, DKK+23) rather than assuming its own conclusions, so I see no circularity. However, as written the extreme-threshold branch of the MQ upper bound contains a systematic query-distribution inconsistency, and one key probability lemma is stated with an unsupported constant; these issues must be repaired before the main claims are established. The informal optimality claim for the MQ lower bound is also not proved in the manuscript.

major comments (3)
  1. [Appendix D, Algorithms 4-5 and Lemma D.2] The pseudocode queries y(A z - s w) (Algorithm 4 line 9; Algorithm 5 lines 10-12), but all localization analysis, including Lemma D.2 and the use of Lemma B.1, is for samples of the form A^{1/2} z - s v, whose marginal is N(-s v, A). With A = I - (1-sigma^2) w w^T, querying A z - s w produces covariance A^2, i.e., variance sigma^4 along w instead of sigma^2. Consequently the proof that the noise rate is at most 6 eps exp(s^2/2)/b and the comparisons with p(b,s) do not apply to the distribution actually queried. Because Theorem 1.2 relies on Algorithm 5 for the extreme-threshold branch (when eta log(1/eta) > 1/t), the membership-query upper bound is not proved as written. The fix appears to be replacing A by A^{1/2} in the query points, but the change must be made consistently in both algorithms and the proof.
  2. [Lemma 3.5 and Appendix C.1] The lemma asserts that a random negative example is simultaneously eta(x) <= 5 eps/p and near the decision boundary with probability at least 1/2. The proof obtains P(eta(x)<=5 eps/p) >= 3/4 by Markov's inequality and P(w* . x in (-t*-1/t*,-t*)) >= 1 - e^{-1} - 2/C; the union bound gives only about 0.38 for large C, not 1/2. The quantitative statement as written is false. Since Algorithm 1 repeats the initialization polylog(1/eps) times, a constant success probability would still suffice, but the lemma and its uses in Theorems 3.4 and D.1 need to be restated with the correct constant and the repetition count adjusted accordingly.
  3. [Section 1, 'Optimality of Query Complexity'] The paper claims the MQ query complexity in Theorem 1.2 is essentially optimal and gives an Omega((1/p)^{1-o(1)}) lower bound 'deduced' from HKL20 by an argument 'essentially identical' to the unit-ball case. This is only a sketch; no formal lower-bound theorem for the Gaussian setting is stated or proved, and the approximation of the Gaussian by the sphere is not quantified. If the near-optimality claim is to be part of the paper's contribution, it should be stated as a theorem with a proof; otherwise the wording should be weakened.
minor comments (5)
  1. [Theorem 1.1 statement] The theorem says a learner making 'less than ~O(d/(p log m))' queries cannot succeed; this should be 'less than ~Omega(d/(p log m))' or equivalently 'at most O(d/(p log m))'. The proof's final display gives the correct threshold r <= O(k/p log(1/p)), so this appears to be a typographical slip in the theorem statement.
  2. [Lemma D.2 statement] The two clauses in Lemma D.2 are asymmetric: the first says 'the probability that ps > p(b,s)/4 is at most 1/2', while the second says 'the probability that ps > p(b,s)/2 is at least 29/30'. The first condition should presumably be 'ps < p(b,s)/4' or the thresholds should be aligned. Please clarify.
  3. [Appendix C.2] In the second case of the proof of Theorem 3.4, the sentence 'Since u0 is close to E_{z~N(0,I)} z' is missing the subscript: it should be 'u0 is close to E_{z~N(0,I)} z \tilde{h}(z)'.
  4. [Appendix F, Definition F.1] Definition F.1 says the small-class oracle draws (x,y) ~ D restricted to y=1 and returns x, but the surrounding text and the name EX^{(-)} indicate the oracle should return negative examples (y=-1). This sign inconsistency should be fixed, as it matters for the implementation claims.
  5. [Throughout] There are several typographical errors, e.g., 'Unfortinately' at the end of Section 3.2 and the garbled inequality display near Equation (5) in Appendix F with repeated terms. A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the lower bound is an adversary/Yao construction against external benchmarks and the upper bound is a constructive algorithm; same-author citations are used as independent lemmas, not as self-fulfilling premises.

full rationale

No circular step meets the evidentiary bar in this paper. The active-learning lower bound (Section 2) is proved by a Yao/decision-tree adversary: Lemmas 2.1-2.3 establish that no query strategy can find k negative examples with fewer than Omega~(k/p) queries under a random halfspace, and the target bound is obtained by contradiction. This is not a fitted parameter renamed as a prediction, and no definition of the target quantity is imported into its own proof. The membership-query upper bound (Theorem 1.2) is a constructive algorithm (Algorithm 1 plus initialization and refinement subroutines) whose guarantee is proved from stated assumptions; it does not assume opt <= eps or a p-biased halfspace correctness as an input to itself. The paper does rely on several same-author prior results: the (v,s,sigma)-rejection procedure and localization lemmas from DKS18, Fact B.4 from DKTZ22, Lemma A.1 from DKK+23a, and a beta-distribution fact from KMT24c. These are self-citations, but each is an independent published statement with its own stated assumptions and proof, and none of them asserts the present paper's target theorem; under the stated rules they count as real evidence rather than circularity. The most serious flagged concerns are internal correctness/consistency issues, not circular reductions: Lemma 3.5's claimed probability at least 1/2 for the simultaneous good-boundary and low-smoothed-noise event appears not to follow from the displayed union bound (which would give a smaller constant), and Appendix D's Algorithms 4-5 query y(A z - s w) while Fact 3.2 and the surrounding analysis are written for A^{1/2} z - s v, so the extreme-threshold branch of Theorem 1.2 may be unproved as written. Both are correctness risks that should be investigated, but neither is a case of a derivation reducing to its own inputs by construction. The score of 2 reflects the presence of multiple same-author citations and the imported localization framework, not a load-bearing circular dependency.

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

The central results rest on standard Gaussian identities and on localization and smoothing lemmas borrowed from prior work. No new entities are introduced, and no parameter is fitted to data. The main unstated background facts are the Chow-vector identity, the rejection-procedure sampling lemma from DKS18, Gaussian tail bounds, and the noise-correlation bound from DKTZ22. These are external benchmarks rather than circular inputs.

assumptions (7)
  • standard math Fact 3.3: E_{x~N(0,I)}[x sign(w·x+t)] = sqrt(2/pi) exp(-t^2/2) w.
    Exact Chow-vector identity for Gaussian halfspaces, used throughout to extract w* from query expectations; stated in Section 3.1.1 and proved in cited literature.
  • domain assumption Lemma B.1 (DKS18): the (v,s,sigma)-rejection procedure accepts with probability sigma exp(-s^2/(2(1-sigma^2))) and the accepted distribution is N(-sv, I-(1-sigma^2)vv^T).
    The localization technique used by Algorithm 3 and Algorithm 5 is built on this lemma; it is quoted from DKS18 without proof in this paper.
  • standard math Fact B.3 (Komatsu inequality): Gaussian tail bounds for halfspace bias.
    Used in Lemma 2.2, Lemma 3.4, and Appendix D to relate thresholds to biases.
  • domain assumption Fact B.4 (DKTZ22): for orthogonal u,w, E[|u·x| 1{S}] <= 2 sqrt(e) Pr(S) sqrt(log(Pr(w·x in B)/Pr(S))).
    Used to bound the noise-induced error in the gradient estimate in Lemma 3.4; quoted from DKTZ22.
  • domain assumption Fact B.5 (DKS18): Pr(sign(w*·x+t) != sign(w·x+t)) <= sin(theta(w,w*)) 2 exp(-t^2/2).
    Used in Theorem 3.1 to convert angular error into 0-1 error; quoted from DKS18.
  • domain assumption Lemma D.1 (DKS18): the randomized-threshold rejection method has expected acceptance probability at most sigma/b.
    Used in the extreme-threshold initialization in Appendix D to control noise amplification; quoted from DKS18.
  • standard math Yao's minimax principle.
    Basis of the lower-bound proof's reduction from randomized algorithms to distributions over hard halfspaces.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Active Learning of General Halfspaces: Label Queries vs Membership Queries." pith.science (2026). https://pith.science/paper/VBTCPEF2

@misc{pith2026250100508,
  author       = {Pith},
  title        = {Pith review of: Active Learning of General Halfspaces: Label Queries vs Membership Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VBTCPEF2}},
  note         = {Machine review of arXiv:2501.00508}
}
abstract

We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces under the Gaussian distribution on $R^d$ in the presence of some form of query access. In the classical pool-based active learning model, where the algorithm is allowed to make adaptive label queries to previously sampled points, we establish a strong information-theoretic lower bound ruling out non-trivial improvements over the passive setting. Specifically, we show that any active learner requires label complexity of $\tilde{\Omega}(d/(\log(m)\epsilon))$, where $m$ is the number of unlabeled examples. Specifically, to beat the passive label complexity of $\tilde{O} (d/\epsilon)$, an active learner requires a pool of $2^{poly(d)}$ unlabeled samples. On the positive side, we show that this lower bound can be circumvented with membership query access, even in the agnostic model. Specifically, we give a computationally efficient learner with query complexity of $\tilde{O}(\min\{1/p, 1/\epsilon\} + d\cdot polylog(1/\epsilon))$ achieving error guarantee of $O(opt)+\epsilon$. Here $p \in [0, 1/2]$ is the bias and $opt$ is the 0-1 loss of the optimal halfspace. As a corollary, we obtain a strong separation between the active and membership query models. Taken together, our results characterize the complexity of learning general halfspaces under Gaussian marginals in these models.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 35 canonical work pages

  1. [1]

    Awasthi, M

    P. Awasthi, M. F. Balcan, and P. M. Long. The power of localization for efficiently learning linear separators with noise. J. ACM , 63(6):50:1--50:27, 2017

    work page 2017

  2. [2]

    D. Angluin. Queries and concept learning. Machine learning , 2:319--342, 1988

    work page 1988

  3. [3]

    Balcan, A

    M.-F. Balcan, A. Broder, and T. Zhang. Margin based active learning. In International Conference on Computational Learning Theory , pages 35--50. Springer, 2007

    work page 2007

  4. [4]

    Bressan, N

    M. Bressan, N. Cesa-Bianchi, S. Lattanzi, A. Paudice, and M. Thiessen. Active learning of classifiers with label and seed queries. Advances in Neural Information Processing Systems , 35:30911--30922, 2022

    work page 2022

  5. [5]

    Balcan, S

    M.-F. Balcan, S. Hanneke, and J. W. Vaughan. The true sample complexity of active learning. Machine learning , 80:111--139, 2010

    work page 2010

  6. [6]

    Balcan and P

    M.-F. Balcan and P. Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory , pages 288--316. PMLR, 2013

    work page 2013

  7. [7]

    Dasgupta

    S. Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems , 17, 2004

    work page 2004

  8. [8]

    Dasgupta

    S. Dasgupta. Coarse sample complexity bounds for active learning. Advances in neural information processing systems , 18, 2005

    work page 2005

Show all 39 references
  1. [9]

    Dasgupta and A

    S. Dasgupta and A. Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms , 22(1):60--65, 2003

    2003

  2. [10]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, V. Kontonis, S. Liu, and N. Zarifis. Efficient testable learning of halfspaces with adversarial label noise. In Proceedings of the 37th International Conference on Neural Information Processing Systems , pages 39470--39490, 2023

    2023

  3. [11]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Agnostically learning multi-index models with queries. arXiv preprint arXiv:2312.16616 , 2023. Conference version in FOCS'24

    2023 arXiv

  4. [12]

    Dasgupta, A

    S. Dasgupta, A. T. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning. In Learning Theory: 18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005. Proceedings 18 , pages 249--263. Springer, 2005

    2005

  5. [13]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polynomial regression for agnostic learning under gaussian marginals in the SQ model. In Proceedings of The 34 th Conference on Learning Theory, COLT , 2021

    2021

  6. [14]

    Diakonikolas, D

    I. Diakonikolas, D. Kane, and L. Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. In International Conference on Machine Learning , pages 7922--7938. PMLR, 2023

    2023

  7. [15]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, and A. Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 1061--1073, 2018

    2018

  8. [16]

    Diakonikolas, V

    I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning , pages 5118--5141. PMLR, 2022

    2022

  9. [17]

    Diakonikolas, D

    I. Diakonikolas, D. Kane, and N. Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems , 33:13586--13596, 2020

    2020

  10. [18]

    Diakonikolas, M

    I. Diakonikolas, M. Ma, L. Ren, and C. Tzamos. Fast co-training under weak dependence via stream-based active learning. In Forty-first International Conference on Machine Learning , 2024

    2024

  11. [19]

    V. Feldman. On the power of membership queries in agnostic learning. The Journal of Machine Learning Research , 10:163--182, 2009

    2009

  12. [20]

    Freund and R

    Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences , 55(1):119--139, 1997

    1997

  13. [21]

    Freund, H

    Y. Freund, H. S. Seung, E. Shamir, and N. Tishby. Selective sampling using the query by committee algorithm. Machine learning , 28:133--168, 1997

    1997

  14. [22]

    Hanneke et al

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

    2014

  15. [23]

    Hopkins, D

    M. Hopkins, D. Kane, and S. Lovett. The power of comparisons for actively learning linear classifiers. Advances in Neural Information Processing Systems , 33:6342--6353, 2020

    2020

  16. [24]

    Hopkins, D

    M. Hopkins, D. Kane, S. Lovett, and G. Mahajan. Point location and active learning: Learning halfspaces almost optimally. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1034--1044. IEEE, 2020

    2020

  17. [25]

    Hanneke and L

    S. Hanneke and L. Yang. Minimax analysis of active learning. J. Mach. Learn. Res. , 16(1):3487--3602, 2015

    2015

  18. [26]

    D. M. Kane, S. Lovett, S. Moran, and J. Zhang. Active classification with comparison queries. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 355--366. IEEE, 2017

    2017

  19. [27]

    S. R. Kulkarni, S. K. Mitter, and J. N. Tsitsiklis. Active learning using arbitrary binary valued queries. Machine Learning , 11:23--35, 1993

    1993

  20. [28]

    Kontonis, M

    V. Kontonis, M. Ma, and C. Tzamos. Active classification with few queries under misspecification. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024. ://openreview.net/forum?id=Ma0993KZlq

    2024

  21. [29]

    Kontonis, M

    V. Kontonis, M. Ma, and C. Tzamos. Active learning with simple questions. In The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada , volume 247 of Proceedings of Machine Learning Research , pages 3064--3098. PMLR , 2024. ://proceedin...

    2023

  22. [30]

    Kontonis, M

    V. Kontonis, M. Ma, and C. Tzamos. The gain from ordering in online learning. Advances in Neural Information Processing Systems , 36, 2024

    2024

  23. [31]

    McCallum, K

    A. McCallum, K. Nigam, et al. Employing em and pool-based active learning for text classification. In ICML , volume 98, pages 350--358. Citeseer, 1998

    1998

  24. [32]

    Rosenblatt

    F. Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review , 65(6):386, 1958

    1958

  25. [33]

    J. Shen. On the power of localized perceptron for label-optimal learning of halfspaces with adversarial noise. In International Conference on Machine Learning , pages 9503--9514. PMLR, 2021

    2021

  26. [34]

    L. Valiant. A theory of the learnable. Communications of the ACM , 27(11):1134--1142, 1984

    1984

  27. [35]

    L. G. Valiant. A theory of the learnable. In Proc.\ 16th Annual ACM Symposium on Theory of Computing (STOC) , pages 436--445. ACM Press, 1984

    1984

  28. [36]

    V. N. Vapnik. The support vector method. In International conference on artificial neural networks , pages 261--271. Springer, 1997

    1997

  29. [37]

    Vershynin

    R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi:10.1017/9781108231596

    2018 doi

  30. [38]

    Yan and C

    S. Yan and C. Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems , 30, 2017

    2017

  31. [39]

    write newline

    " write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence '...

Pith tools

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