Article

Free access

Noise-tolerant learning, the parity problem, and the statistical query model

Authors:

Avrim Blum,

Adam Kalai,

Hal WassermanAuthors Info & Claims

STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing

Pages 435 - 440

https://doi.org/10.1145/335305.335355

Published: 01 May 2000 Publication History

PDF eReader

References

[1]

D. Angluin and P. Laird. Learning from noisy examples. Machine Learning, 2(4):343-370, 1988.

Digital Library

Google Scholar

[2]

J. A. Aslam and S. E. Decatur. General bounds on statistical query learning and PAC learning with noise via hypothesis boosting. In Proceedings of the 3dth Annual Symposium on Foundations of Computer Science, pages 282-291, Nov. 1993.

Digital Library

Google Scholar

[3]

J. A. Aslam and S. E. Decatur. Specification and simulation of statistical query algorithms for efficiency and noise tolerance. J. Comput. Syst. Sci., 56(2):191-208, April 1998.

Digital Library

Google Scholar

[4]

A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich. Weakly learning D NF and characterizing statistical query learning using fourier analysis. In Proceedings of the 26th Annual A CM Symposium on Theory of Computing, pages 253-262, May 1994.

Digital Library

Google Scholar

[5]

S. E. Decatur. Statistical queries and faulty PAC oracles. in Proceedings of the 6th Annual A CM Workshop on Computational Learning Theory. ACM Press, 1993.

Digital Library

Google Scholar

[6]

S. E. Decatur. Learning in hybrid noise environments using statistical queries. In D. Fisher and H.-J. Lenz, editors, Learning from Data: Artificial Intelligence and Statistics V. Springer Verlag, 1996.

Google Scholar

[7]

M. Kearns. Efficient noise-tolerant learning from statistical queries. In Proceedings of the 25th Annual A CM Symposium on Theory of Computing, pages 392-401, 1993.

Digital Library

Google Scholar

Cited By

View all

Budroni AMårtensson E(2024)Further improvements of the estimation of key enumeration with applications to solving LWECryptography and Communications10.1007/s12095-024-00722-116:5(1163-1182)Online publication date: 13-Jun-2024
https://doi.org/10.1007/s12095-024-00722-1
Divesh ALeong JAlexandra V(2024)Worst-Case to Average-Case Hardness of LWE: An Alternative PerspectiveTheory of Cryptography10.1007/978-3-031-78017-2_11(308-336)Online publication date: 28-Nov-2024
https://doi.org/10.1007/978-3-031-78017-2_11
Dao QJain A(2024)Lossy Cryptography from Code-Based AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_2(34-75)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68382-4_2
Show More Cited By

Index Terms

Noise-tolerant learning, the parity problem, and the statistical query model
1. Computing methodologies
  1. Machine learning
2. Mathematics of computing

Recommendations

Efficient noise-tolerant learning from statistical queries

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 ...
Noise-tolerant learning, the parity problem, and the statistical query model

We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. Our algorithm runs in polynomial time for the case ...
General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science

We derive general bounds on the complexity of learning in the statistical query model and in the PAC model with classification noise. We do so by considering the problem of boosting the accuracy of weak learning algorithms which fall within the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing

May 2000

756 pages

ISBN:1581131844

DOI:10.1145/335305

Chairmen:
Frances Yao,
Eugene Luks

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC00

Sponsor:

SIGACT

STOC00: The 32nd Annual ACM Symposium on Theory of Computing

May 21 - 23, 2000

Oregon, Portland, USA

Acceptance Rates

STOC '00 Paper Acceptance Rate 85 of 182 submissions, 47%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

103
Total Citations
View Citations
664
Total Downloads

Downloads (Last 12 months)100
Downloads (Last 6 weeks)13

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Budroni AMårtensson E(2024)Further improvements of the estimation of key enumeration with applications to solving LWECryptography and Communications10.1007/s12095-024-00722-116:5(1163-1182)Online publication date: 13-Jun-2024
https://doi.org/10.1007/s12095-024-00722-1
Divesh ALeong JAlexandra V(2024)Worst-Case to Average-Case Hardness of LWE: An Alternative PerspectiveTheory of Cryptography10.1007/978-3-031-78017-2_11(308-336)Online publication date: 28-Nov-2024
https://doi.org/10.1007/978-3-031-78017-2_11
Dao QJain A(2024)Lossy Cryptography from Code-Based AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_2(34-75)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68382-4_2
Budroni AMårtensson E(2023)Improved Estimation of Key Enumeration with Applications to Solving LWE2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206474(495-500)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206474
Ding LBian SZhang J(2023)PIMA-LPN: Processing-in-memory Acceleration for Efficient LPN-based Post-Quantum Cryptography2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247891(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247891
Bombar MCouteau GCouvreur ADucros C(2023)Correlated Pseudorandomness from the Hardness of Quasi-Abelian DecodingAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38551-3_18(567-601)Online publication date: 9-Aug-2023
https://doi.org/10.1007/978-3-031-38551-3_18
Couteau GDucros C(2023)Pseudorandom Correlation Functions from Variable-Density LPN, RevisitedPublic-Key Cryptography – PKC 202310.1007/978-3-031-31371-4_8(221-250)Online publication date: 2-May-2023
https://doi.org/10.1007/978-3-031-31371-4_8
Esser AZweydinger F(2023)New Time-Memory Trade-Offs for Subset Sum – Improving ISD in Theory and PracticeAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30589-4_13(360-390)Online publication date: 16-Apr-2023
https://doi.org/10.1007/978-3-031-30589-4_13
Liu HYu Y(2023)A Non-heuristic Approach to Time-Space Tradeoffs and Optimizations for BKWAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22969-5_25(741-770)Online publication date: 25-Jan-2023
https://doi.org/10.1007/978-3-031-22969-5_25
Guo QMårtensson EStankovski Wagner P(2022)Modeling and simulating the sample complexity of solving LWE using BKW-style algorithmsCryptography and Communications10.1007/s12095-022-00597-015:2(331-350)Online publication date: 9-Aug-2022
https://doi.org/10.1007/s12095-022-00597-0
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Efficient noise-tolerant learning from statistical queries

Noise-tolerant learning, the parity problem, and the statistical query model

General bounds on statistical query learning and PAC learning with noise via hypothesis boosting