Tight Generalization Bounds for Large-Margin Halfspaces
asymptotically tightclassification algorithmsconvex optimizationempirical risk minimizationfailure probabilitygeneralization boundhigh-dimensional datalarge-margin halfspacesmargin distributionmargin tradeoffsample complexitystatistical learning theorysupport vector machinestheoretical guaranteestraining points
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.