Regularisation of Neural Networks by Enforcing Lipschitz Continuity

In plain words

A neural network can memorise its training examples and then do badly on new ones. One way to guard against that is to make the network smooth: a small change in the input should cause only a small change in the output. The standard name for the worst-case amount of stretching is the Lipschitz constant.

The paper gives a simple way to put a ceiling on this number for a network built from common layer types. Each layer gets its own ceiling, like a speed limit on that layer. Training then works as usual, but after every weight update any layer that has gone over its limit is scaled back down to the limit. The authors find that this helps most when training data is scarce, that it combines well with dropout, and that the choice of how to measure size (the norm) changes the result. The extra work per step is small, according to the authors.

TL;DR

• Each layer's operator norm is capped at a hyperparameter λ under ℓ1, ℓ2 or ℓ∞; the network's Lipschitz bound is then the product of the layer caps §3 eq. 3 §4.
• Enforcement is projected SGD: after each optimiser step, every weight tensor is divided by max(1, norm/λ) eq. 25 alg. 2.
• ℓ1 and ℓ∞ are computed exactly for convolutions, but ℓ2 is estimated by a power method that can underestimate the norm, so only ℓ1 and ℓ∞ give a guarantee §4.1 §6.
• Author-reported: the authors say LCC is weaker alone than combined with dropout §1; a dropout combination is the best cell in several tables, and gains are largest with few training examples §5 §5.8 tab. 1 tab. 2.
• λ is sensitive. Too small a value collapses accuracy and can stop training from converging; too large a value drifts back to the baseline §5.7.

Problem

Regularising neural networks is hard. The most effective methods, dropout and batch normalisation, are heuristic and hard to transfer reliably to new problems. Classical ℓ2 penalties on parameters are less effective §1. Theory relates generalisation gaps to weight magnitudes and to products of norms of the weight matrices, and the Lipschitz constant appears as a key quantity in several such bounds §1 §2. The paper assumes that functions which vary more slowly generalise better, and that controlling the network's Lipschitz constant controls generalisation §1 §4.

Earlier work mostly used ℓ2 operator norms, with spectral normalisation or a spectral penalty as the usual tool §2. The paper argues that ℓ1 and ℓ∞ norms are also worth using, and that they are cheaper to compute exactly for convolutions §1 §3.2 §4.1.

Method

Layer bounds §3. For any feed-forward composition, the Lipschitz constant of a composition is at most the product of the constants of its parts eq. 3. For a linear layer under the p-norm, its Lipschitz constant equals the operator norm of its weight matrix §3.1 eq. 8.

• Fully connected layers §3.1. For W of shape out × in, the ℓ1 operator norm is the largest absolute column sum and the ℓ∞ operator norm is the largest absolute row sum. The ℓ2 norm is the spectral norm, the largest singular value. The bias does not enter the bound eq. 4 §3.1.

• Convolutions, ℓ1 and ℓ∞ §3.2. Let F_ij be the filter from input map j to output map i, and let ‖F‖₁ be the sum of absolute filter entries. The exact norms are the ones below eq. 12 eq. 13.

  \|W\|_1 = \max_{j} \sum_{i} \|F_{i,j}\|_1 eq. 12

  \|W\|_\infty = \max_{i} \sum_{j} \|F_{i,j}\|_1 eq. 13

• Convolutions, ℓ2 §3.2. The spectral norm is found by the power method. Each step applies the layer's own convolution, then its transposed convolution, instead of building the matrix eq. 15 eq. 16 eq. 17 alg. 1. Padding and stride are handled because the real operations are used §3.2.

• Activations and pooling §3.3. ReLU, max pooling and softmax have Lipschitz constant at most 1 for all p-norms §3.3.

• Residual blocks §3.4. A block φ(x) = x + f(x) eq. 18 has bound 1 plus the product of the layer bounds inside f eq. 24.

• Batch normalisation §4.2. Viewed as a diagonal scale, the bound is the largest |γ_i / √Var[x_i]| eq. 26 eq. 28. In training the paper projects γ using a moving-average variance, not the minibatch variance §4.2.

Projection §4. After each update a layer's weights W are replaced by π(W, λ), which divides W by max(1, ‖W‖_p / λ). The projection leaves W unchanged when it is already feasible eq. 25 §4. The paper says this is the closest feasible matrix under the operator-norm distance §4.

Training loop §4 alg. 2. The paper uses projected stochastic gradient. Adam converges quickly, and SGD with Nesterov momentum also works §4 §5 intro. Each weight tensor, including convolution filter banks, is projected after the update §4.

# Project one weight tensor into the feasible set  [eq. 25]
# Input:  weights (dense or conv kernel), cap lam, norm p in {1, 2, inf}
# Output: the weights, scaled down if their operator norm exceeds lam

def project(weights, lam, p):
    # Operator norm under p, computed as in [§3.1] and [§3.2]
    norm = operator_norm(weights, p)
    # Scale only when the norm is above the cap  [eq. 25]
    scale = 1.0 / max(1.0, norm / lam)
    return weights * scale

# Projected stochastic gradient training  [alg. 2]
# Input:  weights W[1..l], caps lam[1..l], optimiser update rule
# Output: trained weights satisfying the per-layer caps

def train(weights, lam, batches):
    # Repeat until the weights converge  [alg. 2]
    for batch in batches:
        # Gradient of the loss at the current weights  [alg. 2]
        grads = gradient(loss, weights, batch)
        # Take an ordinary optimiser step  [alg. 2]
        proposed = update(weights, grads)
        # Project each layer back into its feasible set  [eq. 25] [alg. 2]
        for i in range(len(weights)):
            weights[i] = project(proposed[i], lam[i], p)
    return weights

# Estimate the spectral norm of one layer  [alg. 1]
# Input:  weights W (conv or dense), iteration count n
# Output: sigma, which never exceeds the true spectral norm  [§4.1]

def spectral_norm_estimate(weights, n):
    # Random start vector, shaped like the layer input  [alg. 1]
    x = random_normal(input_shape)
    for i in range(n):
        # Forward pass with the layer's own operation  [eq. 16]
        x_mid = apply(weights, x)
        # Transposed operation (conv transpose or matmul transpose)  [eq. 17]
        x = apply_transpose(weights, x_mid)
    # Ratio of norms; converges only as n grows  [alg. 1]
    return norm(apply(weights, x)) / norm(x)

Choice of norm §4.1 §5. ℓ1 and ℓ∞ are computed exactly, in time linear in the number of weights. ℓ2 is estimated with a small fixed number of power iterations, so the estimate is a lower bound and the constraint is approximate §4.1. The three norms are compared throughout the experiments §5.

Hyperparameter λ §4 §5.7. The paper describes a single λ that caps every layer, so that a depth-d network has a bound of λ^d §4. In the experiments, λ was instead set separately for each layer type (convolution, dense and batch norm), which gives up to three values §5 intro §5.7.

Hyperparameters

Values the paper states, or that the code states where the paper does not. Code-only values are marked.

CIFAR-10 and CIFAR-100 §5.1 §5.2.

MNIST and Fashion-MNIST §5.3. Two convolutions with 64 and 128 maps, 5 × 5 kernels, each followed by 2 × 2 max pooling. Then a dense layer of 128 units and a 10-way output. ReLU throughout. Adam, 60 epochs, learning rate 1e-4 divided by 10 at epoch 50. The last 10,000 training images measure performance for tuning. The code runs 30 epochs with the drop at epoch 20; see Paper vs code mnist.py mnist.py.

SVHN §5.4. VGG-style network with four conv–conv–pool blocks of 64, 128, 192 and 256 maps, then two dense layers of 512 and a logistic output. 20 epochs, Adam, learning rate 1e-4 divided by 10 at epochs 15 and 18. WRN-16-4 uses SGD with learning rate 0.1 divided by 5 at epochs 6, 12 and 16. No augmentation. The code's VGG variant has the same block sizes vgg.py and no augmentation svhn.py.

SINS-10 §5.5. Ten predefined folds, each with 9,000 training and 1,000 test images. VGG: 60 epochs, learning rate 1e-4 divided by 10 at epochs 40 and 50. WRN: 100 epochs, learning rate 0.1 divided by 5 at epochs 30, 60 and 80. The final 1,000 training images are the validation set. Paired t-tests decide significance §5.5. The code schedules match sins10.py sins10.py.

Fully connected networks, tabular data §5.6. Two hidden layers of 100 ReLU units. Dropout p ∈ {0.2, 0.3, 0.4, 0.5}. λ grid: {2, 4, …, 18, 20} for ℓ2 and ℓ∞, {5, 10, …, 45, 50} for ℓ1. Grid search per fold, using a hold-out set from the training data. Two repetitions of 5-fold cross-validation. No code for these runs is in the repository.

Per-run λ values for the plain LCC runs. Each row lists the λ values that the repository's scripts use for LCC without batch norm or dropout. The scripts hold every run; this table shows only the plain-LCC rows.

The λ_bn values are in the scripts on the same lines. For VGG rows the scripts do not set λ_bn, because they run without batch norm. SINS-10 VGG plain-LCC rows are commented out in the script, so they are not in this table sins10-vgg.sh.

Dropout rates in the scripts: CIFAR-10 VGG 0.2 (conv) and 0.5 (dense) cifar10-vgg.sh. CIFAR-10 WRN 0.2 (conv) cifar10-wrn.sh. The other settings are in the same script files.

Results

Author-reported. Setup: test accuracy (%) with mean ± standard deviation over five seeds. Models: VGG19 and WRN-16-10 on CIFAR-10 and CIFAR-100, a small convolutional net on MNIST and Fashion-MNIST, VGG-style and WRN-16-4 on SVHN and SINS-10, and two-hidden-layer networks on tabular data. Baseline: no regulariser, dropout, spectral decay and their combinations with LCC §5. Hardware: not stated.

CIFAR-10 tab. 1. Test accuracy (%).

CIFAR-100 tab. 2. Test accuracy (%).

MNIST and Fashion-MNIST tab. 3. Test accuracy (%).

SVHN tab. 4. Test accuracy (%).

SINS-10, VGG tab. 5. Accuracy (%). The "+/−" column marks a significant change when LCC is added to the other regularisers, at 95% confidence (paired t-test).

SINS-10, WRN tab. 6. Accuracy (%). Same significance convention.

Tabular, fully connected tab. 7. Mean test accuracy (%), two repetitions of 5-fold cross-validation. Bold marks the best method per dataset in the paper.

The paper reports that LCC-ℓ∞ has the highest mean accuracy on eight of the ten datasets, and that its average rank is just over 1.5, against just over 3.5 for no regularisation. It says the gap to the unregularised baseline is not statistically significant, but LCC-ℓ∞ is significantly better than most dropout combinations §5.6 fig. 1.

Sample efficiency fig. 3 fig. 4. Test accuracy (%) at two training-set sizes on CIFAR-10. The values are read from the plotted data in the paper's source, not from a table.

Sensitivity to λ fig. 2. Read from the plotted data. Accuracy on CIFAR-100 VGG19 as the three λ values are scaled by a common factor c, with batch norm. For LCC-ℓ2, c = 0.8 gives 46.94% and c = 0.9 gives 69.57%. The unregularised baseline is 65.46% tab. 2. LCC-ℓ1 fails to converge at c = 0.6 fig. 2 caption.

Paper vs code

The official code is linked from the footnote in §5 §5 intro. It is henrygouk/keras-lipschitz-networks, owned by the first author, not a fork. It is pinned to commit 943150c1c039f9c3351273ff2788064c61d6242e. The repository has no LICENSE file, so code_license is set to "none". No code is quoted in this card; pseudocode is written from the paper and the code is cited by path and line only.

The constraint code agrees with the paper:

• Norm formulas match eq. 12 eq. 13. The ℓ1 constraint sums over the output axis for dense kernels and over kernel height, width and output channels for convolutions. The ℓ∞ constraint does the same over the other axes lipschitz.py lipschitz.py.
• Projection matches eq. 25. Each constraint divides by max(1, norm/λ) lipschitz.py lipschitz.py lipschitz.py.
• Batch norm matches eq. 28, with one addition. The constraint acts on γ, using the moving variance and a term of 1e-6 that the paper does not write lipschitz.py lipschitz.py.

These points differ:

1. MNIST and Fashion-MNIST schedule. The paper says 60 epochs, with the learning rate divided by 10 at epoch 50 §5.3. The code runs 30 epochs and divides at epoch 20 mnist.py mnist.py. The Fashion-MNIST script uses the same file fashion-mnist.sh.
2. Batch norm for VGG. The paper says batch norm "is used in all networks" §5 intro. For VGG it is added only with a flag, and the main-table VGG runs leave it out cifar.py cifar.py vgg.py cifar10-vgg.sh cifar10-vgg.sh. WRN always has batch norm wrn.py wrn.py.
3. Augmentation. The paper says random crops and horizontal flips §5.1. The code shifts images by up to 12.5% in each direction, fills the gaps with the nearest pixel, and flips cifar.py. It does not crop.
4. SINS-10 augmentation. The code builds the same augmenter for SINS-10 but calls model.fit on the raw arrays, so the augmenter is not used sins10.py sins10.py. The paper does not describe augmentation for SINS-10.
5. Plain-LCC SINS-10 VGG runs. The script's plain-LCC rows are commented out. The active VGG rows all use batch norm sins10-vgg.sh sins10-vgg.sh. Table 5 includes plain-LCC rows, so the repository does not reproduce them.
6. Weight decay in WRN. When spectral decay is off, WRN kernels get an ℓ2 penalty of 5e-5 wrn.py wrn.py. That applies to the "None" baseline and to every LCC and dropout run. The paper does not mention it.
7. Output layer. The code constrains the final dense layer with λ_dense vgg.py wrn.py mnist.py mnist.py. The paper says "each layer" §4 without saying whether the output layer is included.
8. One λ or three. §4 describes one λ and a bound of λ^d §4. §5.7 and the code use separate λ values for convolution, dense and batch norm §5.7 vgg.py wrn.py. With separate values, the λ^d bound does not hold; the network bound is the product of the caps actually used.
9. Power iterations. The paper says "a small number" §4.1. The code uses 2 and draws a fresh random start at every constraint call, with no warm start lipschitz.py lipschitz.py lipschitz.py lipschitz.py. The estimate is always at most the true norm, as the paper says, so the ℓ2 constraint is loose by an amount that depends on the layer §4.1.
10. Dropout and test-time scaling. §4.3 describes weights being scaled at test time, which would raise the needed λ §4.3. The repository uses Keras Dropout maybe.py. By Keras's documented behaviour (not stated in this repository), it scales activations during training and does nothing at test time. That is inferred, not confirmed by the code.
11. Residual shortcuts. The WRN block is pre-activation (batch norm, ReLU, convolution, twice) plus a shortcut that uses average pooling and zero-padding, which are not constrained wrn.py. The paper's residual bound eq. 24 counts the shortcut as the identity with bound 1.
12. Tabular runs. There is no code for the tabular experiments in the repository. The grid in §5.6 cannot be checked against code.
13. Python version. The scripts use Python 2 print statements cifar.py sins10.py and Keras 2 APIs such as fit_generator. Porting to Python 3 is needed before running them.

Pitfalls

• ℓ2 is only approximate. Power iteration with two steps can be far from the true spectral norm when the two largest singular values are close, because convergence depends on the ratio σ₂/σ₁ §4.1. The constraint then does not bound the Lipschitz constant. The paper's own conclusion recommends ℓ1 or ℓ∞ when a guarantee is needed §6. If you use ℓ2, log the estimate and check it against an exact SVD on a few layers.
• Cost of projection. For ℓ2 each projection needs a forward and a backward convolution per constrained layer, for each power iteration. ℓ1 and ℓ∞ are computed exactly, linearly in the number of weights §4.1. The paper calls the overhead small but does not measure it.
• λ has a narrow useful range. Values slightly too small collapse accuracy, and the model may not converge at all. Values above the optimum drift back toward the baseline slowly. The optimum differs by dataset, architecture and norm, so there is no typical range §5.7 fig. 2. The code's search ranges (exp of 0–2.5 for ℓ2 and exp of 3–4.5 for ℓ1 and ℓ∞) are a starting point, not a recommendation tune.py.
• The bound is loose by design. The network bound is the product of layer caps. With one λ it grows as λ^d, and residual blocks add the 1 + ∏ term eq. 24. The paper says tighter whole-network bounds may exist but does not give one §3.
• Batch-norm projection uses a moving average. Projecting γ with the minibatch variance is noisy, so the code and the paper use the moving-average variance §4.2 lipschitz.py. The 1e-6 term is not in the paper.
• Dropout changes what λ means. The paper expects that dropout needs a larger λ, but it says that tuning without dropout and then rescaling is not a valid shortcut §4.3.
• Differences are small. Several cells differ by less than one standard deviation (for example, CIFAR-10 WRN, LCC-ℓ∞ 95.82 ± 0.19 vs. dropout + LCC-ℓ∞ 95.68 ± 0.11). Only the SINS-10 and tabular significance tests are reported §5.5 §5.6.
• Plain LCC is weak alone. The authors say the method is not competitive in isolation but is highly effective combined with other common regularisers §1. Several best cells in the tables are dropout combinations tab. 1 tab. 2 tab. 4.
• Data-scarcity claim. The sample-efficiency curves cover CIFAR-10 only §5.8. The abstract's small-data claim rests on them, so treat it as shown for CIFAR-10 alone.
• Unstated values. Batch size, hardware, dropout rates, spectral-decay coefficients, the number of power iterations and the λ values are not in the text. The scripts give them, but the paper does not justify them.

Lineage

• Builds on: dropout and maxnorm [Srivastava et al. 2014] §2; generalisation bounds that use products of norms [Bartlett et al. 2017] [Neyshabur et al. 2017] [Golowich et al. 2018] §1 §2; spectral-norm penalty for networks [Yoshida & Miyato 2017] and spectral normalisation for GANs [Miyato et al. 2018] §2. These are cited by name only; no arXiv ids are given in the paper text.
• Compared against: dropout and spectral decay §5.1; ℓ2 penalties are mentioned as weaker than dropout §1.
• Concurrent work: Sedghi et al. 2018 and Tsuzuku et al. 2018, both on convolutional spectral norms §2.
• Superseded: not stated.