Lipschitz regularity of deep neural networks: analysis and efficient estimation

By Kevin Scaman, Aladin Virmaux. 2018

703 citations recorded by the source corpus.

Deep neural networks are notorious for being sensitive to small well-chosen perturbations, and estimating the regularity of such architectures is of utmost importance for safe and robust practical applications. In this paper, we investigate one of the key characteristics to assess the regularity of such methods: the Lipschitz constant of deep learning architectures. First, we show that, even for two layer neural networks, the exact computation of this quantity is NP-hard and state-of-art methods may significantly overestimate it. Then, we both extend and improve previous estimation methods by providing AutoLip, the first generic algorithm for upper bounding the Lipschitz constant of any automatically differentiable function. We provide a power method algorithm working with automatic differentiation, allowing efficient computations even on large convolutions. Second, for sequential neural networks, we propose an improved algorithm named SeqLip that takes advantage of the linear computation graph to split the computation per pair of consecutive layers. Third we propose heuristics on SeqLip in order to tackle very large networks. Our experiments show that SeqLip can significantly improve on the existing upper bounds. Finally, we provide an implementation of AutoLip in the PyTorch environment that may be used to better estimate the robustness of a given neural network to small perturbations or regularize it using more precise Lipschitz estimations.

Subfields: Artificial Intelligence, Safety, Robustness & Interpretability, 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 Safety, Robustness & Interpretability

In Statistical Learning Theory

Citations in the corpus

On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning (2022, neutral): “Therefore, for a single point x ∈ R n , we obtain: Unfortunately, computing the Lipschitz constant of even the most simple multi-layer perceptron is a NP-hard problem [77].”
Improving MMD-GAN Training with Repulsive Loss Function (2018, methodology): “In this study, Leaky ReLU (LReLU) was used at each layer of D, thus LIPPICO ≈ 1 (Virmaux & Scaman (2018)).”
Learning Smooth Neural Functions via Lipschitz Regularization (2022, methodology): “Several papers complement this subject by proposing more accurate methods to estimate the true Lipschitz constant, such as [Jordan and Dimakis 2020; Virmaux and Scaman 2018; Weng et al. 2018].”
Exactly Computing the Local Lipschitz Constant of ReLU Networks (2020, methodology): “Since, every computational ﬂavor of an optimization problem has a poly-time equivalent decision problem, we will simply claim that an optimization problem is NP-hard if its decision problem is NP-hard.”
Machine Unlearning of Features and Labels (2021, background): “Furthermore, the active research field of Lipschitz-continuous neural networks [23, 30, 49] already provides promising models that may result in better unlearning guarantees in the near future.”
The power of quantum neural networks (2020, background): “2 are satisfied for a large class of classical and quantum statistical models [49, 50], as well as many popular loss functions.”
Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes (2019, methodology): “Exactly computing the Lipschitz constant of neural networks has also been shown to be NP-hard [22], but overestimations of the Lipschitz constant have been shown to provide lower bounds to the pointwise robustness [15, 25, 19, 10, 21].”
Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds (2021, background): “Finding an exact local Lipschitz constant for a neural network is generally NP hard [16], so most works focus on finding a sound upper bound.”
The Lipschitz Constant of Self-Attention (2020, methodology): “(2) Next, we outline some basic results that are useful for estimating Lipschitz constants, also covered in related works (Virmaux & Scaman, 2018; Behrmann et al., 2019).”
Vision GNN: An Image is Worth Graph of Nodes (2022, background): “The Lipschitz constant of FFN is related to the norm of weight matrices and is usually much larger than 1 [52].”
Is Homophily a Necessity for Graph Neural Networks? (2021, background): “ReLU and sigmoid) are 1-Lipschitz continuous [28], i.”
Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks (2019, methodology): “We are aware of only two methods that bound the Lipschitz constant and can scale to fully-connected networks with more than two hidden layers; these methods are [10], which we will refer to as CPLip, and [37], which is called SeqLip.”
On Lipschitz Bounds of General Convolutional Neural Networks (2018, methodology): “In contrast, [11], [15], [16] utilize the gradient with respect to the input instead of the Lipschitz constant.”
Lipschitz Continuity Guided Knowledge Distillation (2021, background): “By Definition 1, ∥f∥Lip has an excellent property of upper bounding the relationship between input perturbation and output variation for a given distance (generally L2 norm), thus it is considered as a metric to evaluate the robustness of neural networks to small perturbations [27, 40, 1].”