FLIP: Fast and Accurate Global Lipschitz Estimation for Large Feedforward Networks

The Lipschitz constant of neural networks is widely used in robustness, control, generalization bounds, and training stability. As modern neural networks continue to scale, existing methods for Lipschitz estimation are either very time-consuming or overly loose. In this work, we focus on both fast and accurate Lipschitz estimation for large feedforward neural networks. We first reformulate the well-known semidefinite program (SDP) framework into an explicit recursive form, and introduce a key theoretical result, bound backpropagation: the SDP objective has upper and lower bounds that can be propagated backward along the recursive computation graph and depend only on partial variables. Leveraging this property, we decompose the original SDP into a sequence of small subproblems, each minimizing a combination of upper and lower bounds over partial variables. We prove that each subproblem is one-dimensional and convex, enabling fast solution via the secant method. Finally, we present the full FLIP algorithm and its complexity, yielding fast and tight Lipschitz estimation for large feedforward networks. Experiments on both randomly generated and trained networks show that FLIP improves speed and tightness by several orders of magnitude over prior methods, giving the tightest Lipschitz estimates for 100M-parameter networks in 3 seconds.