[SOLVED] Terminate Gradient Descent Algorithm when two iterations are “very similar”

Terminate Gradient Descent Algorithm when two iterations are “very similar”

I implemented the Gradient Descent Algorithm in R to find the minimum of the function f(x)=1−xe−x which works wonderfully and gives me [1] 1 as output, but keeps iterating until all 30.000 iterations are over, even if there are only slight changes (many digits behind the decimal point) between the iterations.

How can I add some function to the code, that terminates it as soon as the last two iterations are very similar?

this is my code:

# learning rate
epsilon = 0.02

# set up a number of iteration
iter = 30000

# define the gradient of f(x) with given f'(x)
gradient = function(x) return(-exp(-x) + x * exp(-x))

# randomly initialize the x
x = 8

# create a vector to contain all xs for all steps
x.All = vector("numeric",iter)

# gradient descent method to find the minimum
for(i in 1:iter){
  x = x - epsilon*gradient(x)
  x.All[i] = x
  print(x)
}

I tried things like adding the following without effect.

round (x, digits = 3)
if (x == x - epsilon*gradient) {
break}

I suppose as floating point number x never equals x - epsilon*gradient exactly?

Solution

Its a problem with the stopping rule you consider:

if (x == x - epsilon*gradient) break

The condition will be met only if epsilon * gradient is exactly zero, but the loop should stop when that quantity is sufficiently close to zero. So for instance, if espilon=1 and defining eps2 to be a small number (0.0001), this

if (abs(gradient(x)) < eps2) break

would work.