Algebraic Methods for Robustness Verification in Neural Networks

Robustness verification asks whether a neural network’s prediction remains stable under small input perturbations, a problem that is computationally challenging and often addressed through relaxations or heuristics. In this talk, I present an algebraic-geometric approach to robustness verification, formulating it as a distance minimization problem to the network’s decision boundary. This perspective brings tools from metric algebraic geometry into play, in particular the Euclidean Distance (ED) degree, which measures the intrinsic complexity of verification as a function of network architecture. I will introduce the associated ED discriminant, which identifies inputs where the number of real critical points changes, and a parameter discriminant, which characterizes parameter regimes of reduced algebraic complexity. Finally, I discuss algorithms for computing these objects, closed-form results for several architectures, and an exact robustness certification algorithm based on numerical homotopy continuation. Joint work with Yulia Alexandr and Hao Duan.