Mixed integer quadratically constrained quadratic programming for neural network Lipschitz constant computation
提出一种新的混合整数二次约束二次规划方法，通过引入激活区域约束，在有限计算时间内为神经网络Lipschitz常数提供更紧的上下界，适用于鲁棒性认证。
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 L 2 and L ∞ -norms.