Gradient Boosting

Background

Friedman (2001) showed gradient descent could be applied to a loss in function space, not just parameter space
XGBoost (2016), LightGBM (2017), CatBoost (2018) are the dominant implementations in production today
Consistently wins Kaggle tabular competitions against deep learning

The Concept

Gradient boosting builds an ensemble of weak learners (shallow decision trees) sequentially. Each new tree corrects the residual errors of the previous ensemble by fitting the negative gradient of the loss function. The final prediction is the sum of all tree predictions.

How it Links

Extends decision trees into a competitive ensemble method
The gradient descent analogy connects boosting to neural network optimization
DART (dropout in trees) and regularized boosting connect to deep learning regularization concepts

Concrete Example

Predicting customer churn: the first tree makes a rough split on tenure. The second tree focuses on the customers the first tree got wrong, fitting their residuals. After 100 trees, the model captures complex nonlinear interactions among dozens of features - all interpretable via individual tree splits.

Prerequisites

Decision trees, Random forests, Bias, variance, over/under-fitting

Learning outcomes

Describe AdaBoost as the historical first boosting algorithm and connect it to exponential-loss minimization.
Recognize Friedman's gradient boosting as gradient descent in function space using regression trees as basis functions.
Derive the second-order Taylor objective in XGBoost, the closed-form optimal leaf weight, and the split-gain formula.
Compare XGBoost, LightGBM, and CatBoost along tree-growth strategy, categorical handling, and missing-value handling.
Explain why GBDTs use shallow trees and why early stopping is more critical for boosting than for random forests.

TL;DR

Boosting trains a sequence of weak learners (typically shallow trees) where each new learner corrects the errors of the running ensemble. AdaBoost [1] reweights misclassified examples; Friedman [2] reframed it as gradient descent in function space, with each new tree fit to the negative gradient of the loss. XGBoost [3] took a second-order Taylor expansion to get a closed-form leaf weight $w_j^{*} = -G_j / (H_j + \lambda)$ and a clean split-gain formula. LightGBM [4] swapped level-wise growth for leaf-wise growth and added histogram-based splits. CatBoost [5] added ordered target encoding for categorical features. Used carefully (shallow trees, low learning rate, early stopping) the modern stack still beats deep nets on most tabular datasets.

Intuition

Random forests reduce variance by averaging many independent deep trees; boosting reduces bias by stacking many shallow trees, each one fitting the errors of the previous ensemble. The picture to keep in mind:

Round 1: fit a shallow tree to the original target.
Round 2: fit a shallow tree to the residuals of round 1.
Round 3: fit a shallow tree to the residuals of rounds 1 and 2 combined.
Repeat for hundreds or thousands of rounds, with a small learning rate $\eta$ shrinking each tree’s contribution.

Boosting is gradient descent in function space

If you replace “predict $y$ ” with “predict $-\partial \ell / \partial F$ ” - the negative gradient of your loss with respect to the current model output - each tree becomes a functional gradient step. The whole iterative scheme is literally gradient descent, except the “parameters” are functions and the “steps” are regression trees fit to the gradient. Friedman’s 2001 paper makes this exact, and explains why almost any differentiable loss (squared error, log-loss, Huber, quantile loss) can be plugged in with no change to the algorithm [2].

A short history

1990
1995
2001
2001
2014
2017
2018

Math

AdaBoost as exponential-loss minimization

The original algorithm

AdaBoost trains a sequence of binary classifiers $h_t : \mathcal{X} \to \{-1, +1\}$ . Initialize uniform sample weights $w_i^{(1)} = 1/n$ . At each round:

Fit $h_t$ to minimize the weighted error $\varepsilon_t = \sum_i w_i^{(t)} \mathbb{1}[h_t(x_i) \ne y_i]$ .
Set $\alpha_t = \tfrac{1}{2} \log\!\bigl((1 - \varepsilon_t)/\varepsilon_t\bigr)$ .
Update $w_i^{(t+1)} = w_i^{(t)} \exp(-\alpha_t y_i h_t(x_i)) / Z_t$ , where $Z_t$ normalises.

The final classifier is $H(x) = \operatorname{sign}\!\bigl(\sum_t \alpha_t h_t(x)\bigr)$ .

The hidden objective

Define the additive model $F(x) = \sum_t \alpha_t h_t(x)$ and the exponential loss

\ell(y, F) = \exp(-y F(x)).

Then AdaBoost is exactly coordinate descent on the exponential loss, where each “coordinate” is a (weak learner, weight) pair $(h_t, \alpha_t)$ . Concretely, given the current $F_{t-1}$ , the next round solves

(h_t, \alpha_t) = \arg\min_{h, \alpha}\, \sum_i \exp\!\bigl(-y_i (F_{t-1}(x_i) + \alpha h(x_i))\bigr).

Working through the algebra (see HTF chapter 10), the optimal $\alpha_t$ has the closed form Freund and Schapire wrote down, and the new weights $w_i^{(t+1)}$ are exactly the gradient of $\exp(-y_i F_{t-1}(x_i))$ - which is why AdaBoost “looks like” reweighting [7][1].

Why this matters

Once you see exponential loss, you can swap it for any other margin-based loss

log-loss gives LogitBoost, squared error gives L2Boost - and the algorithm is essentially the same. Friedman’s 2001 paper generalises this observation to any differentiable loss, replacing the analytic update with a gradient step.

Friedman's gradient boosting: functional gradient descent

Setup

Given a loss $\ell(y, F)$ that is differentiable in $F$ , we model

F(x) = \sum_{t=1}^{T} \eta\, f_t(x)

where each $f_t$ is a regression tree and $\eta$ is the learning rate. We build $F$ greedily: at iteration $t$ , we have $F_{t-1}$ and want to choose $f_t$ to minimise

\sum_{i=1}^{n} \ell\!\bigl(y_i,\, F_{t-1}(x_i) + f_t(x_i)\bigr).

Functional gradient

Linearise the loss around $F_{t-1}(x_i)$ :

\ell(y_i, F_{t-1}(x_i) + f_t(x_i)) \approx \ell(y_i, F_{t-1}(x_i)) + g_i\, f_t(x_i),

where $g_i = \partial \ell(y_i, F) / \partial F$ at $F = F_{t-1}(x_i)$ is the per-example gradient. Up to a constant, minimising the linearised loss is

f_t = \arg\min_{f}\, \sum_i g_i\, f(x_i),

which has no minimum on its own - we need to constrain $f$ to a tree of bounded complexity. Friedman’s pragmatic trick: fit $f_t$ as a regression tree to the negative gradients $-g_i$ (called pseudo-residuals) using squared error. The tree that best predicts $-g_i$ is the steepest-descent direction within the tree class.

After fitting the tree’s structure, set the leaf values to the loss-optimal constants:

\gamma_j = \arg\min_{\gamma}\, \sum_{i \in R_j}\,\ell\!\bigl(y_i, F_{t-1}(x_i) + \gamma\bigr),

where $R_j$ is the $j$ -th leaf region. For squared error this is just the residual mean; for log-loss it is a one-step Newton update; for general losses it is a small 1-D optimisation.

Pseudocode

F_0(x) = constant minimising sum_i loss(y_i, c)
for t = 1..T:
    g_i  = d loss(y_i, F_{t-1}(x_i)) / dF
    fit regression tree f_t to (-g_i) using squared error
    for each leaf region R_j of f_t:
        gamma_j = argmin_gamma sum_{i in R_j} loss(y_i, F_{t-1}(x_i) + gamma)
    F_t(x) = F_{t-1}(x) + eta * sum_j gamma_j * 1[x in R_j]

The learning rate $\eta \in (0, 1]$ shrinks each tree’s contribution. Smaller $\eta$ requires more iterations but typically generalises better - the classical bias-variance tradeoff in the boosting setting [2].

XGBoost: second-order Taylor objective and the split-gain formula

Regularized objective

XGBoost adds an explicit regularizer to Friedman’s setup:

\mathcal{L}(F) = \sum_{i=1}^{n}\ell(y_i, F(x_i)) + \sum_{t=1}^{T}\Omega(f_t), \qquad \Omega(f) = \gamma\, T_f + \frac{\lambda}{2}\,\sum_{j=1}^{T_f}\, w_j^{2},

where $T_f$ is the number of leaves in $f$ and $w_j$ is the $j$ -th leaf weight. The penalty $\gamma T_f$ controls tree size; $\lambda \lVert w \rVert_{2}^{2}$ shrinks leaf weights toward zero [3].

Second-order Taylor expansion

At iteration $t$ we want to choose $f_t$ to minimise $\sum_i \ell(y_i, F_{t-1}(x_i) + f_t(x_i)) + \Omega(f_t)$ . Take the Taylor expansion of $\ell$ around $F_{t-1}(x_i)$ to second order:

\ell(y_i, F_{t-1}(x_i) + f_t(x_i)) \approx \ell(y_i, F_{t-1}(x_i)) + g_i\, f_t(x_i) + \tfrac{1}{2}\,h_i\, f_t(x_i)^{2},

where

g_i = \frac{\partial \ell}{\partial F}\bigg|_{F = F_{t-1}(x_i)}, \qquad h_i = \frac{\partial^{2} \ell}{\partial F^{2}}\bigg|_{F = F_{t-1}(x_i)}.

Dropping the constant $\ell(y_i, F_{t-1}(x_i))$ , the per-iteration objective is

\tilde{\mathcal{L}}^{(t)} = \sum_{i=1}^{n}\!\bigl[g_i\, f_t(x_i) + \tfrac{1}{2}\,h_i\, f_t(x_i)^{2}\bigr] + \Omega(f_t).

Optimal leaf weight

Suppose the structure of $f_t$ is fixed: the leaves are $R_1, \dots, R_{T_f}$ and $f_t(x) = w_j$ for $x \in R_j$ . Define per-leaf sums

G_j = \sum_{i \in R_j} g_i, \qquad H_j = \sum_{i \in R_j} h_i.

The objective becomes

\tilde{\mathcal{L}}^{(t)} = \sum_{j=1}^{T_f}\!\Bigl[G_j w_j + \tfrac{1}{2}(H_j + \lambda) w_j^{2}\Bigr] + \gamma T_f.

This is quadratic in each $w_j$ ; setting the derivative to zero,

\boxed{\; w_j^{*} = -\,\frac{G_j}{H_j + \lambda}.\;}

Substituting back,

\tilde{\mathcal{L}}^{(t)*} = -\,\frac{1}{2}\,\sum_{j=1}^{T_f}\,\frac{G_j^{2}}{H_j + \lambda} + \gamma T_f.

This is the structure score of a fixed tree shape: lower is better.

Split-gain formula

To decide whether to split a leaf into left and right children, compare the structure score before and after. With $G = G_L + G_R$ and $H = H_L + H_R$ at the parent, the gain of the split is

\boxed{\; \mathrm{Gain} = \tfrac{1}{2}\!\left(\frac{G_L^{2}}{H_L + \lambda} + \frac{G_R^{2}}{H_R + \lambda} - \frac{(G_L + G_R)^{2}}{H_L + H_R + \lambda}\right) - \gamma.\;}

Splits with negative gain are rejected (this is XGBoost’s pre-pruning, controlled by $\gamma$ ). The formula reduces to Friedman’s variance-reduction split when the loss is squared error and $\lambda = 0$ .

Worked example: log-loss

For binary logistic regression with $p_i = \sigma(F(x_i))$ ,

g_i = p_i - y_i, \qquad h_i = p_i (1 - p_i),

so $h_i$ is the variance of the Bernoulli prediction. Examples that the current model is confident about ( $p_i$ near $0$ or $1$ ) have small $h_i$ and contribute little to the regularizer; examples near the decision boundary have $h_i$ near $1/4$ and dominate. This is the second-order analogue of AdaBoost’s “focus on the hard examples” intuition [3].

XGBoost vs LightGBM vs CatBoost

The three modern frameworks share the gradient-boosted-tree skeleton but differ on tree growth, categorical handling, and engineering tradeoffs. Pick based on dataset shape, not on benchmark folklore.

Property	XGBoost (Chen & Guestrin 2016)	LightGBM (Ke et al. 2017)	CatBoost (Prokhorenkova et al. 2018)
Tree growth strategy	Level-wise (depth-first by depth, balanced).	Leaf-wise (split the leaf with largest loss reduction).	Symmetric / oblivious trees (same split at every node of a level).
Categorical handling	None native - needs one-hot or external target encoding.	Native categorical splits (Fisher-style optimal partition over levels).	Ordered target encoding to avoid target leakage (the headline contribution).
Missing-value handling	Default direction learned per split during training (sparsity-aware).	Default direction learned per split (similar to XGBoost).	Treats missing as a separate category; learnable.
Histogram bins (continuous)	Yes (added in tree_method=hist; original was exact greedy).	Yes - histogram-based by default; very fast.	Yes - greedy oblivious histogram.
GPU support	Yes (gpu_hist, well battle-tested).	Yes (CUDA + OpenCL).	Yes (CUDA).
Distributed training	Yes (Rabit, integrates with Spark, Dask, Ray).	Yes (MPI / socket).	Yes (snowflake / proprietary distributed).
Best at	General-purpose; the safest default for tabular Kaggle.	Speed and large datasets; fast on millions of rows.	Categorical-heavy data; fewest knobs to tune.
Signature paper	KDD 2016 (DOI 10.1145/2939672.2939785, arXiv 1603.02754).	NeurIPS 2017.	NeurIPS 2018 (arXiv 1706.09516).

Level-wise vs leaf-wise in one paragraph

Level-wise growth (XGBoost classic) splits every leaf at each depth before moving deeper, producing balanced trees that are mechanically harder to overfit but slower per gain. Leaf-wise growth (LightGBM) always splits the single leaf with the largest gain, producing deep, unbalanced trees that converge faster on big datasets but overfit aggressively on small ones - so LightGBM users almost always cap num_leaves and min_data_in_leaf to keep the tree from collapsing into a memorising spike. Symmetric / oblivious trees (CatBoost) force the same split at every node of a given level: very fast inference (the path through the tree is just a bitmask), modest extra bias, and useful regularization on small data [4][5].

Implementations

A from-scratch numpy GBM with squared loss, sklearn’s GradientBoostingClassifier, and code sketches for XGBoost and LightGBM (the last two are not on Pyodide so they cannot run in the browser).

python

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class GBMRegressor:
  """Friedman gradient boosting on squared loss. ~60 lines."""
  def __init__(self, n_estimators=200, learning_rate=0.05, max_depth=3, seed=0):
      self.n_estimators = n_estimators
      self.eta = learning_rate
      self.max_depth = max_depth
      self.seed = seed
      self.trees = []
      self.init_ = 0.0

  def fit(self, X, y):
      # F_0 minimizes sum (y_i - c)^2 -> c = mean(y).
      self.init_ = float(np.mean(y))
      F = np.full_like(y, self.init_, dtype=float)
      rng = np.random.default_rng(self.seed)
      self.trees = []
      for t in range(self.n_estimators):
          # Pseudo-residuals = -gradient of (1/2)(y - F)^2 w.r.t. F = (y - F).
          r = y - F
          tree = DecisionTreeRegressor(
              max_depth=self.max_depth,
              min_samples_leaf=5,
              random_state=int(rng.integers(0, 1 << 30)),
          ).fit(X, r)
          update = tree.predict(X)
          F = F + self.eta * update
          self.trees.append(tree)
      return self

  def predict(self, X):
      F = np.full(X.shape[0], self.init_, dtype=float)
      for tree in self.trees:
          F += self.eta * tree.predict(X)
      return F

# usage
rng = np.random.default_rng(0)
X = rng.normal(size=(400, 5))
y = X[:, 0] + 2 * X[:, 1] - X[:, 2] ** 2 + 0.3 * rng.normal(size=400)

gbm = GBMRegressor(n_estimators=300, learning_rate=0.05, max_depth=3).fit(X, y)
print("train R^2:", round(1 - np.var(y - gbm.predict(X)) / np.var(y), 4))

The whole algorithm is "fit a tree to the residuals, scale by eta, repeat". Swapping squared loss for log-loss gives binary-classification GBM with one extra Newton-step in the leaves.

Run the from-scratch GBM live in the browser:

Idle (packages: numpy, scikit-learn)

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class GBMRegressor:
  def __init__(self, n_estimators=200, learning_rate=0.05, max_depth=3, seed=0):
      self.n_estimators = n_estimators
      self.eta = learning_rate
      self.max_depth = max_depth
      self.seed = seed

def fit(self, X, y):
      self.init_ = float(np.mean(y))
      F = np.full_like(y, self.init_, dtype=float)
      rng = np.random.default_rng(self.seed)
      self.trees = []
      for t in range(self.n_estimators):
          r = y - F                       # pseudo-residual for squared loss
          tree = DecisionTreeRegressor(
              max_depth=self.max_depth, min_samples_leaf=5,
              random_state=int(rng.integers(0, 1 << 30)),
          ).fit(X, r)
          F = F + self.eta * tree.predict(X)
          self.trees.append(tree)
      return self

def predict(self, X):
      F = np.full(X.shape[0], self.init_, dtype=float)
      for tree in self.trees:
          F += self.eta * tree.predict(X)
      return F

rng = np.random.default_rng(0)
X = rng.normal(size=(300, 4))
y = X[:, 0] + 2 * X[:, 1] - X[:, 2] ** 2 + 0.3 * rng.normal(size=300)

for n in [10, 50, 200]:
  gbm = GBMRegressor(n_estimators=n, learning_rate=0.05, max_depth=3).fit(X, y)
  r2 = 1 - np.var(y - gbm.predict(X)) / np.var(y)
  print(f"n_estimators = {n:3d}   train R^2 = {r2:.4f}")

(no output yet)

Real-world uses

Where gradient boosting still wins

GBDTs win, by a wide margin, on heterogeneous tabular data. Concrete examples:

Kaggle 2014-2020. XGBoost dominated structured-data competition leaderboards almost completely; LightGBM took over by 2018 for size and speed. Most competition write-ups in this era end with “stacked XGBoost / LightGBM ensembles”.
Online ads CTR. He et al. 2014 (Facebook) introduced the GBDT-then-LR cascade: train GBDT on raw features, use leaf indices as new features for a linear model. Still influential in production today [6].
Search ranking. LambdaMART / LambdaRank are gradient boosting on a pairwise-ranking loss; deployed at Bing, Yahoo!, and many enterprise search systems.
Financial models. Credit risk, fraud, churn, propensity - all routinely served by XGBoost / LightGBM / CatBoost.
Healthcare claim coding and risk adjustment. Tabular medical-claims data with thousands of sparse one-hot codes and a few hundred-thousand patients is GBDT’s home turf.

Pitfalls

Early stopping is not optional

Unlike random forests, where adding trees almost never hurts, gradient boosting overfits aggressively past the optimal iteration count. The training loss continues to drop while validation loss climbs back up. Always set early_stopping_rounds (or early_stopping=True in sklearn’s HistGradientBoosting) and pass an eval_set. Treat the iteration count as a hyperparameter chosen by the validation curve, not a fixed budget.

Leaf-wise growth overfits small datasets

LightGBM’s default leaf-wise tree growth converges fast on big data but builds deep, lopsided trees that memorise small datasets in a few hundred iterations. On any dataset below roughly 10k rows, set num_leaves low (15-31) and min_data_in_leaf high (20-100). On datasets below a thousand rows, classical XGBoost (level-wise) is often safer.

Learning rate and tree count trade off

Smaller learning rate $\eta$ generally generalises better but requires more trees. The classical settings are $\eta \in [0.01, 0.1]$ with n_estimators between 500 and 5000, and an early-stopping budget that lets the algorithm choose. Do not tune $\eta$ alone; sweep $\eta$ and let the early-stopping iteration count adapt.

CatBoost prediction-time encoding pitfalls

CatBoost computes ordered target encodings using training-time permutations. When you predict on a new dataset whose categorical levels include unseen-during-training values, CatBoost falls back to a prior. If your production category distribution drifts (new merchant categories, new geographic codes), monitor for this; otherwise the predictions silently collapse toward the global prior on the new levels.

Use feature monotonicity constraints if you have them

XGBoost, LightGBM, and CatBoost all support per-feature monotonicity constraints (e.g. “predicted default probability must be non-decreasing in debt-to-income”). When the domain dictates a monotone relationship, this is a free regularizer that improves generalization and satisfies regulatory explainability requirements without a measurable accuracy cost.

Interview Q&A

Derive the second-order Taylor objective in XGBoost and the closed-form leaf weight.research

XGBoost minimises a regularized objective at each iteration:

\mathcal{L}^{(t)} = \sum_{i=1}^{n}\,\ell\!\bigl(y_i, F_{t-1}(x_i) + f_t(x_i)\bigr) + \Omega(f_t),\qquad \Omega(f) = \gamma\, T_f + \tfrac{\lambda}{2}\,\sum_{j} w_j^{2}.

Second-order Taylor expand $\ell$ around $F_{t-1}(x_i)$ :

\ell(y_i, F_{t-1}(x_i) + f_t(x_i)) \approx \ell(y_i, F_{t-1}(x_i)) + g_i\, f_t(x_i) + \tfrac{1}{2}\, h_i\, f_t(x_i)^{2},

with $g_i = \partial \ell / \partial F$ and $h_i = \partial^{2}\ell / \partial F^{2}$ evaluated at $F_{t-1}(x_i)$ . Dropping the constant,

\tilde{\mathcal{L}}^{(t)} = \sum_{i}\!\bigl[g_i\, f_t(x_i) + \tfrac{1}{2}\, h_i\, f_t(x_i)^{2}\bigr] + \Omega(f_t).

For a fixed tree structure with leaves $R_1, \dots, R_{T_f}$ and weights $w_j$ , $f_t(x) = w_j$ on $x \in R_j$ . Define $G_j = \sum_{i \in R_j} g_i$ and $H_j = \sum_{i \in R_j} h_i$ . Then

\tilde{\mathcal{L}}^{(t)} = \sum_{j}\!\Bigl[G_j w_j + \tfrac{1}{2}(H_j + \lambda) w_j^{2}\Bigr] + \gamma T_f.

Each $w_j$ enters quadratically and independently; setting $\partial / \partial w_j = G_j + (H_j + \lambda) w_j = 0$ ,

w_j^{*} = -\frac{G_j}{H_j + \lambda}.

Substituting,

\tilde{\mathcal{L}}^{(t)*} = -\,\tfrac{1}{2}\sum_j \frac{G_j^{2}}{H_j + \lambda} + \gamma T_f.

The split-gain formula then comes from comparing the structure score before and after splitting one leaf into $L, R$ :

\mathrm{Gain} = \tfrac{1}{2}\!\left(\frac{G_L^{2}}{H_L + \lambda} + \frac{G_R^{2}}{H_R + \lambda} - \frac{(G_L + G_R)^{2}}{H_L + H_R + \lambda}\right) - \gamma.

Splits with negative gain are rejected, which is XGBoost’s principled pre-pruning [3].

Why do gradient-boosted trees use shallow trees, while random forests use deep ones?onsite

The two ensembles attack different terms of the bias-variance decomposition:

Random forests average many low-bias, high-variance trees. Bias is roughly that of one deep tree, and variance is reduced by averaging decorrelated estimators. Deep trees give a low bias floor; the forest then drives variance down by adding more trees.
Gradient boosting stacks many high-bias, low-variance trees. Each new tree corrects the bias of the running ensemble. Shallow trees (depth 3-8) are intentionally biased so the corrections happen incrementally, controlled by the learning rate $\eta$ . Deep trees in this regime would each absorb most of the residual signal in one round, making the iteration count irrelevant and forcing rapid overfitting.

Concretely: a depth-3 tree can capture two-way interactions and a constant mean per leaf - exactly the level of detail you want to add per iteration when $\eta = 0.05$ and you plan to stack a thousand trees. A depth-12 tree captures eight-way interactions and would memorise the residuals in a couple of rounds. The shallow-tree choice is therefore not a generic “weak learner” cliche; it is the Friedman 2001 prescription that lets functional gradient descent take small, steady steps [2][7].

Explain leaf-wise vs level-wise tree growth and why the choice matters.onsite

Level-wise growth (XGBoost classic, sklearn GradientBoostingClassifier) proceeds by depth: split every leaf at the current depth before considering the next depth. The result is a balanced tree of depth $d$ with up to $2^{d}$ leaves. Easy to parallelise (every leaf at the same depth is split independently), and the depth cap is a clean regularizer.

Leaf-wise growth (LightGBM, also called best-first growth) always splits the single leaf with the largest gain, regardless of depth. The result is an unbalanced tree where most depth lives along the highest-gain path. This converges to a given training loss with far fewer leaves than level-wise growth, which makes it much faster on big data. The cost: on small data the tree extends one branch deep enough to memorise the noise, so leaf-wise implementations require explicit caps on num_leaves and min_data_in_leaf to act as regularizers.

Symmetric / oblivious trees (CatBoost) take the opposite extreme: every node at depth $d$ uses the same split. Each tree of depth $d$ is therefore a $d$ -bit lookup table, which makes inference essentially free (compute $d$ feature thresholds, index a leaf array). Symmetric trees are slightly biased relative to level-wise growth but very robust on small data and extremely fast at serve time [4][5].

Why is early stopping more critical for gradient boosting than for random forests?onsite

In a random forest, each tree is trained independently on its bootstrap sample with no reference to the other trees. Adding more trees just averages in more i.i.d.-ish noise, so test error decreases monotonically (with diminishing returns) and never increases. There is no “wrong number” of trees; you stop when the marginal gain is below your time budget.

Gradient boosting is sequential: each tree fits the residuals of the running ensemble. Past the optimal iteration count, the residuals are mostly noise, and the new trees fit that noise. Training loss keeps dropping, but validation loss climbs back up - a classic overfitting curve. Without early stopping, the iteration count becomes the dominant overfitting risk, even more so than tree depth or learning rate.

The standard recipe: hold out 10-20% as a validation set, train with a high maximum iteration count (e.g. 5000), and let early_stopping_rounds stop training when validation loss has not improved for, say, 50 rounds. Treat the chosen iteration count as the hyperparameter, not the maximum. This is why every production GBDT pipeline has an early-stopping callback and why the no-callback version is essentially a regression bug [3].

Show that AdaBoost is gradient boosting with the exponential loss.research

AdaBoost’s update for binary classifiers $h_t(x) \in \{-1, +1\}$ with weights $\alpha_t$ produces an additive model

F(x) = \sum_{t=1}^{T} \alpha_t\, h_t(x).

Consider the exponential loss

\ell(y, F) = \exp(-y F(x)),\qquad y \in \{-1, +1\}.

The gradient with respect to $F(x_i)$ is

g_i = \frac{\partial \ell(y_i, F)}{\partial F} = -y_i\, \exp(-y_i F(x_i)).

So the negative gradient at iteration $t$ is $-g_i = y_i \exp(-y_i F_{t-1}(x_i))$ , which up to normalisation is exactly AdaBoost’s reweighted target $y_i$ with weight $w_i^{(t)} \propto \exp(-y_i F_{t-1}(x_i))$ . Fitting a weak learner $h_t$ to this weighted classification target is the gradient-boosting step.

For the line-search step, after picking $h_t$ , AdaBoost solves

\alpha_t = \arg\min_{\alpha}\, \sum_i \exp\!\bigl(-y_i (F_{t-1}(x_i) + \alpha h_t(x_i))\bigr).

Splitting the sum into correctly and incorrectly classified examples and setting the derivative in $\alpha$ to zero gives the closed-form $\alpha_t = \tfrac{1}{2}\log\!\bigl((1 - \varepsilon_t)/\varepsilon_t\bigr)$ . The weight update $w_i^{(t+1)} = w_i^{(t)} \exp(-\alpha_t y_i h_t(x_i))/Z_t$ is exactly the gradient-boosting weight update for the exponential loss. Hence AdaBoost is gradient boosting with $\ell(y, F) = \exp(-y F)$ [1][7].

Check yourself

Score: 0 / 5(0 answered)

1. In XGBoost's second-order objective, what is the closed-form optimal leaf weight in terms of G_j and H_j?
2. Why does gradient boosting use shallow trees instead of deep ones?
3. What does early_stopping_rounds typically protect against in GBDT training?
4. Which framework uses leaf-wise tree growth by default?
5. Why is AdaBoost sometimes called gradient boosting in disguise?

Build it yourself

A short evening project:

Extend the from-scratch GBMRegressor above to binary classification with log-loss. The pseudo-residual is $g_i = p_i - y_i$ with $p_i = \sigma(F_{t-1}(x_i))$ , and the leaf update is the one-step Newton refinement using $h_i = p_i (1 - p_i)$ .
Implement XGBoost’s split-gain formula directly (no second-order if you do not want to): for each candidate split, compute the Friedman improvement from squared error and verify it matches sklearn’s GradientBoostingRegressor.feature_importances_ ordering.
Add column subsampling per tree (the “bag” in LightGBM / XGBoost) and confirm that it improves test loss on a noisy dataset by ~1-2% with no other change.
Stretch: implement leaf-wise growth and compare against level-wise on a small (n = 500) and a large (n = 50000) synthetic dataset. You will see the leaf-wise version beat level-wise on the large dataset and badly overfit the small one - exactly the LightGBM default-knobs story.

Interactive Demo

Gradient Boosting Step-by-Step

Watch each tree fit the residuals of the previous ensemble, progressively reducing error.

Data Ensemble Residuals New tree

Trees

0 / 8

Training MSE

0.4422

Learning Rate (shrinkage)0.50

Tip: Click Add Tree and watch how each new tree fits the remaining residuals (gray dashes), progressively improving the ensemble.

References

Freund, Y. and Schapire, R. E. (1997). A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences 55(1), 119-139. doi:10.1006/jcss.1997.1504
Friedman, J. H. (2001). Greedy Function Approximation: A Gradient Boosting Machine. Annals of Statistics 29(5), 1189-1232. doi:10.1214/aos/1013203451
Chen, T. and Guestrin, C. (2016). XGBoost: A Scalable Tree Boosting System. Proceedings of the 22nd ACM SIGKDD. doi:10.1145/2939672.2939785
Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., Ye, Q., and Liu, T.-Y. (2017). LightGBM: A Highly Efficient Gradient Boosting Decision Tree. Advances in Neural Information Processing Systems 30 (NeurIPS 2017). https://papers.nips.cc/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html
Prokhorenkova, L., Gusev, G., Vorobev, A., Dorogush, A. V., and Gulin, A. (2018). CatBoost: unbiased boosting with categorical features. Advances in Neural Information Processing Systems 31 (NeurIPS 2018). arXiv:1706.09516
He, X., Pan, J., Jin, O., Xu, T., Liu, B., Xu, T., Shi, Y., Atallah, A., Herbrich, R., Bowers, S., and Candela, J. Q. (2014). Practical Lessons from Predicting Clicks on Ads at Facebook. Proceedings of the 8th International Workshop on Data Mining for Online Advertising (ADKDD). doi:10.1145/2648584.2648589
Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed.. Springer. https://hastie.su.domains/ElemStatLearn/

Random Forests Support Vector Machines