Concentration Inequalites in Learning with Kernels

on YouTube ↗44m

" summary

Shows that Johnson–Lindenstrauss preserves margins up to (1+ε) while projecting to k = O(ε^-2 log n) dimensions, so SVM decision boundary and pairwise distances remain accurate. Gives fast sparse projections (Kane and Nelson style) where each column has s = O(1/ε · log(1/δ)) nonzeros, and points out concentration must handle negative dependence. Describes kernel approximation via random Fourier features with m = O(ε^-2 d log(1/δ)) to produce explicit embeddings, and LP‑type sampling to solve SVMs from the kernel matrix.

AI-written summary · about

" chapters (37)

1. 0:00Intro
2. 1:27Statement
3. 2:38JL vis Measure Concentration on Sphere
4. 3:21Applications of Johnson-Lindenstrauss
5. 4:08Probabilistic Method
6. 4:33Explicit Mapping
7. 5:49Input data as Feature vectors
8. 6:44The classification problem setup
9. 7:48Linear classifiers Linear classifiers
10. 8:34Max Margin One can work with parallel hyperplanes
11. 11:05The SVM formulation
12. 11:33SVMs represent data as Convex hulls
13. 12:02The Dual formulation
14. 12:42Support vectors and separating hyperplane
15. 13:53SVMs as non-linear classifiers
16. 15:17The Kernel Trick
17. 15:53Popular Kernels
18. 17:20Running Time of SVM Solvers
19. 18:41JL and SVMs: Take 1
20. 22:56Concentration for Faster JL
21. 23:52Negative Dependence and Concentration
22. 25:28Data as Kernels
23. 25:59Random sampling for LP
24. 26:37Abstract LP type problems
25. 27:15What is common?
26. 27:46LP Type problem: abstract framework
27. 28:50Solving LP type problems
28. 29:14Random Sampling Algorithm for LP Type
29. 30:03Sub-Exponential Algorithm for LP-type
30. 30:46Examples: Combinatorial dimension
31. 31:10Running time for SVM
32. 32:43Back to the Primal
33. 34:08Random sampling!
34. 35:03Invarant kernels
35. 36:01Random Kitchen Sinks for Gaussian RBF
36. 37:34JL for SVMs. Take 3: Faster approximation
37. 39:53Open Problems

" related talks

• 46mSketching for Proving Generalization of Support Vector MachinesKasper Larsen · Sketching and Algorithm Design 2023
• 01h 22mGeneralization IVPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019
• 01h 30mAnalytic Methods for Supervised Learning IVAdam R. Klivans · Real Analysis Boot Camp 2013
• 01h 02mTheory and Big DataRavi Kannan · Big Data Boot Camp 2013
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 06mAnalytic Methods for Supervised Learning IIIAdam R. Klivans · Real Analysis Boot Camp 2013
• 01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch IIDavid P. Woodruff · Foundations of Data Science Boot Camp 2018
• 01h 12mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)