CatBoost

Gradient boosting has dominated machine learning competitions and production systems for over a decade. Yet beneath its remarkable success lies a fundamental statistical flaw that went largely unrecognized until CatBoost's developers at Yandex formally characterized and solved it.

This flaw is called prediction shift, sometimes referred to as target leakage in the boosting literature. It occurs because traditional gradient boosting uses the same data points to both compute residuals and train the next tree—creating a subtle but systematic bias that degrades generalization performance.

Understanding prediction shift requires us to think carefully about what gradient boosting is actually doing: it's fitting models to gradients (negative residuals) computed from predictions made by the current ensemble. When those predictions are made on the same data used to train them, information leaks from the targets into the training process in ways that don't generalize.

To understand prediction shift, we must examine the mechanics of gradient boosting at a granular level. Consider the standard gradient boosting procedure:

1. Initialize the model: $F_0(x) = \arg\min_c \sum_{i=1}^n L(y_i, c)$
2. For each boosting iteration $t = 1, 2, ..., T$:
   • Compute pseudo-residuals: $r_{ti} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]{F=F{t-1}}$
   • Fit a base learner $h_t$ to the residuals $(x_i, r_{ti})$
   • Update the model: $F_t(x) = F_{t-1}(x) + \eta h_t(x)$

The critical observation is in step 2: we compute residuals $r_{ti}$ using predictions $F_{t-1}(x_i)$ on the same data points $(x_i, y_i)$ that were used to train $F_{t-1}$.

This creates what statisticians call conditioning on the training set—the residuals we're fitting are not independent samples from any meaningful distribution, but rather quantities that have been optimized on the very data we're using to compute them.

A Concrete Example of Prediction Shift

Imagine we have a dataset where the true relationship is $y = f(x) + \epsilon$, with $\epsilon$ being pure noise. An ideal learner would capture $f(x)$ and leave the noise alone.

In traditional gradient boosting:

• The first tree $h_1$ fits the data, capturing some of $f(x)$ but also fitting some of the noise $\epsilon_i$ for each sample $i$.
• When we compute residuals $r_{2i} = y_i - F_1(x_i)$, these residuals are smaller for samples where $h_1$ happened to fit the noise well (by chance).
• The second tree $h_2$ now sees residuals that are systematically biased—they underestimate the true residual for samples that $h_1$ overfit.
• This bias propagates and compounds through subsequent iterations.

The result: the ensemble becomes increasingly calibrated to artifacts of how it fit the training noise, rather than the underlying signal.

Let's formalize the prediction shift problem mathematically. Consider a dataset $\mathcal{D} = {(x_1, y_1), ..., (x_n, y_n)}$ drawn i.i.d. from distribution $P(X, Y)$.

For a gradient boosting model $F(x)$ trained on $\mathcal{D}$, define:

Conditional expectation given features (the target): $$\mu(x) = \mathbb{E}[Y | X = x]$$

Training prediction for sample $i$: $$\hat{y}_i = F(x_i; \mathcal{D})$$

where $F(x_i; \mathcal{D})$ explicitly denotes that the model was trained on $\mathcal{D}$, which includes $(x_i, y_i)$.

The residual used for gradient computation: $$r_i = y_i - F(x_i; \mathcal{D})$$

Now here's the critical insight. The expected residual conditional on the training set is: $$\mathbb{E}[r_i | \mathcal{D}] = \mathbb{E}[y_i | \mathcal{D}] - F(x_i; \mathcal{D})$$

But because $y_i$ is part of $\mathcal{D}$: $$\mathbb{E}[y_i | \mathcal{D}] = y_i$$

Therefore: $$\mathbb{E}[r_i | \mathcal{D}] = y_i - F(x_i; \mathcal{D})$$

This is not the same as the true expected residual we'd want to fit: $$\mathbb{E}[y - F(x) | X = x_i] = \mu(x_i) - \mathbb{E}[F(x_i)]$$

Quantifying the Shift

The prediction shift can be precisely quantified. For a model trained on $\mathcal{D}$ and applied to a new point $(x, y)$ from the same distribution:

$$\text{Shift}(x) = \mathbb{E}{\mathcal{D}'}[F(x; \mathcal{D}')] - \mathbb{E}{\mathcal{D}}[F(x; \mathcal{D}) | (x, y) \in \mathcal{D}]$$

where $\mathcal{D}'$ is an independent training set of the same size.

This shift measures how different our predictions are when $x$ is in the training set versus when it's held out. For an unbiased learner, this should be zero—but gradient boosting systematically produces non-zero shift due to the target leakage in residual computation.

The magnitude of prediction shift typically:

• Increases with the number of boosting iterations
• Increases with the complexity (depth) of base learners
• Decreases with dataset size (more data dilutes the influence of any single point)
• Increases with the learning rate (larger steps amplify the bias)

CatBoost introduces ordered boosting, a principled solution to prediction shift that maintains the efficiency of gradient boosting while eliminating its statistical bias. The key insight is deceptively simple: when computing residuals for a sample, use predictions from a model that has never seen that sample.

The Ordered Boosting Algorithm

1. Generate a random permutation $\sigma$ of the training indices ${1, 2, ..., n}$
2. For each boosting iteration $t$:
   • For each sample $i$, compute its residual using a model trained only on samples appearing before $i$ in the permutation: $$r_{ti} = -\left[\frac{\partial L(y_i, F)}{\partial F}\right]{F=F{t-1}^{\sigma, i}}$$ where $F_{t-1}^{\sigma, i}$ is trained on ${(x_j, y_j) : \sigma(j) < \sigma(i)}$
   • Fit the base learner to these unbiased residuals

The Crucial Difference

In traditional gradient boosting, we compute:

• $r_i = g(y_i, F(x_i))$ where $F$ was trained on all data including $(x_i, y_i)$

In ordered boosting, we compute:

• $r_i = g(y_i, F^{<i}(x_i))$ where $F^{<i}$ was trained on data excluding $(x_i, y_i)$ and all subsequent samples

The Permutation Ensemble

Using a single permutation would introduce its own bias—samples early in the permutation would have residuals computed from weak models, while later samples would have residuals from strong models. CatBoost addresses this through multiple permutation models:

During training, CatBoost maintains $s$ different permutations ${\sigma_1, ..., \sigma_s}$ (typically $s = 4$). For each tree being added to the ensemble:

1. One permutation is used for structure learning (determining splits)
2. Leaf values are computed using a different permutation to avoid overfitting the structure selection

This ensemble of permutations smooths out the variance introduced by any single ordering while maintaining the unbiased residual computation that eliminates prediction shift.

A naive implementation of ordered boosting would be computationally prohibitive—training $n$ different models to compute $n$ residuals at each iteration would multiply complexity by a factor of $n$. CatBoost employs several sophisticated optimizations to make ordered boosting practical.

Incremental Model Updates

The key insight is that models $F^{<i}$ and $F^{<i+1}$ differ by only one sample. Instead of training from scratch, CatBoost maintains the model incrementally:

For decision tree base learners, this means:

• Histograms for split finding are updated incrementally as samples are added
• Leaf value statistics are maintained as running sums
• Adding sample $i+1$ to the model requires only $O(\log n)$ updates to tree statistics

Oblivious Decision Trees

CatBoost uses oblivious (symmetric) decision trees as base learners, which are crucial for efficient ordered boosting:

• All nodes at the same depth use the same split
• Tree structure is independent of leaf values
• This allows the same tree structure to be used across all ordering prefixes

We'll explore symmetric trees in detail in a later section, but their key property here is: once the tree structure is determined, computing leaf values for any subset of the data is O(n).

Understanding when ordered boosting provides the most significant advantage helps practitioners make informed decisions about algorithm selection.

When Ordered Boosting Helps Most

Ordered boosting's benefits are most pronounced in scenarios where prediction shift is most severe:

1. Small datasets (n < 10,000): With fewer samples, each point's influence on the model is larger, making target leakage more impactful.

2. High model complexity: Deeper trees and more iterations create more opportunities for the model to memorize training noise.

3. High noise-to-signal ratio: When true signal is weak relative to noise, the bias from prediction shift becomes a larger fraction of total error.

4. Imbalanced classes: Minority class samples have outsized influence per-sample, amplifying leakage effects.

When the Advantage is Less Pronounced

Conversely, ordered boosting adds complexity with diminishing returns when:

1. Large datasets (n > 100,000): Each sample has minimal influence on predictions; dilution naturally reduces prediction shift.

2. Strong regularization: Aggressive early stopping and shallow trees already limit overfitting through other means.

3. High signal-to-noise: When signal dominates, the bias from prediction shift is small relative to the signal being learned.

CatBoost's ordered boosting comes with formal theoretical guarantees that distinguish it from heuristic regularization approaches. These guarantees provide principled confidence in the algorithm's behavior.

Unbiasedness of Residuals

The core theoretical property is that residuals computed via ordered boosting are unbiased estimators of the true gradient:

$$\mathbb{E}[r_i | x_i] = \mathbb{E}\left[\frac{\partial L(y, F)}{\partial F}\bigg|_{F=F^{<i}(x_i)}\right]$$

This expectation is taken over:

• The randomness in $y_i$ given $x_i$
• The randomness in the permutation $\sigma$
• The randomness in samples appearing before $i$ in the permutation

For traditional gradient boosting, this expectation is biased because $F$ saw $y_i$.

Consistency and Convergence

Under mild regularity conditions, ordered boosting is consistent—as $n \to \infty$ and the number of iterations $T \to \infty$ appropriately:

$$F_T(x) \xrightarrow{P} f^*(x) = \arg\min_f \mathbb{E}[L(Y, f(X))]$$

The convergence rate matches optimal rates for gradient descent in function space, without the systematic bias that slows convergence in traditional boosting.

Variance Analysis

While ordered boosting eliminates bias, it introduces variance from the random permutation. This variance-bias tradeoff is favorable in practice:

• Variance from permutation: $O(1/n)$ due to averaging effects across samples
• Bias eliminated: Can be $O(1)$ in traditional boosting (doesn't vanish with $n$)

The permutation variance is further reduced by:

1. Using multiple permutations (default: 4 in CatBoost)
2. Averaging predictions from models trained with different permutations at inference time

Generalization Bounds

For classification with the exponential loss, ordered boosting achieves generalization bounds that scale as:

$$R(F_T) \leq \hat{R}(F_T) + O\left(\sqrt{\frac{T \cdot VC(\mathcal{H})}{n}}\right)$$

where:

• $R(F_T)$ is the true risk
• $\hat{R}(F_T)$ is the empirical training risk
• $T$ is the number of boosting iterations
• $VC(\mathcal{H})$ is the VC dimension of the base learner class

Crucially, this bound doesn't require additional correction terms for the prediction shift bias that would appear in analysis of traditional boosting.

Ordered boosting represents one of the most significant theoretical advances in gradient boosting since its inception. By formally characterizing and eliminating prediction shift, CatBoost achieves better generalization through principled mechanism design rather than after-the-fact regularization.