The rate of convergence of AdaBoost

Indraneel Mukherjee, Cynthia Rudin, Robert E. SchapireJMLR 2013

TL;DR

This paper provides a rigorous analysis of AdaBoost's convergence rate, offering both upper and lower bounds on how quickly it approaches optimal performance. The authors resolve a long-standing conjecture by showing that AdaBoost's convergence rate is polynomial in the inverse of the desired accuracy and, crucially, in the norm of the optimal solution, but not necessarily in the number of training examples.

What Problem Does This Paper Address?

AdaBoost is a powerful and widely used ensemble learning algorithm that combines many "weak" learners into a single "strong" learner with high accuracy. While its empirical success is undeniable, a deep theoretical understanding of its convergence properties, particularly its rate of convergence, has remained elusive. Previous work often relied on simplifying assumptions (like the "weak learning assumption") that don't always hold in practice. This paper aims to provide a more general and precise understanding of how quickly AdaBoost converges to the minimum possible error (exponential loss), without these restrictive assumptions. Specifically, it addresses the question of how the number of training rounds scales with the desired accuracy and the complexity of the underlying problem.

Methods

The paper approaches AdaBoost's convergence from a coordinate descent perspective. This means viewing AdaBoost as an iterative process that optimizes a loss function by adjusting one parameter (corresponding to a weak hypothesis) at a time. The key techniques include:

  • Coordinate Descent Analysis: The authors reframe AdaBoost as a coordinate descent algorithm minimizing the exponential loss. This allows them to leverage tools from optimization theory.
  • Decomposition Lemma: A central technical contribution is a lemma that partitions the training data into a "zero-loss set" and a "finite-margin set." This decomposition is crucial for analyzing convergence in the general case where no finite solution might achieve the optimal loss.
  • Upper and Lower Bounds: The paper derives both theoretical upper bounds (guaranteeing a certain rate of convergence) and lower bounds (showing that this rate is necessary in the worst case) for AdaBoost's convergence. These bounds are expressed in terms of the desired accuracy ($\epsilon$) and the $l_1$-norm of the optimal solution ($B$).
  • Analysis of Constants: The authors investigate the constants appearing in the convergence rates, showing how they depend on intrinsic properties of the dataset and feature matrix.

Datasets

The paper does not focus on specific benchmark datasets for training or evaluation. Instead, it uses synthetically constructed feature matrices to demonstrate theoretical bounds and worst-case scenarios. These matrices are designed to highlight specific properties relevant to the convergence analysis, such as complementary rows or specific entry patterns.

Key Insights and Ideas

  • Polynomial Dependence on Optimal Solution Norm is Necessary: A major finding is that the convergence rate must depend polynomially on the $l_1$-norm of the optimal solution ($B$). This means that if the optimal solution is complex (has a large norm), AdaBoost will take longer to converge. This is a significant insight because it highlights a fundamental limitation related to the problem's inherent difficulty, not just the algorithm's efficiency.
  • $O(1/\epsilon)$ Rate for Optimal Loss is Tight: For convergence to the optimal loss (not just an arbitrary target loss), the paper shows an $O(1/\epsilon)$ rate, which is proven to be optimal up to constant factors. This is a strong result, indicating that AdaBoost's speed in finding the best possible solution scales linearly with the inverse of the desired accuracy.
  • Decomposition Lemma is Key: The novel decomposition lemma, splitting data into zero-loss and finite-margin sets, is the cornerstone for proving general convergence rates. It allows for a more nuanced analysis by treating different types of data points separately.
  • Coordinate Descent Equivalence: The paper solidifies the view of AdaBoost as a coordinate descent algorithm, providing a unified framework for understanding its optimization process.

Key Results

  • Theorem 1: AdaBoost achieves a loss within $\epsilon$ of the optimal loss $L(\lambda^*)$ in at most $O(B^6/\epsilon^5)$ rounds, where $B$ is the $l_1$-norm of the optimal solution. Lower bounds show this polynomial dependence on $B$ and $1/\epsilon$ is necessary.
  • Theorem 14: AdaBoost converges to within $\epsilon$ of the optimal loss in at most $O(C/\epsilon)$ rounds, where $C$ depends only on the feature matrix. This $O(1/\epsilon)$ dependence on accuracy is shown to be optimal.
  • AdaBoost.S Variant: A modified algorithm, AdaBoost.S, is introduced, which achieves a faster rate of $O(B^3/\epsilon)$ for convergence to an arbitrary target loss, suggesting that minor algorithmic tweaks can significantly improve performance.
  • Lower Bounds: The paper constructs specific datasets and matrices that demonstrate the necessity of polynomial dependence on $B$ and $1/\epsilon$ for convergence rates.

Limitations and Future Work

  • Large Exponents in Bounds: The authors acknowledge that the exponents in their upper bounds (e.g., $B^6/\epsilon^5$) are likely not tight and could be improved.
  • Constant $C$ Dependence: While the $O(1/\epsilon)$ rate for optimal loss is tight, the constant $C$ can be arbitrarily large in the worst case for real-valued feature matrices, and doubly exponential in the number of examples for integer matrices. This suggests that understanding the behavior of this constant is an important area for future work.
  • Conjectures: The paper proposes tighter conjectures for convergence rates, particularly for the $O(B^2/\epsilon)$ rate for arbitrary target loss and $O(m \ln m / \epsilon^{1+o(1)})$ for optimal loss with integer matrices, which remain open problems.
  • Practical Implications: While the theoretical analysis is rigorous, the paper doesn't directly explore the practical implications of these bounds for tuning AdaBoost or understanding its performance on real-world datasets beyond the theoretical guarantees.

Summary updated

BibTeX
@article{mukherjee2013rate,
  author = {Indraneel Mukherjee and Cynthia Rudin and Robert E. Schapire},
  title = {{The rate of convergence of AdaBoost}},
  journal = {J. Mach. Learn. Res.},
  year = {2013},
}
Figure