Boosting as Gradient Descent

Imagine you're an artist creating a portrait through layered glazes. You don't attempt to capture every detail in the first layer; instead, you build the image incrementally. The first glaze establishes broad tones. The second refines shadows. Each subsequent layer addresses what previous layers missed.

This is precisely how stage-wise optimization builds boosted ensembles. We don't attempt to find the globally optimal combination of M base learners—a computationally intractable problem. Instead, we construct the ensemble one term at a time, each new learner targeting what the current ensemble gets wrong.

This greedy approach, known as forward stagewise additive modeling (FSAM), is the algorithmic heart of gradient boosting.

Problem Setup:

We want to build an additive model: $$F_M(x) = \sum_{m=1}^{M} \beta_m h(x; \theta_m)$$

that minimizes the empirical loss: $$L(F) = \sum_{i=1}^{n} \ell(y_i, F(x_i))$$

where h(x; θ) is a base learner parameterized by θ (e.g., a decision tree with structure θ), βₘ are the weights, and ℓ is the loss function.

Joint Optimization (Intractable):

The ideal approach would solve: $${\beta_m^, \theta_m^}{m=1}^{M} = \arg\min \sum{i=1}^{n} \ell\left(y_i, \sum_{m=1}^{M} \beta_m h(x_i; \theta_m)\right)$$

This is generally intractable because:

1. The search space is enormous (M × complexity of each θ)
2. The problem is highly non-convex in θ (tree structures are discrete)
3. All terms are coupled—optimal θ₁ depends on what θ₂...θₘ are

Stagewise Solution:

Instead, we build the model incrementally:

Stage 0: Initialize F₀(x) = γ₀ (often a constant, like the mean for regression)

Stage m (for m = 1, 2, ..., M):

1. Compute the optimal base learner to add: $$(\beta_m, \theta_m) = \arg\min_{\beta, \theta} \sum_{i=1}^{n} \ell(y_i, F_{m-1}(x_i) + \beta \cdot h(x_i; \theta))$$

2. Update the ensemble: $$F_m(x) = F_{m-1}(x) + \beta_m h(x; \theta_m)$$

Key Property: Once added, a base learner is never modified. We only ever add new terms.

At each stage m, we must solve:

$$(\beta_m, \theta_m) = \arg\min_{\beta, \theta} \sum_{i=1}^{n} \ell(y_i, F_{m-1}(x_i) + \beta \cdot h(x_i; \theta))$$

This is still a challenging optimization problem. Let's see how it's approached for different losses.

Case 1: Squared Error Loss (L2 Boosting)

For ℓ(y, F) = ½(y - F)², the stage-m problem becomes:

$$\min_{\beta, \theta} \sum_{i=1}^{n} \frac{1}{2}(y_i - F_{m-1}(x_i) - \beta \cdot h(x_i; \theta))^2$$

Define the residuals: rᵢ = yᵢ - Fₘ₋₁(xᵢ)

The problem becomes: $$\min_{\beta, \theta} \sum_{i=1}^{n} (r_i - \beta \cdot h(x_i; \theta))^2$$

Key Insight: We're fitting the base learner to the residuals! For β = 1, this is exactly least-squares regression of h on r. For optimal β, we can first find optimal θ by fitting to residuals, then optimize β by line search.

Case 2: Exponential Loss (AdaBoost)

For ℓ(y, F) = exp(-y·F) with y ∈ {-1, +1}, the stage-m problem is:

$$\min_{\beta, \theta} \sum_{i=1}^{n} \exp(-y_i(F_{m-1}(x_i) + \beta \cdot h(x_i; \theta)))$$

Let wᵢ⁽ᵐ⁾ = exp(-yᵢFₘ₋₁(xᵢ)). These are the sample weights. The problem becomes:

$$\min_{\beta, \theta} \sum_{i=1}^{n} w_i^{(m)} \exp(-\beta y_i h(x_i; \theta))$$

Solution approach:

1. For any β > 0, the optimal θ minimizes weighted classification error: $$\theta_m = \arg\min_\theta \sum_{i=1}^{n} w_i^{(m)} \mathbf{1}(y_i \neq h(x_i; \theta))$$

2. Given θₘ, the optimal β is: $$\beta_m = \frac{1}{2} \log\left(\frac{1 - \epsilon_m}{\epsilon_m}\right)$$

where εₘ is the weighted error rate of hₘ.

This is exactly the AdaBoost algorithm! Stagewise optimization of exponential loss recovers AdaBoost.

The magic of gradient boosting is that we can solve the stage-m optimization problem approximately using a simple strategy: fit the base learner to the negative gradient.

Key Insight:

Instead of directly solving: $$(\beta_m, \theta_m) = \arg\min_{\beta, \theta} \sum_{i=1}^{n} \ell(y_i, F_{m-1}(x_i) + \beta \cdot h(x_i; \theta))$$

We:

1. Compute the negative functional gradient: $g_i = -\frac{\partial \ell(y_i, F)}{\partial F}\bigg|{F=F{m-1}(x_i)}$
2. Fit h to approximate g: $\theta_m = \arg\min_\theta \sum_{i=1}^{n} (g_i - h(x_i; \theta))^2$
3. (Optionally) Find optimal step size: $\beta_m = \arg\min_\beta \sum_{i=1}^{n} \ell(y_i, F_{m-1}(x_i) + \beta \cdot h(x_i; \theta_m))$

Why This Works:

The Taylor expansion of L(Fₘ₋₁ + βh) around Fₘ₋₁ is: $$L(F_{m-1} + \beta h) \approx L(F_{m-1}) + \beta \sum_{i=1}^{n} \frac{\partial \ell(y_i, F_{m-1}(x_i))}{\partial F} \cdot h(x_i)$$

To decrease loss, we want the inner product between h and ∂ℓ/∂F to be negative (indicating we're moving against the gradient). The h that achieves this best is the one that points in the direction of -∂ℓ/∂F.

We can now state the complete gradient boosting algorithm, synthesizing everything we've developed:

Algorithm: Gradient Boosting

Input: Training data {(xᵢ, yᵢ)}ⁿᵢ₌₁, differentiable loss function ℓ(y, F), number of stages M, learning rate ν, base learner class ℋ

Initialize: F₀(x) = argminγ Σᵢ ℓ(yᵢ, γ) (constant prediction)

For m = 1 to M:

1. Compute negative gradients (pseudo-residuals): $$r_{im} = -\frac{\partial \ell(y_i, F(x_i))}{\partial F(x_i)}\bigg|{F=F{m-1}}$$

2. Fit base learner to pseudo-residuals: $$h_m = \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{n} (r_{im} - h(x_i))^2$$

3. (Optional) Line search for optimal step: $$\rho_m = \arg\min_\rho \sum_{i=1}^{n} \ell(y_i, F_{m-1}(x_i) + \rho \cdot h_m(x_i))$$

4. Update model with shrinkage: $$F_m(x) = F_{m-1}(x) + \nu \cdot \rho_m \cdot h_m(x)$$

Output: Fₘ(x)

The line search step—finding the optimal ρₘ—deserves careful attention. Different implementations handle this differently.

Why Line Search Matters:

The base learner hₘ gives us a direction to update. The step size ρₘ tells us how far to step. Too small steps waste computation; too large steps may overshoot and increase loss.

Simple Approach (No Line Search):

Many implementations skip explicit line search and simply use ρₘ = 1, relying on the learning rate ν for step size control: $$F_m = F_{m-1} + \nu \cdot h_m$$

This works reasonably well when ν is tuned appropriately (typically 0.01-0.3).

Global Line Search:

Find ρ minimizing total loss: $$\rho_m = \arg\min_\rho \sum_{i=1}^{n} \ell(y_i, F_{m-1}(x_i) + \rho \cdot h_m(x_i))$$

This is a 1D optimization problem, solvable by bisection, golden section, or Newton's method.

Per-Leaf Line Search (Recommended for Trees):

When using decision trees, we can do better. Each leaf j defines a region Rⱼ where hₘ is constant. Instead of one global ρ, we find optimal γⱼ for each leaf:

$$\gamma_{jm} = \arg\min_\gamma \sum_{x_i \in R_{jm}} \ell(y_i, F_{m-1}(x_i) + \gamma)$$

The tree prediction becomes: hₘ(x) = γⱼₘ for x ∈ Rⱼₘ

This is more flexible—different regions can have different step sizes—and often improves performance.

Closed-Form Solutions for Specific Losses:

• Squared loss: γⱼ = mean of residuals in leaf j
• Absolute loss: γⱼ = median of residuals in leaf j
• Logistic loss: Requires Newton step or approximation

XGBoost's Approach:

XGBoost uses second-order (Newton) approximation, incorporating both gradient and Hessian to find per-leaf values: $$\gamma_j = -\frac{\sum_{i \in R_j} g_i}{\sum_{i \in R_j} h_i + \lambda}$$

where gᵢ is the gradient, hᵢ is the Hessian, and λ is L2 regularization.

Gradient boosting applies to regression, binary classification, and multi-class problems. The framework is the same; only the loss function changes.

Regression:

The model output F(x) is the prediction directly. Common losses:

• Squared error: ℓ = ½(y - F)²
• Absolute error: ℓ = |y - F|
• Huber loss: Combines L1 and L2 for robustness

Binary Classification:

The model outputs a log-odds (logit): F(x) = log(p/(1-p))

Probability is: p(y=1|x) = sigmoid(F(x)) = 1/(1 + exp(-F(x)))

Common losses:

• Logistic loss: ℓ = log(1 + exp(-y·F)) for y ∈ {-1, +1}
• Binomial deviance: -y·log(p) - (1-y)·log(1-p) for y ∈ {0, 1}

Multi-class Classification:

For K classes, we maintain K separate models F₁(x), ..., Fₖ(x).

Probabilities via softmax: $$p(y=k|x) = \frac{\exp(F_k(x))}{\sum_{j=1}^{K} \exp(F_j(x))}$$

At each boosting iteration, we:

1. Compute gradients for each class k: gᵢₖ = yᵢₖ - pᵢₖ (where yᵢₖ = 1 if sample i is class k)
2. Fit K trees, one to each gradient vector
3. Update each Fₖ by its corresponding tree

This is computationally expensive (K trees per iteration), which is why efficient implementations like LightGBM use tricks like gradient sampling and one-vs-all reductions.

A natural question: does this stagewise procedure converge? If so, how fast?

Training Loss Convergence:

Under mild conditions, gradient boosting monotonically decreases the training loss. At each stage, we add a term that (at least slightly) improves the fit.

Theorem (Informal): If the base learner class ℋ can approximate arbitrary gradients (e.g., regression trees with enough depth), then gradient boosting converges to the minimum training loss as M → ∞.

Convergence Rate:

For convex loss functions, gradient descent typically achieves:

• O(1/M) convergence for general convex losses
• O(exp(-M)) for strongly convex losses (linear convergence)

Similar rates apply to functional gradient descent (gradient boosting), though the constants depend on the base learner's approximation quality.

Role of Shrinkage in Convergence:

With shrinkage rate ν < 1, each step contributes less. This may seem to slow convergence, but:

1. Regularization effect: Smaller steps require more iterations, but the resulting path through function space is "smoother," leading to better generalization.

2. Implicit L2 penalty: Analysis shows that shrinkage approximates L2 regularization on the coefficient path.

3. Better local optima: The greedy stagewise procedure can get stuck in suboptimal configurations. Shrinkage allows more gradual exploration.

Practical Guidance:

• Use shrinkage ν ∈ [0.01, 0.3] (smaller for more regularization)
• Increase M as ν decreases (rough rule: if ν halves, double M)
• Monitor validation loss; stop early if it plateaus
• Cross-validate to find optimal (ν, M) pair

We've developed the complete algorithmic picture of how gradient boosting constructs ensembles through stagewise optimization. Let's consolidate:

What's Next:

We've covered how to fit base learners at each stage using gradients, but we haven't fully explored the connection between the loss function and the resulting algorithm behavior. The next page examines loss function formulation in depth: how different losses lead to different boosting algorithms, what properties make a loss suitable for boosting, and how to design custom losses for specialized problems.