AdaBoost is not an Optimal Weak to Strong Learner

Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert

Abstract

For decades, AdaBoost has been considered the "gold standard" for boosting weak classifiers into a strong learner. However, recent theoretical advancements have questioned its efficiency relative to the fundamental limits of sample complexity. This paper provides a definitive answer, proving that AdaBoost is sub-optimal. Specifically, it requires a sample complexity that is higher than the theoretical limit by at least one logarithmic factor in the desired accuracy ($\epsilon$).

Introduction

In the landscape of computational learning theory, "boosting" refers to the process of transforming a weak learner—an algorithm that performs only slightly better than random chance—into a strong learner capable of achieving arbitrarily high accuracy. Since its inception, AdaBoost has been the most prominent algorithm in this category.

A central question in this field is sample complexity: what is the minimum number of training samples required to achieve a specific error rate $\epsilon$? While recent research identified a theoretical lower bound and proposed a complex "majority of majorities" algorithm that achieves it, the optimality of the simpler, more ubiquitous AdaBoost remained an open question. This research demonstrates that AdaBoost fails to reach this theoretical efficiency.

The Transparency Trap: Methodology

The authors establish their findings through a rigorous mathematical proof centered on the construction of an adversarial weak learner.

As a theoretical work, this study does not rely on empirical datasets like ImageNet; instead, it utilizes a synthetic "universe" of data points to prove universal sample complexity limits. The core of the issue identified is AdaBoost's interface. Standard AdaBoost provides the weak learner with the entire training set and asks for a hypothesis that performs well on a specific distribution of those samples. The authors discovered that this "transparency" is a structural weakness. Because the weak learner can see the full training set, a "malicious" learner can identify which points in the broader data universe were not included in the sample.

The authors designed a weak learner that satisfies all formal requirements (maintaining an edge over chance on the training data) but specifically selects hypotheses that are incorrect on the data points omitted from the training set. By exploiting these "holes" in the training data, the weak learner ensures that the resulting strong learner generalizes poorly unless the training set is significantly larger than what theory suggests is necessary.

Theoretical Results

The paper’s primary contribution is formalized in Theorem 1.1, which establishes a new lower bound for AdaBoost's sample complexity:

$$m = \Omega\left(\frac{d \ln(1/\epsilon)}{\gamma^2 \epsilon}\right)$$

Where:

  • $d$ is the VC dimension.
  • $\epsilon$ is the target error rate.
  • $\gamma$ is the edge of the weak learner.

In contrast, the theoretical optimal sample complexity is $\Theta(\frac{d}{\gamma^2 \epsilon})$. The presence of the $\ln(1/\epsilon)$ factor proves that AdaBoost is sub-optimal. In high-precision applications where $\epsilon$ is very small, this logarithmic gap represents a substantial increase in the required data.

Key Insights

  • The Logarithmic Gap: The sub-optimality is not a marginal error but a structural property of the algorithm itself.
  • Sub-sampling as a Defense: The authors note that the only known optimal boosting algorithms avoid the "transparency trap" by only showing the weak learner subsets of the training data. This prevents the learner from identifying the "gaps" in the data universe.
  • Variant Vulnerability: This finding is not limited to the original AdaBoost; it extends to popular variants like AdaBoost$_\nu$ and DualLPboost, which share the same full-set interface.

Conclusion and Future Work

This research clarifies that AdaBoost's failure to reach optimality is inherent to its design. However, several questions remain. There is still a small gap between this new lower bound and the best-known upper bound for AdaBoost. Furthermore, the current "optimal" algorithms (like "majority of majorities") are computationally expensive and complex.

The authors suggest that a "sub-sampled AdaBoost" might bridge this gap, potentially offering the simplicity of AdaBoost with the efficiency of an optimal learner. Investigating whether such a modification can achieve optimality without the complexity of multi-level majority votes remains a vital area for future study.

Summary updated

BibTeX
@inproceedings{hgsgaard2023adaboost,
  author = {Mikael Møller Høgsgaard and Kasper Green Larsen and Martin Ritzert},
  title = {{AdaBoost is not an Optimal Weak to Strong Learner}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=xH0zbCNR5E},
}
Figure