Machine Learning · Boosting · Core Derivation

Boosting as Gradient Descent in Function Space

October 2026 · 3 min read

1. Which weak learner $h \in \mathcal{H}$ should we add next?

Given the current ensemble $H(x) = \sum_{t=1}^{T} \alpha_t h_t(x)$ and any differentiable, convex loss $\mathcal{L}$, we want to choose the next weak learner $h \in \mathcal{H}$ (with small step size $\alpha > 0$) that minimizes the updated loss:

$$h = \arg\min_{h \in \mathcal{H}} \mathcal{L}(H + \alpha h).$$

2. First-order Taylor expansion $\implies$ inner product $\bigl\langle \frac{\partial \mathcal{L}}{\partial H},\, \alpha h \bigr\rangle$

Expand $\mathcal{L}(H + \alpha h)$ around $H$ using a first-order Taylor expansion:

$$\mathcal{L}(H + \alpha h) \approx \mathcal{L}(H) + \left\langle \frac{\partial \mathcal{L}}{\partial H},\, \alpha h \right\rangle.$$

Because $\mathcal{L}(H)$ is constant with respect to the candidate function $h$, dropping it turns the optimization into minimizing the inner product between the gradient $\frac{\partial \mathcal{L}}{\partial H}$ and $h$ across all $n$ training points:

$$\begin{aligned} \arg\min_{h \in \mathcal{H}} \mathcal{L}(H + \alpha h) &= \arg\min_{h \in \mathcal{H}} \left( \underbrace{\mathcal{L}(H)}_{\text{constant}} + \left\langle \frac{\partial \mathcal{L}}{\partial H},\, \alpha h \right\rangle \right) \\ &= \arg\min_{h \in \mathcal{H}} \left\langle \frac{\partial \mathcal{L}}{\partial H},\, \alpha h \right\rangle \\ &= \arg\min_{h \in \mathcal{H}} \left( \sum_{i=1}^{n} \frac{\partial \mathcal{L}}{\partial H(x_i)} \cdot \alpha\,h(x_i) \right). \end{aligned}$$

3. Why the negative gradient (residual) minimizes the inner product

For a fixed vector $a$, the dot product $a \cdot b$ (with fixed length $\|b\|$) is minimized when $b$ points in the exact opposite direction, $b = -a$. Therefore, the unconstrained function value $h(x_i)$ that minimizes $\left\langle \frac{\partial \mathcal{L}}{\partial H(x_i)},\, \alpha h(x_i) \right\rangle$ is the negative gradient:

$$h(x_i) = -\frac{\partial \mathcal{L}}{\partial H(x_i)}.$$

For squared loss $\mathcal{L} = \frac{1}{2}\sum_{i=1}^{n} \bigl(H(x_i) - y_i\bigr)^2$, the gradient with respect to $H(x_i)$ is $\frac{\partial \mathcal{L}}{\partial H(x_i)} = H(x_i) - y_i$, giving the ordinary residual:

$$\frac{\partial \mathcal{L}}{\partial H(x_i)} = H(x_i) - y_i \quad\Longrightarrow\quad h(x_i) = -\frac{\partial \mathcal{L}}{\partial H(x_i)} = y_i - H(x_i).$$

4. Completing the square: from inner product to least-squares CART fit

When $h \in \mathcal{H}$ is restricted to a family of shallow regression trees (CART of limited depth), it cannot match $-\frac{\partial \mathcal{L}}{\partial H(x_i)}$ at every point independently. Write the gradient as $r_i = \frac{\partial \mathcal{L}}{\partial H(x_i)}$ and the negative gradient (pseudo-residual) as $t_i = -r_i = -\frac{\partial \mathcal{L}}{\partial H(x_i)}$:

$$\arg\min_{h \in \mathcal{H}} \alpha \sum_{i=1}^{n} r_i\,h(x_i) = \arg\min_{h \in \mathcal{H}} -\alpha \sum_{i=1}^{n} t_i\,h(x_i) = \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{n} \bigl(-2\,t_i\,h(x_i)\bigr).$$

Now normalize (bound) $h$ on the training set so $\sum_{i=1}^{n} h(x_i)^2 = c$ is constant, and note that $t_i = -\frac{\partial \mathcal{L}}{\partial H(x_i)}$ is independent of $h$ so $\sum_{i=1}^{n} t_i^2$ is also constant with respect to $h$. Adding both constants inside the $\arg\min$ completes the square:

$$\begin{aligned} \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{n} \bigl(-2\,t_i\,h(x_i)\bigr) &= \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{n} \Bigl(\underbrace{h(x_i)^2}_{\text{constant } c} - 2\,t_i\,h(x_i) + \underbrace{t_i^2}_{\text{independent of } h}\Bigr) \\ &= \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{n} \bigl(h(x_i) - t_i\bigr)^2. \end{aligned}$$

This gives the general boosting algorithm for any differentiable loss $\mathcal{L}$:

$$\begin{aligned} t_i &= -\frac{\partial \mathcal{L}}{\partial H(x_i)}, \\ h &\leftarrow \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{n} \bigl(h(x_i) - t_i\bigr)^2, \\ H &\leftarrow H + \alpha h. \end{aligned}$$