Margin theory explains why classification can generalize well even when the classifier class is large: confident correct predictions are less sensitive to small perturbations.
Functional and geometric margins
For linear classifiers, the same separating rule can be rescaled, so the meaningful quantity is normalized margin.
Definition. For labels \(Y\in\{-1,1\}\) and score \(f\), the functional margin is \(Yf(X)\). For a linear score \(f_w(x)=\langle w,x\rangle+b\), the geometric margin of \((x,y)\) is \[ \frac{y(\langle w,x\rangle+b)}{\|w\|_2}. \]
Remark. The sign of the margin determines correctness; its magnitude measures confidence. Large-margin methods control the norm of the scoring function while forcing margins to be positive.
Margin losses
Margin losses upper bound zero-one error and are easier to optimize.
Definition. A margin loss has the form \(\phi(yf(x))\), where \(\phi:\mathbb R\to[0,\infty)\). Common choices include the hinge loss \((1-u)_+\), logistic loss \(\log(1+e^{-u})\), and exponential loss \(e^{-u}\).
Proposition. If \(\phi(u)\ge \mathbf 1\{u\le0\}\), then \[ P(Yf(X)\le0)\le P\phi(Yf(X)). \]
Proof. The pointwise inequality \(\mathbf 1\{Yf(X)\le0\}\le \phi(Yf(X))\) holds for every observation. Taking expectations gives the result.
Margin bounds
Generalization can be controlled by the complexity of the real-valued score class and the inverse margin.
Theorem. Let \(\mathcal F\) be a class of scores bounded by \(B\). With probability at least \(1-\delta\), for every \(f\in\mathcal F\) and every \(\gamma>0\), \[ P(Yf(X)\le0) \le P_n(Yf(X)\le\gamma) +\frac{2}{\gamma}\widehat{\mathfrak R}_n(\mathcal F_Y) +3\sqrt{\frac{\log(2/\delta)}{2n}}, \] where \(\mathcal F_Y=\{(x,y)\mapsto yf(x):f\in\mathcal F\}\).
Proof. Upper bound the zero-one loss by the ramp loss that equals \(1\) on \((-\infty,0]\), equals \(0\) on \([\gamma,\infty)\), and is \(1/\gamma\)-Lipschitz. Apply the Rademacher generalization bound to this loss class and use contraction to obtain the complexity term. The empirical ramp loss is bounded by \(P_n(Yf(X)\le\gamma)\).
Low-noise fast rates
Margins in the distribution can improve rates beyond the slow \(n^{-1/2}\) scale.
Definition. A low-noise or margin condition controls the mass near the decision boundary, for example \[ P_X(|\eta(X)-1/2|\le t)\le Ct^\alpha. \]
Remark. When little mass lies near the boundary, disagreement with the Bayes classifier has excess risk comparable to a stronger distance. This curvature is what enables fast-rate classification bounds.
Two distinct meanings of margin
The word margin is used for two mathematically different objects. The geometric margin \(Yf(X)/\|f\|\) is a property of a fitted score and its normed function class. The distributional margin \(|2\eta(X)-1|\) is a property of the data-generating law and measures how decisively the Bayes action is determined. Large-margin generalization bounds use the first; low-noise fast rates use the second.
Distance to a separating hyperplane
Proposition. For the affine hyperplane \(H=\{z:w^\top z+b=0\}\) with \(w\ne0\), the signed Euclidean distance from \(x\) to \(H\) is \[ \frac{w^\top x+b}{\|w\|_2}. \]
Proof. The closest point must lie on the normal line \(x-tw\). Solving \(w^\top(x-tw)+b=0\) gives \(t=(w^\top x+b)/\|w\|_2^2\). The signed length of the displacement along the unit normal \(w/\|w\|_2\) is the displayed ratio.
Scale-sensitive margin classes
Definition. A real-valued class \(\mathcal F\) \(\gamma\)-shatters \(x_1,\ldots,x_m\) if there are thresholds \(r_i\) such that for every \(s\in\{-1,1\}^m\), some \(f\in\mathcal F\) satisfies \[ s_i\{f(x_i)-r_i\}\ge\gamma,\qquad i=1,\ldots,m. \] The largest such \(m\) is the fat-shattering dimension \(\operatorname{fat}_\gamma(\mathcal F)\).
Theorem. Let \(\mathcal F=\{x\mapsto w^\top x:\|w\|_2\le B\}\) on \(\{x:\|x\|_2\le R\}\). Then \[ \operatorname{fat}_\gamma(\mathcal F) \le \min\!\left\{p,\left\lfloor\frac{B^2R^2}{\gamma^2}\right\rfloor\right\} \] up to an absolute constant when affine offsets are included.
Proof outline. If \(m\) points are \(\gamma\)-shattered, average the inequalities over independent random signs and choose the realizing \(w_s\). Duality gives \[ m\gamma\le \mathbb E_s\sup_{\|w\|\le B}\sum_{i=1}^m s_iw^\top x_i =B\,\mathbb E_s\Big\|\sum_i s_ix_i\Big\|_2 \le BR\sqrt m. \] Hence \(m\le B^2R^2/\gamma^2\). Pseudo-dimension gives the ambient-dimensional bound.
A norm-margin sample bound
Corollary. If \(\|X\|_2\le R\), then with probability at least \(1-\delta\), every \(w\) with \(\|w\|_2\le B\) satisfies \[ P(Yw^\top X\le0) \le P_n(Yw^\top X\le\gamma) +\frac{2BR}{\gamma\sqrt n} +3\sqrt{\frac{\log(2/\delta)}{2n}}. \]
Proof. Apply the preceding ramp-loss bound and the Rademacher estimate \(\widehat{\mathfrak R}_n(\mathcal F)\le B\{\sum_i\|X_i\|^2\}^{1/2}/n\le BR/\sqrt n\).
The bound is invariant under simultaneous rescaling of \(w\) and \(\gamma\), because only \(B/\gamma\) matters. It therefore measures normalized geometric separation rather than an arbitrary functional-margin scale.
Tsybakov and Bernstein conditions
Theorem. Let \(g^*=\mathbf1\{\eta\ge1/2\}\), let \(d(g,g^*)=P_X(g\ne g^*)\), and suppose \[ P_X(|2\eta(X)-1|\le t)\le Ct^\alpha. \] Then \[ d(g,g^*)\le C'\{R(g)-R(g^*)\}^{\alpha/(1+\alpha)} \] and the excess loss \(Z_g=\mathbf1\{g(X)\ne Y\}-\mathbf1\{g^*(X)\ne Y\}\) obeys \[ \mathbb EZ_g^2=d(g,g^*) \le C'(\mathbb EZ_g)^{\alpha/(1+\alpha)}. \]
Proof. For every \(t>0\), \[ d(g,g^*)\le P(|2\eta-1|\le t) +P(g\ne g^*,|2\eta-1|>t) \le Ct^\alpha+\frac{R(g)-R(g^*)}{t}. \] Balance the terms with \(t\asymp\{R(g)-R(g^*)\}^{1/(1+\alpha)}\). Since \(Z_g^2=\mathbf1\{g\ne g^*\}\), the variance relation follows.
Massart's bounded-noise regime
Corollary. If \(|2\eta(X)-1|\ge h>0\) almost surely, then \[ R(g)-R(g^*)\ge h\,P_X(g\ne g^*), \qquad \operatorname{Var}(Z_g)\le h^{-1}\mathbb EZ_g. \] This linear Bernstein condition can yield excess-risk rates of order \(d/n\) for VC classes, rather than the generic \(\sqrt{d/n}\) scale.
Margins under adversarial perturbation
Proposition. Let \(f_w(x)=w^\top x+b\), and let perturbations satisfy \(\|\Delta\|\le\rho\) for a norm with dual \(\|\cdot\|_*\). Then \[ \inf_{\|\Delta\|\le\rho}y f_w(x+\Delta) =y f_w(x)-\rho\|w\|_*. \] The classification is robust to every such perturbation exactly when its functional margin exceeds \(\rho\|w\|_*\).
Proof. Hölder's inequality gives \(yw^\top\Delta\ge-\|w\|_*\|\Delta\|\ge-\rho\|w\|_*\). Equality is attained by a dual-norm maximizer in finite dimensions.
This identity connects robust classification to norm regularization: the perturbation geometry chooses the dual norm appearing in the robust margin.