# XGBoost: Why is the "approximate algorithm" faster?

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:
$$\quadG_L \leftarrow 0,\quad H_L \leftarrow 0$$
$$\quad$$for $$j$$ in sorted($$I$$, by $$x_{jk}$$) do:
$$\qquadG_L \leftarrow G_L + g_j,\quad H_L \leftarrow H_L + h_j$$
$$\qquadG_R \leftarrow G − G_L, \quad H_R \leftarrow H − H_L$$
$$\qquadscore \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:
$$\quadG_{kv} \leftarrow \sum_{j\in\{j|s_{k,v} \geq x_{jk}>s_{k,v−1}\}} g_j$$
$$\quadH_{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.

• Arxiv are preprints, so commenting on typos there is rather pointless as the versions of papers there are not final.
– Tim
Apr 2 at 14:10
• From the description alone algorithm 1 has nested for loops vs non-nested in the second case which is an obvious speedup.
– Tim
Apr 2 at 14:13
• @Tim Do you have a link to a version that is final? Apr 2 at 14:40
• @Tim I wish things were that easy. (1) The "Follow same step as in ..." in Algorithm 2 is supposed to be analogous to "for j=..." loop nested inside "for k=..." loop in Algorithm 1. (2) The second for-loop of Algorithm 2 has an implicit iteration over $v$ (also over $j$ and $j$ inside $\{\dots\}$). Apr 2 at 14:44