Pith. sign in

REVIEW 3 major objections 3 minor 52 references

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random

T0 review · 3 major / 3 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 Massart-noised margin halfspaces are learnable with the same $\tilde O((\epsilon\gamma)^{-2})$ sample complexity as random-label noise, via a bounded inverse-margin update.

desk verdict Halfspace result is real and the proof holds; the GLM extension has a definitional gap that makes Theorem 4 false as stated, though the fix is straightforward. read the letter →

arxiv 2501.09851 v1 pith:T4KF4URZ submitted 2025-01-16 cs.LG cs.DS

Gautam Chandrasekaran , Vasilis Kontonis , Konstantinos Stavropoulos , Kevin Tian This is my paper · ORCID
classification cs.LGcs.DS MSC 68Q32
keywords Massartnoisehalfspacelearningmarginsamplecomplexityperceptrongeneralizedlinearmodelssemi-randomproper
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 attacks a gap in the theory of learning halfspaces: noisy labels that are only mildly adversarial (Massart noise, where each point is flipped with probability at most $\eta$) have historically required more samples than purely random label noise. The authors prove this gap is not real, at least for margin halfspaces, by giving a simple perceptron-style algorithm, the Perspectron, that reaches error $\eta+\epsilon$ with $\tilde O((\epsilon\gamma)^{-2})$ samples, the same rate as the best algorithms for the much milder random classification noise. They also extend the method to generalized linear models with a known link function, at a modest extra $\epsilon^{-2}$ cost. The argument turns on a bounded inverse-margin reweighting of the Leaky-ReLU gradient, which acts as a one-sample unbiased certificate of suboptimality. A reader should care because the result says the harder, more realistic Massart model is no harder sample-wise than the easier random-noise model, for these hypothesis classes.

What carries the argument

The central object is the bounded inverse-margin reweighted gradient $g(w;x,y)=(\beta\,\mathrm{sign}(w\cdot x)-y)x/(|w\cdot x|+\gamma)$ for halfspaces, and $(\sigma(w\cdot x)-y)x/(|w\cdot x|+\alpha\gamma)$ for GLMs. It is an unbiased estimator of a separating hyperplane: for every suboptimal $w$, its expectation has inner product at least $2\epsilon$ with $w-w^\star$. The denominator $|w\cdot x|+\gamma$ is the margin padding; it keeps the estimator's Euclidean norm bounded by $2/\gamma$ while preserving the certificate property, and it turns the hard conditional-sampling step of prior work into one reweighted sample. The second mechanism is the perceptron-style potential argument, which uses $\Phi_t=\mathbb{E}[\mathbf{1}_{\{\text{all iterates bad}\}}\|w^\star-w_t\|^2]$ to convert one-step drift into the sample and iteration bounds.

What would settle it

Take $\sigma(t)=t-1/2$, $w^\star=(1,0)$, $w=(0,1)$, $x_1=(1,0)$, $x_2=(-1,0)$, $\gamma=1/2$, and labels drawn with $\eta(x)=(1-|\sigma(w^\star\cdot x)|)/2$; this satisfies the paper's Definition 3. Numerically evaluate $\mathbb{E}[(\sigma(w\cdot x)-y)x/(|w\cdot x|+\alpha\gamma)]\cdot(w-w^\star)$ from Lemma 6: if it falls below $\epsilon$ while the error-gap condition holds, the GLM theorem as stated is false.

Watch

Extended reading notes

Core claim

Theorem 3 states that if examples come from an $\eta$-Massart halfspace model with margin $\gamma$, Algorithm 1 returns $w\in B_d$ with $\ell_{0-1}(w)\le \eta+\epsilon$ with probability at least $1-\delta$, using $O(\log(1/\delta)/(\epsilon^2\gamma^2)+\log(1/(\epsilon\gamma\delta))/\epsilon^2)$ samples and $O(d\log(1/\delta)\log(1/(\epsilon\gamma\delta))/(\epsilon^4\gamma^2))$ time. The load-bearing structural lemma (Lemma 2) shows that whenever $\ell_{0-1}(w)\ge \eta+\epsilon$, the vector $g(w)=\mathbb{E}[(\beta\,\mathrm{sign}(w\cdot x)-y)x/(|w\cdot x|+\gamma)]$, with $\beta=1-2\eta$, satisfies $g(w)\cdot(w-w^\star)\ge 2\epsilon$; because the denominator is at least $\gamma$, this certificate is bounded and estimable from a single sample. The update $w_{t+1}\leftarrow w_t-\lambda(\beta\,\mathrm{sign}(w_t\cdot x_t)-y_t)x_t/(|w_t\cdot x_t|+\gamma)$ is then analyzed through a perceptron-style potential $\|w^\star-w_t\|^2$, yielding the matching bound. For Massart GLMs, the same plan works with $\sigma(w\cdot x)-y$ in place of $\beta\,\mathrm{sign}(w\cdot x)-y$, and a smaller denominator $\alpha\gamma$ with $\alpha=\epsilon/(2-\epsilon)$, which costs an extra $\epsilon^{-2}$ factor in samples.

Load-bearing premise

The load-bearing premise is the margin: every example lies at distance at least $\gamma$ from the optimal boundary, and for the GLM extension the known link function must be nonnegative on $[0,1]$, a sign condition the paper's bounded-asymmetry definition does not explicitly state.

Editorial extensions

If this is right

  • The proper learner for $\gamma$-margin Massart halfspaces now matches the $\tilde O((\epsilon\gamma)^{-2})$ sample complexity of the best random-classification-noise learners.
  • The error target $\eta+\epsilon$, the known noise ceiling, is the right benchmark; lower bounds prevent competing with the true average noise rate, so matching this target is the meaningful resolution.
  • The same method yields a polynomial sample complexity for Massart generalized linear models with known link function, $\tilde O(\gamma^{-2}\epsilon^{-4})$, improving on the prior unspecified polynomial dependence.
  • The algorithm is proper and needs only $\eta$ up to an $\epsilon$ error; when $\eta$ is unknown, a standard discretization over $\beta=1-2\eta$ preserves the guarantees.

Reading between the lines

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

  • The inverse-margin padding is not tied to Leaky-ReLU; any convex surrogate whose reweighted excess equals the classification error could yield analogous certificates for other noise models, such as Tsybakov noise.
  • The extra $\epsilon^{-2}$ in the GLM bound looks like an artifact of the $\epsilon$-small padding $\alpha\gamma$; the paper's own appendix sketches two routes to remove it, so a plausible conjecture is that the true GLM rate is also $\tilde O((\epsilon\gamma)^{-2})$.
  • A practical reading is that the update needs only one pass over samples and one inner product per step, making the Perspectron a drop-in replacement for perceptron in noisy linear classification, though the paper reports no empirical tests.
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 / 3 minor

Summary. The paper studies PAC learning of gamma-margin halfspaces with Massart noise. It proposes the Perspectron (Algorithm 1), a perceptron-like update with inverse-margin reweighting, and proves that it learns with error at most eta + epsilon using O~(gamma^{-2} epsilon^{-2}) samples, matching the best known rates for random classification noise. The proof combines a reweighted separating-hyperplane certificate (Lemmas 1-2), a potential-based martingale argument (Lemma 3), and a validation step (Lemma 4). The paper also claims an extension to generalized linear models with a known link function under Massart noise (Definition 3, Lemma 6, Algorithm 2, Theorem 4), with sample complexity O~(gamma^{-2} epsilon^{-4}). The halfspace part is clean, self-contained, and appears correct; the GLM part has a genuine gap in the definition of the admissible link functions and is, as stated, false.

Significance. If the halfspace result stands, it resolves the motivating question in the affirmative and is a substantial improvement over prior proper learners under Massart noise, with explicit constants, high-probability bounds, and a simple algorithm. The inverse-margin reweighting certificate is a nice technical contribution. The GLM extension, if repaired, would be a meaningful generalization of prior work, but in its current form it is incorrect; the significance of the manuscript therefore currently rests primarily on Theorem 3.

major comments (3)
  1. [Definition 3 / Lemma 6] The proof of Lemma 6 silently requires sigma to be sign-compatible, but Definition 3 does not impose this. In the A-case, the proof replaces sigma(w* . x) by |sigma(w* . x)| sign(w* . x), which is an equality only when sigma has the same sign as its argument; in the B1-case, the inference |sigma(-w . x)| >= |sigma(w* . x)| from |w . x| >= |w* . x| and monotonicity again requires sigma(t) >= 0 for t >= 0. Definition 3 allows, for example, sigma(t) = -1, which satisfies |sigma(t)| - |sigma(-t)| = 0 with tau = 0. For this sigma, Theorem 4 is false as stated: with D_x uniform on {(1,0),(-1,0)}, w* = (1,0), and deterministic labels y = sign(w* . x), the update in Algorithm 2 is a positive multiple of (1,0) on the positive example and zero on the negative example, so the returned halfspace misclassifies the negative example with probability 1/2 while opt_RCN = tau = 0. The definition must add an explicit sign-compatibility condition, such as sigma(t) >= 0 for all t in [0,1], or the theorem must be restricted to the odd case of Definition 2.
  2. [Lemma 6 / Algorithm 2] The analysis applies sigma to w_t . x for iterates w_t that are never projected back to the unit ball, but sigma is only defined on [-1,1]. Lemma 6 states the result for arbitrary w in R^d, and Algorithm 2 does not maintain w_t in B_d, so w_t . x may leave the domain of sigma. Either the algorithm should project or otherwise constrain the iterates, or sigma should be extended to the real line; as written the GLM update and the claim "for any w in R^d" in Lemma 6 are not well-defined.
  3. [Claim 1 / Theorem 4] There is a threshold mismatch in the GLM potential argument. Claim 1 declares an iterate bad when its error is at least opt_RCN + tau + epsilon/2, but Lemma 6 only certifies progress epsilon when the error is at least opt_RCN + tau/2 + epsilon. At the Claim 1 threshold, Lemma 6 gives progress only about epsilon/2 (in the worst case tau = 0), while the potential calculation in Lemma 3 needs progress epsilon to make the stated T = 32/(epsilon^4 gamma^2) suffice. The displayed constants in Claim 1 therefore do not follow from the cited argument; the proof should be written out with the correct progress term and the resulting threshold and T adjusted.
minor comments (3)
  1. [Algorithm 2] Line 2 sets beta <- 1 - 2 eta, but eta is not defined in the GLM setting of Definition 3, and beta is never used in Algorithm 2; this line should be removed or clarified.
  2. [Definition 3] The paragraph after Definition 3 says the noise rate is upper bounded by (1 - sigma(w* . x))/2, but the definition uses (1 - |sigma(w* . x)|)/2; the absolute value should appear consistently.
  3. [Definition 3] The quantity tau is called a "constant shift" but it is an asymmetry parameter, not a shift; a less misleading name would help readers.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the halfspace result is derived from the Massart model and convexity, and the GLM extension has a correctness gap but not a circular one.

full rationale

The central derivation in Theorem 3 is self-contained. Lemma 2 expands the expected certificate under the Massart halfspace model and uses only the model's margin and noise-rate assumptions together with convexity of the Leaky-ReLU loss; no parameter is fitted to the target error eta + epsilon, and the perceptron-style potential argument in Lemma 3 tracks the squared distance to w* without importing the conclusion. The only external identity invoked, Claim 2.1 of [DGT19], is a parameter-free equality and comes from non-overlapping authors, so it is independent support rather than a self-citation chain. Self-citations to the certificate framework of [DKTZ20a, DKTZ24] appear only as motivation and are not load-bearing: the lemmas used in the proof are stated and proved in this paper. The GLM section contains a real mathematical gap, but it is not circularity: Definition 3 permits a non-decreasing sigma that is negative on [0,1], and Lemma 6's B1 case assumes |sigma(-w.x)| >= |sigma(w*.x)| from monotonicity on positive arguments, which requires sign-compatibility; for instance sigma == -1 satisfies Definition 3 with tau = 0 and breaks Theorem 4. This is an assumption/validity issue, not a reduction of a prediction to its inputs, so it does not raise the circularity score.

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

The central claim rests on the standard margin/Massart model assumptions and one cited identity from [DGT19]; no parameters are fitted to data, and no new entities are introduced. The hidden sign condition on sigma is the only unstated input.

assumptions (5)
  • standard math Claim 2.1 of [DGT19]: for all lambda >= 0, E_y[l_lambda(-yw dot x)] = (Pr[sign(w dot x) != y] - lambda) |w dot x|
    Used in Lemma 1 to relate the reweighted Leaky-ReLU loss to excess error; imported from prior work as a black box.
  • domain assumption Massart noise: eta(x) in [0, eta] for all x (Definition 1)
    Core distributional model; the certificate and potential arguments assume the conditional flip probability is bounded by eta.
  • domain assumption Margin: Pr[|w* dot x| < gamma] = 0 (Definitions 1 and 3)
    Ensures |w* dot x| >= gamma almost surely, used to bound the reweighted estimator norm and to prove Lemma 2 and Lemma 6.
  • domain assumption sigma(t) >= 0 for t in [0,1] (implicit in Definition 3)
    Lemma 6's B1 case uses monotonicity of |sigma| on positive arguments; this requires sigma nonnegative on [0,1], which Definition 3 does not state explicitly.
  • standard math Standard concentration inequalities (Hoeffding, union bound)
    Used in Lemma 4 for hypothesis selection and in deriving the sample complexity bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random." pith.science (2026). https://pith.science/paper/T4KF4URZ

@misc{pith2026250109851,
  author       = {Pith},
  title        = {Pith review of: Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T4KF4URZ}},
  note         = {Machine review of arXiv:2501.09851}
}
abstract

We study the problem of PAC learning $\gamma$-margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity $\widetilde{O}((\epsilon\gamma)^{-2})$ and achieves classification error at most $\eta+\epsilon$ where $\eta$ is the Massart noise rate. Prior works [DGT19,CKMY20] came with worse sample complexity guarantees (in both $\epsilon$ and $\gamma$) or could only handle random classification noise [DDK+23,KIT+23] -- a much milder noise assumption. We also show that our results extend to the more challenging setting of learning generalized linear models with a known link function under Massart noise, achieving a similar sample complexity to the halfspace case. This significantly improves upon the prior state-of-the-art in this setting due to [CKMY20], who introduced this model.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 50 canonical work pages

  1. [1]

    Efficient learning of linear separators under bounded noise

    Pranjal Awasthi, Maria - Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015 , volume 40 of JMLR Workshop and Conference Proceedings , pages 167--190. JMLR.org, 2015

    work page 2015

  2. [2]

    Angluin and P

    D. Angluin and P. Laird. Learning from noisy examples. Mach. Learn. , 2(4):343--370, 1988

    work page 1988

  3. [3]

    Arriaga and S

    R. Arriaga and S. Vempala. An algorithmic theory of learning: Robust concepts and random projection. In Proceedings of the 40 th Annual Symposium on Foundations of Computer Science (FOCS) , pages 616--623, New York, NY, 1999

    work page 1999

  4. [4]

    Frieze, Ravi Kannan, and Santosh S

    Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica , 22(1/2):35--52, 1998

    work page 1998

  5. [5]

    Dueling optimization with a monotone adversary

    Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, and Yuanyuan Yang. Dueling optimization with a monotone adversary. In International Conference on Algorithmic Learning Theory , volume 237 of Proceedings of Machine Learning Research , pages 221--243. PMLR , 2024

    work page 2024

  6. [6]

    A. Blum. Machine learning: My favorite results, directions, and open problems. In 44 th Symposium on Foundations of Computer Science (FOCS 2003) , pages 11--14, 2003

    work page 2003

  7. [7]

    Coloring random and semi-random k-colorable graphs

    Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. J. Algorithms , 19(2):204--234, 1995

    work page 1995

  8. [8]

    Learning linear threshold functions in the presence of classification noise

    Tom Bylander. Learning linear threshold functions in the presence of classification noise. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 1994 , pages 340--347. ACM , 1994

    work page 1994

Show all 52 references
  1. [9]

    Bylander

    T. Bylander. Worst-case analysis of the P erceptron and exponentiated update algorithms. Artificial Intelligence , 106, 1998

    1998

  2. [10]

    Non-convex matrix completion against a semi-random adversary

    Yu Cheng and Rong Ge. Non-convex matrix completion against a semi-random adversary. In Conference On Learning Theory, COLT 2018 , volume 75 of Proceedings of Machine Learning Research , pages 1362--1394. PMLR , 2018

    2018

  3. [11]

    Classification under misspecification: Halfspaces, generalized linear models, and evolvability

    Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , 2020

    2020

  4. [12]

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

    2008

  5. [13]

    Learning noisy perceptrons by a perceptron in polynomial time

    Edith Cohen. Learning noisy perceptrons by a perceptron in polynomial time. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97 , pages 514--523. IEEE Computer Society, 1997

    1997

  6. [14]

    Complexity theoretic limitations on learning halfspaces

    Amit Daniely. Complexity theoretic limitations on learning halfspaces. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 , pages 105--117. ACM , 2016

    2016

  7. [15]

    Kane, Puqian Wang, and Nikos Zarifis

    Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, and Nikos Zarifis. Information-computation tradeoffs for learning margin halfspaces with random classification noise. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023 , volume 195 of Proce...

    2023

  8. [16]

    Distribution-independent PAC learning of halfspaces with massart noise

    Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-independent PAC learning of halfspaces with massart noise. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , pages 4751--4762, 2019

    2019

  9. [17]

    Diakonikolas and D

    I. Diakonikolas and D. M. Kane. Hardness of learning halfspaces with massart noise. CoRR , abs/2012.09720, 2020

    2012 arXiv

  10. [18]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. A polynomial time algorithm for learning halfspaces with tsybakov noise. arXiv , 2020

    2020

  11. [19]

    Learning general halfspaces with general massart noise under the gaussian distribution

    Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. In Symposium on Theory of Computation , volume 54, 2022

    2022

  12. [20]

    Nearly tight bounds for robust proper learning of halfspaces with a margin

    Ilias Diakonikolas, Daniel Kane, and Pasin Manurangsi. Nearly tight bounds for robust proper learning of halfspaces with a margin. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alch\' e -Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Syste...

    2019

  13. [21]

    Diakonikolas, D

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

    2018

  14. [22]

    Forster decomposition and learning halfspaces with noise

    Ilias Diakonikolas, Daniel Kane, and Christos Tzamos. Forster decomposition and learning halfspaces with noise. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems , volume 34, pages 7732--77...

    2021

  15. [23]

    Diakonikolas, V

    I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference on Learning Theory, COLT , 2020

    2020

  16. [24]

    Diakonikolas, V

    I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with tsybakov noise. arXiv , 2020

    2020

  17. [25]

    Diakonikolas, V

    I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Non-convex SGD learns halfspaces with adversarial label noise. In Advances in Neural Information Processing Systems, NeurIPS , 2020

    2020

  18. [26]

    Learning general halfspaces with adversarial label noise via online gradient descent

    Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning , pages 5118--5141. PMLR, 2022

    2022

  19. [27]

    Diakonikolas, V

    I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Online Linear Classification with Massart Noise , 2024. Arxiv eprint: 2405.12958

    2024 arXiv

  20. [28]

    A near-optimal algorithm for learning margin halfspaces with massart noise

    Ilias Diakonikolas and Nikos Zarifis. A near-optimal algorithm for learning margin halfspaces with massart noise. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024 , 2024

    2024

  21. [29]

    Feldman, P

    V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami. New results for learning noisy parities and halfspaces. In 47 th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 563--574. IEEE Computer Society, 2006

    2006

  22. [30]

    Robust matrix sensing in the semi-random model

    Xing Gao and Yu Cheng. Robust matrix sensing in the semi-random model. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023 , 2023

    2023

  23. [31]

    Gollakota, P

    A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. Agnostically learning single-index models using omnipredictors. arXiv preprint arXiv:2306.10615 , 2023

    2023 arXiv

  24. [32]

    Hardness of learning halfspaces with noise

    Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noise. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006) , pages 543--552. IEEE Computer Society, 2006

    2006

  25. [33]

    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. Inf. Comput. , 100(1):78--150, 1992

    1992

  26. [34]

    Hopkins, D

    M. Hopkins, D. M. Kane, S. Lovett, and G. Mahajan. Noise-tolerant, reliable active classification with comparison queries. In COLT , 2020

    2020

  27. [35]

    Structured semidefinite programming for recovering structured preconditioners

    Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sidford, and Kevin Tian. Structured semidefinite programming for recovering structured preconditioners. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Pr...

    2023

  28. [36]

    M. J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM , 45(6):983--1006, 1998

    1998

  29. [37]

    Slam: Student-label mixing for distillation with unlabeled examples

    Vasilis Kontonis, Fotis Iliopoulos, Khoa Trinh, Cenk Baykal, Gaurav Menghani, and Erik Vee. Slam: Student-label mixing for distillation with unlabeled examples. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems ...

    2023

  30. [38]

    Kalai, A

    A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically learning halfspaces. In Proceedings of the 46 th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 11--20, 2005

    2005

  31. [39]

    Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian

    Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Semi-random sparse recovery in nearly-linear time. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023 , volume 195 of Proceedings of Machine Learning Research , pages 2352--2398. PMLR , 2023

    2023

  32. [40]

    Klivans, R

    A. Klivans, R. O'Donnell, and R. Servedio. Learning geometric concepts via G aussian surface area. In Proc.\ 49th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 541--550, Philadelphia, Pennsylvania, 2008

    2008

  33. [41]

    A. T. Kalai and R. Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT . Citeseer, 2009

    2009

  34. [42]

    Kearns, Robert E

    Michael J. Kearns, Robert E. Schapire, and Linda Sellie. Toward efficient agnostic learning. Mach. Learn. , 17(2-3):115--141, 1994

    1994

  35. [43]

    Long and R

    P. Long and R. Servedio. Learning large-margin halfspaces with more malicious noise. NIPS , 2011

    2011

  36. [44]

    Massart and E

    P. Massart and E. Nedelec. Risk bounds for statistical learning. Ann. Statist. , 34(5):2326--2366, October 2006

    2006

  37. [45]

    Nasser and S

    R. Nasser and S. Tiegel. Optimal SQ lower bounds for learning halfspaces with massart noise. In Conference on Learning Theory , volume 178 of Proceedings of Machine Learning Research , pages 1047--1074. PMLR , 2022

    2022

  38. [46]

    Rosenblatt

    F. Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review , 65:386--407, 1958

    1958

  39. [47]

    R. H. Sloan. Types of noise in data for concept learning. In Proceedings of the First Annual Workshop on Computational Learning Theory , COLT '88, pages 91--96, San Francisco, CA, USA, 1988. Morgan Kaufmann Publishers Inc

    1988

  40. [48]

    Shalev Shwartz, O

    S. Shalev Shwartz, O. Shamir, and K. Sridharan. Agnostically learning halfspaces with margin errors. TTI Technical Report, 2009

    2009

  41. [49]

    P. M. Vaidya. A new algorithm for minimizing convex functions over convex sets. Math.\ Prog. , 73(3):291--341, 1996

    1996

  42. [50]

    Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise

    Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In Conference on Learning Theory , pages 4526--4527. PMLR, 2021

    2021

  43. [51]

    Zhang, P

    Y. Zhang, P. Liang, and M. Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Proceedings of the 30 th Conference on Learning Theory, COLT 2017 , pages 1980--2022, 2017

    2017

  44. [52]

    Robustly learning single-index models via alignment sharpness

    Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning single-index models via alignment sharpness. CoRR , abs/2402.17756, 2024

    2024 arXiv

Pith tools

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