Analytic Methods for Supervised Learning II
summary
Shows that a decision tree with t leaves has L1(f) ≤ t for t‑leaf tree and uses that to get sparse approximations via zeroing small coefficients; states Mansour conjecture for s‑term DNF and a proven bound of about s^{log log s} · log(1/ε) for the L1 of an approximating polynomial. Describes the low‑degree algorithm (time ≈ n^d), GF(2) feature expansion (time ≈ n^{3d}), an N^{3k/4}‑time k‑junta approach, LP formulation with ≈ n^d variables for L1 minimization, and agnostic/boosting reductions.
AI-written summary · about
chapters (13)
- 0:00Start
- 5:43The Entropy Influence Conjecture
- 27:54The Naive Algorithm
- 36:45Generalization
- 37:35Feature Expansion
- 43:37Structural Theorem
- 53:35Agnostic Learning
- 59:41Classification Error
- 1:01:47The Quantification of a Probability Distribution
- 1:02:11Distribution Specific Agnostic Learning
- 1:03:18Learning an Unknown Disjunction
- 1:07:18Low Degree Algorithm
- 1:23:34Define a Boosting Algorithm
related talks
01h 01mNearest Neighbor Methods II
56mSparsifying Generalized Linear Models
44mConcentration Inequalites in Learning with Kernels
31mFourier Representations in Probabilistic Inference
25mLearning Formulas in Finite Variable Logics
44mActive Regression via Linear-Sample Sparsification
35mSublinear-Time Algorithms in Learning
30mPreconditioning In Sparse Linear Regression Using Graphical Structure