Sharp margin-based generalization bounds for realizable SVM
Abstract
Let the exact homogeneous hard-margin support vector machine be trained on m independent observations from a Borel probability law on a real Hilbert space. We prove that, with score zero counted as an error, there is a universal numerical constant C such that Pp( γm>0, Risk(um)> C/m ( Km+log1/δ ) ) ≤ δ. Here γm is the empirical homogeneous margin, um is the exact minimum-norm unit-margin separator, rm is the largest training radius, and Km:=rm2normum2=rm2/γm2 on {γm>0}. The proof is driven by a deterministic deletion problem. Given vectors x1,…,xn in the unit ball, delete a set B of constraints and let uB be the closest point to the origin that satisfies every retained unit-margin constraint. Suppose that normuB2≤ k and that every deleted vector has nonpositive score under uB. We prove that a family of such deletion sets of cardinality q has size at most exp(8k+2q). The conceptual step is an exact identity obtained from the KKT representation of uB. For a random deletion set, the identity converts the mean squared spread of the separators into a weighted sum of score deficits. It therefore forces a coordinate whose deletion status separates the two conditional means by a quantitatively large amount. Revealing that coordinate decreases the conditional separator variance enough to control the binary entropy of the split. An entropy induction gives the deletion count, and an exact factorial ghost-sample identity converts that count into the stated high-probability SVM bound.
Related
- PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
- Disconnected graphs and extremal bounds for realizable distance orders
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
- How Many Independent Samples Does a Satellite Image Contain? Generalization Bounds for Spatially Dependent Data
- Tight Generalization Bounds for Noiseless Inverse Optimization
BibTeX
@misc{hanneke2026sharp,
title = {{Sharp margin-based generalization bounds for realizable SVM}},
author = {Steve Hanneke and Aryeh Kontorovich},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17845},
eprint = {2609.17845},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17845},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp margin-based generalization bounds for realizable SVM
AU - Steve Hanneke
AU - Aryeh Kontorovich
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17845
UR - https://arxiv.org/abs/2609.17845
AB - Let the exact homogeneous hard-margin support vector machine be trained on m independent observations from a Borel probability law on a real Hilbert space. We prove that, with score zero counted as an error, there is a universal numerical constant C such that Pp( γ_m>0, Risk(u_m)> C/m ( K_m+log1/δ ) ) ≤ δ. Here γ_m is the empirical homogeneous margin, u_m is the exact minimum-norm unit-margin separator, r_m is the largest training radius, and K_m:=r_m^2normu_m^2=r_m^2/γ_m^2 on {γ_m>0}. The proof is driven by a deterministic deletion problem. Given vectors x_1,…,x_n in the unit ball, delete a set B of constraints and let u_B be the closest point to the origin that satisfies every retained unit-margin constraint. Suppose that normu_B^2≤ k and that every deleted vector has nonpositive score under u_B. We prove that a family of such deletion sets of cardinality q has size at most exp(8k+2q). The conceptual step is an exact identity obtained from the KKT representation of u_B. For a random deletion set, the identity converts the mean squared spread of the separators into a weighted sum of score deficits. It therefore forces a coordinate whose deletion status separates the two conditional means by a quantitatively large amount. Revealing that coordinate decreases the conditional separator variance enough to control the binary entropy of the split. An entropy induction gives the deletion count, and an exact factorial ghost-sample identity converts that count into the stated high-probability SVM bound.
ER -