Base-Class Complexity In Boosting Margin Bounds

Margins, Base Rules, and Capacity

A boosting procedure builds a predictor by combining weak rules. Two quantities might therefore seem to control how well the final classifier generalizes: the richness of the rules it can select, and the number of rounds used to combine them. Margin bounds clarify that these are related but distinct sources of complexity. A bound obtained by counting candidate ensembles can charge for every round; a bound based on the convex hull of the weak-rule class can instead depend on the base class without an explicit round-count penalty.

We consider binary classification. Let $X$ be an input, $Y\in\{-1,+1\}$ its label, and let each base rule $h$ map inputs to $\{-1,+1\}$. A normalized weighted vote has score $f(x)=\sum_{t=1}^{T}\alpha_t h_t(x)$, where $\alpha_t\geq 0$ and $\sum_{t=1}^{T}\alpha_t=1$. Its signed margin at $(x,y)$ is $yf(x)$: positive values indicate a correct prediction, while values near zero indicate a prediction with little margin. We use $P$ for the population distribution and $P_n$ for the empirical distribution of $n$ independent observations.

Definition: For a score function $f$, the margin at $(x,y)$ is $yf(x)$. For a threshold $\theta>0$, its population margin probability is $P(Yf(X)\leq\theta)$, and its empirical margin probability is $P_n(Yf(X)\leq\theta)=n^{-1}\sum_{i=1}^{n}1\{Y_i f(X_i)\leq\theta\}$. The classification error is $P(Yf(X)\leq 0)$, with ties counted as errors.

Since $\{Yf(X)\leq 0\}\subseteq\{Yf(X)\leq\theta\}$ when $\theta>0$, a small population margin probability at a positive threshold controls classification error. The challenge is to compare that population probability with its empirical counterpart while accounting for how many candidate predictors are being considered.

A Bound for a Finite Set of Candidate Ensembles

The first result makes the counting cost explicit. It applies to any finite, fixed set of score functions, not only to boosted predictors. The candidates must be specified independently of the sample; after observing data, one may select any candidate from the set because the result holds simultaneously for all of them.

Theorem: Let $\mathcal A$ be a fixed set of $K\geq1$ score functions, and let $(X_i,Y_i)_{i=1}^{n}$ be independent observations from $P$. For any fixed $\theta>0$ and $0<\delta<1$, with probability at least $1-\delta$, every $f\in\mathcal A$ satisfies $$ P(Yf(X)\leq\theta)\leq P_n(Yf(X)\leq\theta)+\sqrt{\frac{\log(K/\delta)}{2n}}. $$

Proof. Fix one $f\in\mathcal A$, and define $Z_i=1\{Y_i f(X_i)\leq\theta\}$. These are independent variables in $[0,1]$ with common expectation $P(Yf(X)\leq\theta)$. Hoeffding's inequality gives, for any $\varepsilon>0$, $$ P\left(P(Yf(X)\leq\theta)-P_n(Yf(X)\leq\theta)>\varepsilon\right)\leq \exp(-2n\varepsilon^2). $$ By the union bound, the probability that this deviation exceeds $\varepsilon$ for at least one of the $K$ functions is at most $K\exp(-2n\varepsilon^2)$. Set $\varepsilon=\sqrt{\log(K/\delta)/(2n)}$. Then $K\exp(-2n\varepsilon^2)=\delta$, proving the simultaneous claim. $\square$

For an ensemble class formed from a finite base class $\mathcal H$ of size $N$, a simple count illustrates how rounds can enter. If each of $T$ positions can choose any one of $N$ rules, there are at most $N^T$ ordered rule lists. If the coefficient vectors are also restricted to a finite grid with $Q$ possibilities, there are at most $N^TQ$ candidates. The theorem's complexity contribution is then bounded by $$ \sqrt{\frac{T\log N+\log Q+\log(1/\delta)}{2n}}. $$ This is a valid counting bound for that finite candidate set. It need not be sharp: different lists can give the same score, and the bound may charge for distinctions that have little effect on prediction.

Worked Example: A Finite Candidate Set and Its Confidence Penalty

Suppose a procedure selects from $K=1000\times1891$ prespecified score functions, uses $n=1000$ observations, and we want confidence $1-\delta=0.95$. The finite-class theorem adds $\sqrt{\log(K/\delta)/(2n)}$ to the empirical margin probability.

Since $\delta=0.05$, $1/\delta=20$, so $$ \log(K/\delta)=3\log(10)+\log(1891)+\log(20). $$ Using natural logarithms, the three terms are approximately $6.908$, $7.545$, and $2.996$. Using unrounded values, their sum is approximately $17.448$. Thus the additive term is $$ \sqrt{\frac{17.448349}{2000}}\approx 0.0934. $$

For example, if a selected candidate has empirical margin probability $0.12$ at the chosen threshold, this bound gives a population margin probability no larger than approximately $0.2134$, simultaneously for every candidate, with probability at least $0.95$. This is a guarantee, not a prediction that the true probability equals the bound.

Worked Example: How a Round Count Enters a List-Counting Bound

Suppose the base class has $N=128$ rules and the ensemble uses $T=5$ positions. In addition to choosing the ordered rule list, suppose there are $Q=4{,}600{,}000$ allowed coefficient or model variants. With $n=2000$ and $\delta=0.05$, the logarithm in the finite-class bound is at most $5\log(128)+\log(Q)+\log(20)$.

The contributions, evaluated before rounding, are $$ 5\log(128)=24.260151,\qquad \log(4{,}600{,}000)=15.341567,\qquad \log(20)=2.995732. $$ Their sum is approximately $42.597451$, which rounds to $42.597$. Therefore the additive penalty is $$ \sqrt{\frac{42.597451}{4000}}\approx 0.1032. $$

The term $5\log(128)$ is the list-counting cost: each of five positions can select one of 128 rules. Increasing $T$ increases that term linearly in this calculation. This conclusion applies to this counting method and candidate construction; it is not a universal claim that every boosting margin bound must worsen with every additional round.

Convex-Hull Complexity Need Not Grow With the Number of Rounds

A normalized weighted vote belongs to the convex hull of the base class. Define $\operatorname{conv}(\mathcal H)$ to be all finite convex combinations of members of $\mathcal H$. Increasing the number of rounds changes which combinations the algorithm can reach, but every such combination remains in this same convex hull. The following identity explains why a Rademacher-complexity analysis can avoid a direct factor of $T$.

Definition: For a fixed sample $(x_i,y_i)_{i=1}^{n}$, the empirical Rademacher complexity of the signed-score class $\mathcal G$ is $$ \widehat{\mathfrak R}_n(\mathcal G)=E_{\sigma}\left[\sup_{g\in\mathcal G}\frac{1}{n}\sum_{i=1}^{n}\sigma_i g(x_i,y_i)\right], $$ where $\sigma_1,\ldots,\sigma_n$ are independent random signs, each equal to $+1$ or $-1$ with probability $1/2$.

Result: Let $\mathcal H$ be a nonempty class of rules and let $\mathcal G_{\mathcal H}=\{(x,y)\mapsto yh(x):h\in\mathcal H\}$. For the class $\mathcal G_{\operatorname{conv}(\mathcal H)}$ obtained by replacing $h$ with any finite convex combination of rules in $\mathcal H$, $$ \widehat{\mathfrak R}_n(\mathcal G_{\operatorname{conv}(\mathcal H)})=\widehat{\mathfrak R}_n(\mathcal G_{\mathcal H}). $$

Proof. Fix a realization of the signs. For any convex combination $f=\sum_{j=1}^{m}\alpha_j h_j$, where $\alpha_j\geq0$ and $\sum_j\alpha_j=1$, $$ \frac{1}{n}\sum_{i=1}^{n}\sigma_i y_i f(x_i) =\sum_{j=1}^{m}\alpha_j\left(\frac{1}{n}\sum_{i=1}^{n}\sigma_i y_i h_j(x_i)\right) \leq \sup_{h\in\mathcal H}\frac{1}{n}\sum_{i=1}^{n}\sigma_i y_i h(x_i). $$ Taking the supremum over all such $f$ preserves this inequality. Conversely, every $h\in\mathcal H$ is itself a convex combination with one term, so the supremum over the convex hull is at least the supremum over $\mathcal H$. The two suprema are equal for each sign vector. Taking expectation over the signs proves the identity. $\square$

This is a capacity statement, not a claim that generalization is automatic. In a Rademacher margin bound for convex combinations, the complexity term can be evaluated on the base class rather than on a separate class of all round-by-round lists. For a finite base class with $N$ rules taking values in $\{-1,+1\}$, a useful samplewise estimate is $$ \widehat{\mathfrak R}_n(\mathcal G_{\mathcal H})\leq\sqrt{\frac{2\log N}{n}}. $$ To see the scale, for any fixed rule the signed sum has moment generating function at most $\exp(\lambda^2 n/2)$, because its $n$ summands are independent random signs times fixed values in $\{-1,+1\}$. Applying the log-sum-exp bound to the maximum over $N$ rules gives an expected maximum at most $\sqrt{2n\log N}$; dividing by $n$ gives the displayed estimate. Thus this complexity estimate depends on $N$, not on how many terms are used to represent a convex combination.

Worked Example: Simple Rules Versus Flexible Rules

Consider two binary base classes, each used to form convex combinations. The first contains $N=4$ simple rules; the second contains $N=1024$ more flexible rules. For $n=1000$, the finite-class Rademacher estimates are $\sqrt{2\log(N)/n}$.

For the simple class, $$ \sqrt{\frac{2\log(4)}{1000}} =\sqrt{\frac{2.772589}{1000}} \approx 0.0527. $$ For the flexible class, $$ \sqrt{\frac{2\log(1024)}{1000}} =\sqrt{\frac{13.862944}{1000}} \approx 0.1177. $$

The second estimate is larger because the base class offers more alternatives. If both classes are used for 20 rounds rather than 5, this particular convex-hull complexity calculation remains the same for each class: it depends on the base class, not the round count. Other aspects of the fitted model, including the observed margins, can still change with the number of rounds.

Interpreting Complexity in Practice

The capacity of a weak-rule class is not determined only by how many rules are written down. A large list may contain many duplicates or near-duplicates, while a compact parameterized family can still be highly flexible. For finite classes, $\log N$ is a direct measure of the counting cost. For infinite classes, capacity measures such as VC dimension or Rademacher complexity provide corresponding controls. In tree boosting, for instance, shallow or otherwise restricted trees typically offer a less flexible base class than unrestricted deep trees, although the actual capacity depends on the allowed splits and input domain.

The two analyses answer different questions. Counting ordered lists is transparent and can show how a particular finite search space grows with $T$. It can be useful when the coefficient choices and candidate lists are genuinely restricted. The convex-hull calculation treats all finite convex combinations at once and shows why a margin bound based on that class need not multiply base-class capacity by the number of rounds. Neither calculation implies that extra rounds are harmless: they can alter the empirical margin distribution, and a bound may worsen if the chosen analysis explicitly counts the larger set of candidates.

Common Pitfall

Wrong reasoning: “The ensemble contains $T$ rules, so every valid margin bound must have a complexity term proportional to $T$.” This confuses the size of one representation with the capacity of the entire predictor class.
Correction: A list-counting argument can produce a $T\log N$ term, because it counts up to $N^T$ ordered lists. But a convex-hull Rademacher calculation can control all normalized combinations using the base-class complexity alone. State which class is being bounded and which argument is used before interpreting a round-count term.
Another warning: A base class with many possible rules is not automatically benign just because the algorithm selects only a few of them. The selection is data-dependent, so a valid bound must account for the candidate class or its capacity rather than treating the selected rules as fixed in advance.

Key takeaway: Base-class capacity and boosting-round count are not interchangeable complexity measures. Counting candidate lists can make the penalty grow with $T$; convex-hull margin analyses can instead depend on the weak-rule class without an explicit $T$ factor. The empirical margins and the assumptions behind the chosen bound remain essential.

Check Your Understanding

Use the definitions and results above to answer these questions.

Why does a positive-threshold margin probability upper-bound the classification error?
If a finite base class has $N$ rules and an ensemble has $T$ ordered positions, why is $N^T$ an upper bound on the number of rule lists?
In the finite-candidate theorem, which quantities determine the additive confidence penalty?
Explain why the empirical Rademacher complexity of a convex hull equals that of its base class.
Give one reason a list-counting bound may be looser than a convex-hull complexity bound.