Tight Generalization Bounds for Large-Margin Halfspaces

Abstract

We prove the first generalization bound for large-margin halfspaces that is asymptotically tight in the tradeoff between the margin, the fraction of training points with the given margin, the failure probability and the number of training points.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Larsen and Schalburg. "Tight Generalization Bounds for Large-Margin Halfspaces." Advances in Neural Information Processing Systems, 2025.

Markdown

[Larsen and Schalburg. "Tight Generalization Bounds for Large-Margin Halfspaces." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/larsen2025neurips-tight/)

BibTeX

@inproceedings{larsen2025neurips-tight,
  title     = {{Tight Generalization Bounds for Large-Margin Halfspaces}},
  author    = {Larsen, Kasper Green and Schalburg, Natascha},
  booktitle = {Advances in Neural Information Processing Systems},
  year      = {2025},
  url       = {https://mlanthology.org/neurips/2025/larsen2025neurips-tight/}
}