Red Points and Blue Points
summary
Given independent n‑dimensional points labeled by an unknown intersection of k halfspaces with a soft margin ρ, the work gives an algorithm that PAC‑learns the classifier in time exponential in √(n log(1/ρ) log k) (more precisely 2^{O(√(n log(1/ρ) log k))}). This improves prior bounds exponential in k or 1/ρ, yields corollaries for low‑weight halfspaces on the Boolean cube, and matches SQ and cryptographic lower bounds up to logarithmic factors. Joint work with Shyamal Patel.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:28Red and blue points origin
- 3:38DNF and neural network hardness
- 6:28Computational vs sample complexity
- 10:28Polytope learning with margins
- 11:56Breakthroughs for two planes
- 13:01Lower bounds via queries and crypto
- 15:12Algorithm for halfspaces
- 20:46Algorithm overview
- 25:58Algorithm demo
- 34:51Complexity analysis
- 35:56Open problems
- 37:39Q&A
related talks
44mConcentration Inequalites in Learning with Kernels
01h 02mTheory and Big Data
01h 34mAlgorithmic High-Dimensional Geometry I
01h 12mRecent Progress in High-Dimensional Learning
41mOn the Average-case Complexity of the Nearest Boolean Vector to a Subspace
01h 14mRecent Progress in High-Dimensional Learning
01h 30mAnalytic Methods for Supervised Learning IV
45mTractability And Overparametrization In Some Simple Models