mlsanityData to 7 Oct 2026

Towards Understanding Learning in Neural Networks with Linear Teachers

arXiv 2101.02533 ↗First posted 7 Jan 2021cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

Can a neural network minimizing cross-entropy learn linearly separable data? Despite progress in the theory of deep learning, this question remains unsolved. Here we prove that SGD globally optimizes this learning problem for a two-layer network with Leaky ReLU activations. The learned network can in principle be very complex. However, empirical evidence suggests that it often turns out to be approximately linear. We provide theoretical support for this phenomenon by proving that if network weights converge to two weight clusters, this will imply an approximately linear decision boundary. Finally, we show a condition on the optimization that leads to weight clustering. We provide empirical results that validate our theoretical analysis.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 30 of its 41 references that are in the map. First posted on arXiv 7 Jan 2021.

Builds on

30 of 41 references.

References · 30

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  4. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  6. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  7. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  8. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  9. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  10. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  11. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
  12. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
18 more
  1. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  2. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  3. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  4. 2020Directional convergence and alignment in deep learningcited by 172
  5. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  6. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  7. 2018Stochastic subgradient method converges on tame functionscited by 120
  8. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  9. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  10. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  11. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  12. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  13. 2020Learning Parities with Neural Networkscited by 77
  14. 2020Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracycited by 70
  15. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  16. 2019Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Modelscited by 53
  17. 2018Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalizationcited by 21
  18. 2019Decoupling Gating from Linearitycited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 4; 2024: 3; 2025: 2; 2026: 1.

19 papers.

Sort:

  1. 2022Modality Competition: What Makes Joint Training of Multi-modal Network Fail in Deep Learning? (Provably)cited by 115
  2. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 84
  3. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  4. 2022Implicit Regularization Towards Rank Minimization in ReLU Networkscited by 53
  5. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  6. 2021On Margin Maximization in Linear and ReLU Networkscited by 34
  7. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  8. 2022Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networkscited by 27
  9. 2023The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networkscited by 23
  10. 2023Understanding Unimodal Bias in Multimodal Deep Linear Networkscited by 18
  11. 2021A Theoretical Analysis of Fine-tuning with Linear Teacherscited by 17
  12. 2023Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputscited by 16
7 more
  1. 2025Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architecturescited by 14
  2. 2024Simplicity Bias of Two-Layer Networks beyond Linearly Separable Datacited by 11
  3. 2024When Are Bias-Free ReLU Networks Effectively Linear Networks?cited by 3
  4. 2024Theoretical Understanding of Learning from Adversarial Perturbationscited by 2
  5. 2022Probability-Dependent Gradient Decay in Large Margin Softmaxcited by 0
  6. 2025Directional Convergence, Benign Overfitting of Gradient Descent in leaky ReLU two-layer Neural Networkscited by 0
  7. 2026On the Rate of Convergence of GD in Non-linear Neural Networks: An Adversarial Robustness Perspectivecited by 0