Gradient Boosting (XGBoost/LightGBM)

What is Gradient Boosting?

Gradient Boosting (Jerome Friedman, 2001) is widely considered the most powerful algorithm for tabular data.

Instead of reweighting data samples like AdaBoost, Gradient Boosting performs Gradient Descent in Function Space:

Each new decision tree is trained to predict the Negative Gradient (Residual Errors) of the current ensemble loss function!

  Step 0: Initial Base Prediction F_0(x) = Mean(y)
       │
       ▼
  Compute Pseudo Residuals: r_i = y_i - F_0(x_i)
       │
       ▼
  Fit Tree h_1(x) to Residuals r_i
       │
       ▼
  Update Ensemble: F_1(x) = F_0(x) + learning_rate * h_1(x)
       │
       ▼
  Repeat for M steps until loss reaches minimum!

Step-by-Step Mathematical Formulation

Given training data ${ (x_i, y_i) }_{i=1}^N$ and a differentiable loss function $L(y, F(x))$:

Step 1: Initialize Constant Model

$$F_0(x) = \arg\min_{\gamma} \sum_{i=1}^N L(y_i, \gamma)$$

For Mean Squared Error, $F_0(x)$ is simply the mean of target values $\bar{y}$.

Step 2: Sequential Boosting Loop (for $m = 1 \dots M$)

1. Compute Pseudo Residuals (Negative Gradients):

$$r_{im} = -\left[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right]{F(x) = F{m-1}(x)}$$

For Mean Squared Error $L = \frac{1}{2}(y - F(x))^2$, the negative gradient is simply the raw residual difference $r_{im} = y_i - F_{m-1}(x_i)$.

2. Fit Decision Tree: Train a shallow decision tree $h_m(x)$ to predict pseudo residuals $r_{im}$.

3. Update Ensemble Model with Shrinkage:

$$F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)$$

Where $\eta$ is the Learning Rate (Shrinkage Factor), typically set between $0.01$ and $0.1$.

Why Gradient Boosting Dominates Tabular Benchmarks

1. Flexible Loss Functions: Can optimize any differentiable loss function (MSE, Log Loss, Focal Loss, Huber Loss, Poisson Loss).
2. Handles Missing Values & Outliers: Decision trees handle non linear interactions, missing values, and un-scaled features naturally.
3. High Precision: Sequential residual fitting builds high precision decision boundaries unmatched by single models.

Say this out loud

Gradient Boosting builds decision trees sequentially to minimize a differentiable loss function. Each new tree fits the negative loss gradient (pseudo residuals) of previous predictions. Shrinkage scales new tree updates by a learning rate like 0.1, preventing overfitting and achieving state of the art predictions on tabular data.

Followups to expect

1. What is Second Order Gradient Boosting (Newton Boosting)? Optimizing trees using both first order gradients g_i and second order Hessian matrices h_i via Taylor expansion, used in XGBoost for faster convergence.
2. Why is early stopping critical in Gradient Boosting? Because boosting sequentially fits errors, training too many trees eventually fits noise in training samples. Monitor validation loss and stop adding trees when validation loss stops improving.