Lipschitz regularity of deep neural networks: analysis and efficient estimation

Abstract

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.

arXiv comment12 pages, 3 figures

References in corpus (2)

• WaveNet: A Generative Model for Raw Audio
• Spectral Normalization for Generative Adversarial Networks

Cited by in corpus (21)

• Gated Graph Recurrent Neural Networks
• Solving Inverse Problems With Deep Neural Networks -- Robustness Included?
• Training robust neural networks using Lipschitz bounds
• Fixed Point Strategies in Data Science
• Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth
• Is Homophily a Necessity for Graph Neural Networks?
• Adaptive neighborhood Metric learning
• Joint Multi-Dimension Pruning via Numerical Gradient Update
• There is Limited Correlation between Coverage and Robustness for Deep Neural Networks
• A Differentially Private Framework for Deep Learning with Convexified Loss Functions
• Designing Stable Neural Networks using Convex Analysis and ODEs
• Enforcing exact physics in scientific machine learning: a data-driven exterior calculus on graphs
• Complex-valued Federated Learning with Differential Privacy and MRI Applications
• Deep KKL: Data-driven Output Prediction for Non-Linear Systems
• Tune smarter not harder: A principled approach to tuning learning rates for shallow nets
• Adversarial Robustness of Deep Learning: Theory, Algorithms, and Applications
• On the Robustness and Generalization of Deep Learning Driven Full Waveform Inversion
• Sensitivity analysis in differentially private machine learning using hybrid automatic differentiation
• An automatic differentiation system for the age of differential privacy
• Fairness Properties of Face Recognition and Obfuscation Systems
• Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations