A VC Margin Bound For Boosted Classifiers

Why Margins Need a Complexity Bound

A boosted classifier can combine many weak rules and achieve zero training error. That fact alone says little about its test error: a sufficiently flexible collection of rules can fit a training sample without generalizing. Margins give a more informative summary. A point classified correctly with a large signed margin is less fragile than one classified correctly by a very small amount.

The aim here is a finite-sample guarantee: with high probability over an independent training sample, bound the classifier’s test error by the observed fraction of training margins below a chosen threshold, plus a term controlled by the VC dimension of the weak-rule class. The argument also explains why controlling the weak rules’ complexity matters even when the final ensemble contains many rounds.

The convention counts a zero margin as an error. A positive margin means the vote predicts the label correctly; a larger positive margin indicates a stronger vote in the correct direction. The threshold \(\gamma>0\) is deliberately larger than zero, so the empirical quantity includes low-margin training observations as well as mistakes.

A Finite-Sample VC Margin Bound

We first state a concrete version of the bound. Its constants are conservative, but each term has a transparent origin. Write \(d\geq 1\) for the VC dimension of \(H\), and let \(\delta\in(0,1)\) be the allowed failure probability. For an integer \(M\geq1\), define

When \(V_M<2n\), set

The three contributions beyond the empirical margin fraction are different. The uniform-convergence term \(\varepsilon_{n,M,\delta}\) reflects the complexity of majority votes built from \(M\) weak rules. The exponential term is the cost of approximating an arbitrary weighted vote by such a finite vote. The threshold \(\gamma\) controls both how many observed margins are counted and how difficult that approximation is.

Proof of the Bound

We use two standard counting and concentration facts, and give the details needed for this argument. First, a majority vote of \(M\) rules from \(H\) has a controlled growth function, including when we examine whether its signed margin is below a fixed threshold. On \(m\) labeled points, each of the \(M\) component rules can produce at most \(\Pi_H(m)\) distinct prediction vectors. Once those \(M\) vectors are fixed, the thresholded average vote determines the margin-sublevel pattern. Thus the number of such patterns is at most \(\Pi_H(m)^M\).

By Sauer’s lemma, \(\Pi_H(m)\leq(em/d)^d\) for \(m\geq d\). If \(m\) points are shattered by the thresholded-vote class, then \(2^m\leq(em/d)^{dM}\). This implies that its VC dimension is at most \(V_M\). Indeed, at \(m_0=4dM\log_2(2eM)\), the inequality \(dM\log_2(em_0/d)<m_0\) holds; for \(m\geq m_0\), the gap \(m-dM\log_2(em/d)\) is increasing. No \(m\geq m_0\) can therefore be shattered.

Second, the Vapnik–Chervonenkis uniform-convergence inequality says that for a class of sets with VC dimension at most \(V<2n\), its empirical and population probabilities differ uniformly by at most \(\sqrt{(32/n)[V\log(2en/V)+\log(8/\delta)]}\) with probability at least \(1-\delta\). One standard form of the inequality is \(P(\sup_A|P_n(A)-P(A)|>\epsilon)\leq8\Pi(2n)e^{-n\epsilon^2/32}\) when \(n\epsilon^2\geq2\); Sauer’s lemma bounds \(\Pi(2n)\) by \((2en/V)^V\). Substitution gives the displayed deviation term. Applied to the sets \(\{(x,y):yg(x)\leq\gamma/4\}\) from all equal-weight votes \(g\) of length \(M\), it gives a single event that works for every such \(g\).

To finish the proof, condition on the observed sample and on any convex vote \(f\). Choose a random equal-weight vote \(g\) as in the lemma, and call an input bad if \(|g(x)-f(x)|\geq\gamma/4\). Integrating the lemma over \(X\) gives expected bad probability at most \(2e^{-M\gamma^2/32}\) under \(D\). Averaging over the \(n\) observed inputs gives the same upper bound for the expected empirical bad fraction. Therefore some realization of \(g\) has the sum of these two bad fractions at most \(4e^{-M\gamma^2/32}\).

For that realization, if \(yf(x)\leq0\) and the input is not bad, then \(yg(x)<\gamma/4\). Consequently, \(P(Yf(X)\leq0)\leq P(Yg(X)\leq\gamma/4)+b_D\), where \(b_D\) is the population bad probability. On the uniform-convergence event, the first probability is at most its empirical counterpart plus \(\varepsilon_{n,M,\delta}\). If \(yg(x)\leq\gamma/4\) and the input is not bad, then \(yf(x)<\gamma/2\leq\gamma\). Thus the empirical counterpart is at most the empirical fraction of \(f\)-margins at most \(\gamma\), plus the empirical bad fraction \(b_S\). Combining these inequalities yields the theorem, since \(b_D+b_S\leq4e^{-M\gamma^2/32}\). The uniform-convergence event holds for every \(g\), so this reasoning applies to every \(f\), including one chosen using the training sample. \(\square\)

Worked Examples

How to Interpret the Bound

The theorem separates observed performance from a complexity penalty. If few training margins fall below \(\gamma\), and both additional terms are small, then the test error must also be small with the stated confidence. The dependence on \(d\), rather than directly on the number of boosting rounds \(T\), is important: a long convex vote can still be controlled through a finite approximation whose complexity depends on the weak-rule class and the chosen approximation length.

The length \(M\) creates a tradeoff. A longer approximating vote makes \(4\exp(-M\gamma^2/32)\) smaller, but increases \(V_M\), and hence can increase the VC deviation term. The margin threshold also matters: increasing \(\gamma\) makes the approximation term decay faster, while generally increasing the observed fraction of margins counted. A useful bound requires balancing these quantities rather than optimizing any one of them in isolation.

Common Mistake

• Wrong reasoning: “The boosted classifier makes no training mistakes, so its test error must be small.” Zero training error controls only the observed labels. It gives no distribution-free guarantee without accounting for the complexity of the class from which the classifier was constructed.
• Correction: Check the empirical margin fraction at a positive threshold and add the complexity and approximation terms. A classifier can have zero training error while many of its training margins are tiny, and a high-complexity weak-rule class can make the uniform-convergence term large.