AdaBoost's quadratic-over-accuracy convergence conjecture

About 15 years old · traced to

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.

References

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.