Efficient Testable Agnostic Learning for Halfspaces
summary
First efficient algorithm that is testable agnostic for learning halfspaces under Gaussian (or strongly log-concave) inputs, running in polynomial time and producing a proper halfspace classifier. The algorithm achieves error O(opt)+œµ against adversarial labels, uses sum‑of‑squares relaxations and connections to pseudorandomness, and later extensions make the tester tolerant (accepting distributions within a small ε fraction of the assumption) while keeping computational efficiency. Joint work with multiple coauthors.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 2:17Agnostic learning framework
- 5:08Motivation for testable learning
- 7:42First testable learners
- 9:52Limitations and improvements
- 11:37Tolerant algorithms
- 12:40Open problems
- 13:56Q&A
related talks
01h 30mAnalytic Methods for Supervised Learning IV
59mTesting Assumptions of Learning Algorithms
35mSublinear-Time Algorithms in Learning
35mTesting Noise Assumptions of Learning Algorithms
01h 12mRecent Progress in High-Dimensional Learning
37mEfficient Algorithms for Reliable Machine Learning
48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory
31mSQ Lower Bounds for Learning Halfspaces with Massart Noise