Towards Certifying π“βˆž Robustness using Neural Networks with π“βˆž-dist Neurons

Bohang Zhang, Tianle Cai, Zhou Lu, Di He, Liwei WangarXiv 2021 · arXiv · OpenReview

TL;DR

This paper introduces a novel neural network architecture, the "$\ell_\infty$-dist net," designed to be inherently robust against adversarial perturbations. By using a new type of neuron based on $\ell_\infty$-distance, these networks achieve provable robustness guarantees and state-of-the-art certified accuracy on several challenging datasets, while also being efficient to train and certify.

What Problem Does This Paper Address?

Modern neural networks, despite their impressive accuracy, are notoriously vulnerable to adversarial attacks. Even tiny, imperceptible changes to input data can cause these networks to misclassify inputs with high confidence. While many defenses exist, they often provide only empirical robustness against specific attacks or offer certified guarantees that are computationally expensive or limited in scope. This paper tackles the challenge of developing neural networks that are theoretically principled and inherently resistant to $\ell_\infty$-norm bounded adversarial perturbations, providing strong, verifiable robustness.

Methods

The core innovation is the $\ell_\infty$-dist neuron. Unlike traditional neurons that use linear transformations followed by non-linear activations, this new neuron directly computes the $\ell_\infty$-distance between the input and its weights. This design choice is crucial because it makes the neuron, and consequently any network built from them ($\ell_\infty$-dist nets), a 1-Lipschitz function with respect to the $\ell_\infty$-norm. This Lipschitz property directly translates into a provable certified robustness guarantee based on the margin of prediction outputs.

The authors also introduce a holistic training strategy to overcome optimization challenges specific to $\ell_\infty$-dist nets. This includes:

  • Mean shift normalization: A simplified normalization technique that preserves the Lipschitz property.
  • Smoothed approximated gradients: Relaxing the $\ell_\infty$-distance to $\ell_p$-distance during training to obtain denser gradients.
  • Identity-map initialization: A ResNet-like approach to enable deeper networks without performance degradation.
  • $\ell_p$-norm weight decay: A more suitable regularization for $\ell_\infty$-dist nets compared to standard $\ell_2$-norm weight decay.

Additionally, they demonstrate how to use $\ell_\infty$-dist nets as robust feature extractors by attaching a shallow conventional network on top, further enhancing performance and adaptability.

Datasets

The paper evaluates its proposed methods on the following standard datasets:

  • MNIST
  • FashionMNIST
  • CIFAR-10
  • TinyImageNet

Key Insights and Ideas

  • $\ell_\infty$-distance as a natural robustness primitive: The paper shows that directly incorporating $\ell_\infty$-distance into neuron design is a powerful way to build inherently robust networks, bypassing the need for complex post-hoc certification methods.
  • Lipschitz property is key to certified robustness: The 1-Lipschitz nature of $\ell_\infty$-dist nets provides a direct and efficient mechanism for certifying robustness by analyzing the margin of predictions.
  • Specialized training is crucial: Conventional deep learning training techniques (like standard batch normalization or $\ell_2$-weight decay) can hinder the robustness of $\ell_\infty$-dist nets, necessitating a tailored training approach.
  • Expressive power of $\ell_\infty$-dist nets: The paper theoretically proves that these networks can approximate any 1-Lipschitz function, demonstrating their flexibility.
  • Efficiency gains: $\ell_\infty$-dist nets offer fast training and certification compared to many existing methods, making them practical for real-world applications.

Key Results

The proposed $\ell_\infty$-dist nets and their composite versions ($\ell_\infty$-dist Net+MLP) achieve state-of-the-art certified accuracies on several benchmarks:

  • MNIST ($\epsilon=0.3$): 93.09% certified accuracy.
  • FashionMNIST ($\epsilon=0.1$): 79.23% certified accuracy.
  • CIFAR-10 ($\epsilon=8/255$): 35.42% certified accuracy.
  • TinyImageNet ($\epsilon=1/255$): 16.31% certified accuracy.

These results significantly outperform previous best-known methods, often with smaller models or comparable computational costs. For instance, on TinyImageNet, their model with 156M FLOPs achieved 16.31% certified accuracy, surpassing a previous result that used a model 33 times larger. The training and certification processes are also noted to be very fast.

Limitations and Future Work

  • Optimization challenges: While the proposed training strategy significantly alleviates optimization difficulties, the authors note that training $\ell_\infty$-dist nets from scratch can still be challenging.
  • Further investigation of optimization: The authors suggest that future work should focus on further handling the optimization difficulties specific to this network architecture.
  • Extending to more challenging tasks: The paper mentions extending the model to more challenging tasks like ImageNet as a future direction.
  • Comparison with other robustness metrics: While the paper focuses on $\ell_\infty$-norm perturbations, future work could explore robustness under other norms or combined perturbation types.

Summary updated

Abstract

It is well-known that standard neural networks, even with a high classification accuracy, are vulnerable to small $\ell_\infty$-norm bounded adversarial perturbations. Although many attempts have been made, most previous works either can only provide empirical verification of the defense to a particular attack method, or can only develop a certified guarantee of the model robustness in limited scenarios. In this paper, we seek for a new approach to develop a theoretically principled neural network that inherently resists $\ell_\infty$ perturbations. In particular, we design a novel neuron that uses $\ell_\infty$-distance as its basic operation (which we call $\ell_\infty$-dist neuron), and show that any neural network constructed with $\ell_\infty$-dist neurons (called $\ell_{\infty}$-dist net) is naturally a 1-Lipschitz function with respect to $\ell_\infty$-norm. This directly provides a rigorous guarantee of the certified robustness based on the margin of prediction outputs. We then prove that such networks have enough expressive power to approximate any 1-Lipschitz function with robust generalization guarantee. We further provide a holistic training strategy that can greatly alleviate optimization difficulties. Experimental results show that using $\ell_{\infty}$-dist nets as basic building blocks, we consistently achieve state-of-the-art performance on commonly used datasets: 93.09% certified accuracy on MNIST ($\epsilon=0.3$), 35.42% on CIFAR-10 ($\epsilon=8/255$) and 16.31% on TinyImageNet ($\epsilon=1/255$).
BibTeX
@misc{zhang2021towards,
  author = {Bohang Zhang and Tianle Cai and Zhou Lu and Di He and Liwei Wang},
  title = {{Towards Certifying π“βˆž Robustness using Neural Networks with π“βˆž-dist Neurons}},
  year = {2021},
  eprint = {2102.05363},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.05363},
}
Figure