  This paper tackles the problem of Lipschitz regularization of Convolutional
Neural Networks. Lipschitz regularity is now established as a key property of
modern deep learning with implications in training stability, generalization,
robustness against adversarial examples, etc. However, computing the exact
value of the Lipschitz constant of a neural network is known to be NP-hard.
Recent attempts from the literature introduce upper bounds to approximate this
constant that are either efficient but loose or accurate but computationally
expensive. In this work, by leveraging the theory of Toeplitz matrices, we
introduce a new upper bound for convolutional layers that is both tight and
easy to compute. Based on this result we devise an algorithm to train Lipschitz
regularized Convolutional Neural Networks.
