XGBoost: Why is the "approximate algorithm" faster?

Question

I am reading T. Chen, C. Guestrin, "XGBoost: A Scalable Tree Boosting System", 2016 (arXiv), which is seemingly full of typos. They propose the so-called "approximate algorithm" (Algorithm 2 below) and justify it as follows (section 3.2):

However, it is impossible to efficiently do so [Algorithm 1] when the data does not fit entirely into memory. Same problem also arises in the distributed setting. To support effective gradient tree boosting in these two settings, an approximate algorithm is needed.

I understand that in order to calculate the gain for every possible split for each feature, one needs to access all datapoints assigned to the current node ("instance set" $I$). Because this assignment is different for every node for every tree, one has to read the entire dataset from the disk, which is slow. What I don't understand is

Why don't we have to do the same when considering a subset of candidate split points?

We still have to calculate the statistics $G_{kv}, H_{kv}, \forall k,v$. These depend on the set of points assigned to the current node. In order to determine which $\mathbf{x}_j$ belong to the node, we need to examine each of them. Therefore, we need to read the entire dataset from disk, which is slow. So where is the speed-up?

---

From the XGBoost paper [with my comments]:

Algorithm 1: Exact Greedy Algorithm for Split Finding
Input: $I$, instance set of current node
Input: $d$, feature dimension [Probably a typo: must be $m$, not $d$]
$gain \leftarrow 0$
$G \leftarrow \sum_{i\in I} g_i, \quad H \leftarrow \sum_{i\in I} h_i$
for $k = 1$ to $m$ do:
$\quad$$G_L \leftarrow 0,\quad H_L \leftarrow 0$
$\quad$for $j$ in sorted($I$, by $x_{jk}$) do:
$\qquad$$G_L \leftarrow G_L + g_j,\quad H_L \leftarrow H_L + h_j$
$\qquad$$G_R \leftarrow G − G_L, \quad H_R \leftarrow H − H_L$
$\qquad$$score \leftarrow \max(score, \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G^2}{H + \lambda})$ [Obviously a typo: must be $gain$ instead of $score$]
$\quad$end
end
Output: Split with max score

Algorithm 2: Approximate Algorithm for Split Finding
for k = 1 to m do:
$\quad$Propose $S_k = \{s_{k1}, s_{k2}, \dots, s_{kl}\}$ by percentiles on feature $k$.
$\quad$Proposal can be done per tree (global), or per split(local).
end
for $k = 1$ to $m$ do:
$\quad$$G_{kv} \leftarrow \sum_{j\in\{j|s_{k,v} \geq x_{jk}>s_{k,v−1}\}} g_j$
$\quad$$H_{kv} \leftarrow \sum_{j\in\{j|s_{k,v} \geq x_{jk}>s_{k,v−1}\}} h_j$
end
Follow same step as in previous section to find max score only among proposed splits.

Answer 1

I suspect that reading the full dataset from disk at each node is inevitable. The purpose of storing a histogram-like data structure in RAM is to avoid repeated passes.

• In order to select the best split point (whether arbitrary or constrained to a fixed set of proposed values) for a given feature, we need to process the points in the order determined by values of the feature. Unfortunately, the training dataset is not stored on disk in any particular order.
• Even if the data were sorted by some feature's values, the order would be different for other features.
• Even if we could access the data in the required order for each feature, and even if such random access reads from disk were efficient, we would still do multiple traversals of the disk-stored training set, because the maximisation of the gain requires a separate traversal for each feature.

The "approximate algorithm" separates reading from disk and traversing the in-memory histogram-like structure. The speed-up would be roughly proportional to the number of features (if disk operations are slow).