Effects of step size in gradient descent optimisation

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?

• 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. – Nick Sabbe Jul 12 '11 at 10:04
• 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... – user88 Jul 12 '11 at 11:52
• @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. – whuber Jul 12 '11 at 13:13