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.