1
$\begingroup$

I have been working on implementing a line search method for gradient descent where I made an assumption that at any given point on my surface of the loss function I can reach the minima by the single correct value of the learning rate $\eta$ which I should choose. I have been trying to find this learning rate using binary search but after the entire implementation, I came to realize that my assumption I made is wrong which means I cant directly reach my minima from any given point on the surface of the loss function for any given learning rate in a single step. Can I get a more intuitive explanation of why my initial assumption is wrong?

Edit: my loss function is convex and has a large number of parameters I am trying to learn ( multidimensional)

Improve this question
$\endgroup$
1
$\begingroup$

This isn't a perfect example but hopefully the idea is clear. If you start at a point just left of 0, small learning rates will never get it out of the local minimum at the left. But large enough learning rates to leave that local minimum will never let it settle at the global minimum at the right.

A decaying learning rate could work for such a point.

enter image description here

Improve this answer
$\endgroup$
  • $\begingroup$ thanks for giving me this example sir. I missed an important detail in the question. My function is convex and I have greater than 2 parameters to learn. Why does my assumption fail in that case? $\endgroup$ – venkat Mar 7 '20 at 7:46
  • $\begingroup$ Standard SGD will get arbitrarily close to the minimum given a small enough learning rate and enough steps. My guess is you perhaps expecting to find the exact minimum, and not running long enough in your search. $\endgroup$ – Sean Owen Mar 7 '20 at 17:59
  • $\begingroup$ my assumption was that as my function is convex I compute just a single gradient and one right $\eta$ will take me directly from this point to the minimum without visiting any intermediate points and computing gradients at them. so I was finding this " one right" $\eta$ using binary search. but this assumption turned out to be wrong as even with the right $\eta$ I am landing in a point with a lesser loss than the starting point but not the minimum. I was expecting an explanation to why this is happening $\endgroup$ – venkat Mar 8 '20 at 8:55
  • $\begingroup$ Sure, that number exists. I am not clear that searching from one point is superior to continuing with SGD. But, how do you mean you use binary search? It is not a search over an ordered list. I think the error is somewhere in there. $\endgroup$ – Sean Owen Mar 8 '20 at 21:13
  • $\begingroup$ From a given point I am finding three points $w_{1},w_{2},w_{3}$ that bracket my minima and am finding those corresponding $\eta_{1}$,$\eta_{2}$,$\eta_{3}$, now I find the best $\eta$ that takes me to the minima which lies in between these three etas by a method similar to binary search. This is where my assumption is failing because this best $\eta$ is taking me to a lower loss but not to the minima directly. $\endgroup$ – venkat Mar 9 '20 at 5:52

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.