Tight Generalization Bounds for Large-Margin Halfspaces

2025/02/19 by Kasper Green Larsen, Larsen, Kasper Green, Natascha Schalburg +1 · 1 voice · 1 citation
Computer Science · Mathematics · #Advanced Topics in Algebra #Approximation Theory and Sequence Spaces #Rings, Modules, and Algebras #cs.LG #math.ST

paper · pdf · doi:10.48550/arxiv.2502.13692

openalex publication_date 2025/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

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

Discussions

• Finally completely tight margin-based generalisation bounds for halfspaces. Very cool proof combining random discretizations with Rademacher complexity in a highly non-trivial way. New arXiv preprint [bsky, 9 points, 0 comments]

Related

• Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
• Efficient Private Algorithms for Learning Large-Margin Halfspaces
• A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
• Replicable Learning of Large-Margin Halfspaces
• The complexity of learning halfspaces using generalized linear methods