19
$\begingroup$

The learning rate parameter ($\nu \in [0,1]$) in Gradient Boosting shrinks the contribution of each new base model -typically a shallow tree- that is added in the series. It was shown to dramatically increase test set accuracy, which is understandable as with smaller steps, the minimum of the loss function can be attained more precisely.

I don't get why the learning rate is considered a regularization parameter? Citing the Elements of Statistical Learning, section 10.12.1, p.364:

Controlling the number of trees is not the only possible regularization strategy. As with ridge regression and neural networks, shrinkage techniques can be employed as well. Smaller values of $\nu$ (more shrinkage) result in larger training risk for the same number of iterations $M$. Thus, both $\nu$ and $M$ control prediction risk on the training data.

Regularization means "way to avoid overfitting", so it is clear that the number of iterations $M$ is crucial in that respect (a $M$ that is too high leads to overfitting). But:

Smaller values of $\nu$ (more shrinkage) result in larger training risk for the same number of iterations $M$.

just means that with low learning rates, more iterations are needed to achieve the same accuracy on the training set. So how does that relate to overfitting?

$\endgroup$
23
+50
$\begingroup$

Suppose you are trying to minimize the objective function via number of iterations. And current value is $100.0$. In given data set, there are no "irreducible errors" and you can minimize the loss to $0.0$ for your training data. Now you have two ways to do it.

  • The first way is "large learning rate" and few iterations. Suppose you can reduce loss by $10.0$ in each iteration, then, in $10$ iterations, you can reduce the loss to $0.0$.

  • The second way would be "slow learning rate" but more iterations. Suppose you can reduce loss by $1.0$ in each iteration and you need $100$ iteration to have 0.0 loss on your training data.

Now think about this: are the two approaches equal? and if not which is better in optimization context and machine learning context?

In optimization literature, the two approaches are the same. As they both converge to optimal solution. On the other hand, in machine learning, they are not equal. Because in most cases we do not make the loss in training set to $0$ which will cause over-fitting.

We can think about the first approach as a "coarse level grid search", and second approach as a "fine level grid search". Second approach usually works better, but needs more computational power for more iterations.

To prevent over-fitting, we can do different things, the first way would be restrict number of iterations, suppose we are using the first approach, we limit number of iterations to be 5. At the end, the loss for training data is $50$. (BTW, this would be very strange from the optimization point of view, which means we can future improve our solution / it is not converged, but we chose not to. In optimization, usually we explicitly add constraints or penalization terms to objective function, but usually not limit number of iterations.)

On the other hand, we can also use second approach: if we set learning rate to be small say reduce $0.1$ loss for each iteration, although we have large number of iterations say $500$ iterations, we still have not minimized the loss to $0.0$.

This is why small learning rate is sort of equal to "more regularizations".

Here is an example of using different learning rate on an experimental data using xgboost. Please check follwoing two links to see what does eta or n_iterations mean.

Parameters for Tree Booster

XGBoost Control overfitting

For the same number of iterations, say $50$. A small learning rate is "under-fitting" (or the model has "high bias"), and a large learning rate is "over-fitting" (or the model has "high variance").

Example of changing learning rate ETA in XGBoost model

PS. the evidence of under-fitting is both training and testing set have large error, and the error curve for training and testing are close to each other. The sign of over-fitting is training set's error is very low and testing set is very high, two curves are far away from each other.

$\endgroup$
  • $\begingroup$ Do you mean that with a low learning rate, you are allowed to iterate more (refine your search more) than with a high learning rate, for the same loss? I think I get the intuition you're trying to pass on but more rigorous explanations and/or an illustrative example wouldn't hurt. $\endgroup$ – Antoine May 11 '16 at 8:29
  • $\begingroup$ thank you. Could you update your links? They do not work for me $\endgroup$ – Antoine May 14 '16 at 10:21
  • $\begingroup$ Using a larger learning rate is always better as long as you don't increase the training error in subsequent iterations. The regularisation you are referring to (bias vs variance) is related to the training/validation error and not the learning rate. Whether you are using large or small learning rate, if you reach 0.0 training error then you are overfitting just as much. If you are using larger learning rate, then you need to stop your optimisation earlier to prevent overfitting. You can use a validation set to see whether your validation error increases at which point you stop the training. $\endgroup$ – Curious Sep 4 '16 at 16:07
  • $\begingroup$ or I might be missing something :) $\endgroup$ – Curious Sep 4 '16 at 16:11
  • $\begingroup$ This is why small learning rate is sort of equal to "more regularizations". According to this paper, the larger the learning rate, the more regularization: Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Rates $\endgroup$ – Antoine Oct 5 '18 at 18:47
2
$\begingroup$

With Newton's method, you update your parameters by subtracting the gradient of the loss divided by the curvature of the loss. In gradient descent optimization, you update your parameters by subtracting the gradient of the loss times the learning rate. In other words, the reciprocal of the learning rate is used in place of the real loss curvature.

Let's define the problem loss to be the loss that defines what is a good model versus a bad one. It's the true loss. Let's define the optimized loss to be what is actually minimized by your update rules.

By definition, a regularization parameter is any term that is in the optimized loss, but not the problem loss. Since the learning rate is acting like an extra quadratic term in the optimized loss, but has nothing to do with the problem loss, it is a regularization parameter.

Other examples of regularization that justify this perspective are:

  • Weight decay, which is like an extra term in the optimized loss that penalizes large weights,
  • terms that penalize complicated models, and
  • terms that penalize correlations between features.
$\endgroup$
  • $\begingroup$ - I don't get In other words, the reciprocal of the learning rate is used in place of the real loss curvature. - I am not a domain expert and it is the first time I see the definition: a regularization parameter is any term that is in the optimized loss, but not the problem loss. I don't quite get it too. Could you please provide a relevant reference? Thanks in advance $\endgroup$ – Antoine May 11 '16 at 8:18
  • $\begingroup$ @Antoine I can't provide a reference. It's just my experience that I tried to justify using three other examples. As for the learning rate sitting in place of the inverse loss curvature, you can see that if you write out Newton's method and the gradient descent update rules side-by-side. $\endgroup$ – Neil G May 11 '16 at 8:20

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.