Boosting builds a strong predictor by adding weak learners sequentially. Its mathematical forms include margin maximization, functional gradient descent, and additive modeling.
Additive models
Boosting searches in the linear span of a weak learner class.
Definition. Given weak learners \(\mathcal H\), an additive predictor has the form \[ F_T(x)=\sum_{t=1}^T\alpha_t h_t(x),\qquad h_t\in\mathcal H. \] For classification \(Y\in\{-1,1\}\), prediction is \(\operatorname{sign}F_T(x)\).
Remark. The number of boosting rounds, shrinkage, and weak learner complexity all act as regularization parameters.
AdaBoost and exponential loss
AdaBoost can be derived as greedy minimization of empirical exponential loss.
Proposition. At round \(t\), AdaBoost chooses a weak learner using weights proportional to \(\exp(-Y_iF_{t-1}(X_i))\). If its weighted error is \(e_t<1/2\), the optimal step for exponential loss along that learner is \[ \alpha_t=\frac12\log\frac{1-e_t}{e_t}. \]
Proof. The empirical exponential loss after adding \(\alpha h\) is \[ \sum_i w_i e^{-\alpha Y_ih(X_i)} =e^{-\alpha}\sum_{Y_ih=1}w_i+e^\alpha\sum_{Y_ih=-1}w_i. \] With normalized weights, this equals \(e^{-\alpha}(1-e_t)+e^\alpha e_t\). Differentiating and setting the derivative to zero gives the displayed \(\alpha_t\).
Training-error decay
Weak learning gives multiplicative decay of exponential loss.
Theorem. If each weak learner has weighted error \(e_t=1/2-\gamma_t\), then AdaBoost's empirical zero-one error is bounded by \[ \prod_{t=1}^T 2\sqrt{e_t(1-e_t)} \le \exp\left(-2\sum_{t=1}^T\gamma_t^2\right). \]
Proof. Zero-one loss is bounded by exponential loss. At each step, the normalized exponential loss is multiplied by \(2\sqrt{e_t(1-e_t)}\). Since \(e_t(1-e_t)=1/4-\gamma_t^2\) and \(\sqrt{1-4\gamma_t^2}\le e^{-2\gamma_t^2}\), the result follows.
Margins and overfitting
Boosting often continues to improve margins after training error reaches zero.
Remark. The empirical margin distribution can explain why more rounds need not immediately overfit. Generalization, however, still depends on weak learner complexity, shrinkage, sample size, and noise.
The weight recursion
Proposition. Let \[ D_t(i)=\frac{\exp\{-y_iF_{t-1}(x_i)\}} {\sum_j\exp\{-y_jF_{t-1}(x_j)\}}. \] After choosing \(h_t\) and \(\alpha_t=\frac12\log\{(1-e_t)/e_t\}\), AdaBoost updates \[ D_{t+1}(i)= \frac{D_t(i)e^{-\alpha_ty_ih_t(x_i)}}{Z_t}, \qquad Z_t=2\sqrt{e_t(1-e_t)}. \]
Proof. Since \(F_t=F_{t-1}+\alpha_th_t\), substitution into the exponential weights gives the recursion. The normalization is \(Z_t=(1-e_t)e^{-\alpha_t}+e_te^{\alpha_t}\), which at the optimal step equals \(2\sqrt{e_t(1-e_t)}\).
Misclassified observations are multiplied by \(e^{\alpha_t}\), while correctly classified observations are multiplied by \(e^{-\alpha_t}\). The next weak learner is therefore fitted against the current margin failures.
Weak learnability and separability
Definition. A weak learner class \(\mathcal H\) has edge \(\gamma>0\) on a sample if, for every distribution \(D\) on the observations, there exists \(h\in\mathcal H\) with \[ \sum_iD(i)y_ih(x_i)\ge2\gamma. \]
Theorem. If every AdaBoost round obtains edge at least \(\gamma\), then \[ P_n\{YF_T(X)\le0\}\le e^{-2T\gamma^2}. \] Thus \(T\ge\log(1/\varepsilon)/(2\gamma^2)\) rounds suffice for empirical error at most \(\varepsilon\).
Proof. This is the training-error product bound with every \(\gamma_t\ge\gamma\): \(\prod_tZ_t\le\prod_te^{-2\gamma_t^2}\le e^{-2T\gamma^2}\).
Functional gradient descent
Proposition. For an additive model \(F\) and differentiable loss \[ \mathcal L(F)=\frac1n\sum_{i=1}^n\ell(Y_i,F(X_i)), \] the negative functional gradient evaluated at the data is the pseudo-response \[ r_i=-\frac{\partial}{\partial u}\ell(Y_i,u) \bigg|_{u=F(X_i)}. \] Gradient boosting selects \(h_t\in\mathcal H\) that approximates \(r=(r_1,\ldots,r_n)\) and updates \(F_t=F_{t-1}+\nu\alpha_th_t\).
Proof. For a direction \(h\), \[ \left.\frac{\mathrm{d}}{\mathrm{d}\alpha} \mathcal L(F+\alpha h)\right|_{\alpha=0} =\frac1n\sum_i \partial_2\ell(Y_i,F(X_i))h(X_i) =-\frac1n\sum_ir_ih(X_i). \] Maximizing correlation with \(r\) therefore chooses the steepest available descent direction in the span of weak learners.
Example. For squared loss, \(r_i=Y_i-F(X_i)\), so each tree or weak learner fits current residuals. For logistic deviance with \(Y\in\{0,1\}\) and probability \(p_F=(1+e^{-F})^{-1}\), \(r_i=Y_i-p_F(X_i)\), the usual likelihood score residual.
Stagewise paths and \(\ell^1\) geometry
When \(\mathcal H=\{\pm h_1,\ldots,\pm h_M\}\), an additive model is \(F=\sum_j\beta_jh_j\). Infinitesimal forward stagewise updates change one coefficient at a time in its descent direction. Under positive-cone conditions, this path coincides with the Lasso path; more generally it is a monotone \(\ell^1\)-regularized path. The number of rounds and shrinkage \(\nu\) control the path length \(\sum_j|\beta_j|\).
Maximum margin as an implicit limit
Theorem. On separable data, minimizing exponential loss over the linear span of weak learners drives coefficient norm to infinity, but under suitable nondegeneracy the normalized direction converges toward the solution of \[ \max_{\|\beta\|_1\le1}\min_i y_i\sum_j\beta_jh_j(x_i). \]
Proof outline. Along a ray \(c\beta\), exponential loss is dominated as \(c\to\infty\) by the smallest margin: \[ \log\sum_i e^{-c y_iF_\beta(x_i)} =-c\min_i y_iF_\beta(x_i)+O(1). \] Thus directions with larger minimum normalized margin eventually have exponentially smaller loss. Coordinate-descent dynamics must be controlled to turn this variational observation into convergence, but the limiting optimization problem follows from the log-sum-exp asymptotics.
Margin-distribution generalization
Theorem. Suppose \(h(x)\in[-1,1]\) for \(h\in\mathcal H\), and let \(F\) lie in the \(\ell^1\)-convex hull of \(\mathcal H\). With high probability, for every \(\theta>0\), \[ P(YF(X)\le0) \lesssim P_n(YF(X)\le\theta) +\frac1\theta \sqrt{\frac{d\log^2(n/d)+\log(1/\delta)}{n}}, \] when \(\mathcal H\) has VC dimension \(d\).
Proof outline. Approximate a convex combination by an average of finitely many independently sampled base classifiers. Hoeffding controls the approximation of margins, while Sauer-Shelah controls the number of label patterns of each sampled base learner. Apply a union bound to the resulting finite approximating class and optimize the number of sampled learners.
Noise sensitivity and robust alternatives
Remark. Exponential loss assigns unbounded weight to large negative margins, so a persistently mislabeled point can dominate late rounds. Logistic loss grows only linearly in the negative tail, and truncated or robust boosting losses limit this leverage. Shrinkage, tree-depth control, subsampling, and early stopping are therefore not merely computational conveniences; they alter statistical robustness.