  In this work we propose a graph-based learning framework to train models with
provable robustness to adversarial perturbations. In contrast to
regularization-based approaches, we formulate the adversarially robust learning
problem as one of loss minimization with a Lipschitz constraint, and show that
the saddle point of the associated Lagrangian is characterized by a Poisson
equation with weighted Laplace operator. Further, the weighting for the Laplace
operator is given by the Lagrange multiplier for the Lipschitz constraint,
which modulates the sensitivity of the minimizer to perturbations. We then
design a provably robust training scheme using graph-based discretization of
the input space and a primal-dual algorithm to converge to the Lagrangian's
saddle point. Our analysis establishes a novel connection between elliptic
operators with constraint-enforced weighting and adversarial learning. We also
study the complementary problem of improving the robustness of minimizers with
a margin on their loss, formulated as a loss-constrained minimization problem
of the Lipschitz constant. We propose a technique to obtain robustified
minimizers, and evaluate fundamental Lipschitz lower bounds by approaching
Lipschitz constant minimization via a sequence of gradient $p$-norm
minimization problems. Ultimately, our results show that, for a desired nominal
performance, there exists a fundamental lower bound on the sensitivity to
adversarial perturbations that depends only on the loss function and the data
distribution, and that improvements in robustness beyond this bound can only be
made at the expense of nominal performance. Our training schemes provably
achieve these bounds both under constraints on performance and~robustness.
