Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks

By Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, George Pappas. 2019

570 citations recorded by the source corpus.

Tight estimation of the Lipschitz constant for deep neural networks (DNNs) is useful in many applications ranging from robustness certification of classifiers to stability analysis of closed-loop systems with reinforcement learning controllers. Existing methods in the literature for estimating the Lipschitz constant suffer from either lack of accuracy or poor scalability. In this paper, we present a convex optimization framework to compute guaranteed upper bounds on the Lipschitz constant of DNNs both accurately and efficiently. Our main idea is to interpret activation functions as gradients of convex potential functions. Hence, they satisfy certain properties that can be described by quadratic constraints. This particular description allows us to pose the Lipschitz constant estimation problem as a semidefinite program (SDP). The resulting SDP can be adapted to increase either the estimation accuracy (by capturing the interaction between activation functions of different layers) or scalability (by decomposition and parallel implementation). We illustrate the utility of our approach with a variety of experiments on randomly generated networks and on classifiers trained on the MNIST and Iris datasets. In particular, we experimentally demonstrate that our Lipschitz bounds are the most accurate compared to those in the literature. We also study the impact of adversarial training methods on the Lipschitz bounds of the resulting classifiers and show that our bounds can be used to efficiently provide robustness guarantees.

Subfields: Artificial Intelligence

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

Citations in the corpus

The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “Second, it depends on the Lipschitz continuity constant M of the loss function; in the context of deep learning, M is controlled by network architectures and its value is typically unknown, although it might be estimated in certain cases via computationally intensive algorithms (Fazlyab et al., 2019”
The Lipschitz Constant of Self-Attention (2020, methodology): “Even in this case however, exact evaluation of the Lipschitz constant of fully-connected and convolutional networks is NP-hard (Virmaux & Scaman, 2018) and obtaining a tight upper bound remains a challenging task, with various works in this direction (Virmaux & Scaman, 2018; Fazlyab et al., 2019; La”
Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds (2021, methodology): “This is different from existing works leveraging optimization tools to find local Lipschitz bound for a fixed network [10, 11].”
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.”
Safe Control With Learned Certificates: A Survey of Neural Lyapunov, Barrier, and Contraction Methods for Robotics and Control (2022, unknown): “First, the use of the Lipschitz constant necessarily introduces conservatism by assuming worst case variation between sampled points (and the estimated Lipschitz constant itself can be either difficult to estimate [84] or provide a very loose upper bound).”
Exactly Computing the Local Lipschitz Constant of ReLU Networks (2020, methodology): “LipSDP uses incremental quadratic constraints to yield a global upper bound on the `2 Lipschitz constant (Fazlyab et al., 2019).”
Globally-Robust Neural Networks (2021, background): “For more complicated networks, there is a growing body of work on computing layer-wise Lipschitz bounds for various types of layers that are commonly used in neural networks (Zou et al., 2019; Fazlyab et al., 2019; Sedghi et al., 2019; Singla & Feizi, 2019; Miyato et al., 2018).”
SmoothLLM: Defending Large Language Models Against Jailbreaking Attacks (2023, unknown): “[60] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas.”
On Mean Absolute Error for Deep Neural Network Based Vector-to-Vector Regression (2020, methodology): “We employ the fact that DNNs with the ReLU activation function are Lipschitz continuous [36].”
Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning (2021, methodology): “, via an SDP-based estimation (112)) and then used to guide re-training until the Lipschitz constraint is satisfied, or (ii) an active enforcement approach where the Lipschitz constraint is directly enforced by the training algorithm of the DNN (e.”
Lipschitz-Certifiable Training with a Tight Outer Bound (2020, methodology): “On the other hand, using local Lipschitz constants to estimate the outer bounds for each given input x is computationally infeasible to be integrated into the training loop for medium-sized networks, and thus limited to 2-layered networks [15, 10, 20].”