Robust optimization for adversarial learning with finite sample
  complexity guarantees
André Bertolace Konstatinos Gatsis Kostas Margellos
Decision making and learning in the presence of uncertainty has attracted
significant attention in view of the increasing need to achieve robust and
reliable operations. In the case where uncertainty stems from the presence of
adversarial attacks this need is becoming more prominent. In this paper we
focus on linear and nonlinear classification problems and propose a novel
adversarial training method for robust classifiers, inspired by Support Vector
Machine (SVM) margins. We view robustness under a data driven lens, and derive
finite sample complexity bounds for both linear and non-linear classifiers in
binary and multi-class scenarios. Notably, our bounds match natural
classifiers' complexity. Our algorithm minimizes a worst-case surrogate loss
using Linear Programming (LP) and Second Order Cone Programming (SOCP) for
linear and non-linear models. Numerical experiments on the benchmark MNIST and
CIFAR10 datasets show our approach's comparable performance to state-of-the-art
methods, without needing adversarial examples during training. Our work offers
a comprehensive framework for enhancing binary linear and non-linear classifier
robustness, embedding robustness in learning under the presence of adversaries.