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

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.

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

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}

• 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. May 30 at 21:16
• I think you need the additional assumption that $f$ is bounded below. Consider $f(x_1, ..., x_n)=x_1$ for a counterexample. May 30 at 21:21
• 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? May 30 at 21:34
• Okay I think I found a contradiction. Gonna write out an answer to my own question 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$$

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.