Analytic Methods for Supervised Learning III
summary
Shows an algorithmic pipeline: a projected gradient descent routine approximately solves the polynomial L1 minimization in time poly(n,1/ε,t), which gives an agnostic sparse-polynomial learner; a novel boosting by branching programs construction converts a weak learner into a strong one (t = O(log(1/ε)/γ^2) via a martingale/Zuma bound); an agnostic random relabeling trick keeps the marginal distribution fixed so KM-style weak learners (factor ~8·opt) boost to opt+ε; also proves Hermite-based low-degree approximators of degree O(1/ε^2) for Gaussian halfspaces, and recalls NP-hardness of finding better-than-trivial separators.
AI-written summary · about
chapters (12)
- 0:00Start
- 1:57What Is Boosting
- 2:30The Weak Learning Assumption
- 6:11Example of a Boosting Algorithm
- 10:21Boosting Algorithm
- 16:29Output Hypothesis
- 22:23Zuma's Inequality
- 28:59Weak Learning Assumption
- 40:26Learning Geometric Concepts
- 41:38Support Vector Machine
- 54:01The Hermit Polynomials
- 1:04:19Approximate Convex Sets
related talks
59mTesting Assumptions of Learning Algorithms
35mSublinear-Time Algorithms in Learning
56mSparsifying Generalized Linear Models
01h 12mRecent Progress in High-Dimensional Learning
01h 18mOptimization I
48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory
01h 01mRobustness, Stochastics, Uncertainty 1
37mEfficient Algorithms for Reliable Machine Learning