What is This for?

Therefore, this is a well-studied domain with a plethora of known approaches to tackle it at scale, and one of the most successful ones with widespread adoption and great baseline performance, is the Gradient Boosted Decision Trees (GBDT) class of methods, of which XGBoost is one of its most popular instantiations. A short, non-exhaustive listicle of where it shows up in practice:

• Kaggle dominance - in winning tabular solutions since 2015, from the ASHRAE Great Energy Predictor III to the TabArena living benchmark
• The Higgs boson challenge, high-energy physics
• Credit scoring and loan default forecasting
• Medicare fraud detection
• The default tabular baseline in benchmarks - Grinsztajn et al., Shwartz-Ziv & Armon, McElfresh et al.
• Still ahead of tabular foundation models past $\sim 10^4$ rows - see A Closer Look at TabPFN v2
• Ahead of tuned deep nets and deep sequence models at scale

The question then arises, what makes them such effective algorithms and how do they work under the hood? ^[1][1]Per my own experience, the concept and theory of Decision Trees are widely known amongst practitioners as it's widely taught in schools. GBDT however, much less so! This short essay sets out to answer this exact question from an applied perspective instead of a dense rigorous treatment, as there are already many existing texts on that - The Elements of Statistical Learning and Boosting: Foundations and Algorithms - and I am personally much more interested in knowing what makes it tick and the reason behind its unreasonable effectiveness out-of-the-box. The end goal is to provide a sufficient technical exposition in an intuitive yet grounded way, and then leverage that understanding to answer the aforementioned question, which hopefully will help my fellow practitioners make better decisions with these tools in their day-to-day work.

A Little Historical and Ontological Detour

The idea of iterative refinement by combining a collection of weak learners to yield a stronger learner is a pretty intuitive one in retrospect, and this is exactly how GBDT works - it combines many Decision Trees into a "super-tree" in a specific way such that the super-tree is more powerful than its constituents.

One of its roots can be traced back to Kearns and Valiant (1989; J. ACM 1994) in PAC learning ^[2][2]Which has one of the funniest names in my opinion - Probably Approximately Correct Learning, ha! when they tussle with the question of whether it's possible to create a strong learner (model) with arbitrarily low error by combining only weak learners, that individually, are only marginally better than random!

Turns out - yes you can, and this gave birth to the ensemble class of methods we all know and love today. I'll skip over straight to the landmark result - for brevity - of AdaBoost (Freund and Schapire, 1997), and this miraculous algorithm, although simple in concept, was shown to be able to drive training error to 0 exponentially-fast, and more interestingly its test time error continues to improve even after the training error has hit $0$! In short and with great deal of simplification, AdaBoost works by maintaining a distribution over its training samples. As the successive weak learners get trained and "combined" into the wider structure of the super-learner, the training samples used to fit each successive weak learner are reweighted (up or down weighted) so as to prioritize - give a boost (!) - the samples where it's making mistakes. The idea, is to learn with more emphasis on the "hard" samples to get them right next time; for output, it uses a simple weighted voting mechanism amongst weak learners (each weighted by a scalar, $\alpha_m$) to decide on what the final value of the super structure would be. Pretty straightforward!

View AdaBoost rounds ↗

Then Friedman (2001) took it a step further, and suggested the idea of fitting each new weak learner to the negative gradient of the loss with respect to the pseudo-residuals, for any differentiable loss, to drive the iterative adaptation process - hence, Gradient Boosting! This essentially recast the solution from a reweighting one, to a numerical optimization task. Written out, the ensemble after $m$ rounds is just the previous ensemble plus one more tree, and that tree is itself just a piecewise-constant function over the regions its splits carve out:

$$\begin{aligned} F_m(x) &= F_{m-1}(x) \;+\; \eta\, h_m(x), \\[0.35em] h_m(x) &= \sum_{j=1}^{T_m} w_{mj}\,\mathbf{1}\!\left\{x \in R_{mj}\right\}. \end{aligned}$$

where

Note that for a single tree at round $m$, the regions $R_{m1},\dots,R_{mT_m}$ are disjoint and cover the whole feature space, so for any given sample on the manifold, $x$ will only fall into a single region and hence be associated with only a single leaf weight as per the tree equation above. Across trees however, the regions $R_{mj}$ from different rounds $m$ can overlap and it is this cumulative iterated segmentation that produces the final margin. Then simply apply a threshold, and voila(!) out pops the class.

View XOR progression ↗

XGBoost Proper

Now we have a GBM (Friedman, 2001) that is nice to deal with in the form of a familiar optimization problem, where we can "intelligently" learn an "optimal" ensemble (boosting) model by stacking weak learners in an end-to-end manner - and indeed it's pretty effective! However, it still has some clunky bits and gaps, and it took Chen and Guestrin in 2016 to finally bridge those gaps with the XGBoost that we know and love today. There are a lot of engineering tricks and clever reformulation that made XGBoost so much better than GBM, and so well adapted to the real-world, large-scale workloads we see in practice, but in the interest of time, I'll focus only on the core, and most consequential bits, providing a necessary and sufficient exposition to the question of "how does it work?"

Reformulation as a Regularized Objective

Friedman's GBM already had shrinkage, subsampling and tree-size limits, and Newton-step boosting existed (LogitBoost). What XGBoost did was fold the explicit penalties $\gamma T + \tfrac12\lambda\|w\|^2$ into the second-order objective so that leaf weights and split gains come in as a single closed-form parcel, and most importantly, did a lot of polishing to engineer the whole thing to scale. By reformulating the learning task as a regularized objective, it in one shot naturally deals with regularization and adverse spurious sample selection in a single pass, instead of a cascade of steps, enabling stabler learning even with tricky datasets.

The objective function

For a regularized objective at round $m$, and with the previous $m-1$ trees frozen (so their $\Omega$ terms are constant and dropped), we have

$$\mathcal{L}^{(m)} \;=\; \sum_{i=1}^{n} \ell\!\left(y_i,\; \hat{y}_i^{(m-1)} + h_m(x_i)\right) \;+\; \Omega(h_m)$$

where $i$ is the sample index, and $\hat{y}_i^{(m-1)}$ is the output from $F_{m-1}$. Also, for simplicity, we're just gonna deal with a binary classification task, therefore the loss is simply the Binary Cross-Entropy.

$$\ell(y_i, \hat{y}_i) \;=\; -\,y_i \hat{y}_i \;+\; \ln\!\left(1 + e^{\hat{y}_i}\right).$$

The regularizer

$$\Omega(h_m) \;=\; \gamma T \;+\; \tfrac{1}{2}\lambda \sum_{j=1}^{T} w_j^{2} \;+\; \alpha \sum_{j=1}^{T} \lvert w_j \rvert$$

$\Omega(h_m)$ is the regularization term for learner $h_m$ (writing $T$ and dropping the subscript for brevity), and can be broken down as follows:

• Leaf-count penalty $\gamma T$ (gamma) - penalizes the number of leaves. This is a simple additive cost per leaf on the number of total leaves, $T$, so as to prevent over-splitting of nodes and to make sure each split is done only with sufficient loss reduction in return.
• L2 shrinkage $\tfrac{1}{2}\lambda \sum_{j=1}^{T} w_j^{2}$ (lambda) - penalizes the magnitude of the assigned leaf value. It effectively tries to push each $w_j$ toward 0, so more emphasis is placed on meaningful samples only. This is most aggressive where $H_j$ (Hessian or curvature) is small (lots of spurious samples).
• L1 sparsity $\alpha \sum_{j=1}^{T} \lvert w_j \rvert$ (alpha) - also penalizes magnitude and additionally encourages sparsity: it can drive a $w_j$ exactly to 0.

As a whole, the above should be a familiar expression for those with some optimization background: this is just a regularized objective. As an aside, the $\tfrac{1}{2}$ on the L2 term is just a mathematical nicety - it cancels on differentiation and keeps the later expression for $w^{*}$ tidy for those picky statisticians. Also, everything below assumes $\alpha = 0$.

From First Order to Second Order Estimation

XGBoost also uses 2nd order optimization rather than 1st order so as to account for not only the gradient, $G$, but also the curvature of the loss landscape, $H$ (the Hessian, in fancy-speak). This is super helpful throughout the learning process, such that it enables the learners to not only determine the direction of steepest descent, but also one that's nicely conditioned. To see why it matters, let's define the gradient and curvature terms first:

Gradient and Hessian

Both are derivatives of the (binary cross entropy) loss with respect to the model's output, evaluated at the current margin, $\hat{y}_i^{(m-1)}$:

$$G_i = \left.\frac{\partial \ell(y_i, \hat{y})}{\partial \hat{y}}\right|_{\hat{y} = \hat{y}_i^{(m-1)}} = \sigma\!\left(\hat{y}_i^{(m-1)}\right) - y_i = p_i - y_i,$$ $$H_i = \left.\frac{\partial^{2} \ell(y_i, \hat{y})}{\partial \hat{y}^{2}}\right|_{\hat{y} = \hat{y}_i^{(m-1)}} = p_i\,(1-p_i).$$

where

• $G_i \in (-1,1)$ - a signed error. $G_i < 0$ means the margin must increase and vice versa.
• $H_i \in (0,\,0.25]$ - the local curvature, maximal at $p_i = 0.5$ (most uncertain). This effectively acts as the support mass of a leaf - large where the model is least confident, and it dampens the step $w^{*}$ there rather than amplify it, and vice versa.

Basically, the gradient provides the signal of "where to go" with respect to the current loss landscape, and the curvature then characterizes where the most interesting regions are, given what the model currently knows (and doesn't know).

Optimal leaf weight

Next, we see where $G$ and $H$ are directly applied - specifically in computing the optimal leaf weight $w_j^{*}$ of each leaf $j$ for a particular tree, $h_m$. Very conveniently, each leaf $j$ contributes $G_j w_j + \tfrac{1}{2} (H_j + \lambda) w_j^{2}$ to the objective (we'll derive this in the next section) where $\lambda > 0$ is a regularizing term. Therefore, by setting the derivative to zero, the optimal weight $w_j^{*}$ admits a closed form solution:

$$\frac{\partial}{\partial w_j}\left[G_j w_j + \tfrac{1}{2}(H_j+\lambda)w_j^{2}\right] \;=\; G_j + (H_j + \lambda) w_j \;=\; 0$$ $$\boxed{\;\; w_j^{*} \;=\; -\frac{G_j}{H_j + \lambda} \;=\; -\frac{\sum_{i \in I_j} (p_i - y_i)}{\sum_{i \in I_j} p_i(1-p_i) + \lambda} \;\;}$$

Obviously, the second derivative is $H_j + \lambda > 0$, so this is a minimum. Note that $\lambda$ serves to dampen the weights of leaves built on little Hessian mass (e.g. nothing much to learn). So now, we have a way to condition the learning on the "informativeness" of certain samples at a given round with $H$, and control for how much emphasis should be placed on it with $\lambda$.

View curvature comparison ↗

Very Smart Plumbing

Chen and Guestrin really went the extra mile to make sure that XGBoost is practically useful. One good example, is how it puts into practice what we've just covered, to efficiently evaluate the gradient, $G$ and curvature $H$, in its objective function!

Second-order surrogate

As nice as the regularized objective is, it unfortunately has no closed-form minimizer over tree structures and weights, and hence we need some way to go around this; the common toolkit to solve such functions is iterative and slow; this would be a tough sell for learning with large-scale datasets, which are so prevalent in the wild (e.g. transactions at Stripe each hour, number of Uber bookings per day). Therefore, XGBoost introduced a surrogate as a bypass, by simply taking the second-order Taylor expansion of the function, which can be easily evaluated directly and is sufficiently representative at local-scale (which our Trees are operating at). Taylor-expand the objective to second order around $\hat{y}_i^{(m-1)}$ and drop the constant $\ell(y_i, \hat{y}_i^{(m-1)})$, and that yields:

$$\tilde{\mathcal{L}}^{(m)} = \sum_{i=1}^{n} \left[ G_i\, h_m(x_i) + \tfrac{1}{2} H_i\, h_m^{2}(x_i) \right] + \gamma T + \tfrac{1}{2}\lambda \sum_{j=1}^{T} w_j^{2}$$

Every sample in leaf $j$ receives the same output $w_j$, so regroup the sum w.r.t. each leaf, then

$$\tilde{\mathcal{L}}^{(m)} = \sum_{j=1}^{T} \left[ \Big(\sum_{i \in I_j} G_i\Big) w_j + \tfrac{1}{2}\Big(\sum_{i \in I_j} H_i + \lambda\Big) w_j^{2} \right] + \gamma T$$

Now, let's make this a bit nicer to write by defining the leaf aggregates

$$\boxed{\;G_j = \sum_{i \in I_j} G_i, \qquad H_j = \sum_{i \in I_j} H_i\;}$$

where $i$ are samples at node $I_j$, and therefore

$$\tilde{\mathcal{L}}^{(m)} = \sum_{j=1}^{T} \left[ G_j w_j + \tfrac{1}{2}(H_j + \lambda) w_j^{2} \right] + \gamma T .$$

Take a moment and notice that the above is $T$ one-dimensional quadratics in $w_j$. The sample index $i$ has vanished and a leaf is now just the pair $(G_j, H_j)$. This makes downstream terms much easier to organize and compute exactly with the gradient, Hessian and optimal-leaf-weight expressions we've already derived!

Structure score

We can go further, and use the same idea to also determine how a tree should split at each node with what we have already derived. Substitute $w_j^{*}$ back, and summing over all leaves we can see that the tree scores exactly

$$\boxed{\;\; \tilde{\mathcal{L}}^{*}(q) \;=\; -\frac{1}{2}\sum_{j=1}^{T} \frac{G_j^{2}}{H_j + \lambda} \;+\; \gamma T \;\;}$$

This is the quality of a tree structure $q$ (tree spawned at round $m$) - of course, lower is better. It plays the role that impurity / Gini plays in a classification tree, but derived from the actual loss directly. And from the above, we can also define the per-node score, $\mathcal{S}(I)$ as

$$\mathcal{S}(I) \;=\; \frac{G_I^{2}}{H_I + \lambda}.$$

What we have done so far, is to show that at the heart of XGBoost, the optimal value of a leaf and the quality of a learned tree (weak-learner) are explicitly parameterized as functions of the first, $G$ and second order, $H$ statistics for any twice-differentiable loss function - very nice! Next, we need a way to compare before vs after a split to quantify whether a split is worth it or not. We do so by introducing a new function called the Gain as such

$$\mathrm{Gain} \;=\; \underbrace{\tilde{\mathcal{L}}^{*}(\text{before})}_{\text{unsplit}} \;-\; \underbrace{\tilde{\mathcal{L}}^{*}(\text{after})}_{\text{split}}$$

Consider splitting node $I$ into $I_L$ (left) and $I_R$ (right), such that $I = I_L \sqcup I_R$ (disjoint), and because $G_I$ and $H_I$ are simply sums of $G_i$ and $H_i$, therefore

$$G_L + G_R = G_I \qquad\qquad H_L + H_R = H_I$$

This makes it trivial to recover either side once we have accumulated $G$ and $H$ for one side. Also, as one node splits into two, $T$ increases by exactly 1, thereby accruing an additional penalty of $1 \times \gamma$. By substituting the structure score into the Gain equation and making use of the sum decomposition above, we arrive at the full Gain equation as follows

$$\boxed{\;\;\mathrm{Gain} \;=\; \frac{1}{2}\left[\; \underbrace{\frac{G_L^{2}}{H_L+\lambda}}_{\text{left child}} \;+\; \underbrace{\frac{G_R^{2}}{H_R+\lambda}}_{\text{right child}} \;-\; \underbrace{\frac{(G_L+G_R)^{2}}{H_L+H_R+\lambda}}_{\text{parent, unsplit}} \;\right] \;-\; \gamma \;\;}$$

where

• Left child score $\dfrac{G_L^{2}}{H_L+\lambda}$ - how much loss the left branch can reduce
• Right child score $\dfrac{G_R^{2}}{H_R+\lambda}$ - how much loss the right branch can reduce
• Parent score $\dfrac{(G_L+G_R)^{2}}{H_L+H_R+\lambda}$ - how much loss the parent node can already reduce by itself without splitting
• $\boldsymbol{\gamma}$ - the additional leaf-penalty we've incurred by splitting one-to-two

XGBoost's simple yet effective strategy is to simply greedily pick the action with largest Gain! Notice the Gain is zero only when the two children want the same weight, $G_L/(H_L{+}\lambda) \approx G_R/(H_R{+}\lambda)$, in which case one shared weight already captures it and the split is pointless. Opposite-sign gradients, where the L/R branches want to move the margin in different directions are the clearest case of disagreement, meaning there's something worth splitting on here, and same-sign gradients with different magnitudes or curvature also produce positive Gain. In order for a split proposal to be accepted, by default, it needs to have a positive Gain value, such that

$$\max \mathrm{Gain} > 0 \quad\Longleftrightarrow\quad \frac{1}{2}\left[\frac{G_L^{2}}{H_L+\lambda} + \frac{G_R^{2}}{H_R+\lambda} - \frac{G_I^{2}}{H_I+\lambda}\right] \;>\; \gamma,$$

so $\gamma$ is literally the minimum loss reduction a split must induce. The routing rule is then simply: for samples where $x_{k^{*}} < v^{*}$ go left, else right, subjected to two additional structural constraints:

$$\min(H_L,\, H_R) \;\ge\; \texttt{min\_child\_weight}, \qquad \text{depth} \;\le\; \texttt{max\_depth}.$$

min_child_weight is a cutoff on Hessian mass so that only gradient induced by sufficiently meaningful or salient samples, not sample count, will be considered in the Gain equation; there's not much meaning creating more splits on already well-classified data points. For example, a child of 50 confidently-classified samples ($H_i \approx 0$) will fail the cutoff, while a child of 5 uncertain ones passes and can have a positive Gain since there's something worth learning here still. max_depth is pretty self-explanatory, it's just the maximal depth limit of the tree, $h_m$ that we explicitly define and enforce; this is to prevent overfitting since a tree of depth $D$, can model interactions up to order of $D$.

In effect, all these mechanics replace tedious per-leaf optimization with simple closed form evaluation with just 2 computed scalars ($\lambda$ and $\gamma$ are fixed) that we can precompute in a batch ahead of time, and thus when it comes time to determine the split at a given node $j$, we can just do a series of fetch-and-sum! Not only that, with some clever arrangements, we can find the "optimal" split in one pass per feature with only iterative sum ops as shown below in Fig 4 for a toy 8-sample dataset.

View split scan ↗

At a node with sample set $I$, for each feature $k \in \{1,\dots,d\}$:

1. Take $I$ in ascending (by convention) order of $x_{ik}$ (pre-sorted once, globally; the node only walks its own subset): $x_{(1),k} \le x_{(2),k} \le \dots \le x_{(|I|),k}$.
2. Precompute totals $G_I = \sum_{i \in I} G_i$, $H_I = \sum_{i \in I} H_i$.
3. Initialise $G_L \leftarrow 0$, $H_L \leftarrow 0$.
4. Then sweep the boundaries $s = 1, \dots, |I|-1$ and assign: $G_L \leftarrow G_L + G_{(s)}$, $H_L \leftarrow H_L + H_{(s)}$, $G_R \leftarrow G_I - G_L$, $H_R \leftarrow H_I - H_L$.
5. Compute Gain and greedily select over all features $k$ at threshold $v$ that passes the cutoff: $(k^{*}, v^{*}) = \operatorname*{arg\,max}_{k,\,v} \mathrm{Gain}(k,v)$.

All this turns what could've been an $O(|I|^2)$ operation per feature per node if done naively (rescanning all $|I|$ samples at each of the $|I|-1$ boundaries), into an $O(1)$ procedure per boundary, and an $O(|I|)$ sweep per feature per node after a one-off $O(n \log n)$ sort per feature - very nice! The above, in turn, enables / unlocks more downstream optimization goodies such as cache-aware gradient prefetching, distributed workflows and more.

There's a slight wrinkle however in my explanation above due to simplifications for clarity. ^[3][3]The exact sweep over every one of the $|I|-1$ boundaries, as I described, is the greedy recipe of plain GBDT (and XGBoost's exact method); the modern default hist uses a related histogram binning. XGBoost also offers an approximation method called the weighted quantile sketch (used for distributed / out-of-core training) - a method leveraging smaller sample approximation of the full thing for faster computation. Formally, for feature $k$ define the Hessian-weighted rank $r_k(z) = \sum_{i:\,x_{ik}<z} H_i \,/\, \sum_i H_i$, then pick only a handful of candidate thresholds $\{v_{k,1}, \dots, v_{k,l}\}$ such that adjacent candidates differ in rank by less than some $\epsilon$, giving roughly $1/\epsilon$ candidates to sweep instead of $|I|-1$. Intuitively, the idea is to build a histogram "sketch" with bins that hold equal amounts of uncertainty ($H$) instead of counts, and only test the bin edges, which is a much smaller set to sweep over!

Inbuilt Handling of Missing Values

Last but not least of the things to highlight, XGBoost has an inbuilt mechanism to deal with missing values in an effective way (super helpful in almost all real world datasets where data is never completely observable). In short, at each node, it checks which branch is best to put the missing value data points to (L or R), and directly dumps all the missing value points to the side that maximizes the Gain.

$$\mathrm{Gain}^{*} \;=\; \max\Big(\, \mathrm{Gain}\big(I_L \cup I_{\text{missing}},\; I_R\big),\;\; \mathrm{Gain}\big(I_L,\; I_R \cup I_{\text{missing}}\big) \Big)$$

This is obvious in hindsight and almost too simple to believe, but it turns out to be very effective in practice, making XGBoost super accommodating to sloppy datasets.

Okay, the above is a lot to take in, and indeed deserves a more thorough treatment to fully illustrate its depth and profoundness. However, I'll stop here and leave it as further reading, or perhaps a fuller in-depth essay if there's a demand for it. Fig 5 provides an overview of what we've discussed here to summarize things.

View full pipeline ↗

Why Does it Work so Well?

After all that exposition, we now turn our attention to the question oft-asked "why is XGBoost so good?". Indeed, there've been multiple times with which I've been forwarded this question and other similar ones along the lines of "why is X (e.g. neural net) not better than XGBoost [in tabular tasks]"?

The answer is context-dependent as one would expect. Note that we're only discussing in the context of tabular datasets and tasks here, which is where XGBoost is most applied - there's little doubt that outside of this domain, Deep Neural models are the reigning champions. Now back to the question at hand - in order to focus the argument, let's narrow our discussion to XGBoost (GBDT) vs Deep Neural Networks (DNN) such as Transformer and Deep Tabular Network.

First, for the positives of DNN. In terms of expressivity, DNN are definitely much more powerful in this regard than XGBoost, so they can represent a far wider class of function mappings compactly (universal approximation, benefits of depth). Not only that, modern Deep Tabular Networks like TabPFN have shown remarkable abilities with in-context learning that's very sample efficient yet performant, being able to learn with just hundreds to thousands of samples. At its limit, even zero-shot transfers without any task-specific training data at all for certain domains; of course, this excludes the pre-training of the transformer on a general corpus. This could be very useful indeed for tasks with very little available data or labels in cold-start settings, or for quick ad hoc tasks where one needs to make a prediction on a specific context without first training a model - hence, I'm very excited to see where this will go!

That being said, in a majority of real-world tasks, we do have a lot of available data - think of any products such as Stripe or Instagram, and at their scale, data abundance is definitely not a problem. Plus, DNN are very compute heavy, being slow to train and serve unlike XGBoost which is super snappy, sufficient to meet the high SLA / TPS requirements of real-time systems without needing a GPU; great news for those with a heavy compute backlog! On the other side of the train-serve equation, non-neural models like XGBoost are also endowed with very quick training speed, paired with the ability to ingest huge datasets ($>100$M rows) via lazy streaming, thereby making it much faster to iterate with unlike the lumbering DNN.

Now, other than the obvious and logistical (compute) reasons, XGBoost also admits certain very helpful properties in its learning process as well! The flipside problem with DNN on their expressivity is the issue of overfitting, which comes at no surprise to any practitioners - it's not easy to "tame" a DNN so it wouldn't just memorize the dataset trivially. XGBoost on the other hand, is capable of dealing with the issue of overfitting naturally - as we've seen previously, all GBDT like XGBoost does, is learn how to partition the feature space into axis-aligned "rectangles" to segment the samples cleanly.

It is precisely the "constraint" of only being able to learn additive axis-aligned rectangular partitions - no rotations or bending! - that naturally induces a structural regularization, thereby preventing it from overfitting easily, e.g. it cannot learn arbitrarily smooth feature segmentation boundaries. Added to that, the margin maximizing effect of boosting in the small-$\eta$ limit further forces an additional constraint in a useful way, preventing degeneration into trivial margin-agnostic segmentation that's highly irregular or jagged. In short, the structure of the trees themselves with their margin maximizing tendency provides built-in, implicit regularization mechanics to XGBoost, on top of other explicit regularizing forces such as $\gamma$, $\lambda$ and co!

Upon some consideration, one could also notice certain congruency between tabular datasets and the structure of XGBoost we just covered in prior sections. For example, the feature manifold of tabular data is typically irregular (e.g. non-smooth with sharp thresholds) such as credit scores - which have categorical spans, where a certain score-band means "poor" while being above a certain score indicates an "excellent" credit risk profile - or glucose level - above certain values, we classify as excessive; hyperglycemia or hypoglycemia - and so on. DNN are biased towards smooth, low frequency boundaries, whereas GBDT like XGBoost's staircase-like boundaries match this inductive bias perfectly. Also, in tabular data, columns are oftentimes "self-describing" or individually-meaningful - annual income and age are by themselves salient and are widely used "abstractions" - which the axis-aligned nature of GBDT naturally assumes for free without needing to manually "impose" any additional constraints.

For example, take the income and age columns of a dataset, and replace them with their sum or differences. No information has been lost, it's just written along a rotated pair of axes, which may or may not be a useful joint feature for the task at hand; worse if it's destructive! Tabular data arrives already with a natural basis imposed by whoever created the columns, so a learner that is invariant to rotation has to rediscover that orientation from scratch, mixing together features with very different statistical properties along the way, which may not yield any useful signal. GBDT on the other hand, naturally leans into these given tabular priors nicely.

Last but not - exhaustively - least, is the ability of GBDT to easily and naturally ignore uninformative features, of which there usually are in any real world datasets, by simply not splitting on those features, and be able to do so for free as part of its Gain computation's factor already, unlike the DNN which could degrade due to relative influences; though, this is more of a problem of plain feedforward networks as newer Transformer-based models like FT-Transformer have accounted for with their per-feature tokenizer.

All these taken together, are reasons why Gradient Boosted Decision Trees like XGBoost normally rank so well in tabular or structured learning tasks and benchmarks, and are so often preferred by production teams even to this day - it's just a tabular-shaped solution to a tabular world, and it's zippy too!

Closing Words

Now dear Readers, we're at the end of our journey. That being said, I must point out a few areas of deficiencies and shortcuts I have taken in this exposition for clarity and brevity, lest I be stoned by the but-ackchyually-police!

First off, the enumeration of XGBoost's mechanics is incomplete and only covers core mechanics that I believe to be necessary and sufficient. For example, there's no mention of how the tree is grown to max_depth and then performs backward-pruning, the full treatment of the weighted quantile sketch and approximate split finding, how it handles categorical data, how it performs multicore training, how additional improvements have allowed it to stream and train lazily for datasets that won't fit in memory, how it computes feature importance, and many more. For those, I would direct the motivated reader to the original paper and the latest official documentation.

Furthermore, the theoretical treatment is also rather lackluster as it's not intended to be a textbook. However, there's a great deal to be gleaned from and pondered on via a more rigorous treatment in depth. For example, how the learning procedure can be seen as an $\ell_1$ walk on the axis-aligned path in the function space, how margin theory can help us understand why it can learn so well, what are its convergence properties and levers that affect it most directly, which in turn help us build intuition to understand why a turn-up-the-rounds-to-11-and-lower-the-learning-rate is a decent strategy in general when tuning XGBoost.

Last and most importantly in my opinion, is the omission on how the model behaves in extreme settings such as dealing with a dataset with huge prevalence imbalance - which is very common in domains such as credit-card fraud, cancer diagnosis, and many others - and as a result this impacts calibration and uncertainty quantification, which in turn affects downstream dependencies such as the policy engine and so on. Other just as important considerations are on dealing with a drifting non-stationary environment, and when uncertainty estimation is unreliable or otherwise. Perhaps these can be addressed in a future write-up on operational considerations in practice.

That's the tour, and I hope that this has been helpful and not too dreadful of a read. For any inquiries, errors and corrections, or simply a conversation on the topic, feel free to reach out and I shall make the best endeavor to reply swiftly. Ta-ta!

References

1. [1]
   Benchmarking state-of-the-art classification algorithms for credit scoring: An update of research

   European Journal of Operational Research. [Online]. Available: https://doi.org/10.1016/j.ejor.2015.05.030
2. [2]
   A data-driven approach to predict the success of bank telemarketing

   Decision Support Systems. [Online]. Available: https://doi.org/10.1016/j.dss.2014.03.001
3. [3]
   Explainable machine-learning predictions for the prevention of hypoxaemia during surgery - Nature Biomedical Engineering

   Nature. [Online]. Available: https://doi.org/10.1038/s41551-018-0304-0
4. [4]
   M5 accuracy competition: Results, findings, and conclusions

   International Journal of Forecasting. [Online]. Available: https://doi.org/10.1016/j.ijforecast.2021.11.013
5. [5]
   XGBoost: A Scalable Tree Boosting System

   arXiv.org. [Online]. Available: https://arxiv.org/abs/1603.02754
6. [6]
   The ASHRAE Great Energy Predictor III competition: Overview and results

   arXiv.org. [Online]. Available: https://arxiv.org/abs/2007.06933
7. [7]
   TabArena: A Living Benchmark for Machine Learning on Tabular Data

   arXiv.org. [Online]. Available: https://arxiv.org/abs/2506.16791
8. [8]
   Higgs Boson Discovery with Boosted Trees

   PMLR. [Online]. Available: https://proceedings.mlr.press/v42/chen14.html
9. [9]
   Deep Learning for Credit Scoring: Do or Don't?

   European Journal of Operational Research. [Online]. Available: https://doi.org/10.1016/j.ejor.2021.03.006
10. [10]
    Performance of CatBoost and XGBoost in Medicare Fraud Detection

    IEEE ICMLA. [Online]. Available: https://doi.org/10.1109/ICMLA51294.2020.00095
11. [11]
    Why do tree-based models still outperform deep learning on tabular data?

    arXiv.org. [Online]. Available: https://arxiv.org/abs/2207.08815
12. [12]
    Tabular Data: Deep Learning is Not All You Need

    arXiv.org. [Online]. Available: https://arxiv.org/abs/2106.03253
13. [13]
    When Do Neural Nets Outperform Boosted Trees on Tabular Data?

    arXiv.org. [Online]. Available: https://arxiv.org/abs/2305.02997
14. [14]
    Accurate predictions on small data with a tabular foundation model | Nature

    nature.com. [Online]. Available: https://www.nature.com/articles/s41586-024-08328-6
15. [15]
    A Closer Look at TabPFN v2: Understanding Its Strengths and Extending Its Capabilities

    arXiv.org. [Online]. Available: https://arxiv.org/abs/2502.17361
16. [16]
    Classification and Regression Trees

    Taylor & Francis. [Online]. Available: https://doi.org/10.1201/9781315139470
17. [17]
    Elements of Statistical Learning: data mining, inference, and prediction. 2nd Edition.

    hastie.su.domains. [Online]. Available: https://hastie.su.domains/ElemStatLearn/
18. [18]
    Boosting: Foundations and Algorithms

    MIT Press. [Online]. Available: https://mitpress.mit.edu/9780262526036/boosting/
19. [19]
    Cryptographic Limitations on Learning Boolean Formulae and Finite Automata

    Journal of the ACM. [Online]. Available: https://doi.org/10.1145/174644.174647
20. [20]
    The Strength of Weak Learnability

    Machine Learning (Springer). [Online]. Available: https://doi.org/10.1007/BF00116037
21. [21]
    A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting

    Journal of Computer and System Sciences. [Online]. Available: https://doi.org/10.1006/jcss.1997.1504
22. [22]
    Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods

    The Annals of Statistics. [Online]. Available: https://doi.org/10.1214/aos/1024691352
23. [23]
    Greedy Function Approximation: A Gradient Boosting Machine

    The Annals of Statistics. [Online]. Available: https://doi.org/10.1214/aos/1013203451
24. [24]
    Additive Logistic Regression: A Statistical View of Boosting

    The Annals of Statistics. [Online]. Available: https://doi.org/10.1214/aos/1016218223
25. [25]
    Approximation by superpositions of a sigmoidal function

    Mathematics of Control, Signals, and Systems. [Online]. Available: https://doi.org/10.1007/BF02551274
26. [26]
    Benefits of Depth in Neural Networks

    PMLR. [Online]. Available: https://proceedings.mlr.press/v49/telgarsky16.html
27. [27]
    TabPFN: A Transformer That Solves Small Tabular Classification Problems in a Second

    arXiv.org. [Online]. Available: https://arxiv.org/abs/2207.01848
28. [28]
    TabLLM: Few-shot Classification of Tabular Data with Large Language Models

    arXiv.org. [Online]. Available: https://arxiv.org/abs/2210.10723
29. [29]
    Using XGBoost External Memory Version — xgboost 3.4.1 documentation

    xgboost.readthedocs.io. [Online]. Available: https://xgboost.readthedocs.io/en/stable/tutorials/external_memory.html
30. [30]
    Feature Selection, L1 vs. L2 Regularization, and Rotational Invariance

    ICML 2004. [Online]. Available: https://doi.org/10.1145/1015330.1015435
31. [31]
    Boosting as a Regularized Path to a Maximum Margin Classifier

    Journal of Machine Learning Research. [Online]. Available: https://jmlr.org/papers/v5/rosset04a.html
32. [32]
    On the Spectral Bias of Neural Networks

    PMLR. [Online]. Available: https://proceedings.mlr.press/v97/rahaman19a.html
33. [33]
    Revisiting Deep Learning Models for Tabular Data

    arXiv.org. [Online]. Available: https://arxiv.org/abs/2106.11959