arXiv stat.ML
· Papers
Bagging Robustly Learns VC Classes with Linear Sample Complexity
arXiv:2608.13514v1 Announce Type: new Abstract: 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 bou