Exact-line-search gradient tree boosting on a finite sample

Fix a finite regression sample $(x_i,y_i{)}_{i=1}^N$ with $N\ge 1$, $x_i\in {\mathbb{R}}^p$ for a finite $p\ge 1$, and $y_i\in \mathcal{Y}$. Let $\mathrm{\ell }:\mathcal{Y}\times \mathbb{R}\to \mathbb{R}$ be a finite-valued per-observation loss, differentiable in its second argument at every score used. Choose a finite round count $M\ge 0$ and finite integer tree-depth cap $d_{\max }\ge 0$. The algorithm is admissible only when the following required minima are attained: an initial constant minimizer and, at every round, a line minimizer in each terminal leaf. For any admitted run, choose any one such minimizer at each finite stage.

Initialize $f_0(x)=c_0$ with $c_0\in \arg {\min }_{c\in \mathbb{R}}{\sum }_{i=1}^N\mathrm{\ell }(y_i,c)\mathrm{.}$ For each round $m=1,\dots ,M$, perform the following steps.

1. For each observation compute the negative score derivative $r_{im}=-{\mathrm{\partial }}_2\mathrm{\ell }(y_i,f_{m-1}(x_i))\mathrm{.}$

2. Run finite-depth CART regression-tree growth, using squared error and depth cap $d_{\max }$, on the responses $r_{im}$ at features $x_i$. Let its nonempty terminal feature regions be $R_{1m},\dots ,R_{J_{m}m}$; their training-index sets partition $\{1,\dots ,N\}$. This tree fit approximates the unrestricted negative score gradient. Its fitted leaf means are used to determine the regression-tree fit and regions, but are not the boosting update offsets.

3. For each leaf region choose an attained exact line minimizer ${\gamma }_{jm}\in \arg {\min }_{\gamma \in \mathbb{R}}{\sum }_{i:x_i\in R_{jm}}\mathrm{\ell }(y_i,f_{m-1}(x_i)+\gamma )\mathrm{.}$ In particular, zero is an admissible comparison offset.

4. Update $f_m(x)=f_{m-1}(x)+{\sum }_{j=1}^{J_m}{\gamma }_{jm}\mathbf{1}\{x\in R_{jm}\}\mathrm{.}$

The output is $f_M$. Because the run has finitely many rounds and finitely many leaves, choosing one attained minimizer at each stage requires no axiom of choice. The defined variant uses the full training sample and exact leafwise line minimization; shrinkage and subsampling are separate variants. This definition asserts no convergence or generalization result.

Finite-sample pseudo-residual and score-loss conventions

The pseudo-residual vector is the negative score-space gradient

Finite regression-tree regions and nonempty leaf sample sets

The finite-depth CART regression-tree fit

Finite output and nonempty leaves

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §§10.9–10.10.3, printed pp. 353–361

Alexey Natekin and Alois Knoll, “Gradient boosting machines, a tutorial,” §§2.3–2.4