# Difference between the Stopping Criteria [closed]

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.

-

## closed as off topic by onestop, whuber♦Aug 14 '12 at 13:00

Questions on Cross Validated are expected to relate to statistics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

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$.

-
I guess you misquoted the criteria numbers! –  Learner Jan 21 '12 at 16:10
In fact I think I overread the max for a min... sorry, hope it looks correct now –  Elvis Jan 21 '12 at 16:42
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).
wrongly typed my Q with $=$ sign. will edit it. –  Learner Jan 21 '12 at 13:34