Ayush Arora
Machine Learning Algorithms

Ch.61: Introduction to XGBoost, Why It Took Over

By Ayush Arora••14 min read

The previous posts worked through gradient boosting's actual mechanics, baseline, pseudo-residual, fit a tree, update, for both regression and classification. XGBoost is what happens when that same algorithm gets a decade of engineering thrown at it. This post is a tour of what XGBoost actually is, why gradient boosting specifically was the algorithm worth building it on top of, and the concrete flexibility/speed/performance decisions that turned "gradient boosting" into "the library every Kaggle winner reaches for."

1. XGBoost Is Not an Algorithm

A common misconception worth clearing up first: XGBoost is not a machine learning algorithm, it's a library, built on top of an already-existing algorithm, gradient boosting. The name itself spells this out: Extreme Gradient Boosting. Someone took gradient boosting, which already worked, and asked "what if we pushed every part of this as far as it would go, both mathematically and in terms of software engineering?"

That someone is Tianqi Chen, who released XGBoost in 2014 (at the time, 35 years old) and published the accompanying paper, XGBoost: A Scalable Tree Boosting System, in 2016. Chen himself entered and won the Higgs Boson Machine Learning Challenge, a Kaggle competition centered on particle physics, using the algorithm, and that win is what first put XGBoost on other competitors' radar. By 2016, 16 of the 29 winning solutions on Kaggle used XGBoost, at which point Chen open-sourced the project so the wider community could keep extending it, which is largely why it grew as fast as it did afterward.

In short: XGBoost is gradient boosting plus two categories of improvement, machine learning refinements to make the model itself better, and software engineering optimizations to make training dramatically faster. This post covers both, but starts with a question worth asking before either: out of every algorithm available in the 90s and 2000s, why extend gradient boosting?

2. Why Gradient Boosting, and Not AdaBoost or Something Else

By the time gradient boosting existed, machine learning already had a fairly mature toolbox. The 70s and 80s produced algorithms like linear regression and naive Bayes, genuinely useful, but narrow: linear regression only works well on linear data, naive Bayes is mainly good on textual/categorical data. Each algorithm was built for a specific kind of data, and none of them generalized well outside that lane.

The 90s produced a second generation, random forest, SVM, and gradient boosting, that were both more powerful and more general: they didn't assume a specific data shape the way the 70s/80s algorithms did. But this generation had its own weakness: as datasets grew through the 2000s and into the 2010s with the rise of the internet, these algorithms didn't scale. Training got slow, and in some cases performance (not just speed) degraded on very large data. That's the specific gap XGBoost was built to close, take an algorithm from the "powerful and general" generation and fix its scalability problem.

That still leaves the question of which algorithm from that generation to extend. AdaBoost, the boosting algorithm that predates gradient boosting, was already a well-known and battle-tested choice. Several concrete factors pointed at gradient boosting instead:

None of these individually rules out AdaBoost, but stacked together they explain why gradient boosting looked like the generation's strongest general-purpose candidate, with one specific, fixable weakness: performance and speed on large data. That fixable-weakness framing is exactly what XGBoost's two workstreams, described next, went after.

3. Three Design Goals

While building XGBoost, Chen worked toward three explicit goals: performance (better results, less overfitting), speed (usable on much larger datasets than vanilla gradient boosting could handle), and flexibility (usable by as many people, on as many platforms, for as many problem types, as possible). The rest of this post walks through each.

4. Flexibility

Flexibility here breaks into four concrete design choices, not a vague promise.

Cross-platform. An XGBoost model trained on Linux runs on Windows or Mac without modification. Not unique among ML libraries, but table stakes.

Multiple programming languages. This one is unusual. Most predictive modeling tooling is locked into Python, R, or occasionally MATLAB. XGBoost ships wrappers for Java, Scala, Ruby, Swift, Julia, C, and C++, in addition to Python and R. The practical payoff: you can train a model in Python, save it, and load that exact model into a Java application to serve predictions, no intermediate API service required. That matters because a lot of production systems, especially in enterprise settings, are built in Java, and without this, getting a Python-trained model into a Java service means standing up a whole API layer just to bridge the language gap.

Compatibility with the surrounding ecosystem. XGBoost integrates cleanly with the libraries a real ML workflow already uses: NumPy, Pandas, and scikit-learn for data prep and modeling; Spark, PySpark, and Dask for distributed computing; SHAP and LIME for model interpretability; Docker and Kubernetes for deployment; Airflow and MLflow for workflow/MLOps. None of these integrations are automatic, someone had to design XGBoost's interfaces to plug into all of them, and that's deliberate flexibility, not an accident of popularity.

Works across problem types. Linear regression only fits regression problems. Logistic regression only fits classification. XGBoost, because it's built on gradient boosted decision trees and gradient boosting accepts any differentiable loss function, handles regression, binary classification, multiclass classification, ranking problems (e.g. recommender systems), anomaly detection, and time series forecasting, all with the same underlying machinery, just a different loss function slotted in.

5. Speed

Before the six specific optimizations, here's the empirical gap they add up to. Training a GradientBoostingClassifier and an XGBClassifier on the same synthetic dataset (10,000 rows, 200 features):

import time
from sklearn.datasets import make_classification
from sklearn.ensemble import GradientBoostingClassifier
from xgboost import XGBClassifier
 
X, y = make_classification(n_samples=10000, n_features=200, n_informative=20, random_state=42)
 
start = time.time()
GradientBoostingClassifier(random_state=42).fit(X, y)
print(f"GradientBoostingClassifier: {time.time() - start:.2f}s")
 
start = time.time()
XGBClassifier(random_state=42, eval_metric="logloss").fit(X, y)
print(f"XGBClassifier: {time.time() - start:.2f}s")
GradientBoostingClassifier: 90.80s
XGBClassifier: 5.76s

Nearly a 16x speedup, on the same data, same default settings, same machine. That gap comes from six specific optimizations.

1. Parallel processing. This one has a genuinely confusing first impression: boosting is inherently sequential, each tree is trained on the previous tree's errors, so how can anything about it be parallel? The resolution is that the sequential part (stage mm depends on stage m−1m-1) stays sequential, parallelism happens inside the construction of a single tree. Building a tree means, at every node, testing every feature's every possible split threshold and picking the best one. With 200 features, that's 200 independent search problems, independent because feature F1F_1's best split doesn't depend on feature F2F_2's. XGBoost runs these searches across CPU cores simultaneously (controlled by the n_jobs hyperparameter) instead of one after another. This is only possible because of a second-order change: XGBoost stores data in column blocks rather than the row-wise storage most ML libraries use, so a whole feature's worth of values sits contiguously and can be handed to one core without touching the rest of the dataset.

2. Cache awareness. CPU cache memory is small (typically 4-8MB on a laptop) but far faster to read from than RAM, because it sits inside the CPU rather than across a system bus. XGBoost builds a histogram of each numerical feature's values (binning them, similar to how a histogram plot bins continuous data) and keeps those bin values in cache memory, since they get reused constantly while the tree is growing. It's the same idea as a cook keeping frequently-needed ingredients on the counter instead of walking back to the fridge every time.

3. Out-of-core computing. If a dataset is 10GB and available RAM is only 8GB, it simply won't load. XGBoost handles this by splitting the dataset into chunks (say, five 2GB chunks), loading and training on one chunk at a time, and resuming training state from where the previous chunk left off, rather than requiring the whole dataset in memory at once. This is controlled by setting tree_method='hist', and it works together with cache awareness, since whatever's reused across chunks still benefits from staying in cache.

4. Distributed computing. This solves a related but distinct problem: instead of one machine processing chunks sequentially, split the dataset across multiple machines (nodes) and train on all of them simultaneously. Each node searches for the best split on its own shard of the data, then a master node collects every node's candidate split, compares them, and picks the overall best one. The benefit over out-of-core computing alone is speed: five machines working in parallel finish faster than one machine working through five chunks in sequence. This requires an external library, Dask or Kubernetes, XGBoost doesn't implement distributed orchestration itself, it integrates with tools that do (a direct payoff of the ecosystem compatibility from Section 4).

5. GPU support. Histogram construction and split-finding are both highly parallelizable, exactly the kind of workload GPUs are built for (many simple cores rather than few powerful ones, the same reason GPUs dominate deep learning training). Setting tree_method='gpu_hist' routes tree construction through the GPU instead of the CPU.

6. Why "extreme." After all six of the above, the name makes sense: this isn't gradient boosting with one clever trick added, it's gradient boosting with essentially every available systems-engineering technique applied to it, parallelism, caching, out-of-core handling, distribution, GPU offload. Hence Extreme Gradient Boosting.

6. Performance

Speed optimizations make training faster; this section covers changes aimed at making the trained model better, four machine-learning-level refinements XGBoost adds on top of plain gradient boosting.

6.1 A Regularization Term Baked Into the Loss

Plain gradient boosting fights overfitting indirectly, through a learning rate that shrinks each tree's contribution, and through pruning each tree during construction. Neither is part of the loss function being minimized, they're external controls layered on top. XGBoost's objective function has a regularization term built directly into it, a penalty on leaf weights, controlled by a hyperparameter usually written λ\lambda. Because it's inside the function being minimized, regularization isn't something to remember to apply, minimizing the objective automatically pulls the model toward simpler, more generalizable trees as a side effect of the optimization itself, rather than as a separate post-hoc constraint.

6.2 Handling Missing Values Without Imputation

Most machine learning algorithms simply refuse to train on data containing missing values:

import numpy as np
import pandas as pd
from sklearn.ensemble import GradientBoostingClassifier
 
X = pd.DataFrame({
    "f1": [1.0, 2.0, 3.0, 4.0, 5.0, 6.0],
    "f2": [10.0, 20.0, np.nan, 40.0, 50.0, 60.0],
})
y = [0, 0, 1, 1, 0, 1]
 
GradientBoostingClassifier(n_estimators=10, random_state=42).fit(X, y)
ValueError: Input X contains NaN.
GradientBoostingClassifier does not accept missing values encoded as NaN natively.

The same data trains without complaint in XGBoost, no imputation step required:

from xgboost import XGBClassifier
 
XGBClassifier(n_estimators=10, random_state=42).fit(X, y)
# trains successfully, no ValueError, no imputation

The mechanism behind this: at every split, XGBoost tests sending all missing-value rows to the left child and tests sending them all to the right child, computes the resulting gain both ways, and keeps whichever direction gives the better split. That per-split "default direction" is learned from the data itself, not assumed, which is why XGBoost can be handed genuinely messy, real-world data and still produce a usable model.

6.3 Efficient Split Finding

Finding the best split at a node means checking, for every feature, every possible threshold, typically the midpoint between each pair of consecutive sorted values, and picking whichever gives the best gini/entropy improvement. This approach, called exact greedy search, is accurate but slow: with a feature that has a million distinct values, that's a million thresholds to test, for every node, of every tree.

XGBoost's alternative is approximate tree learning: instead of testing every possible threshold, bin the continuous feature into a smaller number of candidate split points. Fewer candidates means less computation, at the cost of slightly coarser splits. The bins themselves aren't evenly spaced, they're chosen using a technique called weighted quantile sketch, which places bin boundaries based on the feature's actual quantiles. The practical effect: dense regions of the data (where lots of points cluster) get many small bins, so splits there stay precise, while sparse regions get fewer, wider bins, since there's little to distinguish there anyway. This quantile-aware binning is what lets XGBoost trade a small amount of split precision for a large amount of speed without the model's quality falling off a cliff. Internally, this is also called histogram-based training, since it's the same binning idea a histogram plot uses.

6.4 Tree Pruning

Both pre-pruning (capping tree size during construction, e.g. max_depth, max_leaf_nodes) and post-pruning (growing a tree fully, then trimming it back) reduce overfitting by keeping trees from growing arbitrarily complex. XGBoost exposes both, but adds one more lever plain gradient boosting doesn't have: a gamma hyperparameter that sets a minimum required loss reduction before a new branch is allowed to form at all. A candidate split that improves the loss only marginally simply doesn't get added, regardless of what the pre/post-pruning depth limits would otherwise allow. This is finer-grained control over tree complexity than vanilla gradient boosting offers, and it's part of why XGBoost trees tend to generalize better on the same data.

7. Not the Only "Extreme" Implementation

XGBoost popularized the "gradient boosting plus heavy engineering" approach, but it isn't the only library that took it. LightGBM (Microsoft Research) targets faster training and lower memory usage, with comparable or better accuracy on large-scale data, and supports the same parallel/distributed/GPU training XGBoost does. CatBoost is built around strong native support for categorical features, handling them without the manual encoding most other libraries require. Both are worth knowing exist; which one wins on a given dataset varies, and there's no universal answer.

8. What to Take Away

View all chapters in Machine Learning Algorithms →