pith. sign in

arxiv: 2604.07055 · v2 · submitted 2026-04-08 · 💻 cs.LG

AdaBoost Does Not Always Cycle: A Computer-Assisted Counterexample

Erik Y. Wang This is my paper

Pith reviewed 2026-05-10 18:51 UTC · model grok-4.3

classification 💻 cs.LG
keywords AdaBoostconvergencecounterexampleboosting algorithmsperiodic cyclesirrational frequencycomputer-assisted proofexact arithmetic
0
0 comments X

The pith

AdaBoost does not always converge to a finite cycle, as a block-product construction forces an irrational asymptotic frequency in its burst-winner sequence.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper supplies a computer-assisted counterexample showing that exhaustive AdaBoost need not settle into any repeating cycle. The construction assembles a block-product gadget from two component maps that share an exact period-2 orbit under their five-step branch maps yet possess linearized return maps whose dominant eigenvalues have an irrational logarithmic ratio. This irrational ratio produces an asymptotic frequency for the burst-winner sequence that cannot be rational, and therefore the overall sequence cannot become periodic after any finite prefix. Every step is verified using only exact rational arithmetic. A reader cares because the 2012 open question asked whether the algorithm always cycles, and the answer is now known to be negative in at least one concrete case.

Core claim

The central claim is that exhaustive AdaBoost does not always converge to a finite cycle. A block-product gadget is built whose two factors share an exact period-2 orbit for their 5-step branch maps while their linearized return maps have dominant eigenvalues with an irrational logarithmic ratio. This forces the burst-winner sequence to have an irrational asymptotic frequency, which precludes eventual periodicity. All assertions are certified by exact rational arithmetic.

What carries the argument

The block-product gadget whose factors share a period-2 orbit under 5-step branch maps but have an irrational logarithmic ratio of dominant eigenvalues in their linearized return maps.

If this is right

  • Exhaustive AdaBoost need not converge to any finite cycle.
  • The long-term behavior of AdaBoost can be driven by irrational frequencies that prevent periodicity.
  • Counterexamples of this form can be certified entirely by exact rational arithmetic without floating-point computation.
  • The same style of block-product construction may be reusable for other iterative algorithms whose convergence was previously conjectured.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Analyses of boosting algorithms must now allow for the possibility of aperiodic dynamics rather than assuming eventual cycling.
  • The prevalence of such non-cycling instances under random or natural data distributions remains open.
  • Similar gadgets could be tested in related iterative methods such as other margin-based learners to see whether irrational frequencies arise more generally.

Load-bearing premise

The two factors of the block-product gadget share an exact period-2 orbit for their 5-step branch maps while the logarithmic ratio of the dominant eigenvalues of their linearized return maps is irrational.

What would settle it

Running the burst-winner sequence for a large but finite number of steps in the explicit block-product construction and checking whether a finite repeating block appears, or exhibiting an algebraic proof that the logarithmic eigenvalue ratio is rational.

Figures

Figures reproduced from arXiv: 2604.07055 by Erik Y. Wang.

Figure 1
Figure 1. Figure 1: Schematic construction of M0 = LA ⊞ LB. Rows are indexed by (r, s) ∈ {1, 2, 3, 4} × {1, 2, 3, 4, 5}. The first four columns are copied from row r of LA, while the last four columns are copied from row s of LB. 3 The gadgets, the product system, and the exact invariant affine manifolds The counterexample is built from two small sign matrices, which we call gadgets. Let LA =   1 1 −1 −1 −1 1 1 1 1 −1 −1 … view at source ↗
Figure 2
Figure 2. Figure 2: Schematic of the no-finite-cycle argument. The four points [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript constructs a computer-assisted counterexample to the open question posed by Rudin, Schapire, and Daubechies in COLT 2012 on whether exhaustive AdaBoost always converges to a finite cycle. It introduces a block-product gadget formed from two factors that share an exact period-2 orbit under their 5-step branch maps. The linearized return maps of these factors have dominant eigenvalues whose logarithmic ratio is irrational, as established through exact rational arithmetic certification. This irrationality implies that the burst-winner sequence possesses an irrational asymptotic frequency, which precludes eventual periodicity.

Significance. If the construction and certification hold, the result provides a negative answer to a longstanding open problem in boosting theory. The explicit gadget design combined with exact-arithmetic verification (rather than floating-point or heuristic checks) is a clear strength, enabling independent reproduction and strengthening the reliability of the counterexample.

major comments (1)
  1. The irrationality of the logarithmic ratio of the dominant eigenvalues is load-bearing for the central claim that the frequency is irrational. While the abstract states that this is certified by exact rational arithmetic, the manuscript should explicitly identify the algebraic number field or minimal polynomial used in the certification (e.g., in the section describing the eigenvalue computation) so that readers can confirm the irrationality without re-executing the computer-assisted steps.
minor comments (2)
  1. The abstract notes collaboration with specific large-language-model versions; this disclosure is better placed in the acknowledgments section rather than the abstract.
  2. Consider adding an appendix that lists the explicit rational matrices and characteristic polynomials arising in the block-product construction to facilitate direct verification.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and the constructive suggestion regarding the presentation of our certification. We agree that greater explicitness will improve accessibility and verifiability.

read point-by-point responses

  1. Referee: The irrationality of the logarithmic ratio of the dominant eigenvalues is load-bearing for the central claim that the frequency is irrational. While the abstract states that this is certified by exact rational arithmetic, the manuscript should explicitly identify the algebraic number field or minimal polynomial used in the certification (e.g., in the section describing the eigenvalue computation) so that readers can confirm the irrationality without re-executing the computer-assisted steps.

    Authors: We agree that readers should be able to inspect the algebraic data without re-running the certification code. In the revised manuscript we will add, in the subsection on the linearized return maps, the minimal polynomials over Q for the two dominant eigenvalues, the degrees of the respective number fields, and a short paragraph explaining how exact rational arithmetic in those fields is used to certify that the ratio of their logarithms is irrational. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper constructs an explicit block-product gadget whose shared period-2 orbit under the 5-step branch maps and the irrational logarithmic ratio of dominant eigenvalues in the linearized return maps are both certified directly by exact rational arithmetic. The irrational asymptotic frequency of the burst-winner sequence is then deduced from these verified properties, precluding periodicity. No load-bearing step reduces by definition, by fitting a parameter then relabeling it a prediction, or by a self-citation chain; the argument is self-contained and externally verifiable via the stated exact-arithmetic certification.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the existence of a custom block-product gadget whose orbit-sharing and eigenvalue properties are asserted but not derived from more primitive axioms in the abstract.

axioms (1)
  • domain assumption The two factors share an exact period-2 orbit for their 5-step branch maps
    Invoked as the starting point of the gadget construction in the abstract.
invented entities (1)
  • block-product gadget no independent evidence
    purpose: To embed two period-2 orbits whose combined linearized dynamics produce an irrational frequency ratio
    Newly introduced construction whose independent existence is verified only computationally within the paper.

pith-pipeline@v0.9.0 · 5403 in / 1176 out tokens · 41819 ms · 2026-05-10T18:51:01.291113+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Springer, 1997

    David Cox, John Little, Donal O’shea, and Moss Sweedler.Ideals, varieties, and algorithms. Springer, 1997

    work page 1997

  2. [2]

    SolveAll.org - real research problems

    Edgar Dobriban. SolveAll.org - real research problems. no known solutions. https://solveall. org/, 2026. Accessed: 2026-04-06

    work page 2026

  3. [3]

    Schapire

    Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting.Journal of Computer and System Sciences, 55(1):119–139, 1997

    work page 1997

  4. [4]

    Graduate Texts in Mathematics

    Serge Lang.Algebra. Graduate Texts in Mathematics. Springer, 2012

    work page 2012

  5. [5]

    Sympy: symbolic computing in python.PeerJ Computer Science, 3:e103, 2017

    Aaron Meurer, Christopher P Smith, Mateusz Paprocki, Ondˇ rej ˇCert´ ık, Sergey B Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K Moore, Sartaj Singh, et al. Sympy: symbolic computing in python.PeerJ Computer Science, 3:e103, 2017

    work page 2017

  6. [6]

    Moore, R

    Ramon E. Moore, R. Baker Kearfott, and Michael J. Cloud.Introduction to Interval Analysis. SIAM, Philadelphia, 2009

    work page 2009

  7. [7]

    Schapire

    Cynthia Rudin, Ingrid Daubechies, and Robert E. Schapire. The dynamics of AdaBoost: Cyclic behavior and convergence of margins.Journal of Machine Learning Research, 5:1557–1595, 2004

    work page 2004

  8. [8]

    Schapire, and Ingrid Daubechies

    Cynthia Rudin, Robert E. Schapire, and Ingrid Daubechies. Open problem: Does AdaBoost always cycle? InProceedings of the 25th Annual Conference on Learning Theory (COLT), volume 23 ofProceedings of Machine Learning Research, pages 46.1–46.4. PMLR, 2012

    work page 2012

  9. [9]

    Schapire and Yoav Freund.Boosting: Foundations and Algorithms

    Robert E. Schapire and Yoav Freund.Boosting: Foundations and Algorithms. MIT Press, 2012. 43

    work page 2012