5
$\begingroup$

Original Question

Having used XGBoost a fair bit, clearly changing the learning rate dramatically affects the algorithm's performance. That said, I really can't understand the theoretical justification for it. It makes sense in "vanilla" gradient boosting, when you don't make use of second derivatives. Analogously, one does not need a learning rate if using Newton-Raphson to perform optimisation by finding the zeros of the derivative of the cost function.

I thought it might have to do with ensuring that the updates one makes at every step are small, and thus the gradient expansion to second order is valid, but it seems to me like one could achieve the same thing more effectively by regularising?

Also, the XGBoost docs have a theoretical introduction to XGBoost and don't mention a learning rate anywhere (https://xgboost.readthedocs.io/en/latest/tutorials/model.html)

Is it as simple as "it is experimentally observed to improve performance" and if so, is it possible to rationalise post-fact ?

Update: Almost a year on, I thought I'd update my thinking on this and somewhat refine my question

While it might be the case that the need for a learning rate was ascertained experimentally, it seems likely to me that the reason it is necessary, is to do with the fact that XGBOOST assumes the that the total loss $L$ of a classifier consisting of an existing classifier $F_{t}(x)$ plus a new classifier $f_{t+1}(x)$, can be written as a Taylor Expansion of $L$ about $F_{t}(x)$, which requires $f_{t+1}(x)$ to represent a "small enough" correction to $F_{t}(x)$, that we don't need to expand to too high an order.

My suspicion for a while has been that using lots of regularisation should take care of this, hence why use a learning rate at all? Another approach, could be to say that the tree $f_{t+1}(x)$, which splits the space into a number of distinct regions (terminal nodes) $\{R_{j}\}$, outputs a constant $\epsilon \cdot w_{j}$ in the $j^{th}$ region. By choosing a sufficiently small $\epsilon$, we can ensure that $\epsilon \cdot w_{j}$ will be sufficiently small for any partitioning and any j.

It turns out however, that if you follow the derivation in the XGBOOST docs but take this approach, and use no regularisation, the weight $w_{j}^{*}$ you should assign to the region $R_{j}$ is given by

$w_{j}^{*} = - \frac{\sum_{i \in R_{j}}\frac{\partial \ell}{\partial \hat{y}_{i}}\bigg|_{F_{t}(x_{i})}}{\epsilon \sum_{i \in R_{j}}\frac{\partial ^{2}\ell}{\partial \hat{y}_{i}^{2}}}$

in which $L[F_{t}(x)+f_{t+1}(x)] = \sum_{i=1}^{N}\ell (y_{i}, \hat{y}_{i})=\sum_{i=1}^{N}\ell (y_{i}, F_{t}(x_{i}) + f_{t+1}(x_{i}))$

In other words, if you state that the output of each tree at each leaf will be a constant $w_{j}$ multiplied by a very small number $\epsilon$, small enough to ensure that the product is always small, $w_{j}^{*}$ will simply compensate, so the smaller you make $\epsilon$, the larger you make $w_{j}^{*}$, and the product remains unchanged. Crucially, the product will not necessarily be "small enough" for the Taylor series to quickly converge and justify the second order expansion. However, if a little bit of regularisation is used, enough to stop $w_{j}$ becoming infinite and thus ensure the product is always small, then you're good.

In essence, you have two approaches:

  1. Set $\lambda$ to be "very large", this will ensure that $w_{j}^{*}$ is small, and thus the expansion is valid
  2. Use a learning rate parameter $\epsilon$, and have some small amount of regularisation, to ensure that $w_{j}^{*}$ cannot be arbitrarily large

They sound the same, at a phenomenological level, but let's investigate the $w_{j}^{*}$ they imply. Using approach 1, not having a learning rate, we obtain (as in the xgboost docs, linked above)

$w_{j}^{*}= - \frac{\sum_{i \in R_{j}}\frac{\partial \ell}{\partial \hat{y}_{i}}\bigg|_{F_{t}(x_{i})}}{\lambda + \sum_{i \in R_{j}}\frac{\partial^{2} \ell}{\partial \hat{y}_{i}^{2}}\bigg|_{F_{t}(x_{i})}}$

whereas if we use a learning rate as well, we obtain

$w_{j}^{*}= - \frac{\sum_{i \in R_{j}}\frac{\partial \ell}{\partial \hat{y}_{i}}\bigg|_{F_{t}(x_{i})}}{\frac{\lambda}{\epsilon} + \epsilon \cdot \sum_{i \in R_{j}}\frac{\partial^{2} \ell}{\partial \hat{y}_{i}^{2}}\bigg|_{F_{t}(x_{i})}}$

They look very similar, and in both cases, as you up the amount of regularisation by increasing $\lambda$, the curvature term becomes less relevant. In the case when you have a learning rate, you can get this effect either by increasing $\lambda$ or decreasing $\epsilon$.

No matter which way I think about the problem, either approach seems conceptually the same, but they do give slightly different solutions. Furthermore, in practice, the learning rate is perhaps the most important hyperparamter to tune in XGBOOST, although I haven't seen anybody explore whether similarly good results could be obtained by tuning the regularisation parameter more. In particular, am I missing something jumping out at me from these two equations?

$\endgroup$
  • $\begingroup$ I guess that the answer still goes alonog these lines: stats.stackexchange.com/questions/282544/… (even though you are bringin up the second derivative): setting a LR to a value < 1 helps the algorithm evite spiraling around the minimum. You are right: If we use the second derivative we should get a better feeling of how much we should go into the direction given by the gradient, so yes, for the regression case, the second derivative vanishes, so I am puzzled by your argument as well, however... $\endgroup$ – Fabian Werner Jul 5 '18 at 9:52
  • $\begingroup$ in the classification case, I think that there are more than 2 derivatives and xgboost only uses the first two out of an infinite selection (third derivative helps not to overinterpret the results from the second and so forth) $\endgroup$ – Fabian Werner Jul 5 '18 at 9:54
  • $\begingroup$ My interpretation of using only two derivatives, is that one can use regularisation to ensure that the correction will always be "relatively small", and it is then justified to assume that the second order expansion is a good approximation to how the loss will change when this correction is added. By the way, I don't think the second derivative disappears in "the regression case" (specifically, I think you mean least squares loss), it's a constant, is it not? $\endgroup$ – gazza89 Jul 5 '18 at 14:23
  • $\begingroup$ 1) Yes, I meant that it does not give you any insightful information that you could possibly use in order to get a feeling of how long you should follow the gradient. 2) Thought about it a little longer. Say you want to minimize the function $f(x) = |x|$. You start at $x=0.5$ and you always follow the gradient, i.e. you "spiral" between $x=+0.5$ and $x=-0.5$. How exactly does the second derivative help you in that case to judge how much weight you should put on the gradient? I think this is where you are ... '''wrong''': the second derivative also only describes the change in $\endgroup$ – Fabian Werner Jul 5 '18 at 14:26
  • $\begingroup$ the derivative in a region that might be reeeeeally small (around the point you are right now). So in principle, it does not help you to know how reliable the gradient is... In terms of Taylor series, it helps you to 'know' the function a bit better than with only one derivative but in these simple cases like $x^2$ or $|x|$ you know the function already somehow... $\endgroup$ – Fabian Werner Jul 5 '18 at 14:27
3
$\begingroup$

Further explanation can be found in "XGBoost: A Scalable Tree Boosting System" by Tianqi Chen, Carlos Guestrin.

Besides the regularized objective mentioned in Sec. 2.1, two additional techniques are used to further prevent overfitting. The first technique is shrinkage introduced by Friedman [11]. Shrinkage scales newly added weights by a factor $\eta$ after each step of tree boosting. Similar to a learning rate in tochastic [sic] optimization, shrinkage reduces the influence of each individual tree and leaves space for future trees to improve the model.

We can consult the citation for further information. In "Stochastic Gradient Boosting," Friedman writes

that the "shrinkage" parameter $0 < \eta \le 1$ controls the learning rate of the procedure. Empirically (Friedman 1999), it was found that small values ($\eta \le 0.1$) lead to much better generalization error.

(Except that I've edited the quote to use a different symbol for clarity and consistency with the rest of this thread.)

As with any regularization technique, people use it because it improves generalization error on their modeling tasks. I'm not aware of a study which examines whether the learning rate parameter is strictly necessary in the context of XGBoost (but I would be interested to read one!). Based on the way the "XGBoost: A Scalable Tree Boosting System" paper is written, it seems that the authors did not conduct such an analysis themselves, instead relying on previous results for other boosting algorithms.

Since the Friedman paper is also discussing the effects of adding additional randomization to boosted trees (e.g. bootstrapping), it seems reasonable to surmise that in the context of random subsamples, you would not want early trees to dominate the classification decision, since those early trees are just specific random samples of the entire training data. Instead of having all subsequent trees be strongly influenced by the peculiarities of the first few random samples, introducing the "learning rate" seems like a clever way to down-weight the trees.

Speaking from personal experience, the difference between using a learning rate of 1.0 and a smaller learning rate like 0.1 is that models with the larger learning rate rapidly reduce the loss, but also rapidly reach a plateau. Here's an example comparing the same models on the same data with different learning rates. The smaller learning rate more slowly declines, and it attains a lower loss.

$$ \begin{array}{r|r|r|} \text{Iteration number} & \eta = 1 & \eta = 0.1 \\ \hline 1 & 0.216 & 0.373 \\ 2 & 0.138 & 0.245 \\ 3 & 0.109 & 0.176 \\ 4 & 0.100 & 0.136 \\ 5 & 0.103 & 0.110 \\ 6 & 0.111 & 0.0952 \\ 7 & 0.110 & 0.0845 \\ 8 & \text{terminated} & 0.0783 \\ 9 & - & 0.0758 \\ 10 & - & 0.0739 \\ 11 & - & 0.0716 \\ 12 & - & 0.0700 \\ 13 & - & 0.0702 \\ 14 & - & 0.0697 \\ 15 & - & 0.0703 \\ 16 & - & 0.0705 \end{array} $$

This remark

Having used XGBoost a fair bit, clearly changing the learning rate dramatically affects the algorithm's performance. That said, I really can't understand the theoretical justification for it. It makes sense in "vanilla" gradient boosting, when you don't make use of second derivatives. Analogously, one does not need a learning rate if using Newton-Raphson to perform optimisation by finding the zeros of the derivative of the cost function.

suggests that perhaps you've conflated gradient boosting with gradient descent. It's very common in the neural network community to call the "step size" of a gradient descent algorithm the "learning rate". But this is not the same as the "learning rate" in gradient boosting. In gradient boosting, the "learning rate" is used to "dampen" the effect of each additional tree to the model. In the Friedman paper, the model has this form:

$$ F_m(x) = F_{m-1}(x) + \eta \cdot \gamma_{lm} \mathbf{1}(x \in R_{lm}) $$

which is a math-y way of saying that at round $m$, the prediction function is the previous round's prediction $F_{m-1}$ plus a scalar multiple $\eta$ of the new prediction. The expression $\gamma_{lm} \mathbf{1}(x \in R_{lm})$ represents the solution to an optimization and an indicator function for whether $x$ is a member of that region.

$\endgroup$
  • 1
    $\begingroup$ Yes, I am aware of that, it just seems very peculiar to me to go through a rigorous derivation to find the optimal values to assign to each terminal node in a tree, and after all that, say "but we're going to multiply them all by a small number because this will help us learn more slowly and improve generalisability" . To be clear, I've used XGBoost enough to know that it clearly works, but I don't understand mathematically why it should improve generalisability. $\endgroup$ – gazza89 Jul 6 '18 at 16:35
  • $\begingroup$ @gazza89 If it's any comfort, I'm not sure that Tianqi Chen knows why it's the case, either. Or, if he does, he's kept it to himself since it is not further justified anywhere in his paper. $\endgroup$ – Reinstate Monica Jul 6 '18 at 17:25
0
$\begingroup$

Parameters for Tree Booster eta [default=0.3, alias: learning_rate] step size shrinkage used in update to prevents overfitting. After each boosting step, we can directly get the weights of new features. and eta actually shrinks the feature weights to make the boosting process more conservative. range: [0,1]

From: manual

According to this source: math, learning_rate affects the value of the function of gradient calculation that incorporates both first and second order derivatives. I just looked into code, but I am not good at Py, so my answer is really a guide for you to explore more.

$\endgroup$
  • 1
    $\begingroup$ thanks for the link. My c++ isn't great, but it looks to me like it's doing exactly what I thought, it's finding the best solution as shown in the XGBoost docs, and then multiplying by a learning rate. Unfortunately, justification is pretty thin on the ground, just that it "helps combat overfitting", but I'm still struggling to understand why, other than "it has been experimentally observed". I'm still curious as to whether the same effect could be achieved by regularising more heavily. $\endgroup$ – gazza89 Jul 5 '18 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.