Training (Overparametrized) Neural Networks in Near-Linear Time
summary
Proves that training two‑layer ReLU networks with width m and n samples runs in near‑linear time by replacing the costly J J^T computation (previously Ω(m n^2)) with an approximate Newton update plus a sketching preconditioner, cutting per‑iteration cost to Θ(m n). Shows linear convergence so total time is Θ(m n log(1/ε)) under overparameterization (m ≥ poly(n)); uses randomized linear algebra and regression preconditioning and gives provable bounds.
AI-written summary · about
chapters (7)
- 0:00Intro
- 2:38General introduction: Motivation
- 5:05General introduction: Recent advance
- 8:09Overparametrized neural network
- 9:28Our result
- 10:36Main technique
- 14:58Future directions
related talks
50mLearning and Generalization in Over-parametrized Neural Networks, Going Beyond Kernels
01h 14mRecent Developments in Over-parametrized Neural Networks, Part I
01h 04mRandomized Embeddings and Neural Networks
01h 04mNeural Networks meet Nonparametric Regression: Generalization by Weight Decay and Large...
59mTutorial: Statistical Learning Theory and Neural Networks I
01h 03mUnderstanding ReLU Networks Through Graph Problems and Polyhedra
01h 14mRecent Developments in Over-parametrized Neural Networks, Part II
19mOn the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks