The Product Bound On AdaBoost Training Error

Why Normalization Constants Control Training Error

AdaBoost repeatedly chooses a classifier that performs well under a changing distribution on the training examples. The normalization constant at each update records how much exponential loss remains after that round’s reweighting. Multiplying these constants gives an exact expression for the final empirical exponential loss, and that loss in turn bounds the fraction of training examples classified incorrectly.

This is a training-sample statement: it concerns the examples used to fit the ensemble. It does not, by itself, guarantee a particular test error or generalization performance.

Setup and Definitions

Consider a fixed training set \((x_i,y_i)_{i=1}^n\), with labels \(y_i\in\{-1,+1\}\). At round \(t\), the weak classifier is \(h_t\), also taking values in \(\{-1,+1\}\), and its coefficient is \(\alpha_t\geq 0\). The score after \(T\) rounds and its signed margin on example \(i\) are \(F_T(x_i)=\sum_{t=1}^T\alpha_t h_t(x_i)\) and \(y_iF_T(x_i)\), respectively. A positive signed margin means the score has the correct sign; a negative one means it has the wrong sign.

Start with uniform weights \(D_1(i)=1/n\). At each round, define the weighted error \(\varepsilon_t\), choose a finite coefficient \(\alpha_t\), and update the weights by exponential reweighting. The normalizer \(Z_t\) is the constant that makes the updated weights sum to one.

The usual discrete AdaBoost choice assumes \(0<\varepsilon_t<1\) and sets \(\alpha_t=\tfrac12\log((1-\varepsilon_t)/\varepsilon_t)\). If the weak classifier has error below one half, this coefficient is positive. A classifier with error above one half can instead be flipped, replacing \(h_t\) by \(-h_t\). We will use the usual weak-learner convention \(0<\varepsilon_t\leq 1/2\), with finite coefficients. The equal-error case gives \(\alpha_t=0\).

Worked Examples

The Product Identity and Training-Error Bound

The key fact is that the distribution at any round is the original uniform distribution tilted by the ensemble score accumulated so far. Normalization at each update makes the proportionality constant the reciprocal of the product of the earlier \(Z_t\)'s.

Proof. We first establish the weights’ explicit form. At round 1, \(D_1(i)=1/n\). If \(D_t(i)=\exp(-y_iF_{t-1}(x_i))/(n\prod_{s=1}^{t-1}Z_s)\), then the update gives $$ D_{t+1}(i) =\frac{\exp(-y_iF_{t-1}(x_i))\exp(-\alpha_t y_i h_t(x_i))} {n\left(\prod_{s=1}^{t-1}Z_s\right)Z_t} =\frac{\exp(-y_iF_t(x_i))}{n\prod_{s=1}^{t}Z_s}. $$ The base case and this induction prove the formula for \(D_{T+1}(i)\). Since the updated weights sum to one, $$ 1=\sum_{i=1}^nD_{T+1}(i) =\frac{1}{n\prod_{t=1}^T Z_t} \sum_{i=1}^n\exp\!\bigl(-y_iF_T(x_i)\bigr). $$ Rearranging proves the identity. If \(y_iF_T(x_i)\leq0\), then \(\exp(-y_iF_T(x_i))\geq1\). Therefore $$ \frac1n\sum_{i=1}^n\mathbf{1}\{y_iF_T(x_i)\leq0\} \leq \frac1n\sum_{i=1}^n\exp\!\bigl(-y_iF_T(x_i)\bigr) =\prod_{t=1}^T Z_t. $$ A mistaken prediction with a nonzero score has negative signed margin. A zero-score example is included on the left, so the inequality also covers any convention that treats a zero-score prediction as an error. \(\square\)

Under the discrete AdaBoost coefficient, \(Z_t\) has a simple expression in terms of weighted error. Correct predictions have \(y_i h_t(x_i)=+1\), and errors have \(y_i h_t(x_i)=-1\). Grouping the terms in its definition therefore gives $$ Z_t=(1-\varepsilon_t)e^{-\alpha_t}+\varepsilon_t e^{\alpha_t}. $$ When \(0<\varepsilon_t<1\) and \(\alpha_t=\tfrac12\log((1-\varepsilon_t)/\varepsilon_t)\), this becomes $$ Z_t=2\sqrt{\varepsilon_t(1-\varepsilon_t)}. $$ This also shows why the coefficient is chosen in this form: for fixed \(0<\varepsilon_t<1\), the expression \((1-\varepsilon_t)e^{-\alpha}+\varepsilon_t e^\alpha\) is minimized at that coefficient. Differentiating with respect to \(\alpha\) gives \(-(1-\varepsilon_t)e^{-\alpha}+\varepsilon_t e^\alpha\); setting this equal to zero yields \(e^{2\alpha}=(1-\varepsilon_t)/\varepsilon_t\), and the second derivative is positive.

Proof. Substituting \(\varepsilon_t=\tfrac12-\gamma_t\) gives \(Z_t=2\sqrt{(\tfrac12-\gamma_t)(\tfrac12+\gamma_t)} =\sqrt{1-4\gamma_t^2}\). For \(0\leq u<1\), \(\log(1-u)\leq-u\): indeed, the function \(g(u)=\log(1-u)+u\) has \(g(0)=0\) and derivative \(g'(u)=-u/(1-u)\leq0\). Hence \(\sqrt{1-u}\leq e^{-u/2}\). Apply this with \(u=4\gamma_t^2\) to each factor and multiply the resulting inequalities: \(\prod_t Z_t\leq\prod_t e^{-2\gamma_t^2} =e^{-2\sum_t\gamma_t^2}\). Combining this with the theorem proves the claim. \(\square\)

Interpreting the Bound and Avoiding a Pitfall

Each \(Z_t\) is at most one when \(\varepsilon_t\leq1/2\), so the product cannot increase as additional such rounds are added. The edge bound quantifies one way it can decrease: rounds with larger \(\gamma_t\) contribute more to the exponent. It is a deterministic bound for the fitted training sample and the stated updates, not a promise that the ensemble will generalize.

Common mistake: It is tempting to say that any chosen rule with error below one half gives a factor less than one, or to insert an error above one half directly into the edge formula. The normalization factor depends on the coefficient as well as on the error. With the discrete AdaBoost coefficient, a rule above one half has a negative coefficient; it is not the stipulated nonnegative weak-learner step. Flip the rule first, or analyze the coefficient and normalizer actually used. Also, a product bound below one does not mean the training error equals that product: the theorem gives an upper bound, and it can be loose.

If a round has zero weighted error, the displayed optimal coefficient is infinite, so the finite-coefficient update as stated does not apply. In the usual finite-sample setting, all current weights are positive when previous coefficients are finite. Thus zero weighted error then means the rule classifies every training example correctly, and the training error can already be zero; there is no need to assign an infinite coefficient to use the product-bound argument.