The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
Toward efficient agnostic learning
Open accessAbstract
In this paper we initiate an investigation of generalizations of the Probably Approximately Correct (PAC) learning model that attempt to significantly weaken the target function assumptions. The ultimate goal in this direction is informally termed agnostic learning, in which we make virtually no assumptions on the target function. The name derives from the fact that as designers of learning algorithms, we give up the belief that Nature (as represented by the target function) has a simple or succinct explanation.
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
(1979) · Cited by 43,841
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer Series in Statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,666
The Strength of Weak Learnability
Schapire, R. E. (1990) · Machine Learning · doi:10.1007/bf00116037 · Cited by 4,600
Self-citationPattern Classification and Scene Analysis
Thompson, M., Duda, R. O., & Hart, P. E. (1974) · Leonardo · doi:10.2307/1573081 · Cited by 4,495
Pattern classification and scene analysis
Chien, Y. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100577 · Cited by 3,398
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
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
Convergence of Stochastic Processes.
Robinson, P. M., & Pollard, D. (1985) · Economica · doi:10.2307/2553898 · Cited by 2,184
Convergence of Stochastic Processes
Pollard, D. (1984) · Springer Series in Statistics · doi:10.1007/978-1-4612-5254-2 · Cited by 1,841
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
Learning in Artificial Neural Networks: A Statistical Perspective
White, H. (1989) · Neural Computation · doi:10.1162/neco.1989.1.4.425 · Cited by 922
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
Estimation of Dependences Based on Empirical Data.
Shoesmith, E., Vapnik, V., & Kotz, S. (1984) · The Statistician · doi:10.2307/2988246 · Cited by 764
Cryptographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. (1994) · Journal of the ACM · doi:10.1145/174644.174647 · Cited by 733
Self-citationConstant depth circuits, Fourier transform, and learnability
Linial, N., Mansour, Y., & Nisan, N. (1993) · Journal of the ACM · doi:10.1145/174130.174138 · Cited by 572
Central Limit Theorems for Empirical Measures
Dudley, R. M. (1978) · The Annals of Probability · doi:10.1214/aop/1176995384 · Cited by 571
Computational limitations on learning from examples
Pitt, L., & Valiant, L. G. (1988) · Journal of the ACM · doi:10.1145/48014.63140 · Cited by 515
Recent Developments in Nonparametric Density Estimation
Izenman, A. J. (1991) · Journal of the American Statistical Association · doi:10.2307/2289732 · Cited by 464
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
Self-citationLearning in the Presence of Malicious Errors
Kearns, M., & Li, M. (1993) · SIAM Journal on Computing · doi:10.1137/0222052 · Cited by 340
Self-citationOn the learnability of Boolean formulae
Kearns, M., Li, M., Pitt, L., & Valiant, L. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28426 · Cited by 284
Self-citationReview Papers: Recent Developments in Nonparametric Density Estimation
Izenman, A. J. (1991) · Journal of the American Statistical Association · doi:10.1080/01621459.1991.10475021 · Cited by 281
Crytographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. G. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73049 · Cited by 266
Self-citationTracking drifting concepts by minimizing disagreements
Helmbold, D. P., & Long, P. M. (1994) · Machine Learning · doi:10.1007/bf00993161 · Cited by 161
Learning in the presence of malicious errors
Kearns, M. J., & Li, M. (1988) · doi:10.1145/62212.62238 · Cited by 127
Self-citationConstant depth circuits, Fourier transform, and learnability
Linial, N., Mansour, Y., & Nisan, N. (1989) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63537 · Cited by 126
Density estimation by stochastic complexity
Rissanen, J., Speed, T. P., & Yu, B. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.119689 · Cited by 114
A learning criterion for stochastic rules
Yamanishi, K. (1990) · Conference on Learning Theory · doi:10.5555/92571.92590 · Cited by 86
An improved boosting algorithm and its implications on learning complexity
Freund, Y. (1992) · Conference on Learning Theory · doi:10.1145/130385.130429 · Cited by 61
A Markovian extension of Valiant's learning model
Aldous, D., & Vazirani, U. V. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89558 · Cited by 28
Tracking drifting concepts using random examples
Helmbold, D. P., & Long, P. M. (1991) · Conference on Learning Theory · doi:10.5555/114836.114839 · Cited by 24
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Research works printed but not linked: 2
- 10.1023/A:1022648800760 · doi:10.1023/a:1022648800760 · Paper page
- 10.5555/1625135.1625242 · doi:10.5555/1625135.1625242
Cited by
Hoeting, J. A., Madigan, D., Raftery, A. E., & Volinsky, C. T. (1999) · Statistical Science · doi:10.1214/ss/1009212519 · Cited by 4,118
(2015) · Cited by 2,857
The Lack of A Priori Distinctions Between Learning Algorithms
Wolpert, D. H. (1996) · Neural Computation · doi:10.1162/neco.1996.8.7.1341 · Cited by 1,647
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (1998) · Journal of the ACM · doi:10.1145/285055.285060 · Cited by 1,020
Exponentiated Gradient versus Gradient Descent for Linear Predictors
Kivinen, J., & Warmuth, M. K. (1997) · Information and Computation · doi:10.1006/inco.1996.2612 · Cited by 864
Metadata
- Authors
- Kearns, M. J., Schapire, R. E., & Sellie, L. M.
- Venue
- Proceedings of the fifth annual workshop on Computational learning theory
- Publisher
- ACM
- Published
- 1992-07
- Pages
- 341-352
- OpenAlex
- W1982381767
- Cited by
- 330
- References
- 33
- FWCI
- 12.02
- Type
- conference paper
- Language
- en
- Open access
- gold
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.