Reviews: Lipschitz regularity of deep neural networks: analysis and efficient estimation

The paper studies the problem of estimating the Lipschitz constant of a mapping realized by a trained neural network. Several distinct contributions are made: (i) It is shown that exactly computing the Lipschitz constant of a two layer MLP (Multi Layer Preceptron) with ReLU activation is NP-hard (worst-case result). The algorithm, named AutoLip, is a generalization of multiplying spectral norms of Jacobians for a sequence of mappings, and hence usually provides pessimistic bounds. This technique assumes efficient implementation of the mapping in an auto-differentiable graph. It allows estimating the leading singular value of the transformation, which is equal to the Lipschitz constant.