# Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 25 Nov 2025.

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

- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [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)
- [Improved Margin Generalization Bounds for Voting Classifiers](https://mlsanity.com/paper/2502.16462/) (2025)
- [Optimal Minimal Margin Maximization with Boosting](https://mlsanity.com/paper/1901.10789/) (2019)
- [The Many Faces of Optimal Weak-to-Strong Learning](https://mlsanity.com/paper/2408.17148/) (2024)
- [Tight Generalization Bounds for Large-Margin Halfspaces](https://mlsanity.com/paper/2502.13692/) (2025)

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

- [A Fine-Grained Understanding of Uniform Convergence for Halfspaces](https://mlsanity.com/paper/2605.06004/) (2026)
- [Tight Generalization Bound for AdaBoost](https://mlsanity.com/paper/2607.26838/) (2026)

## Abstract (arXiv)

We prove the first margin-based generalization bound for voting classifiers, that is asymptotically tight in the tradeoff between the size of the hypothesis set, the margin, the fraction of training points with the given margin, the number of training samples and the failure probability.