Lipschitz constraint

Overview

A network is Lipschitz-continuous if a small change in its input changes its output by a bounded amount. The Lipschitz constant is the smallest such bound. The constraint keeps this bound small by capping the operator norm of each layer, so that every layer stretches its input by at most a chosen factor 1804.04368 §3. The network's bound is then the product of the layer caps 1804.04368 §3 eq. 3. The earlier paper uses the same product rule to bound a trained network, without any cap 1312.6199 §4.3.

The invariant that all constrained variants share: after every optimiser step, each layer's weights have operator norm no larger than its cap. This is enforced by projection, which divides the weights by max(1, norm / cap) and leaves them unchanged when they are already feasible 1804.04368 §4 eq. 25. The paper treats this as projected stochastic gradient descent 1804.04368 alg. 2. The bound-only variant below has no projection step.

Variants

The first variant measures a bound and changes nothing in training. The other variants enforce a cap, and they differ in the norm used to measure a layer's stretch. The regularisation paper compares them throughout its experiments 1804.04368 §5.

Bound a trained network, no constraint

Without any change to training, a per-layer upper bound can be read from the weights of a trained network. A dense or rectified layer is bounded by the largest singular value of its weights. Max-pooling has bound 1, and contrast normalisation has bound ε^(−γ) for γ in [0.5, 1] 1312.6199 §4.3. For a convolution the paper gives a Fourier-domain formula for the operator norm 1312.6199 eq. 1. The network bound is the product of the layer bounds 1312.6199 §4.3. For the ImageNet network the paper reports bounds of 2.75 to 11 for the five convolutional layers and 3.12 to 4 for the three fully connected layers 1312.6199 tab. 5. These are upper bounds: a small bound guarantees that no adversarial examples exist, but a large one does not show that they do 1312.6199 §4.3. Card: Intriguing properties of neural networks.

Per-layer cap under the l1 norm

For a dense layer, the l1 operator norm is the largest absolute column sum. For a convolution it is the largest, over input maps, of the summed absolute filter entries 1804.04368 §3.1 eq. 4 eq. 12. Both are computed exactly in time linear in the number of weights 1804.04368 §4.1. Card: Regularisation of Neural Networks by Enforcing Lipschitz Continuity.

Per-layer cap under the l2 (spectral) norm

The l2 operator norm is the largest singular value. For a convolution the paper does not build the matrix. It runs a few power-method steps, each applying the layer's convolution and then its transpose 1804.04368 §3.2 alg. 1. The number of steps is "a small number" in the text 1804.04368 §4.1. The estimate is a lower bound on the true norm, so this cap is approximate and does not guarantee the Lipschitz bound 1804.04368 §4.1. Card: Regularisation of Neural Networks by Enforcing Lipschitz Continuity.

Per-layer cap under the l-inf norm

The l-inf operator norm is the largest absolute row sum for a dense layer, and the analogous sum over output maps for a convolution 1804.04368 §3.1 eq. 13. Like the l1 cap, it is exact and cheap 1804.04368 §4.1. Card: Regularisation of Neural Networks by Enforcing Lipschitz Continuity.

Cap on batch-norm scale

Batch normalisation can be viewed as a diagonal scale. Its bound is the largest |γ_i / √Var[x_i]| 1804.04368 §4.2 eq. 26 eq. 28. The paper projects γ using a moving-average variance rather than the minibatch variance 1804.04368 §4.2. Card: Regularisation of Neural Networks by Enforcing Lipschitz Continuity.

When to use which

Implementation sketch

The projection and the training loop share one core. The paper's experiments use a separate cap per layer type, so the caps are passed per layer.

# Project one layer's weights under its cap  [eq. 25]
# Input:  W (dense or conv kernel), cap lam, norm p in {1, 2, inf}
# Output: W, scaled down only if its operator norm exceeds lam

def project(W, lam, p):
    # Operator norm: column sum (l1), row sum (l-inf) or spectral (l2)  [§3.1]
    norm = operator_norm(W, p)
    # Divide by max(1, norm / lam); feasible weights are unchanged  [eq. 25]
    return W / max(1.0, norm / lam)

# Projected stochastic training  [alg. 2]
# Input:  layers W[1..L], caps lam[1..L], norm p, optimiser update rule
# Output: weights that meet every layer cap

def train(W, lam, p, batches):
    for batch in batches:
        # Ordinary optimiser step on the loss  [alg. 2]
        grads = gradient(loss, W, batch)
        W = update(W, grads)
        # Project every layer back under its cap after the step  [alg. 2]
        for i in range(L):
            W[i] = project(W[i], lam[i], p)
    return W

# Upper bound on a trained network's Lipschitz constant, no projection  [§4.3]
# Input:  layers, each with its kind and weights
# Output: L, the product of the per-layer upper bounds

def network_bound(layers):
    # Start from the neutral factor  [§4.3]
    bound = 1.0
    for layer in layers:
        # Per-layer bound by kind, as in the variant above  [§4.3] [eq. 1]
        bound = bound * layer_bound(layer)
    return bound

Where the variants differ: operator_norm is exact for p = 1 and p = inf, and a short power iteration for p = 2 1804.04368 §4.1. The λ values are not given in the text and must be searched 1804.04368 §5 intro. The bound-only variant skips project and reads layer_bound from the weights. Its convolution case depends on eq. 1, which has a flagged exponent (see Pitfalls).

Contradictions

• Alone or combined. The paper says the constraint is weaker alone than combined with other regularisers 1804.04368 §1. On CIFAR-10 VGG19, the l2 cap alone scores 92.57 against 91.23 for dropout plus the l2 cap 1804.04368 tab. 1, and the l1 cap alone scores 92.48 against 91.72 for dropout plus the l1 cap 1804.04368 tab. 1. For the l-inf cap the combination is higher on the same network: 92.71 against 91.64 1804.04368 tab. 1.
• One cap or one per layer type. The bound of λ^d for a depth-d network assumes a single λ for every layer 1804.04368 §4. The experiments use separate caps for convolution, dense and batch-norm layers [arxiv:1804.04368 §5 intro] §5.7. With separate caps the network bound is the product of the caps used.

Pitfalls

• l2 is only approximate. The power-method estimate can fall short of the true spectral norm, so the cap may not bound the Lipschitz constant 1804.04368 §4.1. Log the estimate if you use this norm.
• The cap value is sensitive. Caps slightly too small collapse accuracy and can stop training from converging. Caps above the best value drift back towards the baseline 1804.04368 §5.7. On CIFAR-100 VGG19 with batch norm, scaling the three caps to 0.8 of their values gives 46.94%, against 65.46% for the baseline and 69.57% at 0.9; the l1 cap fails to converge at 0.6 1804.04368 fig. 2 tab. 2.
• Dropout changes the meaning of the cap. The paper says tuning without dropout and then rescaling is not a valid shortcut 1804.04368 §4.3.
• Gains are often within one standard deviation. For example, on CIFAR-10 WRN-16-10 the l-inf cap scores 95.82 ± 0.19 and dropout plus that cap 95.68 ± 0.11 1804.04368 tab. 1. Only the SINS-10 and tabular results carry significance tests 1804.04368 §5.5 §5.6.
• Scope of the data-scarcity claim. The sample-efficiency curves cover CIFAR-10 only 1804.04368 §5.8.
• Paper and code differ in places. Examples include batch norm for VGG, the MNIST schedule and the augmentation. Check the card's Paper vs code section before copying a setting 1804.04368 §5 intro. Card: Regularisation of Neural Networks by Enforcing Lipschitz Continuity.
• The output layer is not specified. The paper says "each layer" and does not say whether the final dense layer is capped 1804.04368 §4.
• The Fourier formula looks wrong. The bound-only paper writes the exponent as 2πi(u·ξ)/N² 1312.6199 §4.3. The usual 2-D DFT divides by N, not N². Verify the convolution bound numerically before you rely on it 1312.6199 eq. 1.
• Penalising the bound is untested. The bound paper suggests penalising each per-layer bound, which "might help improve the generalisation error", but it does not run that experiment 1312.6199 §4.3. The results reported for the cap come from projection, not from such a penalty 1804.04368 §4.
• Bounds from the first paper are coarse. The ImageNet bounds are computed for one network, and the paper says instability can appear already in the first convolutional layer 1312.6199 §4.3 tab. 5. Do not read them as a general property of that architecture.

Papers

• Intriguing properties of neural networks: gives per-layer upper Lipschitz bounds for trained networks, computed from the weights, and proposes penalising them without testing that.
• Regularisation of Neural Networks by Enforcing Lipschitz Continuity: caps each layer's operator norm under l1, l2 or l-inf, projects after every update, and reports gains on CIFAR, SVHN, MNIST and tabular data.