Research map / Optimization / Implicit bias and generalization
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Leaky ReLU activations for SGD training | Two-layer over-parameterized network · Linearly separable data | non-zero updates to global minimum: M_k = \frac{\norm{\boldsymbol{w}^*}^2}{\alpha^2} + O\Bigg( \frac{\norm{\boldsymbol{w}^*}^2}{\min\{\eta,\sqrt{\eta}\}}\Bi | Helped |
| Use Leaky ReLU activations and SGD | Two-layer over-parameterized network · Linearly separable data | 0-1 test error: \frac{8}{n}\Bigg(\frac{\norm{\boldsymbol{w}^*}^2}{\alpha^2} + O\Bigg(\frac{\norm{\boldsymbol{w}^*}^2}{\min\{\eta,\sqrt{\ | Helped |
| Replace Leaky ReLU with ReLU | Two-layer over-parameterized network · Linearly separable training sets | empirical hinge loss at local minimum: > \frac{1}{2} | Hurt |
| Use sufficiently few hidden units with ReLU | SGD on orthogonal basis examples · Orthogonal basis examples | probability of convergence to non-global minimum: k \le \log_2 (\frac{d}{-\ln(\delta)}) | Hurt |
| Increase the hidden-unit count to the stated threshold with ReLU | SGD on orthogonal basis examples · Orthogonal basis examples | probability of convergence to global minimum: k \ge \log_2 (\frac{2d}{\delta}) | Helped |
| Use a larger learning rate | Leaky ReLU SGD with 50 hidden neurons · MNIST digits 3 and 5 | generalization performance | Hurt |
| Use a larger learning rate | Leaky ReLU SGD with 50 hidden neurons · MNIST digits 3 and 5 | number of updates | Hurt |
Closest papers by meaning
- An Improved Analysis of Training Over-parameterized Deep Neural Networks (NeurIPS 2019 · similarity 0.91)
- On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications (ICLR 2022 · similarity 0.91)
- Towards Understanding Learning in Neural Networks with Linear Teachers (ICML 2021 · similarity 0.90)
- On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective (NeurIPS 2019 · similarity 0.90)
- Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise (ICML 2021 · similarity 0.90)
- Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.