# Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons

arXiv: https://arxiv.org/abs/2102.05363 · HTML: https://mlsanity.com/paper/2102.05363/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 61 references that are in the map.
- First posted on arXiv 10 Feb 2021.

## Builds on (most cited first, 30 of 47)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Regularisation of Neural Networks by Enforcing Lipschitz Continuity](https://mlsanity.com/paper/1804.04368/) (2018)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks](https://mlsanity.com/paper/1802.04034/) (2018)
- [Spectral Norm Regularization for Improving the Generalizability of Deep Learning](https://mlsanity.com/paper/1705.10941/) (2017)
- [MMA Training: Direct Input Space Margin Maximization through Adversarial Training](https://mlsanity.com/paper/1812.02637/) (2018)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)

## Built on by (most cited first, 30 of 40)

- [Certified Training: Small Boxes are All You Need](https://mlsanity.com/paper/2210.04871/) (2022)
- [Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective](https://mlsanity.com/paper/2210.01787/) (2022)
- [Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation](https://mlsanity.com/paper/2210.07394/) (2022)
- [Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspective](https://mlsanity.com/paper/2206.12227/) (2022)
- [Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural networks](https://mlsanity.com/paper/2104.05097/) (2021)
- [Boosting the Certified Robustness of L-infinity Distance Nets](https://mlsanity.com/paper/2110.06850/) (2021)
- [Improving Lipschitz-Constrained Neural Networks by Learning Activation Functions](https://mlsanity.com/paper/2210.16222/) (2022)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [Expressive Losses for Verified Robustness via Convex Combinations](https://mlsanity.com/paper/2305.13991/) (2023)
- [IBP Regularization for Verified Adversarial Robustness via Branch-and-Bound](https://mlsanity.com/paper/2206.14772/) (2022)
- [Denoising Masked AutoEncoders Help Robust Classification](https://mlsanity.com/paper/2210.06983/) (2022)
- [Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization](https://mlsanity.com/paper/2310.00116/) (2023)
- [The Best Defense is a Good Offense: Adversarial Augmentation against Adversarial Attacks](https://mlsanity.com/paper/2305.14188/) (2023)
- [The Effect of Intrinsic Dataset Properties on Generalization: Unraveling Learning Differences Between Natural and Medical Images](https://mlsanity.com/paper/2401.08865/) (2024)
- [On the Paradox of Certified Training](https://mlsanity.com/paper/2102.06700/) (2021)
- [TAPS: Connecting Certified and Adversarial Training](https://mlsanity.com/paper/2305.04574/) (2023)
- [TPC: Transformation-Specific Smoothing for Point Cloud Models](https://mlsanity.com/paper/2201.12733/) (2022)
- [Towards Robust Dataset Learning](https://mlsanity.com/paper/2211.10752/) (2022)
- [Monotone, Bi-Lipschitz, and Polyak-Lojasiewicz Networks](https://mlsanity.com/paper/2402.01344/) (2024)
- [NoiLIn: Improving Adversarial Training and Correcting Stereotype of Noisy Labels](https://mlsanity.com/paper/2105.14676/) (2021)
- [One-vs-the-Rest Loss to Focus on Important Samples in Adversarial Training](https://mlsanity.com/paper/2207.10283/) (2022)
- [Improve Robustness of Reinforcement Learning against Observation Perturbations via l_∞ Lipschitz Policy Networks](https://mlsanity.com/paper/2312.08751/) (2023)
- [On the Convergence of Certified Robust Training with Interval Bound Propagation](https://mlsanity.com/paper/2203.08961/) (2022)
- [Convolutional Neural Networks as 2-D systems](https://mlsanity.com/paper/2303.03042/) (2023)
- [A Scalable, Interpretable, Verifiable & Differentiable Logic Gate Convolutional Neural Network Architecture From Truth Tables](https://mlsanity.com/paper/2208.08609/) (2022)
- [Efficient Robust Conformal Prediction via Lipschitz-Bounded Networks](https://mlsanity.com/paper/2506.05434/) (2025)
- [Certified Robust Models with Slack Control and Large Lipschitz Constants](https://mlsanity.com/paper/2309.06166/) (2023)
- [Provably Adversarially Robust Nearest Prototype Classifiers](https://mlsanity.com/paper/2207.07208/) (2022)
- [Certifying Ensembles: A General Certification Theory with S-Lipschitzness](https://mlsanity.com/paper/2304.13019/) (2023)
- [Do stable neural networks exist for classification problems? -- A new view on stability in AI](https://mlsanity.com/paper/2401.07874/) (2024)

## Abstract (arXiv)

It is well-known that standard neural networks, even with a high classification accuracy, are vulnerable to small ℓ_∞-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 ℓ_∞ perturbations. In particular, we design a novel neuron that uses ℓ_∞-distance as its basic operation (which we call ℓ_∞-dist neuron), and show that any neural network constructed with ℓ_∞-dist neurons (called ℓ∞-dist net) is naturally a 1-Lipschitz function with respect to ℓ_∞-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 ℓ∞-dist nets as basic building blocks, we consistently achieve state-of-the-art performance on commonly used datasets: 93.09% certified accuracy on MNIST (ε=0.3), 35.42% on CIFAR-10 (ε=8/255) and 16.31% on TinyImageNet (ε=1/255).