Boosting Algorithm

Inputs: Training data $\{(x_i, y_i)\}_{i=1}^n$, differentiable loss function $L(y, F(x))$, number of boosting iterations $M$, learning rate $\eta \in (0,1]$.

1. Initialization (initial weak learner):

   \[ F_{0}(x) = \arg\min_{\gamma}\sum_{i=1}^{n}L\bigl(y_{i},\gamma\bigr). \]

   One often takes $F_{0}(x)$ to be a constant (for example the average of targets).

2. For $m=1$ to $M$:

   1. Compute pseudo‐residuals (negative gradients): For each $i$,

      \[ r_{i}^{(m)} = -\left.\frac{\partial L\bigl(y_{i},F(x_{i})\bigr)}{\partial F(x_{i})}\right|_{F=F_{m-1}}. \]

      These pseudo‐residuals $r_{i}^{(m)}$, as a vector, explicitly represent the negative gradient of the loss with respect to predictions of the the current model.

   2. Fit a weak learner: Fit a weak learner (typically a decision tree) to the training set $\{(x_i, r_i^{(m)})\}_{i=1}^n$, with the pseudo‐residuals $r_i^{(m)}$ as the target values.

   3. Update the model:

      \[ F_{m}(x) = F_{m-1}(x) + \eta\,h_{m}(x), \]

      where $\eta$ (the learning rate; usually 0.1) scales the weak learner’s predictions of the pseudo‐residuals.

3. Final model:

   \[ F_{M}(x) \]