Rademacher Margin Bounds For Convex Combinations

Why Bound Margins With Rademacher Complexity?

A classifier formed by boosting is often a convex combination of base rules. A margin bound relates its population classification error to the observed fraction of small-margin examples, plus a term measuring the class's capacity to fit random signs. This tutorial develops that term directly: for a linear supremum, convex combinations do not increase Rademacher complexity beyond that of the base class.

The bound complements a VC margin bound. A VC-dimension argument summarizes a class through its growth on finite samples; a Rademacher argument measures signed correlations on sampled observations. Neither term is automatically smaller in every problem. The distinction is useful because the Rademacher calculation can preserve information about the actual base rules and the sample.

Setup and Definitions

Let $(X,Y)$ be a random pair with $Y\in\{-1,+1\}$, and let $(X_i,Y_i)_{i=1}^n$ be an independent sample from its distribution. A base rule $h$ is a measurable function from the input space to $[-1,1]$. The class $\mathcal H$ consists of such rules. Its convex hull consists of all finite mixtures $f=\sum_{j=1}^m\alpha_jh_j$, where $h_j\in\mathcal H$, $\alpha_j\geq0$, and $\sum_j\alpha_j=1$. In particular, every $f\in\operatorname{conv}(\mathcal H)$ also takes values in $[-1,1]$.

Definition: The signed margin of $f$ at $(x,y)$ is $yf(x)$. For $\gamma>0$, define the ramp loss $$ \phi_\gamma(u)= \begin{cases} 1, & u\leq 0,\\ 1-u/\gamma, & 0<u<\gamma,\\ 0, & u\geq\gamma. \end{cases} $$ It satisfies $1\{u\leq0\}\leq\phi_\gamma(u)\leq1\{u\leq\gamma\}$, takes values in $[0,1]$, and is $1/\gamma$-Lipschitz.

For a fixed sample $S=((x_i,y_i))_{i=1}^n$, let $\varepsilon_1,\ldots,\varepsilon_n$ be independent random signs, each equally likely to be $+1$ or $-1$. We use a one-sided empirical Rademacher complexity, with the zero function added so the supremum is nonnegative:

\widehat{\mathfrak R}_S(\mathcal H) = E_\varepsilon\left[ \sup_{h\in\mathcal H\cup\{0\}} \frac{1}{n}\sum_{i=1}^n\varepsilon_i y_i h(x_i) \right], \qquad \mathfrak R_n(\mathcal H)=E_S[\widehat{\mathfrak R}_S(\mathcal H)].

The zero function in this definition is only a device for the supremum; it need not be a base rule or a classifier. The population complexity averages the empirical quantity over a fresh sample. We assume $\mathcal H$ is countable and measurable, or that it has a countable pointwise-dense subclass with the same supremum. These conditions ensure the suprema used below are measurable.

Worked Example: Convexification Leaves a Linear Supremum Unchanged

On a sample of two observations, suppose two base rules have vectors of signed outputs $ (y_ih_1(x_i))_{i=1}^2=(1,1)$ and $ (y_ih_2(x_i))_{i=1}^2=(1,-1)$. For each sign vector, calculate the supremum over the two rules, including zero.

For $(\varepsilon_1,\varepsilon_2)=(+1,+1)$, the two unscaled sums are $2$ and $0$, so the maximum including zero is $2$. For $(+1,-1)$, they are $0$ and $2$, giving $2$. For $(-1,+1)$, they are $0$ and $-2$, giving $0$. For $(-1,-1)$, they are $-2$ and $0$, also giving $0$. Thus the average maximum is $(2+2+0+0)/4=1$; dividing by $n=2$, the empirical complexity is $1/2$.

A convex combination has signed-output vector $(1,\,2\alpha-1)$, where $0\leq\alpha\leq1$. A linear function of $\alpha$ has supremum over this interval at an endpoint, unless it is constant. Consequently, for each sign vector the supremum is the same as for the two base rules. The convex hull has the same empirical complexity, $1/2$.

Two Facts Behind the Bound

First, a linear functional over a convex hull has the same supremum as over its generating class. Second, a uniform-deviation inequality controls population ramp loss by empirical ramp loss and Rademacher complexity. The next results state and justify these facts, including the passage from a countable class to finite mixtures.

Proposition: For any fixed sample and signs, $$ \sup_{f\in\operatorname{conv}(\mathcal H)\cup\{0\}} \sum_{i=1}^n\varepsilon_i y_i f(x_i) = \sup_{h\in\mathcal H\cup\{0\}} \sum_{i=1}^n\varepsilon_i y_i h(x_i). $$ Therefore $\widehat{\mathfrak R}_S(\operatorname{conv}(\mathcal H))=\widehat{\mathfrak R}_S(\mathcal H)$, when both complexities use this signed-output convention.

Proof. For any finite mixture $f=\sum_j\alpha_jh_j$, linearity gives $\sum_i\varepsilon_i y_i f(x_i)=\sum_j\alpha_j\sum_i\varepsilon_i y_i h_j(x_i)$. This weighted average is at most $\sup_{h\in\mathcal H}\sum_i\varepsilon_i y_i h(x_i)$. The zero option is present on both sides. Conversely, every $h\in\mathcal H$ is itself a convex combination with one term, so the left supremum is at least the right one. The suprema are equal for each sign vector; averaging and dividing by $n$ proves the complexity equality. $\square$

Here is the uniform-deviation step in the one-sided form needed. For a countable measurable class $\mathcal G$ of functions taking values in $[0,1]$, write $Pg=E[g(X,Y)]$ and $P_ng=n^{-1}\sum_i g(X_i,Y_i)$. Define $\mathfrak R_n(\mathcal G)=E_{S,\varepsilon}\sup_{g\in\mathcal G\cup\{0\}}n^{-1}\sum_i\varepsilon_i g(X_i,Y_i)$.

Uniform-deviation result: With probability at least $1-\delta$, for every $g\in\mathcal G$, $$ Pg\leq P_ng+2\mathfrak R_n(\mathcal G)+ \sqrt{\frac{\log(1/\delta)}{2n}}. $$

Proof. Let $A(S)=\sup_{g\in\mathcal G}(Pg-P_ng)$. Introduce an independent sample $S'$ of size $n$. Conditional on $S$, $Pg=E_{S'}P'_ng$, so taking a supremum after this expectation can only be smaller than taking the expectation of the supremum: $E_S A(S)\leq E_{S,S'}\sup_g(P'_ng-P_ng)$. Each pair $(Z_i,Z'_i)$, where $Z_i=(X_i,Y_i)$, has a distribution unchanged by swapping its entries. Introduce independent signs to perform these swaps. For every realization, the supremum of the signed differences is at most the sum of the two separate suprema over $g$, one involving $S'$ and one involving $S$. Their expectations are equal by identical sampling and sign symmetry. Thus $E A(S)\leq2\mathfrak R_n(\mathcal G)$.

Changing one observation in $S$ changes $A(S)$ by at most $1/n$, since every $P_ng$ changes by at most $1/n$, uniformly in $g$. McDiarmid's bounded-differences inequality therefore gives $P\{A(S)>EA(S)+t\}\leq\exp(-2nt^2)$. Taking $t=\sqrt{\log(1/\delta)/(2n)}$ and combining with the expectation bound proves the result. $\square$

Ramp-Loss Contraction and the Margin Bound

The ramp loss is not zero at zero: $\phi_\gamma(0)=1$. In applying contraction, subtract this constant first. For each sign vector, the added term $\phi_\gamma(0)\sum_i\varepsilon_i$ is common to every function, and its expectation is zero. The function $u\mapsto\phi_\gamma(u)-\phi_\gamma(0)$ vanishes at zero and is $1/\gamma$-Lipschitz.

The Rademacher contraction inequality says that if a set of vectors $T\subseteq\mathbb R^n$ contains zero and $\psi(0)=0$ is $L$-Lipschitz, then $E_\varepsilon\sup_{t\in T}\sum_i\varepsilon_i\psi(t_i)\leq L E_\varepsilon\sup_{t\in T}\sum_i\varepsilon_i t_i$. For completeness, the one-coordinate argument compares the two possible signs: conditional on all other signs, the average of the two suprema with values $\psi(t_i)$ is bounded by the corresponding average with $Lt_i$. Indeed, for any two candidate vectors $t,s$, the relevant difference is at most $|\psi(t_i)-\psi(s_i)|\leq L|t_i-s_i|$; the two choices of signs on the linear side include both orientations of this difference. Replacing coordinates one at a time proves the stated inequality. Applying it to the sample vectors $(y_if(x_i))_{i=1}^n$ yields $\mathfrak R_n(\{\phi_\gamma(yf(x)):f\in\operatorname{conv}(\mathcal H)\})\leq\mathfrak R_n(\mathcal H)/\gamma$.

Margin-bound theorem: Suppose $Y\in\{-1,+1\}$, all $h\in\mathcal H$ are measurable and take values in $[-1,1]$, and $\mathcal H$ is countable or satisfies the separability condition stated above. For every $\gamma>0$ and $0<\delta<1$, with probability at least $1-\delta$, simultaneously for all finite mixtures $f\in\operatorname{conv}(\mathcal H)$, $$ P\{Yf(X)\leq0\} \leq \frac{1}{n}\sum_{i=1}^n1\{Y_if(X_i)\leq\gamma\} +\frac{2}{\gamma}\mathfrak R_n(\mathcal H) +\sqrt{\frac{\log(1/\delta)}{2n}}. $$

Proof. Apply the uniform-deviation result to the class $g_f(x,y)=\phi_\gamma(yf(x))$. For every $f$, the indicator of classification error is at most $g_f$, so $P\{Yf(X)\leq0\}\leq Pg_f$. Also, $g_f(X_i,Y_i)\leq1\{Y_if(X_i)\leq\gamma\}$, giving the empirical-margin term in the theorem. The contraction argument bounds the loss-class complexity by $\mathfrak R_n(\mathcal H)/\gamma$, and the deviation result multiplies that complexity by two. Combining these inequalities proves the claim.

If $\mathcal H$ is uncountable but has a countable pointwise-dense subclass, apply the argument first to rational-weight finite mixtures of that subclass. There are only countably many such mixtures, so the uniform event holds simultaneously for them. Any finite mixture can be approximated pointwise by such mixtures: approximate its finitely many component rules pointwise from the dense subclass and its weights by rational simplex weights. The ramp loss is continuous and bounded, so dominated convergence gives convergence of its population expectations; its empirical averages converge as well. The signed suprema have the same separable interpretation. Passing to the limit extends the bound to every finite mixture. $\square$

Worked Example: Absolute Complexity and a Convex Hull

Consider three observations with two base-rule output vectors $h_1=(1,1,1)$ and $h_2=(1,-1,1)$, and take all labels to be $+1$. For the absolute empirical Rademacher complexity, compute the maximum absolute signed sum over the two rules for each of the eight sign vectors.

The sums are $A=\varepsilon_1+\varepsilon_2+\varepsilon_3$ and $B=\varepsilon_1-\varepsilon_2+\varepsilon_3$. If $\varepsilon_1\neq\varepsilon_3$, then $\varepsilon_1+\varepsilon_3=0$, and $|A|=|B|=1$; this occurs for four sign vectors. If $\varepsilon_1=\varepsilon_3$, their sum is $2$ or $-2$; one of $|A|$ and $|B|$ is $3$, and the other is $1$. This also occurs for four sign vectors. Thus the maximum absolute sum is $1$ four times and $3$ four times. Its average is $(4\cdot1+4\cdot3)/8=2$, so after dividing by $n=3$, the absolute complexity is $2/3$.

For a convex combination, the signed sum is a weighted average of $A$ and $B$, whose absolute value cannot exceed $\max(|A|,|B|)$. Since either endpoint is available, the supremum of the absolute value is exactly the same. The convex hull's absolute complexity is also $2/3$. This illustrates the same endpoint principle, while the theorem above uses the one-sided convention with zero included.

Worked Example: Evaluating the Terms in a Small Margin Bound

Let $n=4$, let $\mathcal H$ contain only the constant rule $h(x)=1$, and let the labels in the observed sample be $(+1,+1,+1,-1)$. Take $f=h$ and $\gamma=1/2$. Three signed margins are $1$ and one is $-1$, so the empirical fraction with margin at most $\gamma$ is $1/4$.

For this singleton class the population complexity is the expectation over four independent signs of $\max(0,(\varepsilon_1+\varepsilon_2+\varepsilon_3+\varepsilon_4)/4)$. The sum is $4$ once, $2$ four times, $0$ six times, $-2$ four times, and $-4$ once. Its positive part has expectation $(4+4\cdot2)/16=12/16=3/4$, so $\mathfrak R_4(\mathcal H)=(3/4)/4=3/16$. The complexity contribution is $2\mathfrak R_4(\mathcal H)/\gamma=2(3/16)/(1/2)=3/4$.

For $\delta=0.05$, the confidence contribution is $\sqrt{\log(20)/8}$, approximately $0.612$. The right side of the theorem is therefore $1/4+3/4+0.612=1.612$. Since a probability is at most one, this bound is valid but uninformative for this tiny sample. The calculation makes clear that the theorem's terms can be evaluated correctly even when the resulting guarantee is loose.

How This Differs From a VC Margin Bound

Feature	Rademacher margin bound	VC margin bound
Complexity input	Expected supremum of signed outputs on a sample	Growth-function or VC-dimension control
Convex combinations	The linear signed supremum equals that of the base class	Typically controlled through a VC-style class-size argument
Sample sensitivity	Can reflect the base rules' signed behavior on sampled points	Summarizes combinatorial richness through dimension

The convex-hull equality does not say that a convex hull is always statistically harmless. It says that this particular linear Rademacher supremum does not increase under finite convexification. The margin scale still matters through $1/\gamma$, and a highly variable or rich base class can have a large complexity. Likewise, the VC and Rademacher approaches use different summaries and neither dominates without further assumptions.

Common Mistakes

Counting sign vectors by inspection. Enumerate the sign cases or use the algebraic form of the sums. In the three-observation example above, the two cases each occur four times, yielding average maximum $2$, not $1.5$.
Assuming a continuum of mixtures is automatically covered by a countable-class proof. Use a countable dense subclass and pass to the limit using continuity of the ramp loss and bounded convergence, or establish the required separability directly.
Confusing the complexity conventions. The theorem uses a one-sided supremum with zero included. An absolute empirical complexity is a different definition and should not be substituted without checking the associated inequality and constants.
Calling the Rademacher term a VC dimension. One is a signed-supremum quantity; the other is a combinatorial dimension. Their roles in a bound are related, but they are not interchangeable.

Key takeaway: For bounded binary base rules, the ramp-loss margin bound has an empirical small-margin term, a confidence term, and a complexity term $2\mathfrak R_n(\mathcal H)/\gamma$. The convex hull does not enlarge the underlying linear Rademacher supremum, provided the class and measurability conditions are handled correctly.

Check Your Understanding

Work through these questions using the definitions and proof above.

Why must the zero function be included in the one-sided Rademacher supremum used here?
For a finite mixture $f=\sum_j\alpha_jh_j$, explain why its signed sum cannot exceed the largest signed sum of its component rules.
What two pointwise inequalities connect the ramp loss to classification error and to the empirical margin fraction?
Why is it necessary to justify the extension from rational-weight mixtures to all finite mixtures?
Name one conceptual difference between the Rademacher complexity term and the VC-dimension term.