Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation

• URL: http://arxiv.org/abs/2210.07394v1
• Date: Thu, 13 Oct 2022 22:23:22 GMT
• Title: Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation
• Authors: Zhouxing Shi, Yihan Wang, Huan Zhang, Zico Kolter, Cho-Jui Hsieh
• Abstract summary: Lipschitz constants are connected to many properties of neural networks, such as robustness, fairness, and generalization. Existing methods for computing Lipschitz constants either produce relatively loose upper bounds or are limited to small networks. We develop an efficient framework for computing the $ell_infty$ local Lipschitz constant of a neural network by tightly upper bounding the norm of Clarke Jacobian.
• Score: 79.13041340708395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lipschitz constants are connected to many properties of neural networks, such as robustness, fairness, and generalization. Existing methods for computing Lipschitz constants either produce relatively loose upper bounds or are limited to small networks. In this paper, we develop an efficient framework for computing the $\ell_\infty$ local Lipschitz constant of a neural network by tightly upper bounding the norm of Clarke Jacobian via linear bound propagation. We formulate the computation of local Lipschitz constants with a linear bound propagation process on a high-order backward graph induced by the chain rule of Clarke Jacobian. To enable linear bound propagation, we derive tight linear relaxations for specific nonlinearities in Clarke Jacobian. This formulate unifies existing ad-hoc approaches such as RecurJac, which can be seen as a special case of ours with weaker relaxations. The bound propagation framework also allows us to easily borrow the popular Branch-and-Bound (BaB) approach from neural network verification to further tighten Lipschitz constants. Experiments show that on tiny models, our method produces comparable bounds compared to exact methods that cannot scale to slightly larger models; on larger models, our method efficiently produces tighter results than existing relaxed or naive methods, and our method scales to much larger practical models that previous works could not handle. We also demonstrate an application on provable monotonicity analysis. Code is available at https://github.com/shizhouxing/Local-Lipschitz-Constants.

Related papers

• Scalable Lipschitz Estimation for CNNs [3.8125535078871127]
  Estimating the Lipschitz constant of deep neural networks is of growing interest. CNNs underpin much of the recent success in computer vision related applications. We propose a novel method to accelerate Lipschitz constant estimation for CNNs.
  arXiv  Detail & Related papers  (2024-03-27T14:28:44Z)
• Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram Iteration [122.51142131506639]
  We introduce a precise, fast, and differentiable upper bound for the spectral norm of convolutional layers using circulant matrix theory. We show through a comprehensive set of experiments that our approach outperforms other state-of-the-art methods in terms of precision, computational cost, and scalability. It proves highly effective for the Lipschitz regularization of convolutional neural networks, with competitive results against concurrent approaches.
  arXiv  Detail & Related papers  (2023-05-25T15:32:21Z)
• Lipschitz Continuity Retained Binary Neural Network [52.17734681659175]
  We introduce the Lipschitz continuity as the rigorous criteria to define the model robustness for BNN. We then propose to retain the Lipschitz continuity as a regularization term to improve the model robustness. Our experiments prove that our BNN-specific regularization method can effectively strengthen the robustness of BNN.
  arXiv  Detail & Related papers  (2022-07-13T22:55:04Z)
• Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds [99.23098204458336]
  Certified robustness is a desirable property for deep neural networks in safety-critical applications. We show that our method consistently outperforms state-of-the-art methods on MNIST and TinyNet datasets.
  arXiv  Detail & Related papers  (2021-11-02T06:44:10Z)
• Robust Implicit Networks via Non-Euclidean Contractions [63.91638306025768]
  Implicit neural networks show improved accuracy and significant reduction in memory consumption. They can suffer from ill-posedness and convergence instability. This paper provides a new framework to design well-posed and robust implicit neural networks.
  arXiv  Detail & Related papers  (2021-06-06T18:05:02Z)
• Efficient Proximal Mapping of the 1-path-norm of Shallow Networks [47.20962674178505]
  We show two new important properties of the 1-path-norm neural networks. First, despite its non-smoothness and non-accuracy it allows a closed proximal operator to be efficiently computed. Second, when the activation functions are differentiable, it provides an upper bound on the Lipschitz constant.
  arXiv  Detail & Related papers  (2020-07-02T10:34:06Z)
• On Lipschitz Regularization of Convolutional Layers using Toeplitz Matrix Theory [77.18089185140767]
  Lipschitz regularity is established as a key property of modern deep learning. computing the exact value of the Lipschitz constant of a neural network is known to be NP-hard. We introduce a new upper bound for convolutional layers that is both tight and easy to compute.
  arXiv  Detail & Related papers  (2020-06-15T13:23:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.