PaperlayerView exact revision on arXiv

Source-linked AI summary

Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation

Colin Wei, Tengyu Ma

arXiv:1905.03684v3cs.LGstat.ML

TL;DR

Norm-only Rademacher bounds can scale exponentially with network depth, while lower bounds make that dependence unavoidable without additional data properties. This paper develops data-dependent bounds using hidden-layer and Jacobian norms, with polynomial depth dependence under suitable empirical conditions. It also reports improved test performance from directly regularizing the Jacobian-based measure.

  • Problem

    Norm-only neural-network bounds can depend exponentially on depth, and lower bounds show this dependence is unavoidable when no additional training-data properties are considered.

    Source: §1 · pp. 1–2

  • Method

    The paper augments compositions of functions to make them Lipschitz and coverable, deriving bounds based on training-data hidden-layer and interlayer Jacobian norms.

    Source: §1 · pp. 2–3, §4 · p. 5

  • Results

    The resulting generalization bound scales polynomially rather than exponentially with depth when the network has good Lipschitz constants on the training data.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Directly regularizing the proposed complexity measure can improve test performance, and the bounds and augmentation procedure apply to sequences of function compositions.

    Source: §1 · p. 1, §9 · p. 14

    The presented theorem assumes a neural network with a smooth activation function.

    Source: §1 · p. 2

Abstract

from arXiv · show

Existing Rademacher complexity bounds for neural networks rely only on norm control of the weight matrices and depend exponentially on depth via a product of the matrix norms. Lower bounds show that this exponential dependence on depth is unavoidable when no additional properties of the training data are considered. We suspect that this conundrum comes from the fact that these bounds depend on the training data only through the margin. In practice, many data-dependent techniques such as Batchnorm improve the generalization performance. For feedforward neural nets as well as RNNs, we obtain tighter Rademacher complexity bounds by considering additional data-dependent properties of the network: the norms of the hidden layers of the network, and the norms of the Jacobians of each layer with respect to all previous layers. Our bounds scale polynomially in depth when these empirical quantities are small, as is usually the case in practice. To obtain these bounds, we develop general tools for augmenting a sequence of functions to make their composition Lipschitz and then covering the augmented functions. Inspired by our theory, we directly regularize the network's Jacobians during training and empirically demonstrate that this improves test performance.

1 Introduction

The paper develops data-dependent generalization bounds using hidden-layer and interlayer Jacobian norms, addressing the exponential depth dependence of norm-only bounds. It also reports that directly regularizing the Jacobian-based measure can improve test performance.

1 Introduction

  • The bounds use hidden-layer norms and interlayer Jacobian norms evaluated on training data, yielding polynomial dependence on these quantities and network depth when they are small.The paper contrasts these empirical quantities with a product of weight-matrix norms that can scale exponentially with depth.Source: §1 · p. 2
  • The bounds consider data-dependent properties beyond margin, including hidden-layer norms and interlayer Jacobian norms.The paper identifies the training margin as one established data-dependent property, while proposing these additional quantities.Source: §1 · pp. 1–2
  • For recurrent neural networks, the paper presents a generalization bound that scales polynomially in the same quantities as its standard-network bound.The cited prior RNN bounds either require parameter counting or depend exponentially on depth.Source: §1 · p. 2
  • The leading bound quantity, a sum of products of Jacobian and hidden-layer norms, grows for WideResNets trained without BatchNorm.The figure plots the distribution of this quantity for models trained with and without BatchNorm.Source: §1 · p. 2, Figure 1 · p. 3
  • The technical approach augments function compositions to make them Lipschitz at each layer, then covers the augmented family to obtain generalization bounds.The resulting neural-network bound scales polynomially rather than exponentially in depth when training-data Lipschitz constants are good.Source: §1 · p. 3
  • Directly regularizing the proposed complexity measure can improve test performance, and the paper reports improvements across several CIFAR10 settings.The reported settings include low learning rates, no data augmentation, and replacing BatchNorm with LayerNorm.Source: §1 · p. 3

2 Related Work

Related work studies implicit regularization, complexity-based bounds, noise stability, and data-dependent priors. The paper distinguishes its deterministic, covering-number approach from several neighboring methods and assumptions.

2 Related Work

  • Work on implicit regularization often studies minimum-norm or maximum-margin solutions, but most cited analyses use simplified settings that do not apply to larger neural networks.The passage notes an exception for [Wei et al., 2018].Source: §2 · p. 3
  • Neural-network Rademacher-complexity bounds form the paper's closest line of work, alongside PAC-Bayesian generalization bounds.The cited Rademacher-complexity works include [Neyshabur et al., 2015b, 2018, Bartlett et al., 2017, Golowich et al., 2017, Li et al., 2018a].Source: §2 · p. 3
  • Noise-stability methods relate network behavior on noisy inputs to generalization, while Arora et al. [2018] establish a guarantee for a compressed network under an appropriate noise distribution.The paper says its own bounds apply to the original network and do not rely on a particular noise distribution.Source: §2 · p. 4
  • Nagarajan and Kolter [2019] also use hidden-layer and Jacobian norms, but their bounds depend on inverse ReLU preactivations, whereas this paper treats smooth activations with an additional Jacobian factor.The passage says that additional factor is empirically small and that the bounds use Rademacher complexity and covering numbers rather than PAC-Bayes.Source: §2 · p. 4
  • Data-dependent-prior PAC-Bayes bounds analyze randomized classifiers sampled from a prior, whereas this paper analyzes a deterministic, fixed model.Source: §2 · p. 4

3 Notation

This section introduces notation for indicator functions, norms, derivatives, and covering numbers, including a data-point norm bound for the covered function class.

3 Notation

  • The softened indicator 1_≤κ is defined using a threshold κ and a linear transition to zero by 2κ.The passage states its piecewise values: 1 up to κ, 2 − t/κ between κ and 2κ, and 0 from 2κ onward.Source: §3 · p. 4
  • The section introduces the total derivative operator D, with Df(x) denoting the Jacobian of f at x.Source: §3 · p. 4
  • The function-class covering number N(ϵ, F, s) is defined as the maximum covering number over n-point datasets whose examples have norms at most s.The section also introduces a version parameterized by the norm bounds of multiple inputs.Source: §3 · pp. 4–5

4 Overview of Main Results and Proof Techniques

The section develops data-dependent Lipschitz augmentation and covering tools to address the gap between worst-case and training-data behavior. It uses these tools to bound augmented losses and connect the resulting covers to generalization bounds.

4 Overview of Main Results and Proof Techniques

  • When training examples satisfy the augmented indicators, the augmented loss equals the original training loss while remaining an upper bound on the original loss.The indicators encode bounds on hidden-layer norms and interlayer Jacobians; their parameters are chosen from training-data properties.Source: §4 · pp. 6–7

4.1 Overview of Computational Graph Covering

  • Covering a general computational graph can be reduced to covering its local composition rules, extending the sequential-composition approach.The bound assumes ordered nodes with bounded values and output Lipschitzness after earlier nodes are cut.Source: §4.1 · p. 7

4.2 Lipschitz Augmentation of Computational Graphs

  • Augmenting compositions with indicators on hidden-layer norms and interlayer derivatives makes worst-case Lipschitzness polynomial in depth-related parameters.The augmented output is polynomially Lipschitz with respect to internal nodes after earlier nodes are cut; it upper-bounds the original and agrees with it when the indicators hold.Source: §4.2 · p. 8

5 Covering of Computational Graphs

The section formalizes computational graphs and a release-Lipschitz condition to reduce covering a whole graph family to covering its local composition rules. Neural networks fit this framework by representing matrix operations and activations as separate nodes.

5.1 Formalization of computational graphs

  • A computational graph assigns each node a function of the input variables, formed by applying its composition rule to the functions of its direct predecessors.The paper formalizes the associated node functions recursively and also describes them as compositions of the node rule with predecessor functions.Source: §5.1 · p. 9
  • A feed-forward network with r weight matrices is represented by one input, 2r−1 internal nodes, and one output, with matrix operations and activations assigned separate nodes.The figure description specifies that odd-indexed layers multiply matrices and even-indexed layers apply the activation.Source: §5.1 · p. 9, Figure 3 · p. 9

5.2 Reducing graph covering to local function covering

  • Release-Lipschitzness requires the released graph to remain Lipschitz in each successively released internal node, given the other inputs.The nodes are released in a forest ordering, where each node depends only on the input nodes and earlier nodes.Source: §5.2 · p. 10
  • Under release-Lipschitzness and an output-collapse condition for oversized internal nodes, small covers of local composition rules yield a small cover of the graph family.The release-Lipschitz condition is specified in a forest ordering; the collapse condition requires the output to become constant when an internal node exceeds its bound.Source: §5.2 · p. 10

6 Lipschitz Augmentation of Computational Graphs

The section introduces Lipschitz augmentation for sequential computational graphs to address worst-case Lipschitz growth that can scale exponentially with depth. Combining augmentation with graph covering yields covering bounds for augmented graphs.

6 Lipschitz Augmentation of Computational Graphs

  • Before augmentation, the worst-case Lipschitz constant of sequential computational graphs can scale exponentially with depth.The required worst-case Lipschitzness can reflect a product of operation-level worst-case constants, much larger than average Lipschitzness on typical examples.Source: §6 · pp. 10–11
  • Lipschitz augmentation adds Jacobian nodes and uses user-defined bounds to control Jacobians between pairs of layers.The augmented loss uses soft indicators that truncate the function when a Jacobian exceeds its specified bound.Source: §6 · p. 11
  • The augmentation makes the resulting graph family release-Lipschitz under the stated assumptions on its composition rules and derivatives.The theorem's parameters are determined by the chosen bounds on Jacobians between layers.Source: §6 · pp. 11–12
  • Combining augmentation with graph-covering results gives covering-number bounds computable from bounds for individual function classes.The same tools are used to derive Rademacher complexity bounds for neural networks and RNNs.Source: §6 · p. 12
  • Adding indicators on internal-node norms yields augmented graphs that upper-bound their original counterparts and admit covering bounds.The covering expression includes terms for the node functions, their total derivatives, and the output function.Source: §6 · p. 12

7 Application to Neural Networks

The neural-network bound is derived by modeling the loss as a sequential computational graph, augmenting it, and covering the augmented loss. It depends on hidden-layer and interlayer Jacobian quantities, with no explicit width dependence.

7 Application to Neural Networks

  • Theorem 7.1 bounds generalization for positive-margin networks with a 1-Lipschitz activation whose derivative is Lipschitz.The bound is obtained by augmenting the loss with hidden-layer and Jacobian parameters, then covering the augmented loss.Source: §7 · pp. 12–13
  • The bound depends on hidden-layer norms and interlayer Jacobian quantities evaluated on training data, rather than explicitly on network width.The bound uses weight norms offset by reference matrices; these may avoid scaling with width when the differences are sparse.Source: §7 · p. 13
  • The same techniques extend to RNN generalization bounds that scale polynomially in depth through the corresponding hidden-layer and Jacobian quantities.The passage contrasts this with prior RNN bounds that require parameter counting or depend exponentially on depth.Source: §7 · p. 13

8 Experiments

The experiments report improved test error after Jacobian regularization in several CIFAR10 settings. They also examine regularization with BatchNorm and with LayerNorm replacing BatchNorm.

8 Experiments

  • The experiments directly regularize the classification-margin Jacobian with respect to outputs of normalization layers and after residual blocks.The authors reason that normalization controls hidden-layer norms, so Jacobian regularization also regularizes the product appearing in their bound.Source: §8 · p. 13
  • The reported WideResNet16 experiments use a Frobenius-norm threshold, with regularized layers selected at residual-block ends and after BatchNorm layers.In the LayerNorm setting, BatchNorm layers are replaced with LayerNorm.Source: §8 · pp. 13–14
  • Test error improves across the reported CIFAR10 settings, including low-learning-rate and no-data-augmentation conditions and a LayerNorm replacement for BatchNorm.The authors also report that their complexity measure avoids exponential depth scaling for a WideResNet trained on CIFAR10.Source: §8 · p. 14

9 Conclusion

The conclusion presents tighter generalization bounds based on hidden-layer and interlayer-Jacobian norms, supported by tools for augmenting and covering function compositions. It identifies arbitrary computational graph structures as a direction for future work.

9 Conclusion

  • The paper proves tighter generalization bounds that depend polynomially on hidden-layer norms and interlayer Jacobian norms.The bounds address how data-dependent properties affect generalization.Source: §9 · p. 14
  • The proof framework augments sequential computational graphs into Lipschitz families and then covers those families.The augmentation and covering procedure applies to any sequence of function compositions.Source: §9 · p. 14
  • Extending the techniques to arbitrary computational graph structures remains a direction for future work.The conclusion also describes follow-up work on simpler Jacobian-based bounds and an empirically effective algorithm.Source: §9 · p. 14

A Missing Proofs for Section 7

The proofs bound an augmented loss class by covering network layers and their Jacobians, then convert that complexity bound into a generalization guarantee. A union bound over parameter grids yields the stated results.

A Missing Proofs for Section 7

  • Theorem A.2 bounds the augmented loss class’s empirical Rademacher complexity using constraints on weights, hidden-layer norms, and interlayer Jacobians.The theorem’s activation is 1-Lipschitz with a Lipschitz derivative.Source: A Missing Proofs for Section 7 · p. 19
  • The proof represents the network as a computation graph and covers both its layer functions and Jacobian functions.The resulting augmented losses upper-bound the original losses.Source: A Missing Proofs for Section 7 · p. 19
  • Because the augmented loss upper-bounds margin loss and 0-1 loss, a standard Rademacher generalization bound gives a test guarantee.The argument uses the complexity bound for the augmented loss class.Source: A Missing Proofs for Section 7 · p. 21
  • A union bound over grids of parameter choices extends the bound to the stated theorems with probability 1 − δ.The proof grids choices for layer norms, Jacobians, matrix norms, and related parameters.Source: A Missing Proofs for Section 7 · p. 21

B Missing Proofs in Section 5

The composition lemma controls covering numbers by combining covers for an inner function and a Lipschitz outer function. The proof applies it inductively to computation graphs.

B Missing Proofs in Section 5

  • For graph families, induction removes a node in forest order, applies the composition lemma, and invokes the inductive hypothesis on the smaller graph.The remaining nodes retain the forest ordering needed for the induction.Source: B Missing Proofs in Section 5 · p. 22
  • When the outer family is κ-Lipschitz in its hidden input and collapses outside norm bounds, the composition cover has error κϵw + ϵu.Its log covering number is bounded by the sum of the component log covering numbers.Source: B Missing Proofs in Section 5 · p. 23
  • The proof first covers the inner functions, then constructs outer-function covers for their outputs, giving a product bound on cover size.The resulting cover size is at most N(ϵw, W, sx) · N(ϵu, U, (sh, sx)).Source: B Missing Proofs in Section 5 · p. 23

C Missing Proofs in Section 6

This section supplies proofs and technical tools for Lipschitz augmentation and applies them to a generalization bound for recurrent neural networks. It establishes release-Lipschitzness for hidden-state and Jacobian nodes, completes the complexity proof with a covering-number argument, and derives a 0-1 test-error bound using a union bound over parameters.

C Missing Proofs in Section 6

  • The missing proofs establish release-Lipschitzness for the graph family and use output-rule augmentation and covering arguments to derive Theorem 6.3.The augmentation makes the output constant outside specified norm thresholds, and the resulting bound upper bounds the original graph family’s output.Source: C Missing Proofs in Section 6 · pp. 24–25

D Technical Tools for Lipschitz Augmentation

  • Lemma D.1 shows that augmenting a loss with products of Jacobian norms and auxiliary released-Jacobian matrices makes it τ⋆-Lipschitz under the stated component-Lipschitz assumptions.The auxiliary matrices model Jacobian nodes already released from the computational graph.Source: D Technical Tools for Lipschitz… · pp. 25–26

E Application to Recurrent Neural Networks

  • Theorem E.1 gives a probability 1 − δ generalization guarantee for all RNNs when the activation is 1-Lipschitz and its derivative is ¯σφ-Lipschitz.The proof bounds the Rademacher complexity of an augmented RNN loss, then applies generalization and a union bound as in Theorem 7.1.Source: E Application to Recurrent Neural… · p. 32
  • The proof models the augmented RNN losses with a computational graph whose function family is a strict superset of the original augmented loss class.The graph includes hidden-state and Jacobian nodes, with separate weight matrices allowed at some hidden-state nodes.Source: E Application to Recurrent Neural… · p. 33
  • The graph is release-Lipschitz with constants κrnn-hidden,(i) for hidden-state and auxiliary K nodes and κrnn-jacobian,(i) for Jacobian nodes.Fixing the K nodes reduces the graph to the Section 6 Lipschitz augmentation, so Theorem 6.2 applies; the hidden-state and K-node constants must match.Source: E Application to Recurrent Neural… · p. 33
  • The proof completes the complexity bound with the covering-number argument from Theorem A.2, then derives a 0-1 test-error bound using a union bound over the parameters.The union bound ranges over γ, t(i), σj′←j, aW, aU, and aY.Source: E Application to Recurrent Neural… · p. 33

F ReLU Networks

For ReLU networks, the paper adapts its augmentation technique to obtain a generalization bound involving Jacobian norms, hidden-layer norms, and inverse preactivations. Its proof uses augmented losses that account for preactivations near zero.

F ReLU Networks

  • The ReLU bound is polynomial in Jacobian norms, hidden-layer norms, and inverse preactivations.The augmented loss adds indicators that enforce bounds on the layer norms, Jacobians, and minimum preactivations.Source: F ReLU Networks · pp. 34–35
  • Theorem F.1 gives a generalization guarantee for ReLU networks under a positive-margin assumption, which makes training error zero.The theorem’s preactivation quantity is the minimum over layer coordinates and training datapoints.Source: F ReLU Networks · p. 34
  • Compared with the smooth-activation bound, ReLU retains the same Jacobian sensitivity term, while hidden-layer sensitivity depends on preactivations.The dependence on preactivations parallels the cited Nagarajan and Kolter bound.Source: F ReLU Networks · p. 34
  • The proof builds augmented computation graphs and then reuses the Rademacher-complexity argument and parameter union bound.The augmented losses upper-bound the 0-1 loss.Source: F ReLU Networks · pp. 34–35

G.1 Implementation Details for Jacobian Regularizer

The experiments compare implementation settings for Jacobian regularization and test how the proposed complexity measure behaves with depth. The toolbox includes identities and derivative relations used in the analysis.

G.1 Implementation Details for Jacobian Regularizer

  • Experiments trained for 200 epochs with learning-rate drops at epochs 60, 120, and 150, and tuned the Jacobian-regularization value λ for each setting.For Figure 1, the candidate λ values were 0.1, 0.05, and 0.01; the specific selected values are not given here.Source: §G.1 · p. 36

G.2 Empirical Scaling of our Complexity Measure with Depth

  • The proposed complexity measure is much lower than spectral complexity and appears to scale well with depth for WideResNet models.Figure 5 compares log leading terms for WideResNet models trained on CIFAR10 at depths 10, 16, 22, and 28.Source: Figure 5 · p. 36, §G.2 · pp. 36–37
  • The depth comparison used perfectly fitted, non-augmented CIFAR10 models trained for 50 epochs, with Batchnorm transformations merged into adjacent linear layers at test time.The models had depths 10, 16, 22, and 28, and the final complexity measures were computed on a single model.Source: §G.2 · p. 36
  • The stated bound does not technically apply to ResNet because skip connections complicate Lipschitz augmentation, though a slight modification may remedy this.The authors omit that modification for simplicity.Source: §G.2 · p. 36

H Toolbox

  • The toolbox function u(x1, x2) = (x1 − 1)x2 + 1 outputs values in [0, 1], is at least x1, and composes by multiplying its second arguments.Specifically, u(u(x1, x2), x3) = u(x1, x2x3).Source: H Toolbox · p. 37
  • The toolbox states the chain rule for Jacobians of function compositions and gives a telescoping-sum identity for differences between products.The displayed relations are equations (37) and (38), respectively.Source: H Toolbox · p. 37

Related papers

Loading 1905.03684v3…