Sketching for Proving Generalization of Support Vector Machines
summary
Proves tighter margin-based generalization bounds for binary linear SVMs on linearly separable data by using a randomized Johnson-Lindenstrauss sketch of hyperplanes, not to design an algorithm but to compress the hypothesis class. Main claims: removes an extra log factor from prior bounds, achieves optimal dependence on the confidence delta and on the margin gamma, and gives a matching lower bound. Sketch length is k = O((log n)/gamma^2) with per-query failure about 1/n^2, and the reduction succeeds for the analyzed separable regime.
AI-written summary · about
chapters (7)
- 0:00Sketching and SVMs intro
- 10:32Support vector machines and generalization
- 17:40Why sketching in proofs
- 24:02Sketching discretizes hyperplanes
- 33:05Finalizing generalization proof
- 37:25Summary of sketching
- 42:44Q&A
related talks
44mConcentration Inequalites in Learning with Kernels
01h 04mSketching and Randomized Linear Algebra
56mSparsifying Generalized Linear Models
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
01h 17mGeneralization I
01h 18mGeneralization III
59mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I
45mTractability And Overparametrization In Some Simple Models