Mixed integer quadratically constrained quadratic programming for neural network Lipschitz constant computation

To ensure or certify the robustness of a neural network, its Lipschitz constant plays a prominent role. However, its calculation is NP-hard and one can only expect to bound or estimate it when computing time is limited. By taking into account activation regions at each ReLU neural network layer as new constraints, we propose new quadratically constrained Mixed Integer Programming (MIP) formulations for the neural network Lipschitz constant computation problem. The solutions of these problems provide lower bounds and upper bounds and we show that these bounds coincide with the Lipschitz constant almost everywhere in the parameter space of the neural network. Using various benchmark architectures and datasets from the literature, we run numerical comparisons of the proposed approach with a polynomial optimization technique, a mixed integer programming technique and a branch and bound method. The results show that, when the computing time budget is limited, the quadratically constrained MIP formulation achieves tighter bounds than the other methods for the L2 and L∞-norms.