betaFeedback

WorksMathematics

Rare-Tail Statistics For Learning Biased Gaussian Halfspaces with Label Noise

Abstract

We revisit the classical problem of learning general Gaussian halfspaces in the presence of label noise, with particular focus on the large-bias regime, where information-computation gaps are conjectured in several standard label-noise models. Concretely, we present and analyze the rare-tail mean estimator, an extremely simple one-shot statistic that averages only the observed minority class. In the large-bias regime, classical Averaging (Servedio, 1999) and related global first-moment statistics are provably suboptimal, while the rare-tail mean estimator recovers the target halfspace direction at the information-theoretic sample rate (modulo log factors) under a broad class of label noise models, including probit noise and margin-dependent noise with very slow decay away from the boundary. Notably, our guarantees allow labels arbitrarily close to the decision boundary to be nearly random, while still giving strong directional recovery from a small number of samples. The estimator also cleanly interpolates between the noiseless and noisy regimes: without noise, it attains the same sample rate as classical separability-based methods for realizable halfspaces, and under low noise, or noise that decays away from the boundary, it keeps this rate even after linear separability has been destroyed. As an application, we consider a two-stage curriculum in which source samples, whose noise may be arbitrarily close to 1/21/2 near the boundary and decay very slowly away from it, precede target samples, whose noise flips every label at the same rate, i.e., random classification noise (RCN). Since both stages share the same Bayes optimal halfspace, our estimator supplies the directional warm start needed by existing refinement routines, and together they learn the RCN target at the information-theoretic sample rate in the large-bias regime, up to log factors.

Introduction

A recurring theme in learning theory is that provable guarantees can be highly sensitive to the structure of label noise. The classical random classification noise model (RCN), in which every label is independently flipped at a fixed rate, is straightforward to analyze, and has played a foundational role in the theory of noisy halfspace learning [2]. However, even mild departures from this model can change the statistical and computational behavior of classification problems. For halfspaces, allowing the corruption rate to vary with the instance, or with the margin to the decision boundary, has led to substantially different algorithms and strong statistical-query lower bounds [13, 31, 17]. In this work we revisit a particularly sharp instance of this phenomenon: learning an affine Gaussian halfspace under label noise in the large-bias regime.

Concretely, we observe i.i.d. labeled examples (X,Y)(X,Y) with X∼N(0,Id)X \sim\mathcal{N}(0,I_d), Y∈{+1}Y \in\{+1\}, and an unknown target separator f⋆(x)=sign⁡(m(x))f^\star(x) = \operatorname{sign}(m(x)), where m(x)=⟨w⋆,x⟩+t⋆m(x) = \langle w^\star,x\rangle+ t^\star is the signed margin, and w⋆∈Sd−1w^\star\in S^{d-1}, t⋆∈Rt^\star\in\mathbb{R}. Our goal is to output a halfspace whose excess risk over f⋆f^\star is at most a target accuracy ε\varepsilon.

For ease of exposition, assume the threshold t⋆>0t^\star> 0 (the same ideas apply to t⋆<0t^\star< 0 by symmetry). Then, the halfspace has bias p=min⁡{P(f⋆(X)=−1),P(f⋆(X)=+1)}=Φ(−t⋆)p = \min\{\mathbb{P}(f^\star(X) = -1), \mathbb{P}(f^\star(X) = +1)\} = \Phi(-t^\star), where Φ(⋅)\Phi(\cdot) is the usual Gaussian CDF. Conditioned on X=xX = x, the observed label satisfies Y=f⋆(x)Y = f^\star(x) with probability 1−g(∣m(x)∣)1-g(|m(x)|) and Y=−f⋆(x)Y = -f^\star(x) with probability g(∣m(x)∣)g(|m(x)|), where g:[0,∞)→[0,1/2]g : [0,\infty) \to[0,1/2] is nonincreasing. This margin-dependent noise profile, going back to Bylander’s [9] monotonic-noise model for linear threshold functions, interpolates between the flat η\eta-RCN model, where g(⋅)=ηg(\cdot) = \eta and every label is flipped at the same rate, and boundary-local noise, where corruption is concentrated near the decision boundary and decays away from it. The latter describes a realistic annotation regime, in which labels far from the boundary are more reliable, while labels near the boundary may be close to random. Crowdsourced labels, for example from Amazon Mechanical Turk (AMT), behave this way. Annotators tend to agree on prototypical instances, which we can think of as points far from the decision boundary, and their labels become nearly random on ambiguous instances close to the separator [36, 6]. In contrast, η\eta-RCN describes errors that do not depend on the instance at all, such as labels from annotators who answer without looking at the samples [32].

The large-bias regime is where the distinction between flat and boundary-local noise becomes most pronounced. When t⋆>0t^\star> 0 is large, the true negative class has mass p=Φ(−t⋆)≪1p = \Phi(-t^\star) \ll1, and most samples lie deep in the positive region. Conditioning on the positive side removes only a set of mass pp, so a positive sample looks almost like a draw from N(0,Id)\mathcal{N}(0,I_d) and says little about the orientation of the separator. The negative samples, on the other hand, all come from the thin Gaussian tail cut off by the separator, so where they lie is tied directly to the orientation of the halfspace. In the absence of noise, conditioning on this tail is extremely favorable: if X=Zw⋆+X⊥X = Z w^\star+ X_\perp with Z=⟨w⋆,X⟩∼N(0,1)Z = \langle w^\star, X\rangle\sim\mathcal{N}(0,1) and X⊥∼N(0,Id−w⋆w⋆T)X_\perp\sim\mathcal{N}(0,I_d-w^\star{w^\star}^{T}), then the event Y=−1Y=-1 is simply {Z<−t⋆}\{Z<-t^\star\}. Conditioning on this event then shifts the ZZ coordinate, but leaves the orthogonal directions unchanged in distribution. Consequently, the signal E[X∣Y=−1]\mathbb{E}[X \mid Y=-1] is collinear with −w⋆-w^\star and has large norm Θ(t⋆)\Theta(t^\star) relative to the unit variance noise in every direction.

This suggests an extremely simple estimator: average the examples with the empirically rarer label and orient the resulting vector according to that label. We call this the rare-tail direction estimator (Algorithm 1). This is essentially a variant of Servedio’s classical Averaging algorithm [33], with the labels centered at the majority label, so that the majority samples, which carry noise but no additional signal, drop out of the average. The difference is small for homogeneous halfspaces, but striking for affine ones: in the noiseless biased benchmark discussed above, this rare-tail statistic reaches O(1/t⋆)O(1/t^{\star}) angular precision at the information-theoretically optimal O~(d/p)\widetilde{O}(d/p) sample rate, whereas the global Average statistic requires O~(d/p2)\widetilde{O}(d/p^{2}) samples to reach the same precision (Figure 1).

A 2D cartoon of the noiseless biased regime

Figure 1. A 2D cartoon of the noiseless biased regime. The solid black line is the true boundary and the point −t⋆w⋆-t^\star w^\star is its closest point to the origin. The dashed gray axes depict the decomposition X=Zw⋆+X⊥X = Z w^\star+ X_\perp, and the colored dashed separators are drawn through the same point −t⋆w⋆-t^\star w^\star to isolate directional error. Panel (a) uses the empirical Average moment, while panel (b) uses the empirical minority mean. For the same sample budget n=O~(d/p)n = \widetilde{O}(d/p), the minority mean typically achieves O~(1/t⋆)\widetilde{O}(1/t^\star)-scale angular distance to w⋆w^\star, while the Average estimator typically only reaches O~(1/(t⋆p))\widetilde{O}(1/(t^\star\sqrt{p}))-scale, which explains the larger angle in (a) compared to (b). The signal magnitude of the Average moment is smaller by a 2p2p factor, hence the shorter arrow in (a), while its orthogonal noise is smaller only by a p\sqrt{p} factor, since it also sums over the majority samples.

It remains to understand whether this geometric intuition survives when the labels are unreliable. We find that the answer depends on the shape of the noise profile, as opposed to just the amount of noise there is. In particular, constant-rate flat noise profiles destroy the rare-tail advantage. Under η\eta-RCN, points far inside the majority region are flipped into the observed negative class at the same rate as points near the boundary. In the large-bias regime, this creates a constant-rate stream of false negatives from the Gaussian bulk that dilute the signal, since the observed negative class is no longer a rare tail event, but a mixture of the true tail and mislabeled majority points. Boundary-local noise can produce just as many false negatives, even far more than the true tail, but these are drawn preferentially from near the separator, which, in the large-bias regime, lies far from the origin, in the direction −w⋆-w^{\star}. Therefore, the observed negative class is no longer the true tail, yet the false negatives themselves pull its mean along −w⋆-w^{\star}, thereby turning label noise into signal. The obstruction is therefore not inherent to label noise itself, but to the flatness of the noise profile.

The central question of the paper is whether this one-shot statistic retains its geometric advantage when the noise is not flat, but is otherwise as severe as possible.

We answer this question in the affirmative for a broad class of noise profiles that satisfy a mild regularity condition. This condition, which we call regular variation, rules out RCN-like flat plateaus, but includes noise models that may force random labels close to the decision boundary, but have very slow decay with distance to it. In particular, it includes canonical boundary-local models such as probit noise, which permits the flip probability near the boundary to be arbitrarily close to 1/21/2. Our main theorem shows that, under this condition, the rare-tail direction estimator recovers w⋆w^{\star} to O(1/t⋆)O(1/t^{\star}) angular accuracy using the same leading sample scale as the noiseless regime. Moreover, this is exactly the angular scale needed in the large-bias regime. Indeed, when p=Θ(ε)p=\Theta(\varepsilon), a direction within O(1/t⋆)O(1/t^{\star}) and a correctly chosen threshold already yield ε\varepsilon excess risk. A one-dimensional threshold search along the recovered direction (Algorithm 2) then gives a complete learner that runs in nearly linear time.

Isolating the shape of the noise profile as the obstruction also sheds light on a known computational barrier for learning biased Gaussian halfspaces under RCN. Diakonikolas et al. [20] give efficient algorithms for η\eta-RCN, but in the critical regime p=Θ(ε)p=\Theta(\varepsilon), their sample complexity has a leading O~(d/ε2)\widetilde{O}(d/\varepsilon^{2}) term, while the information-theoretic rate is O~(d/ε)\widetilde{O}(d/\varepsilon). They also give a statistical-query lower bound, suggesting that this quadratic dependence is unavoidable for efficient learners that only see RCN samples. Our analysis suggests where this barrier comes from, namely, the search for a warm start in the presence of constant-rate flat noise. As discussed above, flat noise buries much of the signal, while the same halfspace is easy to warm-start from boundary-local noisy labels. This is also the only part where flatness meaningfully affects learning: given a direction within O(1/t⋆)O(1/t^{\star}) of w⋆w^{\star}, the threshold is a one-dimensional learning problem, and the local refinement procedure of Diakonikolas et al. [20] from this warm-start is sample-efficient, even under RCN.

This suggests a way around the barrier: obtain the warm start from labels whose noise is not flat, and use the RCN samples only for the remaining steps. Strategies of this kind, in which a learner sees data in stages, starting from samples where the signal is easier to extract, have long been used in empirical machine learning under the name of curriculum learning [7], including for training on noisy labels, where the curriculum favors examples whose labels are more likely to be correct [24, 27]. Our two-stage approach serves as a mathematical model of curriculum learning for noisy halfspaces, where both stages share the Gaussian marginal and Bayes-optimal halfspace, but differ only in their label noise. The boundary-local source stage is not a uniformly easier version of the target, since near the boundary its labels may be even noisier than the target’s. Instead, it resembles careful annotators, whose mistakes concentrate on ambiguous instances, as in the crowdsourcing example above. In contrast, the η\eta-RCN target stage resembles a pool in which each label, with probability 2η2\eta, comes from an annotator who answers at random, without looking at the instance. Our curriculum learner Algorithm 1 RARE-TAIL DIRECTION ESTIMATOR

Require: Samples S={(Xi,Yi)}i=1NS = \{(X_i,Y_i)\}_{i=1}^N with Xi∈RdX_i \in\mathbb{R}^d and Yi∈{±1}Y_i \in\{\pm1\}

Ensure: A unit vector w^∈Sd−1\widehat{w} \in\mathbb{S}^{d-1} and empirical rare label y^rt\widehat{y}_{\mathrm{rt}}

1: N+←∑i=1N1{Yi=+1},N−←∑i=1N1{Yi=−1}N_+ \leftarrow\sum_{i=1}^N \mathbf{1}\{Y_i=+1\},\quad N_- \leftarrow\sum_{i=1}^N \mathbf{1}\{Y_i=-1\} 2: y^rt←−1\widehat{y}_{\mathrm{rt}} \leftarrow-1 if N−≤N+N_- \leq N_+, and y^rt←+1\widehat{y}_{\mathrm{rt}} \leftarrow+1 otherwise 3: Irt←{i∈[N]:Yi=y^rt}I_{\mathrm{rt}} \leftarrow\{i \in[N] : Y_i=\widehat{y}_{\mathrm{rt}}\} 4: if Irt=∅I_{\mathrm{rt}}=\varnothing then 5: &nbsp;&nbsp;&nbsp;&nbsp;return any fixed unit vector and y^rt\widehat{y}_{\mathrm{rt}} 6: end if 7: μ^rt←∣Irt∣−1∑i∈IrtXi\widehat{\mu}_{\mathrm{rt}} \leftarrow|I_{\mathrm{rt}}|^{-1}\sum_{i\in I_{\mathrm{rt}}}X_i 8: if μ^rt=0\widehat{\mu}_{\mathrm{rt}}=0 then 9: &nbsp;&nbsp;&nbsp;&nbsp;return any fixed unit vector and y^rt\widehat{y}_{\mathrm{rt}} 10: end if 11: w^←y^rtμ^rt/∥μ^rt∥2\widehat{w} \leftarrow\widehat{y}_{\mathrm{rt}}\widehat{\mu}_{\mathrm{rt}}/\|\widehat{\mu}_{\mathrm{rt}}\|_2 12: return (w^,y^rt)(\widehat{w},\widehat{y}_{\mathrm{rt}})

runs the rare-tail estimator on the source stage to obtain a warm start, and then uses target RCN samples to estimate the threshold and refine the direction locally, following Diakonikolas et al. [20]. Since the learner also sees the source stage, the statistical-query lower bound does not apply, even though the final guarantee is measured on the RCN target.

Our Results

We summarize the main guarantees. Throughout, p=Φ(−t⋆)p=\Phi(-t^\star) denotes the bias of the halfspace under the convention t⋆>0t^\star>0, and our primary regime is the critical large-bias regime p=Θ(ε)p=\Theta(\varepsilon).

Our first result shows that the rare-tail direction estimator obtains the same leading sample scale as in the noiseless benchmark for a broad class of noise profiles that satisfy a mild regularity condition, which we call regular-variation (Definition 2.2).

Theorem 1.1 (Informal: rare-tail direction recovery). Under regularly-varying margin-dependent noise, Algorithm 1 returns a direction w^\widehat{w} with ∠(w^,w⋆)≤O(1/t⋆)\angle(\widehat{w},w^\star)\leq O(1/t^\star) with high probability using O~((d+log⁡(1/δ))/p)\widetilde{O}((d+\log(1/\delta))/p) samples.

The angular scale O(1/t⋆)O(1/t^\star) is exactly the scale needed for excess risk in the critical regime. To estimate the threshold, we use the threshold ERM of Algorithm 2 with the following guarantee:

Theorem 1.2 (Informal: one-dimensional threshold ERM). For any fixed direction w^\widehat{w}, Algorithm 2 uses O~(1/ε2)\widetilde{O}(1/\varepsilon^2) independent validation samples and returns a threshold t^\widehat{t} whose risk is within ε\varepsilon of the best threshold along w^\widehat{w}.

This leads us to the standalone sample-optimal halfspace learning guarantee.

References

  1. [1]Emmanuel Abbe, Elisabetta Cornacchia, and Aryo Lotfi. Provable advantage of curriculum learning on parity targets with mixed inputs. In Advances in Neural Information Processing Systems, volume 36, 2023.arxiv.org/abs/2306.16921
  2. [2]Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2(4):343–370, 1988. doi: 10.1023/A:1022873112823.
  3. [3]Pranjal Awasthi, Vitaly Feldman, and Varun Kanade. Learning using local membership queries. In Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 398–431. PMLR, 2013.arxiv.org/abs/1211.0996
  4. [4]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, volume 40 of Proceedings of Machine Learning Research, pages 167–190. PMLR, 2015.arxiv.org/abs/1503.03594
  5. [5]Maria-Florina Balcan and Nika Haghtalab. Noise in classification. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, chapter 16. Cambridge University Press, 2021.arxiv.org/abs/2010.05080
  6. [6]Beata Beigman Klebanov and Eyal Beigman. Squibs: From annotator agreement to noise models. Computational Linguistics, 35(4):495–503, December 2009. doi: 10.1162/coli.2009.35.4.3502. URL https://aclanthology.org/J09-4005/.
  7. [7]Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, page 41–48, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585161. doi: 10.1145/1553374.1553380. URL https://doi.org/10.1145/1553374.1553380.
  8. [8]Avrim Blum, Alan Frieze, Ravi Kannan, and Santosh Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22(1–2):35–52, 1998. doi: 10.1007/PL00013833.DOI
  9. [9]Tom Bylander. Learning noisy linear threshold functions. Technical report, University of Texas at San Antonio, 1998. Unpublished manuscript.
  10. [10]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, volume 33, 2020.
  11. [11]Edith Cohen. Learning noisy perceptrons by a perceptron in polynomial time. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 514–523. IEEE Computer Society, 1997.
  12. [12]Elisabetta Cornacchia and Elchanan Mossel. A mathematical model for curriculum learning for parities. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 6402–6423. PMLR, 2023.arxiv.org/abs/2301.13833
  13. [13]Ilias Diakonikolas and Daniel M. Kane. Near-optimal statistical query hardness of learning halfspaces with massart noise. In Proceedings of the Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4258–4282. PMLR, 2022.
  14. [14]Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 1061–1073. Association for Computing Machinery, 2018. ISBN 9781450355599.arxiv.org/abs/1707.01242
  15. [15]Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-independent PAC learning of halfspaces with Massart noise. In Advances in Neural Information Processing Systems, volume 32, 2019.arxiv.org/abs/1906.10075
  16. [16]Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with Massart noise under structured distributions. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1486–1513. PMLR, 2020.arxiv.org/abs/2002.05632
  17. [17]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Efficiently learning halfspaces with Tsybakov noise. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 88–101. ACM, 2021. doi: 10.1145/3406325.3450998.DOI
  18. [18]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with general Massart noise under the Gaussian distribution. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 874–885. ACM, 2022. doi: 10.1145/3519935.3519970.DOI
  19. [19]Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with adversarial label noise via online gradient descent. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 5118–5141. PMLR, 17–23 Jul 2022.
  20. [20]Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Pugian Wang, and Nikos Zarifis. Near-optimal bounds for learning gaussian halfspaces with random classification noise, 2023. URL https://arxiv.org/abs/2307.08438.
  21. [21]Ilias Diakonikolas, Daniel Kane, Sihan Liu, and Nikos Zarifis. Testable learning of general halfspaces with adversarial label noise. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1308–1335. PMLR, 2024.arxiv.org/abs/2408.17165
  22. [22]Ilias Diakonikolas, Daniel M. Kane, and Mingchen Ma. Active learning of general halfspaces: Label queries vs membership queries. In Advances in Neural Information Processing Systems, volume 37, 2024.arxiv.org/abs/2501.00508
  23. [23]Morris L. Eaton. A characterization of spherical distributions. Journal of Multivariate Analysis, 20(2):272–276, 1986. ISSN 0047-259X. doi: https://doi.org/10.1016/0047-259X(86)90083-7. URL https://www.sciencedirect.com/science/article/pii/0047259X86900837.
  24. [24]Sheng Guo, Weilin Huang, Haozhi Zhang, Chenfan Zhuang, Dengke Dong, Matthew R. Scott, and Dinglong Huang. CurriculumNet: Weakly supervised learning from large-scale web images. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018.arxiv.org/abs/1808.01097
  25. [25]Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Noise-tolerant, reliable active classification with comparison queries. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1957–2006. PMLR, 2020.arxiv.org/abs/2001.05497
  26. [26]Daniel Hsu and Arya Mazumdar. On the sample complexity of parameter estimation in logistic regression with normal design. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2418–2437. PMLR, 2024.arxiv.org/abs/2307.04191
  27. [27]Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. MentorNet: Learning data-driven curriculum for very deep neural networks on corrupted labels. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2304–2313. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/jiang18c.html.
  28. [28]Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6):1777–1805, 2008. doi: 10.1137/060649057.DOI
  29. [29]Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983–1006, 1998. doi: 10.1145/293347.293351.DOI
  30. [30]Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34(5):2326 – 2366, 2006.DOI
  31. [31]Rajai Nasser and Stefan Tiegel. Optimal sq lower bounds for learning halfspaces with massart noise. In Proceedings of the Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1047–1074. PMLR, 2022.
  32. [32]Vikas C. Raykar and Shipeng Yu. Eliminating spammers and ranking annotators for crowdsourced labeling tasks. Journal of Machine Learning Research, 13(16):491–518, 2012. URL http://jmlr.org/papers/v13/raykar12a.html.
  33. [33]Rocco A. Servedio. On pac learning using winnow, perceptron, and a perceptron-like algorithm. In Annual Conference Computational Learning Theory, 1999. URL https://api.semanticscholar.org/CorpusID:5347529.DOI
  34. [34]Alexandre B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166, 2004. doi: 10.1214/aos/1079120131.DOI
  35. [35]Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
  36. [36]Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009. URL https://proceedings.neurips.cc/paper_files/paper/2009/file/f899139df5e1059396431415e770c6dd-Paper.pdf.
  37. [37]Xiaoxia Wu, Ethan Dyer, and Behnam Neyshabur. When do curricula work? In International Conference on Learning Representations, 2021.arxiv.org/abs/2012.03107

Paper details

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

views · 8

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