# Deriving Gradient Boosting from a Single Decision Tree One decision tree is a poor model: it is a table of averages, and a small change in the data rewrites the table. Yet a few hundred of them added together, each fitted to what the others got wrong, is what most people reach for first on tabular data. Why does fitting leftovers work, what is it minimising, and why do three libraries built on the same idea (XGBoost, LightGBM and CatBoost) disagree about almost everything below the equation?
Many weak trees make a smooth fit. Drag the handle to add trees: each one is a single split, and the sum of a few dozen of them follows a curve no single split can.
The answer is built here in the order you could find it yourself. Start with the dullest model there is and ask what error means. Improve it by asking one question about the data, then keep asking: that is a tree. Notice what the tree still gets wrong and fit a second tree to that: that is boosting. Then comes the one idea that needs care, what a gradient can mean when the thing you move is a function. With that in hand the rest follows: other losses, the size of a leaf, small steps, and what the three libraries add. One colour code runs through the text and the figures: blue is the data, copper is the model's prediction, and violet is the leftover, the thing the next tree is asked to fit. ## Assumptions Everything below follows from six choices. 1. **Data.** Rows $(x_i, y_i)$ for $i=1,\dots,n$, with $x_i$ a vector of features. 2. **A loss.** $\ell(y, F)$ is smooth and convex in the prediction $F$. The training objective is $J=\sum_i \ell(y_i, F(x_i))$, to which a penalty on the model may be added. 3. **An additive model.** $F(x)=F_0+\eta\sum_{m=1}^{M} f_m(x)$, with a step size $\eta\in(0,1]$ and a constant start $F_0$. 4. **Trees are the pieces.** Each $f_m$ is piecewise constant: it sends $x$ to one of $T$ leaves and returns that leaf's value $w$. 5. **Greedy construction.** Trees are added one at a time and never revisited; inside a tree, splits are chosen one at a time. 6. **Axis-aligned splits.** A split asks whether one feature is below one threshold. Assumption 5 is where all three libraries are alike and where the interesting differences live. ## Start with one number Suppose you must predict $y$ and are allowed to ignore $x$. The model is a single number $c$, the same for every row. To choose it you need a price for being wrong. Take the square of the miss, $(y_i-c)^2$, summed over the rows. Squares are smooth, and they charge a large miss much more than a small one.
The best constant is the mean. Drag the line: the violet segments are the leftovers $y_i-c$, and the curve below is the squared error as a function of $c$. It is a parabola, and its bottom is the mean of the $y_i$.
The bottom of that parabola is at the mean, $c=\bar y$. On the 36-row table the mean is $0.42$ and the mean squared error left over is $0.186$. Every model below is an attempt to beat that number. Each row's miss, $r_i=y_i-c$, is its **leftover**, and the whole essay is about what to do with leftovers.
Derivation: the best constant is the mean **The claim.** Among all constants $c$, the one that minimises $S(c)=\sum_i (y_i-c)^2$ is $\bar y=\tfrac1n\sum_i y_i$. **Expand the square.** Each term is $(y_i-c)^2=y_i^2-2cy_i+c^2$, so $$ S(c)=\sum_i y_i^2-2c\sum_i y_i+n\,c^2 . $$ **Find where the slope is zero.** $S$ is a parabola in $c$ that opens upward, so it has one bottom, where its derivative vanishes: $$ \frac{dS}{dc}=-2\sum_i y_i+2nc=0 \quad\Longrightarrow\quad c=\frac1n\sum_i y_i=\bar y . $$ **Check.** At $c=\bar y$ the leftovers sum to zero, $\sum_i (y_i-\bar y)=0$: the model is neither high nor low on average, and no constant can say more.
## Ask one question A constant ignores $x$. The cheapest way to use it is to ask a yes/no question about $x$, such as "is $x\le t$?", and give each answer its own constant. The rows split into a left group and a right group, and each group's best constant is its own mean. Two means can only fit better than one, so the error can only drop, by $$ \Delta=\frac{n_L\,n_R}{n_L+n_R}\,\big(\bar y_L-\bar y_R\big)^2 . $$ The drop is large when both groups are big and their means are far apart. To choose the question, try every threshold of every feature and keep the one with the largest $\Delta$.
The best split is a maximum you can see. Drag the threshold: the step fit changes with it, and the curve below shows how much error each position removes. The tick marks the best one.
Derivation: the reduction in error **The claim.** Splitting a group into $n_L$ and $n_R$ rows with means $\bar y_L,\bar y_R$ lowers the squared error by $\Delta$ above. **Error before the split.** A group of $n$ rows with mean $\bar y$ has error $\sum_i (y_i-\bar y)^2$. Expanding the square and using $\sum_i y_i=n\bar y$ gives $$ \sum_i (y_i-\bar y)^2=\sum_i y_i^2-n\bar y^2 . $$ **Error after the split.** The same expansion for each side gives $\sum_i y_i^2-n_L\bar y_L^2-n_R\bar y_R^2$. **Subtract.** The drop is $$ \Delta=n_L\bar y_L^2+n_R\bar y_R^2-n\bar y^2 . $$ **Write the overall mean from the two sides.** Since $n\bar y=n_L\bar y_L+n_R\bar y_R$, we have $\bar y=\dfrac{n_L\bar y_L+n_R\bar y_R}{n}$, and substituting it gives $$ \Delta=n_L\bar y_L^2+n_R\bar y_R^2-\frac{(n_L\bar y_L+n_R\bar y_R)^2}{n} =\frac{n_Ln_R}{n}\big(\bar y_L-\bar y_R\big)^2 , $$ where the last step puts everything over $n=n_L+n_R$ and the cross terms collect into a square. **Check.** If the two means are equal, $\Delta=0$: a split that changes nothing removes nothing.
On the 36-row table the best single threshold is $x=0.55$, and the left group predicts $0.29$ above the overall mean and the right group $0.41$ below it. One such stump brings the mean squared error from $0.186$ to $0.064$. Now keep asking, inside each group, and each group of the new groups. This is a regression tree: a leaf is a group of rows, and its prediction is their mean. A tree with eight leaves brings the error to $0.011$. With four or five rows per leaf it is close to memorising the table, and nothing in the training error says where to stop. A tree is also the first step of something longer. The first stump was fitted to $y$, but shifting every $y_i$ by the same constant changes no group mean gap, so it would have chosen the same threshold if it had been fitted to the leftovers $y_i-\bar y$ of the best constant. A tree is "fit the leftovers of the model so far" applied once, to the dullest model. The obvious next move is to apply it again. ## Fit the leftovers After the first tree, most rows still have a leftover. Write $F_{m-1}$ for the model so far and $r_i=y_i-F_{m-1}(x_i)$ for the leftover of row $i$. Fit the next tree to the pairs $(x_i, r_i)$ exactly as above, and add it: $$ \htmlClass{eq-model}{F_m}(x)=\htmlClass{eq-model}{F_{m-1}}(x)+\eta\,f_m(x). $$ The step size $\eta$ says how much of each correction to believe. With $\eta=0.3$ and one-split trees, 20 rounds bring the error on the 36 rows to $0.018$ and 40 rounds to $0.011$, as low as the eight-leaf tree, but by a sum of forty steps, each allowed to change the fit by only 30%. A wrong step is cheap to repair on the next round. This differs from averaging many trees fitted independently to the same data, as a random forest does. Here every tree is handed a different problem, namely what the others still get wrong. Nothing so far says why subtracting residuals should minimise anything. For squared loss it is almost a tautology. For any other loss it is not even clear what a "leftover" is. The next section answers both. ## A model is a list of predictions, and a list can be descended The loss only ever looks at what the model predicts on the training rows. So as far as the loss can tell, a model **is** the list of those predictions, $\mathbf F=(F_1,\dots,F_n)$, one entry per row, and the objective is an ordinary function of $n$ numbers: $$ J(\mathbf F)=\sum_{i=1}^n \ell(y_i, F_i). $$ With two rows you can draw every possible model, because a model is a point in the plane.
A model is a point, and the loss is a bowl. Left: the data is the blue point, the circles are equal loss, and the copper point is the current model with the violet arrow pointing downhill. Right: the same point as two predictions against their two outcomes. Drag the handle to take gradient steps.
The slope of the bowl at the current model has one entry per row, and each entry depends on that row alone: $$ \htmlClass{eq-grad}{g_i}=\frac{\partial \ell(y_i,F_i)}{\partial F_i}. $$ It says how fast row $i$'s loss grows when its prediction grows. Moving every prediction against its slope, $F_i\leftarrow F_i-\eta g_i$, lowers the loss for small $\eta$. For squared loss $\ell=\tfrac12(y-F)^2$ the slope is $g_i=F_i-y_i$, so the downhill direction $-g_i$ is exactly the leftover $y_i-F_i$. Each step then closes a fraction $\eta$ of every gap, and after $t$ steps a gap is $(1-\eta)^t$ of what it was. That is gradient descent, but it produced a list, not a model. The list has an entry for each training row and nothing to say about a new $x$. What we need is a function $f$ whose values at the training rows are the step, and which can be evaluated anywhere. A function that copies the step exactly, row by row, is a lookup table of the training rows: a leaf for every row. So the step must come from a family $\mathcal H$ of functions that cannot copy everything, such as trees with a limited number of leaves. Which member of the family is the best step? A step $\eta h$ changes the loss, to first order, by $\eta\sum_i g_i\,h(x_i)$. Write $\langle g,h\rangle=\sum_i g_i h(x_i)$ for that sum. The loss falls fastest for the $h$ that points most nearly along $-g$. Once each member of the family may be rescaled, that is the member closest to $-g$ in squared distance, so the best step is a least-squares fit: $$ f_m=\arg\min_{h\in\mathcal H}\ \sum_{i}\big(\htmlClass{eq-grad}{-g_i}-h(x_i)\big)^2 . $$ This is **functional gradient descent** (Friedman, 2001). Nothing is descended in the parameters of a tree. The point being moved is the list of predictions, the family $\mathcal H$ decides which directions are available, and fitting $\mathcal H$ to $-g$ is what carries the step to rows it has not seen. The tree is the least-squares shadow of the negative gradient.
The size of the tree decides how much of the gradient it can copy. Violet bars are the negative gradient of the squared loss at the best constant. The copper step function is the tree fitted to them, and the curve above is the model after one best step. Drag the handle to give the tree more leaves.
A tree with two leaves keeps 65% of the descent the exact step would give, four leaves 82%, eight leaves 94%. With 35 leaves it copies the gradient exactly, and then it is the lookup table. The number of leaves trades how faithfully the step follows the gradient against how well it extends to a row it has not seen, and all the regularisation below is a way to set that trade. The first stump in the previous section is the case in the figure with two leaves. The loss it removes, half of $\Delta$, is $2.19$: the same number you get from the geometry, $\tfrac12\lVert r\rVert^2\cos^2\theta$, as it must.
Derivation: the best step in a family is a least-squares fit **The claim.** Among functions $h$ of a given length $\lVert h\rVert=\big(\sum_i h(x_i)^2\big)^{1/2}$, the loss falls fastest, to first order, for the one closest to $-g$; for squared loss one best-scaled step removes $\tfrac12\lVert r\rVert^2\cos^2\theta$ of the loss. **First-order change.** For a small step $\varepsilon h$, a Taylor expansion of each row's loss in its prediction gives $$ J(\mathbf F+\varepsilon h)=J(\mathbf F)+\varepsilon\sum_i g_i\,h(x_i)+O(\varepsilon^2) =J(\mathbf F)+\varepsilon\,\langle g,h\rangle+O(\varepsilon^2). $$ **Rewrite with an angle.** The sum is an inner product, so $\langle g,h\rangle=\lVert g\rVert\,\lVert h\rVert\cos\phi$ with $\phi$ the angle between $g$ and $h$. At a fixed length $\lVert h\rVert$ the change is most negative when $\cos\phi=-1$, that is, when $h$ points along $-g$. If the family cannot reach $-g$, the best member is the one with the smallest angle to it. **Smallest angle is least squares.** Put $\theta$ for the angle between $-g$ and $h$. The best multiple $c\,h$ of a given $h$ minimises $\lVert -g-c\,h\rVert^2$, and setting the derivative in $c$ to zero gives $$ c=\frac{\langle -g,h\rangle}{\langle h,h\rangle}, \qquad \min_c\lVert -g-c\,h\rVert^2=\lVert g\rVert^2\,(1-\cos^2\theta). $$ The smaller the left side, the larger $\cos\theta$ and the smaller the angle. So choosing $h$ to minimise the squared distance to $-g$, over the family and over scale, picks the member with the smallest angle. **The loss removed.** For squared loss, $-g=r$ is the leftover and the loss is $\tfrac12\lVert r\rVert^2$. After the step $c\,h$ the leftover is $r-c\,h$, so the loss becomes $\tfrac12\lVert r-c\,h\rVert^2=\tfrac12\lVert r\rVert^2(1-\cos^2\theta)$ with the best $c$. The loss removed is $$ \tfrac12\lVert r\rVert^2\cos^2\theta=\tfrac12\,\frac{\langle r,h\rangle^2}{\langle h,h\rangle}. $$ **Check.** When the family contains $r$ itself, $\theta=0$ and the whole loss is removed in one step; when $h$ is perpendicular to $r$, $\cos\theta=0$ and the step changes nothing to first order.
## Other losses: the leftover is the negative gradient The leftover of the first section appears as the special case of squared loss. For other losses the negative gradient is what replaces it, and the tree is fitted to that. | Loss | $\ell(y,F)$ | $-g=-\partial\ell/\partial F$ | What the tree sees | | --- | --- | --- | --- | | Squared | $\tfrac12(y-F)^2$ | $y-F$ | the residual, with its full size | | Absolute | $\lvert y-F\rvert$ | $\operatorname{sign}(y-F)$ | only which side of the fit the row is on | | Logistic, $y\in\{0,1\}$ | $\log(1+e^F)-yF$ | $y-\sigma(F)$ | the gap to the predicted probability |
The tree fits the negative gradient, and the loss decides what that is. Drag the outlier up and down. Under squared loss its leftover grows with it and drags the split; under absolute loss its leftover stays at one unit.
Derivation: the three gradients **The claim.** The negative gradient $-\partial\ell/\partial F$ is $y-F$ for squared loss, $\operatorname{sign}(y-F)$ for absolute loss, and $y-\sigma(F)$ for logistic loss with $F$ a log-odds. **Squared loss.** With $\ell=\tfrac12(y-F)^2$ the chain rule gives $$ \frac{\partial\ell}{\partial F}=-(y-F)\quad\Longrightarrow\quad -g=y-F . $$ **Absolute loss.** With $\ell=\lvert y-F\rvert$ the derivative is $-1$ when $Fy$, so $-g=\operatorname{sign}(y-F)$: the tree sees only which side of the fit the row is on, however far away it is. **Logistic loss.** With $\ell=\log(1+e^F)-yF$, differentiate the logarithm first: $$ \frac{d}{dF}\log(1+e^F)=\frac{e^F}{1+e^F}=\sigma(F), $$ so $$ \frac{\partial\ell}{\partial F}=\sigma(F)-y\quad\Longrightarrow\quad -g=y-\sigma(F), $$ the gap between the label and the predicted probability. A row with $\sigma(F)\approx y$ has almost no gradient: it is already fitted.
This is why the same procedure serves regression and classification: the loss decides what the tree is asked to fit, and the machinery does not change. The step is only a first-order statement at the training rows. It says nothing by itself about the loss on new rows, which depends on the tree class, $\eta$ and the number of rounds. ## What size should a leaf be? The tree's shape comes from fitting the negative gradient. Its leaf values are a separate choice, and the mean of the leftovers is not always the best one. For squared loss the mean of the leftovers is right. For logistic loss, the mean of $y-p$ is not the best step: a leaf whose rows all have $p\approx0.99$ barely moves the loss, while a leaf of uncertain rows can move it a lot. Friedman's remedy, as I recall it, was a line search inside each leaf. The XGBoost paper makes it a formula by expanding the loss to second order around the current model. For a leaf holding a set of rows with gradients $g_i$ and curvatures $h_i=\partial^2\ell/\partial F^2$, adding a constant $w$ to every row changes the loss by approximately $$ \sum_i\Big(g_i\,w+\tfrac12 h_i\,w^2\Big)+\tfrac12\lambda w^2 =G\,w+\tfrac12\,(H+\lambda)\,w^2, \qquad G=\sum_i g_i,\ H=\sum_i h_i . $$ The last term is a penalty $\tfrac12\lambda w^2$ on large leaf values, added to the objective. The expression is a parabola in $w$, and its minimum is $$ \htmlClass{eq-model}{w^*}=-\frac{G}{H+\lambda}, \qquad\text{worth}\qquad \tfrac12\frac{G^2}{H+\lambda}\ \text{of loss reduction.} $$
A leaf value is the bottom of a parabola. Drag the penalty $\lambda$: the parabola stiffens and its minimum, the leaf value, moves toward zero. The grey curve is the true loss the parabola approximates.
For squared loss every $h_i=1$, so $w^*=\text{(sum of residuals)}/(n+\lambda)$: the mean residual, shrunk toward zero by $\lambda$. For logistic loss $h_i=p_i(1-p_i)$ is small for confident rows, which is why the step is not the plain mean. Putting the best leaf value back into the score gives each split a price tag. If a split sends gradient and curvature sums $(G_L,H_L)$ to the left and $(G_R,H_R)$ to the right, its gain is $$ \text{gain}=\tfrac12\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 . $$ The $\gamma$ is a fixed charge per new leaf: a split that does not pay for itself has negative gain and is not made. This is the quantity the XGBoost paper writes down, and the scan that finds the best threshold is a single pass over the sorted rows, accumulating $G_L$ and $H_L$ as the threshold moves. On the 36-row table with $\lambda=0,\gamma=0$ the best threshold is $0.55$ with gain $2.19$; with $\lambda=3$ and $\gamma=0.05$ the same threshold wins with gain $1.81$. Regularisation lowered the gain without moving the choice. With less obvious data it would move it. The two scores are the same thing. For squared loss every $h_i=1$, and with $\lambda=\gamma=0$ the gain is exactly half the drop $\Delta$ of the first sections, because the loss carries a factor $\tfrac12$. The formula the XGBoost paper writes down is therefore the variance-reduction score of a plain tree, with curvature and a penalty added.
Derivation: the second-order gain contains the tree's split score **The claim.** For squared loss, $\lambda=\gamma=0$, the gain of a split is $\tfrac12\,\dfrac{n_Ln_R}{n}\big(\bar y_L-\bar y_R\big)^2=\tfrac12\Delta$. **Set up the sums.** With $g_i=F_i-y_i$ and $h_i=1$ we have $H_L=n_L$, $H_R=n_R$, $H=n$, and $G_L=n_L\bar g_L$, $G_R=n_R\bar g_R$, with $\bar g$ the mean gradient of a side. The gain is $$ \tfrac12\left[\frac{G_L^2}{n_L}+\frac{G_R^2}{n_R}-\frac{(G_L+G_R)^2}{n}\right] =\tfrac12\left[n_L\bar g_L^2+n_R\bar g_R^2-n\bar g^2\right], $$ where $\bar g=(n_L\bar g_L+n_R\bar g_R)/n$ is the overall mean. **Use the earlier identity.** The bracket has exactly the form of $\Delta$ in the first derivation, with $\bar g$ in place of $\bar y$, so it equals $\dfrac{n_Ln_R}{n}\big(\bar g_L-\bar g_R\big)^2$. **Bring back the leftovers.** The gradient is $g_i=F_i-y_i=-r_i$, minus the leftover of row $i$. Squaring removes the sign, so $$ \text{gain}=\tfrac12\,\frac{n_Ln_R}{n}\big(\bar r_L-\bar r_R\big)^2 , $$ the split score of the first sections applied to the leftovers. On the first round the model is a constant, the leftovers are $y_i$ minus that constant, the gaps between means are unchanged, and the gain is $\tfrac12\Delta$. **Check.** On the 36-row table the best stump has gain $2.19$, which is half of the error it removes, $0.186-0.064=0.122$ per row times 36 rows $=4.39$.
## Small steps, many trees Each tree could be added at full strength, $\eta=1$. The figure shows what that costs. It grows trees with four leaves on a noisy 60-row table and scores each model on 1,500 fresh rows, averaged over six tables, for three step sizes.
A smaller step needs more trees and ends lower. Solid lines are the error on fresh rows, dotted lines the error on the training rows, and the dot marks each step size's best number of trees. Drag the handle along the number of trees.
With $\eta=1$ the fresh-row error is lowest after 2 trees, at $0.132$, and it climbs after that: by 80 trees the training error is $0.000$ and the fresh-row error $0.165$. With $\eta=0.1$ it takes 28 trees to reach its best, $0.105$, and at 80 trees the fresh-row error is still $0.120$ with a training error of $0.022$. The step $\eta=0.3$ sits between them, with its best of $0.106$ at 9 trees. These are six tables with one noise level, so the ordering of the two small steps is a direction, not a ranking. The shape is what carries over: a small step spends more trees to move the same distance, and each tree changes the fit less, so the number of trees becomes a dial you can set on fresh rows and stop when it turns. That is why assumption 3 carries a step size. The step size and the number of trees are not independent knobs: together they set how far along the path of fits, from the constant toward the memorised table, the model is allowed to travel. ## Three libraries, one equation Everything up to here is shared: an additive model of regularised trees, each a least-squares step along the negative gradient, with leaf values and split scores from the second-order gain. XGBoost, LightGBM and CatBoost differ in four decisions about how to *compute* it, each of which is a consequence of assumption 5. | Decision | XGBoost | LightGBM | CatBoost | | --- | --- | --- | --- | | Where to look for a split | every threshold, or quantile candidates (a sparsity-aware algorithm and a weighted quantile sketch are in the paper) | feature histograms | quantised borders | | In what order to grow | level by level by default | the leaf with the largest gain next | one shared split per level | | Which rows to look at | all rows, or a random subset | gradient-based one-side sampling (GOSS) | random or gradient-weighted sampling | | How to treat categories and ordering | by the user or by built-in handling | its own category handling | ordered target statistics and ordered boosting | The cells beyond what the three papers' abstracts state are the libraries' documented behaviour as I recall it, not re-verified here. The mechanisms below are derived or measured; the table says only which library is associated with which mechanism. ### Where to look: exact scan or histogram The exact scan sorts each feature and tries every midpoint between neighbouring values, so a node with $n$ rows has up to $n-1$ candidates per feature. A histogram method first cuts each feature into $q$ bins, then tries only the $q-1$ bin edges. Accumulating $(G,H)$ per bin takes one pass over the rows; after that every candidate costs a constant.
Fewer candidates, a coarser maximum. The grey curve is the error removed by every possible threshold of one feature on the 240-row table. The copper dots are the thresholds a histogram with $q$ bins tries. Drag the handle to change $q$.
The price is that the best threshold may fall inside a bin. On this feature the exact best threshold removes more error than any bin edge until the bins are fine: with 4 or 8 bins the best edge keeps 53% of the best gain, with 16 it keeps 81%, and with 64 it keeps all of it. Grown into an eight-leaf tree, the same coarse bins cost more: the training error is $0.0097$ with exact thresholds, and $0.295$, $0.088$ and $0.017$ with 8, 16 and 64 equal-count bins per feature. These tables have 240 rows, so a few hundred bins are as many as there are values. This shows the cost of coarse bins, not what a library with hundreds of bins loses. What the histogram buys is a second trick. A node's histogram is the sum of its two children's histograms, bin by bin, so once the parent is known, only the smaller child has to be scanned; the sibling is the difference.
One child is free. Each bar is the gradient sum in one bin. The parent's histogram was built once; the left child's is built by scanning its rows; the right child's, dashed, is the parent's minus the left's. Drag the split along the bins.
The dashed bars are computed by subtraction, and the page checks that they equal the histogram you would get by scanning the right child's rows. This is arithmetic, so it holds for any loss. ### In what order to grow: depth, leaf, or level Given a budget of leaves, a tree can spend it in three orders. **Level by level** splits every leaf at each depth. **Leaf by leaf** always splits the leaf with the largest gain, wherever it is. **Symmetric** trees use one shared threshold for a whole level, so a tree of depth $d$ is a lookup table with $2^d$ cells indexed by $d$ yes/no answers.
The same budget is spent three ways. Drag the handle to give each tree 2, 4, 8, 16 or 32 leaves. The leaf-by-leaf tree puts its cells where the data change; the symmetric tree must cut everywhere a shared threshold cuts.
The target on this table has three regions, a strong corner and two weaker bands, and the tree that goes leaf by leaf reaches them first. At eight leaves, the training errors are $0.043$ (level by level), $0.0097$ (leaf by leaf) and $0.150$ (symmetric). At sixteen they are $0.0079$, $0.0077$ and $0.060$: level by level has caught up, symmetric has not. That is training error, which always favours flexibility. The question that matters is the error on rows the tree has not seen, and it depends on how noisy the labels are. The next figure draws fresh 240-row tables with the same three-region target and a chosen amount of label noise, grows each tree on one table, scores it on 1,500 fresh rows, and averages over six tables.
The best order depends on the noise. Solid lines are error on fresh rows, dotted lines are error on the training rows; the dot marks each order's best leaf count. Drag the handle to add noise to the labels.
With little noise (0.1) the two flexible orders do best and reach the same fresh-row error, $0.095$, at 32 leaves; the symmetric tree needs 64 leaves and ends at $0.126$. Add noise and the picture changes. At 1.0 the symmetric tree's best fresh-row error, $1.19$ at 32 leaves, is below leaf-by-leaf's $1.25$ at 8 leaves and level-by-level's $1.27$ at 8: the flexible orders have started fitting noise while the shared-threshold constraint holds the symmetric tree back. In the middle, at 0.5, all three are within 4% of each other. These are six tables and one tree each, so a 5% difference is a direction, not a ranking. What is robust is the shape: the more noise, the more the constraint pays, and the fewer leaves each tree can use before it begins to fit noise. Leaf-by-leaf growth is greedy at every step. Where the structure is uneven, as here, it reaches a lower training error with the same number of leaves; on small, noisy tables it overfits sooner, which is why a minimum row count per leaf matters for it. The symmetric tree loses flexibility and gains two things: prediction is $d$ comparisons and one lookup, and the shared constraint acts as a regulariser. ### Which rows to look at: sampling by gradient Rows with a small gradient are already fitted; they contribute little to any gain. LightGBM's one-side sampling (GOSS) keeps the fraction $a$ of rows with the largest $\lvert g\rvert$, draws a fraction $b$ of the rest at random, and multiplies the drawn rows by $(1-a)/b$ so that sums stay unbiased. With $a=0.2$ and $b=0.1$ on 240 rows, the sampled gradient sum has the same mean as the full sum, which a simulation of 20,000 draws confirms. Unbiased is not the same as better. The bet is that a few rows carry most of the gradient, so keeping them exactly and thinning the rest costs little. The figure tests the bet on this table: at each boosting round it estimates the gain of the best split of the full data from 30% of the rows, two ways.
Sampling by gradient is a bet on skew. Top: one draw, with the rows it keeps in violet and the ones it draws in blue. Bottom: the gain estimated over 250 draws, by one-side sampling and by uniform sampling of the same number of rows, against the full-data gain (black). Drag the handle through the boosting rounds.
The measured result is mixed. At round 3 one-side sampling's error is $1.14$ against $1.48$ for uniform sampling; at round 8 it is $0.48$ against $0.36$. The skew it relies on is modest here: the top fifth of the rows holds between 34% and 41% of the total gradient at every round. A weaker version of the bet is therefore the honest one: the sampling is cheap and unbiased, and whether it beats uniform sampling depends on how skewed your gradients are. The same paper bundles features that are rarely non-zero together (exclusive feature bundling), a column-side version of the same idea of skipping what carries little information. ### Categories and the label you are about to learn A tree cannot split on a category without a number for it. There are two answers in the libraries. The first is to keep the category as a category and search over groupings of its values. With $k$ categories there are $2^{k-1}-1$ ways to split them into two groups, which is hopeless to scan. For squared loss there is a classical shortcut: sort the categories by their average residual $G_c/H_c$ and scan only the $k-1$ cut points of that order. The best of those is the best of all the groupings.
Sorting turns a huge search into a short scan. Bars are categories, sorted by their average residual; copper and blue are the two groups of the best cut. Below, the gain found by scanning the sorted order, by splitting off one category against the rest, and by trying every grouping. Drag the handle to change the number of categories.
On a table with eight categories the sorted scan, with 7 candidates, finds a gain of $201.7$, the same as trying all 127 groupings, while the best single category against the rest finds $187.0$. With twelve categories the sorted scan still matches all 2,047 groupings, at $346.5$, and one-against-rest falls to $152.2$. The page checks the equality for every $k$ from 3 to 12. As I recall, LightGBM applies this ordering to categorical splits; I have not re-checked its documentation. The second answer is to turn the category into a number before training, and that is where the label can leak. A common choice is the average label of the category, $\text{TS}=(\sum_{j\in\text{cat}}y_j+a\,p)/(\text{count}+a)$, with a prior $p$ of weight $a$. If the average includes the row's own label, the encoding carries information it should not have. Take a coin-flip label, which has no relation to the category, and $k$ rows per category. Then the encoding of a row and its label have correlation $$ \operatorname{corr}(\text{TS}_i,y_i)=\frac{1}{\sqrt{k}}, $$ for any prior weight $a$. A category seen twice leaks $0.71$ of a correlation of pure noise; seen a dozen times, $0.29$. A tree that finds this threshold has learned the labels it is being trained on, and it looks excellent until test time.
The row's own label leaks into its encoding. Each dot is one row, labelled 0 or 1 by a coin flip. Drag the handle to change how often a category repeats. The violet bars mark each group's mean encoding, and $r$ is the correlation between the encoding and the row's own label: the average that includes the label separates the two groups, and the ordered average does not.
CatBoost's answer is an **ordered** statistic: draw a random permutation of the rows and encode each row using only the rows before it. The row's own label is never in its own encoding, and the measured correlation stays at zero for every $k$ (it is $-0.006$ at $k=4$ over 300 simulated tables). The price is that the first rows of every category see only the prior, so the encoding is noisier early in the permutation.
Derivation: the 1/√k correlation Let $y_i$ be independent coin flips with variance $\sigma^2$, and let a category have $k$ rows with sum $S$. Then $\text{TS}=(S+ap)/(k+a)$. Its covariance with $y_i$ is $\operatorname{Cov}(S,y_i)/(k+a)=\sigma^2/(k+a)$, since $y_i$ is one of the $k$ terms of $S$. Its variance is $k\sigma^2/(k+a)^2$. The correlation is the covariance over $\sqrt{\text{Var}(\text{TS})\sigma^2}$, so the factors of $(k+a)$ and $\sigma$ cancel and leave $1/\sqrt k$.
The same mistake appears one level up. The residual used to fit tree $m$ is computed with a model that has already seen the row. In its simplest form, a leaf with $n$ rows predicts their mean, and the in-sample residual of one row is exactly $(1-1/n)$ times its held-out residual, the residual against the mean of the other rows.
A row in the fit looks closer to it than it is. The highlighted row's residual against the leaf mean that includes it (solid) is shorter than against the mean of the others (dashed). Drag the handle to change the number of rows in the leaf.
With 4 rows the in-sample residual is three quarters of the held-out one; with 20 it is 95%. Residuals computed on training data are systematically too small, and the effect is largest in small leaves. The CatBoost paper calls this **prediction shift** and argues it affects every standard implementation; its remedy, **ordered boosting**, computes each row's residual from a model that was not fitted on that row. I verified the paper's framing against its abstract only, and I have not reproduced its full argument here. ## What the differences mean for the choice Each difference above is a mechanism with a cost and a benefit. Reading them as a design space, with the figure that shows each one: | If your table looks like… | The mechanism that responds | Figure | A test to run (proposed) | | --- | --- | --- | --- | | millions of rows, many features, training time dominates | histograms and the subtraction trick; sampling rows or bundling features | bins, subtract, goss | compare wall time at equal validation error, with 255 bins against 32 | | structure concentrated in a few regions, plenty of signal | leaf-by-leaf growth reaches them with fewer leaves | growth, noise | fix the leaf budget; compare leaf-by-leaf with level-by-level | | few thousand rows, noisy labels | symmetric trees, small leaf budget, strong $\lambda$ | noise | compare with and without the symmetric constraint, using cross-validation | | high-cardinality categorical columns | ordered statistics; sorted category splits | leak, cat, shift | drop the categorical columns and see whether the gap between libraries closes | | gradients concentrated on few rows (heavy tails, rare positives) | gradient-based sampling | goss | check what share of $\lvert g\rvert$ the top fifth holds before relying on it | The right-hand column is a proposal. None of these tests was run here, and the table says where to look, not what you will find. Three cautions carry over from the figures. - **A tie on training error says nothing.** All three growth orders reach near-zero training error with enough leaves. Compare them on rows they have not seen. - **A speed-up is not free accuracy.** Histograms and sampling both approximate the exact gain; the figures show how large that approximation can be at coarse settings, and the gap closes as the settings grow. - **Defaults are part of the algorithm.** A library's default leaf count, bin count, regularisation and sampling rate decide which regime you are in; comparing two libraries at their defaults compares settings as much as methods. ## What this can and cannot tell you The derivation says what each library is *trying* to compute, and why the three agree on the equation. It does not say which is better on a given table. The comparisons above are on two small synthetic tables with exact thresholds, no early stopping, no row sampling, and one loss; the orders of magnitude (how fast a histogram loses accuracy, how far a symmetric tree falls behind) depend on the structure of the data and will change on yours. What carries over: - **Leaf budget, not depth, is the honest unit.** Level by level, leaf by leaf and symmetric trees only mean the same thing at $2^d$ leaves, and then they still differ in where the leaves go. - **Regularisation moves the gain before it moves the choice.** $\lambda$ and $\gamma$ shrink and prune; they matter more as the data get noisier. - **Leakage is a property of the encoding, not the library.** Whenever a feature is computed from the label, ask whether a row's own label is in its own feature. A test to run, proposed and not measured here: fix the leaf budget, the learning rate and the validation scheme, then compare the three libraries on your table with and without its high-cardinality categorical columns. If the gap closes without them, the encoding was the difference; if it does not, look at the growth order. The opening question asked why fitting leftovers works. It works because the leftover is a gradient: each tree is a step downhill on the training loss, restricted to what a tree can express, and its size is the bottom of a parabola. What the three libraries disagree about is the engineering of that step. ## Further reading - [Friedman — *Greedy Function Approximation: A Gradient Boosting Machine*](https://doi.org/10.1214/aos/1013203451), Annals of Statistics, 2001. Functional gradient descent and per-leaf line search. I did not open this page in the session; the title and venue are from memory. - [Chen and Guestrin — *XGBoost: A Scalable Tree Boosting System*](https://arxiv.org/abs/1603.02754). The regularised objective, the second-order gain, the sparsity-aware split finding and the weighted quantile sketch. - [Ke et al. — *LightGBM: A Highly Efficient Gradient Boosting Decision Tree*](https://papers.nips.cc/paper_files/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html). Gradient-based one-side sampling and exclusive feature bundling. - [Prokhorenkova et al. — *CatBoost: unbiased boosting with categorical features*](https://arxiv.org/abs/1706.09516). Ordered boosting and the treatment of categorical features, against prediction shift. - [Deriving the Prior-Data Fitted Network](pfn-derived) and [Deriving the Media Mix Model](mmm-derived), the same method applied elsewhere.