  We establish an equivalence between a family of adversarial training problems
for non-parametric binary classification and a family of regularized risk
minimization problems where the regularizer is a nonlocal perimeter functional.
The resulting regularized risk minimization problems admit exact convex
relaxations of the type $L^1+$ (nonlocal) $\operatorname{TV}$, a form
frequently studied in image analysis and graph-based learning. A rich geometric
structure is revealed by this reformulation which in turn allows us to
establish a series of properties of optimal solutions of the original problem,
including the existence of minimal and maximal solutions (interpreted in a
suitable sense), and the existence of regular solutions (also interpreted in a
suitable sense). In addition, we highlight how the connection between
adversarial training and perimeter minimization problems provides a novel,
directly interpretable, statistical motivation for a family of regularized risk
minimization problems involving perimeter/total variation. The majority of our
theoretical results are independent of the distance used to define adversarial
attacks.
