Support vector machines get sharper error guarantees for clean data
Sharp margin-based generalization bounds for realizable SVM
Machine Learning
Summary
This work improves the understanding of how well support vector machines (SVMs) perform when they perfectly separate training data with a margin. The authors prove a precise mathematical bound on how often the SVM makes mistakes on new data, based on geometric properties of the training samples. Their approach uses a novel method involving deleting constraints and measuring how well the remaining data can still be separated. This result provides a clearer picture of the reliability of SVM classifiers in ideal conditions.
What this means in practice
- •For machine learning engineers: Use tighter SVM error bounds to better estimate classifier reliability when training with perfectly separable data.
- •For data scientists: Assess how training data geometry influences SVM generalization for cleaner, margin-based classification tasks.
A theory result. No direct application yet.
Authors
Steve Hanneke, Aryeh Kontorovich
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\left( γ_m>0,\quad \Risk(u_m)> \frac{C}{m} \left( K_m+\log\frac1δ \right) \right) \le δ. \] 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^2\norm{u_m}^2=r_m^2/γ_m^2\) on \(\{γ_m>0\}\). The proof is driven by a deterministic deletion problem. Given vectors \(x_1,\ldots,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 \(\norm{u_B}^2\le 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.