  A major challenge in defending against adversarial attacks is the enormous
space of possible attacks that even a simple adversary might perform. To
address this, prior work has proposed a variety of defenses that effectively
reduce the size of this space. These include randomized smoothing methods that
add noise to the input to take away some of the adversary's impact. Another
approach is input discretization which limits the adversary's possible number
of actions.
  Motivated by these two approaches, we introduce a new notion of adversarial
loss which we call distributional adversarial loss, to unify these two forms of
effectively weakening an adversary. In this notion, we assume for each original
example, the allowed adversarial perturbation set is a family of distributions
(e.g., induced by a smoothing procedure), and the adversarial loss over each
example is the maximum loss over all the associated distributions. The goal is
to minimize the overall adversarial loss.
  We show generalization guarantees for our notion of adversarial loss in terms
of the VC-dimension of the hypothesis class and the size of the set of allowed
adversarial distributions associated with each input. We also investigate the
role of randomness in achieving robustness against adversarial attacks in the
methods described above. We show a general derandomization technique that
preserves the extent of a randomized classifier's robustness against
adversarial attacks. We corroborate the procedure experimentally via
derandomizing the Random Projection Filters framework of
\cite{dong2023adversarial}. Our procedure also improves the robustness of the
model against various adversarial attacks.
