# Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- Builds on 57 of its 85 references that are in the map.
- First posted on arXiv 4 Oct 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [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)
- [A Downsampled Variant of ImageNet as an Alternative to the CIFAR datasets](https://mlsanity.com/paper/1707.08819/) (2017)
- [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)
- [Regularisation of Neural Networks by Enforcing Lipschitz Continuity](https://mlsanity.com/paper/1804.04368/) (2018)
- [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)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [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)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [MMA Training: Direct Input Space Margin Maximization through Adversarial Training](https://mlsanity.com/paper/1812.02637/) (2018)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)

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

- [Certified Training: Small Boxes are All You Need](https://mlsanity.com/paper/2210.04871/) (2022)
- [Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation](https://mlsanity.com/paper/2210.07394/) (2022)
- [Improving Lipschitz-Constrained Neural Networks by Learning Activation Functions](https://mlsanity.com/paper/2210.16222/) (2022)
- [Expressive Losses for Verified Robustness via Convex Combinations](https://mlsanity.com/paper/2305.13991/) (2023)
- [Denoising Masked AutoEncoders Help Robust Classification](https://mlsanity.com/paper/2210.06983/) (2022)
- [Temperature Balancing, Layer-wise Weight Analysis, and Neural Network Training](https://mlsanity.com/paper/2312.00359/) (2023)
- [Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram Iteration](https://mlsanity.com/paper/2305.16173/) (2023)
- [Banana: Banach Fixed-Point Network for Pointcloud Segmentation with Inter-Part Equivariance](https://mlsanity.com/paper/2305.16314/) (2023)
- [Decoupled Rationalization with Asymmetric Learning Rates: A Flexible Lipschitz Restraint](https://mlsanity.com/paper/2305.13599/) (2023)
- [Eliminating Catastrophic Overfitting Via Abnormal Adversarial Examples Regularization](https://mlsanity.com/paper/2404.08154/) (2024)
- [TAPS: Connecting Certified and Adversarial Training](https://mlsanity.com/paper/2305.04574/) (2023)
- [Verification of Neural Networks' Global Robustness](https://mlsanity.com/paper/2402.19322/) (2024)
- [Raising the Bar for Certified Adversarial Robustness with Diffusion Models](https://mlsanity.com/paper/2305.10388/) (2023)
- [Improve Robustness of Reinforcement Learning against Observation Perturbations via l_∞ Lipschitz Policy Networks](https://mlsanity.com/paper/2312.08751/) (2023)
- [LRS: Enhancing Adversarial Transferability through Lipschitz Regularized Surrogate](https://mlsanity.com/paper/2312.13118/) (2023)
- [Towards Optimal Adversarial Robust Q-learning with Bellman Infinity-error](https://mlsanity.com/paper/2402.02165/) (2024)
- [Low-Rank Adversarial PGD Attack](https://mlsanity.com/paper/2410.12607/) (2024)
- [Subhomogeneous Deep Equilibrium Models](https://mlsanity.com/paper/2403.00720/) (2024)
- [On Using Certified Training towards Empirical Robustness](https://mlsanity.com/paper/2410.01617/) (2024)
- [Achieving Domain-Independent Certified Robustness via Knowledge Continuity](https://mlsanity.com/paper/2411.01644/) (2024)
- [Exposing and Defending the Achilles' Heel of Video Mixture-of-Experts](https://mlsanity.com/paper/2602.01369/) (2026)
- [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)
- [COMMIT: Certifying Robustness of Multi-Sensor Fusion Systems against Semantic Attacks](https://mlsanity.com/paper/2403.02329/) (2024)
- [Learning conditional distributions on continuous spaces](https://mlsanity.com/paper/2406.09375/) (2024)
- [Estimating Neural Network Robustness via Lipschitz Constant and Architecture Sensitivity](https://mlsanity.com/paper/2410.23382/) (2024)
- [TAROT: Towards Essentially Domain-Invariant Robustness with Theoretical Justification](https://mlsanity.com/paper/2505.06580/) (2025)
- [Optimization-Induced Dynamics of Lipschitz Continuity in Neural Networks](https://mlsanity.com/paper/2506.18588/) (2025)
- [Robust Behavior Cloning Via Global Lipschitz Regularization](https://mlsanity.com/paper/2506.19250/) (2025)
- [Consensus-based optimization for closed-box adversarial attacks and a connection to evolution strategies](https://mlsanity.com/paper/2506.24048/) (2025)

## Abstract (arXiv)

Designing neural networks with bounded Lipschitz constant is a promising way to obtain certifiably robust classifiers against adversarial examples. However, the relevant progress for the important ℓ_∞ perturbation setting is rather limited, and a principled understanding of how to design expressive ℓ_∞ Lipschitz networks is still lacking. In this paper, we bridge the gap by studying certified ℓ_∞ robustness from a novel perspective of representing Boolean functions. We derive two fundamental impossibility results that hold for any standard Lipschitz network: one for robust classification on finite datasets, and the other for Lipschitz function approximation. These results identify that networks built upon norm-bounded affine layers and Lipschitz activations intrinsically lose expressive power even in the two-dimensional case, and shed light on how recently proposed Lipschitz networks (e.g., GroupSort and ℓ_∞-distance nets) bypass these impossibilities by leveraging order statistic functions. Finally, based on these insights, we develop a unified Lipschitz network that generalizes prior works, and design a practical version that can be efficiently trained (making certified robust training free). Extensive experiments show that our approach is scalable, efficient, and consistently yields better certified robustness across multiple datasets and perturbation radii than prior Lipschitz networks. Our code is available at https://github.com/zbh2047/SortNet.