Gradient Boosting
How do hundreds of tiny trees, each fixing the last one's mistakes, win on tabular data?
The situation
A shallow tree misses your rush-hour delays, and a deep tree memorises noise. A teammate suggests gradient boosting. The interviewer asks:
How does gradient boosting work, and how does it differ from a random forest?
Running example: predicting delivery time from distance (the same simulated data as Decision Trees): 60 training deliveries and 300 test ones, with a rush-hour bump around 6 km. A single depth-3 tree reached a test MSE of 3.16; the noise floor is about 2.25. Every boosted model here is trained live in your browser.
One tree is either too simple or too wobbly
A shallow tree misses detail (high bias); a deep tree memorises noise (high variance). Random Forest attacks variance by averaging many deep trees grown independently. Boosting attacks bias: it adds many shallow trees in sequence, each one specialising in what the current model still gets wrong.
The idea
Think of a round of golf. Your first shot gets you near the hole, and every shot after that only has to fix what's left. Boosting works the same way: each small tree corrects the remaining errors of everything before it.
Play
Try to break it. Set the learning rate to 1.0 with depth 2, and add trees until you reach the end. Then try a learning rate of 0.1.
Train a boosted model live
Lower ν needs more trees but reaches a better test error; scikit-learn: "Smaller values of learning_rate require larger numbers of weak learners… Empirical evidence suggests that small values of learning_rate favor better test error" docs. The test curve's minimum is where early stopping would stop.
Now say why: why does test error rise at full strength while training error keeps falling, and why does a smaller learning rate help?
Maths
In one breath
Gradient boosting builds a model one small tree at a time, and each new tree is trained to fix the mistakes of everything before it. "Mistakes" means the negative gradient of the loss, which for squared error is just the residual, so boosting is gradient descent in function space. A small learning rate (shrinkage) plus many shallow trees, stopped early on validation data, gives the strongest off-the-shelf models for tabular data. XGBoost added a regularised second-order objective and fast, sparsity-aware split finding; LightGBM added histograms, leaf-wise growth and sampling tricks for speed; CatBoost fixed target leakage with ordered boosting and native categorical handling.What you'll be able to do after this: explain boosting vs bagging, derive the residual-fitting update, tune learning rate vs number of trees, read XGBoost's split-gain formula, and choose between XGBoost, LightGBM and CatBoost.Fit the leftovers, step by step
- Start with the simplest possible model: predict the average delivery time for everyone. F₀ = the mean.
- The red lines are the residuals, actual minus predicted: what the model hasn't explained yet. Mean squared error: 46.3.
- Fit a small tree (depth 2) to the residuals, not the original times, and add half of it to the model (learning rate 0.5). The error drops to 15.1.
- New residuals, smaller than before. The next tree is fitted to these.
- Add half of tree 2: error 6.6. Keep going: each tree nibbles away at what's left. Hundreds of small corrections add up to a flexible model.
Gradient descent, where each step is a tree
Friedman (2001) framed boosting as "numerical optimization in function space"; scikit-learn: "at each iteration, the estimator hm is fitted to predict the negative gradients of the samples" scikit-learn ensemble guide.
Because only the gradient is needed, the same machinery handles any differentiable loss: squared error (regression), log-loss (classification), quantile loss (prediction intervals), Poisson (counts), and ranking losses (LambdaMART, used in search).
A penalty on tree complexity, and Newton steps
XGBoost adds a complexity penalty to every tree and uses both the gradient g and the second derivative h of the loss Chen & Guestrin 2016, §2:
Plugging the best leaf values back in gives a score for any split, used to choose (and reject) splits:
The very first split on our deliveries, starting from F₀ = mean, with squared error (g = F₀ − y, h = 1 per delivery). λ shrinks the leaf values toward 0 (more cautious steps); γ is a minimum gain a split must clear, so large γ prunes it.
In practice
From AdaBoost to the modern libraries
| System | Year | Key idea |
|---|---|---|
| AdaBoost (Freund & Schapire) | 1997 | Reweight misclassified examples; exponential loss |
| Gradient Boosting Machine (Friedman) | 2001 | Boosting as gradient descent in function space, for any differentiable loss; shrinkage |
| Stochastic GB (Friedman) | 2002 | Each tree sees a random subsample of rows |
| XGBoost (Chen & Guestrin) | 2016 | Regularised second-order objective; sparsity-aware splits; scalable system |
| LightGBM (Ke et al., Microsoft) | 2017 | Histograms, leaf-wise growth, GOSS and EFB; "up to over 20 times" faster training |
| CatBoost (Prokhorenkova et al., Yandex) | 2018 | Ordered boosting and ordered target statistics for categorical features; symmetric trees |
| HistGradientBoosting (scikit-learn) | — | LightGBM-style histograms inside scikit-learn, with native missing values and categories |
The knobs that stop it memorising
| Knob | XGBoost / LightGBM name | Effect |
|---|---|---|
| Learning rate | eta / learning_rate | Smaller steps; more trees needed; usually better test error |
| Number of trees + early stopping | n_estimators, early_stopping_rounds | Stop when validation loss stops improving |
| Tree size | max_depth (XGBoost) / num_leaves (LightGBM) | Interaction order the model can capture; shallow trees (3–8) are typical |
| Row subsampling | subsample / bagging_fraction | Stochastic gradient boosting (Friedman 2002); "a typical value of subsample is 0.5" in scikit-learn |
| Column subsampling | colsample_bytree / feature_fraction | Borrowed from random forests; XGBoost users found it "prevents over-fitting even more so than the traditional row sub-sampling" p. 3 |
| Leaf regularisation | reg_lambda, reg_alpha, gamma / min_split_gain | Shrink leaf values; demand a minimum gain per split |
| Minimum leaf size | min_child_weight / min_data_in_leaf | No leaves built on a handful of points |
XGBoost, LightGBM and CatBoost: what's actually different
| XGBoost | LightGBM | CatBoost | |
|---|---|---|---|
| Split finding | Exact greedy or approximate (weighted quantile sketch); histograms too | Histogram-based | Histogram-based |
| Tree growth | Level-wise (depth-limited) | Leaf-wise: always split the leaf with the largest gain (deeper, lopsided trees) | Symmetric (oblivious): same split across a whole level; very fast inference |
| Speed tricks | Sparsity-aware splits (learns a default direction for missing values; "more than 50 times faster" on sparse data); cache-aware blocks | GOSS (keep large-gradient rows, sample the rest) and EFB (bundle mutually exclusive sparse features) | GPU training; ordered computations |
| Categorical features | Native support in recent versions; otherwise encode | Native (gradient-statistics based splits) | Native: ordered target statistics, plus feature combinations |
| Signature fix | Regularised 2nd-order objective | Training speed on big data | "Prediction shift" from target leakage → ordered boosting |
Sources: XGBoost §3–4; LightGBM abstract (GOSS, EFB, "up to over 20 times") NeurIPS 2017; CatBoost arXiv 1706.09516.
CatBoost's insight: boosting leaks the target
Each residual is computed with a model that was trained on that same example, so training residuals are systematically smaller than they would be on new data. The authors call this a "prediction shift caused by a special kind of target leakage present in all currently existing implementations of gradient boosting." The same leak happens when you replace a category with the mean target of that category. Their fix computes each example's statistics only from examples that come earlier in a random ordering CatBoost, p. 1–4. With high-cardinality categories (user, ad, publisher IDs), this matters.
Random Forest and Gradient Boosting, side by side
| Random Forest (bagging) | Gradient Boosting | |
|---|---|---|
| Trees built | Independently, in parallel | Sequentially, each fixing the last |
| Each tree | Deep, low bias, high variance | Shallow, high bias, low variance |
| Mainly reduces | Variance (averaging) | Bias (stage-wise fitting) |
| More trees | Never hurts accuracy (just slower) | Eventually overfits; needs early stopping |
| Tuning effort | Low; good defaults | Higher (learning rate, depth, trees, regularisation) |
| Typical accuracy on tabular data | Strong | Usually the strongest |
Training a gradient-boosted model
- Pick the loss for your target (squared error, log-loss, quantile, Poisson, ranking).
- Hold out a validation set (time-based if the data is temporal).
- Start with learning rate 0.05–0.1, depth 4–8 (or ~31 leaves in LightGBM), subsample 0.8, colsample 0.8.
- Set many trees (thousands) with early stopping on validation loss (e.g. 50–100 rounds of patience).
- Tune tree size and minimum leaf size first, then regularisation; lower the learning rate at the end for a final boost.
- Handle categories natively (CatBoost, LightGBM, HistGradientBoosting) or with leakage-safe target encoding.
- Explain with SHAP values; check calibration if probabilities are used (boosted trees often need it).
Use it, or reach for something else?
Use gradient boosting when
- Tabular data with mixed numeric and categorical features
- You want top accuracy: churn, fraud, credit, pricing, CTR, demand, ranking
- Missing values, outliers and skewed features are common
Consider something else when
- Little time to tune → Random Forest
- Strictly interpretable model required → small tree or linear model
- Images, audio, free text → neural networks
- Strong trends to extrapolate → linear / time-series models
The answer that sounds right
"Add each tree at full strength, as many as possible"
Adding each correction in full (learning rate 1) fixes the training data fast, too fast: within about 10 trees the model starts fitting noise, and test error rises while training error keeps falling. In the Play lab, in the Intuition tab, learning rate 1.0 with depth-2 trees reaches its best test MSE (≈ 3.2) almost immediately and then degrades to ≈ 4.2 by 300 trees. Boosting will always drive training error toward zero; the craft is in stopping it from memorising.
What to keep
- Boosting overfits if you let it. Unlike random forests, more trees eventually hurt; always use early stopping.
- Sequential training is harder to parallelise across trees (libraries parallelise within each tree).
- No extrapolation: like any tree model, predictions flatten outside the training range. Use linear models or feature tricks for trends (e.g. predict the change, not the level).
- Not for raw images, audio or text: neural networks own those; boosting shines on heterogeneous tabular features.
- Probabilities can be miscalibrated after heavy tuning or class weighting. my take
Say it
How does gradient boosting work, and how does it differ from a random forest?
Say your answer out loud
Aim for 30 seconds. It feels different from reading it, and that's the point.
Tick what you covered
The interviewer pushes further
Follow-up 1 of 5
Bagging vs boosting?
Answer it out loud, then check.
Bagging trains independent high-variance models on bootstrap samples and averages them, reducing variance; more trees never hurt. Boosting trains weak learners sequentially on the current errors, reducing bias; it can overfit, so it needs a learning rate and early stopping.
Follow-up 2 of 5
Why is it called gradient boosting?
Answer it out loud, then check.
Each stage takes a step in function space along the negative gradient of the loss with respect to the predictions; the tree approximates that gradient using the features. For squared loss the negative gradient is the residual; for log-loss it's y − p.
Follow-up 3 of 5
Learning rate vs number of trees?
Answer it out loud, then check.
They trade off: halving the learning rate roughly needs twice the trees. Smaller learning rates usually generalise better. Fix a smallish rate, use many trees and pick the count by early stopping.
Follow-up 4 of 5
What does XGBoost add over classic GBM?
Answer it out loud, then check.
An explicit regularisation term (γ per leaf, λ on leaf weights), a second-order (Newton) approximation giving closed-form leaf values and a split-gain formula, sparsity-aware handling of missing values, column subsampling, and systems work (column blocks, cache awareness, out-of-core, distributed).
Follow-up 5 of 5
LightGBM's leaf-wise growth: pros and cons?
Answer it out loud, then check.
It splits whichever leaf reduces loss most, so it reaches lower loss with fewer leaves and trains fast, but can grow deep, lopsided trees that overfit small data. Control it with num_leaves, max_depth and min_data_in_leaf.
The 30-second answer
Gradient boosting builds an additive model of shallow trees sequentially. Each new tree is fitted to the negative gradient of the loss at the current predictions, which for squared error is just the residuals, and is added with a small learning rate. So it's gradient descent in function space, reducing bias step by step, whereas random forests average independent deep trees to reduce variance. It overfits if you add too many trees, so you use a small learning rate, shallow trees, subsampling, regularisation and early stopping. XGBoost adds a regularised second-order objective and fast split finding, LightGBM uses histograms and leaf-wise growth for speed, and CatBoost uses ordered boosting to avoid target leakage, especially with categorical features.
Go further
What not to say
- "More trees always help." That's true for random forests, not boosting.
- "Boosting uses deep trees." Typically shallow; depth controls interaction order.
- "XGBoost is a different algorithm from gradient boosting." It's a regularised, engineered implementation of it.
Key terms and sources
GBM, XGBoost, LightGBM, CatBoost · built from Friedman (2001), Chen & Guestrin (2016), Ke et al. (2017), Prokhorenkova et al. (2018), Grinsztajn et al. (2022) and scikit-learn's docs · checked 28 Oct 2026
Why it's the tabular default
Competitions
Of 29 winning Kaggle solutions published in 2015, 17 used XGBoost (8 used it alone); deep nets were second with 11. At KDD Cup 2015, "XGBoost was used by every winning team in the top-10" Chen & Guestrin, p. 1.
Higgs-1M, 500 trees: time per tree (s, ↓) and test AUC
Table 3 p. 8. scikit-learn has since added HistGradientBoosting, which its docs describe as "orders of magnitude faster" on large data.
Trees vs deep learning on tabular data
On a benchmark of 45 datasets, "tree-based models remain state-of-the-art on medium-sized data (∼10K samples) even without accounting for their superior speed." Their three reasons: neural networks are biased toward overly smooth functions, they're hurt by uninformative features, and they're rotation-invariant while tabular columns have meaning Grinsztajn et al. 2022. With larger training sets (50K) the gap narrowed in their appendix.
Read library benchmarks carefully
CatBoost's paper reports big wins where categorical features dominate (Amazon: log-loss 0.139 vs 0.163–0.164 for LightGBM/XGBoost, +17%), but with categorical handling equalised, the raw implementations differ by about 0.2% on average CatBoost, Tables 8–9. The library matters less than features, tuning and early stopping. my take
Glossary
| Term | Meaning |
|---|---|
| Pseudo-residual | Negative gradient of the loss at the current prediction. |
| Shrinkage / learning rate | Scale each tree's contribution by ν < 1. |
| Early stopping | Stop adding trees when validation loss stops improving. |
| Stochastic gradient boosting | Fit each tree on a random subsample of rows. |
| Leaf-wise vs level-wise | Split the best leaf anywhere vs fill each depth level. |
| GOSS / EFB | LightGBM's gradient-based row sampling / sparse feature bundling. |
| Ordered boosting | CatBoost's leakage-free residuals and target statistics. |
| LambdaMART | Gradient boosting for ranking (search). |
What this page is built from
- J. H. Friedman, "Greedy function approximation: a gradient boosting machine", Annals of Statistics 29(5) (2001); "Stochastic gradient boosting", CSDA 38 (2002).
- T. Chen & C. Guestrin, XGBoost: A Scalable Tree Boosting System, KDD 2016.
- G. Ke et al., LightGBM: A Highly Efficient Gradient Boosting Decision Tree, NeurIPS 2017.
- L. Prokhorenkova et al., CatBoost: unbiased boosting with categorical features, NeurIPS 2018.
- L. Grinsztajn, E. Oyallon & G. Varoquaux, Why do tree-based models still outperform deep learning on tabular data?, NeurIPS 2022.
- scikit-learn, Ensembles: gradient boosting and HistGradientBoosting.
The delivery data is simulated; the boosted models on this page are trained live with a small implementation (squared error, CART trees fitted to residuals).