Norm of gradient in gradient descent

Question

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.

Answer 1

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)$.

Answer 2

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.