Globally-Robust Neural Networks

Klas Leino; Zifan Wang; Matt Fredrikson

Source-linked AI summary

Globally-Robust Neural Networks

Klas Leino, Zifan Wang, Matt Fredrikson

arXiv:2102.08452v2Feb 16, 2021cs.LGcs.CRstat.ML

TL;DR

Adversarial examples motivate models whose robust predictions can be efficiently certified. This paper introduces globally robust networks trained with global Lipschitz bounds, achieving state-of-the-art deterministic verified accuracy with low training, memory, and certification overhead.

Problem
Adversarial examples expose neural networks to deliberate misclassification, motivating efficient certification of robust predictions against perturbations.
Method
The paper defines global robustness and trains models with global Lipschitz bounds and an additional robustness-violation class, encouraging accuracy while discouraging violations.
Results
The approach achieves state-of-the-art deterministic verified-robust accuracy, including 63% VRA at ϵ=1.58 on MNIST, while imposing little training overhead and none during certification.
Takeaways & Limitations
Global Lipschitz bounds can support effective real-time certification, and the approach provides simple, fast, memory-efficient certifiably robust networks by construction.
Takeaways & Limitations
The tightness of the estimated global Lipschitz bounds remains an open issue, and global bounds may be insufficient in practice, requiring costlier post-hoc certification as a fallback.

Abstract

from arXiv · show

The threat of adversarial examples has motivated work on training certifiably robust neural networks to facilitate efficient verification of local robustness at inference time. We formalize a notion of global robustness, which captures the operational properties of on-line local robustness certification while yielding a natural learning objective for robust training. We show that widely-used architectures can be easily adapted to this objective by incorporating efficient global Lipschitz bounds into the network, yielding certifiably-robust models by construction that achieve state-of-the-art verifiable accuracy. Notably, this approach requires significantly less time and memory than recent certifiable training methods, and leads to negligible costs when certifying points on-line; for example, our evaluation shows that it is possible to train a large robust Tiny-Imagenet model in a matter of hours. Our models effectively leverage inexpensive global Lipschitz bounds for real-time certification, despite prior suggestions that tighter local bounds are needed for good performance; we posit this is possible because our models are specifically trained to achieve tighter global bounds. Namely, we prove that the maximum achievable verifiable accuracy for a given dataset is not improved by using a local bound.

1. Introduction

The paper introduces global robustness as an operational alternative for certifying local robustness and trains models that use global Lipschitz bounds for efficient certification. The resulting method is simple, resource-efficient, and achieves state-of-the-art deterministic verified accuracy.

1. Introduction: Global robustness requires different prediction regions to remain separated by at least ϵ, with abstention on the intervening margin.Operationally, this matches composing a model with a routine that returns predictions only when ϵ/2-local robustness can be certified.
1. Introduction: Existing local-robustness verification methods can require orders of magnitude more time than inference and may time out or exhaust memory on moderately large CNNs.These costs motivate certification methods that can operate efficiently at inference time.
1. Introduction: Global Lipschitz bounds can make online certification nearly as efficient as inference, but prior training methods did not produce sufficiently small bounds.The paper addresses this training limitation directly.
1. Introduction: The proposed approach incorporates global Lipschitz bounds into the network and trains an additional robustness-violation class alongside ordinary accuracy.The authors show that global bounds need not be as limiting as previously thought.
1. Introduction: 63% VRA at ϵ=1.58 on MNIST surpasses prior approaches by multiple percentage points, while the method also achieves state-of-the-art VRA on CIFAR-10 and scales to Tiny-Imagenet.The method imposes little training overhead and none during certification.
1. Introduction: The method is simple, fast, memory-efficient, and achieves state-of-the-art deterministic verified accuracy.The paper presents simplicity as an asset rather than a limitation.

2. Constructing Globally-Robust Networks

GloRo Nets construct globally robust classifiers by adding a robustness-violation output based on global Lipschitz bounds. A non-abstaining prediction certifies the original model’s local robustness, while abstention covers points near decision boundaries.

2. Constructing Globally-Robust Networks: GloRo Nets augment a neural network with an additional ⊥ class that signals when a point cannot be certified as globally robust.Global robustness separates differently labeled regions by a margin and permits abstention within that margin.
2. Constructing Globally-Robust Networks: For an input x, the ⊥ logit estimates the strongest competing class after worst-case Lipschitz-bounded logit changes within the ϵ-ball.It accounts for the predicted class decreasing and another class increasing under the perturbation.
2. Constructing Globally-Robust Networks: The instrumented GloRo model concatenates the ⊥ logit with the original network outputs.This construction turns the robustness check into part of the forward pass.
2. Constructing Globally-Robust Networks: If the GloRo model predicts a non-⊥ class, that prediction matches the original model and is ϵ-locally robust.This is the certification guarantee established by Theorem 1.
2. Constructing Globally-Robust Networks: The certification calculation conservatively assumes the predicted class decreases maximally while other classes increase maximally.A tighter variant can instead use Lipschitz constants of the predicted-class margins.
2. Constructing Globally-Robust Networks: The construction predicts ⊥ on the original decision boundary and on every point within ϵ of that boundary, thereby achieving global robustness.The method is designed so that non-⊥ predictions occur only when a sufficient output margin supports certification.

3. Revisiting the Global Lipschitz Constant

The paper argues that global Lipschitz bounds can match local-bound certification in principle while offering lower certification cost, provided models are trained to control global steepness. It formalizes this through a construction showing that locally certifiable points can also be certified globally.

Global versus local bounds: Global bounds are cheaper to deploy because they can be computed in advance, whereas local bounds require per-point computation, memory, and reduce throughput.The global bound therefore adds essentially no non-trivial overhead when verifying new points.
Training implications: Local bounds may be tighter, but global-bound training can discourage unnecessary steepness and make global and local steepness more similar.This regularization is presented as a possible explanation for why global bounds can work effectively in trained models.
Theoretical equivalence: Theorem 3 states that any finite set of points locally certifiable by a model can be certified by another model using a global Lipschitz bound.The constructed model preserves the predictions on the set and satisfies the global verification condition.
Theoretical equivalence: Among jointly locally robust points, differently classified points must be more than 2ϵ apart.This separation underlies the construction used to replace local certification with global certification.
Theoretical equivalence: The constructed function increases linearly with distance to separating Voronoi faces, while its local and global Lipschitz constants are equal everywhere.The Voronoi faces separating differently labeled points define the relevant decision boundary.
Caveats: The authors caution that suitable models may be difficult to obtain through training and that estimated global bounds can be too loose for verification.Their evaluation nevertheless reports effective certification and tighter bounds than standard models.

4. Implementation

GloRo Nets incorporate certification into both training and inference by treating abstention as a model output and bounding the network Lipschitz constant through layer spectral norms. The implementation supports common CNN and ResNet components, while ℓ∞ certification remains a scope limitation.

Training: GloRo Nets can be trained with a standard objective by appending an abstention class to the one-hot labels, since abstention is never the correct training label.Certification is therefore encoded directly in the model’s predictions.
Training: A TRADES-inspired loss can further improve verifiable accuracy by separately balancing correct predictions and robust predictions.The robust term uses an over-approximate loss, with KL divergence performing best empirically in the authors’ experiments.
Bounding the global Lipschitz constant: The product of the spectral norms of the network’s layers provides an upper bound on the entire feed-forward network’s Lipschitz constant.This bound is computed from the sequence of layer transformations composing each class output.
Implementation: For CNNs, ReLU layers use spectral norm 1, while convolutional and dense-layer norms are estimated with the power method; related bounds extend the approach to ResNets.Skip connections and batch-normalization layers can also be bounded for ResNet architectures.
Inference: After training, the global bound can be computed once, so certifying new points requires no additional non-trivial overhead.The power method is run to convergence at test time before reusing the resulting bound.
Scope: The paper focuses on ℓ2 certification because its analogous global-bound approximation is loose in ℓ∞ space.The authors note that ℓ∞-specific certification methods may be more effective for that norm.

5. Evaluation

The evaluation finds that GloRo Nets achieve state-of-the-art deterministic verified robustness across benchmark datasets while substantially reducing training and certification costs. Their global Lipschitz bounds are tighter and more operationally efficient than competing approaches, though bound tightness still leaves room for improvement.

5.1. Verified Accuracy: GloRo Nets consistently outperform previous state-of-the-art deterministic VRA methods across MNIST, CIFAR-10, and Tiny-Imagenet.They improve over prior best results by approximately 15 percentage points on MNIST at ϵ=1.58, 7 percentage points on CIFAR-10, and 2 percentage points on Tiny-Imagenet.
5.1. Verified Accuracy: GloRo Nets support generic activation functions with bounded Lipschitz constants, whereas KW and BCP tailor their analyses specifically to ReLU activations.The reported results use MinMax activations, whose Lipschitz constant is 1.
5.2. Training and Certification Cost: GloRo Nets require only a few seconds per epoch and at most 50% more memory than standard training, with total training time at most half that of BCP.Their memory scalability also permits larger batch sizes, despite requiring more training epochs.
5.2. Training and Certification Cost: GloRo Nets certify the CIFAR-10 test set over 14× faster than BCP with less than a tenth of its memory, and over 6,000× faster than KW.Certification uses a single forward pass, making GloRo Nets the most scalable state-of-the-art technique reported here.
5.2. Training and Certification Cost: GloRo Nets certify the entire CIFAR-10 test set in under half a second, whereas Randomized Smoothing requires over ten hours for the same instances.Randomized Smoothing typically achieves higher VRA but provides a stochastic rather than deterministic guarantee.
5.3. Lipschitz Tightness: GloRo Nets produce global Lipschitz upper bounds several orders of magnitude smaller than those of standard networks, and their bounds are substantially tighter for verification.The lower bound reaches 83% of the upper bound on MNIST, approximately 70% on CIFAR-10, and 47% on Tiny-Imagenet.

6. Related Work

The paper situates GloRo Nets among deterministic and stochastic certification methods, emphasizing global Lipschitz bounds as a scalable alternative to tighter local bounds and costly verification.

Lipschitz-based certification: GloRo Nets incorporate global bounds into training and require no additional inference-time certification work.Their certification applies to networks optimized specifically for the global bound.
Other certifiable-training methods: Prior alternatives include contractive architectures, Lipschitz-margin losses, linear-programming methods, linear-region objectives, and abstract interpretation.These methods differ in whether they modify architectures, training losses, optimization procedures, or verification representations.
Local versus global bounds: Theorem 3 shows that, in principle, global bounds can match local-bound robust classification on any set of points certifiable by local bounds.The authors report that training against global bounds can mitigate looseness while avoiding the scalability costs of tighter local bounds.
Randomized Smoothing: Randomized Smoothing provides stochastic rather than deterministic guarantees, whereas GloRo Nets provide deterministic guarantees and certify batches in one forward pass.Randomized Smoothing may use as many as 100,000 samples, reducing throughput by several orders of magnitude.

7. Conclusion

The conclusion presents GloRo Nets as a simple, fast, memory-efficient approach to deterministic verified robustness, while acknowledging unresolved questions about tightening global bounds.

Conclusion: The method achieves simple, fast, memory-efficient training with state-of-the-art deterministic verified accuracy.The authors characterize simplicity as an asset rather than a limitation, based on empirical comparisons with more complicated methods.
Open questions: The authors leave open whether tighter Lipschitz bounds or additional training techniques can unlock the method’s remaining potential.They suggest costlier post-hoc certification as a possible fallback when a global bound is insufficient in practice.
Theoretical guarantee: Theorem 1 establishes that a non-abstaining certified prediction equals the network prediction and is locally robust within radius ϵ.The proof uses output-wise Lipschitz upper bounds to show that competing logits cannot overtake the predicted class inside the ϵ-ball.
Theoretical guarantee: The proof derives the robustness guarantee by bounding each competing output at a perturbed point and comparing it with the predicted output.The argument concludes that fi(x′) < fj(x′) for every competing class i.

A.2. Tighter Bounds for Theorem 1

The appendix replaces conservative separate-logit bounds with margin Lipschitz constants, tightening certification by directly bounding the predicted class’s margin over each competitor.

Tighter bounds: GloRo Nets conservatively assume the predicted logit decreases while every competing logit increases maximally within the ϵ-ball.The appendix notes that this assumption guarantees local robustness but can be removed using margin bounds.
Margin Lipschitz constants: The margin Lipschitz constant directly bounds changes in fj−fi for each pair of classes i and j.Definition 4 formalizes an upper bound that applies to the pairwise logit margin over all input pairs.
Margin-based certification: The tighter variant defines the predicted class j from the underlying model and uses pairwise margin constants to certify its prediction.The proof follows the same structure as Theorem 1 while replacing separate output bounds with margin bounds.
Margin-based certification: The resulting argument again concludes F(x′)=j for every perturbation within the certified radius.The appendix explicitly identifies this as local robustness at x.

A.3. Proof of Theorem 2

The proof constructs a globally Lipschitz classifier from a Voronoi tessellation, assigning values based on distance to differently labeled boundaries and preserving local certification on the sample.

Theorem 3: Theorem 3 states that if every point in S is locally certifiable using its local Lipschitz constant, another classifier exists that preserves predictions on S and certifies them using a global constant.The constructed classifier satisfies |g(x)| > ϵK_G for every x in S.
Construction: The construction uses Voronoi cells of S and defines the boundary from faces separating points with different classifier labels.For each x, d(x) is the minimum distance to such a boundary face.
Construction: The constructed function preserves the classifier’s sign because its nonnegative distance factor leaves the original label sign unchanged.The proof states g(x)>0 if and only if f(x)>0.
Proof cases: Points on opposite sides of the boundary are handled by bounding the sum of their distances to the boundary by their pairwise distance.The contradiction argument uses the boundary crossing of the line segment between the points.
Proof cases: Points on the same side are handled by bounding the difference of their boundary distances by their pairwise distance.A larger difference would contradict the minimum-distance definition of d(x).
Global bound: The construction yields a global Lipschitz bound at most 1/ϵ and ensures every sample point has magnitude at least 1.The proof uses separation of differently labeled sample points and the triangle inequality.
Categorical extension: Theorem 3 extends from binary to categorical classifiers by assigning one distance-based output coordinate to the cell’s class and zero to the others.The categorical construction preserves the same global-certification principle.
Separation lemma: Local robustness forces differently labeled sample points to be more than 2ϵ apart.The lemma proves this using the midpoint, which would otherwise have to receive both labels.

B. Hyperparameters

The appendix documents architectures, preprocessing, scheduling, optimization, and search choices used to train GloRo Nets, including separate MinMax and ReLU configurations.

Architectures: Architectural notation specifies convolutional and dense layers, with MinMax or ReLU activations after each non-top layer and no explicit Softmax.The architectures use SAME padding unless noted otherwise.
Data preprocessing: Training uses scaled features in [0,1], with augmentation applied to CIFAR and Tiny-Imagenet but not MNIST.The augmentation pipeline includes rotations, shifts, flips, shearing, and zooming.
Scheduling: The appendix evaluates schedules for ϵ and λ, selecting settings by verified accuracy and preferring simpler ϵ schedules when results do not differ significantly.Linear, logarithmic, and single-value ϵ schedules are described, while λ is tuned over [1,10] and refined in increments of 0.1.
Initialization and optimization: Optimization uses Adam, compares Glorot uniform with orthogonal initialization, and searches power-iteration counts from {1,2,5,10}.Power iteration is run to convergence after each epoch with tolerance 1×10^-5.
Training budget: All experiments use minibatches of 256, while epoch counts are selected by comparing verified accuracy across training runs.The search covers 100–1000 epochs in increments of 100, then tests fewer epochs when needed.
Search strategy: Hyperparameters are selected greedily rather than through a global grid search because the evaluation contains many choices and hardware resources are limited.The authors state that better settings may have been missed.

C. Comprehensive VRA Comparisons

The appendix compares GloRo Nets with a broader set of deterministic and stochastic certification methods, while cautioning that literature-reported figures are not fully standardized.

Baselines: Section 5 compares GloRo Nets in depth with KW and BCP, two deterministic certification approaches reported as state of the art.The appendix also provides a wider overview of earlier and subsequent approaches.
Comparison scope: The comprehensive comparison includes deterministic and stochastic guarantees, with the best results reported in the literature included.Table C.1 also includes the methods compared directly in Section 5.
Caveat: Reported values in the broader literature comparison are ball-park figures because architectures, data scaling, and augmentation are not standardized.The authors therefore caution that the comparison is not truly apples-to-apples.
Results: GloRo Nets achieve the highest VRA on MNIST for both ϵ = 0.3 and ϵ = 1.58.They also match concurrent CIFAR-10 results from Cayley and come within one percentage point of the VRA reported by Trockman & Kolter.

D. MinMax vs. ReLU GloRo Nets

MinMax activations improve GloRo-Net VRA over ReLU while imposing only modest additional time and memory costs, with similar Lipschitz bounds.

Verified accuracy: MinMax activations substantially improve GloRo-Net VRA compared with ReLU activations across the evaluated cases.The reported main-paper results use MinMax activations.
Cost: MinMax-based GloRo Nets are slightly slower and more memory-intensive than ReLU-based models.The difference is described as not particularly significant.
Lipschitz bounds: MinMax and ReLU GloRo Nets produce fairly similar global and average local Lipschitz bounds.Their bound magnitudes and tightness relative to empirical lower bounds are similar.
Measurement: The evaluation measures timing and memory for standard and GloRo networks with TensorFlow and for KW and BCP with PyTorch.The authors note that framework differences may affect memory efficiency comparisons.

F. Optimizing for Lipschitz Lower Bounds

The appendix estimates global and local Lipschitz lower bounds through optimization and discusses how dimensionality and training hyperparameters affect bound tightness.

Global lower bounds: Global lower bounds use the margin Lipschitz constant for class pairs and maximize it over 100 randomly initialized test-point pairs.Each optimization uses Adam for 7,500 gradient steps.
Local lower bounds: Local lower bounds optimize a radius-constrained variant of the margin Lipschitz constant around fixed test points.The procedure uses 5,000 Adam steps and averages results over 100 random choices of the reference point.
Evaluation: Figure D.1 compares certifiable-training results, CIFAR-10 certification cost, and global versus average-local Lipschitz bounds.Certification timing and memory are reported for ϵ = 36/255, with GPU memory normalized per instance.
Bound tightness: Global upper-bound tightness is high on MNIST but decreases on CIFAR-10 and Tiny-Imagenet.The discussion notes that lower-bound optimization may also become looser in higher dimensions.
Training trade-offs: Using fewer power iterations on CIFAR-10 and Tiny-Imagenet improves expediency but may prevent learning tighter bounds and higher VRA.The authors identify additional computation and alternative training settings as directions for improvement.