Boosting and the Expressive Power of Simple Weak Learners via the $γ$-VC Dimension

In this paper we show that the generalization error of AdaBoost is $Θ\big(\tfrac{d\ln(nγ^{2}/d)}{nγ^2}+\tfrac{\ln(1/δ)}{n}\big)$, where $γ$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the class containing the weak hypotheses, $n$ is the sample size, and $δ$ is the confidence parameter. The contribution of this paper is the upper bound; the matching lower bound follows from prior work. The upper bound proof follows by combining the known fact that AdaBoost outputs a voting classifier whose voting function has zero empirical $γ/2$-margin loss with what is, to the best of our knowledge, a new margin-based generalization bound for voting classifiers.

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 Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on $O(d^\star)$ independent bootstrap samples and outputs their majority vote, where $d^\star$ denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires $Ω(d^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.

Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<δ\le 1/2$, with probability at least $1-δ$, $$L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right).$$ This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].