So we have gradient descent: $$x^{(i+1)} = x^{(i)} - \tau \nabla f(x^{(i)})$$

And we gotta show that $$\left|\nabla f\left(x^{(j)}\right)\right| \to 0$$

The conditions are:

  • $f: \mathbb R^n \to \mathbb R$ is differentiable

  • $\nabla f: \mathbb R^n \to \mathbb R^n$ is lipschitz continuous, so there exists an $L > 0$ such that: $$|\nabla f(x)-\nabla f(y)| \leq L|x-y|,\ \forall x,y \in \mathbb R^n$$

  • $\tau < \frac{1}{L}$

I've been trying to solve this for like an hour and can't get any further, can someone point me in the right direction?

I've been trying the following:

Assume there exists an $\epsilon > 0$, such that $|\nabla f(x^{(j)})| \geq \epsilon$ for infinitely many j but I haven't been able to find any contradiction with the assumptions.

  • $\begingroup$ Hint: Show that $\nabla f(x^{(i)})$ is Lipschitz continuous with constant $L^{i+1} \tau^i$. $\endgroup$
    – aschepler
    May 30 at 18:55

2 Answers 2


Start by proving that:

$$f(y) \le f(x) + \nabla f(x)^\intercal (y-x) + \frac L2 \left\|x-y\right\|^2$$

and then you will have:

\begin{align} f\left(x^{(t+1)}\right) \le f\left(x^{(t)}\right) - \tau \left(1 - \frac12\tau L\right)\left\|\nabla f\left(x^{(t)}\right)\right\|^2 \end{align}

If $f$ is bounded below by $\mu$, then

\begin{align} \tau \left(1 - \frac12\tau L\right) \sum_{t=0}^T \left\|\nabla f\left(x^{(t)}\right)\right\|^2 &\le \sum_{t=0}^T \left(f\left(x^{(t)}\right) - f\left(x^{(t+1)}\right)\right)\\ &= f\left(x^{(0)}\right) - f\left(x^{(T+1)}\right)\\ &\le f\left(x^{(0)}\right) - \mu < \infty \end{align}

  • $\begingroup$ Is there a way to show it with my approach too? Finding some contradiction with the assumptions if you assume it doesn't go against 0. $\endgroup$ May 30 at 21:16
  • $\begingroup$ I think you need the additional assumption that $f$ is bounded below. Consider $f(x_1, ..., x_n)=x_1$ for a counterexample. $\endgroup$
    – Ben Ciotti
    May 30 at 21:21
  • $\begingroup$ We've shown that f is monotonically decreasing and that the set of accumulation points of x^(j) is a non-empty subset of the critical points of f. I guess this can be used instead? $\endgroup$ May 30 at 21:34
  • $\begingroup$ Okay I think I found a contradiction. Gonna write out an answer to my own question $\endgroup$ May 30 at 21:41

I think I was able to find a contradiction. We know that $$x^{(j+1)}-x^{(j)} = -\tau \nabla f(x^{(j)})$$ we have also know that $$f(x^{(j+1)}) \leq f(x^{(j)}) + \langle \nabla f(x^{(j)}), x^{(j+1)}-x^{(j)}\rangle + L|x^{(j+1)}-x^{(j)}|^2$$

Inputting the first equation into the second one we get: $$f(x^{(j+1)}) \leq f(x^{(j)}) - \tau(1-L\tau)|\nabla f(x^{(j)})|^2$$

$(1-L\tau)$ is positive if $\tau < \frac{1}{L}$ so that's why this is one of the assumptions.

Now if we assume that $|\nabla f(x^{(j)})| > \epsilon$ for infinitely many j then we get: $$f(x^{(j+1)}) < f(x^{(j)}) - \tau(1-L\tau)\epsilon^2$$

$$\tau(1-L\tau)\epsilon^2 > 0 \implies\lim_{j \to \infty} f(x^{(j)}) = -\infty$$

This is a contradiction to something we've already proven:

The set of accumulation points of $(x^{(j)})$ is a non-empty subset of the critical points of f.

Since if $f(x^{(j)})$ just keeps dropping there are no critical points in f so the set of accumulation points of $(x^{(j)})$ is empty.


You must log in to answer this question.

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