Robust Learning of a Single Neuron via Sharpness
summary
Proves that, under two mild distributional conditions (anticoncentration along one good vector and 1/t^4 tail control of one-dimensional projections), running mini-batch SGD on a convex surrogate with a sufficiently large batch size and small step size converges in O(log 1/ε) iterations and uses O(D·f(1/ε)) samples to return a weight with error C·OPT+ε. Handles many activations including GeLU and Swish, derives a provable local sharpness/error-bound around a target region, and requires initialization at zero.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:29Agnostic learning single neuron
- 3:58Minimizing mean squared loss
- 6:35Main result assumptions
- 8:26Comparison prior work
- 11:47Related optimization work
- 13:44Convex surrogate sharpness
- 18:32SGD convergence region
- 21:05Results nonmonotone activations
- 21:47Open questions
- 22:52Proof sketch ReLU sharpness
- 29:35Q&A
related talks
50mLearning and Generalization in Over-parametrized Neural Networks, Going Beyond Kernels
58mFirst-Order Stochastic Optimization
46mOn the Foundations of Deep Learning: SGD, Overparametrization, and Generalization
01h 01mRobustness, Stochastics, Uncertainty 2
13mThe dynamical view of machine learning: implicit biases of large learning rates
33mProvably Efficient Algorithms for Training Deep Networks
56mHow neural networks learns simple functions?
46mSmooth Nonconvex Min-Max Optimization