The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Efficient noise-tolerant learning from statistical queries
Open accessAbstract
In this paper, we study the problem of learning in the presence of classification noise in the probabilistic learning model of Valiant and its variants. In order to identify the class of “robust” learning algorithms in the most general way, we formalize a new but related model of learning from statistical queries . Intuitively, in this model a learning algorithm is forbidden to examine individual examples of the unknown target function, but is given acess to an oracle providing estimates of probabilities over the sample space of random examples. One of our main results shows that any class of functions learnable from statistical queries is in fact learnable with classification noise in Valiant's model, with a noise rate approaching the information-theoretic barrier of 1/2. We then demonstrate the generality of the statistical query model, showing that practically every class learnable in Valiant's model and its variants can also be learned in the new model (and thus can be learned in the presence of noise). A notable exception to this statement is the class of parity functions, which we prove is not learnable from statistical queries, and for which no noise-tolerant algorithm is known.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
The Strength of Weak Learnability
Schapire, R. E. (1990) · Machine Learning · doi:10.1007/bf00116037 · Cited by 4,600
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
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
An Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697
Self-citation
Cited by
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898
Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., & Papernot, N. (2021) · 2021 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp40001.2021.00019 · Cited by 810
“2Kearns [16] shows that any PAC learning algorithm has a corresponding SQ learning equivalent.”
BackgroundInfluentialCost-sensitive learning by cost-proportionate example weighting
Zadrozny, B., Langford, J., & Abe, N. (2004) · Third IEEE International Conference on Data Mining · doi:10.1109/icdm.2003.1250950 · Cited by 680
Noise-tolerant learning, the parity problem, and the statistical query model
Blum, A., Kalai, A., & Wasserman, H. (2003) · Journal of the ACM · doi:10.1145/792538.792543 · Cited by 598
Towards Making Systems Forget with Machine Unlearning
Cao, Y., & Yang, J. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.35 · Cited by 622
The reusable holdout: Preserving validity in adaptive data analysis
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., & Roth, A. (2015) · Science · doi:10.1126/science.aaa9375 · Cited by 307
On the (im)possibility of fairness
Friedler, S. A., Scheidegger, C., & Venkatasubramanian, S. (2016) · arXiv · doi:10.48550/arxiv.1609.07236 · Cited by 247
Multiaccuracy: Black-Box Post-Processing for Fairness in Classification
Kim, M. P., Ghorbani, A., & Zou, J. (2019) · Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3306618.3314287 · Cited by 193
Agnostic Learning of Monomials by Halfspaces Is Hard
Feldman, V., Guruswami, V., Raghavendra, P., & Wu, Y. (2012) · SIAM Journal on Computing · doi:10.1137/120865094 · Cited by 143
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
Beimel, A., Nissim, K., & Stemmer, U. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40328-6_26 · Cited by 72
A Survey of Machine Unlearning
Nguyen, T. T., Huynh, T. T., Ren, Z., Nguyen, P. L., Liew, A. W.-C., Yin, H., & Nguyen, Q. V. H. (2022) · arXiv · doi:10.48550/arxiv.2209.02299 · Cited by 193
“More precisely, statistical query learning assumes that most of the learning algorithms can be represented as a sum of some efficiently computable transformations, called statistical queries [79].”
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model
Ghazi, B., Pagh, R., & Velingker, A. (2019) · arXiv · doi:10.48550/arxiv.1906.08320 · Cited by 62
Confidence Scores Make Instance-dependent Label-noise Learning Possible
Berthon, A., Han, B., Niu, G., Liu, T., & Sugiyama, M. (2020) · arXiv · doi:10.48550/arxiv.2001.03772 · Cited by 57
Athena: Probabilistic Verification of Machine Unlearning
Sommer, D. M., Song, L., Wagh, S., & Mittal, P. (2022) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2022-0072 · Cited by 51
Towards Probabilistic Verification of Machine Unlearning
Sommer, D. M., Song, L., Wagh, S., & Mittal, P. (2020) · arXiv · doi:10.48550/arxiv.2003.04247 · Cited by 38
Metadata
- Authors
- Kearns, M.
- Venue
- Journal of the ACM
- Published
- 1998-11
- Volume
- 45
- Issue
- 6
- Pages
- 983-1006
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1995897489
- Cited by
- 665
- References
- 4
- FWCI
- 11.38
- 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.
