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.