Bagging Plus Robust ERM Learns VC Classes With Sample Complexity Linear in VC Dimension

arXiv 2608.13514·medium signalXBlueskyLinkedInCopy link

Montasser, Hanneke and Srebro's 2019 upper bound for adversarially robust learnability of VC classes is improved exponentially here: robust learnability with sample complexity linear in the VC dimension d. The algorithm is strikingly plain — run robust ERM on O(d*) independent bootstrap samples (d* being the dual VC dimension) and take the majority vote, i.e. Breiman's 1996 bagging heuristic composed with RERM, producing an improper learner. A matching lower bound shows the O(d*) oracle calls are unavoidable: any learner in this oracle model needs Ω(d*) RERM calls even with arbitrarily many training examples.