PaperlayerView exact revision on arXiv

Source-linked AI summary

The Rate of Convergence of AdaBoost

Indraneel Mukherjee, Cynthia Rudin, Robert E. Schapire

arXiv:1106.6024v1math.OCcs.AIstat.ML

TL;DR

AdaBoost’s convergence rate to minimum exponential loss was not fully understood, particularly without simplifying assumptions. This paper analyzes AdaBoost as coordinate descent and proves two complementary rates. It establishes polynomial dependence for bounded-norm targets and a tight, dataset-dependent C/ε rate to the best possible loss.

  • Problem

    Prior work established asymptotic convergence to minimum exponential loss but did not provide a convergence rate, and the paper seeks rates without simplifying assumptions.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes AdaBoost as coordinate descent and uses a decomposition of examples into finite-margin and zero-loss sets to prove a separate rate to the infimum.

    Source: §1 · pp. 2–3

  • Results

    Within C/ε iterations, AdaBoost reaches exponential loss at most ε above the best possible value, with dataset-dependent C; this ε dependence is tight up to constants.

    Source: §1 · pp. 2–3, §6 · p. 25

  • Takeaways & Limitations

    The paper establishes upper and lower bounds for convergence to both bounded-target losses and an infimum that may not be realizable.

    Source: §6 · p. 25

    The bounded-target rate has large exponents that the authors believe are not tight.

    Source: §3.1 · p. 9

Abstract

from arXiv · show

The AdaBoost algorithm was designed to combine many "weak" hypotheses that perform slightly better than random guessing into a "strong" hypothesis that has very low error. We study the rate at which AdaBoost iteratively converges to the minimum of the "exponential loss." Unlike previous work, our proofs do not require a weak-learning assumption, nor do they require that minimizers of the exponential loss are finite. Our first result shows that at iteration $t$, the exponential loss of AdaBoost's computed parameter vector will be at most $\epsilon$ more than that of any parameter vector of $\ell_1$-norm bounded by $B$ in a number of rounds that is at most a polynomial in $B$ and $1/\epsilon$. We also provide lower bounds showing that a polynomial dependence on these parameters is necessary. Our second result is that within $C/\epsilon$ iterations, AdaBoost achieves a value of the exponential loss that is at most $\epsilon$ more than the best possible value, where $C$ depends on the dataset. We show that this dependence of the rate on $\epsilon$ is optimal up to constant factors, i.e., at least $\Omega(1/\epsilon)$ rounds are necessary to achieve within $\epsilon$ of the optimal exponential loss.

1. Introduction

The paper studies rates for AdaBoost’s convergence to minimum exponential loss without relying on simplifying assumptions. It gives a polynomial-round guarantee relative to bounded-norm parameter vectors and a separate dataset-dependent C/ε guarantee relative to the best possible loss.

1. Introduction

  • AdaBoost is viewed as coordinate descent on exponential loss, choosing a weak hypothesis and step that lower the objective each round.Earlier work showed asymptotic convergence to the minimum, but did not give a convergence rate.Source: §1 · p. 2
  • For any parameter vector with ℓ1-norm at most B, AdaBoost reaches loss within ε of its loss in polynomially many rounds in log N, m, B, and 1/ε.The log N dependence is used because the number of weak hypotheses can be extremely large.Source: §1 · p. 2
  • Lower bounds show that some polynomial dependence on B and 1/ε is necessary for the bounded-target convergence rate.Source: §1 · p. 2
  • Within C/ε rounds, AdaBoost achieves exponential loss at most ε above the best possible value, with C depending on the dataset.This rate is separate from the bounded-norm guarantee and cannot always prove it, since C may exceed 2m in some worst cases.Source: §1 · pp. 2–3
  • The decomposition lemma splits examples into finite-margin and zero-loss sets; restricting loss to the finite-margin set yields a finite minimizer and enables the second rate proof.Source: §1 · p. 3
  • An exponential-loss guarantee may interest practitioners, but minimizing that loss need not be perfectly correlated with test accuracy.Source: §1 · p. 3

2. Coordinate Descent View of AdaBoost

AdaBoost can be formulated as coordinate descent on the exponential loss, with each round selecting a weak-hypothesis coordinate and a loss-reducing step. The formulation relates example weights to margins and extends to confidence-rated hypotheses under the paper’s specified implementation.

2. Coordinate Descent View of AdaBoost

  • AdaBoost is coordinate descent on exponential loss, represented using a feature matrix whose entries are labeled weak-hypothesis predictions.The ith coordinate of Mλ is the unnormalized margin on training example i.Source: §2 · p. 4
  • At each iteration, coordinate descent selects the steepest directional derivative and a step that maximally decreases the objective; this matches AdaBoost’s weak-learning choice.Source: §2 · pp. 4–5
  • AdaBoost’s example weights are proportional to the exponential of the negative current margin, linking its weighted correlation choice to the coordinate update.Source: §2 · pp. 4–5
  • The coordinate step is found by line search, and the loss drop depends on the edge for that round.The edge is the absolute value of the weighted correlation between the chosen hypothesis and the examples.Source: §2 · p. 5
  • The rate bounds also hold for confidence-rated hypotheses; the paper’s AdaBoost version uses the specified step size and loss guarantee, while proofs tolerate small numerical inaccuracies.Source: §2 · pp. 5–6

3. First convergence rate: Convergence to any target loss

The section bounds AdaBoost’s rounds to reach a target loss in terms of a reference vector’s ℓ1-norm and gives lower bounds showing this dependence can be necessary. It also introduces a rescaled variant and examines worst-case limits on convergence.

3.1 Upper Bound

  • 13∥λ∗∥1^6ε^-5 rounds suffice for AdaBoost to reach loss L(λ∗)+ε, giving a polynomial target-loss rate.Source: §3.1 · p. 6
  • The proof’s progress mechanism balances edge size against solution growth: large steps increase the solution size but also drive down suboptimality.Source: §3.1 · p. 6
  • The proved upper-bound exponents are described as likely loose; the proposed O(B^2/ε) rate remains a conjecture.Source: §3.1 · p. 9

3.2 Faster rates for a variant

  • AdaBoost.S optionally scales each updated hypothesis combination by the loss-minimizing scalar in [0,1], and is presented with a faster convergence rate.Source: §3.2 · p. 9
  • In the reported experiments, scaling back never occurs, so AdaBoost and AdaBoost.S are identical on those datasets.Source: §3.2 · p. 10

3.3 Lower-bounds

  • The norm-based lower-bound argument extends beyond AdaBoost to coordinate descent algorithms and a broad class of loss functions.Source: §3.3 · p. 10
  • For abstaining hypotheses, some m-example matrices require reference-solution norms exponential in m to attain loss 2/m+ε, making norm dependence necessary.Source: §3.3 · pp. 11–12
  • With arbitrary confidence levels, convergence can be arbitrarily slow: the required rounds for any fixed loss below 1 grow as Ω(1/ν).Source: §3.3 · p. 13

4. Second convergence rate: Convergence to optimal loss

This section studies AdaBoost’s convergence to optimal loss, including a feature-matrix-dependent convergence bound and an Ω(1/ε) lower bound. It estimates and bounds the quantities governing the convergence constant, with results for real-valued and {-1,0,+1} feature matrices and for the norm of η*.

4.1 Upper Bound

  • AdaBoost reaches within ε of the optimal loss in at most C/ε rounds, where C depends only on the feature matrix.The bound applies without requiring a weak-learning assumption or a finite solution attaining the optimal loss.Source: §4.1 · p. 14
  • The proof partitions examples into zero-loss Z and finite-margin F: either Z supplies a large edge or progress comes from F.When the loss on Z is small relative to suboptimality, a round reduces suboptimality by a constant fraction; the proof’s per-round quadratic decrease yields the C/ε rate.Source: §4.1 · pp. 14, 16, 18, 19
  • On a three-example dataset, 2/(9ε) rounds are necessary to reach loss at most 2/3 + ε, showing that Ω(1/ε) rounds can be necessary.For integer feature matrices, C can be Ω(2^m) in the worst case, so the bound does not establish the conjecture in.Source: §4 · p. 14, §4.1 · p. 15

4.2 Proof of the decomposition lemma

  • An admissible sequence has a subsequence whose losses vanish on Z and stay bounded away from zero on F; the proof also establishes a finite optimizer on F and bounded F-margins.For combinations with loss at most m on F, each F-margin lies in [−ln m, µmax].Source: §4.2 · pp. 19–21

4.3 Investigating the constants

  • For feature matrices with entries in {−1, 0, +1}, the constant C in Theorem 14 has an upper bound doubly exponential in the number of examples, which cannot be improved without significantly changing the previous section’s proof.Source: §4.3 · p. 21
  • For real-valued feature matrices, the convergence constant can be arbitrarily large; for {-1,0,+1} matrices, γ^-1, λ_min^-1, and μ_max can each reach Ω(2^m/m).Consequently, a bound on C derived from Corollary 23 is at least 2^{Ω(2^m/m)} in the worst case, and the previous section’s proof techniques do not admit a better bound.Source: §4.3 · pp. 22–23
  • When every entry of M is −1, 0, or +1, each of λ_min^-1 and µ_max is at most 2^{O(m ln m)}.Source: §4.3 · p. 23
  • For feature matrices with only {-1,0,+1} entries, the decomposition vector η* satisfies ||η*||_1 ≤ 2^{O(m ln m)}.Source: §4.3 · p. 23

5. Improved Estimates

The section combines earlier techniques to derive new convergence bounds and lower bounds, and proposes tighter conjectured rates. For feature matrices with entries in {-1, 0, +1}, it gives an upper bound to the optimal loss and a near-optimal conjecture.

5. Improved Estimates

  • For {-1, 0, +1} feature matrices, the derived rate to the optimal loss is 2^O(m ln m) ln^6(1/ε) ε^-5.The bound follows by combining Theorem 1 with a decomposition-lemma solution whose ℓ1-norm is at most 2^O(m ln m) ln(1/ε).Source: §5 · p. 23
  • If Conjecture 6 holds, the rate to the optimal loss improves to 2^O(m ln m) ln(1/ε) ε^-1.The paper presents this as a conjecture, not an established bound.Source: §5 · pp. 23–24
  • For feature matrices with {-1, 0, +1} entries, the conjectured rate to within ε of optimal loss is 2^O(m ln m) ε^-(1+o(1)).The conjecture is stated for AdaBoost convergence to within ε of the optimal loss.Source: §5 · p. 24
  • The section also gives lower bounds for convergence to arbitrary target losses, including that polynomial dependence on ε^-1 is unavoidable for some datasets.The argument distinguishes competing with a finite solution from convergence when the optimum is achieved by a finite solution, where O(ln(1/ε)) rounds may suffice.Source: §5 · pp. 24–25

6. Conclusion

The paper establishes upper and lower bounds for AdaBoost convergence to finite target losses and to the possibly unrealizable infimum loss. It also identifies open conjectures and notes that some derived bounds have large exponents or constants.

6. Conclusion

  • For finite target losses, a poly(B, 1/ε) rate holds, and polynomial dependence on the ℓ1-norm B is necessary.The derived upper bound has large exponents, while a minor AdaBoost variant is described as achieving a much tighter, near-optimal rate.Source: §6 · p. 25
  • For convergence to the infimum loss, the paper proves a C/ε upper bound that is tight up to constant factors.The rate constant depends on dataset-related parameters; its worst-case bound for {-1, 0, +1} feature matrices is doubly exponential in the number of training examples.Source: §6 · p. 25
  • The paper conjectures tighter bounds for both kinds of convergence that are not presently known to hold.Figure 5 summarizes the results and conjectures.Source: §6 · p. 25

Appendix

The appendix proves a lower bound on the number of AdaBoost rounds needed to approach the optimal loss on a particular dataset. Its argument tracks the edge and loss over successive rounds.

Appendix

  • For any ε < 1/3, AdaBoost needs at least 2/(9ε) steps to get within ε of the optimum loss on the dataset in Table 4.The optimum loss is 2/3, and the target loss is (2/3) + ε.Source: Appendix · pp. 26–27
  • On the analyzed dataset, the edge in each round t ≥ 2 is 1/t.The proof establishes this edge pattern by induction after specifying the normalized example weights and selected hypothesis.Source: Appendix · pp. 26–27
  • The lower bound follows by calculating the loss after T rounds from the round-by-round edges.The appendix states that the loss expression yields the 2/(9ε) requirement for ε < 1/3.Source: Appendix · p. 27

Proof of Lemma 25

The proof bounds quantities used to control convergence constants by analyzing the feature matrix and related linear systems. It also characterizes the feature matrix restricted to finite-loss examples.

Proof of Lemma 25

  • The proof reduces a nonnegative linear-system solution to a unique reduced problem by setting selected coordinates to zero.The reduction preserves the solution norm and supports the subsequent norm bound.Source: Proof of Lemma 25 · p. 29
  • For a solvable system Ax = b with {-1, 0, +1} entries and x > 0, a solution exists with norm at most 1 + k·k!, where k = rank(A).The proof first reduces to a nonnegative solution and then uses a segment to obtain a positive solution.Source: Proof of Lemma 25 · p. 30
  • The feature matrix restricted to finite-loss examples admits a positive linear combination y > 0 satisfying M_F^T y = 0.This follows from the stated characterization of M_F.Source: Proof of Lemma 25 · p. 30
  • The bound on µmax is ln m · |F|^1.5 · |F|!, which is at most 2^O(m ln m).Here F is the set of finite-loss examples.Source: Proof of Lemma 25 · p. 30
Loading 1106.6024v1…