= Solution
<Gradient> boosting initializes a constant score and iterates: compute logistic negative <gradients> $r_i^{(m)}=2y_i/[1+e^{2y_if_{m-1}(x_i)}]$ (for loss $\log(1+e^{-2yf})$), fit the base regressor $h_m$ to these pseudo-responses, choose a line-search step, and set $f_m=f_{m-1}+\nu\rho_mh_m$. For a stump $\beta\operatorname{sgn}(x_j-\alpha)$, sort each coordinate once. Sweeping the $n-1$ split positions while maintaining left and right sums gives the optimal $\beta$ and squared error in $O(n)$ per coordinate, hence $O(np)$ overall.
Back to article page
