Pith. sign in

REVIEW 6 minor 50 references

AdaBoost’s generalization error is tightly Θ(d ln(nγ²/d)/(nγ²) + ln(1/δ)/n).

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-30 19:33 UTC pith:DXB3YTYG

load-bearing objection Clean matching upper bound for AdaBoost that removes the leftover ln(ln) factor; the new zero-margin voting lemma is the real reusable piece.

arxiv 2607.26838 v1 pith:DXB3YTYG submitted 2026-07-29 cs.LG

Tight Generalization Bound for AdaBoost

Mikael M{\o}ller H{\o}gsgaard This is my paper
classification cs.LG
keywords AdaBoostgeneralization boundsmargin boundsvoting classifiersVC-dimensionweak learningboosting
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

AdaBoost turns a weak learner that is only slightly better than chance into a strong voting classifier. This paper proves that, after enough rounds, the error that classifier makes on fresh data is on the order of d ln(nγ²/d) over nγ², plus a usual confidence term. That rate matches a known lower bound, so it is tight up to constants. The proof rests on a new margin bound: any voting combination that perfectly separates the training data by a positive margin γ cannot have large true error when the weak hypotheses come from a class of VC-dimension d. A sympathetic reader cares because the classical explanation of boosting via margins is finally made quantitatively sharp for the algorithm that started the field.

Core claim

When AdaBoost is run for at least ln(n)/γ² rounds with an empirical γ-weak learner whose hypotheses lie in a class of VC-dimension d, the returned voting classifier has generalization error O(d Ln(nγ²/d)/(nγ²) + ln(1/δ)/n) with probability 1−δ. Combined with the matching Ω lower bound from prior work, the rate is therefore Θ of that quantity.

What carries the argument

A new margin-based generalization bound for voting classifiers (Theorem 1): every g in the convex hull of H with zero empirical γ-margin loss satisfies true zero-margin loss at most O(d Ln(cγ²n/d)/(γ²n) + ln(1/δ)/n). The proof uses a ghost sample of size roughly εn/2 on which every point has non-positive margin, then bounds the VC-dimension of the resulting family of index sets by O(d/γ²) via a Rademacher argument after a γ/2 shift.

Load-bearing premise

The collection of training-set index subsets that can serve as a fully misclassified ghost sample for some zero-margin voting function must itself have VC-dimension no larger than a constant times d over γ squared.

What would settle it

Exhibit a hypothesis class of VC-dimension d and an empirical γ-weak learner such that, after T ≥ ln(n)/γ² rounds, AdaBoost’s voting classifier still has true error ω(d ln(nγ²/d)/(nγ²)) on a positive fraction of distributions, or show that the admissible ghost-index family can shatter more than O(d/γ²) points.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The long-standing gap between AdaBoost’s best upper bound and the information-theoretic lower bound is closed up to universal constants.
  • Any boosting procedure that produces a voting classifier with zero empirical γ/2-margin loss inherits the same tight rate.
  • Previous margin bounds that carried an extra ln ln(nγ²/d) factor are now known to be loose for the zero-margin-loss case.
  • The same ghost-sample-plus-Rademacher technique yields tight margin bounds for infinite VC classes whenever the empirical margin loss vanishes.

Where Pith is reading between the lines

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

  • The same rate should hold for any algorithm whose output is a convex combination that achieves positive empirical margin, not only AdaBoost’s particular reweighting schedule.
  • When the weak class is finite the new bound recovers the optimal finite-class margin bounds already known, suggesting the VC argument is tight rather than merely convenient.
  • Modern tree-boosting systems that stop early or regularize margins may still be governed by a similar d/(nγ²) term once their effective margin and effective dimension are measured.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper proves that AdaBoost, run for T ≥ ln(n)/γ² rounds with an empirical γ-weak learner whose hypotheses lie in a class of VC-dimension d, has generalization error Θ(d ln(nγ²/d)/(nγ²) + ln(1/δ)/n). The contribution is the matching upper bound (Theorem 3). It is obtained by combining the classical fact that AdaBoost produces a voting function with zero empirical γ/2-margin loss (Lemma 2, verified in Appendix A) with a new margin-based generalization bound for voting classifiers over VC classes (Theorem 1). Theorem 1 is proved via a ghost-sample argument in which the ghost sample is smaller than usual and consists entirely of nonpositive-margin points; the family of admissible ghost-index sets is shown to have VC-dimension O(d/γ²) by a Rademacher argument after a γ/2 margin shift, after which Sauer’s lemma yields the claimed rate. Tightness follows from the matching Ω lower bound of Høgsgaard–Larsen–Ritzert (2023).

Significance. Closing the remaining logarithmic gap in AdaBoost’s generalization rate is a clean and worthwhile contribution to classical learning theory. Prior upper bounds were suboptimal by up to a (ln ln(nγ²/d))² factor; the new margin bound for voting classifiers when the empirical γ-margin loss is zero extends optimal finite-class results to finite VC-dimension and is of independent interest. The argument is fully written out, elementary once the ghost-sample reduction is set up, and relies only on standard VC/Rademacher tools plus the classical AdaBoost margin analysis. Combined with the cited matching lower bound, the paper settles the generalization rate of AdaBoost (in the stated parameter regime) up to universal constants.

minor comments (6)
  1. [Theorem 1] In the statement of Theorem 1 the quantity d_γ = c d/γ² appears after the bound; it would be clearer to define d_γ before the displayed inequality and to state explicitly that C absorbs the choice of c.
  2. [§5] The proof of Theorem 1 invokes “the standard Rademacher bound for VC-classes (see [42, Theorem 5.6])” with a universal constant c′. A one-line recall of the precise form used (e.g., Rad ≤ √(c′ d/k)) would make the argument self-contained for readers who do not have the lecture notes at hand.
  3. [Lemma 2] Lemma 2 cites [44, pp. 111–113] for the exponential decay of the empirical margin loss; Appendix A then supplies the elementary verification that T ≥ ln(n)/γ² forces the loss to zero. A forward pointer to Appendix A in the lemma statement would help.
  4. [§2] Related Work notes that the previous best upper bound [29] is suboptimal by up to (ln ln(·))². A brief explicit comparison of the leading terms (old vs. new) would make the improvement easier to appreciate.
  5. [Introduction / §5] Typographical: “interresting” → “interesting” (p. 1); “V oting” → “Voting” in the §5 heading; “it’s generalization error” → “its” in the introduction.
  6. [Theorem 3 / Introduction] The range restrictions under which the matching lower bound of [28] applies (γ ≤ c₁, d ≥ c₂ ln(1/γ), etc.) are stated in the introduction but not restated in Theorem 3. A short remark that the Θ claim holds in that regime would avoid any ambiguity.

Circularity Check

1 steps flagged

No significant circularity: upper bound is a self-contained VC/Rademacher argument; only the matching lower bound is cited from overlapping-author prior work.

specific steps
  1. self citation load bearing [Abstract; §1 (pp. 1–2); Theorem 3 discussion]
    "The contribution of this paper is the upper bound; the matching lower bound follows from prior work. ... the tightness of this upper bound is witnessed by the work [28]. More specifically, [28] showed that ... the generalization error of AdaBoost is at least Ω(d ln(nγ²/d)/(nγ²) + ln(1/δ)/n)"

    The combined Θ rate uses a matching lower bound from overlapping-author work [28]. This is minor and not circular for the paper's actual contribution: the upper bound (Theorem 1/3) is proved independently via VC/Rademacher arguments and does not assume or re-derive that lower bound. Flagged only because it is the sole self-citation that participates in the headline Θ claim.

full rationale

The paper's new contribution is the upper bound (Theorems 1 and 3). Its derivation chain is: (i) classical AdaBoost margin analysis (Lemma 2 + Appendix A, from Schapire–Freund) yields zero empirical γ/2-margin loss after T ≥ ln(n)/γ² rounds; (ii) a new margin bound for voting classifiers (Theorem 1) is proved via a ghost-sample argument, a Rademacher bound on the VC-dimension of the family A_S of admissible index sets (k ≤ O(d/γ²)), and Sauer counting to obtain the stated ε. None of these steps defines the target rate in terms of itself, fits parameters to data, or smuggles an ansatz. The Θ claim additionally invokes the matching Ω lower bound from Høgsgaard–Larsen–Ritzert [28] (overlapping authors). That citation is load-bearing only for tightness of the combined rate, not for the upper-bound derivation, which stands independently. This is ordinary self-citation of a prior lower bound and does not make the new proof circular. No fitted inputs, self-definitional identities, or uniqueness-by-author-fiat appear.

Axiom & Free-Parameter Ledger

2 free parameters · 4 axioms · 0 invented entities

The argument rests entirely on classical VC/Rademacher machinery and the textbook AdaBoost margin analysis. Universal constants c,C are existential (chosen large enough for the inequalities) rather than data-fitted. No new physical or statistical entities are postulated. The only domain assumption beyond standard math is the existence of an empirical γ-weak learner on every reweighting of every sample drawn from P.

free parameters (2)
  • universal constant c in d_γ = c d/γ² = existential, ≥4c'
    Chosen large enough (c≥4c') so the Rademacher bound implies VC-dimension of A_S is at most d_γ; not fitted to data.
  • universal constant C in the final O(·) bound = existential
    Absorbs numerical factors (10, ln 2, etc.) appearing in the ε threshold and the exp(·)≤δ calculation; not fitted to data.
axioms (4)
  • standard math Standard Rademacher complexity bound for a VC-class of dimension d: E sup_h (1/k)Σ σ_i y_i h(x_i) ≤ √(c' d/k)
    Invoked in §5 citing Rebeschini lecture notes [42, Thm 5.6]; load-bearing for the VC-dimension of A_S.
  • standard math Sauer’s lemma: a set system of VC-dimension d_γ on N points has at most (eN/d_γ)^{d_γ} sets
    Used in §5 to bound |A_S| and thereby P(E2).
  • domain assumption AdaBoost with empirical γ-weak learner produces ϵ_t ≤ 1/2−γ each round and, after T≥ln(n)/γ² rounds, a normalized voting function with zero empirical γ/2-margin loss
    Lemma 2, taken from Schapire–Freund [44, pp. 111–113] with the zero-loss claim verified in Appendix A.
  • domain assumption There exists an empirical γ-weak learner W that, on every distribution over every sample S∼P^n, returns h∈H with weighted error ≤1/2−γ, and VC(H)=d
    Standing assumption of Theorem 3 and of the whole weak-to-strong framework; without it AdaBoost’s margin guarantee does not hold.

pith-pipeline@v1.2.0-daily-grok45 · 16731 in / 3044 out tokens · 97342 ms · 2026-07-30T19:33:54.901825+00:00 · methodology

0 comments
read the original abstract

In this paper we show that the generalization error of AdaBoost is $\Theta\big(\tfrac{d\ln(n\gamma^{2}/d)}{n\gamma^2}+\tfrac{\ln(1/\delta)}{n}\big)$, where $\gamma$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the class containing the weak hypotheses, $n$ is the sample size, and $\delta$ is the confidence parameter. The contribution of this paper is the upper bound; the matching lower bound follows from prior work. The upper bound proof follows by combining the known fact that AdaBoost outputs a voting classifier whose voting function has zero empirical $\gamma/2$-margin loss with what is, to the best of our knowledge, a new margin-based generalization bound for voting classifiers.

discussion (0)

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

Reference graph

Works this paper leans on

50 extracted references · 3 linked inside Pith

  1. [1]

    The Uniform Hardcore Lemma via Approximate Bregman Projections

    Boaz Barak, Moritz Hardt, and Satyen Kale. “The Uniform Hardcore Lemma via Approximate Bregman Projections”. In:Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1193–1200 (cit. on p. 3)

    2009

  2. [2]

    Boosting the margin: a new explanation for the effectiveness of voting methods

    Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire. “Boosting the margin: a new explanation for the effectiveness of voting methods”. In:The Annals of Statistics26.5 (1998), pp. 1651– 1686 (cit. on p. 3). 7

    1998

  3. [3]

    Agnostic Boosting

    Shai Ben-David, Philip M. Long, and Yishay Mansour. “Agnostic Boosting”. In:Computational Learning Theory, 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19, 2001, Proceedings. Ed. by David P. Helmbold and Robert C. Williams...

    2001

  4. [4]

    Learnability and the Vapnik-Chervonenkis dimension

    Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. “Learnability and the Vapnik-Chervonenkis dimension”. In:J. ACM36.4 (1989), pp. 929–965 (cit. on pp. 1, 5)

    1989

  5. [5]

    Prediction Games and Arcing Algorithms

    Leo Breiman. “Prediction Games and Arcing Algorithms”. In:Neural Computation11.7 (Oct. 1999), pp. 1493–1517.issn: 0899-7667 (cit. on p. 3)

    1999

  6. [6]

    Of Dice and Games: A Theory of Generalized Boosting

    Marco Bressan, Nataly Brukhim, Nicol` o Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, and Maximilian Thiessen. “Of Dice and Games: A Theory of Generalized Boosting”. In: Proceedings of Thirty Eighth Conference on Learning Theory. Ed. by Nika Haghtalab and Ankur Moitra. Vol. 291. Proceedings of Machine Learning Research. PMLR, 30 Jun–04 Jul ...

    2025

  7. [7]

    Online Agnostic Boosting via Regret Minimization

    Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran. “Online Agnostic Boosting via Regret Minimization”. In:Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual. Ed. by Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, a...

    2020

  8. [8]

    Multiclass Boosting: Simple and Intuitive Weak Learning Criteria

    Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran. “Multiclass Boosting: Simple and Intuitive Weak Learning Criteria”. In:Advances in Neural Information Processing Systems. Ed. by A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine. Vol. 36. Curran Associates, Inc., 2023, pp. 1403–1425 (cit. on p. 3)

    2023

  9. [9]

    Boosting With the L2 Loss

    Peter B¨ uhlmann and Bin Yu. “Boosting With the L2 Loss”. In:Journal of the American Statistical Association98.462 (2003), pp. 324–339 (cit. on p. 3)

    2003

  10. [10]

    Efficient, Noise-Tolerant, and Private Learning via Boosting

    Mark Bun, Marco Leandro Carmosino, and Jessica Sorrell. “Efficient, Noise-Tolerant, and Private Learning via Boosting”. In:Proceedings of Thirty Third Conference on Learning Theory. Ed. by Jacob Abernethy and Shivani Agarwal. Vol. 125. Proceedings of Machine Learning Research. PMLR, Sept. 2020, pp. 1031–1077 (cit. on p. 3)

    2020

  11. [11]

    XGBoost: A Scalable Tree Boosting System

    Tianqi Chen and Carlos Guestrin. “XGBoost: A Scalable Tree Boosting System”. In:Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016. Ed. by Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi. ACM, 2016, pp. 785–794 (...

    2016

  12. [12]

    2026 (cit

    Arthur da Cunha, Mikael Møller Høgsgaard, and Andrea Paudice.Sample-Near-Optimal Agnostic Boosting with Improved Running Time. 2026 (cit. on p. 3)

    2026

  13. [13]

    Boosting, Voting Classifiers and Randomized Sample Compression Schemes

    Arthur da Cunha, Kasper Green Larsen, and Martin Ritzert. “Boosting, Voting Classifiers and Randomized Sample Compression Schemes”. In:Proceedings of The 36th International Conference on Algorithmic Learning Theory. Ed. by Gautam Kamath and Po-Ling Loh. Vol. 272. Proceedings of Machine Learning Research. PMLR, 24–27 Feb 2025, pp. 390–404 (cit. on p. 3)

    2025

  14. [14]

    Optimal Parallelization of Boosting

    Arthur da Cunha, Mikael Møller Høgsgaard, and Kasper Green Larsen. “Optimal Parallelization of Boosting”. In:Advances in Neural Information Processing Systems. Ed. by A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang. Vol. 37. Curran Associates, Inc., 2024, pp. 14540–14569 (cit. on p. 3)

    2024

  15. [15]

    Revisiting Agnostic Boosting

    Arthur da Cunha, Mikael Møller Høgsgaard, Andrea Paudice, and Yuxin Sun. “Revisiting Agnostic Boosting”. In:CoRRabs/2503.09384 (2025) (cit. on p. 3)

    arXiv 2025

  16. [16]

    Improving Regressors Using Boosting Techniques

    Harris Drucker. “Improving Regressors Using Boosting Techniques”. In:Proceedings of the 14th International Conference on Machine Learning(Aug. 1997) (cit. on p. 3)

    1997

  17. [17]

    Boosting Methods for Regression

    Nigel Duffy and David Helmbold. “Boosting Methods for Regression”. In:Mach. Learn.47.2–3 (May 2002), pp. 153–200.issn: 0885-6125 (cit. on p. 3)

    2002

  18. [18]

    TabArena: A Living Benchmark for Machine Learning on Tabular Data

    Nick Erickson, Lennart Purucker, et al. “TabArena: A Living Benchmark for Machine Learning on Tabular Data”. In:arXiv preprint arXiv:2506.16791(2025) (cit. on p. 2)

    Pith/arXiv arXiv 2025

  19. [19]

    Distribution-Specific Agnostic Boosting

    Vitaly Feldman. “Distribution-Specific Agnostic Boosting”. In:Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings. Ed. by Andrew Chi-Chih Yao. Tsinghua University Press, 2010, pp. 241–250 (cit. on p. 3). 8

    2010

  20. [20]

    A decision-theoretic generalization of on-line learning and an application to boosting

    Yoav Freund and Robert E. Schapire. “A decision-theoretic generalization of on-line learning and an application to boosting”. In:Computational Learning Theory, Second European Conference, EuroCOLT ’95, Barcelona, Spain, March 13-15, 1995, Proceedings. Ed. by Paul M. B. Vit´ anyi. Vol. 904. Lecture Notes in Computer Science. Springer, 1995, pp. 23–37 (cit....

    1995

  21. [21]

    Greedy function approximation: A gradient boosting machine

    Jerome H. Friedman. “Greedy function approximation: A gradient boosting machine.” In:The Annals of Statistics29.5 (2001), pp. 1189–1232 (cit. on p. 3)

    2001

  22. [22]

    On the doubt about margin explanation of boosting

    Wei Gao and Zhi-Hua Zhou. “On the doubt about margin explanation of boosting”. In:Artificial Intelligence203 (2013), pp. 1–18.issn: 0004-3702 (cit. on p. 3)

    2013

  23. [23]

    Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning

    Dmitry Gavinsky. “Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning”. In: Algorithmic Learning Theory. Ed. by Nicol` o Cesa-Bianchi, Masayuki Numao, and R¨ udiger Reischuk. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 98–112.isbn: 978-3-540-36169-5 (cit. on p. 3)

    2002

  24. [24]

    Sample-Efficient Agnostic Boosting

    Udaya Ghai and Karan Singh. “Sample-Efficient Agnostic Boosting”. In:Advances in Neural Infor- mation Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024. Ed. by Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and...

    2024

  25. [25]

    Sample-Optimal Agnostic Boosting with Unlabeled Data

    Udaya Ghai and Karan Singh. “Sample-Optimal Agnostic Boosting with Unlabeled Data”. In:CoRR abs/2503.04706 (2025) (cit. on p. 3)

    Pith/arXiv arXiv 2025

  26. [26]

    Margins are insufficient for explaining gradient boosting

    Allan Grønlund, Lior Kamma, and Kasper Green Larsen. “Margins are insufficient for explaining gradient boosting”. In:Proceedings of the 34th International Conference on Neural Information Pro- cessing Systems. NIPS ’20. Vancouver, BC, Canada: Curran Associates Inc., 2020.isbn: 9781713829546 (cit. on p. 3)

    2020

  27. [27]

    Margin- based generalization lower bounds for boosted classifiers

    Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, and Jelani Nelson. “Margin- based generalization lower bounds for boosted classifiers”. In:Proceedings of the 33rd International Conference on Neural Information Processing Systems. Red Hook, NY, USA: Curran Associates Inc., 2019 (cit. on p. 3)

    2019

  28. [28]

    AdaBoost is not an Optimal Weak to Strong Learner

    Mikael Møller Høgsgaard, Kasper Green Larsen, and Martin Ritzert. “AdaBoost is not an Optimal Weak to Strong Learner”. In:International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA. Ed. by Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett. Vol. 202. Proceedings of Ma...

    2023

  29. [29]

    Improved Margin Generalization Bounds for Voting Classifiers

    Mikael Høgsgaard Møller and Kasper Green Larsen. “Improved Margin Generalization Bounds for Voting Classifiers”. In:Proceedings of Thirty Eighth Conference on Learning Theory. Ed. by Nika Haghtalab and Ankur Moitra. Vol. 291. Proceedings of Machine Learning Research. PMLR, 2025, pp. 2822–2855 (cit. on p. 3)

    2025

  30. [30]

    Reproducibility in learning

    Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. “Reproducibility in learning”. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2022. Rome, Italy: Association for Computing Machinery, 2022, pp. 818–831.isbn: 9781450392648 (cit. on p. 3)

    2022

  31. [31]

    Potential-Based Agnostic Boosting

    Adam Kalai and Varun Kanade. “Potential-Based Agnostic Boosting”. In:Advances in Neural Infor- mation Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems

  32. [32]

    The Impossibility of Parallelizing Boosting

    Amin Karbasi and Kasper Green Larsen. “The Impossibility of Parallelizing Boosting”. In:Proceedings of The 35th International Conference on Algorithmic Learning Theory. Ed. by Claire Vernade and Daniel Hsu. Vol. 237. Proceedings of Machine Learning Research. PMLR, 25–28 Feb 2024, pp. 635–653 (cit. on p. 3)

    2024

  33. [33]

    LightGBM: A Highly Efficient Gradient Boosting Decision Tree

    Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. “LightGBM: A Highly Efficient Gradient Boosting Decision Tree”. In:Advances in Neural Information Processing Systems. Ed. by I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett. Vol. 30. Curran Associates, Inc., 2017 (...

    2017

  34. [34]

    Cryptographic Limitations on Learning Boolean Formulae and Finite Automata

    Michael J. Kearns and Leslie G. Valiant. “Cryptographic Limitations on Learning Boolean Formulae and Finite Automata”. In:J. ACM41.1 (1994), pp. 67–95 (cit. on p. 1)

    1994

  35. [35]

    Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers

    V. Koltchinskii and D. Panchenko. “Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers”. In:The Annals of Statistics30.1 (2002), pp. 1–50 (cit. on p. 3). 9

    2002

  36. [36]

    Improved Replicable Boosting with Majority-of-Majorities

    Kasper Green Larsen, Markus Engelund Mathiasen, and Clement Svendsen. “Improved Replicable Boosting with Majority-of-Majorities”. In:Proceedings of The 37th International Conference on Algorithmic Learning Theory. Ed. by Matus Telgarsky and Jonathan Ullman. Vol. 313. Proceedings of Machine Learning Research. PMLR, 23–26 Feb 2026, pp. 1–18 (cit. on p. 3)

    2026

  37. [37]

    2025 (cit

    Kasper Green Larsen and Natascha Schalburg.Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets. 2025 (cit. on p. 3)

    2025

  38. [38]

    Algorithms and Hardness Results for Parallel Large Margin Learning

    Philip M. Long and Rocco A. Servedio. “Algorithms and Hardness Results for Parallel Large Margin Learning”. In:Journal of Machine Learning Research14.95 (2013), pp. 3105–3128 (cit. on p. 3)

    2013

  39. [39]

    The Cost of Parallelizing Boosting

    Xin Lyu, Hongxun Wu, and Junzhao Yang. “The Cost of Parallelizing Boosting”. In:Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3140–3155 (cit. on p. 3)

    2024

  40. [40]

    A Theory of Multiclass Boosting

    Indraneel Mukherjee and Robert E. Schapire. “A Theory of Multiclass Boosting”. In:Journal of Machine Learning Research14.14 (2013), pp. 437–497 (cit. on p. 3)

    2013

  41. [41]

    CatBoost: unbiased boosting with categorical features

    Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. “CatBoost: unbiased boosting with categorical features”. In:Proceedings of the 32nd International Conference on Neural Information Processing Systems. NIPS’18. Montr´ eal, Canada: Curran Associates Inc., 2018, pp. 6639–6649 (cit. on p. 2)

    2018

  42. [42]

    Chaining

    Patrick Rebeschini.Lecture Notes in Algorithmic Foundations of Learning: Covering Numbers Bounds for Rademacher Complexity. Chaining. Lecture 5 (Chaining), Department of Statistics, University of Oxford. Version of December 8, 2021. Dec. 2021 (cit. on p. 7)

    2021

  43. [43]

    The Strength of Weak Learnability (Extended Abstract)

    Robert E. Schapire. “The Strength of Weak Learnability (Extended Abstract)”. In:30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989. IEEE Computer Society, 1989, pp. 28–33 (cit. on p. 1)

    1989

  44. [44]

    Schapire and Yoav Freund.Boosting: Foundations and Algorithms

    Robert E. Schapire and Yoav Freund.Boosting: Foundations and Algorithms. The MIT Press, May 2012.isbn: 9780262301183 (cit. on pp. 1, 3–5)

    2012

  45. [45]

    Improved boosting algorithms using confidence-rated pre- dictions

    Robert E. Schapire and Yoram Singer. “Improved boosting algorithms using confidence-rated pre- dictions”. In:Proceedings of the Eleventh Annual Conference on Computational Learning Theory. COLT’ 98. Madison, Wisconsin, USA: Association for Computing Machinery, 1998, pp. 80–91.isbn: 1581130570 (cit. on p. 3)

    1998

  46. [46]

    Smooth Boosting and Learning with Malicious Noise

    Rocco A. Servedio. “Smooth Boosting and Learning with Malicious Noise”. In:Computational Learning Theory. Ed. by David Helmbold and Bob Williamson. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 473–489.isbn: 978-3-540-44581-4 (cit. on p. 3)

    2001

  47. [47]

    Smoothness, Low-Noise and Fast Rates

    Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. “Smoothness, Low-Noise and Fast Rates”. In: CoRRabs/1009.3896 (2010) (cit. on p. 3)

    Pith/arXiv arXiv 2010

  48. [48]

    A Theory of the Learnable

    Leslie G. Valiant. “A Theory of the Learnable”. In:Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA. Ed. by Richard A. DeMillo. ACM, 1984, pp. 436–445 (cit. on pp. 1, 5)

    1984

  49. [49]

    On the uniform convergence of relative frequencies of events to their probabilities

    Vladimir Vapnik and Alexey Chervonenkis. “On the uniform convergence of relative frequencies of events to their probabilities”. English. In:Theory of Probability and its Applications16 (1971), pp. 264–280 (cit. on pp. 1, 5). A Calculations Showing That T≥ln (n)/γ2 Implies Lγ/2 S (g) = 0 To prove the final assertion of Lemma 2, it suffices to show that the...

    1971

  50. [2009]

    Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada. Ed. by Yoshua Bengio, Dale Schuurmans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta. Curran Associates, Inc., 2009, pp. 880–888 (cit. on p. 3)

    2009