Theoretical framework links adversarial robustness to lattice traversal for multilayered perceptrons

A new arXiv preprint introduces a theoretical framework that reduces the adversarial robustness problem for multilayered perceptron (MLP) classifiers to a lattice traversal problem. In this formulation, each lattice element corresponds to an interval—an axis-aligned hyper-rectangle—containing an input point x.

The authors define two types of robustness certifications: a sound certification guarantees that x can be freely perturbed within the interval without changing the MLP’s prediction, while a complete certification guarantees that moving x outside the interval will change the prediction. Although sound certification aligns with the well-studied adversarial robustness problem, complete certification has not been previously formalized in the literature.

The paper develops lattice traversal operators and applies them within a refine-and-verify iterative scheme, leveraging formal MLP verifiers to ensure sound maximality and complete minimality. The authors also analyze associated optimization problems, uncovering computational asymmetries: minimum solutions for complete certifications can be obtained in polynomial oracle calls, whereas sound certifications are shown to be strongly intractable.

Additionally, the researchers provide logarithmic-time algorithms for optimization in symmetric intervals (ℓ∞-spheres) and present an empirical evaluation using a novel system called ParallelepipedoNN.