Adversarially robust PAC learning has proved to be challenging, with the
currently best known learners [Montasser et al., 2021a] relying on improper
methods based on intricate compression schemes, resulting in sample complexity
exponential in the VC-dimension. A series of follow up work considered a
slightly relaxed version of the problem called adversarially robust learning
with tolerance [Ashtiani et al., 2023, Bhattacharjee et al., 2023, Raman et
al., 2024] and achieved better sample complexity in terms of the VC-dimension.
However, those algorithms were either improper and complex, or required
additional assumptions on the hypothesis class H. We prove, for the first time,
the existence of a simpler learner that achieves a sample complexity linear in
the VC-dimension without requiring additional assumptions on H. Even though our
learner is improper, it is "almost proper" in the sense that it outputs a
hypothesis that is "similar" to a hypothesis in H.
We also use the ideas from our algorithm to construct a semi-supervised
learner in the tolerant setting. This simple algorithm achieves comparable
bounds to the previous (non-tolerant) semi-supervised algorithm of Attias et
al. [2022a], but avoids the use of intricate subroutines from previous works,
and is "almost proper."