2
$\begingroup$

I have a doubt . I read somewhere that gradient descent will diverge if the step size chosen is large. But the gradient descent say using exact line search says chose a step size only if it moves down i.e f[x[k+1]]< f[x[k]]..

what i read which led to this doubt In some slides

Now ideally it choses the direction of negative gradient[this itself says that the direction is towards the inner contours] and the step size is chosen till the point[using exact line search ] where f keeps on decreasing..so at max which will be reached in case of anisotropic or [circular form] it should straight end at the minimum

$\endgroup$
  • 1
    $\begingroup$ The standard gradient descent does have a fixed stepsize, so it is possible overshoot. That is illustrated in the picture you linked. $\endgroup$ – P. Siehr Aug 16 '17 at 11:54
  • $\begingroup$ so step size is not chosen according to exact line search here? and ikf exact line search haapens the overshooting condition wont happen? $\endgroup$ – YNWA Aug 16 '17 at 11:56
  • $\begingroup$ Try minimizing $f(x) = x^2$ starting from $x_0= 1$ and using $\eta = 1$. To overcome this, you'll detect when the decrease in objective function isn't consistent with the (mean) gradient magnitude, in those cases you'll divide $\eta$ by $2$. @P.Siehr $\endgroup$ – reuns Aug 16 '17 at 11:58
  • $\begingroup$ Here is a basic implementation of the problem in your slides. You can see the solution explodes, if the step size is too large. $\endgroup$ – P. Siehr Aug 16 '17 at 12:13
  • $\begingroup$ @reuns Yes, that is a very naive, but usually very good and easy to implement., method of steps size control. (And I use it often as well.) Linesearch, that is mentioned by OP, is another method to guarantee convergence. $\endgroup$ – P. Siehr Aug 16 '17 at 12:14
3
$\begingroup$

Gradient Descent Method means each iteration you move from the current point to the next using the opposite direction of the gradient.

Each iteration is a function of 2 parameters:

  • Direction.
  • Step Size.

The Gradient Descnet direction only promises there is a small ball which within this ball the value of the function decrease (Unless you're on a stationary point).
Yet the size (Radius) of this ball isn't known.

There are many algorithms to find a valid step size.
One of them (Probably the hardest) is the Exact Line Search.
In practice better choice would be Backtracking.

For large Step Size you may get outside the "Ball" where the function is decreasing and practically find a worse point.
Iterating this might cause a diverge.

| cite | improve this answer | |
$\endgroup$

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.