Gradient Boosting

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Additive Models and Forward Stagewise Fitting
5. Boosting as Functional Gradient Descent
6. The Gradient Boosting Algorithm
7. Gradient Boosting for Regression (Squared Loss)
8. Gradient Boosting for Classification (Log-Loss)
9. Regularization Techniques
10. XGBoost: Second-Order Formulation
11. Common Pitfalls
12. Research Perspective
13. Summary
14. Exercises

Learning Objectives

1. Formalize boosting as sequential minimization in function space.
2. Derive the gradient boosting update as functional gradient descent.
3. Show that for squared loss, gradient boosting fits residuals.
4. Derive the XGBoost objective with second-order approximation.
5. Explain the roles of shrinkage, subsampling, and tree depth in regularization.
6. Compare the bias-reduction mechanism of boosting vs. the variance-reduction of bagging.

Notation

• $F(\mathbf{x}) = \sum_{m=0}^M \eta \cdot h_m(\mathbf{x})$ — additive ensemble
• $h_m$ — $m$-th base learner (weak learner, typically a shallow tree)
• $\eta \in (0, 1]$ — learning rate (shrinkage)
• $L(y, F(\mathbf{x}))$ — loss function
• $\tilde{y}_i^{(m)} = -\frac{\partial L(y_i, F(\mathbf{x}_i))}{\partial F(\mathbf{x}_i)}\bigg|_{F=F_{m-1}}$ — pseudo-residuals
• $g_i, h_i$ — first and second derivatives of loss (XGBoost notation)

Core Intuition

While bagging reduces variance by averaging independent models, boosting reduces bias by sequentially correcting errors. Each new weak learner is fit to the mistakes (pseudo-residuals) of the current ensemble. The ensemble builds up a powerful predictor from many simple models, each contributing a small correction.

Additive Models and Forward Stagewise Fitting

The ensemble model is additive:

where $F_0$ is a constant initialization (e.g., the mean of $y$) and each $h_m$ is a shallow tree.

Forward stagewise fitting: At step $m$, fix all previous terms and optimize only $h_m$:

Boosting as Functional Gradient Descent

View $F$ as a point in function space. The loss functional is $\mathcal{L}(F) = \sum_i L(y_i, F(\mathbf{x}_i))$. The functional gradient at data points is:

We cannot step directly in this infinite-dimensional direction, so we fit a base learner $h_m$ to approximate the negative gradient:

where $\tilde{y}_i^{(m)} = -\frac{\partial L}{\partial F(\mathbf{x}_i)}\big|_{F_{m-1}}$ are the pseudo-residuals.

The Gradient Boosting Algorithm

1. Initialize: $F_0(\mathbf{x}) = \arg\min_c \sum_i L(y_i, c)$.
2. For $m = 1, \ldots, M$:
   • Compute pseudo-residuals: $\tilde{y}_i^{(m)} = -\frac{\partial L(y_i, F_{m-1}(\mathbf{x}_i))}{\partial F_{m-1}(\mathbf{x}_i)}$.
   • Fit base learner: $h_m \approx \arg\min_h \sum_i(\tilde{y}_i^{(m)} - h(\mathbf{x}_i))^2$.
   • Update: $F_m = F_{m-1} + \eta \cdot h_m$.
3. Output: $F_M(\mathbf{x})$.

Gradient Boosting for Regression (Squared Loss)

For $L(y, F) = \frac{1}{2}(y - F)^2$:

The pseudo-residuals are literally the residuals. Each tree fits the errors of the previous ensemble.

Gradient Boosting for Classification (Log-Loss)

For binary classification with $L(y, F) = \log(1 + e^{-yF})$ where $y \in \{-1, +1\}$:

Points that are currently misclassified (large negative $y_iF_{m-1}$) get pseudo-residuals close to $\pm 1$ (high weight). Correctly classified points get small pseudo-residuals.

Regularization Techniques

Shrinkage (learning rate $\eta$). Using $\eta < 1$ scales each tree's contribution:

Smaller $\eta$ requires more trees $M$ but generalizes better (analogous to smaller step size in optimization).

Subsampling (stochastic gradient boosting). Each tree is fit on a random fraction $q \in (0.5, 0.8)$ of the training data. Introduces randomness similar to SGD.

Tree constraints: Limit depth (typically 3–8), minimum leaf size, and maximum leaves.

L2 regularization on leaf weights (in XGBoost): penalizes large predictions in individual leaves.

XGBoost: Second-Order Formulation

XGBoost uses a second-order Taylor approximation of the loss at step $m$:

where $g_i = \frac{\partial L(y_i, F_{m-1}(\mathbf{x}_i))}{\partial F_{m-1}}$, $h_i = \frac{\partial^2 L(y_i, F_{m-1}(\mathbf{x}_i))}{\partial F_{m-1}^2}$, and $\Omega(h_m) = \gamma T + \frac{\lambda}{2}\sum_{j=1}^T w_j^2$ penalizes tree complexity ($T$ = number of leaves, $w_j$ = leaf weight).

Optimal leaf weight for leaf $j$ (containing indices $I_j$):

Optimal objective value (used for split scoring):

Split gain: The reduction in objective from splitting leaf $j$ into $L, R$:

Common Pitfalls

Pitfall 1. Overfitting with too many trees and high learning rate. Unlike random forests, gradient boosting can overfit as $M$ increases. Use early stopping based on validation loss.

Pitfall 2. Ignoring feature scale. While trees are scale-invariant, the pseudo-residuals and learning rate interact with the loss scale. Standardization is less critical than for linear models but still relevant for convergence speed.

Pitfall 3. Confusing bagging (reduces variance) with boosting (reduces bias). They attack different components of generalization error.

Research Perspective

Boosting was introduced by Schapire (1990) and Freund & Schapire (1995, AdaBoost). Friedman (2001) unified boosting as gradient descent in function space. XGBoost (Chen & Guestrin, 2016) added second-order optimization and systems-level efficiency, becoming the dominant method for tabular data. LightGBM (Ke et al., 2017) and CatBoost (Prokhorenkova et al., 2018) further improved scalability and handling of categorical features.

Summary

• Gradient boosting builds additive models by sequentially fitting pseudo-residuals.
• It is functional gradient descent: each tree approximates the negative gradient of the loss.
• For squared loss, pseudo-residuals = actual residuals; for log-loss, they weight hard examples.
• Shrinkage and subsampling prevent overfitting; early stopping is essential.
• XGBoost uses a second-order Taylor expansion for optimal leaf weights and split scoring.
• Boosting reduces bias (contrast with bagging which reduces variance).

Exercises

Exercise 1. Derive the pseudo-residuals for Huber loss $L(y,F) = \begin{cases}\frac{1}{2}(y-F)^2 & |y-F| \leq \delta \\ \delta|y-F| - \frac{\delta^2}{2} & \text{otherwise}\end{cases}$.

Exercise 2. Show that AdaBoost is equivalent to forward stagewise fitting with exponential loss $L(y,F) = e^{-yF}$.

Exercise 3. Derive the optimal leaf weights (equation 9) by setting the derivative of the XGBoost objective to zero.

Exercise 4. Prove that gradient boosting with squared loss and depth-1 trees (stumps) is equivalent to fitting residuals with a single-split regressor.

Exercise 5. Explain mathematically why early stopping in gradient boosting acts as regularization (relate to the number of gradient descent steps).