Randomized Embeddings and Neural Networks
summary
Shows that two-layer ReLU training admits an exact convex reformulation with variables polynomial in sample size but exponential in feature rank, and that a randomized zonotope vertex sampling scheme cuts the exponential dependence by sampling hyperplane chambers. Tools are JL-style and l2→l1 embeddings, Dvoretzky-type geometry and zonotope solid angles; complexity scales like n^r or 1/θ where θ is a cone angle. Experiments (Airline 120M×28: 500-d sketch → 1.06 approximation) and 400 UCI/CIFAR-10 runs report faster, more reliable solutions than SGD/Adam.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:32Workshop logistics
- 3:54Randomized embeddings overview
- 9:02Johnson-Lindenstrauss lemma
- 12:35Least squares via sketching
- 17:47Quantized embeddings & LSH
- 25:13Neural networks convex reformulations
- 32:02Training two-layer ReLU complexity
- 37:30Convex training via random sampling
- 43:20Convex vs nonconvex benchmarks
- 46:15Interpreting networks via embeddings
- 48:03Clifford algebra for networks
- 56:40Open problems
- 57:00Q&A
related talks
59mTutorial: Statistical Learning Theory and Neural Networks I
56mRandom Embeddings, Matrix-valued Kernels and Deep Learning
01h 34mAlgorithmic High-Dimensional Geometry II
50mLearning and Generalization in Over-parametrized Neural Networks, Going Beyond Kernels
29mApplying Randomized Methods for Zonotope Enumeration and...
19mTraining (Overparametrized) Neural Networks in Near-Linear Time
33mProvably Efficient Algorithms for Training Deep Networks
17mUniversality of Neural Networks