The Regularized Learning Objective

A significant enhancement XGBoost introduces over traditional Gradient Boosting Machines (GBMs) lies in its objective function. While standard GBM minimizes a loss function iteratively, XGBoost incorporates regularization directly into the objective being optimized at each step. This approach provides more direct control over model complexity, helping to prevent overfitting from the ground up.

Recall that gradient boosting builds an ensemble model additively. At step $t$, we add a new tree $f_t(x)$ to the prediction from the previous step $\hat{y}^{(t-1)}$:

$$\hat{y}^{(t)} = \hat{y}^{(t-1)} + \eta f_t(x)$$

where $\eta$ is the learning rate (often called eta or learning_rate in XGBoost). XGBoost aims to find the tree $f_t$ that optimizes the following objective function at step $t$:

$$Obj^{(t)} = \sum_{i=1}^n l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \sum_{k=1}^t \Omega(f_k)$$

Here, $l(y_i, \hat{y}_i)$ is the differentiable loss function (e.g., squared error for regression, log loss for classification) measuring the discrepancy between the true label $y_i$ and the prediction $\hat{y}_i$ for the $i$-th training instance. $\Omega(f_k)$ represents a regularization term for the $k$-th tree, penalizing its complexity.

Since the regularization terms for trees $f_1, ..., f_{t-1}$ are constant at step $t$, we can simplify the objective for finding the best $f_t$:

$$Obj^{(t)} \approx \sum_{i=1}^n l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t)$$

Optimizing this objective directly for a general tree structure $f_t$ is computationally challenging. XGBoost employs a clever strategy using a second-order Taylor expansion of the loss function around the current prediction $\hat{y}_i^{(t-1)}$.

Taylor Expansion for a Tractable Objective

The Taylor expansion of the loss $l$ around $\hat{y}_i^{(t-1)}$ is:

$$l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) \approx l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t(x_i)^2$$

where $g_i$ and $h_i$ are the first and second-order derivatives (gradient and Hessian) of the loss function $l$ evaluated at the previous prediction $\hat{y}_i^{(t-1)}$:

$$g_i = \frac{\partial l(y_i, \hat{y})}{\partial \hat{y}} \bigg|_{\hat{y}=\hat{y}_i^{(t-1)}}$$ $$h_i = \frac{\partial^2 l(y_i, \hat{y})}{\partial \hat{y}^2} \bigg|_{\hat{y}=\hat{y}_i^{(t-1)}}$$

Using the second-order approximation provides more information about the loss function's shape compared to just using the gradient (as in traditional GBM), often leading to faster convergence and better accuracy, especially for custom loss functions.

Removing the constant term $l(y_i, \hat{y}_i^{(t-1)})$ (which doesn't affect the optimization of $f_t$), the objective function to minimize at step $t$ becomes:

$$Obj^{(t)} \approx \sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t(x_i)^2] + \Omega(f_t)$$

This approximated objective is now expressed in terms of the gradients $g_i$, Hessians $h_i$, and the new tree $f_t$ we need to determine.

The XGBoost Regularization Term

XGBoost defines the regularization term $\Omega(f_t)$ specifically for decision trees. Let a tree $f_t$ be defined by its structure (which maps an input $x_i$ to a leaf node) and the weights (prediction scores) $w_j$ assigned to each leaf $j$. If the tree has $T$ leaves, the XGBoost regularization term is:

$$\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2$$

This term consists of two parts:

1. $\gamma T$: A penalty proportional to the number of leaves $T$. Higher values of $\gamma$ (gamma, gamma parameter) make the algorithm more conservative, requiring a larger loss reduction to justify adding a new leaf (i.e., making a split). This acts similarly to pruning but is incorporated directly into the objective. It can be seen as a form of $L_0$ regularization on the number of leaves.
2. $\frac{1}{2} \lambda \sum_{j=1}^T w_j^2$: An $L_2$ regularization penalty on the leaf weights $w_j$. Higher values of $\lambda$ (lambda, reg_lambda parameter) shrink the leaf weights towards zero, making the model less sensitive to individual observations and reducing the influence of any single tree.

XGBoost also supports $L_1$ regularization on weights ($\alpha \sum |w_j|$, controlled by the reg_alpha parameter), which can induce sparsity in the weights. The full regularization term can be $\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum w_j^2 + \alpha \sum |w_j|$. We focus here on the more commonly discussed $\gamma$ and $\lambda$ terms.

Deriving the Optimal Leaf Weights and Structure Score

Let's incorporate the regularization term into our approximated objective. We define $I_j = \{i | q(x_i) = j\}$ as the set of indices of training instances that fall into leaf $j$, where $q(x)$ represents the tree structure mapping an instance to a leaf index. The prediction $f_t(x_i)$ for an instance $x_i$ in leaf $j$ is simply the leaf weight $w_j$. Substituting this and $\Omega(f_t)$ into the objective:

$$Obj^{(t)} \approx \sum_{i=1}^n [g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2$$

We can group the summation by the leaves of the tree:

$$Obj^{(t)} \approx \sum_{j=1}^T [ (\sum_{i \in I_j} g_i) w_j + \frac{1}{2} (\sum_{i \in I_j} h_i) w_j^2 ] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2$$

Rearranging terms:

$$Obj^{(t)} \approx \sum_{j=1}^T [ (\sum_{i \in I_j} g_i) w_j + \frac{1}{2} (\sum_{i \in I_j} h_i + \lambda) w_j^2 ] + \gamma T$$

Let $G_j = \sum_{i \in I_j} g_i$ be the sum of gradients and $H_j = \sum_{i \in I_j} h_i$ be the sum of Hessians for the instances in leaf $j$. The objective becomes:

$$Obj^{(t)} \approx \sum_{j=1}^T [ G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 ] + \gamma T$$

Now, for a fixed tree structure $q$ (which determines $T$ and the sets $I_j$), this objective is a sum of independent quadratic functions of the leaf weights $w_j$. We can find the optimal weight $w_j^*$ for each leaf by setting the derivative with respect to $w_j$ to zero:

$$\frac{\partial Obj^{(t)}}{\partial w_j} = G_j + (H_j + \lambda) w_j = 0$$

Solving for $w_j$:

$$w_j^* = - \frac{G_j}{H_j + \lambda}$$

This formula gives the optimal prediction score for each leaf in a given tree structure. It balances the sum of gradients (desired change) against the sum of Hessians (curvature of the loss) plus the $L_2$ regularization term $\lambda$. A larger $\lambda$ shrinks the optimal weight towards zero.

Substituting $w_j^*$ back into the objective function gives the minimum objective value achieved for that specific tree structure $q$:

$$Obj^{(t)}(q) = \sum_{j=1}^T [ G_j (-\frac{G_j}{H_j + \lambda}) + \frac{1}{2} (H_j + \lambda) (-\frac{G_j}{H_j + \lambda})^2 ] + \gamma T$$ $$Obj^{(t)}(q) = \sum_{j=1}^T [ -\frac{G_j^2}{H_j + \lambda} + \frac{1}{2} \frac{G_j^2}{H_j + \lambda} ] + \gamma T$$ $$Obj^{(t)}(q) = -\frac{1}{2} \sum_{j=1}^T \frac{G_j^2}{H_j + \lambda} + \gamma T$$

This final expression is extremely important. It provides a score for a tree structure $q$. XGBoost uses this scoring function during tree construction to evaluate the quality of potential splits. The algorithm greedily chooses splits that maximize the reduction in this objective score. The "gain" of a split is calculated as the score of the parent node minus the combined scores of the resulting child nodes, minus the complexity cost $\gamma$ for adding a new leaf.

Summary

The regularized learning objective is a foundation of XGBoost's effectiveness. By incorporating $L_1$ and $L_2$ penalties ($\alpha$, $\lambda$) and a tree complexity penalty ($\gamma$) directly into the objective function, and by using a second-order Taylor expansion involving gradients ($g_i$) and Hessians ($h_i$), XGBoost achieves several advantages:

• Direct Complexity Control: Regularization is part of the optimization goal, not just an afterthought.
• Generality: The use of gradients and Hessians allows the framework to work with various differentiable loss functions easily.
• Efficient Tree Building: The derived objective score provides a principled way to evaluate and choose splits during tree construction, directly optimizing the regularized objective.

This sophisticated objective function sets the stage for the efficient split-finding algorithms and system optimizations that further distinguish XGBoost, which we will explore next.