Gradient Boosting

Imagine a committee where each expert only speaks up about what the previous expert got wrong. Each correction is small and imperfect, but after enough rounds the committee's collective answer is surprisingly accurate. That is the core idea behind gradient boosting.

The algorithm starts with a single prediction — typically the mean of the training targets. It then measures the residual errors (how far each prediction is from the truth), fits a shallow decision tree to those residuals, and adds a scaled version of that tree to the model. The residuals shrink. A new tree is fitted to the new residuals, and the cycle repeats.

After $T$ rounds the final prediction is the sum of $T$ small trees:

$$\hat{y} = F_0 + \eta \sum_{t=1}^{T} h_t(x)$$

where $F_0$ is the initial guess, $\eta$ is the learning rate (a small shrinkage factor like $0.1$), and each $h_t$ is a shallow tree fitted to the residuals at round $t$.

Algorithms like XGBoost (Chen & Guestrin, 2016) and LightGBM (Ke et al., 2017) are refined, highly optimised versions of this idea. They dominate structured-data competitions and underpin systems from fraud detection to medical diagnosis.

The chart below shows eight data points (blue dots). The model starts with the mean prediction (dashed line). Each round you click Add one tree fits a tiny stump to the current residuals and adds it to the ensemble. Watch the red residual bars collapse toward zero.

<!-- {{c_html_intro}} -->
<div class="gb-wrap">
  <div class="gb-top">
    <div class="chart-label">{{label_chart}}</div>
    <canvas id="gbCanvas" width="480" height="220"></canvas>
  </div>
  <div class="residual-section">
    <div class="chart-label">{{label_residuals}}</div>
    <canvas id="resCanvas" width="480" height="100"></canvas>
  </div>
  <div class="info-row">
    <span class="round-badge">{{label_round}} <span id="roundNum">0</span></span>
    <span class="rmse-badge">RMSE: <span id="rmseVal">—</span></span>
  </div>
  <div class="btns">
    <button id="btnAdd" type="button">{{btn_add}}</button>
    <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div id="treeLog" class="tree-log"></div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.gb-wrap { padding: .5rem; max-width: 500px; }
.chart-label { font-size: .78rem; color: #666; margin-bottom: .2rem; font-weight: 600; text-transform: uppercase; letter-spacing: .04em; }
canvas { display: block; border: 1px solid #dde3ea; border-radius: 6px; background: #f8fafc; width: 100%; }
.info-row { display: flex; gap: 1rem; align-items: center; margin: .5rem 0; flex-wrap: wrap; }
.round-badge, .rmse-badge { font-size: .88rem; font-weight: 700; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.tree-log { font-size: .8rem; color: #444; line-height: 1.6; max-height: 80px; overflow-y: auto; }
.tree-log .entry { display: flex; gap: .5rem; }
.tree-log .t-round { color: #1d3557; font-weight: 700; min-width: 3ch; }
.tree-log .t-split { color: #555; }
.tree-log .t-rmse { color: #0a7d33; font-weight: 600; margin-left: auto; }

// Code not found

Notice how the first few trees make the biggest dent — residuals that once spanned several units shrink rapidly. Later trees do progressively finer correction. This is the bias-variance trade-off in action: early rounds attack bias; too many rounds on noisy data start fitting noise instead of signal (overfitting). The learning rate $\eta$ controls how aggressively each tree is trusted.

The word gradient is not decoration. Gradient boosting is gradient descent in function space, a framing due to Jerome Friedman (2001).

• Loss function: for regression we minimise mean squared error $L(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2$. The negative gradient with respect to the current prediction is exactly $y - \hat{y}$ — the residual.
• Gradient step: fitting a tree to the residuals and adding it to the model is one step of steepest descent. The learning rate $\eta$ is the step size.
• Any differentiable loss: swap in logistic loss and you get gradient boosting for classification; use custom loss functions for ranking, survival analysis, or any task where a gradient can be computed.
• Regularisation: XGBoost adds an $\ell_2$ penalty on the leaf weights and a term on the number of leaves, automatically controlling overfitting without needing a separate validation loop.

Training $T$ trees each of depth $d$ on $n$ samples costs $O(T \cdot n \cdot d \cdot 2^d)$ — polynomial in all parameters. Prediction is $O(T \cdot 2^d)$ per sample. Both are fast enough that XGBoost runs on millions of rows on a laptop.

Compare this with neural network training, where gradient descent happens in weight space and can require billions of steps. Gradient boosting's key advantage on structured data is that each step fits an interpretable tree rather than adjusting millions of anonymous weights.

Gradient boosting sits behind a remarkable range of real systems:

• Competitive machine learning: XGBoost won or featured in the majority of Kaggle structured-data competitions between 2014 and 2020. It remains the first model practitioners reach for on tabular data.
• Credit and fraud scoring: banks and fintechs use gradient boosting to score loan applications and flag suspicious transactions in real time, because it handles missing values, mixed feature types, and skewed distributions naturally.
• Search and recommendation: click-through rate (CTR) models at major tech companies are often gradient-boosted ensembles trained on billions of examples with LightGBM for speed.
• Medical risk prediction: clinical decision-support tools use gradient boosting to predict readmission, sepsis onset, or cancer recurrence from electronic health records.
• Scientific computing: dimensionality reduction and feature selection pipelines often gate downstream models with a gradient-boosted importance score to strip irrelevant columns before fitting heavier models.

The common thread is structured, heterogeneous data — rows and columns with a mix of continuous, categorical, and missing values — where gradient boosting consistently outperforms simpler models and often matches deep networks at a fraction of the training cost.

Gradient boosting's elegance lies in its humility: no single tree needs to be right, only less wrong than the last model. By pointing each tree at the residuals left by all the previous ones, the algorithm performs gradient descent in function space and assembles an ensemble that is routinely among the most accurate methods for structured data.

The idea generalises far beyond regression. Any differentiable loss function — classification, ranking, survival — plugs in by swapping the residuals for the corresponding negative gradient. XGBoost and LightGBM add regularisation, histogram-based splits, and parallelism on top, but the core loop remains: fit, measure error, fit the error, repeat.

Next time you see a Kaggle leaderboard dominated by gradient-boosted ensembles, or a credit model that "just works," remember: underneath is a long chain of weak trees, each one quietly correcting the mistakes of the last.