Bagging Robustly Learns VC Classes with Linear Sample Complexity

We revisit the problem of learning predictors robust to adversarial examples at test-time.

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of…