Let $U$ be an open convex subset of $\mathbf{R}^n$ and $f:U\rightarrow\mathbf{R}$ be a differentiable and convex function. We assume that $f$ has a unique global minimum $x^\star$ over $U$. It is well-known that if $\nabla f$ is $L$-Lipschitz then for any $x_0\in U$ the sequence
$$x_{n+1}=x_n – L^{-1}\nabla f(x_n) $$
converges to $x^\star$. I would like to know whether the Lipschitz condition is necessary.
Specifically, I am looking for a counterexample. Is it possible to find $U$ and $f$ such that for some $x_0\in U$ and any $\eta>0$ the gradient descent
$$x_{n+1}=x_n-\eta\nabla f(x_n)$$
does not converge to $x^\star$?
For example, I would be very interested to see if there exists a counterexample with $\nabla f$ uniformly continuous over $U$.
Best Answer
I think that the example from the linked answer can be modified to fit your bill "fix $x_0$, no $\eta > 0$" works.
First, we note that the example cannot be one-dimensional. Indeed, you can always choose $\eta$ such that $x_1$ is already the minimizer.
In two dimensions, I think that the following should work. Define $$ f(x,y) = \frac23 (x^2 + 2 y^2)^{3/4} $$ and choose $(x_0, y_0) = (1,1)$. It seems that no $\eta$ gives you convergence. I guess that it is also not hard to prove this.