Improved Generalization Bounds for Robust Learning
  We consider a model of robust learning in an adversarial environment. The
learner gets uncorrupted training data with access to possible corruptions that
may be effected by the adversary during testing. The learner's goal is to build
a robust classifier, which will be tested on future adversarial examples. The
adversary is limited to $k$ possible corruptions for each input. We model the
learner-adversary interaction as a zero-sum game. This model is closely related
to the adversarial examples model of Schmidt et al. (2018); Madry et al.
(2017). Our main results consist of generalization bounds for the binary and
multiclass classification, as well as the real-valued case (regression). For
the binary classification setting, we both tighten the generalization bound of
Feige, Mansour, and Schapire (2015), and are also able to handle infinite
hypothesis classes. The sample complexity is improved from
$O(\frac{1}{\epsilon^4}\log(\frac{|\mathcal{H}|}{\delta}))$ to
$O\big(\frac{1}{\epsilon^2}(\sqrt{k
\mathrm{VC}(\mathcal{H})}\log^{\frac{3}{2}+\alpha}(k\mathrm{VC}(\mathcal{H}))+\log(\frac{1}{\delta})\big)$
for any $\alpha > 0$. Additionally, we extend the algorithm and generalization
bound from the binary to the multiclass and real-valued cases. Along the way,
we obtain results on fat-shattering dimension and Rademacher complexity of
$k$-fold maxima over function classes; these may be of independent interest.
  For binary classification, the algorithm of Feige et al. (2015) uses a regret
minimization algorithm and an ERM oracle as a black box; we adapt it for the
multiclass and regression settings. The algorithm provides us with near-optimal
policies for the players on a given training sample.
