Lipschitz-Certifiable Training with a Tight Outer Bound

Sungyoon Lee, Jaewook Lee, Saerom Park

Deep neural networks are notoriously fragile; tiny, invisible "adversarial perturbations" to an image can easily trick a model into misclassifying it. While many empirical defenses exist, they often fail against novel, unforeseen attacks.

Verifiable (or certifiable) training aims to solve this by providing a mathematical guarantee: within a certain "perturbation ball" around an input, the model's prediction cannot change. However, researchers face a significant "scalability wall." Existing methods are generally either too slow (dual relaxation methods provide tight bounds but involve expensive optimization) or too loose (layer-wise propagation methods produce bounds so pessimistic that the model struggles to learn effectively).

This paper introduces Box Constraints Propagation (BCP), a new certifiable training algorithm that is over 12 times faster than previous state-of-the-art methods. By cleverly combining Lipschitz analysis with interval arithmetic to create tighter "outer bounds" for neural network outputs, BCP achieves high certified robustness and is the first deterministic method to scale effectively to the Tiny ImageNet dataset.

The Box Constraints Propagation (BCP) Method

The core innovation of this research is BCP. Instead of just tracking one type of boundary through the network layers, BCP tracks two distinct bounds:

  1. Ball Outer Bounds ($\ell_2$): Based on Lipschitz constants, which measure how much the function can "stretch" the input.
  2. Box Outer Bounds ($\ell_\infty$): Based on interval arithmetic, which tracks the minimum and maximum range of every neuron.
Illustration of Box Constraints Propagation

By taking the intersection of these two bounds at each layer, BCP creates a much tighter "envelope" around the possible outputs of the network. A box and a ball might both be loose approximations of a complex shape in high-dimensional space, but their intersection is significantly smaller and tighter. This simple geometric insight allows BCP to cut off large areas of "impossible" outputs that previous methods had to account for.

To train with this tighter envelope, the authors define a "Worst-Translated Logit." During training, the model doesn't just try to classify the clean image; it attempts to classify the "worst-case" version of that image within the tight BCP bound. They provide an efficient iterative algorithm to solve this inner optimization problem quickly, ensuring the overall training process remains fast.

Key Results and Insights

The researchers evaluated BCP on three standard benchmarks: MNIST, CIFAR-10, and Tiny ImageNet. Scaling deterministic certification to Tiny ImageNet (a dataset with 200 classes and higher resolution images) represents a significant milestone for the field.

Logit space bounds across datasets
  • Massive Speedup: BCP is over 12 times faster per epoch than the previous state-of-the-art dual relaxation method (CAP). This speed allows researchers to use larger architectures (like Wide ResNets) and more complex datasets that were previously off-limits for certifiable training.
  • Tighter Bounds: By effectively using local properties of the input rather than relying on a single pessimistic "global" Lipschitz constant, BCP's bounds are 25.3% to 55.4% tighter on average than standard global Lipschitz bounds.
  • State-of-the-Art Performance: On CIFAR-10, BCP achieved comparable verification accuracy to CAP but with significantly higher natural accuracy (65.72% vs 60.10% for a 6C2F architecture).
  • Scaling to Tiny ImageNet: BCP achieved a 20.1% verification accuracy on Tiny ImageNet (with $\ell_2$-perturbation of $\epsilon = 36/255$). This is the first time a deterministic method has shown non-trivial certified robustness on a dataset of this scale.

Limitations and Future Work

While BCP is a major step forward in scalable verification, the authors acknowledge the persistent accuracy-robustness trade-off. Models trained for certified robustness still exhibit lower "natural" accuracy on clean images compared to standard, non-robust models (e.g., ~28.8% natural accuracy on Tiny ImageNet vs. much higher for standard training).

Future work will likely focus on finding ways to further tighten these bounds without increasing computational cost, or developing new neural architectures specifically designed to be "friendly" to box and ball propagation. Adapting the verification loss to be more sensitive to specific input locations also remains a promising avenue for improvement.

Summary updated

Abstract

Verifiable training is a promising research direction for training a robust network. However, most verifiable training methods are slow or lack scalability. In this study, we propose a fast and scalable certifiable training algorithm based on Lipschitz analysis and interval arithmetic. Our certifiable training algorithm provides a tight propagated outer bound by introducing the box constraint propagation (BCP), and it efficiently computes the worst logit over the outer bound. In the experiments, we show that BCP achieves a tighter outer bound than the global Lipschitz-based outer bound. Moreover, our certifiable training algorithm is over 12 times faster than the state-of-the-art dual relaxation-based method; however, it achieves comparable or better verification performance, improving natural accuracy. Our fast certifiable training algorithm with the tight outer bound can scale to Tiny ImageNet with verification accuracy of 20.1\% ($\ell_2$-perturbation of $\epsilon=36/255$). Our code is available at \url{https://github.com/sungyoon-lee/bcp}.
BibTeX
@inproceedings{lee2020lipschitz,
  author = {Sungyoon Lee and Jaewook Lee and Saerom Park},
  title = {{Lipschitz-Certifiable Training with a Tight Outer Bound}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=G8jarY0zeq},
}
Figure