betaFeedback

WorksComputer Science

Agnostic Marginal-Nonuniform Learning

Abstract

We study the problem of binary classification in the marginal-nonuniform learning framework in the agnostic setting. In this model, the constants in the learning rate may depend on the marginal distribution of the unlabeled data, but the guarantee must hold uniformly over all conditional distributions of the labels. We also study fine-grained rates. We consider two criteria. (1) The standard agnostic setting, where the learner competes with the best concept in the class. In this setting, an immediate consequence of standard agnostic PAC learning results gives us the optimal rate of 1n\tfrac{1}{\sqrt{n}} for every class H\mathcal{H} with finite VC(H)\mathrm{VC}(\mathcal{H}) and shows that arbitrarily slow rates are necessary otherwise. This also gives us the optimal fine-grained rate of VC(H)n\sqrt{\tfrac{\mathrm{VC}(\mathcal{H})}{n}}. Therefore, the dependence on the marginal distribution does not help, which is in contrast to the realizable setting. (2) In the relaxed agnostic setting, where the learner competes with (1+λ)(1+λ) times the error of the best concept for a fixed λ∈(0,1]λ\in (0,1], the picture from the realizable setting reappears. We obtain a trichotomy of the achievable optimal rates: exponential rates of the form e−ne^{-n} arise precisely when the class is finite; linear rates of the form 1n\tfrac{1}{n} arise when the class is infinite but VC(H)\mathrm{VC}(\mathcal{H}) is finite; and arbitrarily slow rates occur when VC(H)=∞\mathrm{VC}(\mathcal{H})=\infty. We also obtain the optimal fine-grained rate of uVCE(H)λn\tfrac{\mathrm{uVCE}(\mathcal{H})}{λn}, where uVCE(H)\mathrm{uVCE}(\mathcal{H}) is a recently introduced combinatorial complexity dimension called the uncentered VC\mathrm{VC}-eluder dimension.

Introduction

A central question in statistical learning theory is how many labeled examples are needed to predict well on unseen data. The classical PAC model [38, 37] answers the uniform case: one rate has to hold for every marginal distribution over the instance space and every target concept in the class. This gives a clean worst-case theory, in which the VC dimension characterizes learnability, but it cannot tell an easy data distribution from a hard one. Marginal-nonuniform learning [4, 25] relaxes exactly this point. The constants in the rate may depend on the marginal distribution DX\mathcal{D}_{X} of the unlabeled data, but once DX\mathcal{D}_{X} is fixed, the guarantee must hold uniformly over everything else. It sits between uniform PAC learning and universal learning [9], where the constants may depend on the whole data distribution.

Marginal-nonuniform learning has a classical counterpart in concept-nonuniform learning, introduced by Benedek and Itai [ [7] and usually called simply nonuniform learning. In this framework, the roles are exchanged: the constants in the rate may depend on the target concept, but the guarantee must hold uniformly over all marginal distributions. This model makes a much larger family of classes learnable, namely all countable unions of VC classes, and it underlies structural risk minimization, Occam’s razor and the minimum description length principle [39, 8 Rissanen,] 1978, Lugosi and Zeger, 1996]. It distinguishes concepts that are easy to learn from concepts that are hard to learn, whereas marginal-nonuniform learning distinguishes easy marginals from hard ones. Together with uniform and universal learning, these are the four natural notions of learnability obtained by letting the rate depend on the marginal, on the target, on both, or on neither [4]. We recall them, in the form needed for this paper, in § 1.1.

In the realizable case, the possible marginal-nonuniform rates are by now well understood. Hanneke et al. [ [25] proved a trichotomy for binary classification: every class is learnable at an exponential rate, at a linear rate, or only at arbitrarily slow rates, and in the linear case the optimal rate is d/nd/n, where dd is the VC-eluder dimension of Hanneke and Xu [2024]. This dimension can be much smaller than the VC dimension. The work of Brukhim et al. [ [11] extended the characterization to multiclass classification, using the uncentered DS-eluder dimension. All of these results assume that some concept in the class labels the data perfectly.

Agnostic marginal-nonuniform learning. Consider an email provider that stores a large archive of messages. The prediction task is chosen only later: filtering spam, detecting phishing, or flagging messages as urgent. The messages, and hence the marginal DX\mathcal{D}_{X}, are fixed before the task is known, which is the situation marginal-nonuniform guarantees are designed for. But the labels will come from users, who click carelessly and who disagree with each other: the same newsletter is spam to one user and wanted by another. No concept in the class will label the data perfectly. What the provider can hope for is a filter that is nearly as accurate as the best concept in the class, whatever the task and the behavior of the users turn out to be.

This is the step from realizable to agnostic learning [27, 29]. It is the standard second step in PAC learning: one first studies the realizable case, where the optimal rate is VC⁡(H)/n\operatorname{VC}(\mathcal{H})/n, and then drops the assumption on the labels, where the optimal rate becomes VC⁡(H)/n\sqrt{\operatorname{VC}(\mathcal{H})/n}. We take the same step in the marginal-nonuniform setting. The learner competes with inf⁡h∈Her⁡D(h)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h), the constants may depend on the marginal DX\mathcal{D}_{X}, and the guarantee must hold for every distribution D\mathcal{D} over X×Y\mathcal{X}\times\mathcal{Y} with that marginal. In the example, the archive fixes DX\mathcal{D}_{X}, while the task and the behavior of the annotators, i.e., the conditional distribution of the label given the message, are left completely free.

If VC⁡(H)<∞\operatorname{VC}(\mathcal{H})<\infty, the classical agnostic PAC upper bound applies directly: it holds for every distribution D\mathcal{D} over X×Y\mathcal{X}\times\mathcal{Y}, with constants that do not depend on D\mathcal{D}, so in particular it holds for every distribution with a given marginal DX\mathcal{D}_{X}. The classical agnostic PAC lower bound also carries over. Its hard distributions all have the same marginal, namely the uniform distribution on a set of VC⁡(H)\operatorname{VC}(\mathcal{H}) points shattered by H\mathcal{H}, and only the conditional distribution of the labels depends on the sample size and on the learner. It is therefore a lower bound in the marginal-nonuniform model as well. Combining the two, H\mathcal{H} is agnostically marginal-nonuniformly learnable at exact rate 1n\frac{1}{\sqrt{n}} whenever VC⁡(H)<∞\operatorname{VC}(\mathcal{H})<\infty. It also provides a fine-grained rate of VC⁡(H)n\sqrt{\frac{\operatorname{VC}(\mathcal{H})}{n}}. Therefore, we could say that the dependence on the marginal does not help.

Relaxed agnostic marginal-nonuniform learning. The 1n\frac{1}{\sqrt{n}} rate is the price of competing with the best concept exactly. In many applications this is more than one needs. Suppose that in the example above the best rule in the class disagrees with the user on 1% of the messages. A guarantee of the form “error at most 1.1%, plus a term of order 1/n1/n” is then far more useful than “error at most 1%, plus a term of order 1/n1/\sqrt{n}”. When the best concept is already good, a small multiplicative loss costs almost nothing, while the additive 1/n1/\sqrt{n} term dominates the bound.

This motivates the relaxed agnostic criterion: for a fixed λ∈(0,1]\lambda\in(0,1], the learner competes with (1+λ)inf⁡h∈Her⁡D(h)(1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h). Guarantees of this multiplicative form are common. The weighted majority algorithm competes with a constant factor times the loss of the best expert [31]; efficient algorithms for learning halfspaces with adversarial label noise under suitable distributional assumptions typically guarantee error (1+λ)OPT⁡+ε(1+\lambda)\operatorname{OPT}+\varepsilon or C⋅OPT⁡+εC\cdot\operatorname{OPT}+\varepsilon [14, 3]; and bounds that improve when the best error is small are known as optimistic or first-order bounds. [36]. The relaxed criterion also interpolates between the two classical settings: when the data are realizable it is the realizable criterion, and as λ→0\lambda\to0 it becomes the agnostic one.

In this case we show that under the relaxed criterion the realizable picture returns, both for the rates and for the fine-grained rates. The achievable rates form the same trichotomy as in the realizable case [25]: exponential for finite classes, linear for infinite classes of finite VC dimension, and arbitrarily slow otherwise. Note that even a finite class only has rate 1n\frac{1}{\sqrt{n}} under the standard criterion, so the multiplicative slack already matters there. The fine-grained rate is of order dλn\frac{d}{\lambda n}, where dd is the uncentered VC-eluder dimension of the class, and the dependence on the marginal is confined to an exponentially small term. So the leading term is again governed by the uncentered VC-eluder dimension rather than by the VC dimension. The VC⁡(H)/n\sqrt{\operatorname{VC}(\mathcal{H})/n} barrier of the agnostic case is therefore caused entirely by insisting on the constant 1 in front of the best error.

Main results

We first place our setting among the four learning paradigms mentioned above. A distribution D\mathcal{D} over X×Y\mathcal{X} \times\mathcal{Y} consists of its marginal DX\mathcal{D}_{\mathcal{X}} and its conditional distribution of the label given the instance, which we denote DY∣X\mathcal{D}_{\mathcal{Y} \mid\mathcal{X}}. In the realizable case, DY∣X\mathcal{D}_{\mathcal{Y} \mid\mathcal{X}} is given by a target concept; in general it plays the role that the target concept plays there. For λ∈[0,1]\lambda\in[0,1] and a learner A\mathcal{A}, write

Eλ(A,D,n)=ES∼Dn[er⁡D(AS)]−(1+λ)inf⁡h∈Her⁡D(h)\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)=\mathbb{E}_{S\sim\mathcal{D}^{n}}[\operatorname{er}_{\mathcal{D}}(\mathcal{A}S)]-(1+\lambda)\inf_{h\in\mathcal{H}}\operatorname{er}_{\mathcal{D}}(h)

for the excess error, where λ=0\lambda=0 is the standard agnostic criterion and λ>0\lambda>0 the relaxed one. Adapting Bousquet et al. [ [9] and Hanneke et al. [ [25], the four paradigms differ only in the order of the quantifiers. Throughout, we extend every rate function R:N→[0,1]R:\mathbb{N}\to[0,1] to positive real arguments by setting R(t)=R(⌈t⌉)R(t)=R(\lceil t\rceil) for all t>0t>0.

Definition 1.1. Let R:N→[0,1]R:\mathbb{N}\to[0,1] be a rate function with lim⁡n→∞R(n)=0\lim_{n\to\infty}R(n)=0 and let λ∈[0,1]\lambda\in[0,1].

  • H\mathcal{H} is λ\lambda-agnostically uniformly learnable at rate RR if

∃A ∃C,c>0 for all DY∣X for all DX for all n∈NEλ(A,D,n)≤CR(cn).\exists\mathcal{A}\ \exists C,c>0\ \text{for all }\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}\ \text{for all }\mathcal{D}_{\mathcal{X}}\ \text{for all }n\in\mathbb{N}\quad\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)\le CR(cn).
  • H\mathcal{H} is λ\lambda-agnostically universally learnable at rate RR if

∃A for all DY∣X for all DX ∃C,c>0 for all n∈NEλ(A,D,n)≤CR(cn).\exists\mathcal{A}\ \text{for all }\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}\ \text{for all }\mathcal{D}_{\mathcal{X}}\ \exists C,c>0\ \text{for all }n\in\mathbb{N}\quad\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)\le CR(cn).
  • H\mathcal{H} is λ\lambda-agnostically concept-nonuniformly learnable at rate RR if

∃A for all DY∣X ∃C,c>0 for all DX for all n∈NEλ(A,D,n)≤CR(cn).\exists\mathcal{A}\ \text{for all }\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}\ \exists C,c>0\ \text{for all }\mathcal{D}_{\mathcal{X}}\ \text{for all }n\in\mathbb{N}\quad\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)\le CR(cn).
  • H\mathcal{H} is λ\lambda-agnostically marginal-nonuniformly learnable at rate RR if

∃A for all DX ∃C,c>0 for all DY∣X for all n∈NEλ(A,D,n)≤CR(cn).\exists\mathcal{A}\ \text{for all }\mathcal{D}_{\mathcal{X}}\ \exists C,c>0\ \text{for all }\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}\ \text{for all }n\in\mathbb{N}\quad\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n)\le CR(cn).

Here D\mathcal{D} is the distribution over X×Y\mathcal{X}\times\mathcal{Y} with marginal DX\mathcal{D}_{\mathcal{X}} and conditional label distribution DY∣X\mathcal{D}_{\mathcal{Y}\mid\mathcal{X}}.

Uniform learning is the classical agnostic PAC model: the constants depend on nothing. In universal learning they may depend on the whole distribution. The two nonuniform models sit in between and are incomparable: in the concept-nonuniform model the constants may depend on how the labels are generated but not on the marginal, and in the marginal-nonuniform model it is the other way round. This paper is about the last paradigm. It is the natural one when the unlabeled data are fixed in advance and the labeling task is not. We state our results at two levels of detail. The first is the rate in the sense of Definition 1.1, which describes the shape of the learning curve. Throughout we assume ∣H∣≥3|\mathcal{H}|\ge3, which only excludes trivial classes [25]. Our first result is regarding the rates for standard agnostic and relaxed agnostic settings.

Theorem 1.2. [Rates, informal] Let H\mathcal{H} be a concept class with ∣H∣≥3|\mathcal{H}| \ge3.

  • Standard agnostic learning.

    1. H\mathcal{H} is 00-agnostically marginal-nonuniformly learnable at exact rate 1n\frac{1}{\sqrt{n}} if and only if VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty.

    2. H\mathcal{H} requires arbitrarily slow rates to be 00-agnostically marginal-nonuniformly learnable if and only if VC⁡(H)=∞\operatorname{VC}(\mathcal{H}) = \infty.

  • Relaxed agnostic learning. For every fixed 0<λ≤10 < \lambda\le1:

    1. H\mathcal{H} is λ\lambda-agnostically marginal-nonuniformly learnable at exact rate e−n\mathrm{e}^{-n} if and only if H\mathcal{H} is finite.

    2. H\mathcal{H} is λ\lambda-agnostically marginal-nonuniformly learnable at exact rate 1n\frac{1}{n} if and only if H\mathcal{H} is infinite and VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty.

    3. H\mathcal{H} requires arbitrarily slow rates to be λ\lambda-agnostically marginal-nonuniformly learnable if and only if VC⁡(H)=∞\operatorname{VC}(\mathcal{H}) = \infty.

For the standard criterion, the rates are exactly those of uniform agnostic PAC learning. For the relaxed criterion, they are exactly those of realizable marginal-nonuniform learning [25].

Rates alone say nothing about the constants. A bound CR(cn)CR(cn) in which CC and cc may depend on the marginal does not tell us how the class and the marginal together determine the error. This is addressed by the fine-grained rates of Bousquet et al. [ [10], which separate the two dependences into different additive terms: one asks for a bound of the form

Eλ(A,D,n)≤KR(n)+δ(n),\mathcal{E}_{\lambda}(\mathcal{A},\mathcal{D},n) \le K R(n) + \delta(n),

where KK is a universal constant, the leading term R(n)R(n) depends only on the class (and on λ\lambda), and all dependence on the marginal is confined to a lower-order term δ(n)=o(R(n))\delta(n) = o(R(n)). A matching lower bound asks that a universal constant multiple of R(n)R(n) cannot be avoided. The marginal then determines only how long one has to wait before the class-dependent rate takes over, and not the rate itself. The precise definitions are in § 3.

Theorem 1.3 (Fine-grained rates, informal). 1. If VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty, then H\mathcal{H} is 00-agnostically marginal-nonuniformly learnable at exact fine-grained rate VC⁡(H)n\sqrt{\frac{\operatorname{VC}(\mathcal{H})}{n}}.

  1. If 1≤uVCE⁡(H)<∞1 \le\operatorname{uVCE}(\mathcal{H}) < \infty, then for every 0<λ≤10 < \lambda\le1, H\mathcal{H} is λ\lambda-agnostically marginal-nonuniformly learnable at exact fine-grained rate uVCE⁡(H)λn\frac{\operatorname{uVCE}(\mathcal{H})}{\lambda n}.

Related Works

Agnostic universal and nonuniform learning. The work of Hanneke and Moran [ [20] extends the universal learning theory of Bousquet et al. [ [9] to the agnostic setting, showing that the optimal universal rate is e−n\mathrm{e}^{-n}, e−o(n)\mathrm{e}^{-o(n)}, o(n−1/2)o(n^{-1/2}), or arbitrarily slow, and Hanneke and Xu [ [22] characterize the agnostic universal rates of ERMs. Since the constants there may depend on the entire data distribution, every finite class is learnable at rate e−n\mathrm{e}^{-n} even under the standard criterion, whereas in the marginal-nonuniform framework two concepts already force rate 1n\frac{1}{\sqrt{n}} unless the criterion is relaxed. In classical comparator-dependent nonuniform learning2, the agnostic case is handled by structural risk minimization [39, 32, 35], and Hanneke et al. [2025c] characterize nonuniform multiclass learnability in both the realizable and the agnostic settings, under both full-information and bandit feedback. To our knowledge, marginal-nonuniform learning has so far been studied only in the realizable case [25, 11].

Multiplicative slack in the uniform setting. In the uniform learning framework, it is well known that a multiplicative slack yields fast rates. Relative deviation and optimistic bounds [39, 36] show that the error of ERM on nn examples, over a class of VC dimension dd, is at most (1+λ)(1+\lambda) times the best error in the class plus O(dlog⁡(n)/(λn))O(d\log(n)/(\lambda n)), and the first-order learner of Mathiasen et al. [ [33] (see also Hanneke et al. [2024]) removes the logarithmic factor. Additionally, the work of Asilis et al. [ [1] gives a learner whose error is at most cc times the best error in the class, for a constant c≤2.1c \le2.1, plus the optimal additive term. In statistics, bounds of this form, with a leading constant larger than one, are called nonexact oracle inequalities, and they can give fast rates where exact ones only give slow rates [30]. Our results for the relaxed criterion are the marginal-nonuniform analogue, with the VC dimension replaced by the uncentered VC-eluder dimension, which can be much smaller, and with exponential rates for finite classes; neither follows from the uniform bounds.

Learning with a known marginal. Marginal-nonuniform learning is related to learning under a fixed marginal that is known to the learner [6]. This is also the idealized limit of semi-supervised learning, where the value of unlabeled data has been studied extensively [5, 15, 19]. Our fine-grained lower bounds use a single marginal, so they hold even for learners that know DX\mathcal{D}_{\mathcal{X}}. In particular, under the standard criterion, knowing the marginal does not improve the fine-grained rate VC⁡(H)/n\sqrt{\operatorname{VC}(\mathcal{H})/n}.

Preliminaries

References

  1. [1]Julian Asilis, Mikael Møller Høgsg aard, and Grigoris Vellegas. On agnostic PAC learning in the small error regime. In Advances in Neural Information Processing Systems, volume 38, 2025.arxiv.org/abs/2502.09496
  2. [2]Patrice Assouad. Deux remarques sur l’estimation. Comptes Rendus de l’Académie des Sciences de Paris, Série I, 296:1021–1024, 1983.
  3. [3]Pranjal Awasthi, Maria Florina Balcan, and Philip M. Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM, 63(6):50:1–50:27, 2017.
  4. [4]Shai Ben-David, Gyora M. Benedek, and Yishay Mansour. A parameterization scheme for classifying models of PAC learnability. Inf. Comput., 120(1):11–21, July 1995. ISSN 0890-5401. doi: 10.1006/inco.1995.1094. URL https://doi.org/10.1006/inco.1995.1094.
  5. [5]Shai Ben-David, Tyler Lu, and Dávid Pál. Does unlabeled data provably help? Worst-case analysis of the sample complexity of semi-supervised learning. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 33–44, 2008.
  6. [6]Gyora M. Benedek and Alon Itai. Learnability with respect to fixed distributions. Theoretical Computer Science, 86(2):377–389, 1991.
  7. [7]Gyora M. Benedek and Alon Itai. Nonuniform learnability. Journal of Computer and System Sciences, 48(2):311–323, 1994.
  8. [8]Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam’s razor. Information Processing Letters, 24(6):377–380, 1987.
  9. [9]Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 532–541, 2021.
  10. [10]Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, and Ilya Tolstikhin. Fine-grained distribution-dependent learning curves. In Proceedings of the 36th Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5890–5924, 2023.arxiv.org/abs/2208.14615
  11. [11]Nataly Brukhim, Steve Hanneke, Amirreza Shaeiri, and Maximilian Thiessen. Marginal-nonuniform multiclass learning. In Advances in Neural Information Processing Systems, 2026.arxiv.org/abs/2611.09543
  12. [12]Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050–2057, 2004.
  13. [13]Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang. Sample complexity of agnostic multiclass classification: Natarajan dimension strikes back. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC ’26, page 722–733, New York, NY, USA, 2026. Association for Computing Machinery. ISBN 9798402752364. doi: 10.1145/3798129.3800787. URL https://doi.org/10.1145/3798129.3800787.
  14. [14]Amit Daniely. A PTAS for agnostically learning halfspaces. In Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 484–502. PMLR, 2015.arxiv.org/abs/1410.7050
  15. [15]Malte Darnstädt, Hans Ulrich Simon, and Balázs Szörényi. Unlabeled data does provably help. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pages 185–196, 2013.DOI
  16. [16]Ofir David, Shay Moran, and Amir Yehudayoff. Supervised learning through the lens of compression. In Advances in Neural Information Processing Systems, volume 29, 2016.
  17. [17]Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition, volume 31 of Applications of Mathematics. Springer, 1996.DOI
  18. [18]Yoav Freund and Robert E. 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.DOI
  19. [19]Christina Göpfert, Shai Ben-David, Olivier Bousquet, Sylvain Gelly, Ilya Tolstikhin, and Ruth Urner. When can unlabeled data improve the learning rate? In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1500–1518. PMLR, 2019.arxiv.org/abs/1905.11866
  20. [20]Steve Hanneke and Shay Moran. A theory of universal agnostic learning. arXiv preprint arXiv:2601.20961, 2026.arxiv.org/abs/2601.20961
  21. [22]Steve Hanneke and Mingyue Xu. Universal rates of ERM for agnostic learning. In Proceedings of the Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 2666–2703. PMLR, 2025.arxiv.org/abs/2506.14110
  22. [24]Steve Hanneke, Qinglin Meng, and Amirreza Shaeiri. Representation preserving multiclass agnostic to realizable reduction. In ICML, 2025a.
  23. [25]Steve Hanneke, Shay Moran, and Maximilian Thiessen. Marginal-nonuniform PAC learnability. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025b. URL https://openreview.net/forum?id=aoVCFtox89.DOI
  24. [27]David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78–150, 1992. ISSN 0890-5401. doi: 10.1016/0890-5401(92)90010-D. URL http://dx.doi.org/10.1016/0890-5401(92)90010-D.
  25. [28]Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan. Realizable learning is all you need. In Proceedings of the 35th Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, 2022.DOI
  26. [29]Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2–3):115–141, 1994.
  27. [30]Guillaume Lecué and Shahar Mendelson. General nonexact oracle inequalities for classes with a subexponential envelope. The Annals of Statistics, 40(2):832–860, 2012.
  28. [31]Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994.
  29. [32]Gábor Lugosi and Kenneth Zeger. Concept learning using complexity regularization. IEEE Transactions on Information Theory, 42(1):48–54, 1996.
  30. [33]Markus Engelund Mathiasen, Jian Qian, and Nikita Zhivotovskiy. An optimal agnostic PAC algorithm, 2026. URL https://arxiv.org/abs/2608.06363.
  31. [35]Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY, USA, 2014. ISBN 978-1-107-05713-5.
  32. [36]Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, volume 23, pages 2199–2207, 2010.
  33. [37]L. G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, November 1984. ISSN 0001-0782. doi: 10.1145/1968.1972. URL https://doi.org/10.1145/1968.1972.
  34. [38]V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. doi: 10.1137/1116025. URL https://doi.org/10.1137/1116025.
  35. [39]Vladimir N. Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998.

Paper details

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

views · 7

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents