Tight Generalization Bound for AdaBoost

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.

{AdaBoost.MH} reduces multi-class classification to a collection of binary subproblems and enjoys the classical boosting-type convergence guarantee under a weak learning condition. A more structured variant, Factorized {AdaBoost.MH}, uses base classifiers of the form $\mathbf{h}(x)=α\mathbf{v} \bm{\varphi}(x)$, where a single binary classifier $\bm{\varphi}$ is shared across all classes and the label dependence is carried by a vote vector $\mathbf{v} \in\{\pm1\}^K$. This factorization is algorithmically attractive and achieves better performance in practice, but its convergence depends on whether one can always choose a vote vector with sufficiently large induced binary weight mass. Previous work resolved this question with a lower bound $\max\{1/n,1/\sqrt{2K}\}$, which still leaves a dimension-dependent slowdown relative to the original {AdaBoost.MH} analysis. In this paper, we sharpen this combinatorial step. For the minimax quantity $\mathfrak{W}_{n,K}$ governing the factorized edge, we prove $\mathfrak{W}_{n,K} = C_{\min\{n+1,K\}}$, where $C_q=1$ for $q=1$, $C_q=q/(3q-4)$ for even $q\ge2$, and $C_q=(q+1)/(3q-1)$ for odd $q\ge2$. Since $C_q\downarrow 1/3$, our bounds show that $\mathfrak{W}_{n,K}=Θ(1)$ uniformly over $n$ and $K$. Consequently, Factorized {AdaBoost.MH} achieves the same boosting-type convergence rate as {AdaBoost.MH} up to a universal constant factor, removing the previously suggested additional dependence on $n$ or $K$ in the number of boosting rounds.

A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error $O((d/n)\log(n/d))$ for classes of VC dimension $d$, and that every known optimal learner can be pushed away from the $Θ(d/n)$ rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension $d$ and over known finite insertion budgets, the minimax expected error is $Θ(1/n)$ at $d=1$ and $Θ((d/n)\log(n/d))$ for $d\geq 2$. The same rates hold with Littlestone dimension $d_{\mathrm L}$ in place of $d$, so the clean online-to-batch rate $O(d_{\mathrm L}/n)$ is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.