# Determine the optimum learning rate for gradient descent in linear regression

How can one determine the optimum learning rate for gradient descent? I'm thinking that I could automatically adjust it if the cost function returns a greater value than in the previous iteration (the algorithm will not converge), but I'm not really sure what new value should it take.

(Years later) look up the Barzilai-Borwein step size method; onmyphd.com has a nice 3-page description. The author says

this approach works well, even for large dimensional problems

but it's terrible for his applet of the 2d Rosenbrock function. If anyone uses Barzilai-Borwein, please comment.

You are on the right track. A common approach is to double the step size whenever you take a successful downhill step and halve the step size when you accidentally go "too far." You could scale by some factor other than 2, of course, but it generally won't make a big difference.

More sophisticated optimization methods will likely speed up convergence quite a bit, but if you have to roll your own update for some reason the above is attractively simple and often good enough.

• I was thinking of multiply/divide by two as well. However, I'm concerned that multipling by two each time a successful step occurs will end up in much more iterations. I was hoping that there is a way to do it using the gradient, since it provides some info on how steep the slope is. – Valentin Radu Dec 19 '12 at 18:40
• It doesn't seem plausible to me, that you can get such information from the gradient. Gradient alone doesn't tell you how far you are from the optimum, and what's more important - how does the gradient itself change when $x$ changes. For that you would need a Hessian. – sjm.majewski Dec 25 '12 at 18:34
• If you're dealing with an underlying stationary process, the maximum learning rate is governed by the spectrum of the correlation matrix, right? – bright-star Mar 21 '14 at 23:19