Difference between the Stopping Criteria [closed]

Question

I would like to know the difference between below mentioned stopping criteria used in various gradient descent algorithm

1. $\frac{Prev\_fun\_value - curr\_fun\_value}{Pre\_fun\_value} \le tol$
2. $Prev\_fun\_value - curr\_fun\_value \le tol*max(1,Prev\_fun\_value)$

where $Prev\_fun\_value$ is the previous function value before the update and $curr\_fun\_value$ is the current function value after the update of optimization variable and $tol$ is the tolerance.

Answer 1

Denote $x_i$ the successive values in the descent algorithm. The criteria are

1. $ | f(x_i) - f(x_{i+1}) | \le tol \cdot |f(x_i)| $

2. $ | f(x_i) - f(x_{i+1}) | \le tol \cdot \max(1, |f(x_i)|) $

Rougly speaking :

• Criterion 1 stops when two successive values are smaller $ tol \cdot k$ where $k$ is the order of magnitude of $f$ around the extremum.

• Criterion 2 stops when two successive values are smaller than $tol \cdot k$ or smaller than $tol$.

When $k$ is bigger than 1, criterion 1 and 2 are the same.

But if the function take small values, it makes a difference. If $tol = 0.01$ for example, and the values of your function have order of magnitude 1/1000, with criterion 1 you will stop as soon as two successive values of the function are at distance ${} \le 1/1000\times 0.01 = 0.00001$ (this is an order of magnitude) ; and with criterion 2, you’ll wait successive values $\le 0.01$.

Answer 2

There isn't any real difference, although 2 should presumably have $\leq$ in its statement.

Note that if $Prev\_fun\_value \geq 1$ in 2, then both are exactly equivalent (by dividing through $Prev\_fun\_value$ on both sides).