Analytic Methods for Supervised Learning I
summary
A concrete claim: decision trees become learnable by finding the largest Fourier coefficients and outputting the sign of a sparse polynomial. The algorithm (the Kushilevitz–Mansour style routine) recursively estimates prefix sum-of-squares values via queries, has recursion depth N and width ≤ 1/θ², and runs poly(N,1/θ) to recover all coefficients ≥ θ. Consequences and open points: quasi‑poly time algorithms exist without queries but polynomial time is unknown; structural questions like Mansour's conjecture and efficient learning of k-junta functions remain unresolved.
AI-written summary · about
chapters (8)
- 0:00Intro
- 1:10Supervised Learning
- 6:07Decision Trees
- 12:45Hardness
- 17:14Outline
- 22:18Query Access
- 30:18Occams Razor
- 33:38Algorithm
related talks
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
01h 01mNearest Neighbor Methods II
31mFourier Representations in Probabilistic Inference
01h 04mLearning Staircases
44mConcentration Inequalites in Learning with Kernels
01h 05mRecovering Hidden Sparsity via Sum of Squares
35mSublinear-Time Algorithms in Learning
01h 12mRecent Progress in High-Dimensional Learning