The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Scale-sensitive dimensions, uniform convergence, and learnability
Open accessAbstract
Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper, we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to obtain the weakest combinatorial condition known to imply PAC learnability in the statistical regression (or “agnostic”) framework. Furthermore, we find a characterization of learnability in the probabilistic concept model, solving an open problem posed by Kearns and Schapire. These results show that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Modeling by shortest data description
Rissanen, J. (1978) · Automatica · doi:10.1016/0005-1098(78)90005-5 · Cited by 6,011
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (2015) · Measures of Complexity · doi:10.1007/978-3-319-21852-6_3 · Cited by 3,105
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (1971) · Theory of Probability & Its Applications · doi:10.1137/1116025 · Cited by 2,448
Estimation of Dependences Based on Empirical Data
Vapnik, V. (2006) · Information Science and Statistics · doi:10.1007/0-387-34239-7 · Cited by 2,238
Learnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839
Self-citationOn the density of families of sets
Sauer, N. (1972) · Journal of Combinatorial Theory, Series A · doi:10.1016/0097-3165(72)90019-2 · Cited by 844
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Haussler, D. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90010-d · Cited by 843
Self-citationEmpirical Processes: Theory and Applications
Pollard, D. (1990) · Project Euclid (Cornell University) · Cited by 710
A combinatorial problem; stability and order for models and theories in infinitary languages
Shelah, S. (1972) · Pacific Journal of Mathematics · doi:10.2140/pjm.1972.41.247 · Cited by 491
Some Limit Theorems for Empirical Processes
Gine, E., & Zinn, J. (1984) · The Annals of Probability · doi:10.1214/aop/1176993138 · Cited by 432
A course on empirical processes
Dudley, R. M. (1984) · Lecture Notes in Mathematics · doi:10.1007/bfb0099432 · Cited by 384
Efficient distribution-free learning of probabilistic concepts
Kearns, M. J., & Schapire, R. E. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80062-5 · Cited by 373
Vapnik, V. N. (1982) · Springer eBooks · Cited by 295
Necessary and Sufficient Conditions for the Uniform Convergence of Means to their Expectations
Vapnik, V. N., & Chervonenkis, A. Y. (1982) · Theory of Probability and Its Applications · doi:10.1137/1126059 · Cited by 236
Fat-shattering and the learnability of real-valued functions
Bartlett, P. L., Long, P. M., & Williamson, R. C. (1994) · Annual Conference on Computational Learning Theory (COLT) · doi:10.1145/180139.181158 · Cited by 117
Structural Risk Minimization for Character Recognition
Guyon, I., Vapnik, V. N., Boser, B. E., Bottou, L., & Solla, S. A. (1991) · neural information processing systems · Cited by 105
Uniform and universal Glivenko-Cantelli classes
Dudley, R. M., Gin�, E., & Zinn, J. (1991) · Journal of Theoretical Probability · doi:10.1007/bf01210321 · Cited by 100
Characterizations of Learnability for Classes of {0, ..., n)-Valued Functions
Ben-David, S., Cesa‐Bianchi, N., Haussler, D. H., & Long, P. M. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1008 · Cited by 92
Self-citationA generalization of Sauer's lemma
Haussler, D. H., & Long, P. M. (1995) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(95)90001-2 · Cited by 86
Self-citationVapnik, V. N. (1989) · Conference on Learning Theory · doi:10.5555/93335.93339 · Cited by 33
Cited by
A tutorial on support vector regression
Smola, A. J., & Schölkopf, B. (2004) · Statistics and Computing · doi:10.1023/b:stco.0000035301.49549.88 · Cited by 13,387
Kernel Methods for Pattern Analysis
Shawe-Taylor, J., & Cristianini, N. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809682 · Cited by 6,587
An overview of statistical learning theory
Vapnik, V. N. (1999) · IEEE Transactions on Neural Networks · doi:10.1109/72.788640 · Cited by 6,266
(2015) · Cited by 2,857
Advances in Large-Margin Classifiers
(2000) · The MIT Press eBooks · doi:10.7551/mitpress/1113.001.0001 · Cited by 1,869
Metadata
- Authors
- Alon, N., Ben-David, S., Cesa-Bianchi, N., & Haussler, D.
- Venue
- Journal of the ACM
- Published
- 1997-07
- Volume
- 44
- Issue
- 4
- Pages
- 615-631
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2017753243
- Cited by
- 340
- References
- 20
- FWCI
- 17.12
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.