Functional Gradient Descent

Standard machine learning algorithms, like linear regression or neural networks with fixed architectures, often optimize by finding the best set of parameters $\theta$ for a predefined model structure $f(x; \theta)$. Techniques like gradient descent are used to iteratively update these parameters to minimize a loss function $L(y, f(x; \theta))$ averaged over the training data. The update rule typically looks like $\theta_{new} = \theta_{old} - \eta \nabla_{\theta} L$, where $\nabla_{\theta} L$ is the gradient of the loss with respect to the parameters.

Gradient Boosting Machines (GBMs) approach optimization from a different perspective. Instead of optimizing parameters within a fixed model structure, GBMs build the model itself iteratively. The "parameter" we are optimizing is the entire function $F(x)$ representing the ensemble. We are searching through the space of possible functions to find the one that best minimizes the overall loss on the training data. This optimization process can be understood as performing gradient descent in function space.

Optimization in Function Space

Imagine a high-dimensional space where each point corresponds to a specific function $F$. Our goal is to find the function $F^*$ in this space that minimizes the total loss over our dataset $(x_i, y_i)$ for $i=1, \dots, N$:

$$L_{total}(F) = \sum_{i=1}^{N} L(y_i, F(x_i))$$

Just like in parameter space, we want to iteratively improve our current estimate of the optimal function. Let $F_{m-1}(x)$ be our current ensemble model after $m-1$ boosting iterations. We want to find a new function $h_m(x)$ (our base learner, typically a decision tree) such that adding it to the current model moves us closer to the minimum loss. That is, we want:

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

where $\eta$ is a step size (the learning rate), and $h_m(x)$ points in a direction that reduces the loss $L_{total}$.

The Gradient Direction

In standard gradient descent, the negative gradient $-\nabla_{\theta} L$ tells us the direction in parameter space that leads to the steepest decrease in loss. What is the equivalent in function space?

We can think of the predictions $F(x_i)$ for each training sample $i$ as the "coordinates" defining our current position in function space. The gradient of the total loss $L_{total}$ with respect to these coordinates is a vector where the $i$-th component is the partial derivative of the individual loss term $L(y_i, F(x_i))$ with respect to the model's prediction $F(x_i)$, evaluated at the current model $F_{m-1}$:

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

This vector $(g_{1m}, g_{2m}, \dots, g_{Nm})$ represents the direction of steepest ascent for the total loss in function space at the point defined by $F_{m-1}$.

Pseudo-Residuals: The Target for Base Learners

To minimize the loss, we need to move in the direction opposite to the gradient. We define the negative gradient components, often called pseudo-residuals, for each sample $i$ at iteration $m$:

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

These pseudo-residuals $r_{im}$ represent the target values that our next base learner $h_m(x)$ should approximate. Why "pseudo-residuals"?

Consider the case of regression with Squared Error loss: $L(y, F(x)) = \frac{1}{2}(y - F(x))^2$. The gradient component is:

$$\frac{\partial L(y_i, F(x))}{\partial F(x)} = \frac{\partial}{\partial F(x)} \left( \frac{1}{2}(y_i - F(x))^2 \right) = -(y_i - F(x))$$

Evaluating this at $F_{m-1}(x_i)$ gives $-(y_i - F_{m-1}(x_i))$. The negative gradient is therefore:

$$r_{im} = - [-(y_i - F_{m-1}(x_i))] = y_i - F_{m-1}(x_i)$$

In this specific case, the pseudo-residuals are exactly the ordinary residuals (the difference between the true value and the current model's prediction). For other loss functions, $r_{im}$ is not the simple residual but still represents the direction (in function space, evaluated pointwise) where the current model $F_{m-1}$ needs the most improvement.

Taking the Step

We cannot directly "add" the vector of pseudo-residuals $(r_{1m}, \dots, r_{Nm})$ to our function $F_{m-1}(x)$. Instead, we fit a base learner $h_m(x)$ to predict these pseudo-residuals based on the input features $x_i$:

$$h_m = \arg \min_{h} \sum_{i=1}^{N} (r_{im} - h(x_i))^2$$

This base learner $h_m(x)$ provides an approximation of the desired negative gradient step across the entire input domain, not just at the training points.

Finally, we update our ensemble model by adding this new learner, scaled by the learning rate $\eta$:

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

This update performs an approximate gradient descent step in function space. By iteratively computing pseudo-residuals based on the current ensemble's errors and fitting new base learners to these pseudo-residuals, the GBM algorithm progressively minimizes the overall loss function. This functional gradient view provides a powerful unifying framework for understanding how gradient boosting works across different loss functions and base learners.