LipBaB: Computing exact Lipschitz constant of ReLU networks
This addresses the need for exact Lipschitz constants in deep learning applications like robustness certification and stability analysis, offering a novel computational method.
The authors tackled the problem of computing tight bounds for the Lipschitz constant of ReLU neural networks, introducing LipBaB, a branch and bound framework that provides certified bounds up to any desired precision for any p-norm.
The Lipschitz constant of neural networks plays an important role in several contexts of deep learning ranging from robustness certification and regularization to stability analysis of systems with neural network controllers. Obtaining tight bounds of the Lipschitz constant is therefore important. We introduce LipBaB, a branch and bound framework to compute certified bounds of the local Lipschitz constant of deep neural networks with ReLU activation functions up to any desired precision. We achieve this by bounding the norm of the Jacobians, corresponding to different activation patterns of the network caused within the input domain. Our algorithm can provide provably exact computation of the Lipschitz constant for any p-norm.