Question about step size in gradient boosting

Question

Above is the pseudocode for gradient boosting. In Step 2.3, we're computing a multiplier (or step length) $\gamma_m$. Suppose the loss function $L(y_i, \hat{y}_i) = \frac{1}{2}(y_i - \hat{y}_i)^2$. Then to find $\gamma_m$, we would have

$\begin{align*} \gamma_m &= \text{arg min}_\gamma \frac{1}{2}\sum_{i = 1}^n (y_i - F_{m-1}(x_i) - \gamma h_m(x_i))^2 \end{align*}$

Taking the derivative wrt $\gamma$, we have

\begin{align*} \frac{\partial}{\partial \gamma} \frac{1}{2}\sum_{i = 1}^n (y_i - F_{m-1}(x_i) - \gamma h_m(x_i))^2 &= -\sum_{i=1}^n h_m(x_i)(y_i - F_{m-1}(x_i) - \gamma h_m(x_i))\\ &= -\sum_{i=1}^n h_m(x_i)(y_i - F_{m-1}(x_i) + \gamma \sum_{i=1}^n h_m^2(x_i)\\ & \overset{set}{=}0\\ \Rightarrow \gamma_m &= \frac{\sum_{i=1}^n h_m(x_i)(y_i - F_{m-1}(x_i))}{\sum_{i=1}^n h_m(x_i)^2} \end{align*}

Is this correct? If so, what's the intuition behind this step length $\gamma$? In my own implementation of this algorithm, I've been computing $\gamma_m = \frac{\sum_{i=1}^n h_m(x_i)(y_i - F_{m-1}(x_i))}{\sum_{i=1}^n h_m(x_i)^2}$ and the values of $\gamma_m$ are all very close to 1. What does that suggest about my algorithm?

Answer 1

Boosting can be seen as gradient descent performed in function space $\mathcal{H}$ of weak learners (see e.g. [1, 2]). From the point of view of empirical risk minimization, at time step $m$ we would like to take a step in the negative gradient direction $-\nabla_{F_{m-1}} L(y, F_{m-1})$, whose coordinate projection on the observed dataset equals to the vector of pseudo residuals $(r_{1m}, \dots, r_{nm})^{\mathsf{T}}$ defined in the question. Since the set of weak learners $\mathcal{H}$ does not necessarily contain a function $h$ such that $h(x_{i}) = r_{im}$, it is a job of the weak learning algorithm to select a function $h_{m} \in \mathcal{H}$ which best correlates (in some way) with the negative gradient direction given by the vector of pseudo residuals. For more details on the specific case of quadratic loss see [3].

Once we think of $h_{m}$ as an approximation to the negative gradient direction, choosing the step size $\gamma_{m}$, as defined in the question, is known as line-search in optimization literature. In words, it simply selects a step-size that yields a maximum decrease of the empirical (i.e., training) loss function. Hence, in your case, $\gamma \approx 1$ suggests that a model can fit the data further (that is, taking a gradient descent step is able to further minimize the training loss). Once $\gamma$ reaches $0$, a local minimum or a saddle point has been reached and the optimization procedure (i.e., empirical risk minimization) stops.

Note that other step size schemes are also possible (e.g., a constant step size $\gamma_{m} = \gamma_{0}$, a decreasing step sizes scheme $\gamma_{m} = \gamma_{0}/\sqrt{m}$, etc.). Different step size schemes can provide the same guarantees on the training loss (e.g., ensure convergence to a local minimum of the training loss) that hold under different assumptions of the empirical training loss and/or the weak learning algorithm. However, modifying the step size scheme can affect the generalization properties of the algorithm in ways that to the best of my knowledge are not yet fully understood.

[1] Mason et. al. Boosting Algorithms as Gradient Descent. NIPS 1999.

[2] Friedman. Greedy Function Approximation: a Graident Boosting Machine. Ann. Statist. 2001.

[3] Buhlmann and Yu. Boosting with the $L_{2}$-Loss: Regression and Classification.