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.