Affine-Image Propagation for Tight and Scalable $\ell_{2}$ Neural Network Verification

While bound propagation methods are highly effective for certifying neural network robustness against $\ell_{\infty}$ adversaries, scalable verification for $\ell_{2}$ perturbations remains a significant open challenge. Existing approaches suffer from severe geometric loss: elementwise bounding methods like $\alpha$-CROWN relax Euclidean balls to bounding boxes, losing a factor of $\sqrt{n}$ in radius, while the recently proposed SDP-CROWN rounds deformed ellipsoids back into balls, losing a factor proportional to the condition number of the weights. Consequently, tight $\ell_{2}$ verification is currently restricted to near-isometric or Lipschitz-regularized networks where these approximations are not vacuous. In this paper, we introduce affine-image propagation, a novel CROWN-compatible framework that exactly propagates the affine geometry of $\ell_{2}$ balls and $\ell_{\infty}$ boxes through the network. To bypass the prohibitive computational cost of exact Semidefinite Programming (SDP) constraints required by this representation, we derive highly scalable, SDP-based bounds utilizing diagonal-dominance surrogates. Our approach effectively eliminates the geometric bottlenecks of prior work, yielding the first large-scale, SDP-style bound propagation method capable of tight $\ell_{2}$ verification for general, non-Lipschitz-regularized neural networks.