# Improved Margin Generalization Bounds for Voting Classifiers

arXiv: https://arxiv.org/abs/2502.16462 · HTML: https://mlsanity.com/paper/2502.16462/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 23 Feb 2025.

## Builds on (most cited first, 8 of 8)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)
- [Margins are Insufficient for Explaining Gradient Boosting](https://mlsanity.com/paper/2011.04998/) (2020)
- [Margin-Based Generalization Lower Bounds for Boosted Classifiers](https://mlsanity.com/paper/1909.12518/) (2019)
- [AdaBoost is not an Optimal Weak to Strong Learner](https://mlsanity.com/paper/2301.11571/) (2023)
- [The Many Faces of Optimal Weak-to-Strong Learning](https://mlsanity.com/paper/2408.17148/) (2024)

## Built on by (most cited first, 4 of 4)

- [Revisiting Agnostic Boosting](https://mlsanity.com/paper/2503.09384/) (2025)
- [Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets](https://mlsanity.com/paper/2511.20407/) (2025)
- [The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity](https://mlsanity.com/paper/2605.29819/) (2026)
- [Tight Generalization Bound for AdaBoost](https://mlsanity.com/paper/2607.26838/) (2026)

## Abstract (arXiv)

In this paper we establish a new margin-based generalization bound for voting classifiers, refining existing results and yielding tighter generalization guarantees for widely used boosting algorithms such as AdaBoost (Freund and Schapire, 1997). Furthermore, the new margin-based generalization bound enables the derivation of an optimal weak-to-strong learner: a Majority-of-3 large-margin classifiers with an expected error matching the theoretical lower bound. This result provides a more natural alternative to the Majority-of-5 algorithm by (Hogsgaard et al., 2024), and matches the Majority-of-3 result by (Aden-Ali et al., 2024) for the realizable prediction model.