Loss Functions for Boosting

Squared loss is elegant, well-behaved, and computationally convenient. But it has an Achilles' heel: extreme sensitivity to outliers. A single data point with a prediction error of 100 contributes as much to the loss as 10,000 points with errors of 1. In real-world datasets—riddled with measurement errors, data entry mistakes, and genuine anomalies—this sensitivity can be catastrophic.

Enter the absolute loss (also called L1 loss, LAD loss for Least Absolute Deviation, or Mean Absolute Error when averaged). Instead of squaring the error, we simply take its absolute value:

$$L(y, \hat{y}) = |y - \hat{y}|$$

This seemingly minor change has profound consequences. The absolute loss grows linearly with error magnitude—not quadratically. An outlier with error 100 contributes 100 to the loss, not 10,000. This robustness comes at a price: the loss function is not smooth, introducing mathematical and computational challenges that require careful handling.

The absolute loss function measures the absolute difference between predicted and actual values:

$$L(y, \hat{y}) = |y - \hat{y}|$$

For a dataset of $n$ observations, the total loss is:

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

Key Properties:

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

2. Symmetry: Like squared loss, the penalty is symmetric: $L(y, y+\epsilon) = L(y, y-\epsilon)$.

3. Convexity: The function is convex (though not strictly convex everywhere), ensuring a global minimum exists.

4. Non-smoothness: The function has a "kink" at $y = \hat{y}$ where it's not differentiable. This is the source of mathematical complexity.

5. Linear Growth: Errors grow linearly with magnitude, unlike the quadratic growth of squared loss.

Visual Comparison:

Imagine the loss surface as a function of prediction $\hat{y}$ for fixed $y$:

• Squared loss: A smooth parabola with minimum at $\hat{y} = y$. The curvature (second derivative = 1) is constant everywhere.

• Absolute loss: A V-shaped function with its vertex at $\hat{y} = y$. Constant slope of -1 for $\hat{y} < y$ and +1 for $\hat{y} > y$. The "kink" at the vertex is where the derivative doesn't exist.

This V-shape has two important implications:

1. The gradient is constant (±1) regardless of how close we are to the target
2. At the target, the gradient is undefined (but we're at the minimum, so this is okay)

For gradient boosting to work, we need the gradient of the loss with respect to predictions. Let's compute it carefully.

Case 1: $\hat{y} < y$ (underprediction)

$$L = y - \hat{y}$$ $$\frac{\partial L}{\partial \hat{y}} = -1$$

Case 2: $\hat{y} > y$ (overprediction)

$$L = \hat{y} - y$$ $$\frac{\partial L}{\partial \hat{y}} = +1$$

Case 3: $\hat{y} = y$ (exact match)

The derivative doesn't exist! The function has a corner.

Combining Cases:

We can write this compactly using the sign function:

$$\frac{\partial L}{\partial \hat{y}} = \text{sign}(\hat{y} - y) = \begin{cases} -1 & \text{if } \hat{y} < y \ 0 & \text{if } \hat{y} = y \ +1 & \text{if } \hat{y} > y \end{cases}$$

The choice of 0 at $\hat{y} = y$ is the standard convention, though any value in $[-1, 1]$ is a valid subgradient.

The Pseudo-Residual for Absolute Loss:

In gradient boosting, we fit to the negative gradient:

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

Unlike squared loss where residuals are continuous values, absolute loss residuals are discrete: they're always -1, 0, or +1!

Interpretation:

• $r_i = +1$: We're underpredicting; move prediction up
• $r_i = -1$: We're overpredicting; move prediction down
• $r_i = 0$: Perfect prediction; no update needed

The magnitude of the error doesn't matter—only its direction. A prediction that's off by 1 receives the same pseudo-residual as one that's off by 1,000. This is the source of both the robustness (outliers don't dominate) and the challenge (we lose information about error magnitude).

When building trees for gradient boosting, we need to determine the optimal prediction for each leaf. For absolute loss, this requires solving:

$$w_j^* = \arg\min_w \sum_{i \in I_j} |y_i - (F_{m-1}(x_i) + w)|$$

Let $r_i = y_i - F_{m-1}(x_i)$ be the residual. We're finding:

$$w_j^* = \arg\min_w \sum_{i \in I_j} |r_i - w|$$

Theorem: The value $w^*$ that minimizes the sum of absolute deviations is the median of the values ${r_i : i \in I_j}$.

Proof Sketch:

Consider moving $w$ from below the median to above it. Each residual $r_i < w$ contributes $w - r_i$ to the loss, and each $r_i > w$ contributes $r_i - w$.

• Moving $w$ up by $\delta$ decreases the contribution from points above $w$ by $\delta$ per point
• Moving $w$ up by $\delta$ increases the contribution from points below $w$ by $\delta$ per point

If more points are above $w$ than below, moving up decreases total loss. If more are below, moving down decreases loss. The optimum is where these balance—the median!

Computational Implications:

Computing the median is O(n) using selection algorithms (or O(n log n) with sorting), compared to O(n) for the mean. This makes leaf value computation slightly more expensive.

Weighted Median:

In practice, samples may have weights (from subsampling, cross-validation, etc.). The optimal leaf value becomes the weighted median: the value where cumulative weight on each side is equal.

Example:

Suppose a leaf contains residuals: ${-5, -2, 1, 3, 100}$

• Mean (squared loss): $(-5 - 2 + 1 + 3 + 100)/5 = 19.4$
• Median (absolute loss): 1 (the middle value)

The outlier (100) pulls the mean far from most data points. The median is unaffected. This illustrates why absolute loss is robust.

Just as squared loss estimtes the conditional mean, absolute loss estimates the conditional median.

Theorem: Among all functions of $X$, the conditional median minimizes expected absolute error:

$$\text{Med}[Y|X] = \arg\min_{f(X)} \mathbb{E}[|Y - f(X)|]$$

Why Median Instead of Mean?

The median has a remarkable property: it's the value that minimizes the sum of absolute deviations. This is why:

1. Robustness: The median is a robust estimator. Moving one observation to infinity changes the mean unboundedly but doesn't change the median.

2. Breakdown Point: The median has a breakdown point of 50%—you can corrupt up to half the data before the estimate breaks down. The mean has a breakdown point of 0%—a single outlier can move it arbitrarily.

3. Skewed Distributions: For skewed distributions, the median better represents the "typical" value than the mean.

Connection to Quantile Regression:

Absolute loss is a special case of quantile loss, used to predict the $\tau$-th quantile of the distribution:

$$L_\tau(y, \hat{y}) = \begin{cases} \tau(y - \hat{y}) & \text{if } y > \hat{y} \ (1-\tau)(\hat{y} - y) & \text{if } y \leq \hat{y} \end{cases}$$

For $\tau = 0.5$ (the median), this simplifies to:

$$L_{0.5}(y, \hat{y}) = 0.5|y - \hat{y}|$$

which is just half the absolute loss. Different $\tau$ values let you predict different quantiles:

• $\tau = 0.1$: 10th percentile (conservative lower bound)
• $\tau = 0.5$: Median (typical value)
• $\tau = 0.9$: 90th percentile (conservative upper bound)

This extends absolute loss to quantile regression, useful for prediction intervals and risk assessment.

Robustness can be formalized through influence functions, which measure how much an estimator changes when we add an observation at a particular value.

Influence Function for Mean (Squared Loss):

$$IF(y; \bar{y}) = y - \bar{y}$$

The influence grows unboundedly as $|y|$ increases. An observation at $y = 10^9$ has an influence proportional to $10^9$.

Influence Function for Median (Absolute Loss):

$$IF(y; \text{med}) = \text{sign}(y - \text{med})$$

The influence is bounded—it's always either -1, 0, or +1, regardless of how extreme $y$ is. An observation at $y = 10^9$ has the same influence as one at $y = 2 \cdot \text{med}$.

Practical Implications:

When training with absolute loss:

• Outliers contribute to the gradient with magnitude 1, same as normal points
• No single point can dominate the optimization
• The model focuses on getting the majority of points right
• Extreme predictions don't get disproportionate correction

Empirical Comparison:

Consider training on data with 5% outliers (residuals 10× larger than typical):

Squared loss sacrifices accuracy on the majority to reduce error on outliers. Absolute loss does the opposite—it maintains accuracy on the majority at the cost of larger errors on outliers.

Which is better depends on your application:

• If outliers represent real phenomena you care about → squared loss
• If outliers are noise you want to ignore → absolute loss

Absolute loss introduces computational challenges not present in squared loss:

1. Non-differentiability at Zero:

When $\hat{y} = y$, the gradient is undefined. Implementations must handle this:

• Use 0 as the subgradient when residual is exactly zero (common convention)
• Add small epsilon to residuals to avoid exact zeros
• Use smooth approximations (see Huber loss, next page)

2. Leaf Value Computation:

Finding the median is O(n log n) with sorting or O(n) with selection algorithms:\n

• Sorting-based: Sort residuals, take middle value. Simple but slower.
• Quickselect: Average O(n), worst case O(n²). Faster in practice.
• Median of medians: Guaranteed O(n), complex to implement.

Most implementations use quickselect, falling back to sorting for small leaves.

3. No Closed-Form Hessian:

The second derivative is zero everywhere except at zero, where it's undefined (a Dirac delta function). XGBoost-style second-order methods cannot directly use absolute loss.

Workaround: Use a small constant (e.g., 1) as the Hessian approximation, which makes the algorithm behave like first-order gradient descent.

The constant gradient magnitude (always ±1) leads to different convergence behavior compared to squared loss.

Early Iterations:

With squared loss, residuals start large and provide strong gradients. As predictions improve, gradients shrink, naturally reducing the step size near convergence.

With absolute loss, gradients are always ±1 regardless of residual size. Early iterations don't automatically take larger steps.

Near Convergence:

Squared loss: Gradients shrink to zero as predictions approach targets. Convergence is smooth.

Absolute loss: Gradients remain ±1 even for small residuals. The algorithm may "oscillate" around the optimum, taking steps that overshoot.

Implications:

1. Learning rate matters more: With constant gradients, the learning rate solely determines step size. Too large → oscillation. Too small → slow convergence.

2. Line search helps: Adaptive step size selection (line search) is more valuable for absolute loss than squared loss.

3. Early stopping: Since the loss doesn't plateau as smoothly, early stopping based on validation loss is crucial.

Loss Curve Characteristics:

Squared loss training curves often show smooth exponential decay. Absolute loss curves can be:

• More jagged (discrete gradients cause quantized updates)
• Less smooth near convergence
• Sometimes plateau then drop (median jumps when point crosses threshold)

Best Practices for Absolute Loss:

1. Use more trees with smaller learning rate
2. Enable early stopping with patience
3. Consider line search if available
4. Monitor both training and validation loss carefully
5. Compare against squared loss baseline

We've thoroughly explored the absolute loss function as a robust alternative to squared loss. Let's consolidate the key insights:

What's Next:

Squared loss is ideal for clean data; absolute loss handles contamination. But what if you want the best of both? The next page introduces Huber Loss—a smooth compromise that behaves like squared loss for small errors (efficiency) and like absolute loss for large errors (robustness). This hybrid approach often achieves better results than either extreme alone.