PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:1810.05369v4stat.MLcs.LG

TL;DR

The paper asks whether explicit regularization changes neural-network generalization relative to the NTK and whether the resulting regularized optimum can be attained. It uses margin theory and new kernel lower-bound techniques, then proves polynomial-time noisy-gradient optimization for infinite-width regularized networks. On a constructed distribution, regularized neural nets learn with O(d) samples while NTK predictors require Ω(d^2), and weakly regularized loss selects maximum normalized-margin solutions.

  • Problem

    Existing NTK analyses provide convergence and generalization results, but their equivalence with neural-network gradient descent breaks under explicit ℓ2 regularization.

  • Method

    The paper combines margin theory, kernel sample-complexity lower bounds based on feature focus, and perturbed optimization dynamics for regularized infinite-width networks.

  • Results

    O(d) samples suffice for the optimal ℓ2-regularized neural net, whereas NTK-span predictors cannot succeed with o(d^2) samples; noisy gradient descent finds an infinite-width global optimizer in polynomial iterations.

  • Takeaways & Limitations

    Explicit regularization can yield better margins, generalization, and sample efficiency than the corresponding kernel method while remaining globally optimizable in the infinite-width setting.

  • Takeaways & Limitations

    The polynomial-time optimization guarantee is stated for infinite-width networks, and the discrete-time result additionally assumes Lipschitz gradients for Φ and V.

Abstract

from arXiv · show

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 $Ω(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.

1 Introduction

The paper argues that explicit regularization can give neural networks better generalization and sample efficiency than their induced NTK, while also studying whether regularized optima are computationally attainable.

  • Motivation: Over-parameterized gradient descent can learn a predictor in the RKHS induced by the NTK, whose generalization can be analyzed as a kernel method.This connection holds under sufficient over-parameterization, suitable initialization scale, and learning-rate scheduling.
  • Motivation: Explicit regularization breaks the usual equivalence between neural-network gradient descent and NTK prediction.The paper focuses on regularizers such as weight decay, which are useful in practice but outside prior kernel-equivalence analyses.
  • Kernel lower bounds: The paper develops sample-complexity lower bounds for NTK methods that apply to both classification and squared ℓ2 loss, even with infinite over-parameterization.The proof intuition is that regularization enables adaptive informative features, whereas the kernel cannot focus on them.
  • Optimization and experiments: Noisy gradient descent reaches a global optimizer for infinite-width two-layer networks with ℓ2-regularized loss in polynomially many iterations.The paper also empirically reports improved margin and generalization with explicit regularization.
  • Margin theory: Weakly regularized logistic loss on homogeneous networks selects the maximum normalized-margin solution among networks with the same architecture.The regularizer coefficient is taken to be very small, approaching zero.

2 Generalization of Regularized Neural Net vs. NTK Kernel

The paper compares explicitly regularized neural nets with fixed NTK predictors on a distribution whose signal lies in two coordinates and whose remaining coordinates are noise. Regularization enables a larger margin and a provable sample-complexity advantage over NTK kernel methods.

  • Sample-complexity comparison: O(d) samples suffice for the global ℓ2-regularized logistic-loss optimizer, whereas NTK predictors require Ω(d^2) samples.The theorem states that with o(d^2) samples, no predictor in the NTK training-data span can achieve small generalization error, while the regularized neural net can learn with O(d) samples.
  • Setting: The constructed distribution places all signal in the first two coordinates, while the remaining d −2 coordinates are random noise.The first two coordinates and the label follow four equally likely cases; coordinates k ≥3 are independent uniform random bits.
  • Mechanism: Regularization lets the neural net find informative, data-adaptive features that are easier for the final-layer weights to separate.For this distribution, four ReLU neurons aligned with ±e1 and ±e2 are sufficient to fit the data.
  • Mechanism: The NTK uses a fixed feature space and therefore cannot adapt its features to the informative coordinates.Its training-data-span predictors must rely heavily on random features, which can fit training data but generalize poorly.
  • Margin theory: Weakly regularized logistic-loss minimizers achieve the maximum normalized margin among networks with the same homogeneous architecture.This margin result holds regardless of network depth or width and supports the neural network generalization argument.
  • Lower-bound technique: The NTK lower bound applies beyond classification, including standard 0-1 classification and squared ℓ2 loss, and uses a novel fixed-kernel lower-bound technique.The technique argues that focusing on a small number of informative features would require a very high RKHS norm.

3 Perturbed Wasserstein Gradient Flow Finds Global Optimizers in Polynomial Time

The section models infinite-width neural networks as distributions over hidden-unit parameters and analyzes perturbed Wasserstein gradient flow with small uniform noise. Under stated regularity and homogeneity assumptions, the dynamics converge to global or approximate global minimizers in polynomial time.

  • Main optimization result: For infinite-width two-layer networks with ℓ2-regularized loss, noisy gradient descent finds a global optimizer in polynomially many iterations.This result addresses optimization of the regularized objective rather than only kernel-like regimes.
  • Relation to prior work: The analysis provides explicit polynomial convergence rates, contrasting prior infinite-width Wasserstein-flow results that establish convergence without rates or can require exponential time in dimension.The comparison concerns a slightly different perturbed flow algorithm.
  • Distributional neural-network formulation: Infinite-width neural networks are modeled as distributions over weights, with the loss and regularizer represented by functionals of that distribution.The framework uses a convex loss, a positive regularizer on the unit sphere, and 2-homogeneous network and regularizer components.
  • Perturbed dynamics: Noisy gradient descent adds small uniform noise over the unit sphere, maintaining mass in descent directions and informally reinitializing a small fraction of neurons.The perturbation is designed to ensure that descent directions remain available throughout optimization.
  • Polynomial-time convergence: Under regularity assumptions and existence of the flow, perturbed Wasserstein gradient flow reaches an ϵ-approximate global minimum in polynomial time.The theorem specifies polynomial dependence on the error threshold, dimension, and regularity-related parameters.
  • Technical boundary: A discrete-time version also admits polynomial-time convergence when the network and regularizer have Lipschitz gradients, avoiding the assumption that a continuous-time solution exists.The discrete update uses a step size η and the same perturbation and transport terms.

4 Weak Regularizer Guarantees Max Margin Solutions

Weak regularization drives the global optimum of a positive-homogeneous network toward the maximum normalized margin. Combining this margin result with complexity bounds yields width-aware architectural conclusions and generalization guarantees.

  • Scope of the theorem: Theorem 4.1 applies to any continuous positive-homogeneous prediction function, not only two-layer ReLU networks.The network parameterization satisfies f(x; cΘ) = c^a f(x; Θ) for c > 0.
  • Max-margin characterization: As λ approaches zero, the normalized margin of the global regularized logistic-loss optimum converges to the maximum margin for separable positive-homogeneous predictors.The result applies beyond two-layer ReLU networks, including feedforward ReLU networks of arbitrary depth and width.
  • Optimization interpretation: The margin intuition is a trade-off: the loss favors larger margins, while the weak regularizer favors smaller parameter norms.This explains why small regularization selects high-margin solutions under homogeneity.
  • Approximate optimization: Approximate minimizers of the regularized loss can achieve margins approximating the maximum margin, extending the result beyond exact global optimization.This approximate-margin statement is given in Theorem C.2.
  • Generalization: Combining the margin theorem with neural-network complexity bounds gives width-free generalization bounds that scale mainly with C γ⋆,M q(q−1)/2√n.The bound includes a smaller-order term ϵ(γ⋆,M).
  • Effect of width: Larger network architectures have at least as large a maximum normalized margin as smaller architectures, and their corresponding max-margin generalization bound is at least as good.The result follows by embedding a smaller network in the larger architecture.
  • Comparison with linear prediction: The max-margin architecture result differs from ℓ2-normalized linear prediction, where adding features can increase data norms and worsen generalization bounds.For neural networks, added neurons can be viewed as learned features and do not decrease the max-margin solution’s generalization bound.

5 Simulations

Simulations validate that explicit regularization improves neural-network generalization and that increasing hidden-layer width reduces test error while increasing margin.

  • Explicit regularization: Regularized two-layer networks generalize better than unregularized networks trained from the same initialization.The experiment uses a large initialization scale and compares λ = 5 × 10^-4 with λ = 0.
  • Width scaling: As hidden-layer width grows in two-layer networks, test error decreases and margin increases, matching the theoretical prediction.The paper reports this comparison as an empirical validation of its width-related theory.

6 Conclusion

The paper finds that explicitly ℓ2-regularized neural nets can generalize better than corresponding kernel methods. It also links weakly regularized cross-entropy optimization to maximum-margin solutions and establishes polynomial-time optimization only for infinite-width networks.

  • Explicitly ℓ2-regularized neural nets can generalize better than the corresponding kernel method.
  • Weakly regularized cross-entropy optimization favors solutions with maximum normalized margin among ReLU networks.
  • For infinite-width networks, a global minimizer of the regularized loss can be found in polynomial time.
  • Optimizing the margin of finite-sized neural networks remains a proposed direction for future work.

B.1 Lower Bound on NTK Kernel Generalization

This section proves that NTK kernel predictors incur constant test error when the sample size is below order d^2. The proof uses symmetry, kernel decomposition, polynomial approximation, and concentration arguments to show that the kernel cannot exploit the informative coordinates.

  • The kernel is decomposed into positive scalings of gradient-feature and ReLU-feature inner products.
  • n ≲ d^2 samples suffice for a high-probability lower bound applying to every NTK prediction coefficient vector β.
  • The kernel predictor misclassifies an Ω(1) fraction of test examples under distribution D.
  • Sign symmetry makes the first two coordinates contribute little to the prediction after pairing opposite-coordinate examples.
  • The resulting auxiliary prediction forces an incorrect sign on a constant-probability subset of equally likely test examples.
  • A polynomial approximation and concentration lemma establish a large auxiliary prediction with high probability when n is below order d^2.

B.2 Proof of Theorem 2.1

The proof combines the NTK lower bound with a constructive neural-network upper bound. A regularized network attains constant normalized margin and consequently a small generalization error, while the kernel retains the lower bound.

  • The NTK lower bound reduces the theorem to upper bounding the regularized neural-network generalization error.
  • With λ = poly(n)^-1, the regularized network achieves a margin that is a constant-factor approximation to the max-margin.
  • A network with at least 4 hidden units has constant norm, margin 1, and normalized margin Θ(1).
  • The margin bound yields the desired neural-network generalization guarantee, completing the comparison with the kernel lower bound.
  • Regression setting: The analogous regression argument uses truncated squared loss and a λ-regularized squared-error objective.
  • Regression setting: As λ → 0, the regularized regression optimizer’s loss approaches 0 and its norm approaches the minimum-norm interpolating solution.

C.1 Multi-class Setting

In the multi-class setting, weakly regularized cross-entropy solutions converge in normalized margin to the maximum achievable margin. The proof relies on global minimizer existence, diverging solution norm, and exponential loss scaling.

  • The loss is defined for prediction functions mapping examples to R^l, with labels drawn from [l].
  • The multi-class theorem assumes positive maximum normalized margin γ⋆ and proves γλ → γ⋆ as λ → 0.
  • A global minimizer of the regularized multi-class cross-entropy loss exists.
  • As λ decreases, the norm of the regularized minimizer diverges.
  • The proof compares exponential lower and upper bounds on cross-entropy using the achieved and maximum normalized margins.
  • Because γλ is always at most γ⋆, the lower-limit inequality yields convergence to γ⋆.

C.3 Proofs of Theorem 4.1

The binary result is obtained by reducing the problem to the two-class multi-class setting, preserving margins and regularized-loss minimizers. Generalization bounds then depend on normalized margin through a Rademacher-complexity argument.

  • The binary proof reduces to the multi-class case with l = 2, using a single real-valued score and logistic loss.
  • The relabeled multi-class margin equals the binary margin, so the two formulations have identical regularized-loss minimizers.
  • The generalization analysis bounds classification error using normalized training margin and Rademacher complexity for bounded-depth networks.
  • The bound depends on the data norm C, depth, sample size n, and inverse powers of the normalized margin.The supplied passages state that the dominant scaling is with C γ^(-q(q−1)/2) / √n.

D.1 Proof of Proposition D.1

The proposition is proved by combining margin-loss generalization bounds with Rademacher-complexity estimates for normalized, bounded-norm ReLU networks. Theorem E.4 supplies the optimization guarantee under regularity and homogeneity assumptions.

  • The proof applies a classical margin-loss theorem to Rademacher-complexity bounds for depth-q networks.
  • The hypothesis class assumes bounded input norm, while the regularity conditions require convex smooth regularization and bounded Lipschitz functions on the sphere.
  • A depth-related caveat is that although the explicit depth factor decreases, the normalized margin may also decrease under stricter norm constraints.
  • The normalized-margin bound is obtained by rescaling parameters to preserve the network function while controlling Frobenius norms.
  • Under 2-homogeneity and the stated assumptions, noisy dynamics reach within 2ϵ of the global infimum by time tϵ.
  • The proof separates progress from average descent and progress from a negative directional derivative, with noise amplifying mass in descent directions.

E.3 Missing Proofs for Theorem E.4

The missing-proof section establishes the noisy Wasserstein-gradient-flow convergence result through bounds on moments, objective changes, and directional descent. It also gives a discrete-time analogue with polynomial convergence.

  • Integration-by-parts identities and boundedness arguments control the evolution of the particle distribution and its second moment.
  • The objective's change is related to average particle velocity, while sufficiently small noise keeps additional noise terms controlled.
  • The contradiction argument shows that a persistent descent direction must induce a substantial change in the objective.
  • The discrete-time update also achieves an ϵ-global objective gap for suitable noise and step size, with polynomial iteration complexity.
  • The resulting discrete-time guarantee is min0≤t≤tϵ L[ρt] − L⋆ ≤ ϵ.

F.1 Test Error and Margin vs. Hidden Layer Size

The simulations test the predicted relationship between hidden-layer width, margin, and test error on synthetic data and MNIST. They report decreasing test error and increasing margin as width grows.

  • The experiment varies hidden-layer size and measures both margin and test error on synthetic data and MNIST.
  • Test error decreases while margin increases as hidden-layer size grows, matching the theoretical prediction.
  • On synthetic data, networks use 2^i hidden units for i from 4 to 10, with 20 trials averaged at each size.
  • At hidden-layer size 27 or greater, all synthetic-data trials fit the training data perfectly.

F.2 Neural Net and Kernel Generalization vs. Training Set Size

Experiments compare regularized two-layer neural networks with a ReLU-feature kernel method as training-set size varies, showing lower neural-network test error as n grows.

  • The experiment plots generalization error against n using a trained neural net and an ℓ2 kernel method with ReLU features.The ground truth is a random neural network with six hidden units, while the trained network uses as many hidden units as examples.
  • The networks are trained for 20000 steps with λ = 10^-8, averaging results over 100 trials per plot point.
  • Two-layer nets clearly outperform the ℓ2 kernel method in test error as n grows.Classification uses 0-1 error, while regression uses squared error.
  • As λ decreases, the one-dimensional network’s normalized margin approaches the ideal ℓ1 SVM objective.The comparison uses 1000 evenly spaced normalized ReLU features because the exact feature vector is intractable.
Loading 1810.05369v4…