Calculating A Finite-Sample Margin Bound

From a Margin Distribution to a Test-Error Bound

A margin bound turns information about a fitted ensemble on the training sample into a statement about its population classification error. The calculation has two distinct parts: the observed fraction of small training margins, and a penalty for the complexity of the class and the uncertainty from having only a finite sample. Keeping these parts separate makes the calculation easier to check—and makes clear why a low training error alone does not guarantee a small test error.

Let $(X,Y)$ be a random pair with $Y\in\{-1,+1\}$, and let $S=((X_1,Y_1),\ldots,(X_n,Y_n))$ be an independent and identically distributed sample from its distribution. A base classifier $h$ takes values in $\{-1,+1\}$. A convex combination of base classifiers is a function $f(x)=\sum_{j=1}^m\alpha_j h_j(x)$, where $\alpha_j\geq 0$ and $\sum_{j=1}^m\alpha_j=1$. Its signed margin on $(x,y)$ is $y f(x)$. A positive margin indicates a correct prediction; a nonpositive margin is a classification error under the convention used here.

Definition: For a margin threshold $\theta>0$, the empirical margin fraction is $\widehat P_S(Yf(X)\leq\theta)=n^{-1}\sum_{i=1}^n\mathbf{1}\{Y_i f(X_i)\leq\theta\}$. The population classification error is $P(Yf(X)\leq0)$. Since every nonpositive margin is at most $\theta$, the empirical margin fraction measures how much of the training sample lies near or on the wrong side of the decision boundary.

The bounds below apply to a fixed base class and hold uniformly over its convex combinations $f$. Thus, a classifier may be selected using the sample and still be covered by the guarantee. The VC version uses the VC dimension $d$ of the base class; the Rademacher version uses its empirical Rademacher complexity on the sample.

VC margin bound: Suppose the base class $\mathcal H$ consists of binary classifiers with VC dimension $d$, $1\leq d\leq n$, and the sample is i.i.d. Then, with probability at least $1-\delta$ over the sample, simultaneously for every convex combination $f$ and every $\theta>0$, $$ P(Yf(X)\leq 0)\leq \widehat P_S(Yf(X)\leq\theta)+\frac{4}{\theta}\sqrt{\frac{2d\log(2en/d)+\log(2/\delta)}{n}}. $$

This is a conservative finite-sample form of a VC margin bound. The displayed constants are part of the version used for the calculations here. If the right-hand side exceeds 1, replacing it by 1 gives the trivial but sharper probability bound.

Rademacher margin bound: Suppose every $h\in\mathcal H$ takes values in $[-1,1]$, the sample is i.i.d., and $0<\delta<1$. Define $\widehat{\mathfrak R}_S(\mathcal H)=E_\sigma[\sup_{h\in\mathcal H}n^{-1}\sum_{i=1}^n\sigma_iY_i h(X_i)]$, where the $\sigma_i$ are independent random signs taking values $-1$ and $+1$ with equal probability. With probability at least $1-\delta$, simultaneously for every convex combination $f$ and every $\theta>0$, $$ P(Yf(X)\leq 0)\leq \widehat P_S(Yf(X)\leq\theta)+\frac{2\widehat{\mathfrak R}_S(\mathcal H)}{\theta}+3\sqrt{\frac{\log(2/\delta)}{2n}}. $$

Both bounds have the same basic structure: empirical mass below the chosen margin threshold, plus a complexity contribution that grows as $\theta$ shrinks, plus a confidence contribution. The VC bound substitutes a dimension-based penalty; the Rademacher bound uses a sample-specific complexity estimate. These are alternative guarantees, not terms to add together.

Worked VC Calculation

Worked Example: A VC-Based Test-Error Bound

Suppose $n=50{,}000$, the base-class VC dimension is $d=5$, and the desired failure probability is $\delta=0.05$. For a fitted ensemble, 6% of the sample has margin at most $\theta=0.4$. Calculate the stated VC margin bound.

First calculate the dimension and confidence quantity: $$ 2d\log(2en/d)+\log(2/\delta) =10\log(2e\cdot 50{,}000/5)+\log(40). $$

Here $2e\cdot 50{,}000/5=20{,}000e\approx54{,}365.6$, so $\log(54{,}365.6)\approx10.9035$, and $\log(40)\approx3.6889$. Therefore the quantity inside the square root is $$ \frac{10(10.9035)+3.6889}{50{,}000} =\frac{112.7239}{50{,}000} \approx0.00225448. $$

Taking the square root gives approximately $0.047481$. The VC complexity contribution is $4/0.4=10$ times this value, or approximately $0.47481$. Adding the empirical margin fraction gives $$ 0.06+0.47481=0.53481. $$

Thus this version of the bound is approximately $0.535$, or at most $53.5\%$ after rounding upward. It is a valid upper bound at the stated confidence level, not a prediction that the actual test error is close to 53.5%. In this example the complexity penalty is large relative to the observed margin fraction, so the guarantee is informative but not especially tight.

Worked Rademacher Calculation

Worked Example: Comparing Four Margin Thresholds

Take $n=5{,}000$, $\delta=0.0125$, and $\widehat{\mathfrak R}_S(\mathcal H)=0.025$. The observed fractions at or below four thresholds are $0.18, 0.14, 0.10,$ and $0.08$, for $\theta=0.15, 0.20, 0.25,$ and $0.30$, respectively. Calculate each Rademacher bound.

The confidence contribution is shared across the four calculations: $$ 3\sqrt{\frac{\log(2/0.0125)}{2(5{,}000)}} =3\sqrt{\frac{\log(160)}{10{,}000}} \approx3\sqrt{0.0005075174} \approx0.0675844. $$

For $\theta=0.15$, the complexity contribution is $2(0.025)/0.15=0.333333$. The bound is $0.18+0.333333+0.0675844=0.5809177$, approximately $0.5809$.

For $\theta=0.20$, the complexity contribution is $0.050/0.20=0.250000$. The bound is $0.14+0.250000+0.0675844=0.4575844$, approximately $0.4576$.

For $\theta=0.25$, the complexity contribution is $0.050/0.25=0.200000$. The bound is $0.10+0.200000+0.0675844=0.3675844$, approximately $0.3676$.

For $\theta=0.30$, the complexity contribution is $0.050/0.30=0.1666667$. The bound is $0.08+0.1666667+0.0675844=0.3142511$, approximately $0.3143$.

Among these four calculations, the largest threshold gives the smallest upper bound. The empirical fraction falls as $\theta$ increases, but the complexity term $2\widehat{\mathfrak R}_S(\mathcal H)/\theta$ falls faster in this particular comparison. This choice is not a general rule: the best threshold depends on the empirical margin distribution.

Why Convex Combinations Use the Base-Class Complexity

In a Rademacher calculation, it is useful to know why the complexity of a convex combination does not require an additional penalty for the number of learners in the combination. On a fixed sample, the Rademacher average is a linear functional of the classifier's values. A linear functional over a convex hull cannot exceed its largest value over the original class.

Result: On any fixed labeled sample, the empirical Rademacher complexity of the convex hull of $\mathcal H$ equals that of $\mathcal H$, when complexity is defined by the supremum of the same linear functional over each class.

To verify this, fix the sample and a realization of the signs. Write $A(h)=n^{-1}\sum_{i=1}^n\sigma_iY_i h(X_i)$. If $f=\sum_j\alpha_jh_j$ is a convex combination, then $$ A(f)=\sum_j\alpha_j A(h_j)\leq\sum_j\alpha_j\sup_{h\in\mathcal H}A(h)=\sup_{h\in\mathcal H}A(h). $$ Taking the supremum over all $f$ in the convex hull gives an upper bound by the supremum over $\mathcal H$. The reverse inequality holds because every $h\in\mathcal H$ is itself a convex combination with one term. The two suprema are therefore equal for each sign realization. Taking expectation over the signs proves the equality of empirical Rademacher complexities. $\square$

This identity explains why the Rademacher bound above uses the base-class complexity even when the fitted classifier is an ensemble. It does not say that every fitted ensemble has the same test error, nor does it remove the empirical margin term or the confidence term.

Choosing a Threshold From Several Candidates

A bound stated for a fixed threshold can be evaluated at a threshold chosen after inspecting the margin distribution only if the probability guarantee covers that choice. The displayed margin bounds hold simultaneously for every $\theta>0$, so their guarantee already covers such a choice. In other settings, or when using a bound guaranteed only at each prespecified threshold, a finite-grid correction is needed.

Result: Suppose a bound holds at each of $K$ prespecified thresholds with failure probability at most $\delta/K$. Then, with probability at least $1-\delta$, all $K$ bounds hold simultaneously, and the smallest of their right-hand sides may be selected after observing the sample.

For each threshold $k$, let $A_k$ be the event that its bound fails. By assumption $P(A_k)\leq\delta/K$. The union bound gives $$ P\left(\bigcup_{k=1}^K A_k\right)\leq\sum_{k=1}^K P(A_k)\leq K(\delta/K)=\delta. $$ Consequently, with probability at least $1-\delta$, none of the $K$ bounds fails. On that event, whichever threshold has the smallest calculated upper bound is also covered. $\square$

Worked Example: Selecting From a Three-Threshold Grid

Suppose $n=2{,}000$, $\widehat{\mathfrak R}_S(\mathcal H)=0.04$, and three thresholds $0.2,0.4,0.6$ have empirical margin fractions $0.10,0.16,0.31$, respectively. We want simultaneous confidence $1-\delta=0.95$ for these three candidate bounds. Allocate $\delta/3$ to each threshold, so each uses $\delta_k=0.05/3$.

The confidence term for each is $$ 3\sqrt{\frac{\log(2/\delta_k)}{2n}} =3\sqrt{\frac{\log(120)}{4{,}000}} \approx3\sqrt{0.00119687} \approx0.10379. $$

At $\theta=0.2$, the complexity contribution is $0.08/0.2=0.4$, giving $0.10+0.4+0.10379=0.60379$. At $\theta=0.4$, it is $0.08/0.4=0.2$, giving $0.16+0.2+0.10379=0.46379$. At $\theta=0.6$, it is $0.08/0.6\approx0.13333$, giving $0.31+0.13333+0.10379\approx0.54712$. The smallest of the three simultaneous bounds is approximately $0.4638$, at threshold $0.4$.

The correction matters: using $\delta=0.05$ separately for all three and then choosing the minimum would not, by itself, give a 95% simultaneous guarantee.

Common Calculation Pitfalls

Mixing up the threshold and the error boundary. The empirical term counts margins at most $\theta$; the target population error counts margins at most zero. The gap is controlled by the complexity penalty.
Dropping the factor of two or the threshold. In the stated Rademacher bound the complexity term is $2\widehat{\mathfrak R}_S(\mathcal H)/\theta$, not $\widehat{\mathfrak R}_S(\mathcal H)$ alone.
Using a confidence level as though it were a failure probability. A 95% guarantee means $\delta=0.05$, and the formula uses $\log(2/\delta)$.
Rounding a component too early. Keep several digits in the confidence term and complexity term, add them, and round only the final result. For example, $3\sqrt{\log(160)/10{,}000}\approx0.0675844$, which rounds to $0.0676$, not $0.0674$.
Calling an upper bound an estimated error. A bound can be conservative. It certifies that the error is no larger than its right-hand side at the stated confidence level; it does not estimate the error as equal to that number.

A reliable calculation therefore starts by fixing the exact bound and its assumptions, records the empirical fraction for each threshold, computes each penalty without premature rounding, and checks whether threshold selection requires a simultaneous confidence adjustment.

Check Your Understanding

Work through these questions using the definitions and bound forms above.

For $n=1{,}000$, an empirical margin fraction of $0.12$, a Rademacher complexity of $0.03$, threshold $\theta=0.25$, and $\delta=0.05$, identify each of the three contributions to the Rademacher bound.
Why does increasing $\theta$ decrease the Rademacher complexity contribution but not necessarily decrease the complete bound?
In the VC bound, what quantities determine the dimension contribution, and why does the bound become uninformative if its right-hand side exceeds 1?
Suppose bounds are evaluated at four prespecified thresholds and one wants simultaneous failure probability at most $0.02$. What failure probability should be assigned to each threshold by the union-bound method?
Explain why the empirical Rademacher complexity of a convex hull equals that of its base class on a fixed sample.