# Stopping criteria for gradient method

For numerically solving a smooth convex optimization $\min\{f(x): x\in S\}$ where $S$ is a closed convex set, we can apply some different algorithms: gradient method, accelerated gradient, proximal gradient ... depending on the structure of the problem. Solving is to find a solution $x*$ such that $f(x^*)=\inf\{f(x): x\in S\}:=f^*$. To this end, we try to construct an iterative sequence $\{x^k\}$ that converges to some solution $x^*$, or the sequence of numbers $\{f(x^k)\}$ tends to $f^*$. Note that, if $x^k\to x^*$ then the continuity of $f$ can ensures that $f(x^k) \to f^*$.

My questions are:

1. In which cases we should focus on the convergence of $\{f(x^k)\}$ rather than of $\{x^k\}$? Is finding a point $x^K$ such that $x^K$ close enough to a solution $x^*$ better than finding a point $x^K$ such that $f(x^K)$ close enough to $f^*$?

2. What is the best stopping criteria for an algorithm? I know the following ways:

• Determine the number of iterations we need to perform to achieve a desired error $\epsilon$, i.e., $||x^k-x^*||<\epsilon$ or $|f(x^k)-f^*|<\epsilon$ implies $k\geq N$ for some $N$. I see that this way is very reliable.

• terminating when $||x^{k+1}-x^k||$ or $|f(x^{k+1})-f(x^k)|$ is small enough.

• terminating when $||\nabla f(x^k)||$ is small enough.

Could you explain how the second and the third cases work? Why $||\nabla f(x^k)||$ small enough can implies that $f(x^k)$ is approximate the optimal value $f^*$. I have been know that the case $f$ is strongly convex this can be verified. Is this stopping criteria still reliable in the case where $f$ is not strongly convex?

I will discuss the termination criteria for the simple gradient method $x_{k+1} = x_{k} - \frac{1}{L}\nabla f(x_k)$ for unconstrained minimisation problems. If there are constraints, then we would use the projected gradient method, but similar termination condition hold (imposed on the norm of the difference $x_k-z_k$).

The third criterion, namely $\|\nabla f(x_k) \| < \epsilon$ if fine for strongly convex functions with $L$-Lipschitz gradient. Indeed, if $f$ is $\mu$-strongly convex, that is

\begin{aligned} f(y) \geq f(x) + \nabla f(x)^\top (y-x) + \tfrac{\mu}{2} \|y-x\|^2 \end{aligned},\tag{1}

then, for $x^*$ such that $\nabla f(x^*)=0$ (the unique minimiser of $f$), we have

\begin{aligned} f(x) - f(x^*)\leq \tfrac{1}{2\mu}\|\nabla f(x) \|^2, \end{aligned}\tag{2}

so, if $\|\nabla f(x) \|^2 < 2\mu\epsilon$, then $f(x) - f(x^*) < \epsilon$, i.e., $x$ is $\epsilon$-suboptimal.

But termination is a mysterious thing... In general (under the assumptions you drew) it is not true that we will have $\|x-x^*\|<\epsilon$ if $\| \nabla f(x) \| < \kappa \epsilon$, for some $\kappa > 0$ (not even locally). There might be specific cases where such a bound holds, notwithstanding. Unless you draw some additional assumptions on $f$, this will not be a reliable termination criterion.

However, strong convexity is often too strong a requirement in practice. Weaker conditions are discussed in the article: D. Drusvyatskiy and A.S. Lewis, Error bounds, quadratic growth, and linear convergence of proximal methods, 2016.

Let $f$ be convex with $L$-Lipschithz gradient and define $\mathcal{B}_\nu^f = \{x: f(x) - f^* < \nu\}$. Let us assume that $f$ has a unique minimiser $x^*$ (e.g., $f$ is strictly convex). Then assume that $f$ has the property

\begin{aligned} f(x) - f(x^*) \geq \tfrac{\alpha}{2} \|x-x^*\|^2, \end{aligned}\tag{3}\label{3}

for all $x\in\mathcal{B}_\nu^f$ for some $\nu>0$. Functions which satisfy this property are not necessarily strongly convex. As a counterexample we have $f = (\max\{|x|-1,0\})^2$. Of course if $f$ is strongly convex the above holds and if $f$ is given in the form $f(x) = h(Ax)$ where $h$ is a strongly convex function and $A$ is any matrix.

Then, condition \eqref{3} is shown to be equivalent to

\begin{aligned} \|x-x^*\| \leq \frac{2}{\alpha} \|\nabla f(x) \|, \end{aligned}\tag{4}\label{4}

for all $x\in\mathcal{B}_{\nu}^f$ and with $\alpha < 1/L$.

Clearly in this case we may use the termination condition $\| \nabla f(x) \| < \epsilon\alpha/2$ which will imply that $\|x-x^*\| < \epsilon$.

In regard to the second condition, you may use it again for strongly convex functions or if \eqref{3} holds locally about $x^*$. The reason for that is that the following bound holds for the gradient method:

\begin{aligned} \tfrac{L}{2}\|\nabla f(x_k) \|^2 \leq f(x_k) - f(x_{k+1}). \end{aligned}\tag{5}\label{5}

The right hand side of \eqref{5} is further upper bounded by $L_f \|x_k - x_{k+1}\|$, where $L_f$ is the Lipschitz constant of $f$ (we know that $f$ is Lipshcitz continuous), so a condition on $\|x_{k+1}-x_{k}\|$ may potentially be used, but we may see that the basis for all this is the bound on $\|\nabla f(x_k) \|$.

If $$f$$ is strictly convex, it has at most one minimum and at this minimum its gradient is zero. So the third criteria should work fine. If $$f$$ is not convex, you may reach a local minimum so this criterion is not really justified. If you are using a gradient method, the second criteria is very similar to the third because each step (or the difference $$x^{k+1}-x^{k}$$) is obtained from the gradient.

• I know the fact that "If $f$ is convex, it has just one minimum on $R^n$ and at this minimum its gradient is zero. But can you explain why $||\nabla f(x^k)||$ small enough can implies that $f(x^k)$ is approximate the optimal value $f^*$? In addition, in the constrained case, the gradient does not need to be zero at the minimum point. – Richkent Jan 19 '16 at 16:27
• Well, if $\|\nabla f\|$ is small enough (say below $\epsilon$), it can be approximated by zero, meaning that you are very close to the optimal. If $f$ is convex, the gradient is monotonous and continuous, so if it's close to zero, you are close to the minimum. – citronrose Jan 19 '16 at 16:34
• draw a $C^1$ (strictly) convex function $\mathbb{R} \to \mathbb{R}$ you'll see that if the minimum is at $a \ne -\infty$ then $|f'(x)| < \epsilon$ only when $x \in ]a-\delta;a+\delta[$, and the smaller is $\epsilon$ the smaller will be $\delta$ . after that, just remember that convex on $\mathbb{R}^n$ means that you can minimize with respect to each $x_i$ one after the other. – reuns Jan 19 '16 at 16:44
• "If $f$ is convex, it has just one minimum" is completely wrong. Some convex functions have no minimizers (e.g. $f(x) = \exp(x)$), others have a continuum of minimizers (e.g. $f(x) = 0$). – Guillaume Garrigos Mar 1 at 21:02
• @citronrose $\exp$ doesn't necessarily have a minimum on a closed domain, take for instance $S = \mathbb{R}$ or $S = [a,+\infty[$ for any $a \in \mathbb{R}$. Of course there is no such counterexamples if $S$ is compact, which is maybe the case you had in mind. – Guillaume Garrigos Mar 5 at 15:53