2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Richkent Jan 19 '16 at 16:27
  • $\begingroup$ 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. $\endgroup$ – citronrose Jan 19 '16 at 16:34
  • $\begingroup$ 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. $\endgroup$ – reuns Jan 19 '16 at 16:44
  • $\begingroup$ "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$). $\endgroup$ – Guillaume Garrigos Mar 1 at 21:02
  • $\begingroup$ @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. $\endgroup$ – Guillaume Garrigos Mar 5 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.