AdaBoost's quadratic-over-accuracy convergence conjecture

Let λ\bm{\lambda}^* be any weight vector and let B=λ1B=\|\bm{\lambda}^*\|_1. For exponential loss LL and AdaBoost's iterates, quadratic convergence conjecture. For every λ\bm{\lambda}^* and every ε>0\varepsilon>0, AdaBoost reaches loss at most L(λ)+εL(\bm{\lambda}^*)+\varepsilon in O(B2/ε)O(B^2/\varepsilon) rounds, with only absolute constants hidden by the order notation. The paper proves a polynomial rate with a larger exponent and identifies this conjectured monotonicity-based rate as likely but unproved.

Sources & referencesView supporting material

Primary source

Indraneel Mukherjee, Cynthia Rudin and Robert E. Schapire, “The Rate of Convergence of AdaBoost”, arXiv:1106.6024 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.