Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 30K / Solution

Gradient boosting initializes a constant score and iterates: compute logistic negative gradients $r_i^{(m)}=2y_i/[1+e^{2y_i{f}_{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 }_m{h}_m$. For a stump $\beta \mathrm{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.