Research map / Label-efficient and robust learning / Recognition and long-tail
A Boosting-Type Convergence Result for AdaBoost.MH with Factorized Multi-Class Classifiers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves convergence bounds for factorized AdaBoost.MH (binary classifier plus vote vector), resolving a COLT 2014 open problem with an n-independent edge lower bound of 1/sqrt(2K).
Problem
Factorized AdaBoost.MH (Kégl's multi-class Hamming trees) lacks a convergence rate because the factorization breaks the standard weak-learning argument; an open problem from COLT 2014 asked for a convergence rate with limited dependence on sample size n.
Approach
Shows via a minimax reformulation and averaging over Rademacher code vectors (with Khintchine inequality) that for any data and weight matrix there exists a vote vector giving pseudo-weight mass at least 1/sqrt(2K), yielding exponential convergence with T* = O(K ln(nK)) iterations under the empirical weak learning condition.
Key results
- Theorem 3.3 gives an n-dependent edge lower bound of 1/n, implying T* of order O(n^2 ln n) iterations.
- Theorem 3.4 gives an n-independent lower bound of 1/sqrt(2K), resolving the COLT 2014 open problem with T* = O(K ln(nK)) iterations (Corollary 3.6: T* = 4K ln(2n(K-1))/(δ')^2 + 1).
- Combined bound: for any data, weights and labels there exists a vote vector v with w'_Σ >= max(1/n, 1/sqrt(2K)), so the bound vanishes only if n and K grow together.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a Rademacher vote-vector argument to obtain an n-independent lower bound on w′Σ | Factorized AdaBoost.MH · Arbitrary training setup | lower bound on w′Σ: 1/n -> 1/√(2K) | Helped |
| Apply the n-independent lower bound on w′Σ under the empirical δ′-weak learning condition | Factorized AdaBoost.MH · Factorized AdaBoost.MH convergence | iterations until weighted exponential error is zero: ⌈2n² ln(2n(K−1))/(δ′)²⌉ + 1 -> ⌈4K ln(2n(K − 1))/(δ′)²⌉ + 1 | Helped |
Limitations
- Purely theoretical; no experiments validate the bounds.
- Convergence relies on the empirical δ'-weak learning assumption for the base binary classifier family.
- The NeurIPS checklist marks limitations as NA, so limitations are not discussed explicitly.
Experimental setup
Baselines: AdaBoost.MH with one-against-all classifiers Kégl factorized AdaBoost.MH
Builds on: AdaBoost.MH Kégl multi-class Hamming trees AdaBoost
Closest papers by meaning
- Precision-based Boosting (AAAI 2021 · similarity 0.88)
- AdaBoost is not an Optimal Weak to Strong Learner (ICML 2023 · similarity 0.87)
- Boosting with Tempered Exponential Measures (NeurIPS 2023 · similarity 0.85)
- SnapBoost: A Heterogeneous Boosting Machine (NeurIPS 2020 · similarity 0.85)
- The Many Faces of Optimal Weak-to-Strong Learning (NeurIPS 2024 · similarity 0.85)
- Robust Minimax Boosting with Performance Guarantees (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.