AdaBoost Does Not Always Cycle: A Computer-Assisted Counterexample

Erik Y. Wang

cs.LGApr 8, 2026

AdaBoost Does Not Always Cycle: A Computer-Assisted Counterexample

Authors: Erik Y. Wang

Organizations: Department of Computer Science, Stanford University

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Schematic construction of $M_{0}=L_{A}\boxplus L_{B}$ . Rows are indexed by $(r,s)\in\{1,2,3,4\}\times\{1,2,3,4,5\}$ . The first four columns are copied from row $r$ of $L_{A}$ , while the last four columns are copied from row $s$ of $L_{B}$ .

Panel of Figure 2 — Figure 2: Schematic of the no-finite-cycle argument. The four points $Q_{ij}=P_{i}^{A}\otimes P_{j}^{B}$ sit at the vertices of a phase square in $\mathcal{P}$ , pairwise separated by at least $\delta>0$ . Each A-burst ( blue ) toggles the A-phase $i$ , and each B-burst ( orange ) toggles the B-phase $j$ . The burst-boundary states $W_{n}$ ( red dots ) converge toward these vertices as $\|W_{n}-Q_{i_{n}j_{n}}\|\to 0$ , but the irrational limiting frequency of A-bursts precludes eventual periodicity of the burst-winner sequence and hence convergence of the AdaBoost orbit to any finite cycle.

Ensemble Learning

Ensemble learning combines multiple predictors to improve accuracy, robustness, calibration, or uncertainty estimates.

See all 272 papers

AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block
Aug 14, 2026Kenan Xu, Xiangfeng WangAI-Assisted Mathematical Discovery Alternating Direction Method of Multipliers
School of Mathematical Sciences, East China Normal University, Shanghai 200241, P.R. China. · Key Laboratory of Mathematics and Engineering Applications (MoE) and School of Mathematical Sciences, East China Normal University, Shanghai 200241, P.R. China.
Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH
Aug 2, 2026Xin Zou, Jingyuan XuEnsemble Learning Multiclass Classification
Independent Researcher · School of Computer Science, Wuhan University, Wuhan, China
Exploring Collatz Dynamics with Human-LLM Collaboration
Mar 10, 2026Edward Y. ChangDynamical Systems
Computer Science, Stanford University · QuadriumAI

Aug 14, 2026J/K move · Enter open · S save

AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block

Kenan Xu, Xiangfeng Wang

School of Mathematical Sciences, East China Normal University, Shanghai 200241, P.R. China. · Key Laboratory of Mathematics and Engineering Applications (MoE) and School of Mathematical Sciences, East China Normal University, Shanghai 200241, P.R. China.

AI-Assisted Mathematical Discovery Alternating Direction Method of Multipliers

Open paper AskPDF arXiv

The alternating direction method of multipliers (ADMM), as a landmark algorithm, has attracted tremendous research attention and extensive practical applications over the past two decades. It is well known that, although the two-block ADMM enjoys well-established theoretical convergence guarantees, its direct extension to the three-block case may fail to converge, as demonstrated by existing counterexamples [5]. However, to the best of our knowledge, the case in which the third constraint block is the identity remains unresolved: the existing literature gives neither a general convergence proof nor a counterexample for this subclass. In this paper, we give a negative answer: direct three-block ADMM may fail even when the first two blocks are strongly convex quadratics. Using Codex with GPT-5.6 Sol, we construct an explicit rational counterexample candidate and verify it along a piecewise-affine reduction path; exact checks show that direct three-block ADMM on this instance produces a bounded nonconvergent orbit of period 66. Within the same Codex workflow, we further guide a study of multiplier relaxation and clarify when convergence can be restored at the fixed-instance and class levels: a problem-dependent small dual step can restore convergence, whereas no positive relative step works uniformly over the whole class. Furthermore, we also test the recent Kimi Code with Kimi K3 model without the Codex candidate or project-specific route guidance; along a different path it produces an exact locally attracting period-23 certificate, convertible to an equivalent all-identity instance. The comparison suggests that different research-harness configurations can shape the mathematical objects explored and the certificates pursued.

Abstract

Ensemble Learning

Explore similar work

AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block

Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH

Exploring Collatz Dynamics with Human-LLM Collaboration