Predicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory
summary
Survey claims: PAC learning is often computationally hard, so the field studies agnostic and restricted-distribution settings and gets concrete algorithms and limits. Key tools include L1 polynomial regression reducing agnostic learning to low-degree polynomial approximators, and Fourier analysis where degree-1 Fourier coefficients identify linear threshold functions under uniform noise. Known bounds: Gaussian halfspace agnostic algorithms run roughly n^{1/ε^2}, quasi-agnostic methods give OPT·√log(1/OPT) or PTAS-style tradeoffs, one-dimensional distribution learners achieve about 3·OPT + ε with sample-optimal, near-linear-time routines, and recent work attains near-OPT, dimension-independent guarantees for single Gaussians and product distributions.
AI-written summary · about
chapters (10)
- 0:00Introduction and basic models
- 3:20Function classes and complexity
- 9:00Formalizing the PAC model
- 14:20Efficient learning algorithms
- 17:40Hardness results in learning
- 22:10Agnostic learning with noise
- 25:40Learning under nice distributions
- 30:25Learning with incomplete data
- 38:55Unsupervised learning
- 44:02Recent progress and outlook
related talks
35mSublinear-Time Algorithms in Learning
01h 30mAnalytic Methods for Supervised Learning IV
35mTesting Noise Assumptions of Learning Algorithms
17mEfficient Testable Agnostic Learning for Halfspaces
01h 06mAnalytic Methods for Supervised Learning III
59mTesting Assumptions of Learning Algorithms
39mA PAC Approach to Application-Specific Algorithm Selection
37mEfficient Algorithms for Reliable Machine Learning