Weak Learnability And Exponential Training-Error Decay

From a Weak Advantage to a Training-Error Rate

AdaBoost repeatedly asks a weak learner to classify the training cases under a changing distribution of weights. A learner that does only slightly better than chance on each round may still produce a classifier with very small training error after enough rounds. The key qualification is that the advantage must persist: it is not enough for the learner to have an edge under the initial weights and then lose it as AdaBoost changes those weights.

The result in this tutorial is a finite-sample statement. It bounds the fraction of the observed training cases classified incorrectly when the selected weak rule has a uniform positive edge at every round. It does not, by itself, bound the error on new observations.

Definition: Fix a labeled training sample $(x_i,y_i)_{i=1}^n$, with $y_i\in\{-1,+1\}$. A distribution $D$ on this sample is a vector of nonnegative weights $D(i)$ summing to one. The weighted error of a binary rule $h:\mathcal X\to\{-1,+1\}$ is $$ \epsilon_D(h)=\sum_{i=1}^n D(i)\mathbf{1}\{h(x_i)\ne y_i\}. $$ The rule’s edge, in the usual advantage-over-chance convention, is $\gamma_D(h)=\tfrac12-\epsilon_D(h)$. The signed correlation is $1-2\epsilon_D(h)=2\gamma_D(h)$.

For a fixed $\gamma\in(0,\tfrac12)$, the weak-learning condition with edge $\gamma$ on this sample says that, for every distribution $D$ on the sample, the weak-learning procedure can return a rule $h$ satisfying $$ \epsilon_D(h)\le \frac12-\gamma. $$ This is a condition over all weight distributions on the observed cases, not just the uniform distribution. In AdaBoost, it is applied to the distribution at each round. The condition can depend on the training sample and the available weak-rule class; it is not a claim about all possible data distributions.

How the Edge Controls One Round

Write the current AdaBoost weight distribution as $D_t$, and let $h_t$ have weighted error $\epsilon_t=\epsilon_{D_t}(h_t)$. For $0<\epsilon_t<\tfrac12$, the discrete AdaBoost coefficient is $$ \alpha_t=\frac12\log\left(\frac{1-\epsilon_t}{\epsilon_t}\right). $$ The round’s normalization factor is the weighted average of the multiplicative changes to the example weights. Correctly classified cases receive the factor $e^{-\alpha_t}$; incorrectly classified cases receive $e^{\alpha_t}$. Therefore $$ Z_t=(1-\epsilon_t)e^{-\alpha_t}+\epsilon_t e^{\alpha_t} =2\sqrt{\epsilon_t(1-\epsilon_t)}. $$ In terms of the advantage edge, $\epsilon_t=\tfrac12-\gamma_t$, so $$ Z_t=\sqrt{1-4\gamma_t^2}. $$ Thus a larger positive edge makes the training-error upper bound contract more rapidly. This calculation concerns the normalization factor, not the actual error at each round; the bound follows by multiplying these factors across rounds.

Worked Example: Computing a Round’s Edge and Factor

Suppose five training cases have current weights $0.10,0.20,0.15,0.25,0.30$, and a weak rule misclassifies cases 1 and 4 only. The weights sum to one, and its weighted error is $$ \epsilon_t=0.10+0.25=0.35. $$ Its advantage edge is $\gamma_t=0.50-0.35=0.15$, and its signed correlation is $1-2(0.35)=0.30=2\gamma_t$.

The coefficient is $$ \alpha_t=\frac12\log\left(\frac{0.65}{0.35}\right) =\frac12\log\left(\frac{13}{7}\right)\approx 0.3095. $$ The normalization factor is $$ Z_t=2\sqrt{0.35(0.65)}=2\sqrt{0.2275}=\sqrt{0.91}\approx 0.9539. $$ The edge formula gives the same value: $\sqrt{1-4(0.15)^2}=\sqrt{0.91}$. This example verifies the round calculation; by itself, one round with edge $0.15$ does not establish a constant-edge condition over later rounds.

Constant Edge Gives Exponential Decay

The training error is controlled by an exponential quantity that accumulates the roundwise normalization factors. Define the aggregate score after $T$ rounds by $F_T(x)=\sum_{t=1}^T\alpha_t h_t(x)$, and use its sign for classification. At a tie, any fixed sign convention may be used.

Theorem: Suppose AdaBoost is run on a fixed sample of size $n$, with binary labels and binary weak rules. At each round $t=1,\ldots,T$, suppose the selected rule has weighted error $\epsilon_t\le \tfrac12-\gamma$ for a fixed $\gamma\in(0,\tfrac12)$. If no round has zero weighted error, then the fraction $\widehat R_T$ of training cases misclassified by $\operatorname{sign}(F_T)$ satisfies $$ \widehat R_T\le \prod_{t=1}^T \sqrt{1-4\gamma^2} =(1-4\gamma^2)^{T/2} \le \exp(-2\gamma^2T). $$ If a round has zero weighted error, AdaBoost classifies all training cases correctly at that round and may stop; its training error is then zero.

Proof. Define the unnormalized exponential sum $$ S_t=\sum_{i=1}^n \exp\left(-y_iF_t(x_i)\right), \qquad S_0=n. $$ The AdaBoost distribution before round $t$ is $D_t(i)=\exp(-y_iF_{t-1}(x_i))/S_{t-1}$. After adding $\alpha_t h_t$ to the score, factor out $S_{t-1}$ to obtain $$ S_t=S_{t-1}\sum_{i=1}^n D_t(i)\exp\left(-\alpha_t y_i h_t(x_i)\right). $$ Because $y_i h_t(x_i)=+1$ on correctly classified cases and $-1$ on incorrectly classified cases, the sum is $$ (1-\epsilon_t)e^{-\alpha_t}+\epsilon_t e^{\alpha_t} =2\sqrt{\epsilon_t(1-\epsilon_t)} =\sqrt{1-(1-2\epsilon_t)^2}. $$ The edge condition gives $1-2\epsilon_t\ge 2\gamma$, so this factor is at most $\sqrt{1-4\gamma^2}$. Iterating $S_t=S_{t-1}Z_t$ yields $S_T/n\le(1-4\gamma^2)^{T/2}$.

If case $i$ is misclassified, then $y_iF_T(x_i)\le 0$, and hence $\exp(-y_iF_T(x_i))\ge 1$. Thus the number of misclassified cases is at most $S_T$, which gives $\widehat R_T\le S_T/n$. Finally, for $0\le u<1$, $\log(1-u)\le-u$. Taking $u=4\gamma^2$ gives $(1-4\gamma^2)^{T/2}\le \exp(-2\gamma^2T)$, as claimed. $\square$

Worked Example: Bounding Training Error After 100 Rounds

Suppose the weak-learning condition holds with advantage edge $\gamma=0.10$ at each of $T=100$ rounds. The theorem gives $$ \widehat R_{100}\le (1-4(0.10)^2)^{50} =0.96^{50}\approx 0.1299. $$ The simpler exponential bound is $$ \widehat R_{100}\le \exp\bigl(-2(0.10)^2(100)\bigr) =e^{-2}\approx 0.1353. $$ The exponential expression is slightly looser here, as expected from the inequality used in the proof. Both are upper bounds; neither says that the realized error must equal the bound.

Worked Example: How Many Rounds Ensure Zero Training Errors?

Suppose $n=100$ and the same constant edge $\gamma=0.10$ is maintained. Since the training-error fraction is an integer multiple of $1/100$, an upper bound strictly below $0.01$ forces the fraction to be zero. The exponential bound is below $0.01$ when $$ e^{-0.02T}<0.01 \quad\Longleftrightarrow\quad T>\frac{\log(100)}{0.02}\approx 230.26. $$ Thus $T=231$ rounds suffice under the stated condition: the bound is $e^{-4.62}\approx0.00985<0.01$. This is a sufficient guarantee, not a necessary round count; the actual classifier may fit the sample sooner.

What the Condition Does Not Guarantee

The theorem controls an empirical quantity: errors on the particular $n$ training cases. The weak-learning condition is also imposed only on distributions over those cases. Neither statement directly controls how the final classifier behaves at new feature values, nor does the exponential rate establish that the observed sample represents the population well.

For example, let the input space be $\{x_1,x_2,x_3\}$, with labels $+1$ at all three points, and let the weak-rule class contain just one rule $h$, defined by $h(x_1)=h(x_2)=+1$ and $h(x_3)=-1$. Suppose the observed training sample consists of $x_1$ and $x_2$. For every distribution on these two training cases, $h$ has weighted error zero, so it satisfies the weak-learning condition there with any $\gamma<\tfrac12$. AdaBoost stops with zero training error, but $h$ is wrong at $x_3$.

This can correspond to high population error, not merely a hypothetical point outside the support. For instance, assign population probabilities $0.05,0.05,0.90$ to $x_1,x_2,x_3$, respectively. The probability of observing one $x_1$ and one $x_2$ in two independent draws is $2(0.05)(0.05)=0.005>0$. On that possible training sample the error is zero, while the population error of $h$ is $0.90$. The example does not say such a sample is likely; it shows that the training bound alone cannot rule out large test error.

Common pitfall: “The weighted error is below one half, so AdaBoost’s test error decreases exponentially.” This conclusion does not follow. The required condition is a positive edge at every round under the changing training weights, and the theorem’s conclusion is exponential decay of training error only. Generalization requires additional reasoning beyond this finite-sample calculation.

Interpreting the Rate

A constant edge is a uniform guarantee that the weak learner can keep finding a useful rule even as AdaBoost concentrates weight on difficult cases. The exponential bound quantifies the consequence: for fixed $\gamma>0$, the upper bound decreases geometrically with the number of rounds. If the edge varies by round, the same derivation instead gives a product of factors $\sqrt{1-4\gamma_t^2}$, where $\gamma_t=\tfrac12-\epsilon_t$; a single positive edge at the first round is not enough to replace that product by a constant-edge rate.

The rate also depends strongly on the size of the edge. When $\gamma$ is small, the exponent $2\gamma^2T$ grows slowly, so many rounds may be needed for a useful upper bound. When a perfect rule appears, the separate zero-error case applies and the training error is already zero. These are statements about fitting the fixed sample, not prescriptions that more rounds must improve performance on new data.

Check Your Understanding

Use the definitions and theorem to answer the following questions.

Under the convention $\gamma=\tfrac12-\epsilon$, what is the signed correlation $1-2\epsilon$ in terms of $\gamma$?
If the weighted error is $0.42$, calculate the advantage edge and the one-round normalization factor.
For a constant advantage edge $\gamma=0.05$, write the theorem’s exponential upper bound after $T$ rounds.
Why does $\widehat R_T<1/n$ imply zero training errors?
State one additional kind of information that would be needed before drawing a conclusion about test error.