The weak-learning game of factorized AdaBoost.MH: the exact value of an instance, and the effective class number
Abstract
Let W range over the nonnegative n × K matrices of total mass one, let Y^(ℓ) be the signed one-hot label matrix of a label map ℓ: [n] → [K], and let v range over {± 1}^K. The quantity maxᵥ |(W odot Y^(ℓ))v|₁ is the binary weight mass that a factorized multi-class base classifier can induce, and Kégl asked in 2014 whether it admits a positive lower bound independent of n. Zou and Xu have recently determined its minimum over both W and ℓ exactly, W_(n,K) = C_(min{n+1,K}) with C_q = q/(3q-4) for even q ≥ 2 and C_q = (q+1)/(3q-1) for odd q ≥ 3, and they conjecture that some effective class number governs the hardness contributed by the labels. We determine the value of a fixed instance. For every n, every K and every label map using exactly m distinct labels with 2 ≤ m ≤ 9, min_(W) maxᵥ |(W odot Y^(ℓ))v|₁ = C_(min{m+1, K}). The value therefore depends on the instance only through the number of labels it uses: not on the number of examples, and not on how the examples are distributed among those labels. This identifies the effective class number of an instance as min{m+1,K} and contains W_(n,K) = C_(min{n+1,K}) as the case m = min{n,K}. The lower half of the identity is already contained, unstated, in the refined lower-bound argument of the source; what is new is the matching upper bound at every m, obtained by re-instantiating the source's own two weight-matrix constructions at m, and the exact value and its two independence properties that follow. The lower bounds are certified by optimal maximiser strategies of the underlying ± 1 matrix game, in closed form, to which the source's analytic argument has no counterpart. All the finite content is machine-checked in Lean 4; Section [sec:verif] says exactly what is and what is not formalised.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
916b25419e57066c949adc292a3fdccb4e237906d36f88ab8e65a886bf09b774
Claim ledger
Stated results
AB1routine2026-09-03
Weak duality for the finite +-1 matrix game behind W_(n,K), proved directly with no minimax theorem (existsᵥoteₒf_dual), plus the two certificate-format soundness theorems: lowerₒf_cert (an integer dual certificate on m label slots and M column slots, transported to an arbitrary instance by a slot map, bounds wSigma from below for every n, every K and every weight matrix) and upperₒfₚrimal (an integer weight table on m rows and M columns, with a 2^M-pattern check, is a weight matrix of the full instance)
AB2known2026-09-03
The constant sequence C_q of arXiv:2608.01091v2 eq. (Cq): non-increasing in q, C_(q+1) = C_q for odd q, 1/3 < C_q <= 1, and the two parity formulas C_q = q/(3q-4) for even q >= 2 and C_q = (q+1)/(3q-1) for odd q >= 3
AB3known2026-09-03
For every n, every K and every label map using at most m <= 9 distinct labels, every weight matrix admits a vote vector with wSigma >= Cₘ₊₁; and >= Cₘ when in addition every class is somebody's label. Certified by the explicit optimal maximiser mixed strategies certE1..certE9, certF1..certF9 – 18 integer certificates, check = true by decide – which are exactly tight (E[sigma_c v_c] = C, E[sigma_c vⱼ] = -C for a different used column j, E[sigma_c eps] = -C on the unused ones)
AB4candidate2026-09-03
THE EXACT VALUE OF AN INSTANCE. For every n, every K and every label map l: [n] -> [K] whose range has exactly m elements, 2 <= m <= 9, min over W in Wcal_(n,K) of max over v in +-1^K of ||(W (.) Yˡ) v||₁ equals Cₘinm+1, K – so the value depends on the instance only through the number of labels it uses, not on n and not on how the examples are distributed among those labels. This makes exact the 'effective class number' that arXiv:2608.01091v2 introduces as a conjecture: the effective class number of an instance is min|image l|+1, K, and their W_(n,K) = Cₘinn+1,K is the case m = minn,K
AB5known2026-09-03
W_(n,K) = Cₘinn+1,K – the source's own Theorem thm::exact-value – machine-checked for EVERY n >= 1 and K >= 1 with minn,K <= 9: no label matrix and weight matrix beat the bound (frakWₗower, quantified over all of them), and one attains it (frakWᵤpper, with existsₗabelₘap_card supplying the instance)
AB6routine2026-09-03
Negative controls: the minimax value of an instance is unique (IsGameValueᵤnique), so a wrong value is refuted rather than merely unproved; on n = 4, K = 5 with four distinct labels (value 3/7) a primal witness keeps wSigma strictly below 1/2 for every vote vector (too large refuted) while the dual certificate forbids wSigma <= 2/5 for every weight matrix (too small refuted); the same four labels with K = 4 have value 1/2!= 3/7 (a wrong K gives a different value); and certE4's 21 atoms with the claimed value raised from 3/7 to 1/2 fail check (the check has teeth). Non-vacuity: an instance with exactly four labels, a vote vector and a weight matrix are all exhibited
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- AdaBoost.MH (Schapire–Singer 1999) reduces multi-class classification to K binary problems by putting weights Wᵢⱼ ≥ 0 on example–label pairs and a *signed one-hot* label matrix Y (Yᵢⱼ = +1 exactly when j is example i's true class, −1 otherwise). Factorized AdaBoost.MH (Kégl 2013) uses base classifiers h(x) = α v φ(x), a single binary rule φ shared across classes with the class dependence carried by a vote vector v ∈ ±1^K. Fixing v collapses the weighted example–label problem back to a binary problem on the examples, but only with total induced mass ‖(
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7