Sorting out Lipschitz function approximation

By Cem Anil, James Lucas, Roger Baker Grosse. 2018

386 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Simple and Principled Uncertainty Estimation with Deterministic Deep Learning via Distance Awareness (2020, methodology): “, gradient penalty or norm-preserving activation [1, 2, 12, 28]), and we chose spectral normalization in this work due to its simplicity and its minimal impact on a DNN’s architecture and the optimization dynamics [3, 5, 62].”
Certified Adversarial Robustness via Randomized Smoothing (2019, methodology): “Some conservative methods bound the global Lipschitz constant of the neural network (Gouk et al., 2018; Tsuzuku et al., 2018; Anil et al., 2019; Cisse et al., 2017), but these approaches tend to be very loose on expressive networks.”
On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning (2022, background): “In particular, constraining the Lipschitz constant of a model – intuitively, a bound on how much the model’s response can change in proportion to a change in its input [5] – has proven to strengthen the decision surface around a point [22, 45, 46, 80, 91], preventing attacks of a given magnitude fro”
Globally-Robust Neural Networks (2021, methodology): “…or close analogues, during training to promote robustness (Tsuzuku et al., 2018; Raghunathan et al., 2018; Cisse et al., 2017; Cohen et al., 2019b; Anil et al., 2019; Pauli et al., 2021; Qin et al., 2019; Finlay & Oberman, 2019; Lee et al., 2020; Gouk et al., 2021; Singla & Feizi, 2019; Farnia et…”
JFB: Jacobian-Free Backpropagation for Implicit Networks (2021, methodology): “The L -Lipschitz condition on T Θ is used since recent works show Lipschitz continuity with respect to inputs improves generalization (Sokoli´c et al. 2017; Gouk et al. 2021; Finlay et al. 2018) and adversarial robustness (Cisse et al. 2017; Anil, Lucas, and Grosse 2019).”
On the Connection Between Adversarial Robustness and Saliency Map Interpretability (2019, background): “(Anil et al., 2018) previously noted that Lip-schitz constrained networks exhibit interpretable saliency maps (without an explanation), which can be regarded as a side-effect of the increase in adversarial robustness.”
Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks (2019, methodology): “In [2], the maximum spectral norm of the network Jacobian (taken over the data distribution) is used as an estimate of the true Lipschitz constant.”
A Closer Look at Accuracy vs. Robustness (2020, background): “[2], Qian and Wegman [39], Huster et al.”
FSPool: Learning Set Representations with Featurewise Sort Pooling (2019, methodology): “More generally, sorting within a single feature vector has been used for modeling more powerful functions under a Lipschitz constraint for Wasserstein GANs [2] and improved robustness to adversarial examples [7].”
Learning Smooth Neural Functions via Lipschitz Regularization (2022, methodology): “Specifically, Anil et al. [2019] constrain all the layers to be 1-Lipschitz and multiply the final layer with a constant 𝑘 to make it 𝑘 -Lipschitz.”
On the distance between two neural networks and the stability of learning (2020, background): “A final line of related work studies the effect of architectural decisions on signal propagation through the network (Saxe et al., 2014; Pennington et al., 2017; Yang & Schoenholz, 2017; Xiao et al., 2018; Anil et al., 2019), which inspired aspects of our work.”
Wasserstein Dependency Measure for Representation Learning (2019, background): “However, recent work [2] has shown that that such techniques severely restrict the capacity of typical neural networks and could hurt performance in complex tasks where high capacity neural networks are essential.”
Learning to Optimize: A Primer and A Benchmark (2021, methodology): “This was also partially addressed by [87] where the authors used sorting activation functions [14] and Lipschitz networks to encourage gradient norm preservation.”
Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds (2021, methodology): “Since the MaxMin activation function [15] has been shown to outperform ReLU on certified robustness [4, 30], we take MaxMin as an example to explain how to apply our local Lipschitz bound.”
The Lipschitz Constant of Self-Attention (2020, background): “For example, Lipschitz constraints can endow models with provable robustness against adversarial pertubations (Cisse et al., 2017; Tsuzuku et al., 2018; Anil et al., 2019), and guaranteed generalisation bounds (Sokoli´c et al., 2017).”
Property-driven Training: All You (N)Ever Wanted to Know About (2021, background): “Lipschitz robustness training (Anil, Lucas, and Grosse 2019; Pauli et al. 2021) 4.”
Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (2019, background): “Combining training longer with existing techniques for constraining Lipschitz number (Anil et al., 2019; Cisse et al., 2017) could potentially alleviate this issue, and we leave it as a future work.”
Normalization Techniques in Training DNNs: Methodology, Analysis and Application (2020, background): “…a linear layer can be controlled/bounded during training by normalizing the weight with (approximate) orthogonality [23], [24], which is an important property for certiﬁed defense against adversarial attacks [282], [283], [284], and for theoretically analyzing DNNs generalization [285], [286].”