Why does gradient boosting still need ordered boosting when its categorical encodings are already leak-free?

## The shift moves up a level Gradient boosting builds an additive model in rounds. At round `t` the current ensemble `F(t-1)` predicts each training row, the loss's negative gradient at that prediction is computed for every row, and a new tree is fitted to those gradients (for squared error the gradient is just the residual `y - F(t-1)(x)`). The step nobody questions is the one that hides the problem: **`F(t-1)` was fitted on the same rows whose gradients you are computing.** Row `i` participated in choosing the earlier trees' splits and leaf values. Those trees are therefore slightly tuned toward `y_i`, so `F(t-1)(x_i)` is closer to `y_i` than it would be for a genuinely new point drawn from the same distribution. The gradient you compute for row `i` is systematically smaller in magnitude than the gradient the same point would produce out of sample. The conditional distribution of the gradient given the features differs between training data and fresh data — precisely the definition of the prediction shift that motivates ordered target statistics, applied now to residuals instead of features. Two consequences follow. First, the bias does not cancel over rounds; each round starts from an already-optimistic fit and adds to it, so the effect accumulates with the number of trees. Second, it is worst exactly where you most want help: small datasets and rare regions of the feature space, where one row exerts real leverage on the fitted model. Roughly speaking, one row's influence on a model fitted to `n` rows scales like `1/n`, so the shift shrinks as the sample grows. ## The ordered construction Ordered boosting applies the permutation trick to the gradients. Fix a random permutation of the training rows. Define a family of **supporting models**, where the model `M(j)` is trained using only the first `j` rows of that permutation. When you need the residual for the row sitting at position `i`, you evaluate it with `M(i-1)` — a model built from rows that came before it and therefore never saw `y_i`. The tree for the current round is then fitted to residuals none of which were contaminated by their own row. Because the same permutation drives the ordered target statistics, encodings and residuals stay consistent: a row is encoded from its history and scored by a model trained on that same history. ## Why the exact version is impossible and what replaces it The literal construction needs one supporting model per row, which is `n` models and `n` times the training cost — unusable on anything real. Practical implementations keep supporting models only for prefixes whose sizes grow geometrically (prefix lengths 1, 2, 4, 8, and so on), which is a logarithmic number of models, and use the largest available prefix model that still excludes the row. The approximation weakens the guarantee slightly and still multiplies memory and training time relative to the plain computation, which is why the plain, self-referential gradient remains an option in these algorithms rather than being deleted. ## How to recognise it in the wild The symptom of unaddressed shift is a training fit that keeps improving while holdout performance plateaus early or degrades, on a dataset small enough that any single row matters, often with high-cardinality categorical features whose encodings amplify the same effect. It is not the ordinary overfitting story of a too-deep tree: shrinking depth and adding regularisation help with variance, while the shift is a **bias** in the quantity being fitted. ## What it is not Ordered boosting is not row subsampling, and it is not bagging. Stochastic subsampling draws a different random subset per round to decorrelate trees and reduce variance; the subset can still contain the row whose residual you compute, so it does not remove the bias. Ordered boosting is also not a substitute for a held-out set — it makes the residuals used *during* fitting unbiased, but you still need untouched data to estimate generalisation and to choose how many trees to keep. And it costs nothing at scoring time: the supporting models are a training-time device, and the deployed ensemble is an ordinary sequence of trees. ## The judgment it demands Because the bias it removes scales down with sample size while its cost scales up with it, ordered boosting is a small-and-noisy-data instrument. On a few thousand rows with many rare category levels it can change the holdout number visibly; on tens of millions of rows it usually buys a difference lost inside validation noise while multiplying training time. Knowing the mechanism is what lets you make that call instead of turning the option on out of superstition.