Gradient Boosting and XGBoost: The Math, Derived Step by Step

On spreadsheets full of rows and columns, one family of models keeps winning: gradient boosted trees. In lesson 41 we derived the logistic regression gradient. Today we use the same idea in a surprising new place. Gradient boosting is gradient descent, but instead of updating numbers, we update an entire function.

• Tabular data champion
• Gradient descent on functions

Here is the plan. First, the core idea of fitting trees to negative gradients. Second, a tiny example worked by hand through three rounds. Third, the log loss version. Fourth, the XGBoost objective with gradients, hessians, the optimal leaf weight, and the split gain. We finish with engineering tricks and tuning in Python. We will not re-teach trees or SHAP; see lessons 19 and 20.

• Pseudo-residuals
• Hand example, three rounds
• Log loss
• XGBoost objective and gain

A boosted model is a sum. We start with a constant guess, F zero, then add small trees one at a time. After M rounds the prediction is F zero of x plus the sum of learning rate times tree m of x. Each tree has one job: correct whatever the ensemble so far still gets wrong.

• F_M(x) = F_0 + sum of trees
• Each tree fixes mistakes

Now the key mental shift. Our total loss depends on the predictions F of x i, one number per training row. Imagine those n predictions as n free variables. The loss is just a function of an n dimensional point. Gradient descent on that point is something we already know how to do.

• L = sum of loss(y_i, F(x_i))
• Treat predictions as variables

The negative gradient with respect to each prediction is called the pseudo-residual, r i. For squared error with a one half in front, the loss is one half of y minus F, squared. Its derivative with respect to F is F minus y, so the negative gradient is y minus F. That is exactly the ordinary residual. For other losses it is not, hence the name pseudo.

• r_i = -dL/dF(x_i)
• Squared error: r_i = y_i - F(x_i)

We cannot move the predictions freely, because new rows must also get predictions. So we fit a small regression tree to the pseudo-residuals. The tree is a smooth, generalizing approximation of the downhill direction. Then we step: F m equals F m minus one plus eta times the tree, where eta is the learning rate, also called shrinkage.

• Step: fit h_m to r_i
• Then F_m = F_{m-1} + eta h_m

The whole algorithm fits in four lines. Initialize F zero to the constant that minimizes the loss. For each round, compute pseudo-residuals, fit a tree to them, and update the model with shrinkage. Repeat for M rounds. Everything else, including XGBoost, is a refinement of these four steps.

• Init constant
• Compute r_i
• Fit tree, update, repeat

Let us do it by hand. Four rows with x equal to one, two, three, four, and targets y equal to ten, twelve, twenty, and twenty six. Use squared error, stumps with one split, and a learning rate of one half. The best constant for squared error is the mean: ten plus twelve plus twenty plus twenty six is sixty eight, divided by four, gives seventeen.

• x = 1, 2, 3, 4
• y = 10, 12, 20, 26
• Learning rate 0.5

Round one. The residuals, y minus seventeen, are minus seven, minus five, three, and nine. The sum of squared errors is forty nine plus twenty five plus nine plus eighty one, which is one hundred sixty four. The best stump splits between x two and x three. The left leaf averages minus seven and minus five to give minus six. The right leaf averages three and nine to give plus six.

• Residuals: -7, -5, 3, 9
• Loss sum of squares: 164

Now apply shrinkage. For the first two rows, F one is seventeen plus one half times minus six, which is fourteen. For the last two rows it is seventeen plus three, which is twenty. The new errors are minus four, minus two, zero, and six. Squared and summed, that is sixteen plus four plus zero plus thirty six, equals fifty six. The loss fell from one hundred sixty four.

• F1 = 17 + 0.5 * (-6) = 14
• F1 = 17 + 0.5 * 6 = 20
• Loss: 164 to 56

Round two. The residuals are minus four, minus two, zero, and six. This time the best split isolates the last point. The left leaf averages minus four, minus two, and zero to get minus two. The right leaf is six. After shrinking, we add minus one on the left and plus three on the right. F two becomes thirteen, thirteen, nineteen, and twenty three. The loss drops to twenty.

• Residuals: -4, -2, 0, 6
• Split after x = 3
• F2: 13, 13, 19, 23

Round three. The residuals are minus three, minus one, one, and three. Splitting between x two and x three gives leaf values minus two and plus two. Half of that is plus or minus one. F three is twelve, twelve, twenty, and twenty four, and the loss is eight. Notice the pattern: each round closes only part of the gap, and the loss falls from one sixty four, to fifty six, to twenty, to eight.

• Residuals: -3, -1, 1, 3
• F3: 12, 12, 20, 24
• Loss: 8

Why not use a learning rate of one? Each tree is fitted to noisy residuals, so a full step trusts that noise completely. Small steps average the errors of many different trees, much like a careful walker who checks the slope often. The cost is that you need more rounds. A common mistake is lowering eta without raising the number of trees, and then wondering why the model underfits.

• Small eta: many small steps
• Reduces overfitting
• Trade-off: more trees

For classification, the trees do not output probabilities directly. The ensemble produces a raw score F, a log odds value, and we convert it with the sigmoid: p equals one over one plus e to the minus F. This is the same link we used in logistic regression. Trees add up in log odds space, where adding numbers is safe and unbounded.

• F(x) is log-odds
• p = 1 / (1 + e^-F)

The log loss for one row is minus y log p minus one minus y times log of one minus p. Differentiating with respect to the score F, using the chain rule through the sigmoid, everything collapses to p minus y. The same clean result as lesson 41. So the pseudo-residual is y minus p: the label minus the current predicted probability.

• L = -[y log p + (1-y) log(1-p)]
• dL/dF = p - y
• Pseudo-residual = y - p

A quick example. Four rows, three positive and one negative. The best constant probability is three quarters, so F zero is the natural log of three, about one point one. Residuals are plus zero point two five for each positive row, and minus zero point seven five for the negative one. These now drive the next tree, exactly like the squared error case.

• 3 positives, 1 negative
• F0 = ln 3 = 1.099, p = 0.75
• Residuals: +0.25, -0.75

Here is a subtlety. For squared error, the mean residual in a leaf is the best leaf value. For log loss it is not, because the loss is curved differently. A one step Newton approximation says: leaf value equals the sum of residuals divided by the sum of p times one minus p. For a leaf with two positives, that is zero point five over zero point three seven five, about one point three three.

• Mean residual is not the right step
• Newton step: sum r / sum p(1-p)

That Newton idea is the heart of XGBoost. Instead of an informal fix, it builds the objective around a second-order approximation of the loss, adds an explicit penalty on tree complexity, and then solves for the best leaf weights in closed form. Let us derive it, one step at a time.

• Second-order Taylor expansion
• Explicit regularization
• Closed-form leaf weights

The objective is the sum of losses over rows plus a penalty for each tree. The penalty, Omega, equals gamma times T plus one half lambda times the sum of squared leaf weights. Here T is the number of leaves, w j is the weight of leaf j, gamma charges for every extra leaf, and lambda shrinks big weights, just like L2 regularization in lesson 17.

• Obj = sum l(y_i, F_i) + sum Omega(f_k)
• Omega = gamma T + 1/2 lambda sum w_j^2

At round t, we add a tree f. Expand the loss around the current prediction with a Taylor series to second order. The change is approximately g i times f of x i plus one half h i times f of x i squared. Here g i is the first derivative, the gradient, and h i is the second derivative, the hessian. The constant term does not depend on the new tree, so we drop it.

• g_i = dl/dF
• h_i = d2l/dF2
• l ≈ l0 + g f + 1/2 h f^2

What are g and h for our losses? For squared error with the one half, g is F minus y and h is one. For log loss, g is p minus y and h is p times one minus p. Notice h is largest when the model is unsure, p near one half, and tiny when it is confident. The hessian acts as a measure of how much each row matters.

• Squared error: g = F - y, h = 1
• Log loss: g = p - y, h = p(1-p)

A tree assigns every row to exactly one leaf, and every row in leaf j receives the same weight w j. So we can regroup the sum by leaf. Define big G j as the sum of gradients in leaf j, and big H j as the sum of hessians. The objective becomes a sum over leaves of G j times w j plus one half H j plus lambda times w j squared, plus gamma T.

• G_j = sum of g_i in leaf j
• H_j = sum of h_i in leaf j

Each leaf now has a simple quadratic in w: G w plus one half H plus lambda times w squared. Take the derivative and set it to zero: G plus H plus lambda times w equals zero. So the optimal weight is w star equals minus G over H plus lambda. The gradient says which way to go; the hessian and lambda say how far. With lambda zero and h equal to one, this is just the mean residual.

• d/dw: G + (H + lambda) w = 0
• w* = -G / (H + lambda)

Plug w star back in. Each leaf contributes minus one half G squared over H plus lambda. So the best objective for a tree structure is minus one half times the sum over leaves of G j squared over H j plus lambda, plus gamma T. This is a score for the tree shape. The bigger the sum, the better the tree, which gives us a clean way to compare splits.

• Obj* = -1/2 sum G_j^2/(H_j+lambda) + gamma T
• Lower is better

Now consider splitting one leaf into a left and right child. The gain is the score after minus the score before. That gives one half times the bracket of G left squared over H left plus lambda, plus G right squared over H right plus lambda, minus the parent term, then minus gamma for the extra leaf. If the gain is negative, the split is not worth it, so gamma also acts as a built-in pruning rule.

• Gain = 1/2 [GL²/(HL+λ) + GR²/(HR+λ) − (GL+GR)²/(HL+HR+λ)] − γ

Back to our four rows at round one. With squared error, g is F minus y: seven, five, minus three, minus nine, and every h is one. Choose lambda equal to one and gamma equal to zero point five. Split between x two and x three: G left is twelve, H left is two, G right is minus twelve, H right is two. The parent has G equal to zero and H equal to four.

• g = 7, 5, -3, -9; h = 1
• lambda = 1, gamma = 0.5

Compute it. Left term: twelve squared is one forty four, over two plus one, equals forty eight. Right term is also forty eight. The parent term is zero because G is zero. Half of ninety six is forty eight; subtract gamma and the gain is forty seven point five. The leaf weights are minus twelve over three, which is minus four, and plus four. Compare the unregularized values of minus six and plus six: lambda shrank them.

• 144/3 + 144/3 - 0 = 96
• Gain = 48 - 0.5 = 47.5
• w_L = -4, w_R = +4

XGBoost tries every candidate split and keeps the best. Split after x one instead: G left is seven, H left is one, G right is minus seven, H right is three. The terms are forty nine over two, which is twenty four point five, and forty nine over four, which is twelve point two five. Half the total is eighteen point three seven five, minus gamma gives seventeen point eight seven five. The middle split wins by a wide margin.

• Split after x=1: gain 17.875
• Split after x=2: gain 47.5
• Pick the best

Beyond the math, XGBoost borrows tricks from random forests. Row subsampling trains each tree on a random fraction of the rows. Column subsampling lets each tree, or each split, see only some features. Both reduce correlation between trees, which cuts overfitting, and both speed training. Typical values sit between about half and one, but treat them as hyperparameters to test.

• Row subsample
• Column subsample
• Less correlation, faster

Checking every possible threshold on millions of rows is slow. Histogram methods bucket each feature into a limited number of bins, say two hundred fifty six. For each bin we accumulate G and H, then scan the bins left to right, computing gain from running sums. The cost depends on bins, not on distinct values. A neat extra: a sibling's histogram equals the parent's minus the other child's.

• Bin features into ~256 buckets
• Sum G and H per bin
• Scan bins for best gain

Boosted trees handle missing values natively. At every split, XGBoost tries sending all rows with missing values to the left, then to the right, and computes the gain both ways. It keeps the better direction as the default for that node. So missingness is learned from the data rather than patched with an imputed number, though you should still ask why values are missing.

• Learn a default direction
• Try missing left and right
• Keep the higher gain

At a high level, LightGBM grows trees leaf-wise, always splitting the leaf with the largest gain, which is fast but can overfit small data. It also uses gradient-based sampling and bundles sparse features. CatBoost focuses on categorical features with ordered target statistics and ordered boosting to reduce target leakage, and it uses symmetric trees. XGBoost grows level by level by default. All three share the same gradient boosting core.

• LightGBM: leaf-wise growth, GOSS, EFB
• CatBoost: ordered boosting, categoricals

In practice, we set a large number of trees and let early stopping choose. Split off a validation set, with the leakage safe habits from lesson 35. Create an XGBClassifier with a learning rate of zero point oh five, max depth of four, subsample of zero point eight, and column sample of zero point eight. Pass early stopping rounds of fifty and fit with the validation set as the eval set.

• Hold out a validation set
• Stop when it stops improving

What should you tune? Fix a moderate learning rate and let early stopping set the tree count. Then tune depth, usually between three and eight, and min child weight, which requires a minimum hessian sum per leaf. Then lambda, gamma, and the sampling rates. Search with the methods of lesson 45 coming soon. Common mistakes: tuning on the test set, and early stopping on the same data you report.

• learning_rate and n_estimators
• max_depth, min_child_weight
• lambda, gamma, subsample

Let us recap. Gradient boosting is gradient descent in function space: each tree fits the negative gradients, scaled by a learning rate. For squared error those are residuals, and for log loss they are y minus p. XGBoost uses gradients and hessians, gives w star equals minus G over H plus lambda, and scores splits with a gain formula where gamma prunes. Histograms, subsampling, and learned missing directions make it fast.

• Pseudo-residuals = negative gradients
• w* = -G/(H+λ)
• Gain from G and H sums

That is lesson 42. Next time, in lesson 43, we turn to support vector machines and derive the dual problem and the kernel trick. Thanks for watching.

• Lesson 43
• Subscribe for the full course