PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalization bounds for deep convolutional neural networks

Philip M. Long, Hanie Sedghi

arXiv:1905.12600v6cs.LGcs.AIcs.NEmath.STstat.MLstat.TH

TL;DR

Generalization bounds for convolutional networks should account for their structure while relating error to quantities such as training loss and distance from initialization. This paper derives bounds using covering-number arguments and finds bounds independent of image and feature-map dimensions, with linear rather than exponential dependence on depth.

  • Problem

    Generalization analyses in terms of distance from initialization had largely focused on fully connected networks, although convolutional layers’ weight tying constrains the functions they compute.

    Source: §1 · p. 1

  • Method

    The paper bounds covering numbers by controlling the parameter-to-loss Lipschitz constant, then derives generalization bounds for networks with parameters near initialization.

    Source: §1 · p. 2

  • Results

    The bounds are independent of input pixel count and hidden feature-map dimensions, and use a sum of layerwise initialization distances with linear rather than exponential depth dependence.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The relative-error-style bound is especially strong when training loss is small, a condition described as common in modern practice.

    Source: §1 · p. 2

    The basic setting assumes inputs and hidden layers have the same channel count, inputs have vectorized norm at most 1, and activations are 1-Lipschitz and nonexpansive.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

We prove bounds on the generalization error of convolutional networks. The bounds are in terms of the training loss, the number of parameters, the Lipschitz constant of the loss and the distance from the weights to the initial weights. They are independent of the number of pixels in the input, and the height and width of hidden feature maps. We present experiments using CIFAR-10 with varying hyperparameters of a deep convolutional network, comparing our bounds with practical generalization gaps.

1 INTRODUCTION

Generalization analyses for deep networks can use distance from initialization rather than absolute weight size, avoiding the concern that small initial weights may promote vanishing gradients. This paper develops convolutional-network bounds that account for weight tying, remain independent of image and feature-map dimensions, and scale linearly with depth.

1 INTRODUCTION

  • Distance from initialization is motivated by the possibility that small absolute initial weights promote vanishing gradients, while suitable initializations can allow accurate models to be reached with short parameter-space travel.The introduction also notes theoretical reason to expect this distance to decrease as parameter count increases.Source: §1 · p. 1
  • The bounds account for convolutional weight tying and are independent of input pixel count and hidden feature-map height and width.The bounds use distance from initial weights and parameter count.Source: §1 · pp. 1–2
  • Unlike earlier bounds based on a product of layerwise distances, the most general bounds sum distances from initialization and depend linearly on depth.They apply to networks mixing convolutional and fully connected layers, including purely fully connected networks.Source: §1 · p. 2
  • The analysis bounds covering numbers by controlling the Lipschitz constant of the mapping from parameters to network loss.These covering bounds yield both training–test error bounds and relative-error-style bounds, the latter especially strong when training loss is small.Source: §1 · p. 2
  • The covering-number bounds are polynomial in inverse cover granularity, with exponent equal to the model’s parameter count.The parameter-to-function Lipschitz constant determines the scale factor B.Source: §1 · p. 2

2 BOUNDS FOR A BASIC SETTING

This section sets up a basic convolutional-network setting and gives a high-probability generalization bound for networks whose kernels lie within a specified distance of initialization. Its proof route uses Lipschitz parameterization and controls the change in loss when one layer’s convolution operator changes.

2 BOUNDS FOR A BASIC SETTING

  • Convolution is a linear operator and can be represented as a matrix-vector product, with the operator matrix describing convolution by a kernel.The basic-setting introduction presents a bound for a clean and simple setting.Source: §2 · p. 2

2.1 THE SETTING AND THE BOUNDS

  • The basic setting assumes inputs and hidden layers share c channels, inputs have vectorized norm at most 1, and activations are 1-Lipschitz and nonexpansive.The network uses zero-padding; each non-final layer applies convolution followed by a componentwise activation, and the final-layer weights are fixed with norm 1.Source: §2.1 · p. 3
  • For kernels within distance β of initialization, Theorem 2.1 gives a high-probability generalization bound that holds uniformly over the resulting function class.The class Fβ consists of CNN functions whose kernel tensors are within β of the initial kernel tensor; the section also notes that a margin-loss bound upper-bounds test misclassification probability.Source: §2.1 · p. 3

2.2 TOOLS

  • The tools define (B,d)-Lipschitz parameterization as a map from a d-dimensional unit ball to functions whose outputs vary by at most B times parameter distance.A standard empirical-process lemma is then invoked to translate such parameterization into generalization bounds.Source: §2.2 · pp. 3–4

2.3 PROOF OF THEOREM 2.1

  • The proof bounds how much the loss changes when one layer’s convolution operator changes while all other layers remain fixed.It uses the loss’s λ-Lipschitz property and factors the network into computations before and after the altered convolution.Source: §2.3 · p. 4

2. Since the non-linearities

The section bounds how changes to convolutional and fully connected layers affect the loss, then compares the resulting bound with prior bounds in a concrete setting. Its comparison highlights a dimension-independent, more slowly growing bound under the stated initialization and perturbation conditions.

2. Since the non-linearities

  • For 1-Lipschitz, nonexpansive nonlinearities and the stated initialization constraints, changing all convolutional layers yields a loss-difference bound via layerwise replacement and the triangle inequality.The proof combines single-layer bounds and balances layerwise changes under a total perturbation constraint.Source: §2 · pp. 4–5

2.4 COMPARISONS

  • The bound comparison uses an identity initialization and equal-sized parameter changes; in this case, the new bound is independent of d and grows more slowly with λ, c, and L.The authors state that this specific case illustrates a broader phenomenon when initialization is close to identity and parameter changes are on a similar scale.Source: §2.4 · pp. 5–6
  • For a simple concrete comparison of bounds, when each convolutional layer in K0 computes the identity and K adds ϵ to every entry, disregarding edge effects, ||op(K(i))||2 = 1 + ϵk2c and ||K − K0||σ = ϵk2cL.Source: §2.4 · p. 5
  • The cited Golowich et al. (2017) bound requires an additional activation-function assumption, while the authors suspect modifying its proof would not remove exponential dependence on L.The stated activation restriction is satisfied by ReLU.Source: §2.4 · p. 6

3 A MORE GENERAL BOUND

The paper extends its basic bound to networks with convolutional and fully connected layers under assumptions on inputs, losses, and initialization. It proves a high-probability bound and discusses its proof and comparisons with prior bounds.

3.1 THE SETTING

  • The general setting covers networks with convolutional layers followed by fully connected layers, with 1-Lipschitz, nonexpansive activations and pooling and a λ-Lipschitz bounded loss.The input is a d × d × c tensor and the output is an m-dimensional vector.Source: §3.1 · p. 6
  • With probability at least 1 − δ, Theorem 3.1 bounds population loss by empirical loss plus a term depending on W, β, ν, L, χ, λ, and n.The theorem assumes bounded input norm and the section's network and loss conditions.Source: §3.1 · pp. 6–7

3.2 PROOF OF THEOREM 3.1

  • The proof bounds loss changes for individual convolutional and fully connected layers, then combines those bounds by replacing layers one at a time and applying the triangle inequality.The argument uses ||·||N to witness the relevant Lipschitz parameterization.Source: §3.2 · p. 7

3.3 MORE COMPARISONS

  • The comparison section considers the fully connected case and a concrete construction with D = cd^2, D components per hidden layer, and D classes.The supplied comparison passages identify bounds from Bartlett et al. (2017) and Golowich et al. (2017), but do not provide complete expressions for their terms.Source: §3.3 · p. 8

4 EXPERIMENTS

The experiments examine how parameter count and distance from initialization relate to generalization gaps in a 10-layer all-convolutional CIFAR-10 model. As width increases, the gap remains nearly flat even as parameter count grows.

4 EXPERIMENTS

  • As the network becomes more over-parameterized, the generalization gap remains almost flat with increasing W.The study scaled channel counts while keeping depth and other architectural elements fixed, and averaged each setting over five random initializations.Source: §4 · p. 9
  • The generalization gap increases with W||K − K0||σ in the tested 10-layer all-convolutional CIFAR-10 model.The models were trained with dropout and an exponential learning-rate schedule, sweeping initial learning rates and batch sizes 32, 64, and 128.Source: §4 · p. 9
  • The authors offer decreasing ||K − K0||σ as a bound-consistent explanation for the nearly flat gap as W grows.They report fluctuations in this distance and attribute some of them to training instability; medians are also presented across W.Source: §4 · p. 9

A PROOF OF LEMMA 2.3

This proof section transfers parameter-space covers to function-space covers for Lipschitz-parameterized classes, then applies covering-number generalization bounds.

A PROOF OF LEMMA 2.3

  • An ε-cover ensures every member of a set lies within ε of some cover element, while ρmax measures the supremum difference between functions.These definitions supply the function-space distance and covering notion used in the proof.Source: A PROOF OF LEMMA 2.3 · p. 12
  • Covering-number bounds yield generalization bounds under the stated sampling and probability conditions.The section invokes standard results and a bound combining results of Giné and Guillou (2001).Source: A PROOF OF LEMMA 2.3 · p. 12
  • A cover of the parameter ball induces a function-class cover when the class is Lipschitz parameterized.The proof uses an ε/B-cover of the unit ball to obtain an ε-cover under ρmax, then applies a ball-covering lemma.Source: A PROOF OF LEMMA 2.3 · p. 13

B PROOF OF (1)

The proof applies Theorem 2.1 across distance scales and selects the scale set by the weights’ distance from initialization. This yields a generalization bound in terms of empirical loss and complexity terms.

B PROOF OF (1)

  • A union bound over Theorem 2.1 applications gives probability at least 1 − δ for all j and all f in Fβj.Source: B PROOF OF (1) · p. 13
  • For each K, the proof chooses the least j such that ||K − K0||σ ≤ βj to apply the bounds at that scale.Source: B PROOF OF (1) · p. 14
  • The bound controls expected loss by (1 + η) times empirical loss plus terms involving W, ||K − K0||σ, λn, and δ.The displayed bound is Ez∼P[ℓf(z)] ≤ (1 + η)ES[ℓf(z)] + C(W(2||K − K0||σ + log(λn)) + log(log(||K − K0||σ)/δ)).Source: B PROOF OF (1) · p. 14

C THE OPERATOR NORM OF op(K(i))

The proof reduces the operator-norm calculation for op(K(i)) to finding the norm of J. It uses a padded tensor and a Fourier-based lemma to obtain the stated norm relation.

C THE OPERATOR NORM OF op(K(i))

D PROOF OF LEMMA 3.2

The proof tracks convolutional and fully connected layer perturbations and bounds their effect on loss using the loss Lipschitz condition. It decomposes the network around the layer being perturbed.

D PROOF OF LEMMA 3.2

  • For a convolutional layer j, the proof decomposes fΘ as gdown ◦ fop(K(j)) ◦ gup to analyze the loss change.The loss is λ-Lipschitz in its first argument, and the input norm is bounded by χ.Source: D PROOF OF LEMMA 3.2 · p. 14
  • The proof uses layerwise bounds on convolutional operator-norm changes and fully connected weight changes, denoted by βi and γi.Source: D PROOF OF LEMMA 3.2 · p. 15

E PROOF OF LEMMA 3.3

The proof treats perturbations to a fully connected layer by decomposing the network around that layer and using the Lipschitz property of the loss.

E PROOF OF LEMMA 3.3

  • The fully connected layer perturbation is denoted γi = ||V(i) − V(i)0||2.Source: E PROOF OF LEMMA 3.3 · p. 15
  • For fully connected layer j, the proof writes fΘ = gdown ◦ fV(j) ◦ gup to examine the effect of its weight perturbation.The loss difference is bounded using λ-Lipschitz continuity in the loss’s first argument.Source: E PROOF OF LEMMA 3.3 · p. 15
Loading 1905.12600v6…