Gradient Boosting

Definition

Gradient boosting builds a prediction one small correction at a time. It starts from a constant — usually the mean of the target — then repeatedly fits a shallow decision tree to what the model still gets wrong and adds a fraction of that tree to the running total. Fifty to a few thousand such trees, each individually useless, sum to a model that is still the default choice for tabular prediction.

The word most explanations get slightly wrong is gradient. Each new tree is not fitted to the errors; it is fitted to the negative gradient of the loss with respect to the model's current predictions. For squared error those two things are the same object — the derivative of ½(y − F)² with respect to F is F − y, so the negative gradient is exactly the residual y − F — which is why the folk version, "it fits the residuals", works, and why it silently stops being true the moment you change the loss function.

If you carry the residual story into a classifier you will misread almost everything the library does: why a leaf's value is Σ(y − p) / Σp(1 − p) instead of the mean of y − p, why XGBoost's min_child_weight is measured in second derivatives rather than rows, and why halving the learning rate roughly doubles the number of trees you need. The rest of this page is those three answers, with the arithmetic.

How It Works

The whole algorithm is five lines. L is any loss you can differentiate once with respect to the prediction, h is a base learner (nearly always a small tree), and η is the learning rate:

F_0(x) = the constant c that minimises sum_i L(y_i, c)

for m = 1 .. M:
    r_i   = -dL(y_i, F(x_i)) / dF(x_i)      evaluated at F = F_{m-1}    # one number per row
    h_m   = base learner fitted to the pairs (x_i, r_i)
    F_m   = F_{m-1} + eta * h_m

Note what the gradient is taken with respect to. Not the tree's split thresholds, not any weight — the prediction at each training point. So r is a vector of n numbers, one per row, and it exists only at the training points. Turning those n numbers into something you can evaluate at a new x is the base learner's entire job.

One boosting round, worked by hand

Six stores, one feature — weekly ad spend in thousands of dollars — and a target of units sold in hundreds. Loss is squared error, base learner is a depth-1 tree (a "stump"), learning rate is 0.1.

Step 0. The constant that minimises squared error is the mean: F₀ = 48 / 6 = 8. Squared error is 6² + 4² + 2² + 2² + 4² + 6² = 112, an MSE of 18.667.

Step 1. The negative gradients are y − F₀ = [−6, −4, −2, +2, +4, +6]. These are the targets the stump is fitted to, and here they are also the residuals, because the loss is squared error.

Step 2. The stump tries each midpoint threshold and keeps the one leaving the least squared error around the two leaf means:

x ≤ 35 wins. Its leaves are the means of the gradients on each side: −4 and +4.

Step 3. Multiply by η = 0.1 and add. The three low-spend stores move from 8 to 7.6, the three high-spend ones to 8.4. New residuals: [−5.6, −3.6, −1.6, +1.6, +3.6, +5.6], squared error 93.76 — a 16.3% drop from one depth-1 tree that was allowed to contribute a tenth of what it asked for.

Round 2 repeats the loop on the new gradients. The same split wins; the leaves are now ∓3.6, and after adding 0.1 of them the squared error is 78.9856. Round 3 gives leaves ∓3.24 and squared error 67.0183 — cumulatively 40.2% below where it started.

Watch the leaf values: 4.00, 3.60, 3.24. Each is exactly (1 − η) times the last, because each round closes a tenth of the remaining gap. That geometric decay is the whole story of the learning rate, and we will use it below.

What "gradient descent" means when there are no parameters

Ordinary gradient descent updates a vector of numbers: θ ← θ − η ∂L/∂θ. Boosting performs the same update on a function: F ← F − η ∂L/∂F. The difficulty is that ∂L/∂F is only defined where you have labels, so the step is not a function at all — it is n numbers sitting at n points in space. Fitting a tree to those numbers is what converts a step you can only take on the training set into a step you can take everywhere. That is the sense in which boosting is gradient descent in function space, formalised by Mason, Baxter, Bartlett and Frean (Boosting Algorithms as Gradient Descent, NIPS 1999) and by Friedman's Greedy Function Approximation (Annals of Statistics 29, 1189–1232, 2001).

Two consequences follow immediately. First, nothing inside the tree is trained by gradient descent — the tree is grown by the greedy split search described on the decision trees page, and the gradient enters only as the target it is asked to predict. Second, you do not strictly need a loss function you can differentiate; you need one number per row saying which way that prediction should move. LambdaMART exploits exactly this: ranking metrics like NDCG are step functions of the scores and have zero gradient almost everywhere, so it skips the loss and defines the per-document gradient directly, weighting each document pair by how much swapping it would change NDCG. Eight LambdaMART ensembles formed the winning entry of the 2010 Yahoo! Learning to Rank Challenge. Under the residual story that model is inexplicable.

When the negative gradient stops being a residual

Take binary classification with log loss. The model predicts log-odds F, and the probability is p = σ(F), as in logistic regression:

• L = −[ y·ln p + (1 − y)·ln(1 − p) ], so ∂L/∂F = p − y and the negative gradient is y − p.
• The second derivative is p(1 − p).

y − p looks like a residual and is not one. It is a difference of probabilities, bounded in [−1, 1], while the quantity you must add to F lives in log-odds and is unbounded. Averaging those gradients in a leaf therefore gives a step in the wrong units. Both Friedman's TreeBoost and XGBoost fix this the same way: the tree's structure is chosen from the gradients, but each leaf's value is then re-solved as a Newton step using the second derivatives,

w = Σ(y − p) / (Σ p(1 − p) + λ)

with λ the L2 penalty from regularization. Take one leaf holding four rows, three positive, all currently at p = 0.5. Then Σ(y − p) = 1.5 − 0.5 = 1.0 and Σ p(1 − p) = 4 × 0.25 = 1.0, so with λ = 0 the Newton step is w = 1.0 — against 0.25 if you had simply averaged the four gradients. Summing log loss over the four rows:

Four times the step, and 2.4 times the loss reduction. The Newton value still falls 9% short of the exact leaf optimum ln 3, because a second-order Taylor expansion is an approximation — but it captures 99.3% of what was available in one shot. For squared error the second derivative is exactly 1, so w collapses to the plain mean residual and the two rows of that table become one row. That degenerate case is the entire reason "gradient boosting fits the residuals" survived as folklore.

The same second derivative explains a parameter that otherwise looks arbitrary. XGBoost's min_child_weight (default 1) is a floor on the sum of Hessians in a child, not on the number of rows. Under log loss p(1 − p) peaks at 0.25, so a child of rows the model is maximally unsure about needs at least 4 of them; a child of rows already predicted at p = 0.99 contributes only 0.0099 each and needs 102. The parameter silently demands more evidence before the tree is allowed to carve out rows it is already confident about — and for squared-error regression, where every Hessian is 1, it degenerates into a plain row count.

The learning rate and the tree count are one knob

Because each round closes a fixed fraction of the remaining gap, the error left after m rounds decays like (1 − η)ᵐ, and the rounds needed to reach any target scale as 1 / ln(1/(1 − η)) ≈ 1/η. Running the six-store example above to convergence at three learning rates:

Halving η from 0.10 to 0.05 exactly doubles the first column and multiplies the second by 2.05. Dividing it by ten multiplies them by 10.2 and 10.4 — slightly more than ten, as the ≈ in the formula predicts. Friedman reported the same relationship in 2001 ("smaller values of ν give rise to larger optimal M-values"), and the standard advice since has been to fix a small rate, typically 0.01 to 0.1, and let early stopping choose the number of rounds.

Why pay ten times the trees for the same fit? Because the trees are not the same trees. At η = 1 each tree commits fully to a greedy step computed on noisy data, and later trees spend their capacity undoing that overreach; at η = 0.1 the same structure is spread across ten trees that each see slightly different remaining error, and the ensemble ends up smoother and generalises better. This is the rare hyperparameter where the slow setting is reliably the good one — and the reason learning_rate and n_estimators must never be tuned on separate axes of a grid search.

Types

Three implementations dominate, and they differ in ways that change results, not just speed.

XGBoost (Chen and Guestrin, KDD 2016) made the second-order view explicit: it expands any twice-differentiable loss to second order and adds a penalty of γ per leaf plus ½λ per squared leaf weight, so both the leaf value −G/(H + λ) and the gain of a candidate split drop out of one formula. It grows level-wise by default, filling each depth before going deeper, which wastes splits on branches with little to gain but is hard to make overfit. Its sparsity-aware split finder learns a default direction for missing values at every node, so NaNs need no imputation.

LightGBM (Ke et al., NIPS 2017) buckets each feature into a histogram — 255 bins by default — so scanning a split costs O(bins) instead of O(rows), and grows leaf-wise, always expanding whichever leaf promises the largest loss reduction. At a fixed leaf budget that reaches a lower training loss than level-wise growth, and overfits harder for precisely the same reason, which is why num_leaves and max_depth are the first things to cap on a small dataset. Its two named tricks follow the gradients: GOSS keeps the rows with the largest gradients and subsamples the rest (rescaling them so the gain estimate stays unbiased), on the argument that a row the ensemble already predicts well contributes little to a split decision; EFB bundles sparse features that are never non-zero together into a single column.

CatBoost (Prokhorenkova et al., NeurIPS 2018) attacks a leakage the others do not name. Encoding a categorical value by the mean target of its rows uses each row's own label to build that row's own feature — for a category appearing once, the encoding is the label — and the same leakage recurs when gradients are computed from a model that was fitted on the row it is scoring. Ordered boosting removes both by computing each row's target statistic and each row's gradient only from a random permutation prefix that excludes the row. That costs several models over several permutations, so training is slower. CatBoost also uses oblivious trees, applying the same split at every node of a level: weaker per tree, but the whole tree reduces to a bitmask index, which makes inference unusually fast.

The trade-off in one line: LightGBM when rows are many, CatBoost when high-cardinality categoricals are many, XGBoost when you want the most forgiving defaults.

Real-World Applications

Web search and product ranking. LambdaMART is gradient boosting with a hand-defined gradient, and it has been the workhorse of learning-to-rank since Microsoft Research introduced it around 2010. The winning entry of the 2010 Yahoo! Learning to Rank Challenge combined eight LambdaMART ensembles with two neural rankers and two logistic models; the boosted trees carried it, and the choice of gradient — a λ per document pair scaled by the NDCG change from swapping that pair — is why a metric with no usable derivative could be optimised at all.

Advertising click prediction. Facebook's Practical Lessons from Predicting Clicks on Ads (ADKDD 2014) describes a hybrid that is still copied: boosted trees trained daily turn raw features into leaf-membership indicators, and those indicators feed a logistic regression updated online. The combination beat either component alone by over 3% in normalised entropy — a large margin in ad ranking. Each half does what it is good at: the trees discover feature interactions offline, the linear model absorbs the last hour of data in real time.

Tabular prediction generally, which is where credit scoring, churn, demand forecasting and fraud detection actually live. The controlled evidence is Grinsztajn, Oyallon and Varoquaux (NeurIPS 2022) across 45 datasets, discussed from the ensemble side on the ensemble methods page; the interesting half here is their explanation rather than their scoreboard. They attribute the gap to three inductive biases, and all three are properties of the mechanism above. A sum of axis-aligned piecewise-constant steps fits an irregular target without smoothing it, where a neural network is biased toward smooth functions. A tree simply never splits on an uninformative column, where a dense layer mixes it into every unit. And boosting is not rotation-invariant — it treats "income" as a thing rather than as one direction in a vector space, which is correct, because on tabular data the columns mean something.

Key Concepts

• The gradient is per-row, not per-parameter. It is an n-vector attached to the training points, which is why the base learner is needed at all and why boosting works with any base learner that can regress on real numbers, not only trees.
• Newton leaf values. Structure from the first derivative, value from the first divided by the second. This is what makes boosting work on log loss, Poisson loss, ranking objectives and quantile loss without changing anything else.
• Stochastic gradient boosting (Friedman, 2002): sample a fraction of the rows — typically 0.5 to 0.8 — for each tree. It regularises and speeds training at once, and it is the boosting analogue of the row resampling in a random forest, though used for a different reason.
• Early stopping is not optional. Training loss falls monotonically with every round by construction, so it carries no information about when to stop. Only a held-out fold does, which is why cross-validation with an early-stopping round count is the standard recipe.
• Gain-based feature importance is biased, favouring high-cardinality and continuous columns simply because they offer more candidate splits. Where the attribution matters, use SHAP values rather than the built-in feature_importances_ — see explainable AI.

Challenges

Label noise is amplified rather than averaged away. The algorithm's design is to concentrate on rows it currently gets wrong, and a mislabelled row is permanently wrong. Its gradient therefore grows round after round while successive trees carve ever-finer leaves around it. This is the exact inverse of bagging, where averaging dilutes a bad row's influence across many trees. Bounding the per-row gradient is the standard mitigation — absolute error or Huber loss cap it, where squared error lets it grow without limit — and it is why boosting on a noisily-labelled dataset can end up worse than a random forest that ignores the same rows.

Boosted models cannot extrapolate, at all. Every leaf emits a constant, so the ensemble's output is a sum of constants and is bounded by the range of leaf values learned in training. Feed it a feature value beyond anything it saw and it returns the edge prediction, forever. A linear model extrapolates a trend; a boosted tree flatlines. This is the single most common way boosting is misapplied to time series, where the target has a trend and the fix is to model differences or detrend first rather than to feed a raw timestamp.

The sequence is the point, so trees cannot be parallelised. A random forest trains 500 trees on 500 cores; boosting must finish tree m before it knows what tree m+1 should fit. The parallelism available is inside one tree — split evaluation across features and histogram bins, which is what GPU implementations exploit — and inference is likewise a chain of hundreds of small trees, which is a poor fit for hardware that likes large dense operations.

More trees is a risk, not a free improvement. In a bagged ensemble the 500th tree can only help; here every extra round further reduces training loss and eventually begins to fit noise, which is overfitting in its most literal form. Boosting has roughly six interacting knobs — learning rate, rounds, depth or leaf count, row subsample, column subsample, L1/L2 penalty — against a forest's effective two, and getting them wrong costs real accuracy. That tuning burden, not the accuracy ceiling, is the honest reason to reach for a forest first on a new problem.

Future Trends

The one genuine challenge to boosting's tabular monopoly is the arrival of pre-trained tabular models. TabPFN (Hollmann et al., Nature 637, 319–326, January 2025) is a transformer pre-trained on millions of synthetic tabular tasks that classifies a new dataset by in-context learning — the training rows go in the prompt and no gradient step is taken at fit time — and it reported beating tuned boosting on datasets up to about 10,000 samples and 500 features while taking seconds rather than a tuning budget. That 10,000-row ceiling was the load-bearing caveat, and it is the part that has dated. Its successor TabPFN-2.5 (Prior Labs, arXiv:2511.08667, November 2025) raised the supported problem to 50,000 rows and 2,000 features — a fivefold increase in rows and, with the wider feature limit, a twentyfold increase in data cells (50,000 × 2,000 = 100M against the old 10,000 × 500 = 5M) — and reports still outperforming tuned tree ensembles across that range on the TabArena benchmark. So the honest summary as of mid-2026 is narrower than "boosting owns everything above ten thousand rows": gradient boosting remains the default for tabular data and still holds the very large and very wide problems, but the size at which an in-context model contests it has moved up roughly 5× in a year, and independent evaluations under distribution shift continue to report smaller margins than the headline benchmarks. Any claim about which method wins should be read with the row count, the feature count, and the date in hand.

Code Example

Twenty lines reproduce every number above. The first block is the boosting loop; note that the only line specific to squared error is the one computing grad.

import math

x = [10, 20, 30, 40, 50, 60]      # weekly ad spend, $ thousands
y = [2, 4, 6, 10, 12, 14]         # units sold, hundreds
n, eta = len(y), 0.1

def stump(target):
    """Depth-1 tree: try every midpoint, keep the split with the least leftover SSE."""
    best = None
    for i in range(1, n):
        thr = (x[i - 1] + x[i]) / 2
        left = [target[j] for j in range(n) if x[j] <= thr]
        right = [target[j] for j in range(n) if x[j] > thr]
        ml, mr = sum(left) / len(left), sum(right) / len(right)
        sse = sum((v - ml) ** 2 for v in left) + sum((v - mr) ** 2 for v in right)
        if best is None or sse < best[0]:
            best = (sse, thr, ml, mr)
    return best

F = [sum(y) / n] * n                                   # F_0 = the mean, 8.0
for m in range(1, 4):
    grad = [y[i] - F[i] for i in range(n)]             # -dL/dF for L = (y - F)^2 / 2
    _, thr, ml, mr = stump(grad)                       # fit the stump to the GRADIENTS
    F = [F[i] + eta * (ml if x[i] <= thr else mr) for i in range(n)]
    sse = sum((y[i] - F[i]) ** 2 for i in range(n))
    print(f"round {m}: split x<={thr:g}  leaves {ml:+.2f}/{mr:+.2f}  SSE {sse:.4f}")

# round 1: split x<=35  leaves -4.00/+4.00  SSE 93.7600
# round 2: split x<=35  leaves -3.60/+3.60  SSE 78.9856
# round 3: split x<=35  leaves -3.24/+3.24  SSE 67.0183

Now the classification case, on the single leaf from the table above. Only the gradient and the leaf value change — the loop around them is identical:

sigmoid = lambda z: 1 / (1 + math.exp(-z))

labels, p = [1, 1, 1, 0], 0.5          # four rows in one leaf, current log-odds F = 0
g = sum(yi - p for yi in labels)       # negative gradients, y - p        -> 1.0
h = sum(p * (1 - p) for _ in labels)   # second derivatives, p(1 - p)     -> 1.0

def logloss(F):
    q = sigmoid(F)
    return sum(-(yi * math.log(q) + (1 - yi) * math.log(1 - q)) for yi in labels)

print(f"mean of gradients {g / len(labels):.4f}  loss {logloss(g / len(labels)):.4f}")
print(f"Newton leaf value {g / h:.4f}  loss {logloss(g / h):.4f}")
print(f"exact optimum     {math.log(3):.4f}  loss {logloss(math.log(3)):.4f}")

# mean of gradients 0.2500  loss 2.5538
# Newton leaf value 1.0000  loss 2.2530
# exact optimum     1.0986  loss 2.2493

Change labels to a regression target and set every h to 1, and the second block prints the same number twice: the mean of the gradients and the Newton step coincide. That single collapse is the whole distance between the folk explanation of gradient boosting and the algorithm.