4
$\begingroup$

Im using gradient-descent-based algorithm for my problem where
new_value = old_value - Step_size*Gradient

For exit criteria, im determining the change in fn value between iteration i.e.,
if (old_Objective_fn_value - new_Objective_fn_value) <=0.001 exist otherwise continue.

For different Step_size, the algorithm meets the exit criteria at different point. For example, when my Step_size is x the final objective function value is p and when my Step_size is y the final objective function value is q.

I would like to know any logical reason why the algorithm converges at different objective fun values rather than at the same.

How can we make the algorithm converge to the same objective function value irrespective of the step size with the same exit criterion?

$\endgroup$
  • 2
    $\begingroup$ If you start at other initial estimates, but use the same step size, do you still have convergence in the same point? If not, it could be that your problem is simply ill-defined for gradient descent (I believe something like sin(1/x) would cause this). Don't forget that these methods are approximations of the true max/min, so it is normal to see some variation when changing the parameters of the algorithm. $\endgroup$ – Nick Sabbe Jul 12 '11 at 10:04
  • $\begingroup$ I agree with Nick, this Q needs more details about the function you are trying to optimize, a method of counting gradient, step size values you use... $\endgroup$ – user88 Jul 12 '11 at 11:52
  • $\begingroup$ @Learner @mbq Yes, because without some indication of a specific statistical/machine learning application, this is purely a question of applied math and belongs on the math site. $\endgroup$ – whuber Jul 12 '11 at 13:13
1
$\begingroup$

You encountered a known problem with gradient descent methods: Large step sizes can cause you to overstep local minima. Your objective function has multiple local minima, and a large step carried you right through one valley and into the next. This is a general problem of gradient descent methods and cannot be fixed. Usually, this is why the method is combined with the second-order Newton method into the Levenberg-Marquardt.

$\endgroup$
  • $\begingroup$ Welcome to our community and thanks for your contribution! $\endgroup$ – whuber Jul 26 '11 at 13:45

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.