why slow learning rate, more iterations would be better (comparing to large learning rate less iterations)?

Question

why slow learning rate, more iterations would be better (comparing to large learning rate less iterations)?

I think this statement is generally true for neural network or gradient boosting models.

Here is one example to demonstrate the problem. In the demo, we are trying to approximate a 2D quadratic function. Ground truth is shown in left figure, and the approximation is shown in right figure. Gradient boosting model is used, where $f(x)=\sum_{i=1}^n \alpha\cdot b_n(x)$. $n$ is the iterations, and $\alpha$ is the learning rate.

1. learning rate $0.2$, iteration $50$.

2. learning rate $0.02$, iteration $500$.

Intuitively I can understand small learning rate is "fine tuning" instead of "rough tuning", but is there any formal explanations?

a related post

Boosting: why is the learning rate called a regularization parameter?

Answer 1

Gradient descent uses the gradient of the cost function evaluated at the current set of coefficients to decide next best choice to minimize the cost function.

I'm assuming we're only using the first derivative to find the gradient and the learning rate is $\alpha$. Lets use an example of a cost function as $10 b^2$. If the current best value of b is -20, then the gradient at this point is -40 and the negative gradient is 40. So we add $\alpha$ x 40 to the current value of b. If we use a value of alpha = 1, then our next best value of b will be 20, which has "overshot" the optimal point of b=0. Continuing with the same value of $\alpha$ = 1 , we get the next gradient as -40 which would take us back to b=-20; thus the algorithm would never converge on the global optimum.

If we use a smaller value of $\alpha$=0.1, then the next best value of b would be -20 + 4 = -16, which is approaching the optimal and it looks like it will converge.

If we use a slightly larger value of $\alpha$=0.2, then the next best value of b would be -20 + 8 = -12, which is closer to the optimal but the step size is larger at this point looks like it may miss the global optimum. But as we approach the global minimum, the gradient also decreases, at b=-12 the gradient = -24, which gives a step size of 4.8 .

So this shows that a smaller value of $\alpha$ also means it will take many more iterations for it to converge than a higher value of $\alpha$.

Hence, a smaller $\alpha$ (learning rate) results in a smaller step size and a better approximation of the true derivative, which in turn improves the ability to locate the optimal point.

However, as the algorithm approaches the true optimum the error of fit decreases, consequently decreasing the step size and improving the approximation of the derivative. But a large learning rate may hamper this by over-estimating the gradient resulting in the algorithm "oscillating" around the true optimum.

In practice, the truncation/round-off of small floating point numbers should also be taken into account so that the resulting step size is not too small to be used for floating point operations.

Answer 2

I assume your question concerns learning rate in the context of the gradient descent algorithm.

If the learning rate $\alpha$ is too small, the algorithm becomes slow because many iterations are needed to converge at the (local) minima, as depicted in Sandeep S. Sandhu's figure. On the other hand, if $\alpha$ is too large, you may overshoot the minima and risk diverging away from it (fail to reach it). See this website for some nice visuals.

So it's a trade-off and you need to find an $\alpha$ somewhere in the middle.

Answer 3

The formal explanation would have to do with continuity and differentiability at each point of the function. But in general, since gradient descent is a non-analytic solution to an optimization problem, you can see why using a coarser step size would not be as effective; the gradient at one point of a function simply is not as accurate the further away you go from that point. It is akin to the step size, or delta h in the first principles approach to the derivative, or the rectangle width in Riemann integration.

Note that you have given a nice, convex optimization problem. In many situations, we are dealing with highly nonconvex optimization landscapes with potentially many obstructive features like local minima, plateaux, ravines etc. In this case, I think the related post would have more info, but you could imagine a situation where a large learning rate early on might be able to sidestep a local minima, while a small learning rate would go into it. This might ultimately result in a worse optima than what a large learning rate would get.