# Sorting out Lipschitz function approximation

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

## Key facts

- Cited by 213 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2018.

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

- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Orthogonalizing Convolutional Layers with the Cayley Transform](https://mlsanity.com/paper/2104.07167/) (2021)
- [JFB: Jacobian-Free Backpropagation for Implicit Networks](https://mlsanity.com/paper/2103.12803/) (2021)
- [Learning Smooth Neural Functions via Lipschitz Regularization](https://mlsanity.com/paper/2202.08345/) (2022)
- [Generative Modeling with Optimal Transport Maps](https://mlsanity.com/paper/2110.02999/) (2021)
- [Skew Orthogonal Convolutions](https://mlsanity.com/paper/2105.11417/) (2021)
- [Spectral Normalisation for Deep Reinforcement Learning: an Optimisation Perspective](https://mlsanity.com/paper/2105.05246/) (2021)
- [Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds](https://mlsanity.com/paper/2111.01395/) (2021)
- [A Dynamical System Perspective for Lipschitz Neural Networks](https://mlsanity.com/paper/2110.12690/) (2021)
- [A Unified Algebraic Perspective on Lipschitz Neural Networks](https://mlsanity.com/paper/2303.03169/) (2023)
- [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)
- [Direct Parameterization of Lipschitz-Bounded Deep Networks](https://mlsanity.com/paper/2301.11526/) (2023)
- [A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awareness](https://mlsanity.com/paper/2205.00403/) (2022)
- [Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100](https://mlsanity.com/paper/2108.04062/) (2021)
- [Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation](https://mlsanity.com/paper/2210.07394/) (2022)
- [How Smooth Is Attention?](https://mlsanity.com/paper/2312.14820/) (2023)
- [A Neural-Network-Based Convex Regularizer for Inverse Problems](https://mlsanity.com/paper/2211.12461/) (2022)
- [Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons](https://mlsanity.com/paper/2102.05363/) (2021)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (2021)
- [Almost-Orthogonal Layers for Efficient General-Purpose Lipschitz Networks](https://mlsanity.com/paper/2208.03160/) (2022)
- [On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning](https://mlsanity.com/paper/2210.06443/) (2022)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Wasserstein GANs Work Because They Fail (to Approximate the Wasserstein Distance)](https://mlsanity.com/paper/2103.01678/) (2021)
- [Neural Network Robustness as a Verification Property: A Principled Case Study](https://mlsanity.com/paper/2104.01396/) (2021)
- [LOT: Layer-wise Orthogonal Training on Improving ℓ2 Certified Robustness](https://mlsanity.com/paper/2210.11620/) (2022)
- [Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural networks](https://mlsanity.com/paper/2104.05097/) (2021)
- [Universal approximation property of invertible neural networks](https://mlsanity.com/paper/2204.07415/) (2022)
- [Low Curvature Activations Reduce Overfitting in Adversarial Training](https://mlsanity.com/paper/2102.07861/) (2021)

## Abstract (arXiv)

Training neural networks under a strict Lipschitz constraint is useful for provable adversarial robustness, generalization bounds, interpretable gradients, and Wasserstein distance estimation. By the composition property of Lipschitz functions, it suffices to ensure that each individual affine transformation or nonlinear activation is 1-Lipschitz. The challenge is to do this while maintaining the expressive power. We identify a necessary property for such an architecture: each of the layers must preserve the gradient norm during backpropagation. Based on this, we propose to combine a gradient norm preserving activation function, GroupSort, with norm-constrained weight matrices. We show that norm-constrained GroupSort architectures are universal Lipschitz function approximators. Empirically, we show that norm-constrained GroupSort networks achieve tighter estimates of Wasserstein distance than their ReLU counterparts and can achieve provable adversarial robustness guarantees with little cost to accuracy.