Why is a gradient boosting leaf's value found by line search rather than averaging?

## Two optimisations per stage, not one A single stage of gradient boosting does two separate pieces of optimisation, and candidates who have only implemented the squared-error case usually notice only one of them. 1. **Find the partition.** A shallow tree is grown on the pseudo-residuals -- the negative gradients of the loss at the current predictions. This step decides *which rows get grouped together*. 2. **Choose the value for each region.** For each terminal leaf `j`, pick the single constant `gamma_j` that minimises the **actual loss** for the rows in that leaf, given everything the model already predicts for them: ``` gamma_j = argmin over c of sum over rows i in leaf j of L(y_i, F_{m-1}(x_i) + c) ``` That second step is the *line search*: a one-dimensional minimisation along the direction the tree just chose. The tree says -these rows should move together-; the line search says -and here is how far they should actually move.- ### Why averaging the gradients is not enough The tree in step 1 is normally grown by least-squares fitting on the pseudo-residuals, whatever the real loss is. That is a deliberate approximation: the gradient field is a linear approximation of the loss surface, and squared-error splitting on it is fast and well understood. But a linear approximation is only trustworthy for a small step, and the leaf value *is* the step. If you simply averaged the gradients inside the leaf and used that as the output, you would be trusting the linear approximation to tell you a magnitude, which it cannot do for a non-quadratic loss. For squared error the two steps agree exactly: the pseudo-residuals *are* the errors, and the constant minimising the sum of squared errors in a leaf is their mean. This coincidence is why the line search is invisible in the simplest presentation of the algorithm -- and why so many people believe -leaf value = mean of the residuals- is a law rather than a special case. ### The absolute-error case, where it becomes visible Take `L = |y - F|`. The pseudo-residuals are `+1` and `-1`, so their mean inside a leaf is a number between minus one and plus one that carries no information about how far off the predictions are. Averaging that would be nonsense as an update. Solve the line search instead: ``` gamma_j = argmin over c of sum over i in leaf j of |(y_i - F_{m-1}(x_i)) - c| ``` The constant minimising a sum of absolute deviations is the **median**, so the leaf value is the median of the leaf's current errors. Notice what has happened: the *direction* came from the signs, but the *magnitude* came from a robust order statistic of the real errors. That is why absolute-error boosting shrugs off an extreme target -- an outlier contributes one sign to the split search and one element to a median, never a magnitude that drags the update. Other losses give other closed forms or none at all. Log loss has no closed-form minimiser for the leaf constant, so implementations solve it approximately -- one cheap step of a numeric minimisation per leaf, computed from quantities the stage already has. ### The consequences worth stating in an interview - **The split search and the leaf values optimise different objectives.** Splits use a squared-error proxy on gradients; leaves use the true loss. Saying -the tree minimises the loss- is imprecise, and a good interviewer will probe it. - **Robustness lives in the leaf value as much as in the loss.** Choosing absolute error but then averaging the leaf's errors would discard most of the robustness you asked for. - **Leaf values depend on the current model, not just on the leaf's rows.** `F_{m-1}(x_i)` appears inside the minimisation, so the same partition would get different values at stage 3 and stage 300. - **The step is bounded by the loss, not by the tree.** For losses whose gradient saturates -- log loss, absolute error -- a leaf full of badly-missed rows cannot demand an unbounded jump, because the line search is solving the real loss, which stops rewarding movement past a point. ### How to say it in one breath The tree picks a direction in function space by fitting the negative gradient; the line search picks the step length inside each region by minimising the genuine loss. Mean under squared error, median under absolute error, an approximate solve under log loss -- one algorithm, three different leaf values, because the leaf value is defined by the objective and not by the tree.