PaperlayerView exact revision on arXiv

Source-linked AI summary

Implicit Regularization in Deep Learning

Behnam Neyshabur

arXiv:1709.01953v2cs.LG

TL;DR

Deep learning generalization remains difficult to explain because highly expressive networks can be trained successfully despite computational and capacity challenges. This dissertation studies implicit regularization, develops complexity and invariance-aware methods, and finds improved generalization from Path-SGD-style optimization. It also identifies degeneracies that make invariance-based analyses depend on parameters and architecture.

  • Problem

    Highly expressive, over-parameterized networks can generalize despite computational intractability and multiple training-error-minimizing solutions, raising questions about optimization bias and suitable complexity control.

  • Method

    The dissertation analyzes complexity measures, norm-based and PAC-Bayes guarantees, neural-network invariances, and optimization algorithms including Path-SGD and data-dependent path normalization.

  • Results

    The dissertation reports that implicit regularization is central to generalization, and that Path-SGD achieves better generalization error than SGD across fully connected and recurrent benchmarks.

  • Takeaways & Limitations

    Complexity measures and optimization algorithms should reflect neural-network invariances, while implicit regularization provides a central lens for understanding deep-learning success.

  • Takeaways & Limitations

    Invariance analyses depend on parameter-dependent degeneracies, including inactive ReLU units and inserted linear layers that can increase paths without increasing the span dimension.

Abstract

from arXiv · show

In an attempt to better understand generalization in deep learning, we study several possible explanations. We show that implicit regularization induced by the optimization method is playing a key role in generalization and success of deep learning models. Motivated by this view, we study how different complexity measures can ensure generalization and explain how optimization algorithms can implicitly regularize complexity measures. We empirically investigate the ability of these measures to explain different observed phenomena in deep learning. We further study the invariances in neural networks, suggest complexity measures and optimization algorithms that have similar invariances to those in neural networks and evaluate them on a number of learning tasks.

TOYOTA TECHNOLOGICAL INSTITUTE AT CHICAGO

The thesis committee includes Nathan Srebro as thesis advisor, alongside Yury Makarychev, Ruslan Salakhutdinov, and Gregory Shakhnarovich.

  • Nathan Srebro is listed as the thesis advisor.
  • The committee information identifies the advisor and additional committee members.
  • Yury Makarychev, Ruslan Salakhutdinov, and Gregory Shakhnarovich are also listed.

Implicit Regularization in Deep Learning

The document identifies Nathan Srebro as thesis advisor and includes a dedication in memory of Sina Masihabadi.

  • Nathan Srebro is identified as the thesis advisor.
  • These front-matter statements provide advisor and dedication information.
  • The document is dedicated in memory of Sina Masihabadi.

Introduction

The dissertation studies why highly expressive, over-parameterized neural networks can generalize despite computational and statistical challenges, emphasizing implicit regularization by optimization. It develops complexity measures, invariance-aware algorithms, and empirical evaluations across network types and tasks.

  • Introduction: Deep learning uses complex, highly over-parameterized models that learn hierarchies of representations and have achieved broad practical success.
  • Introduction: Neural-network learning involves expressive power, optimization, and generalization, respectively concerning realizable functions, training loss minimization, and unseen-data performance.
  • Introduction: Learning moderately sized networks is computationally intractable, so architectural expressiveness alone does not explain practical trainability and generalization.
  • Introduction: The dissertation studies implicit regularization, complexity measures, generalization, and their relationship in deep learning.
  • Main Contributions: It proves norm-based capacity-control bounds, including cases where bounds are independent of hidden-unit count, and connects PAC-Bayes theory with sharpness.
  • Main Contributions: It investigates SGD conditions associated with flat minima and empirically compares complexity measures for explaining implicit regularization and generalization.
  • Main Contributions: The dissertation characterizes neural-network invariances, proposes the Path-norm and Path-SGD, and reports better generalization error than SGD across fully connected and recurrent benchmarks.
  • Main Contributions: A unified data-dependent path-normalization framework connects Path-SGD and batch normalization while varying data dependence and optimization choices.

Preliminaries

The preliminaries define statistical learning, neural-network architectures, shared parameters, forward computation, and ReLU properties. They frame generalization as the gap between population and training performance.

  • Statistical Learning: Statistical learning uses an i.i.d. training set to learn a predictor with low expected classification error under an unknown distribution.
  • Statistical Learning: Training error estimates expected loss, but minimizing it can yield memorization and poor expected performance; their difference is the generalization error.
  • Statistical Learning: The framework defines expected and empirical margin losses, with margin zero corresponding to classification loss and training error.
  • Neural Networks: A feedforward network is represented by a directed acyclic graph, edge weights, and an activation function, with outputs computed by forward propagation.
  • Activation Functions: ReLU is defined as σRELU(z)=max(z,0) and has Lipschitz, idempotency, and non-negative homogeneity properties used in the analysis.
  • Neural Networks: Weight sharing maps multiple edges to common parameters, covering standard networks when the mapping is one-to-one and shared-weight architectures otherwise.
  • Neural Networks: Network size, depth, and width are defined through edge count, longest directed path, and maximum vertex in-degree.
  • Neural Networks: Time-unfolded recurrent networks are feedforward networks with shared weights mapping input sequences to output sequences.

Generalization

Implicit regularization is identified as the section topic.

  • The section introduces implicit regularization as its subject.

Generalization and Capacity Control

The paper studies capacity control through model classes and complexity measures, using generalization bounds based on class size, VC dimension, Rademacher complexity, norms, and PAC-Bayes quantities. It argues that parameter count and Lipschitz control alone can be inadequate, while combined measures such as sharpness and norm can provide more informative capacity control.

  • Model-class capacity limits the predictors considered so that training and population errors can be related.
  • Union bounds over finite model classes yield generalization guarantees whose complexity term is ln |F|.
  • VC dimension provides a parameter-precision-independent capacity measure and supports generalization bounds for classification model classes.
  • In over-parameterized settings, total parameter count is too weak to explain generalization, while simply bounding network Lipschitzness can produce unreasonable capacity bounds.
  • Rademacher complexity bounds for feedforward networks can depend on layerwise ℓ1 norms of hidden-unit weights, with capacity scaling roughly as a product of these quantities.
  • PAC-Bayes analysis separates expected sharpness from KL divergence, motivating their joint use with norm to control capacity.

On the Role of Implicit Regularization in Generalization

Experiments show that increasing network size can continue improving test performance after training error reaches zero, contrary to size-based capacity control. The paper interprets this pattern as evidence for optimization-induced implicit regularization, potentially favoring low-complexity or low-norm solutions.

  • The matrix-factorization analogy motivates implicit norm regularization as an inductive bias whose capacity can be independent of hidden-unit count.
  • Classical size-based reasoning predicts overfitting after approximation error is reduced and capacity control is lost.
  • Experiments on MNIST and CIFAR-10 found that test error continued decreasing after larger networks had already reached zero training error.
  • Even with five percent random labels, test error continued decreasing as network size exceeded the size needed for zero training error.
  • The results suggest that optimization implicitly favors solutions with low complexity, potentially explaining generalization despite very large parameter counts.

Norm-based Capacity Control

The paper characterizes norm-based capacity control in feedforward networks, showing when regularization yields width-independent bounds and when capacity remains depth-sensitive or becomes infinite. It also relates per-unit, path, and overall regularization to convexity, computational limits, and inductive bias.

  • Capacity: Overall ℓp regularization controls capacity independently of network width only when p ≤2, even with bounded depth.
  • Capacity: When 1/p + 1/q < 1, increasing width and depth can reduce the magnitude control while preserving capacity, making the capacity infinite.
  • Per-unit and path regularization: For layered networks, path regularization and per-unit regularization are equivalent, but this equivalence fails for non-layered graphs with paths of different lengths.
  • Per-unit and path regularization: Per-unit regularization can realize every function with an optimal representation whose non-input subgraph is a tree, eliminating incentives to share lower-level units.
  • Capacity: Even when the total weight magnitude is bounded, capacity can depend exponentially on network depth.
  • Convexity: Overall ℓ2 regularization with two layers is equivalent to a convex neural network using ℓ2-constrained hidden units and ℓ1 output regularization.

ℓp-regularized Linear Predictors

This section develops norm-based capacity control for linear predictors and layered networks, using Rademacher-complexity tools and structural properties of the resulting measures. It characterizes when norm constraints control capacity independently of network size and identifies remaining depth dependence and open questions.

  • Linear predictors: Rademacher-complexity bounds for linear separators with bounded ℓp norm are established using Massart and Khintchine-Kahane inequalities.The proof also uses a contraction lemma and norm inequalities.
  • Layered networks: Theorem 3 bounds the complexity of layered networks by applying contraction and matrix-to-vector reductions across layers.The argument applies the same layerwise control recursively and bounds the first layer separately.
  • Complexity measure: The measure ψ^d_p,q is shown to be a semi-norm by proving convexity of its level sets, non-negative homogeneity, and the triangular inequality.For non-negative homogeneous activations, convex combinations of represented functions remain in the model class under the stated conditions.
  • Capacity control: Norm-based capacity control is insufficient without network-size control for depth d > 2 with per-unit p > 1 or overall p > 2 regularization.The result contrasts with linear models and two-layer networks, where weaker dimensional or size dependence is available.
  • Limitations and open questions: Even ℓ2 regularization retains an exponential dependence on depth, while the precise polynomial norm dependence in margin-based bounds may not be tight.The discussion also identifies unresolved questions about depth-independent ψ-based capacity control and how ψ^d_p,q changes with depth.

Sharpness/PAC-Bayes Generalization Bounds

This section derives PAC-Bayes generalization guarantees based on expected sharpness for ReLU networks. The bound uses spectral-norm perturbation control and conditions governing layer interactions and activation-pattern sensitivity, yielding linear rather than exponential depth dependence.

  • Sharpness control: The sharpness of a network is bounded using the product of the spectral norms of its layers.This connects perturbation sensitivity to a layerwise spectral-norm complexity measure.
  • Generalization bound: PAC-Bayes is combined with a perturbation bound to derive a generalization guarantee for d-layer ReLU networks with margin γ.The proof first bounds perturbations preserving the margin and then evaluates the corresponding KL term.
  • Result: For reasonable σ, the resulting generalization error depends linearly on depth and has no exponential dependence on depth.Optimizing σ balances expected sharpness against the norm term in the bound.
  • Empirical verification: The conditions hold for trained networks in the reported MNIST experiment, with empirical suggestions µ ≥ 1/4, C2 ≤ 5, and C3 ≤ 3.Figure 6.1 verifies the conditions on a 10-layer perceptron with more than 10,000,000 parameters.
  • Conditions: Condition C1 controls weak interactions between successive layers, while C2 and C3 control activation-pattern changes and unusually large incoming-weight norms.The perturbation analysis separates unchanged-activation error from error caused by changed activations.

6.3.1 Supporting Lemma

This section supplies supporting bounds used in the sharpness analysis and compares condition behavior between random initialization and learned weights. The reported comparison finds the learned network similar to its initialization on these conditions.

  • Empirical comparison: Figures 6.2–6.4 compare conditions C1, C2, and C3, together with output values, for random initialization and learned weights.The comparisons cover condition number, activation flips, incoming-weight norms, and outputs.
  • Empirical comparison: The learned network is reported to be very similar to its random initialization in terms of the three conditions.This conclusion is stated for a 10-layer network with 1000 hidden units per layer trained on MNIST.
  • Error decomposition: The analysis separates perturbation effects associated with changed activation patterns from those associated with perturbed linear transformations.This decomposition supports the later control of activation-sensitive sharpness terms.
  • Supporting bounds: The supporting argument uses induction and matrix perturbation bounds to control errors when one or more network layers are replaced by noisy weights.The proof considers base cases and an induction step over the number of noisy layers.

6.4.3 Proof of Lemma 29

This proof bounds perturbation errors caused by activation changes across multiple noisy layers. It uses induction to show how these terms scale with perturbation magnitude and combines them with earlier bounds.

  • Error decomposition: The proof represents perturbation error using differences between activation-pattern matrices of the perturbed and unperturbed networks.The resulting expression is decomposed into terms involving activation changes and noisy weights.
  • Induction: The base case separately controls one noisy layer and accounts for the dependence of the perturbed activation pattern on the random perturbation.The argument bounds the activation change with high probability before taking the relevant expectation.
  • Scaling: When each layer perturbation scales as O(σ), the first term is O(σ) while the last two terms decay at least as O(σ^3/2).The latter terms are therefore excluded from the reported computation of Err.
  • Induction: The induction step extends the bound from k noisy layers to k + 1 noisy layers by substituting the previous error estimate into the decomposed expression.The resulting terms are bounded using the same approach as the earlier perturbation lemma.

Empirical Investigation

The empirical investigation compares complexity measures across true-versus-random-label training and varying network sizes, emphasizing that norm, margin, sharpness, and PAC-Bayes terms must be interpreted jointly. Several measures track generalization patterns, but their explanatory power varies with architecture and scale.

  • Scaling and margins: Norm-based capacity control requires accounting for output scaling because zero/one loss is invariant to scaling while norms are not.The authors use margins to make norm comparisons meaningful when training error is zero.
  • Scaling and margins: The robust margin γ_margin is defined by allowing a small fraction ϵ of training points to fall below the threshold γ.Reasonable choices of ϵ between 0.001 and 0.1 leave the qualitative and relative empirical results almost unchanged.
  • PAC-Bayes measures: Sharpness and norm jointly provide a better predictor of generalization error than sharpness alone in the PAC-Bayes experiments.The bound combines expected sharpness and KL divergence, whose relationship depends on the perturbation scale σ.
  • True labels versus random labels: Random-label models require higher norm than true-label models at fixed expected sharpness, indicating that sharpness alone is not a scale-invariant capacity measure.The comparison uses VGG networks trained on subsets of CIFAR10 and evaluates norm relative to margin or expected sharpness.

Generalization

The paper frames deep learning through expressive power, optimization, and generalization. Generalization concerns performance on unseen data, alongside the ability to represent functions and minimize training loss.

  • Learning properties: Deep learning models are studied through expressive power, optimization, and generalization.These properties concern representable functions, efficient training-loss minimization, and performance on unseen data, respectively.

Invariances

The paper studies function-preserving transformations in neural networks and seeks geometries, regularizers, and optimization methods that respect these invariances. For ReLU networks, path-based analysis characterizes degrees of freedom and shows that node-wise rescaling accounts for the generic invariances under stated conditions.

  • Optimization geometry matters because gradient descent is tied to the ℓ2 norm, while the appropriate geometry for deep networks may also determine implicit regularization.The paper explicitly links geometry, optimization method, and regularizer choice.
  • Node-wise rescaling preserves a ReLU network’s function by scaling incoming weights by α and outgoing weights by 1/α.These transformations motivate invariant geometries and optimization algorithms.
  • Gradient descent is not rescaling invariant and can perform poorly on networks whose incoming weights are unbalanced.Scaling down an edge increases its gradient, producing updates unlike those expected from a rescaling-invariant rule.
  • For RNNs, feasible node-wise rescalings are characterized completely, and all such transformations can be expressed in the stated form.The characterization motivates optimization algorithms and measures invariant to these transformations.
  • The path formulation separates parameter and input dependence, yielding dG(w) ≤ rank J(w), with equality when the path vectors span the full path space.The path-Jacobian rank is generically |E| − |Vinternal|, except on a measure-zero parameter subset.
  • Under the full-span condition, node-wise rescaling is the only invariance for a fixed-architecture ReLU network, while degenerate parameter settings can have additional invariances.The null-space dimension depends on the weights, and uniform-over-input analyses may underestimate invariances that hold only for many inputs.

Path-Normalization for Feedforward and Recurrent Neural Networks

The chapter develops the path-regularizer as a rescaling-invariant complexity measure and derives Path-SGD as an approximate steepest-descent method for it, including extensions to shared-weight networks. It also analyzes computational cost and the contribution of higher-order terms.

  • Path-regularizer: The path-regularizer sums squared products of weights over all input-to-output paths and is invariant to node-wise rescaling.It equals the minimum ℓ2 per-unit regularizer among rescaling-equivalent feed-forward networks.
  • Path-SGD: Path-SGD uses an approximate steepest-descent step with respect to the path-regularizer and estimates gradients from training mini-batches.The stochastic update applies the path-based geometry to parameter optimization.
  • Higher-order terms: The κ(2) term can be zero for feed-forward and convolutional networks but nonzero for recurrent networks when a parameter repeats along a path.This distinction arises from interactions between edges sharing a parameter on the same input-output path.
  • Shared weights: For shared-weight networks, the resulting update remains invariant to all feasible node-wise rescalings, including a simpler update using only κ(1).The theorem establishes invariance for both the full and simplified update rules.
  • Computational cost: Computing κ(1) adds O(dTH^2) time beyond the standard O(BdTH^2) mini-batch gradient, while κ(2) adds O(dTH^2(T + H)).Relative to mini-batch gradients, the additional costs are O(1/B) and O((T + H)/B), respectively.

Experiments on Path-SGD

Experiments compare Path-SGD with SGD and AdaGrad on feed-forward and recurrent networks. Across the reported tasks, Path-SGD often reaches accuracy faster, generalizes better, and is less affected by unbalanced parameterizations, while very long recurrent sequences remain difficult.

  • Feed-forward experiments: Path-SGD is compared with SGD and AdaGrad on MNIST, CIFAR-10, CIFAR-100, and SVHN.The feed-forward experiments use four benchmark datasets and examine objective, training-error, and test-error curves.
  • Initialization: Unbalanced initialization considerably hurts SGD and AdaGrad, whereas Path-SGD performs essentially the same as under balanced initialization.This tests the predicted invariance of Path-SGD updates under rescaling-equivalent parameterizations.
  • Feed-forward experiments: Path-SGD can reach the same accuracy faster and sometimes achieves lower final generalization error than SGD and AdaGrad.The authors attribute the better test behavior to implicit regularization from steepest descent under the path-regularizer.
  • Recurrent experiments: On the addition problem, a simple identity-initialized RNN with path-normalization achieves 0% error on sequences of length 750, while all other methods fail.For sequences of length 1000, RNNs fail even with Path-SGD.
  • Recurrent experiments: On sequential MNIST, RNN-Path generally outperforms other RNN methods except LSTMs, including on the long-term-dependency task.The comparison is based on test-error rates reported in Table 10.2.
  • Recurrent experiments: Path-normalization outperforms RNN-ReLU and RNN-tanh while narrowing the gap with LSTMs by 57% on PTB and 54% on text8.These comparisons are reported for the recurrent-network benchmarks in Table 10.3.

Data-Dependent Path Normalization

The unified framework combines path-based complexity measures with data-dependent normalization choices and optimization schemes. It connects Path-SGD, batch normalization, and diagonal natural-gradient methods while analyzing their invariance properties.

  • Framework: The framework chooses a per-node complexity measure γv and a normalization matrix R that controls the degree of data dependence.Non-data-dependent diagonal choices recover path-SGD-like behavior, while covariance-based choices introduce data dependence.
  • Framework: It combines each choice of R with either normalized reparameterization or approximate steepest descent, yielding DDP-Normalization and DDP-SGD variants.Both approaches can be implemented through forward and backward propagation.
  • Invariances: DDP-SGD is invariant to weight rebalancing regardless of the amount of data dependence, whereas DDP-Normalization lacks equally favorable invariance properties.The distinction reflects whether optimization acts more directly on the represented function or on its parameterization.
  • Natural-gradient connection: With a suitable data-dependent choice of Rv, DDP-SGD is equivalent to the diagonal natural gradient.The equivalence is stated for the diagonal Fisher-information approximation.
  • Batch normalization: Batch normalization can be viewed as a reparameterization of the same standard feed-forward model class, with a different optimization geometry.The reparameterization makes node complexity explicit so it can be implicitly regularized by stochastic gradient updates.
  • Conclusion: The dissertation’s central conclusion is that implicit regularization from optimization is a key component of deep-learning generalization and success.The work supports this view through complexity measures, optimization algorithms, invariance analysis, and experiments.
Loading 1709.01953v2…