Bagging Robustly Learns VC Classes with Linear Sample Complexity
By Omar Montasser · Paper · stat.ML
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 Mo