Gradient Boosting

Gradient Boosting is an ensemble learning method that builds a strong predictive model by sequentially adding weak learners — typically shallow decision trees — each one trained to correct the residual errors of the combined ensemble so far. It is one of the dominant algorithms in structured/tabular data competitions and production ML systems, powering everything from click-through rate prediction at major tech companies to medical risk scoring. A counterintuitive fact: despite being called "gradient" boosting, the gradients being followed are in function space, not parameter space — the algorithm never takes a derivative with respect to any weight vector in the traditional sense.

The core insight

Instead of fitting a model to labels directly, gradient boosting fits each new weak learner to the negative gradient of the loss function evaluated at the current ensemble's predictions. For squared-error loss this negative gradient is just the residual, but the genius is that this formulation generalises to any differentiable loss — log-loss, Huber loss, quantile loss — simply by swapping the gradient formula. The "aha moment" is recognising that gradient descent in function space and the classic residual-fitting intuition are the same algorithm viewed through different lenses.

How It Works

Setting Up the Functional Gradient Framework

Let the dataset be {(xi,yi)}i=1n\{(x_i, y_i)\}_{i=1}^{n} and let L(y,y^)L(y, \hat{y}) be a differentiable loss function. Gradient boosting constructs an additive model:

1
FM(x)=F0(x)+∑m=1Mν⋅hm(x)\quad F_M(x) = F_0(x) + \sum_{m=1}^{M} \nu \cdot h_m(x)

Explanation: The final model is a sum of MM weak learners hmh_m, each scaled by a learning rate ν∈(0,1]\nu \in (0,1], added on top of a base prediction F0F_0.

Symbols:

  • FM(x)F_M(x) — the full ensemble after MM boosting rounds
  • F0(x)F_0(x) — initial constant prediction (usually the minimiser of LL over constants, e.g. the mean for MSE)
  • hm(x)h_m(x) — the mm-th weak learner (typically a regression tree)
  • ν\nu — learning rate / shrinkage parameter
  • MM — total number of boosting rounds

Computing Pseudo-Residuals

At each step mm, compute the pseudo-residuals — the negative gradient of the loss with respect to the current predictions:

2
rim=−[∂L(yi, F(xi))∂F(xi)]F=Fm−1\quad r_{im} = -\left[\frac{\partial L(y_i,\, F(x_i))}{\partial F(x_i)}\right]_{F=F_{m-1}}

Explanation: Each pseudo-residual rimr_{im} is the direction in which we should nudge the prediction for example ii to reduce the loss most steeply.

Symbols:

  • rimr_{im} — pseudo-residual for sample ii at boosting round mm
  • L(yi,F(xi))L(y_i, F(x_i)) — loss for sample ii given prediction F(xi)F(x_i)
  • ∂/∂F(xi)\partial / \partial F(x_i) — partial derivative with respect to the prediction value (not a parameter)

Concrete example for MSE: L=12(yi−F)2L = \frac{1}{2}(y_i - F)^2, so rim=yi−Fm−1(xi)r_{im} = y_i - F_{m-1}(x_i) — the ordinary residual.

For log-loss (binary classification): Let pi=σ(Fm−1(xi))p_i = \sigma(F_{m-1}(x_i)). Then:

3
rim=yi−pi\quad r_{im} = y_i - p_i

Explanation: Even for classification, the pseudo-residual takes the same residual form, but here pip_i is a predicted probability, making this a probability-error signal rather than a raw output error.

Fitting and Line Search

Fit a weak learner hmh_m to the pseudo-residuals {(xi,rim)}\{(x_i, r_{im})\}. Then find an optimal step size γm\gamma_m by solving:

4
γm=arg⁡min⁡γ∑i=1nL ⁣(yi,  Fm−1(xi)+γ⋅hm(xi))\quad \gamma_m = \arg\min_{\gamma} \sum_{i=1}^{n} L\!\left(y_i,\; F_{m-1}(x_i) + \gamma \cdot h_m(x_i)\right)

Explanation: This one-dimensional line search finds the scalar multiplier γm\gamma_m that most reduces the total loss when we add hmh_m to the ensemble, analogous to choosing the right step size in gradient descent. Update the ensemble:

5
Fm(x)=Fm−1(x)+ν⋅γm⋅hm(x)\quad F_m(x) = F_{m-1}(x) + \nu \cdot \gamma_m \cdot h_m(x)

Explanation: The new ensemble is the old one plus the scaled, line-search-optimal new weak learner, shrunk further by ν\nu to prevent overfitting. In practice — especially in XGBoost and LightGBM — the leaf-level step sizes are absorbed into the tree's leaf values, making a separate γm\gamma_m unnecessary; the tree fitting and line search happen simultaneously. ---

researcher · Jerome H. Friedman | b. 1945 | Invented the gradient boosting framework and its practical algorithms

Friedman is a statistician at Stanford University who unified boosting as gradient descent in function space in his landmark 2001 paper "Greedy Function Approximation: A Gradient Boosting Machine." He also introduced stochastic gradient boosting — subsampling the training data at each round — which dramatically improved both speed and generalisation. Remarkably, Friedman developed much of this theory while simultaneously co-authoring The Elements of Statistical Learning, which became one of the most cited ML textbooks in history.

researcher · Leo Breiman | 1928 – 2005 | Foundational work on ensemble methods and arcing/boosting connections

Breiman was a statistician at UC Berkeley best known for inventing Random Forests, but his 1997 paper "Arcing the Edge" was one of the first to interpret boosting as a gradient descent procedure, directly inspiring Friedman's later formalisation. His insight that ensemble methods could be understood through statistical optimisation lenses shifted the field's thinking away from purely algorithmic explanations. Breiman famously left academia for a decade to work as a consultant before returning to Berkeley — his practical experience strongly shaped his skepticism of overly parametric statistical models.

---

Figure
Gradient Boosting Sequential Ensemble Construction
Gradient Boosting: Sequential Ensemble Construction F₀(x) base pred. pseudo-r₁ −∂L/∂F₀ h₁(x) tree 1 + F₁(x) F₀ + ν·h₁ pseudo-r₂ −∂L/∂F₁ ··· Fₘ(x) = F₀ + Σ ν·hₘ strong ensemble ν = learning rate (shrinkage) L = any differentiable loss

---

Figure
Decision Tree Leaf Structure in XGBoost
Shallow Tree Fitted to Pseudo-Residuals Root Split feature ≤ threshold True False Internal Node feature₂ ≤ t₂ Leaf R₃ val = Σr_i / count Leaf R₁ val = Σr_i / count Leaf R₂ val = Σr_i / count Leaf value = mean pseudo-residual (exact for MSE loss) depth typically 3–8

---

PyTorch / NumPy Implementation Sketch

```python import numpy as np from sklearn.tree import DecisionTreeRegressor class GradientBoostingMSE: """Minimal gradient boosting for regression (MSE loss).""" def __init__(self, n_estimators=100, learning_rate=0.1, max_depth=3): self.n_estimators = n_estimators self.lr = learning_rate self.max_depth = max_depth self.trees = [] self.F0 = None def fit(self, X, y):

# Initialise F0 as the mean (minimises MSE over constants) self.F0 = np.mean(y) F = np.full(len(y), self.F0) for m in range(self.n_estimators):

# [Eq 2] Pseudo-residuals = negative gradient of MSE = y - F residuals = y - F

# Fit a shallow tree to the pseudo-residuals tree = DecisionTreeRegressor(max_depth=self.max_depth) tree.fit(X, residuals) self.trees.append(tree)

# [Eq 5] Update ensemble F += self.lr tree.predict(X) return self def predict(self, X): F = np.full(X.shape[0], self.F0) for tree in self.trees: F += self.lr tree.predict(X) return F

# Quick validation on synthetic data rng = np.random.default_rng(42) X = rng.standard_normal((500, 5)) y = np.sin(X[:, 0]) + 0.5 X[:, 1] <strong> 2 + rng.standard_normal(500) 0.1 model = GradientBoostingMSE(n_estimators=200, learning_rate=0.05, max_depth=4) model.fit(X, y) preds = model.predict(X) print(f"Train MSE: {np.mean((y - preds)2):.4f}") ```

Intuition

The Mental Model

Imagine you are a sculptor fixing a rough clay figure through committee critique. On day 1, a first apprentice makes the best figure they can. On day 2, a second apprentice looks only at where the first figure is still wrong — too tall here, too thin there — and makes a correction figure that captures just those errors. A third apprentice does the same for the remaining errors, and so on. The final sculpture is the sum of all the correction layers. The critical insight is that each apprentice is not trying to recreate the whole figure from scratch; they are only responsible for what the previous team got wrong. The "gradient" is just a mathematically precise answer to the question "which direction should the correction go?" — and choosing a good loss function is choosing a good definition of "wrong."

Historical Development

Origins · 1 minhow this was discovered
History
1895
Karl Pearson and Francis Galton develop regression to the mean — the foundational statistical concept that boosting algorithms ultimately optimise against.
1990
Robert Schapire publishes "The Strength of Weak Learnability," proving theoretically that weak learners can be combined into arbitrarily accurate strong learners — the theoretical spark for all boosting.
1995
Yoav Freund and Robert Schapire introduce AdaBoost, the first practical boosting algorithm, which reweights misclassified examples iteratively; it wins the Gödel Prize in 2003.
1997
Leo Breiman's paper "Arcing the Edge" (and subsequent "Prediction Games and Arcing Algorithms") reinterprets AdaBoost as a gradient descent procedure, planting the seed for Friedman's generalisation.
1999–2001
Jerome Friedman publishes "Greedy Function Approximation: A Gradient Boosting Machine" (2001) and the stochastic gradient boosting extension — the definitive theoretical and practical formalisation of the framework.
2007
John Langford, Lihong Li, and others develop significant theory around boosting convergence; Gábor Lugosi and Nicolas Vayatis publish regret bounds connecting boosting to online learning.
2014
Tianqi Chen begins developing XGBoost, released publicly in 2014, introducing regularised objectives, second-order (Newton) tree fitting, and column subsampling — the version that dominates Kaggle competitions.
2016
Microsoft Research releases LightGBM, introducing Gradient-based One-Side Sampling (GOSS) and Exclusive Feature Bundling (EFB), achieving 20× speed-ups over XGBoost on large datasets.
2019
CatBoost (Yandex) matures with ordered boosting to reduce prediction shift; gradient boosting firmly established as the state-of-the-art algorithm for tabular/structured data, winning the "Which ML method is best for tabular data?" NeurIPS 2022 benchmark study.

Why It Matters

Real-World Impact
Bing / Google Ad Click-Through Rate PredictionMicrosoft and Google have publicly documented using gradient boosting (and gradient boosted trees into neural pipelines) to predict ad CTR, where even 0.1% accuracy gains translate to hundreds of millions of dollars in annual revenue.
Kaggle Competition DominanceXGBoost and LightGBM appear in winning solutions for roughly 60–70% of structured-data Kaggle competitions (2016–2023), outperforming deep learning on tabular data in the majority of benchmarks.
Credit Scoring and Fraud DetectionMajor banks including JPMorgan and Citibank use LightGBM-based gradient boosting models for real-time transaction fraud scoring, where inference latency of <5ms is achievable from pre-built trees.
Medical Risk StratificationEpic Systems' deterioration index (used in 30%+ of US hospitals) for predicting patient sepsis uses gradient boosting over EHR features, with reported AUCs above 0.8 on held-out populations.
Ride-Sharing Surge Pricing (Uber/Lyft)Uber Engineering has published that gradient boosting models are core to their demand forecasting pipeline, predicting ride demand at the geohash level 30–60 minutes ahead.
High-Energy Physics (CERN)The LHCb collaboration at CERN uses XGBoost-based classifiers for particle identification in the LHCb detector, replacing slower cut-based analyses and improving signal-to-background ratios by factors of 2–5.
Weather Forecasting Post-ProcessingECMWF and NOAA use gradient boosting to statistically post-process raw NWP model output (EMOS/MOS), correcting systematic forecast biases with skill improvements of 10–25% in temperature and precipitation accuracy.

Prerequisites

What This Leads To

See Also

AdaBoost · Random Forests · Regularisation · Feature Importance and SHAP · Bayesian Optimisation

Before this

Where this leads