Gradient Boosting — Step-by-Step Mathematical Derivation

Imagine you are trying to guess a number. You make a first rough guess, someone tells you "you are a little too low," so you nudge your guess up. They say "still a bit low," so you nudge again. After many small, guided nudges, you land very close to the right answer. Gradient Boosting works exactly like this: it starts with a rough guess and then adds many small correction steps, where each correction is guided by the mistakes made so far.

Before proceeding, it is helpful to establish a few terms that recur throughout this derivation:

Model — The current predictive function, denoted $F (x)$ : given an input $x$ , it returns a prediction.
Loss — A scalar measure of prediction error. A smaller loss indicates a more accurate prediction, and our objective is to minimize it.
Weak learner — A simple model, typically a shallow decision tree, whose individual accuracy is only marginally better than random guessing. Although limited on its own, a collection of such learners can achieve strong performance.
Ensemble — A combination of many weak learners, where the final prediction is the aggregate of their individual contributions.
Iteration / Stage — A single round of the procedure, in which exactly one new weak learner is added. Rounds are indexed by $m$ , with $M$ rounds performed in total.

Big picture in one line: at every round, add a new weak learner that pushes the current model in the direction that reduces the loss the fastest.

Problem Setup

Let's first write down what we are given and what we want.

We are given training data: pairs of inputs and their correct answers, written as ${(x_{i}, y_{i})}_{i = 1}^{n}$ .
- $x_{i}$ is the $i$ -th input (its features), $y_{i}$ is the correct target value, and $n$ is how many examples we have.
Our goal is to learn a function $F (x)$ that makes predictions with the smallest total loss over all training examples.
The loss function $L (y, F (x))$ compares the true answer $y$ with the prediction $F (x)$ and returns a "wrongness" score. It only needs to be $differentiable$ , which is exactly why Gradient Boosting works for both regression and classification.

Putting all together, the ideal model is the one that minimizes the total loss:

F^{*} = \arg min_{F} \sum_{i = 1}^{n} L (y_{i}, F (x_{i}))

Here $\arg min_{F}$ reads as "the function $F$ that makes the following sum as small as possible," and $\sum_{i = 1}^{n}$ means "add this up across all $n$ training examples."

Finding this perfect $F^{*}$ in one shot is too hard. So instead of learning one giant model at once, Gradient Boosting builds the model gradually, as a sum of many small pieces (an additive ensemble):

F_{M} (x) = F_{0} (x) + \sum_{m = 1}^{M} ν h_{m} (x)

$F_{0} (x)$ is the initial model — our first rough guess.
$h_{m} (x)$ is the weak learner added at round $m$ — one small correction.
$ν \in (0, 1]$ is the learning rate. It is a small number that scales down each correction so we take gentle steps instead of overshooting.

Stagewise Additive Construction

"Stagewise" simply means we improve the model one stage (round) at a time, and we never go back and change earlier pieces — we only add new ones.

At stage $m$ , we take the model we already have, $F_{m - 1} (x)$ , and add one new weak learner to it:

\begin{array}{r} (1) & F_{m} (x) = F_{m - 1} (x) + ρ_{m} h_{m} (x) \end{array}

Read: $New model = Old model + learning rate \times new correction$
In a perfect world, at each stage we would directly solve for the best possible correction and the best step size together:

(ρ_{m}, h_{m}) = \arg min_{ρ, h} \sum_{i = 1}^{n} L (y_{i}, F_{m - 1} (x_{i}) + ρ h (x_{i}))

where

$ρ_{m}$ is the step size chosen freshly at each stage, while
$ν$ is the global learning rate that shrinks every step by the same fixed amount for safety.

Why this step? This sets up the "one round at a time" recipe and honestly admits that the ideal one-shot correction is too hard to compute. That admission is what motivates the gradient-based shortcut used in every step that follows.

Step by Step — Mathematical Derivation

Step 1: Initialize the Model

Start with a simple constant model $F_{0} (x)$ .
This gives the boosting process a reasonable baseline before any tree is added.
The initial model is chosen to minimize the loss over all constant values.

\begin{array}{r} F_{0} (x) = \arg min_{γ} \sum_{i = 1}^{n} L (y_{i}, γ) \end{array}

where $\arg min_{γ}$ means we are searching for the value $γ$ that minimizes $\sum L (y_{i}, γ)$

For regression, $F_{0} (x)$ is usually the mean of the target values.
For classification, $F_{0} (x)$ is often the log-odds of the positive class.

Step 2: Iteration Loop

The algorithm then iterates $M$ times (where $M$ is the number of trees). Each iteration is denoted as $m$

Step 2.1: Compute the Pseudo-Residuals

At iteration $m$ , look at the current model $F_{m - 1} (x)$ .
For each training example, we are calculating its residuals $r_{i m}$ by taking a derivative of the loss function with respect to the previous prediction $F_{𝑚 - 1}$ and negative gradient.
These values ( $r_{i m}$ ) are called pseudo-residuals.

\begin{matrix} (for i = 1, 2, ..., n) & r_{i m} = - {[\frac{\partial L (y_{i}, F (x_{i}))}{\partial F (x_{i})}]}_{F (x) = F_{m - 1} (x)} \end{matrix}

The little $\partial$ symbol means "derivative" — it measures how fast the loss changes if we tweak the prediction. The minus sign flips it so the value points in the direction that reduces loss (this is the "negative gradient").
Each pseudo-residual is a correction signal: its sign ( $+$ or $-$ ) says which way to move, and its size says how strongly.
Worked example of squared-error loss,

\begin{array}{r} L (y, F) = \frac{1}{2} (y - F)^{2} \end{array}

We can compute the pseudo-residual

\begin{aligned} r_{i m} & = - {[\frac{\partial L (y_{i}, F (x_{i}))}{\partial F (x_{i})}]}_{F (x) = F_{m - 1} (x)} \\ = - \frac{1}{2} \frac{\partial L (y_{i} - F_{m - 1} (x_{i}))^{2}}{\partial F_{m - 1} (x_{i})} \\ r_{i m} & = y_{i} - F_{m - 1} (x_{i}) \end{aligned}

So for regression with squared loss, Gradient Boosting repeatedly fits trees to the residual errors.

Step 2.2: Fit a Weak Learner to the Pseudo-Residuals

Now train a weak learner, usually a shallow regression tree, to predict the pseudo-residuals.
The training pairs for this step are $(x_{i}, r_{i m})$ .
The tree approximates the direction of steepest descent in function space.

h_{m} = \arg min_{h} \sum_{i = 1}^{n} (r_{i m} - h (x_{i}))^{2}

Note: The tree does not try to predict the original target $y_{i}$ directly.
It only learns the pattern of the current errors made by the ensemble.
$R_{1 m}, R_{2 m}, \dots, R_{J_{m} m}$ are the leaf (terminal) regions created by the tree built at boosting step $m$ . It divides the feature space into $J_{m}$ non-overlapping terminal regions.
- Each input point $x$ falls into exactly one region, and within that region the tree predicts one constant correction value.
- These regions are rule-based partitions formed by tree splits (for example, feature thresholds), and together they cover the full space seen by the tree.
- This is why the model update is piecewise: only the correction value of the leaf containing $x$ is applied.

Step 2.3: Find the Optimal Step Size

After fitting the tree structure, we determine how much of this new tree should be added to the model.
This is done using a line search on the actual loss.
In the most general form, we find a single multiplier $ρ_{m}$ such that:

ρ_{m} = \arg min_{ρ} \sum_{i = 1}^{n} L (y_{i}, F_{m - 1} (x_{i}) + ρ h_{m} (x_{i}))

Because each leaf is independent, it is common to compute a separate value for each leaf instead of one shared multiplier. If $R_{j m}$ is the $j$ -th leaf of tree $m$ , its optimal value is found by looking only at the points inside that leaf:

ρ_{j m} = \arg min_{ρ} \sum_{x_{i} \in R_{j m}} L (y_{i}, F_{m - 1} (x_{i}) + ρ)

Notice the sum runs over $x_{i} \in R_{j m}$ only — that is the direct link back to Step 2.2: we reuse the exact leaves it built and solve one tiny optimization per leaf.
So Step 2.2 answered "which points belong together?" and Step 2.3 answers "what value goes in each group?"
For squared-error loss, this optimal value $ρ_{j m}$ simply works out to be the mean (average) residual of the points in that leaf.

Step 2.4: Update the Ensemble

Once the tree and its leaf values are computed, add the new learner to the current model.
The learning rate $ν$ keeps the update small and stable.
This helps reduce overfitting and usually improves generalization.
Recall the tree $h_{m} (x)$ returns a single constant per leaf — the value of whichever leaf $x$ falls into:

h_{m} (x) = {\begin{cases} ρ_{1 m}, & x \in R_{1 m} \\ ρ_{2 m}, & x \in R_{2 m} \\ ⋮ \\ ρ_{J_{m} m}, & x \in R_{J_{m} m} \end{cases}

A compact way to write this same piecewise function is with the indicator $1 (\cdot)$ , which equals $1$ when its condition holds and $0$ otherwise. Since $x$ lands in exactly one leaf, only that leaf's term survives:

h_{m} (x) = \sum_{j = 1}^{J_{m}} ρ_{j m} 1 (x \in R_{j m})

Plugging this scaled correction into the update $F_{m} (x) = F_{m - 1} (x) + ν h_{m} (x)$ gives:

F_{m} (x) = F_{m - 1} (x) + ν \sum_{j = 1}^{J_{m}} ρ_{j m} 1 (x \in R_{j m})

Written out as an explicit piecewise rule, the same update reads:

F_{m} (x) = F_{m - 1} (x) + ν \cdot {\begin{cases} ρ_{1 m} & if x \in R_{1 m} \\ ρ_{2 m} & if x \in R_{2 m} \\ ⋮ \\ ρ_{J_{m} m} & if x \in R_{J_{m} m} \end{cases}

In words, the new prediction equals the old prediction plus a small correction from the new tree.

New prediction = Old prediction + learning rate \times tree correction

Step 2.5: Repeat the Process

Repeat the residual computation, tree fitting, step-size estimation, and model update for $m = 1, 2, \dots, M$ .
Each new tree focuses on the remaining mistakes of the current ensemble.
Over many iterations, the model becomes increasingly accurate.

F_{M} (x) = F_{0} (x) + ν \sum_{m = 1}^{M} \sum_{j = 1}^{J_{m}} ρ_{j m} 1 (x \in R_{j m})

This final model is the sum of many small corrective learners.
Gradient Boosting works well because each step makes a targeted improvement instead of attempting a large correction all at once.

Why the Method Works

Gradient descent updates a model by moving in the negative gradient direction.
Gradient Boosting applies the same idea, but the update is done in function space rather than directly on parameter vectors.
The weak learner approximates the negative gradient, and the line search decides how far to move in that direction.

F_{m} \approx F_{m - 1} - ν \nabla_{F} L

This is why the method is called Gradient Boosting.
It is boosting because we add weak learners sequentially.
It is gradient-based because each learner follows the negative gradient of the loss.

In compact form, the Gradient Boosting update is:

$F_{m} (x) = F_{m - 1} (x) + ν h_{m} (x)$

where $h_{m} (x)$ is trained to approximate the negative gradient of the loss at stage $m - 1$ .

Gradient Boosting = fit a weak learner to the negative gradient of the loss, then take a small step in that direction—repeated many times. Choosing squared-error loss recovers the "fit trees to residuals" intuition; choosing other losses (log-loss, absolute error, etc.) gives us classification, robust regression, and more, all from the same framework.

Deep Dive on Step 2.3 and 2.3

Example

Suppose at round $m$ the tree learns two split rules on a single feature (say, house size in sq. ft.). It ends up with three leaves:

graph TD
    A["size > 1500 ?"] -->|No| B["size > 800 ?"]
    A -->|Yes| R3["Leaf R_3m
points inside: 5
value +12"]
    B -->|No| R1["Leaf R_1m
points inside: 4
value -7"]
    B -->|Yes| R2["Leaf R_2m
points inside: 6
value +3"]

Here $J_{m} = 3$ , so the leaves are $R_{1 m}, R_{2 m}, R_{3 m}$ .

Worked example. Say we want the correction for a new house with size = 1200.
- Start at the top: is 1200 > 1500? No → go left.
- Next: is 1200 > 800? Yes → land in leaf $R_{2 m}$ .
- The tree returns that leaf's single constant, $+ 3$ . Every other leaf is ignored for this input.
Why "non-overlapping and covering the full space." Any size you pick (10, 1200, 9000, …) follows the rules to exactly one leaf — never zero, never two. The three leaves together account for every possible house size.
Why "piecewise / staircase." The tree's output as size increases is not a smooth ramp; it jumps between three flat values: $- 7$ for small houses, $+ 3$ for medium, $+ 12$ for large.

Input `size`	Leaf reached	Correction returned
400	$R_{1 m}$	$- 7$
1200	$R_{2 m}$	$+ 3$
2000	$R_{3 m}$	$+ 12$

Key idea for the next step: the numbers $- 7, + 3, + 12$ shown above came from

Step 2.2 fitting the residuals, but they are only rough placeholders.

Step 2.3 keeps these three leaf boxes fixed and recomputes the best number to store in each one so the real loss drops as much as possible.

Where do these numbers actually come from?

Two different things get "derived" when a tree is built, and it helps to keep them separate:

The split thresholds (e.g. 800, 1500) — these define the shape of the boxes and are chosen in Step 2.2.
The leaf values (e.g. -7, +3, +12) — these are the number stored in each box. Step 2.2 sets a rough version; Step 2.3 computes the optimal one.

(a) How each leaf value is derived — it is just an average of residuals.

For squared-error loss, the best constant to place in a leaf is the mean of the residuals of the points that fell into it. To see why, minimize the leaf's loss:

ρ_{j m} = \arg min_{ρ} \sum_{x_{i} \in R_{j m}} \frac{1}{2} (r_{i m} - ρ)^{2}

Differentiate with respect to $ρ$ and set it to zero:

\sum_{x_{i} \in R_{j m}} (r_{i m} - ρ) = 0 ⟹ ρ_{j m} = \frac{1}{| R_{j m} |} \sum_{x_{i} \in R_{j m}} r_{i m}

So in our example, $+ 3$ literally means "the residuals of the 6 houses inside leaf $R_{2 m}$ averaged to $+ 3$ ." Each leaf value is simply the average correction its members were asking for.

(b) How the split thresholds are derived — a greedy search.

The tree is not told 800 or 1500 in advance. It scans candidate thresholds for the feature and, for each one, checks how much it reduces the squared error of the residuals (how much "purer" the two resulting groups become). It keeps the single split that reduces the error the most, then repeats the same search independently on each child group until a stopping rule (max depth, min points per leaf) is hit.

best split = \arg min_{feature, t} \underset{error in left box}{\underset{⏟}{\sum_{x_{i} \in left (t)} (r_{i m} - {\bar{r}}_{left})^{2}}} + \underset{error in right box}{\underset{⏟}{\sum_{x_{i} \in right (t)} (r_{i m} - {\bar{r}}_{right})^{2}}}

where ${\bar{r}}_{left}$ and ${\bar{r}}_{right}$ are the mean residuals on each side. The threshold that makes this total smallest becomes a split like size > 800.

(c) How the feature space gets partitioned.

Every chosen split is an axis-aligned cut (size > 800). Stacking these cuts carves the input space into the non-overlapping leaf boxes $R_{1 m}, R_{2 m}, R_{3 m}$ . In our one-feature example the "space" is just the number line of house sizes, sliced into three intervals:

R_{1 m} : size \leq 800, R_{2 m} : 800 < size \leq 1500, R_{3 m} : size > 1500

In one line: split thresholds come from greedily minimizing residual error (Step 2.2); leaf values come from averaging the residuals inside each box (refined in Step 2.3).