9
$\begingroup$

Suppose $f\colon\mathbb{R}^n\to\mathbb{R}$ is convex and differentiable, and assume that $f$ has a minimizer.

If $(x_k)$ is the sequence generated by exact gradient descent, must it converge to a minimizer?

Here "exact gradient descent" means that $x_{k+1} = x_k-t_k\nabla f(x_k)$ where it is assumed that $t_k$ is a minimizer of the function $t\mapsto f(x_k-t\nabla f(x_k))$ for $t\geq 0$ (the existence of $t_k$ is assumed for all $k$).

Reference or counterexample would be great. (I am aware of Wolfe's example demonstrating the importance of differentiability. I am also aware that this works when $f$ is strictly convex and coercive.)

$\endgroup$
  • $\begingroup$ So there's a little bit of a logical fallacy here, I think. Let me know what you think. In exact gradient descent, you compute the gradient $\nabla f(x)$, then you look for a $t$ that minimizes $f(x-t\nabla f(x))$. You must of course use a one-dimensional optimization algorithm to solve that step size problem! So you are in effect pre-assuming the convergence of an optimization algorithm on the very function you are trying to minimize, albeit only along lines. With all of the common non-exact step size approaches there is no circular assumption. $\endgroup$ – Michael Grant Mar 14 '18 at 13:14
  • $\begingroup$ Furthermore, assuming the typical case that a gradient algorithm only converges in the limit, the line searches themselves will only converge in the limit, too. Assuming a finite computation speed you'll never complete even the first step. $\endgroup$ – Michael Grant Mar 14 '18 at 13:17
  • $\begingroup$ That said, I think you can argue that if you assume Lipschitz continuity of the gradient, exact line search meets all the criteria of a backtracking line search with an Armijo step size rule, so the number of outer iterations can be bounded by the result for that approach. $\endgroup$ – Michael Grant Mar 14 '18 at 13:21
  • 2
    $\begingroup$ I wrote "If", so I assume we can do all the one-dimensional optimizations on the rays exactly. It is a thought experiment (as is math in general :) $\endgroup$ – max_zorn Mar 14 '18 at 14:47
  • 1
    $\begingroup$ Lipschitz continuity guarantees a rate of convergence in typical proofs of gradient descent (e.g., Boyd&Vandenberge, 9.3.1), but it is not clear that it is needed for convergence per se. $\endgroup$ – LinAlg Mar 14 '18 at 16:00
5
+50
$\begingroup$

Here is something that can go wrong without strict convexity.

Define $f(x,y)=\max(0,|x|-1,|y|-1)^2.$ This isn't $C^1,$ but that can be fixed later. It attains the minimum value of $0$ in the square $|x|,|y|\leq 1.$ If we start at a point with $x,y>1$ and $x-1>2(y-1)$ then $f$ is locally equal to $(x-1)^2$ and has gradient $(2(x-1),0).$ The minimum of $y$ along the horizontal line of constant $y$ is $(y-1)^2,$ and we can adverserially pick the next point $(x',y')$ to have $x'$ slightly less than $-1,$ so $(-x'),y'>1$ with $y'-1>2((-x')-1).$ This is the same kind of inequality we started with for $(x,y)$ except rotated anti-clockwise by a right angle. Continuing in this way, we get a sequence of points whose limit set consists of the four corners $(\pm 1,\pm 1),$ and hence diverge by oscillation.

To fix the non-differentiability, in the region $x,y>1$ and $(x-1)/(y-1)\in (1/2,2),$ replace $f$ by the function that sends $(1+t(1+\cos\theta),1+t(1+\sin\theta))$ to $4t^2$; here $t>0$ and $0<\theta<\pi/2.$ Along $(x-1)=2(y-1)$ this equals $(x-1)^2$ with horizontal gradient as required. The other boundary $(y-1)=2(x-1)$ is similar, and the other corners can be handled in the same way so that the function is even in $x$ and $y.$ The derivatives at $(\pm 1,\pm 1)$ are still zero.

If the level sets are bounded, this should be the only thing that can go wrong - the sequence can diverge by oscillation, but all the limit points are minimizers.

$\endgroup$
  • $\begingroup$ This is true, but the function is minimal at the four corners of the square. Although the sequence $x_k$ diverges, the sequence $f(x_k)$ converges to the minimum. $\endgroup$ – Damien Mar 22 '18 at 8:28
  • $\begingroup$ Can you give a final formula with all fixed? $\endgroup$ – max_zorn Mar 24 '18 at 5:07
  • $\begingroup$ @max_zorn: I'm not sure what you mean. There's no analytic function (e.g. elementary functions), because the set of minima of a convex analytic function have to be an affine space - the intersection with any line is either the whole line or a single point. $\endgroup$ – Dap Mar 24 '18 at 9:08
2
$\begingroup$

We have assumed that $f : \mathbb{R}^N \rightarrow \mathbb{R}$ is convex, differentiable and has a minimiser. Let the line search function be denoted by, $$ \begin{align} g_k : \mathbb{R} \rightarrow& \mathbb{R} \\ t \mapsto& f(x_k - t \nabla f(x_k)) \end{align} $$

Lemma 1. If $\frac{dg_k}{dt}(0) = 0$ then $x_k$ is the minimum of $f$.

Proof. The derivative of $g_k$ is $\frac{dg_k}{dt} = \nabla f(x_k - t\nabla f(x_k)) \cdot \nabla f(x_k)$. Suppose that $\frac{dg_k}{dt}(0) = 0$, then $\nabla f(x_k)\cdot\nabla f(x_k) =0$, i.e. $\|\nabla f(x_k)\|^2 = 0$, and so $x_k$ is at the minimum. $\square$

The function $g_k$ is,

  • Convex as an affine transformation of $f$, which is convex.
  • Non constant. If it were then $\frac{dg_k}{dt} = 0$ for every $t \in \mathbb{R}$ and so $x_k$ is the minima by Lemma 1.

Lemma 2. If $x_{k+1} = x_k$ then $x_{k+1}$ is the minima.

Proof. The value $t_k$ is the minimiser of the function $g_k$. If $t_k = 0$ then, $\frac{dg}{dt}(0) = 0$, and so, by Lemma 1 we are at the minimum. Instead assume that $t_k \neq 0$. If $x_{k+1} = x_k$ then $t_k \nabla f(x_k) = 0$ and so $x_k$ is the minimum. $\square$

Lemma 3. The sequence defined by $z_k = f(x_k)$ is strictly decreasing unless $x_k$ is the global minima of $f$, in which case $x_n = x_k$, $\forall n\geq k$.

Proof. It suffices to prove that $g_k(t_k) < g_k(t)$ for every $t \in \mathbb{R}$. We know that $g_k(t_k) \leq g_k(t) $ by assumption. If $\exists t^* \neq t_k$ such that $g_k(t_k) = g_k(t^*) $, then $g_k$ is constant. By Lemma 1 it follows that $x_k$ is the minima. If it is the minima then $\nabla f(x_k) = 0$ and so $x_{k+1} = x_k$. $\square$

Theorem The sequence $z_k = f(x_k)$ converges to the minimum $x^*$.

Proof. The sequence $z_k$ is a real and strictly decreasing for all $z_k > f(x^*)$. It is bounded below by $f(x^*)$ and so it converges its infimum $ \ell = \inf_k{z_k} $ by the monotone convergence theorem. But $f(x_k) \to \ell$ which means that $\nabla f(x_{k}) \to 0$ as $k \to \infty$. $\nabla f(x_{k}) = 0$ only at the minimum of $f$, and so $\ell$ is the minimum.

$\endgroup$
  • $\begingroup$ The last proof is missing an argument: Why is the limit of $z_k$ equal to $f(x^*)$? It could be stuck to be larger than $f(x^*)$. $\endgroup$ – daw Mar 21 '18 at 14:10
  • $\begingroup$ @daw It converges to the infimum due to the monotone convergence theorem. $\endgroup$ – Damien Mar 21 '18 at 18:06
  • $\begingroup$ the monotone convergence theorem tell you that the sequence is converging, it does not tell you anything what the limit is precisely. $\endgroup$ – daw Mar 21 '18 at 19:09
  • $\begingroup$ @daw Yes that is true. It converges to the minimum because of the direction of the gradient. I've put more details in the post. $\endgroup$ – Damien Mar 21 '18 at 19:54
  • 1
    $\begingroup$ When you apply Bolzano-Weierstrass, why are the sequences bounded? Great attempt though! $\endgroup$ – max_zorn Mar 22 '18 at 5:37

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.