A line that separates two clouds is cheap. A line that separates them with room to spare is rare — and that room is a promise about data it has never seen. Bartlett’s result: what controls generalization is not the ambient dimension d, nor the count of parameters, but the margin γ. The capacity term scales as R²/γ² and does not grow when you pad the space with a thousand irrelevant coordinates. Down the center, data flows: points go in, the max-margin separator is fit, the bound comes out. Blue builds it; red tries to inflate the margin and cheat.
source P. L. Bartlett, The Sample Complexity of Pattern Classification with Neural Networks: the Size of the Weights is More Important than the Size of the Network, IEEE Trans. Inf. Theory 44(2):525–536, 1998 (with SVM margin theory, Vapnik 1995) — stat.berkeley.edu/~bartlett AMBER · paywalled journal, cited by author/title/year. Rendered, not quoted.
A linear classifier is w·x = 0. On separable data infinitely many lines work; the max-margin one pushes the boundary as far from both clouds as it can. Two margins must not be confused:
geometric margin = min |w·x| / ‖w‖ — a real distance, scale-invariant. functional margin = min |w·x| — inflates if you just scale w. The theorem is stated for the geometric one; with normalized weights the geometric margin equals 1/‖w‖.
Capacity is not the parameter count. It is the single number R²/γ² — data radius over margin, squared. Live for the current separator:
| quantity | value |
|---|
Why does an SVM generalize when d > m — more features than examples? The naive count says it must overfit. It does not, because a wide margin is low effective capacity: the VC-style term d+1 is replaced by R²/γ², which never saw d.
The geometric margin of the-duality — the primal gap the dual support vectors carve — is turned here into a generalization guarantee. Each sphere is the next one’s premise: duality gives γ, the-vc-dimension gives the counting it displaces.
The blue team’s live check: the margin the machine reports must be scale-invariant — rescaling w by any k must leave it unchanged. The witness re-fits, scales the weights ×10, and confirms the reported margin holds. If red switches to the functional margin, this is where it turns red.
Two classes in the plane, cleanly separable: positives at first-coordinate +s, negatives at −s, each spread over a second coordinate ±1. The gap s is the geometric margin the max-margin line will find.
Then the space is padded with d−2 irrelevant zero coordinates — noise dimensions carrying no signal. The margin bound’s whole claim is that these change nothing: same radius, same margin, same capacity. Feed both into the panel.
| class | coord 1 | coord 2 | coords 3..d |
|---|---|---|---|
| + | +s | ±1 | 0 (padding) |
| − | −s | ±1 | 0 (padding) |
Scaling w by k must not move the boundary or the geometric margin — it is a real distance. Watch the readout stay fixed while k slides.
Every number is computed live from the fitted separator — the geometric margin, the radius, the capacity R²/γ², the bound. Nothing is looked up.
What the machine proves: the generalization bound scales as R²/(γ²m) — a larger margin gives a smaller bound (exactly proportional to 1/γ²), the max-margin separator is unique, and the bound is dimension-free: padding d from 2 to 200 leaves it identical. The current separator’s bound is above; these invariances are the output.
The blue witness (left) confirms scale-invariance live; the red team (right) tries to inflate the margin and make the bound meaningless.
“Dimension-free” is also conditional: it needs the data to sit in a bounded-radius ball R. Unbounded features re-import dimension through R. The bound frees you from d, not from geometry.
“More features always means more overfitting.” Cut. With d > m an SVM still generalizes — capacity is R²/γ², which never reads d. Padding proves it live.
“The margin is min |w·x|.” Cut. That is the functional margin and it is meaningless alone — scale w and it grows without bound. The theorem uses min |w·x|/‖w‖.
“There can be several best separators.” Kept, corrected. Many separators exist; the max-margin one is unique on separable data — the panel maximizes a strictly concave margin at one direction.
The red team’s move: report the functional margin instead of the geometric one — drop the /‖w‖ normalization. Now scaling weights ×10 “inflates” the margin tenfold, the capacity R²/γ² shrinks toward zero, and the bound looks arbitrarily good for free. The blue witness (window 7) is watching.
Switch to the un-normalized margin and the reported value stops being a distance — the witness rescales w ×10, sees the margin change, disagrees, and turns red. The attack is real and it is caught.