  We propose the first general PAC-Bayesian generalization bounds for
adversarial robustness, that estimate, at test time, how much a model will be
invariant to imperceptible perturbations in the input. Instead of deriving a
worst-case analysis of the risk of a hypothesis over all the possible
perturbations, we leverage the PAC-Bayesian framework to bound the averaged
risk on the perturbations for majority votes (over the whole class of
hypotheses). Our theoretically founded analysis has the advantage to provide
general bounds (i) independent from the type of perturbations (i.e., the
adversarial attacks), (ii) that are tight thanks to the PAC-Bayesian framework,
(iii) that can be directly minimized during the learning phase to obtain a
robust model on different attacks at test time.
