Show that in gradient descent the gradient goes against 0 (Under certain conditions)

Question

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.

Answer 1

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}

Answer 2

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.