Bagging Robustly Learns VC Classes with Linear Sample Complexity
The paper claims a simple bagging-plus-RERM method cuts robust learning sample complexity for VC classes to linear in VC dimension.
Omar Montasser proves an exponential improvement over the 2019 upper bound for adversarially robust learning. The algorithm runs robust ERM on independent bootstrap samples and returns a majority vote, using `O(d*)` oracle calls where `d*` is the dual VC dimension. The paper also gives a matching lower bound in that oracle model: in general, `Ω(d*)` RERM calls are necessary even with unlimited training data. Source: ArXiv · AI/CL/LG's note.
Omar Montasser proves an exponential improvement over the 2019 upper bound for adversarially robust learning. The algorithm runs robust ERM on independent bootstrap samples and returns a majority vote, using `O(d*)` oracle calls where `d*` is the dual VC dimension. The paper also gives a matching lower bound in that oracle model: in general, `Ω(d*)` RERM calls are necessary even with unlimited training data. Source: ArXiv · AI/CL/LG's note.
score 6