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$
14
  • $\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$ Commented Mar 14, 2018 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$ Commented Mar 14, 2018 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$ Commented Mar 14, 2018 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
    Commented Mar 14, 2018 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
    Commented Mar 14, 2018 at 16:00

2 Answers 2

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$
3
  • $\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
    Commented Mar 22, 2018 at 8:28
  • $\begingroup$ Can you give a final formula with all fixed? $\endgroup$
    – max_zorn
    Commented Mar 24, 2018 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
    Commented Mar 24, 2018 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$
7
  • $\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
    Commented Mar 21, 2018 at 14:10
  • $\begingroup$ @daw It converges to the infimum due to the monotone convergence theorem. $\endgroup$
    – Damien
    Commented Mar 21, 2018 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
    Commented Mar 21, 2018 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
    Commented Mar 21, 2018 at 19:54
  • 1
    $\begingroup$ When you apply Bolzano-Weierstrass, why are the sequences bounded? Great attempt though! $\endgroup$
    – max_zorn
    Commented Mar 22, 2018 at 5:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .