Fast & Accurate Method for Bounding the Singular Values of Convolutional Layers with Application to Lipschitz Regularization

Alexandre Araujo, Benjamin Négrevergne, Yann Chevaleyre, Jamal Atif

Abstract

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.

Introduction

The Lipschitz constant of a neural network quantifies its sensitivity to input perturbations. Controlling this constant—Lipschitz regularization—is essential for ensuring training stability, improving generalization, and enhancing robustness against adversarial attacks. However, determining the exact Lipschitz constant of a deep network is an NP-hard problem. Typically, researchers approximate it by multiplying the spectral norms (maximum singular values) of individual layers. For convolutional layers, this spectral norm corresponds to the maximum singular value of the associated weight matrix. Existing methods like the power method are computationally intensive, while faster alternatives often yield loose bounds that over-regularize the model. This work introduces "LipBound," a method that is both tight and computationally efficient.

Methodology

The core innovation lies in bridging deep learning operations with classical matrix theory. A 2D convolution can be represented as a doubly-block Toeplitz matrix. The authors leverage three key components:

  1. Toeplitz-Fourier Link: The singular values of Toeplitz matrices are asymptotically related to the Fourier transform of their generating sequence.
  2. LipBound Theorem: A new upper bound is derived based on the maximum modulus of a multivariate trigonometric polynomial constructed from the convolution kernel.
  3. PolyGrid Algorithm: To find the maximum of these polynomials, the authors employ a grid search. Since convolution kernels in deep learning are typically small (e.g., 3x3, 5x5), this search is highly efficient and parallelizable on GPUs.
Visualizing the modulus of the multivariate trigonometric polynomials for various kernel sizes. The PolyGrid algorithm efficiently searches these landscapes to find the maximum value, which serves as the LipBound.

Key Insights

A critical observation is the asymptotic tightness of the proposed bound. As the input image size increases, the gap between the LipBound and the true singular value diminishes, making the bound nearly exact for high-resolution inputs like those in ImageNet.

The approximation gap (the difference between the LipBound and the true singular value) decreases rapidly as image size increases, making the bound nearly exact for realistic input sizes.

Furthermore, the inherent small size of kernels in modern architectures turns a theoretically hard optimization problem into a practically simple one. This efficiency allows Lipschitz regularization (LipReg) to be used alongside Adversarial Training (AT), where it helps control adversarial generalization error more effectively than AT alone.

Experimental Results

The method was evaluated on CIFAR-10, CIFAR-100, and ImageNet using Wide ResNet and ResNet-101 architectures.

  • Efficiency: LipBound achieved an accuracy ratio of 0.992 (relative to the true spectral norm) while being nearly 10x faster than the best power-method-based approaches (0.49ms vs 4.30ms per layer).
  • Robustness: On CIFAR-10, combining AT with LipBound (AT+LipReg) increased accuracy under PGD attacks to 45.7%, up from 42.6% with standard AT.
  • Scalability: Successful application to ResNet-101 on ImageNet demonstrated that the method scales to large datasets and deep architectures without significant overhead.

Conclusion

LipBound provides a "best of both worlds" solution for Lipschitz regularization in CNNs. While the PolyGrid search complexity scales with kernel size, it remains optimal for the small kernels prevalent in current architectures. Future work includes extending this framework to dilated or depthwise convolutions and exploring applications in GAN stability and invertible neural networks.

Summary updated

Abstract

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.
BibTeX
@inproceedings{araujo2021fast,
  author = {Alexandre Araujo and Benjamin Négrevergne and Yann Chevaleyre and Jamal Atif},
  title = {{Fast \& Accurate Method for Bounding the Singular Values of Convolutional Layers with Application to Lipschitz Regularization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=IhuHv9RQ5-5},
}
Figure