# boosting

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-08. [HTML](https://dictionaryofml.org/terms/boosting.html) · [typeset PDF](https://dictionaryofml.org/terms/boosting.pdf) · [LaTeX](https://dictionaryofml.org/terms/boosting.tex) · [Python demo](https://dictionaryofml.org/terms/boosting.py) · [notebook](https://dictionaryofml.org/terms/boosting.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

Boosting is an ensemble method that sequentially combines simple base learners, also called weak learners. At each iteration, a base learner uses a modified training set constructed from the original training set and the current predictions. Gradient boosting replaces the labels by negative loss partial derivatives, while adaptive boosting retains the labels and changes the weights of the data points. The resulting hypothesis is an additive combination of the learned corrections.

## Definition

The weather station Krems an der Donau records the daily minimum and maximum temperature. Each day is a data point with the minimum temperature as its feature $x$ and the maximum temperature as its label $y$ (Fig. 1). The figure also shows a hypothesis learned by a depth-one decision tree. This tree is too simple to capture the relation between $x$ and $y$. Boosting improves the hypothesis by adding another hypothesis that corrects its prediction errors. The two curves correspond to the first two iterations of this process.

Boosting is an ensemble method that sequentially combines base learners to obtain a more accurate hypothesis (Hastie et al., 2009, Ch. 10). The base learners are typically simple models, such as shallow decision trees, and are also called weak learners.

![Figure 1 of the entry boosting](https://dictionaryofml.org/terms/fig/boosting-fig1.svg)

*Figure 1: Two iterations of boosting on five days of weather measurements at Krems an der Donau. The dashed curve is the hypothesis learned by the first depth-one decision tree. The second decision tree is learned from its residuals. Adding that decision tree gives the solid curve and lowers the average squared prediction error from $31.0$ to $10.9$. Data generated by pythondemos/boosting.py*

In contrast to ensemble methods such as bagging and stacking, boosting trains its base learners sequentially. At iteration $t$, a base learner learns a hypothesis $\widehat{h}^{(t)}$ from a modified training set $\widetilde{\mathcal{D}^{(\rm train)}}^{(t)}$. This training set is constructed from the original training set $\mathcal{D}^{(\rm train)}$ and the predictions of $\widetilde{h}^{(t-1)}$ (Fig. 2).

![Figure 2 of the entry boosting](https://dictionaryofml.org/terms/fig/boosting-fig2.svg)

*Figure 2: Boosting constructs each modified training set $\widetilde{\mathcal{D}^{(\rm train)}}^{(t)}$ from the original training set $\mathcal{D}^{(\rm train)}$ and the current aggregate hypothesis $\widetilde{h}^{(t-1)}$. The dotted arrows show that the original training set and the preceding base learner affect the next modified training set. A base learner learns the next correction from that training set*

Boosting methods start from an initial hypothesis $\widetilde{h}^{(0)}$, which is iteratively improved by the update

\begin{equation}
\widetilde{h}^{(t)} = \widetilde{h}^{(t-1)}+
\eta^{(t)}
\widehat{h}^{(t)}\text{,}\qquad
t=1,\ldots,T\text{.}
\tag{1}
\end{equation}

Here, $\eta^{(t)}$ is a learning rate and $\widehat{h}^{(t)}$ the hypothesis of the $t$-th base learner (see Fig. 3). The additive updates Eq. (1) therefore form a sequence of aggregate hypotheses.

![Figure 3 of the entry boosting](https://dictionaryofml.org/terms/fig/boosting-fig3.svg)

*Figure 3: Boosting constructs a sequence of hypothesis maps. Each new hypothesis map $\widetilde{h}^{(t+1)}$ is obtained from a base learner $\widehat{h}^{(t+1)}$ that aims to correct the prediction errors of the current hypothesis $\widetilde{h}^{(t)}$*

Different boosting methods construct $\widetilde{\mathcal{D}^{(\rm train)}}^{(t)}$ differently. Gradient boosting replaces the label $y$ of each data point $({\mathbf x},y)$ by the negative partial derivative of its loss with respect to the current prediction,

$$
-\left.
\frac{\partial
L\left(({\mathbf x},y),z \right)}{\partial z}
\right|_{z=\widetilde{h}^{(t-1)}({\mathbf x})}.
$$

These values are pseudo-labels, also called negative gradients. This construction applies when the loss function depends on the hypothesis through its prediction. For the squared error loss, the pseudo-labels are proportional to the prediction errors $y-\widetilde{h}^{(t-1)}({\mathbf x})$. Algorithm 1 summarizes a basic form of gradient boosting (Hastie et al., 2009, Algorithm 10.3).

![Algorithm 1 of the entry boosting](https://dictionaryofml.org/terms/fig/boosting-alg1.svg)

*Algorithm 1: Gradient boosting*

Gradient boosting can be viewed as an extension of gradient descent from updates of a finite-dimensional model parameter to updates in a hypothesis space. For the squared error loss and a base learner that uses linear regression, this connection is exact under the orthogonality and normalization condition stated below. At iteration $t$, Algorithm 1 learns a linear map that predicts the residuals $y^{(r)}-\big({\mathbf x}^{(r)}\big)^\top
{\mathbf w}^{(t-1)}$, for $r=1,\ldots,m$. If the feature matrix ${\mathbf X}=\big({\mathbf x}^{(1)},\ldots,
{\mathbf x}^{(m)}\big)^\top$ has full column rank, the model parameter of this map is the unique least-squares solution (Hastie et al., 2009, Sect. 3.2, Eq. (3.6))

$$
\Delta{\mathbf w}^{(t)}=
({\mathbf X}^{\top}{\mathbf X})^{-1}{\mathbf X}^{\top}
\big({\mathbf y}-{\mathbf X}{\mathbf w}^{(t-1)}\big).
$$

If the columns of ${\mathbf X}$ are also orthogonal and normalized such that ${\mathbf X}^{\top}{\mathbf X}=m\mathbf{I}$, then

$$
\Delta{\mathbf w}^{(t)}=
\frac{1}{m}{\mathbf X}^{\top}
\big({\mathbf y}-{\mathbf X}{\mathbf w}^{(t-1)}\big),
$$

which is the negative gradient, at ${\mathbf w}^{(t-1)}$, of the scaled average squared error loss $f({\mathbf w}) := \frac{1}{2m}
\left\lVert {\mathbf y}-{\mathbf X}{\mathbf w} \right\rVert_{2}^{2}$. The factor $1/2$ cancels the factor $2$ that differentiating the square produces. With matching initialization and learning rates, the boosting iterates satisfy $\widetilde{h}^{(t)}=
h^{({\mathbf w}^{(t)})}$ and coincide with the gradient descent iterates.

Adaptive boosting applies boosting to binary classification. Like gradient boosting in Algorithm 1, it uses the additive update Eq. (1). However, it uses a different construction for the training set $\widetilde{\mathcal{D}^{(\rm train)}}^{(t)}$: the prediction errors of $\widetilde{h}^{(t-1)}$ determine weights, with larger weights assigned to misclassified data points.

Algorithm 2 presents adaptive boosting.M1 (Hastie et al., 2009, Algorithm 10.1).

![Algorithm 2 of the entry boosting](https://dictionaryofml.org/terms/fig/boosting-alg2.svg)

*Algorithm 2: Adaptive boosting.M1*

At the start of iteration $t$, the normalized weights satisfy

$$
q^{(r)}=
\frac{\exp\!\left(-y^{(r)}
\widetilde{h}^{(t-1)}
({\mathbf x}^{(r)})\right)}
{\sum_{r'=1}^{m}
\exp\!\left(-y^{(r')}
\widetilde{h}^{(t-1)}
({\mathbf x}^{(r')})\right)}.
$$

Since the normalized sample weights $q^{(r)}$ in the preceding display sum to $1$, the quantity $\epsilon^{(t)}$ defined in Algorithm 2 is the weighted average 0/1 loss of $\widehat{h}^{(t)}$ on the training set used at iteration $t$.

A single iteration of adaptive boosting reduces the average exponential loss, which is the empirical risk

$$
\widehat{L}\big(\widetilde{h}^{(t)}|\mathcal{D}^{(\rm train)}\big)
:= \frac{1}{m}
\sum_{r=1}^{m}
\exp\!\left(-y^{(r)}
\widetilde{h}^{(t)}
({\mathbf x}^{(r)})\right).
$$

Substituting the additive update Eq. (1) into this empirical risk gives

$$
\widehat{L}\big(\widetilde{h}^{(t)}|\mathcal{D}^{(\rm train)}\big)
=\kappa^{(t)}
\widehat{L}\big(\widetilde{h}^{(t-1)}|\mathcal{D}^{(\rm train)}\big),
$$

where

$$
\kappa^{(t)}=(1-\epsilon^{(t)})
e^{-\eta^{(t)}}+\epsilon^{(t)}
e^{\eta^{(t)}}
=2\sqrt{\epsilon^{(t)}(1-\epsilon^{(t)})}.
$$

Thus, if $0<\epsilon^{(t)}<1/2$, then $0<\kappa^{(t)}<1$. For this iteration, scalar multiplication by $\kappa^{(t)}$ is a contractive operator on the average exponential loss. Since the 0/1 loss is bounded by the exponential loss, repeated contractions also reduce an upper bound on the training error (Schapire and Freund, 2012, Thm. 3.1). This argument concerns the empirical loss; it does not assert that the hypotheses themselves form a contractive sequence.

**See also:** [ensemble](https://dictionaryofml.org/terms/ensemble.html), adaptive boosting, gradient boosting, [base learner](https://dictionaryofml.org/terms/baselearner.html), [bagging](https://dictionaryofml.org/terms/bagging.html), contractive operator.

## References

- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>
- Schapire and Freund (2012). Boosting: Foundations and Algorithms. *MIT Press*.

## Cite this entry

```bibtex
@misc{dictml_boosting,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {boosting},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-11},
  url = {https://dictionaryofml.org/terms/boosting.html}
}
```