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

The gist 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.

Boosting and Expressive Power

Boosting is a paradigm where weak learners are repeatedly trained and combined to form a strong learner, transforming simple rules into highly accurate predictors <ref:2610.10383#pg2>. The central question addressed is what can be learned by boosting hypotheses from a fixed simple base class <ref:2610.10383#pg3>. A key motivation is that the weak hypotheses are intended to be simple “rules of thumb” <ref:2610.10383#pg3>. Decision stumps are particularly canonical, depending on a single feature and threshold, and were used as a standard base hypothesis class in early AdaBoost evaluations <ref:2610.10383#pg3>.

The γ-VC Dimension

The paper introduces the concept of the γ-VC dimension to characterize the sample complexity for weak-to-strong learning up to a constant factor scaling in γ <ref:2610.10383#pg4>. Definition 1.1 defines a sample as γ-realizable with respect to H if there exists a hypothesis h ∈ H such that corrQ(h):= E(x,y)∼Q[y · h(x)] ≥ γ <ref:2610.10383#pg4>. This parameter measures how rich a family of target concepts can be weakly represented, with edge γ, by the base class <ref:2610.10383#pg4>. It also characterizes the sample complexity of weak-to-strong learning <ref:2610.10383#pg5>.

VC and γ-VC Dimension Relationship

The paper establishes a relationship between the classic VC dimension and the γ-VC dimension. Theorem 1.3 states that for any hypothesis class H, VCγ(H) = O(VC(H)/γ2) <ref:2610.10383#pg6>. This is an upper bound derived from empirical Rademacher complexity <ref:2610.10383#pg7>. Furthermore, for every integer d = omega(log(1/γ)), there exists a base hypothesis class H with VC dimension VC(H) ≤ d for which the sample complexity bound is tight <ref:2610.10383#pg9>.

Expressivity of Simple Concept Classes

The study then focuses on simple classes like decision stumps and axis-parallel rectangles. For decision stumps in R d, the bounds are determined by discrepancy theory <ref:2610.10383#pg11>. Theorem 4.3 provides an upper bound for VCγ(DSd) as VCγ(DSd) = O min (√d/γ log d/γ, log d/γ2)! <ref:2610.10383#pg12>. The paper shows that for d ≤ 1/γ2, the γ-VC dimension of decision stumps grows as √d/γ <ref:2610.10383#pg14>.

Algorithmic Guarantees and Bounds

The analysis connects the γ-VC dimension to sample complexity via BaggedAdaBoost <ref:2610.10383#pg7>. Theorem 1.2 guarantees that the BaggedAdaBoost algorithm satisfies an error bound of O(dCγ + log(1/δ)) with respect to n samples <ref:2610.10383#pg15>. The paper proves that this dependence on VC dimension can be replaced by VCCγ(H) for a universal constant C <ref:2610.10383#pg7>.

Lower Bounds and Final Results

The paper establishes lower bounds for the γ-VC dimension of decision stumps, showing that VCγ(DSd) = omega (√d/γ) in certain regimes <ref:2610.10383#pg15>. For axis-parallel rectangles Rd, the lower bound is VCγ(Rd) = omega d (log(d−1)/2 (1/γ)/γ) <ref:2610.10383#pg21>. Finally, the worst-case sample complexity for weak-to-strong learning is established as Θ d/(εγ2) + log(1/δ)/ε <ref:2610.10383#pg7>. The paper concludes by showing that combining AdaBoost with bagging achieves a sample complexity of O ((dCγ + log(1/δ))/ε) <ref:2610.10383#pg24>. This result is formalized in Theorem 6.1, which states the guarantee for the BaggedAdaBoost algorithm <ref:2610.10383#pg25>. The lower bound on sample complexity is given by Theorem 6.9, showing that there exists a distribution D over X and a target c: X → ±1 such that P[LD(A(S)) > ε] ≥ δ <ref:2610.10383#pg28>. This demonstrates the required sample size for weak-to-strong learning with a γ-weak learner is at least omega ((dγ + log(1/δ))/ε) <ref:2610.10383#pg29>. The results show that VCγ is the right information-theoretic parameter for weak-to-strong learning and gives a boosting-style algorithm matching this parameter up to a constant-factor change in the margin <ref:2610.10383#pg7>. This paper is 2610.10383. The references include work on PAC learning, discrepancy theory, and boosting algorithms. The acknowledgements note that ChatGPT suggested using the discrepancy bound for intervals in permutations due to Spencer et al. [2001] which led to an improvement of the upper bound in Theorem 1.4 from O √ d γ log 3/2 d γ to O √ d γ log d γ. The authors take full responsibility for all results and the content of this paper. The references list includes foundational works on VC dimension, boosting, and discrepancy methods. The paper is 2610.10383.

--- Page 1 ---

The gist 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.

How it works

Boosting is a paradigm where weak learners are repeatedly trained and combined to form a strong learner, transforming simple rules into highly accurate predictors <ref:2610.10383#pg2>. The central question addressed is what can be learned by boosting hypotheses from a fixed simple base class <ref:2610.10383#pg3>. A key motivation is that the weak hypotheses are intended to be simple “rules of thumb” <ref:2610.10383#pg3>. Decision stumps are particularly canonical, depending on a single feature and threshold, and were used as a standard base hypothesis class in early AdaBoost evaluations <ref:2610.10383#pg3>.

The γ-VC Dimension

The paper introduces the concept of the γ-VC dimension to characterize the sample complexity for weak-to-strong learning up to a constant factor scaling in γ <ref:2610.10383#pg4>. Definition 1.1 defines a sample as γ-realizable with respect to H if there exists a hypothesis h ∈ H such that corrQ(h):= E(x,y)∼Q[y · h(x)] ≥ γ <ref:2610.10383#pg4>. This parameter measures how rich a family of target concepts can be weakly represented, with edge γ, by the base class <ref:2610.10383#pg4>.

Lower Bounds and Final Results

The paper establishes lower bounds for the γ-VC dimension of decision stumps, showing that VCγ(DSd) = omega (√d/γ) in certain regimes <ref:2610.10383#pg15>. For axis-parallel rectangles Rd, the lower bound is VCγ(Rd) = omega d (log(d−1)/2 (1/γ)/γ) <ref:2610.10383#pg21>.

1. Bold header: Adaptive Sample Complexity for Boosting

The improved system can achieve error at most ε with O(dCγ + log(1/δ)ε) samples when using a γ-weak learner with base class H having a Cγ-VC dimension dCγ, as stated in Theorem 6.1.

2. Bold header: Optimized Boosting Algorithm

The BaggedAdaBoost algorithm can be implemented to guarantee that for every distribution D over X × Σ and every δ ∈ (0, 1), it returns a classifier with error at most ε with O(dCγ + log(1/δ)ε) samples, replacing the classical VC-based bound.

3. Bold header: Enhanced Expressive Power for Simple Learners

The system can leverage the improved bounds on the γ-VC dimension for simple classes like decision stumps, which shows that classes such as decision stumps have logarithmic ordinary VC dimension in terms of the ambient dimension, yet their boosted expressivity can grow polynomially with the ambient dimension.

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 R d.