about
AdaBoost Does Not Always Cycle (arxiv.org)
2 points by gone35 18 days ago | hide | past | pdf | discuss on HN

In plain words: A 2012 question asked whether AdaBoost's exhaustive version, which keeps retraining on the hardest cases, always settles into a repeating cycle. A two-part example whose growth rates have an irrational ratio shows it does not: the winners never settle into a cycle, all checked exactly.

Abstract · AdaBoost Does Not Always Cycle: A Computer-Assisted Counterexample

We give a computer-assisted counterexample to the open question, posed by Rudin, Schapire, and Daubechies in COLT 2012, of whether exhaustive AdaBoost always converges to a finite cycle. The construction is based on a block-product gadget whose two factors share an exact period-2 orbit for their 5-step branch maps, but whose linearized return maps have dominant eigenvalues with an irrational logarithmic ratio. This irrationality forces the burst-winner sequence to have an irrational asymptotic frequency, precluding eventual periodicity. All assertions are certified by exact rational arithmetic. This work was developed in collaboration with GPT-5.4 Pro and Claude Opus 4.6.

Erik Y. Wang
arXiv:2604.07055 · cs.LG · submitted Apr 8, 2026 · updated Apr 17, 2026
abstract · pdf · html

add comment on HN