A Worked Comparison Of Boosting Updates And Bounds

Why Compare Updates and Bounds?

Boosting calculations connect three quantities that are easy to conflate: the distribution of weights used to choose a weak rule, the coefficients accumulated in the ensemble, and the margins of individual observations. A small numerical example makes their roles visible. It also shows why a favorable training margin or a small empirical margin fraction is not, by itself, a population guarantee: a bound needs a stated sampling assumption and a way to account for which predictors were considered.

We use binary labels \(y_i\in\{-1,+1\}\) and classifiers \(h(x_i)\in\{-1,+1\}\). The signed margin of observation \(i\) under an ensemble \(F\) is \(y_iF(x_i)\). A positive margin means the ensemble score has the correct sign; a larger positive margin indicates a more confident signed score. In discrete AdaBoost, a round selects a weak rule with weighted error below one half and adds a log-odds coefficient.

Worked AdaBoost Updates

Consider four observations with labels \(y=(+1,+1,-1,-1)\). To keep the update arithmetic focused, begin at a specified continuation state: the current weights are \(D_2=(1/12,1/12,3/4,1/12)\), and the existing score is \(F_1=\alpha_1h_1\), where \(\alpha_1=\tfrac12\log 3\) and \(h_1=(+1,+1,+1,-1)\). The weights and existing score are state information at the start of this calculation; they are not being inferred from a uniform initialization. We now calculate two consecutive standard, unshrunk rounds.

To verify the result, write the unnormalized total for errors as \(\epsilon_t e^{\alpha_t}\), and the total for correct classifications as \((1-\epsilon_t)e^{-\alpha_t}\). The coefficient definition gives \(e^{2\alpha_t}=(1-\epsilon_t)/\epsilon_t\), hence \[ \epsilon_t e^{\alpha_t}=(1-\epsilon_t)e^{-\alpha_t} =\sqrt{\epsilon_t(1-\epsilon_t)}. \] Adding the two totals gives \(Z_t=2\sqrt{\epsilon_t(1-\epsilon_t)}\). Dividing either group total by \(Z_t\) gives \(1/2\). This also shows why a reweighting calculation must normalize the correct group in proportion to its previous weights, rather than assigning each observation an arbitrary share. \(\square\)

Margins and Shrinkage

At each round the signed margin changes by a particularly simple amount: \[ y_iF_t(x_i)=y_iF_{t-1}(x_i)+\nu\alpha_t y_i h_t(x_i). \] The increment is \(+\nu\alpha_t\) for an observation classified correctly by the new rule and \(-\nu\alpha_t\) for one classified incorrectly. Thus a weak rule can improve some margins while reducing others; the weighted error determines its coefficient, not a guarantee that every observation improves.

A Finite-Sample Margin Bound

A margin bound relates the population classification error to an empirical fraction of small margins, plus a sampling penalty. To give a completely explicit finite-sample result, consider a finite family of \(K\) candidate score functions, fixed before observing the sample. Each score \(F\) takes values in \([-1,1]\), and classification predicts the sign of \(F(x)\). For a threshold \(\gamma\ge0\), a small-margin observation is one for which \(yF(x)\le\gamma\). We use the tie rule that \(F(x)=0\) predicts \(+1\). The event \(\{yF(x)\le0\}\) is the nonpositive-margin event; it contains the classification-error event under this tie rule, and is contained in the small-margin event.

For a proof, fix one \(F\) and define \(Z_i=\mathbf{1}\{Y_iF(X_i)\le\gamma\}\). These are independent Bernoulli random variables with common mean \(p_F=P\{YF(X)\le\gamma\}\). Hoeffding's inequality gives \[ P\left\{p_F-\frac1n\sum_{i=1}^n Z_i>s\right\}\le e^{-2ns^2}. \] Set \(s=\sqrt{\log(K/\delta)/(2n)}\); the right-hand side is \(\delta/K\). Taking a union bound over the \(K\) functions shows that, with probability at least \(1-\delta\), for every \(F\), \(p_F\le n^{-1}\sum_i Z_i+s\). Finally, \(\{YF(X)\le0\}\subseteq\{YF(X)\le\gamma\}\), so the same upper bound holds for the population error. \(\square\)

Common Pitfalls and Interpretation

• Forgetting to renormalize a group. After an update, the correct group has total weight \(1/2\), distributed according to its previous relative weights. In the round-2 calculation, the correct weights \(1/12,3/4,1/12\) have relative proportions \(1:9:1\), so their new values are \(1/22,9/22,1/22\), not values obtained by dividing each by 20. Always check that all updated weights sum to one.
• Using the wrong distribution for the next error. The round-3 error is evaluated under \(D_3\), so it is \(9/22\approx0.4091\), not a weight from an earlier round. Its coefficient is \(\tfrac12\log(13/9)\approx0.1839\).
• Assuming all margins increase. The margin increment's sign is determined by whether that round's rule is correct on that observation. A later correct rule can improve a negative margin without making it positive.
• Applying a fixed-predictor bound after unrestricted selection. The theorem pays for a finite family considered uniformly. If the predictor is selected from a family not included in that count, or from an unrestricted class, this calculation alone does not justify the claimed guarantee. A suitable complexity-controlled bound is then needed.

The practical lesson is to keep the three calculations separate and then connect them deliberately: weighted error determines a round's coefficient, the signed rule output determines each margin change, and the generalization statement needs an explicit sampling model and predictor family. A small empirical margin fraction is informative, but it is not a population statement until the bound's assumptions and penalty are accounted for.