Recent Progress in High-Dimensional Learning
Talkat Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020) · 2020-08-19..08-28·
summary
Shows polynomial‑time algorithms that learn half‑spaces under Massart noise up to error η+ε, first via an improper partitioned classifier and now via a proper algorithm that matches η+ε. Key tools: a leaky ReLU convex surrogate, two simple lemmas (W* has negative surrogate loss if λ≥η and margin γ; any high 0/1 error induces a slab with large surrogate loss), and an iterative min‑max procedure using slab reweighting plus projected gradient descent. Empirical test on UCI Adults adds noise outside a target group and finds standard learners amplify subgroup harm while the Massart‑robust method preserves subgroup accuracy.
AI-written summary · about
chapters (12)
- 0:00Start
- 4:56MODELS FOR NOISE
- 13:08RECENT RESULTS
- 17:59OUTLINE
- 23:32CONVEX SURROGATES, CONTINUED
- 28:02A GENERAL FRAMEWORK
- 32:50ANALYZING THE GAME
- 34:45PROOF OF LEMMA 1
- 39:36PROOF OF LEMMA 2
- 42:55THE ALGORITHM
- 46:57EXPERIMENTS
- 51:30DISCUSSION
related talks
31mSQ Lower Bounds for Learning Halfspaces with Massart Noise
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
37mEfficient Algorithms for Reliable Machine Learning
59mTesting Assumptions of Learning Algorithms
30mComputational Barriers For Learning Some Generalized Linear Models