# Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel

arXiv: https://arxiv.org/abs/1810.05369 · HTML: https://mlsanity.com/paper/1810.05369/

## Key facts

- Cited by 131 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2018.

## Built on by (most cited first, 30 of 131)

- [TRAK: Attributing Model Behavior at Scale](https://mlsanity.com/paper/2303.14186/) (2023)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Surrogate Gap Minimization Improves Sharpness-Aware Training](https://mlsanity.com/paper/2203.08065/) (2022)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Self-supervised Learning is More Robust to Dataset Imbalance](https://mlsanity.com/paper/2110.05025/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [DR3: Value-Based Deep Reinforcement Learning Requires Explicit Regularization](https://mlsanity.com/paper/2112.04716/) (2021)
- [Convex Analysis of the Mean Field Langevin Dynamics](https://mlsanity.com/paper/2201.10469/) (2022)
- [A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network](https://mlsanity.com/paper/2102.02410/) (2021)
- [Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscape](https://mlsanity.com/paper/2402.01258/) (2024)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [Understanding the role of importance weighting for deep learning](https://mlsanity.com/paper/2103.15209/) (2021)
- [Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalization](https://mlsanity.com/paper/2307.11007/) (2023)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Why Do You Grok? A Theoretical Analysis of Grokking Modular Addition](https://mlsanity.com/paper/2407.12332/) (2024)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [The Tunnel Effect: Building Data Representations in Deep Neural Networks](https://mlsanity.com/paper/2305.19753/) (2023)
- [Continual Learning in Linear Classification on Separable Data](https://mlsanity.com/paper/2306.03534/) (2023)
- [Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data](https://mlsanity.com/paper/2310.02541/) (2023)
- [Feature emergence via margin maximization: case studies in algebraic tasks](https://mlsanity.com/paper/2311.07568/) (2023)
- [Gradient-Based Feature Learning under Structured Data](https://mlsanity.com/paper/2309.03843/) (2023)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [Birth-death dynamics for sampling: Global convergence, approximations and their asymptotics](https://mlsanity.com/paper/2211.00450/) (2022)
- [Properties of the After Kernel](https://mlsanity.com/paper/2105.10585/) (2021)
- [Sparse Neural Additive Model: Interpretable Deep Learning with Feature Selection via Group Sparsity](https://mlsanity.com/paper/2202.12482/) (2022)
- [The Asymmetric Maximum Margin Bias of Quasi-Homogeneous Neural Networks](https://mlsanity.com/paper/2210.03820/) (2022)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [Overparameterization of deep ResNet: zero loss and mean-field analysis](https://mlsanity.com/paper/2105.14417/) (2021)

## Abstract (arXiv)

Recent works have shown that on sufficiently over-parametrized neural nets, gradient descent with relatively large initialization optimizes a prediction function in the RKHS of the Neural Tangent Kernel (NTK). This analysis leads to global convergence results but does not work when there is a standard ℓ2 regularizer, which is useful to have in practice. We show that sample efficiency can indeed depend on the presence of the regularizer: we construct a simple distribution in d dimensions which the optimal regularized neural net learns with O(d) samples but the NTK requires Omega(d2) samples to learn. To prove this, we establish two analysis tools: i) for multi-layer feedforward ReLU nets, we show that the global minimizer of a weakly-regularized cross-entropy loss is the max normalized margin solution among all neural nets, which generalizes well; ii) we develop a new technique for proving lower bounds for kernel methods, which relies on showing that the kernel cannot focus on informative features. Motivated by our generalization results, we study whether the regularized global optimum is attainable. We prove that for infinite-width two-layer nets, noisy gradient descent optimizes the regularized neural net loss to a global minimum in polynomial iterations.