Comparing Complexities of Decision Boundaries for Robust Training: A Universal Approach

Daniel Kienitz, Ekaterina Komendantskaya, Michael A Lones; Proceedings of the Asian Conference on Computer Vision (ACCV), 2022, pp. 4495-4513

We investigate the geometric complexity of decision boundaries for robust training compared to standard training. By considering the local geometry of nearest neighbour sets, we study them in a model-agnostic way and theoretically derive a lower-bound \Rstar \in \mathbb R on the perturbation magnitude \delta \in \mathbb R for which robust training provably requires a geometrically more complex decision boundary than accurate training. We show that state-of-the-art robust models learn more complex decision boundaries than their non-robust counterparts, confirming previous hypotheses. Then, we compute \Rstar for common image benchmarks and find that it also empirically serves as an upper bound over which label noise is introduced. We demonstrate for deep neural network classifiers that perturbation magnitudes \delta \geq \Rstar lead to reduced robustness and generalization performance. Therefore, \Rstar bounds the maximum feasible perturbation magnitude for norm-bounded robust training and data augmentation. Finally, we show that \Rstar < 0.5R for common benchmarks, where R is a distribution's minimum nearest neighbour distance. Thus, we improve previous work on determining a distribution's maximum robust radius.