SQ Lower Bounds for Learning Halfspaces with Massart Noise
summary
Proves an SQ lower bound: no statistical-query algorithm with polynomially many queries and polynomial accuracy learns a linear threshold function under Massart noise rate eta = 1/3 to error better than 1 / poly(log n), even when OPT is exponentially small (≈ exp(−K) with K ≈ log n). Key ingredients are a mixture-of-Gaussians construction and moment-matching to produce two distributions A,B plus a union-of-intervals set J realized as a degree-K polynomial threshold function, using non-Gaussian component analysis and moment-matching to force SQ hardness.
AI-written summary · about
chapters (19)
- 0:00Intro
- 3:05Agnostic Noise
- 4:34Hardness
- 5:46Random Noise
- 6:50Proof Idea
- 8:30Better Noise Models
- 11:06Error Rates
- 12:19What Can We Achieve?
- 14:06SQ Lower Bounds
- 15:11Lower Bounds for Functions
- 16:06New Lower Bound
- 17:24Problem
- 19:51Need
- 21:58B Construction
- 23:12Fix
- 24:50Parameters
- 26:52Improvement
- 27:11Conclusions
- 27:37Further Work
related talks
01h 12mRecent Progress in High-Dimensional Learning
17mEfficient Testable Agnostic Learning for Halfspaces
35mTesting Noise Assumptions of Learning Algorithms
01h 30mAnalytic Methods for Supervised Learning IV
59mTesting Assumptions of Learning Algorithms
44mConcentration Inequalites in Learning with Kernels
53mOptimality in Locally Private Estimation and Learning
01h 30mHigh-Dimensional Statistics II