  This paper investigates the theory of robustness against adversarial attacks.
We focus on randomized classifiers (\emph{i.e.} classifiers that output random
variables) and provide a thorough analysis of their behavior through the lens
of statistical learning theory and information theory. To this aim, we
introduce a new notion of robustness for randomized classifiers, enforcing
local Lipschitzness using probability metrics. Equipped with this definition,
we make two new contributions. The first one consists in devising a new upper
bound on the adversarial generalization gap of randomized classifiers. More
precisely, we devise bounds on the generalization gap and the adversarial gap
(\emph{i.e.} the gap between the risk and the worst-case risk under attack) of
randomized classifiers. The second contribution presents a yet simple but
efficient noise injection method to design robust randomized classifiers. We
show that our results are applicable to a wide range of machine learning models
under mild hypotheses. We further corroborate our findings with experimental
results using deep neural networks on standard image datasets, namely CIFAR-10
and CIFAR-100. All robust models we trained models can simultaneously achieve
state-of-the-art accuracy (over $0.82$ clean accuracy on CIFAR-10) and enjoy
\emph{guaranteed} robust accuracy bounds ($0.45$ against $\ell_2$ adversaries
with magnitude $0.5$ on CIFAR-10).
