Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks

Yusuke Tsuzuku; Issei Sato; Masashi Sugiyama

Source-linked AI summary

Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks

Yusuke Tsuzuku, Issei Sato, Masashi Sugiyama

arXiv:1802.04034v3Feb 12, 2018cs.CVcs.LGstat.ML

TL;DR

Deep networks remain vulnerable to small adversarial perturbations, while prior certification methods are costly or restricted to special architectures. This paper derives scalable Lipschitz-margin certificates and trains networks to enlarge guarded areas. The method provides non-trivial certification and improved robustness, including for large networks, while its invariant-property trade-off becomes unfavorable for excessively large training radii.

Problem
Prior certification methods require strong network-structure assumptions and massive computational costs, limiting their applicability to complicated networks.
Method
The paper combines Lipschitz constants with prediction margins for efficient certification and introduces Lipschitz-margin training to constrain networks toward smoothness.
Results
The method provides non-trivial certification and improved robustness for networks ranging from small to large, with negligible computational costs.
Takeaways & Limitations
LMT offers a broadly applicable route toward certifiable and robust deep learning models.
Takeaways & Limitations
Excessively large c can make constant functions optimal, so stronger invariant properties do not guarantee high accuracy on noisy examples.

Abstract

from arXiv · show

High sensitivity of neural networks against malicious perturbations on inputs causes security concerns. To take a steady step towards robust classifiers, we aim to create neural network models provably defended from perturbations. Prior certification work requires strong assumptions on network structures and massive computational costs, and thus the range of their applications was limited. From the relationship between the Lipschitz constants and prediction margins, we present a computationally efficient calculation technique to lower-bound the size of adversarial perturbations that can deceive networks, and that is widely applicable to various complicated networks. Moreover, we propose an efficient training procedure that robustifies networks and significantly improves the provably guarded areas around data points. In experimental evaluations, our method showed its ability to provide a non-trivial guarantee and enhance robustness for even large networks.

1 Introduction

The paper targets certifiable robustness against adversarial perturbations, addressing limitations in existing defenses and certification methods. It links Lipschitz constants with prediction margins and proposes scalable calculation and training procedures.

Small, intentionally created input perturbations can deceive deep networks and raise security concerns, especially in object recognition systems.
Existing defenses, including defensive distillation, transformations, detections, heuristics, and adversarial training, remain vulnerable or risk overfitting to attacks.
Prior certification methods often apply only to specially structured small networks, while wide evaluation networks make them computationally intractable or inapplicable.
The proposed method aims to provide scalable lower bounds on deceptive perturbation sizes and enlarge guarded areas across diverse network structures.
The paper bounds loss-landscape slope using Lipschitz constants because input gradients can provide a false sense of security.

2 Related work

Prior certification work often restricts networks to special structures or encodes verification as formal optimization problems, incurring prohibitive costs and limiting application to small networks.

Existing approaches commonly restrict certification to networks using ReLU exclusively as activation functions.
Bastani et al. encoded networks as linear programs, Katz et al. used satisfiability modulo theories, and Raghunathan et al. used semidefinite programs.
These formulations demand prohibitive computational costs and are limited to small networks.

3 Problem formulation

The paper formulates adversarial perturbations under an ℓ2 threat model and defines certification through a radius whose perturbations preserve the classifier’s prediction.

The threat model treats X as a data point with true label tX and measures similarity using the ℓ2-norm.
An adversarial perturbation is a perturbation that produces a similar input capable of deceiving the classifier.
The classifier F outputs a vector of class scores and predicts the index with the largest score.
A guarded area is a radius-c hypersphere around X in which the stated prediction-preservation condition holds.
The defense goal is to ensure larger guarded areas for data points drawn from the data distribution.

4 Calculation and enlargement of guarded area

The method certifies guarded areas from prediction margins and Lipschitz bounds, then trains networks to enlarge those areas. LMT remains broadly applicable with negligible computational overhead but trades expressiveness for smoothness as c increases.

4.1 Lipschitz constant and guarded area: Perturbations smaller than the certified margin-to-Lipschitz bound cannot deceive the network at a data point.
4.1 Lipschitz constant and guarded area: The certification can use either of two propositions connecting prediction margins and Lipschitz constants, including a subnetwork-based variant.
4.2 Guarded area enlargement: LMT converts guarded-area conditions into losses and uses a computationally efficient, differentiable estimate of the Lipschitz upper bound during training.
4.2 Guarded area enlargement: Increasing c strengthens the intended invariant property, but extremely large c can make constant functions optimal and reduce accuracy on noisy examples.
4.2 Guarded area enlargement: The Lipschitz-bound calculation costs almost the same as increasing batch size by one, making its overhead negligible for typical mini-batches.

5 Calculation of the Lipschitz constant

The paper develops unified, differentiable upper bounds for network Lipschitz constants by recursively combining component bounds, including linear, convolutional, normalization, pooling, and activation layers. Fast spectral-norm estimation and inference-time reuse make the calculation scalable to complex networks, while tighter component bounds improve whole-network certification.

Recursive network bounds: The method recursively combines Lipschitz bounds for composition, addition, and concatenation to estimate an upper bound for the whole network.The resulting calculation is unified across common network components and differentiable with respect to network parameters.
Linear layers: Fully-connected, convolutional, and normalization layers are treated as linear operations at inference time, enabling joint analysis of common layer pairs.Bias parameters can be ignored because they do not change layer Lipschitz constants.
Spectral-norm calculation: A Gaussian power-iteration update estimates the spectral norm of linear operators, requiring only one iteration during training and no additional convolution or transposed-convolution operation.For convolutional layers, the training-time procedure instead requires increasing the batch size by one.
Spectral-norm calculation: The spectral-norm estimate can support an upper-bound guarantee with probability higher than 1 − 2/π, while larger batches make the probability exponentially closer to one.Singular value decomposition is also available for more accurate calculation.
Putting the bounds together: The resulting convolutional bounds are numerically tighter than previous results, normalization-layer bounds are novel, and component improvements produce substantially different whole-network upper bounds.The paper also reports that using the inference-time bound during training regularizes Lipschitz constants and accommodates batch-normalization layers.
Pooling and activation: Pooling and activation bounds use a theorem giving ∥f∥2 ≤√nL, where n counts the maximum overlap of component inputs.The bound applies when each component function has Lipschitz constant at most L.

6 Numerical evaluations

Numerical evaluations found tighter Lipschitz bounds, larger provably guarded areas, and effective robustness certification for modern large networks. LMT improved certification and attack robustness, though its ℓ∞ guarantee remained below a prior specialized method in one comparison.

6.1 Tightness of bounds: LMT improved convolutional-layer bounds, producing significant differences in upper bounds for the Lipschitz constants of whole networks.Pooling-layer bounds did not depend on training methods, whereas convolutional-layer bounds improved under LMT.
6.1 Tightness of bounds: The estimated error ratios for LMT were 1.42, 1.02, and 1.15 across inequalities (i)–(iii), with an overall median error of 1.72.The corresponding ratios were 39.9, 1.13, and 1.82 for an unregularized model, while adversarial training exceeded 2.4 in discrepancy.
6.1 Tightness of bounds: The median provably guarded area increased from 0.012 in a naive model to 1.02 with LMT, corresponding to 0.036 in the ℓ∞ norm.The naive-model guarantee meant changing several pixels by one on the 0–255 scale could not change the prediction.
6.2 Scalability test: LMT certified guarded areas larger than 0.029 for more than half of SVHN test data on a 16-layer wide residual network with width factor 4.Other training methods did not provide such strong certification in this large-network setting.
6.2 Scalability test: With an architectural modification and c = 0.1, the median guarded area exceeded 0.08 while accuracy dropped to 86%.This certification corresponds to changing 400 input elements by ±1 on the 0–255 image scale without causing error over 50%.
6.2 Scalability test: LMT slightly reduced accuracy but largely improved robustness against the 100-iteration C&W attack compared with other regularization-based techniques.The authors note that LMT is independent of adversarial training and input transformations, allowing potential combination with them.

7 Conclusion

The paper presents scalable Lipschitz-based certification and Lipschitz-margin training for improving provable perturbation invariance across network sizes. It reports tighter bounds, larger certified areas, and improved attack robustness, while leaving applications beyond this setting for future work.

7 Conclusion: The work provides tighter spectral bounds, fast differentiable operator-norm estimation, and a training algorithm that constrains networks to be smooth.These components target perturbation-invariance certification across a broad range of networks.
7 Conclusion: LMT improves certification and robustness against attacks while providing non-trivial certification for small to large networks with negligible computational costs.The conclusion summarizes the method’s reported scalability and robustness outcomes.
7 Conclusion: Applying the developed techniques to GAN training and training with noisy labels remains future work.The stated future directions extend beyond the paper’s demonstrated applications.

A Proof of Proposition 1

The proof connects Lipschitz bounds with classifier outputs and establishes how power iteration estimates spectral norms for linear components. These bounds support the paper’s certification framework.

Proposition 1 considers a classifier with Lipschitz constant L and output vector F(X).
The proof reduces the required inequality to a vector inequality involving maxima over non-target coordinates.
For functions with Lipschitz constants L1 and L2, the proof uses compositional bounds involving their product.
A matrix representation shows that recursive updates are equivalent to power iteration on MᵀM.
The iteration converges almost surely toward the dominant singular direction, allowing σ := ∥f(u)∥2 to approximate the spectral norm.

C.3 Proof of Theorem 2

The proof of Theorem 2 analyzes power iteration and extends the calculation to normalization and convolutional components. It also identifies a training-dynamics failure mode and a mitigation.

Power iteration is analyzed through the largest singular value of MᵀM and a quantity ω governing the approximation error.
With batch size 128, taking the maximum upper bound gives failure probability below (2/π)128/2 ≤ 10−12.
Batch normalization is treated using inference-time constants γi, βi, µi, and σi, while input-independent terms are omitted from the Lipschitz calculation.
The resulting linear treatment jointly calculates the Lipschitz constant of batch normalization and preceding linear layers, though a numerical issue can arise for a single normalization layer.
Power-iteration estimation can fail when normalization-layer dynamics drive u toward a one-hot vector, so small perturbations are added after normalization.
The convolutional bound follows because convolution satisfies Theorem 3’s assumptions and includes matrix multiplication by the reshaped kernel matrix W′.

D.3 Tighter bound of n-repetition in Theorem 3

This section derives tighter repetition bounds for pooling and convolutional layers by incorporating receptive-field size, input dimensions, and stride.

The method provides tight repetition counts for pooling and convolutional layers.
For convolution, repetition is initially bounded by the receptive-field size hk · wk.
The bound is refined using the padded input size and kernel dimensions, including the case where equal 8 × 8 input and kernel sizes require one repetition.
Stride provides an additional way to tighten the repetition bound.
Max-pooling has Lipschitz constant bounded by one, while average-pooling is bounded through a vector inequality.
For elementwise activation and nonlinear functions, Theorem 3 requires only their individual Lipschitz constants.

F Experimental setups

The experiments evaluate the proposed method across small and wide networks using specified training protocols and Lipschitz-based baselines. The section also discusses practical applicability and extensions.

Experimental settings: The first experiment uses a network with two convolutional and two fully connected layers, trained with Adam for 20 epochs and batch size 50.
Experimental settings: The evaluation estimates local Lipschitz constants by applying Gaussian input perturbations, recomputing input gradients 100 times, and taking the maximum.
Experimental settings: A 16-layer wide residual network with width factor k = 4 is evaluated on SVHN using 10,000 validation images.
Experimental settings: For the wide-network experiment, models use Nesterov momentum for 160 epochs with batch size 128 and scheduled learning-rate reductions.
Discussion: The guarded-area calculation imposes almost no inference-time computational overhead and can estimate perturbation bounds even without true labels.
Discussion: LMT can handle normalization layers that Parseval networks cannot control within their stated framework, and it supports class-pair-specific hyperparameters and combined adversarial training.