ScaLip: Bridging the Scalability–Tightness Gap in Lipschitz Estimation of Deep Neural Networks

Tight Lipschitz constant estimation is fundamental to the certified robustness of deep neural networks. While state-of-the-art Semidefinite Programming (SDP) formulations yield tight formal bounds, their monolithic Linear Matrix Inequality (LMI) constraints couple decision variables globally, scaling poorly with network depth and width. Recent compositional approaches mitigate this by breaking the massive LMI into smaller layer-wise SDPs; however, to achieve this decoupling, they should rely on intermediate surrogate objectives that inherently degrade the final bound. Moreover, despite this decomposition, the resulting layer-wise SDPs remain computationally intractable for convolutional layers. In this paper, we propose ScaLip, a novel reformulation of the exact SDP problem into an unconstrained optimization objective. By introducing a recursive framework, the strict feasibility of the underlying LMI constraints is guaranteed by construction. This reformulation allows the global Lipschitz bound to be computed efficiently, end-to-end, using highly scalable first-order methods. We mathematically prove that our unconstrained objective preserves the optimal value of the original SDP formulation. Empirical results demonstrate that ScaLip matches the tightness of monolithic SDPs while requiring only a fraction of their computational cost. Remarkably, it scales substantially better than even existing layer-wise SDP approaches, which have so far offered the most scalable SDP-based alternative. This enhanced scalability extends tight SDP-based Lipschitz estimation to convolutional neural networks and paves the way for analyzing much larger architectures.