Testing Assumptions of Learning Algorithms
summary
Introduces a framework that testable agnostic learning actually either accepts and outputs a classifier with error ≤ OPT+ε or rejects, using a concrete moment-matching tester that checks low-degree monomial moments up to degree k. Key tools are k-wise independence and sandwiching polynomials to transfer pseudorandomness fooling results into proofs. Achieves halfspace algorithms in time about d^{O(1/ε^2)} (improvable) and a faster d^{O(log 1/ε)} TDS learner under Gaussians; shows separations requiring exponential samples for some classes.
AI-written summary · about
chapters (10)
- 0:00Introduction to learning
- 4:09Hardness and testing
- 10:44Testable agnostic learning
- 13:38Moment matching tool
- 19:01Sandwiching polynomials
- 29:14Limitations and extensions
- 33:32Advanced distribution testing
- 36:46Universal testable learning
- 43:00Learning with distribution shift
- 50:47Advanced results and conclusion
related talks
37mEfficient Algorithms for Reliable Machine Learning
35mTesting Noise Assumptions of Learning Algorithms
35mSublinear-Time Algorithms in Learning
17mEfficient Testable Agnostic Learning for Halfspaces
48mA New Paradigm for Learning with Distribution Shift
01h 06mAnalytic Methods for Supervised Learning III
48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory
01h 30mAnalytic Methods for Supervised Learning IV