Tight Generalization Bounds for Large-Margin Halfspaces

TL;DR

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…

Opening excerpt from the authors’ abstract. source