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

By Colin Wei, Jason D. Lee, Qiang Liu, Tengyu Ma. 2018

275 citations recorded by the source corpus.

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 $\ell_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(d^2)$ 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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “…ﬁeld analysis to establish that for inﬁnitely wide neural networks, the empirical distribution of the neural network parameters can be described as a Wasserstein gradient ﬂow (Mei et al., 2018; Chizat & Bach, 2018a; Sirignano & Spiliopoulos, 2018; Rotskoﬀ & Vanden-Eijnden, 2018; Wei et al., 2018).”
Few-Shot Learning via Learning the Representation, Provably (2020, background): “3 or Wei et al. (2019)), E xi n iid ∼ p,z∼N(0,I)[‖Φ(X) ⊤z‖∞] .”
TRAK: Attributing Model Behavior at Scale (2023, unknown): “, 2019), optimization (Wei et al., 2019), and robustness (Gao et al.”
Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks (2019, methodology): “For two-layer networks, a series of works used the mean ﬁeld method to establish the evolution of the network parameters via a Wasserstein gradient ﬂow (Mei et al., 2018b; Chizat & Bach, 2018a; Wei et al., 2018; Rotskoff & Vanden-Eijnden, 2018; Sirignano & Spiliopoulos, 2018).”
Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks (2019, background): “Existing generalization bounds for deep neural networks (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2018; Golowich et al., 2018; Dziugaite and Roy, 2017; Arora et al., 2018; Li et al., 2018; Wei et al., 2019; Neyshabur et al., 2019) based on uniform convergence usually cannot p”
Why Do Better Loss Functions Lead to Less Transferable Features? (2020, background): “Other work has shown that dropout on intermediate layers has both implicit and explicit effects, and both are important to accuracy [74].”
Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations (2019, background): “For example, Wei et al. (2018) showed polynomial convergence rate under certain conditions.”
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, unknown): “While some works have shown quantitative results by modifying the dynamics (Mei et al., 2019; Wei et al., 2019; Chizat, 2019), we do not take this path in order to stay close to the way neural networks are used in practice and because our numerical experiments suggest that those modiﬁcations are…”
Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin (2019, background): “Other works show global minimizers of regularized logistic loss are equivalent to margin maximizers, in linear cases [Rosset et al., 2004] and for deep networks [Wei et al., 2018, Nacson et al., 2019].”
Do Wide and Deep Networks Learn the Same Things? Uncovering How Neural Network Representations Vary with Width and Depth (2020, background): “…to their corresponding kernels (Matthews et al., 2018; Lee et al., 2018; Jacot et al., 2018), but substantial differences exist between behavior in this inﬁnite width limit and the behavior of ﬁnite-width networks (Novak et al., 2018; Wei et al., 2019; Chizat et al., 2019; Lewkowycz et al., 2020).”
Confident Learning: Estimating Uncertainty in Dataset Labels (2019, unknown): “Once label errors are found, we observe ordering label errors by the normalized margin: p̂(ỹ=i;x,θ)−maxj 6=i p̂(ỹ=j;x,θ) (Wei et al., 2018) works well.”
Continual Learning in Linear Classification on Separable Data (2023, methodology): “In Remark 3.2, we explained why existing analysis techniques (e.g., from Rosset et al. (2004); Wei et al. (2019)) are less suitable for our setting, in which the scale of iterates is also of great importance (and not only their direction).”
Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks (2020, background): “(ii) Another line of research applies the mean-field analysis for NNs (Mei et al., 2018; Chizat & Bach, 2018; Sirignano & Spiliopoulos, 2019a; Rotskoff & Vanden-Eijnden, 2018; Mei et al., 2019; Dou & Liang, 2019; Wei et al., 2018; Sirignano & Spiliopoulos, 2019b; Fang et al., 2019; Araújo et al., 20”