This question discusses the size of gradient in gradient descent. Some examples were pointed to show it is not necessarily the case that gradient will decrease, for example, $f(x) = \sqrt{|x|}$ or $f(x) = 1- \cos(x)$ with $x \in (-\pi, \pi)$.
My question is: Suppose we have a nonconstant function $f \in C^{\infty}(K)$ where $K \subset \mathbb R^n$ is a compact set. Further assume $f$ only has one stationary point $x^* \in \text{int}(K)$ and assume this point $x^*$ is a global minimum. Let $\{x_k\}$ be a sequence generated by gradient descent. Will $\{\|\nabla f(x_k)\|\}$ be monotonically decreasing?
I feel like the answer is yes. The counterexamples (certainly not exclusive) do not satisfy the assumptions.
$\endgroup$ 122 Answers
$\begingroup$I would like to point out that also convexity of $f$ does not ensure a decrease of the gradient.
Consider $$f(x) = \frac12 x^\top \begin{pmatrix}1 & 0 \\ 0 & 100 \end{pmatrix}x$$ with starting value $x_0 = (1000,1)$. It can be checked that a gradient step (with exact step length) leads to $x_1 = (495, -49.5)$ and the norm of the gradient increases by almost a factor of 5.
$\endgroup$ 2 $\begingroup$For $t>0$, let $g(t) = \exp(\cos(1/t^4)-1/t^2)$. Notice that setting $g(0)=0$, $g(t)>0$ for $t> 0$, $g$ is smooth and it oscillates infinitely often as $t$ approaches $0^+$.
For $t\geqslant 0$, consider $F(t) = \int_0^t\,g(s)\,ds$. We have that $F$ is smooth and $F(0)=0$ is a global minimum. Moreover, its derivative is not monotonic decreasing as $t\to 0$.
At this point, we just need to take $f(x) = F\left({\lVert x - x^* \rVert}^2\right)$.
$\endgroup$
