Analytic Methods for Supervised Learning IV

on YouTube ↗01h 30m

" summary

Shows that agnostic learning of a single halfspace under the Gaussian reduces to finding a low‑degree polynomial: Hermite/Fourier coefficients give approximation error O(1/√D), so D = Θ(1/ε^2) suffices; algorithm uses polynomial regression to recover that polynomial. Connects approximation to noise stability = Θ(√ε) (Boolean and Gaussian) and uses PCA on positive examples plus Caffarelli contraction and Gaussian surface‑area bounds (Ball/Nazarov: ≤ O(n^1/4)) to extend to intersections and general convex sets; runtime grows with degree and K.

AI-written summary · about

" chapters (5)

1. 0:00Polynomial approximation
2. 12:48Noise stability and learning
3. 29:28Boolean and Gaussian analysis
4. 52:16Surface area and convex sets
5. 1:10:01Learning with PCA

" related talks

• 17mEfficient Testable Agnostic Learning for HalfspacesArsen Vasilyan · Meet the Fellows Welcome Event Fall 2024
• 01h 31mUnsupervised LearningSantosh Vempala · The Brain and Computation Boot Camp
• 01h 12mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 36mPrivately Learning High-Dimensional DistributionsGautam Kamath · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)
• 48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning TheoryRocco A. Servedio · Real-Time Decision Making
• 29mApproximating Spherical Gaussian MixturesAnanda Suresh · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 07mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis