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

Arthur da Cunha; Kasper Green Larsen; Liang-Yu Zou

cs.LGOct 7, 2026

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

Authors: Arthur da Cunha, Kasper Green Larsen, Liang-Yu Zou

Organizations: Aarhus University

Abstract

Boosting converts weak hypotheses with a small edge over random guessing into highly accurate predictors, but the expressive power of the resulting classifier can depend strongly on the structure of the base class. We study this phenomenon through the $γ$ -VC dimension introduced by Alon et al. (STOC 2021). Our first result shows that this parameter characterizes the sample complexity for weak-to-strong learning up to a constant factor scaling in $γ$ . We then sharpen the general relationship between the classic VC dimension and the $γ$ -VC dimension. Finally, we also give improved upper and lower bounds on the $γ$ -VC dimension for the fundamental concept classes of decision stumps and axis-parallel rectangles in $\mathbb{R}^d$ .

Figures & tables

Figure 1 : Illustration of the block construction. Each submatrix

A_{i}

corresponds to a subsequence

P_{i}

, and the rows of

A_{i}

are distinct

\{\pm 1\}

-patterns of length

l

Figure 2 : Illustration of the block construction. Each submatrix

A_{i}

is a

i

-scaled copy of a Hadamard matrix, and corresponds to the subsequence

P_{i}

Figure 3 : Illustration of different grid constructions when

d=2

and

m=8

Panel of Figure 4 — Figure 4 : Illustrations of the construction. The numbers $\{-1,0,+1\}$ in a cell or sub-cell represent the value of $g_{\mathbf{k}}$ at the grid points in that cell or sub-cell.

Figure 5 : Illustration of the contribution from the grid points inside a positively good cell

\sigma

\sum_{{\mathbf{q}}:{\mathbf{q}}\geq{\mathbf{p}}}g_{{\mathbf{k}},{\mathbf{q}}}

for a point

{\mathbf{p}}

contained in

\sigma

. In the left figure, the green (yellow) box represents the box formed by

{\mathbf{q}}_{1}({\mathbf{q}}_{2})

and its reflections. The contribution from the 4 grid points which form the green (yellow) boxes is 1 (0). In the right figure, the blue box represents the center sub-cell of

\sigma

. For every grid point in the red box, the contribution from it and its reflections is 1.

Explore similar work

Tight Generalization Bound for AdaBoost
Jul 29, 2026Mikael Møller HøgsgaardGeneralization Bounds Empirical Risk Minimization
Department of Statistics, University of Oxford
Bagging Robustly Learns VC Classes with Linear Sample Complexity
Aug 13, 2026Omar MontasserEmpirical Risk Minimization Tree Ensembles
Yale University
An Optimal Agnostic PAC Algorithm
Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyOptimal Sample Complexity Sample Complexity
Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley

Jul 29, 2026, cs.LGJ/K move · Enter open · S save

Tight Generalization Bound for AdaBoost

Mikael Møller Høgsgaard

Department of Statistics, University of Oxford

Generalization Bounds Empirical Risk Minimization Upper Bounds

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Tight Generalization Bound for AdaBoost

Bagging Robustly Learns VC Classes with Linear Sample Complexity

An Optimal Agnostic PAC Algorithm