PaperlayerView exact revision on arXiv

Source-linked AI summary

Globally-Robust Neural Networks

Klas Leino, Zifan Wang, Matt Fredrikson

arXiv:2102.08452v2cs.LGcs.CRstat.ML

TL;DR

Because adversarial examples threaten reliable classification, this paper defines global robustness and trains networks using global Lipschitz bounds and a robustness-violation class. The resulting models achieve state-of-the-art deterministic verified accuracy, including 63% VRA at ε=1.58 on MNIST.

  • Problem

    Neural networks are vulnerable to adversarial examples, motivating training methods that produce models whose robust predictions can be efficiently certified against perturbations.

    Source: §1 · p. 1

  • Method

    The method trains globally robust networks by incorporating global Lipschitz bounds and a robustness-violation class into the forward pass.

    Source: §1 · p. 2

  • Results

    GloRo achieves state-of-the-art deterministic verified accuracy; on MNIST, it reaches 63% VRA at ε=1.58, surpassing prior approaches by multiple percentage points.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For any points robustly classified using a local Lipschitz bound, a model exists whose global bound implies the same robust classification.

    Source: §1 · p. 2

    It remains uncertain whether such networks are readily obtainable through training, and loose estimated global bounds may prevent verification even when the true bound would suffice.

    Source: §3 · p. 4

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 globally robust classifiers that use global Lipschitz bounds for efficient certification and reports state-of-the-art deterministic verified-robust accuracy. It also proves that global bounds need not reduce the set of points that can be robustly classified using local bounds.

Introduction

  • Because adversarial examples can deliberately cause misclassification and heuristic defenses can fail under adaptive attacks, the paper focuses on models whose robust predictions can be efficiently certified.The cited prior works are Papernot et al. (2016), Szegedy et al. (2014), Carlini & Wagner (2017), Lee et al. (2020), Tsuzuku et al. (2018), and Wong et al. (2018).Source: §1 · p. 1
  • Global robustness requires a separation of width at least ϵ between differently labeled regions and abstention on some inputs, operationally matching certification of ϵ/2-local robustness.The classifier signals a violation rather than predicting when the input falls in the abstention region.Source: §1 · p. 1
  • Existing verification methods can take orders of magnitude longer than a forward pass, time out, or exhaust memory, while global-bound certification can run nearly as efficiently as inference.Prior training methods had not produced sufficiently small global bounds; training for sufficiently small local bounds remained costly in time and memory.Source: §1 · p. 2
  • For any points robustly classified using a local Lipschitz bound, the authors prove there exists a model whose global bound implies the same robust classification.This result motivates an approach to certifiable training that uses global bounds exclusively.Source: §1 · p. 2
  • The method incorporates a Lipschitz bound into the forward pass to define a robustness-violation class, then uses standard training to discourage violations while encouraging accuracy.The authors describe the approach as simple, fast, and capable of running with limited memory.Source: §1 · p. 2
  • 63% VRA at ϵ=1.58 on MNIST surpasses prior approaches by multiple percentage points; the method also achieves state-of-the-art VRA on CIFAR-10 and scales to Tiny-Imagenet.The paper reports little training overhead and none during certification for deterministic guarantees against ℓ2-bounded perturbations.Source: §1 · p. 2

2. Constructing Globally-Robust Networks

The section defines global robustness and constructs GloRo Nets, whose predictions are robust by construction when they do not output ⊥.

2.1. Global Robustness

  • Global robustness uses an extra class, ⊥, so no two points within distance ϵ receive different non-⊥ labels.The intended robust-training objective is high accuracy and verifiable robustness, ideally assigning ⊥ only to points off the data manifold.Source: §2.1 · p. 2

2.2. Certified Globally-Robust Networks

  • The added ⊥ logit accounts for the predicted class decreasing and competing logits increasing by their Lipschitz bounds within an ϵ-ball.The construction uses y⊥ = maxi≠j{yi + (Ki + Kj)ϵ}.Source: §2.2 · p. 3, Figure 2 · p. 3
  • A GloRo Net prediction other than ⊥ matches the original model’s prediction and certifies that it is ϵ-locally robust at that point.The construction adds a ⊥ output based on upper bounds on the logits’ Lipschitz constants.Source: §2.2 · p. 3
  • GloRo Nets label points on or within ϵ of the original model’s decision boundary as ⊥, yielding global robustness.The section presents the method for constructing GloRo Nets and states that the construction is globally robust.Source: §2 · p. 2, §2.2 · p. 3

3. Revisiting the Global Lipschitz Constant

Although local Lipschitz bounds may be tighter, they are costly to compute repeatedly; the section shows that a global bound can in principle certify the same finite set of locally certifiable points.

Tradeoffs

  • Local bounds require more memory, reduce parallelism and throughput, and must be recomputed for each new point; a global bound can be computed in advance, making verification essentially free.Each instance requires its own local bound, so memory use grows with batch size.Source: §3 · pp. 3–4

Training with global bounds

  • GloRo’s loss penalizes incorrect predictions that a global bound cannot verify, discouraging unnecessary steepness and potentially bringing global and local Lipschitz constants closer.Local bounds may be tighter; prior work found global bounds on typical networks prohibitively large, while local bounds may be smaller on in-distribution points, and local Lipschitzness suffices for robustly classifying well-separated data.Source: §3 · p. 4

Theoretical basis

  • For any finite set of points certifiable with a local Lipschitz constant, there exists a classifier that preserves their predictions and certifies them with a global Lipschitz constant.Theorem 3 is stated for binary classifiers and also holds for categorical classifiers.Source: §3 · p. 4
  • The proof uses the fact that differently labeled locally robust points are more than 2ϵ apart, then constructs outputs from distance to separating Voronoi faces so the local and global Lipschitz constants match.Theorem 3’s categorical extension and proof details are in Appendix A.4; Lemma 1’s proof is in Appendix A.5.Source: §3 · p. 4

Limitations and evaluation

  • Training may not easily find the constructed networks, and loose global-bound estimates may prevent verification; nevertheless, evaluation finds effective global certification and tighter bounds than on standard models.The passage points to Sections 5.1 and 5.3 for those evaluation results.Source: §3 · p. 4

4. Implementation

GloRo Nets are trained with standard classification losses that encode certification in the labels, and their global Lipschitz bounds are computed from layer-wise spectral norms. The implementation also describes a TRADES-inspired loss and practical procedures for bounding those norms.

4.1. Training

  • Appending a zero to each one-hot label makes ⊥ an incorrect target, so standard classification training penalizes predictions unless they are correct and locally robust.Cross-entropy is one example of the standard objective.Source: §4.1 · p. 5
  • GloRo-TRADES combines classification loss with an over-approximate robust loss, balancing correct and robust predictions; KL divergence works best empirically, though cross-entropy in both terms often works as well.The loss is inspired by TRADES, whose local-Lipschitz-continuity effects are discussed by Yang et al. (2020).Source: §4.1 · p. 5

4.2. Bounding the Global Lipschitz Constant

  • The product of a feed-forward network’s layer spectral norms upper-bounds its global Lipschitz constant (Szegedy et al., 2014).For an output decomposed as k transformations, the bound is the product of their spectral norms.Source: §4.2 · p. 5
  • For CNNs, ReLU layers use spectral norm 1 and power iteration estimates convolutional and dense layer norms; bounds for skip connections and batch normalization enable ResNet use (Farnia et al., 2019).Other layer-wise Lipschitz-bound methods are cited for more complicated networks (Fazlyab et al., 2019; Sedghi et al., 2019; Miyato et al., 2018).Source: §4.2 · p. 5
  • Persisting power-method iterates reduces training iterations, but the resulting estimate need not be an upper bound; after training, a converged true bound can be computed once for certification without non-trivial per-point overhead.With few iterations, the additional memory is approximately that required to run the network on one instance.Source: §4.2 · p. 5
  • The paper focuses on ℓ2 bounds because the analogous global-bound approximation is loose in ℓ∞, where prior work uses norm-specific certification strategies.Source: §4.2 · p. 5

5. Evaluation

The evaluation compares GloRo Nets with prior certified methods on verified accuracy, training and certification costs, and the tightness of their Lipschitz bounds. It reports strong verified accuracy alongside low computational costs and tighter bounds than standard models.

5.1. Verified Accuracy

  • GloRo Nets beat prior deterministic VRA: nearly 2 percentage points over KW on MNIST (ϵ=0.3), approximately 15 over BCP on MNIST (ϵ=1.58), approximately 7 over BCP on CIFAR-10, and approximately 2 over BCP on Tiny-Imagenet.At ϵ=1.58 on MNIST, GloRo Nets also slightly exceed the VRA of Randomized Smoothing, which offers only a stochastic guarantee; KW could not scale to Tiny-Imagenet because of memory pressure.Source: §5.1 · p. 6, Figure 4 · p. 7
  • GloRo Nets use MinMax activations for their reported results, but even with ReLU activations they match or outperform KW and BCP; their method also supports generic activations with bounded Lipschitz constants.KW and BCP tailor their analysis to ReLU and would require non-trivial modifications to support MinMax activations.Source: §5.1 · p. 6, §5 · p. 6

5.2. Training and Certification Cost

  • GloRo Nets take only a few seconds per epoch and at most 50% more memory than standard training, while total training takes at most half as long as BCP.Their larger batch sizes require more epochs, but this does not outweigh the lower time per epoch.Source: §5.2 · p. 7, Figure 4 · p. 7
  • On CIFAR-10, GloRo Nets certify over 14× faster than BCP using less than a tenth of its memory, and over 6,000× faster than KW.Certification takes under half a second for the CIFAR-10 test set, compared with over ten hours for Randomized Smoothing.Source: §5.2 · pp. 7–8, Figure 4 · p. 7

5.3. Lipschitz Tightness

  • GloRo Nets’ global Lipschitz upper bound is several orders of magnitude smaller than standard networks’ and their optimized lower bound reaches 83% of it on MNIST, 70% on CIFAR-10, and 47% on Tiny-Imagenet.Using the lower bound instead of the upper bound would raise CIFAR-10 VRA from 58% to 64%.Source: Figure 4 · p. 7, §5.3 · p. 8
  • The local Lipschitz lower bound is essentially zero relative to the global upper bound in standard models, versus 6–35% in GloRo Nets, which outperform BCP despite its local-bound certification.The results suggest that a tighter local-bound estimate could still improve GloRo Nets’ VRA at runtime, though obtaining one is challenging.Source: §5.3 · p. 8

6. Related Work

GloRo Nets build on prior Lipschitz-based certification and training, but optimize networks for global-bound certification and distinguish their approach from local-bound, post-hoc, and randomized methods.

Related Work

  • Prior studies linked large global Lipschitz bounds to adversarial blind spots and found direct weight-norm regularization subpar on MNIST, while this work argues global bounds can still yield useful robust models.Szegedy et al. (2014) proposed Lipschitz regularization as a potential remedy; Huster et al. (2018) noted limitations of layer-wise bounds, and Yang et al. (2020) called for further study of locally-Lipschitz functions.Source: §6 · p. 8
  • Unlike post-hoc Lipschitz certification (Hein & Andriushchenko, 2017), GloRo Nets optimize for certification, requiring no additional inference-time work.Both approaches rely on similar techniques, but GloRo Nets use the global bound exclusively.Source: §6 · p. 8
  • Prior work explored Lipschitz-based robustness training, including contractive Perseval networks (Cisse et al., 2017) and universal Lipschitz approximators using sorting activations (Anil et al., 2019).These architectural advances complement GloRo Nets; other certification approaches include dual networks (Wong & Kolter, 2018), linear-region methods (Croce et al., 2019; Madry et al., 2018), and abstract interpretation.Source: §6 · pp. 8–9
  • Unlike Lipschitz Margin Training (Tsuzuku et al., 2018), GloRo Nets add a predicted-class-dependent logit rather than penalizing every non-ground-truth logit, avoiding penalties for distant boundaries.The paper reports greater verified accuracy than LMT and dual networks, while noting that both LMT and GloRo Nets have comparable cost from using global bounds.Source: §6 · p. 9
  • Local-bound training can yield competitive verified accuracy, but Theorem 3 says local-bound magnitude need not improve robust-classification limits, and global-bound training can mitigate looseness at lower cost.The authors identify the overhead of computing tighter local bounds as an impediment to scalability.Source: §6 · p. 9

Randomized Smoothing

  • Randomized Smoothing (Cohen et al., 2019a; Lecuyer et al., 2018) has higher verified accuracy than deterministic methods, including GloRo Nets, but provides stochastic rather than deterministic guarantees.Its typical false-positive rate is around 0.1%, whereas GloRo Nets certify a batch in one forward pass; smoothing may require up to 100,000 samples, reducing throughput by several orders of magnitude.Source: §6 · p. 9

7. Conclusion … A.1. Proof of Theorem 1

The paper presents an efficient, memory-efficient method for certifiably robust networks with state-of-the-art deterministic verified accuracy, while noting that tighter global Lipschitz bounds or additional training techniques may improve it. Theorem 1 establishes that a non-abstaining certified prediction is correct and remains unchanged throughout the specified perturbation region.

7. Conclusion

  • The method is simple, fast, memory-efficient, and achieves state-of-the-art deterministic verified accuracy through effective use of global Lipschitz bounds.Its potential is not theoretically limited by the global Lipschitz constant itself.Source: §7 · p. 9
  • Whether tighter Lipschitz bounds or additional training techniques can unlock the method’s remaining potential remains an open question.Source: §7 · p. 9
  • Costlier post-hoc certification may serve as a fallback when a global bound is insufficient in practice.Source: §7 · p. 9

A.1. Proof of Theorem 1

  • If the certified classifier does not abstain at x, its prediction equals F(x), the classifier’s prediction at x.Source: §A.1 · p. 12
  • The proof uses upper bounds on each output’s Lipschitz constant to show that every class other than j remains below j throughout the epsilon-ball around x.Here j = F(x), and the margin threshold is the maximum competing output plus (K_i + K_j) epsilon.Source: §A.1 · p. 12
  • Consequently, F(x′) = j for every x′ within distance epsilon of x, so F is locally robust at x.Source: §A.1 · p. 12

A.2. Tighter Bounds for Theorem 1

This section replaces the conservative assumption that the predicted logit falls and every competing logit rises by their maximum amounts with a bound on each pairwise logit margin. The resulting GloRo variant certifies local robustness using margin Lipschitz constants.

A.2. Tighter Bounds for Theorem 1

  • The margin-based approach avoids assuming that the predicted class decreases maximally while all other classes increase maximally, instead bounding the margin fj−fi directly.The original assumption is conservative but guarantees local robustness.Source: §A.2 · p. 12
  • Definition 4 gives an upper bound on the margin Lipschitz constant for each pair of classes, which the variant uses for the underlying model’s predicted label.The variant sets j = F(x), the label assigned by the model being instrumented.Source: §A.2 · p. 12
  • When the certificate does not abstain, the proof establishes that every competing logit remains below the predicted logit throughout the ε-ball, so the classifier is locally robust at x.The proof follows the argument for Theorem 1 and concludes that F(x′)=j for any such x′.Source: §A.2 · p. 12

A.3. Proof of Theorem 2 Theorem 2. ¯F · A.4. Proof of Theorem 3 · A.5. Proof of Lemma 1

The appendix proves that finite samples verifiable using local Lipschitz bounds can also be verified by a constructed classifier with a global Lipschitz bound. It also establishes a separation condition for differently labeled robust points and uses a midpoint argument to prove global robustness.

A.3. Proof of Theorem 2 Theorem 2. ¯F

  • If two points within distance 2ϵ have different predictions, the midpoint argument forces their predictions to agree, so global robustness holds.The proof applies local robustness at each endpoint to the midpoint, contradicting the assumption that the endpoint predictions differ.Source: §A.3 · p. 13

A.4. Proof of Theorem 3

  • For finite S with |f(x)| > ϵKL(x,ϵ), a classifier g preserves f’s predictions on S and globally certifies every point in S.The proof gives g a global Lipschitz constant at most 1/ϵ and establishes |g(p)| ≥ 1 ≥ ϵKG for every p in S.Source: §A.4 · p. 13
  • The construction defines B as Voronoi faces separating differently labeled samples and uses each point’s distance d(x) to B in defining g.The sign of g follows the sign of f.Source: §A.4 · p. 13
  • The construction has global Lipschitz constant at most 1/ϵ: opposite-label points use d(x1)+d(x2) ≤ ||x1−x2||, while same-label points use |d(x1)−d(x2)| ≤ ||x1−x2||.The proof establishes each distance inequality by contradiction using the minimum distance to B.Source: §A.4 · p. 13
  • Every sample point is at least ϵ from B, so |g(p)| ≥ 1 ≥ ϵKG for all p in S.For a boundary face, its differently labeled generating samples are at least 2ϵ apart by Lemma 1, giving the stated distance bound.Source: §A.4 · p. 13, §A.5 · p. 14
  • The construction extends to categorical classifiers by assigning d(x)/ϵ to the coordinate for the sample’s label and zero to the other coordinates.Each pairwise difference between output coordinates has the same Lipschitz constant as the binary construction, allowing certification with a global bound.Source: §A.4 · p. 14

A.5. Proof of Lemma 1

  • If every point in S is ϵ-locally robust, differently classified points x1 and x2 in S must satisfy ||x1−x2|| > 2ϵ.Otherwise their midpoint would have to receive both endpoint labels.Source: §A.5 · p. 14

B. Hyperparameters

This appendix describes the hyperparameters used to train the GloRo Nets reported in Section 5 and explains how settings were selected. Because of resource limits, the authors used a greedy search rather than a global grid search.

Architectures

  • For Tiny-ImageNet, removing one dense and one convolutional layer yielded the same or better verified accuracy at lower training cost.The resulting architecture is denoted 8C2F; the other listed architectures were used to facilitate direct comparisons with prior work.Source: B. Hyperparameters · p. 14

Data preprocessing

  • Features were scaled to [0,1], and augmentation was used on CIFAR and Tiny-ImageNet but not MNIST.The stated ImageDataGenerator transforms include rotation, shifts, horizontal flips, shear, and zoom; a separate tfds pipeline was also used.Source: B. Hyperparameters · p. 14

ϵ scheduling

  • The authors compared single, linear, and logarithmic ϵ schedules, selecting the highest verified accuracy and breaking ties by preferring simpler schedules.Linear and logarithmic schedules began in the first epoch and ended at half the total epochs; scheduling ϵ was often unnecessary when scheduling λ instead.Source: B. Hyperparameters · pp. 14–15

Initialization & optimization

  • Initialization was selected by verified accuracy, with Glorot uniform winning ties; all experiments used Adam with the specified initial learning rate and default remaining settings.Learning-rate decay began halfway through training; its target was selected from {1×10−7, 5×10−7, 1×10−6, 5×10−6} by VRA, and Tiny-ImageNet used an initial rate of 2.5×10−4 after higher rates failed to decrease loss.Source: B. Hyperparameters · p. 15

Batch size & epochs

  • All experiments used minibatches of 256; training duration was tuned by verified accuracy, and warm-up helped in some cases, particularly CIFAR-10.Epoch counts were searched in increments of 100 from 100 to 1000, then in increments of 50 when more epochs stopped improving verified accuracy; CIFAR-10 used the same warm-up duration as prior work.Source: B. Hyperparameters · pp. 15, 17

λ scheduling

  • For TRADES, λ scheduling often yielded superior results; the authors searched λ values from 1 to 10 by ones, then refined the best whole number in 0.1 increments.They denote linear schedules as ‘x,y,e’ and a constant λ as ‘x’.Source: B. Hyperparameters · p. 17

Power iteration

  • Power iteration used 1, 2, 5, or 10 iterations per training update, with ties favoring fewer; verified accuracy used converged global bounds.After each epoch, power iteration ran to convergence at tolerance 1×10−5, and its converged random variables were saved for test-time use.Source: B. Hyperparameters · p. 17

Search strategy

  • Rather than globally searching all hyperparameter combinations, the authors used a greedy search ordered by expected impact on verified accuracy and training cost.They explored ϵ scheduling, λ scheduling, epochs, learning-rate decay, warm-up, initialization, power iterations, and minibatch size, in that order.Source: B. Hyperparameters · p. 17

C. Comprehensive VRA Comparisons

GloRo Nets achieve the highest VRA on MNIST at both tested radii and closely match concurrent Cayley on CIFAR-10. The appendix also surveys a wider range of certification approaches, while cautioning that cross-paper results are not apples-to-apples.

C. Comprehensive VRA Comparisons

D. MinMax vs. ReLU GloRo Nets · E. Measuring Memory Usage

MinMax activations improve GloRo Nets’ verifiable accuracy over ReLU activations, with only a modest increase in time and memory costs. The memory section describes how usage and certification-time comparisons were measured and why Randomized Smoothing training times were omitted.

D. MinMax vs. ReLU GloRo Nets

E. Measuring Memory Usage

  • Memory was measured at each epoch’s end using TensorFlow’s MaxBytesInUse() for standard and GloRo networks and PyTorch’s peak active use for KW and BCP.The experiments used TensorFlow for standard and GloRo networks, and PyTorch for KW and BCP.Source: E. Measuring Memory Usage · p. 18
  • To make cross-framework certification-time and memory results more comparable, PyTorch gradient tracking was left enabled despite being unnecessary for certification.The authors note that PyTorch allows more memory-management control than TensorFlow, which does not allow this optimization.Source: E. Measuring Memory Usage · p. 18
  • Randomized Smoothing training times were omitted because it post-processes a pretrained model, and the authors assume adding Gaussian noise to data augmentation has negligible training-cost impact.The added noise matches the radius used for smoothing.Source: E. Measuring Memory Usage · p. 18

F. Optimizing for Lipschitz Lower Bounds

The section estimates global and local Lipschitz lower bounds by optimization and discusses why the observed gap between upper and lower bounds may not reflect the bounds alone. It identifies input dimensionality and training hyperparameters as factors affecting the gap.

Global Lower Bounds

  • The global lower bound uses a margin Lipschitz constant for each class pair and reports the maximum over 100 random test-set initial pairs after 7,500 Adam steps.Both points in each pair are initialized from the test set.Source: F. Optimizing for Lipschitz Lower Bounds · p. 18

Local Lower Bounds

  • The local lower bound optimizes within the ϵ-ball around a fixed random test point, using 5,000 Adam steps and reporting the mean across 100 choices of that point.At each step, the two optimized points are projected onto the ϵ-ball and initialized from the test set.Source: F. Optimizing for Lipschitz Lower Bounds · pp. 18–19

Discussion

  • The global upper bound is fairly tight for MNIST GloRo Nets but less so for CIFAR-10 and Tiny-Imagenet; higher input dimensionality may make both learning tight bounds and optimizing lower bounds harder.Thus, some apparent looseness may come from the lower-bound optimization rather than the upper bound.Source: F. Optimizing for Lipschitz Lower Bounds · p. 19
  • Fewer power iterations on CIFAR-10 and Tiny-Imagenet were chosen partly to save training time, and more computation during training may yield tighter bounds and higher VRA.The authors suggest exploring alternative training strategies and hyperparameters.Source: F. Optimizing for Lipschitz Lower Bounds · p. 19

Related papers

Loading 2102.08452v2…