Loss Functions for Boosting

At the heart of every gradient boosting algorithm lies a deceptively simple question: how do we measure prediction error? This measurement—the loss function—is far more than a mathematical nicety. It fundamentally shapes how the algorithm learns, what patterns it prioritizes, and how robust the final model is to different data characteristics.

The squared loss (also called L2 loss, quadratic loss, or mean squared error) is the most natural starting point. It's the loss function most practitioners reach for first, the default in virtually every boosting library, and the one whose behavior most closely matches our intuition about "prediction error."

Yet beneath this simplicity lies remarkable depth. Understanding squared loss thoroughly—its gradients, its Hessian, its sensitivity characteristics, its connection to conditional expectation—provides the conceptual scaffolding for understanding every other loss function in gradient boosting.

The squared loss function measures the squared difference between predicted and actual values. For a single observation with true value $y$ and prediction $\hat{y}$:

$$L(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2$$

The factor of $\frac{1}{2}$ is a convenience that simplifies the gradient, as we'll soon see. Some formulations omit it, which affects only the scale of gradients.

For a dataset of $n$ observations, the total loss (or empirical risk) is:

$$\mathcal{L}(F) = \sum_{i=1}^{n} L(y_i, F(x_i)) = \frac{1}{2}\sum_{i=1}^{n}(y_i - F(x_i))^2$$

Where $F(x)$ is our prediction function, which in gradient boosting is an additive ensemble:

$$F(x) = \sum_{m=0}^{M} f_m(x)$$

Key Properties of Squared Loss:

1. Non-negativity: $L(y, \hat{y}) \geq 0$ for all $y, \hat{y}$, with equality only when $\hat{y} = y$.

2. Symmetry: The penalty is the same whether we overpredict or underpredict by the same amount: $L(y, y+\epsilon) = L(y, y-\epsilon)$.

3. Convexity: The function is strictly convex in $\hat{y}$, guaranteeing a unique global minimum and enabling efficient optimization.

4. Smoothness: The loss is infinitely differentiable—no kinks, corners, or discontinuities—which enables gradient-based optimization.

5. Quadratic Growth: Errors grow quadratically with the magnitude of the residual. A prediction that's 10 units off is penalized 100 times more than one that's 1 unit off.

Gradient boosting performs optimization in function space. At each iteration, we add a new base learner that moves our prediction in the direction of steepest descent on the loss surface. To do this, we need the gradient of the loss with respect to the prediction.

Computing the Gradient:

For squared loss $L(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2$, we compute:

$$\frac{\partial L}{\partial \hat{y}} = \frac{\partial}{\partial \hat{y}} \left[ \frac{1}{2}(y - \hat{y})^2 \right]$$

Applying the chain rule:

$$\frac{\partial L}{\partial \hat{y}} = \frac{1}{2} \cdot 2 \cdot (y - \hat{y}) \cdot (-1) = -(y - \hat{y}) = \hat{y} - y$$

The Negative Gradient (Pseudo-Residual):

In gradient boosting, we fit the base learner to the negative gradient:

$$r_i = -\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} = y_i - F(x_i)$$

This is precisely the residual—the difference between the true value and our current prediction!

Gradient Boosting Update with Squared Loss:

The gradient boosting algorithm with squared loss proceeds as:

1. Initialize: $F_0(x) = \bar{y}$ (the mean of training targets)

2. For $m = 1, 2, \ldots, M$:

   • Compute residuals: $r_i^{(m)} = y_i - F_{m-1}(x_i)$
   • Fit base learner $h_m(x)$ to residuals $(x_i, r_i^{(m)})$
   • Update: $F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)$

3. Return: $F_M(x)$

Where $\eta$ is the learning rate (shrinkage parameter).

Why This Works:

Each base learner $h_m$ learns to correct the errors of the current ensemble. If $F_{m-1}(x_i)$ underpredicts (residual positive), $h_m$ learns to predict a positive value for $x_i$. Adding this correction moves the ensemble prediction closer to the target.

Over many iterations, the residuals shrink (ideally toward zero), and the ensemble converges to an excellent approximation of the conditional expectation $\mathbb{E}[Y|X]$.

Modern boosting implementations like XGBoost and LightGBM use not just the gradient but also the Hessian (second derivative) of the loss function. This additional information enables more sophisticated tree construction and optimal leaf value computation.

Computing the Hessian:

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

$$\frac{\partial^2 L}{\partial \hat{y}^2} = \frac{\partial}{\partial \hat{y}}(\hat{y} - y) = 1$$

The Hessian of squared loss is constant (always 1)! This has profound implications:

Implications of Constant Hessian:

1. Uniform Curvature: The loss surface has the same curvature everywhere—a perfect parabola. There are no flat regions where gradients vanish and no steep cliffs where optimization becomes numerically difficult.

2. Optimal Step Size: Since curvature is constant, a single learning rate works equally well for all predictions. There's no need for adaptive step sizes.

3. Simple Leaf Weights: In XGBoost, the optimal leaf weight for samples in a leaf is:

$$w^* = -\frac{\sum_i g_i}{\sum_i h_i + \lambda}$$

Where $g_i$ is the gradient and $h_i$ is the Hessian for sample $i$. For squared loss, $h_i = 1$ for all samples, so:

$$w^* = -\frac{\sum_i g_i}{n_{\text{leaf}} + \lambda} = \frac{\sum_i (y_i - F(x_i))}{n_{\text{leaf}} + \lambda}$$

This is simply the (regularized) mean of residuals in the leaf!

Taylor Expansion View:

XGBoost approximates the loss using a second-order Taylor expansion around the current prediction $F_{m-1}(x_i)$:

$$L(y_i, F_{m-1}(x_i) + f_m(x_i)) \approx L(y_i, F_{m-1}(x_i)) + g_i f_m(x_i) + \frac{1}{2}h_i f_m(x_i)^2$$

Where:

• $g_i = \frac{\partial L}{\partial F}|{F=F{m-1}(x_i)} = F_{m-1}(x_i) - y_i$ (gradient)
• $h_i = \frac{\partial^2 L}{\partial F^2}|{F=F{m-1}(x_i)} = 1$ (Hessian)

For squared loss, this expansion is exact (not an approximation) because squared loss is a quadratic function. This exactness makes squared loss particularly well-suited for optimization.

Squared loss has a deep connection to statistical estimation. Minimizing squared loss is equivalent to estimating the conditional expectation of $Y$ given $X$.

Theorem (Conditional Mean Minimizes Squared Error):

For any random variable $Y$ with finite variance:

$$\mathbb{E}[Y|X] = \arg\min_{c(X)} \mathbb{E}[(Y - c(X))^2]$$

In words: among all functions of $X$, the one that minimizes expected squared error is the conditional mean $\mathbb{E}[Y|X]$.

Proof Sketch:

Let $f(X)$ be any function. Then:

$$\mathbb{E}[(Y - f(X))^2] = \mathbb{E}[(Y - \mathbb{E}[Y|X] + \mathbb{E}[Y|X] - f(X))^2]$$

Expanding and using the property that $\mathbb{E}[(Y - \mathbb{E}[Y|X])|X] = 0$:

$$= \mathbb{E}[(Y - \mathbb{E}[Y|X])^2] + \mathbb{E}[(\mathbb{E}[Y|X] - f(X))^2]$$

The first term is the irreducible variance $\text{Var}(Y|X)$. The second term is minimized (equals zero) when $f(X) = \mathbb{E}[Y|X]$.

Connection to Maximum Likelihood:

Squared loss also arises from maximum likelihood estimation under Gaussian errors. If we assume:

$$Y = f(X) + \epsilon, \quad \epsilon \sim \mathcal{N}(0, \sigma^2)$$

The log-likelihood is:

$$\log p(y|x, f, \sigma) = -\frac{1}{2\sigma^2}(y - f(x))^2 - \log(\sigma\sqrt{2\pi})$$

Maximizing this log-likelihood is equivalent to minimizing squared loss! The Gaussian assumption justifies squared loss when:

1. Errors are symmetric around zero
2. Large errors are exponentially unlikely
3. Error variance is constant across the feature space

When These Assumptions Fail:

• Heavy-tailed errors: Squared loss is too sensitive to outliers
• Asymmetric errors: Underprediction and overprediction may have different costs
• Heteroscedastic errors: Error variance changes with $X$

In these cases, alternative loss functions (covered in subsequent pages) may be more appropriate.

Before gradient boosting begins iterating, we need an initial prediction $F_0(x)$. The optimal initialization minimizes the loss over a constant:

$$F_0 = \arg\min_c \sum_{i=1}^{n} L(y_i, c)$$

For Squared Loss:

$$F_0 = \arg\min_c \sum_{i=1}^{n} \frac{1}{2}(y_i - c)^2$$

Taking the derivative and setting to zero:

$$\frac{d}{dc} \left[ \frac{1}{2}\sum_{i=1}^{n}(y_i - c)^2 \right] = -\sum_{i=1}^{n}(y_i - c) = 0$$

Solving:

$$nc = \sum_{i=1}^{n} y_i \implies c = \frac{1}{n}\sum_{i=1}^{n} y_i = \bar{y}$$

The optimal initial prediction is the sample mean!

This makes intuitive sense: with no feature information, our best guess for any observation is the average target value.

Effect on First Iteration:

With $F_0 = \bar{y}$, the initial residuals are:

$$r_i^{(1)} = y_i - \bar{y}$$

These are the centered targets—deviations from the mean. The first tree learns to predict which observations are above or below average, and by how much.

Variance Decomposition:

The total variance of $y$ can be decomposed as:

$$\text{Var}(y) = \mathbb{E}[(y - \bar{y})^2] = \underbrace{\mathbb{E}[(y - F_M(x))^2]}{\text{Residual variance}} + \underbrace{\mathbb{E}[(F_M(x) - \bar{y})^2]}{\text{Explained variance}}$$

As boosting progresses, the residual variance decreases while explained variance increases. The ratio (explained/total) is the $R^2$ score, a key metric for regression model quality.

The learning rate $\eta$ (also called shrinkage) controls how much each tree contributes to the ensemble:

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

Why Use Shrinkage with Squared Loss?

Even though the gradient direction is exact for squared loss, taking full steps ($\eta = 1$) often leads to overfitting. Shrinkage provides implicit regularization by:

1. Requiring More Trees: Smaller learning rate means more trees needed to achieve the same training loss, allowing each tree to be simpler.

2. Averaging Effect: More trees with smaller contributions lead to smoother predictions, similar to ensemble averaging.

3. Slower Convergence: The model has more opportunities to correct errors gradually, reducing the impact of noise.

Empirical Evidence:

Extensive experiments by Friedman (2001) showed that shrinkage improves generalization:

"Using a small learning rate combined with more iterations is always a better strategy than using a larger learning rate with fewer iterations."

Squared loss has favorable computational properties that make it efficient to optimize in gradient boosting frameworks.

1. Cheap Gradient Computation:

The gradient $(\hat{y} - y)$ requires only a single subtraction per sample—O(n) for the entire dataset. No exponentials, logarithms, or other expensive operations.

2. Constant Hessian:

With Hessian = 1, there's no need for per-sample second derivative computation. This simplifies tree construction in XGBoost-style implementations.

3. Simple Leaf Value:

The optimal leaf value is the mean of residuals in that leaf:

$$w_j^* = \frac{1}{|I_j|} \sum_{i \in I_j} r_i$$

This is O(|Ij|) per leaf, computed efficiently during tree construction.

4. Additive Structure:

Squared loss decomposes additively over samples:

$$\mathcal{L} = \sum_{i=1}^{n} L_i$$

This enables parallelization across samples for gradient computation and distributed training.

Memory Efficiency:

Since the Hessian is constant, implementations can avoid storing per-sample Hessians, saving n × 8 bytes (for 64-bit floats). This matters for large datasets:

Modern implementations recognize squared loss and skip Hessian storage automatically.

SIMD Optimization:

The simple gradient formula $(\hat{y} - y)$ is trivially vectorizable. Modern CPUs can compute 4-8 gradients per cycle using SIMD instructions, making squared loss gradient computation memory-bound rather than compute-bound.

We've established squared loss as the foundational loss function for regression-based gradient boosting. Let's consolidate the key insights:

What's Next:

Squared loss excels when errors are roughly Gaussian and outliers are rare. But real-world data often violates these assumptions. The next page explores Absolute Loss (L1 loss)—a robust alternative that targets the conditional median instead of the mean, dramatically reducing sensitivity to outliers while maintaining the elegant structure of gradient boosting.