5
$\begingroup$

Let $f: \mathbb{R}^d\rightarrow\mathbb{R}_{\geq 0}$ be a function which is convex and smooth (i.e., in $C^{\infty}$). If $x^* \in \mathbb{R}^d$ is the (global) minimum of $f$, it is well known that gradient descent with a (sufficiently small) fixed step size $\eta$, $$ x_{n+1} = x_{n} - \eta \nabla f(x_n), $$ converges to the global minimum $x_n \rightarrow x^*$.

Question: What is the asymptotic behavior of gradient descent when a finite minimizer $x^*$ does not exist (i.e., when $\forall x \in \mathbb{R}^d : \nabla f(x)\neq 0$)?

My guess is that $x_n/||x_n||$ should converge to some finite solution, but I could not find a proof. Or perhaps there is some counter-example to this claim?

Thanks in advance!

$\endgroup$
7
  • $\begingroup$ The function $f(x)=atan2(x(1),x(2))$ is a counterexample. You can also find a continuous counterexample by changing this function locally at the half line of discontinuity. $\endgroup$
    – user100927
    Commented Oct 5, 2017 at 11:38
  • $\begingroup$ Thanks for the answer, but this function appears to be non-convex. $\endgroup$ Commented Oct 5, 2017 at 11:51
  • $\begingroup$ Ok then take $f(x)=ax(1)^2-x(2)$ with $a>\eta^{-1}$ instead. $\endgroup$
    – user100927
    Commented Oct 5, 2017 at 12:07
  • $\begingroup$ This function can be negative, and also this is not a counter-example since $ x_n / || x_n ||$ converges to $(0,1)$ or $(0,-1)$. $\endgroup$ Commented Oct 5, 2017 at 13:00
  • 2
    $\begingroup$ Btw, the two variable function $f(x,y)=e^x + x^2y^2$ is not convex. $\endgroup$ Commented Oct 6, 2017 at 8:31

1 Answer 1

3
$\begingroup$

I think there are simple counterexamples of the form $f(x,y)=\phi(x)+\psi(y)$ (here $x$ and $y$ denote real variables), where $\phi$ and $\psi$ are smooth, positive, decreasing, strictly convex functions.

The idea is that, $-\psi'(x)$ and $-\phi'(x)$ being positive decreasing functions, is not an obstruction for their ratio to oscillate between arbitrarily large and small values, on arbitrarily large intervals. This produces zig-zag orbits $z_n:=(x_n,y_n)$ for which $z_n/\|z_n\|$ may accumulate to both $(1,0)$ and $(0,1)$.

Construction. Define some smooth, positive, decreasing functions $u(t)$ and $v(t)$ such that for all $n\in\mathbb{N}$ $$u(x):={1\over (n!)^2}\quad\text{for $n$ even, and}\; n!+1\le x\le (n+2)!$$ and $$v(x):={1\over (n!)^2}\quad\text{for $n$ odd, and}\; n!+1\le x\le (n+2)!$$

(so one has only to extend them smoothly for $x\le2$ and between $n!$ and $n!+1$ to have them defined everywhere). As a consequence we have $${v(x)\over u(x)}=\begin{cases} n^{-2} &\text{for $n$ odd, and }\; n!+1\le x\le (n+1)! \\ n^2 &\text{for $n>0$ even, and }\; n!+1\le x\le (n+1)! \\ \end{cases}$$ while $$n^{-2}\le {v(x)\over u(x)}\le n^2 \quad \text{for any $n>0$ and }\; n! \le x\le n!+1 \ .$$

Note also that $u$ (respectively $v$) has finite integral on any right-unbounded interval, because the contribute to the integral on any interval $[n!+1, (n+2)!+1]$ (for $n$ even, resp. odd) is bounded by $(n+2)!/(n!)^2=(n+2)(n+1)/n!$. Therefore we can consider the smooth, decreasing, strictly convex functions $$\phi(x):=\int_x^\infty u(t)dt\quad\text{and }\quad \psi(x):=\int_x^\infty v(t)dt\; .$$

The negative gradient iteration $u_{n+1}=u_n-\eta\nabla f(u_n)$ writes, with $z_n:=(x_n,y_n)$ $$ \begin{cases} x_{n+1}=x_n+\eta \,u(x_n) \\ y_{n+1}=y_n+\eta \,v(y_n)\\ \end{cases} $$ and it follows from the above identities and inequalities on $v/u$ that it produces sequences $(x_n,y_n)$ with $\liminf_{n\to+\infty}y_n/x_n=0$ and $\limsup_{n\to+\infty}y_n/x_n=+\infty$, corresponding to a sequence $z_n/\|z_n\|$ that clusters both to $(1,0)$ and to $(0,1)$.

Sketch of the computation. Both sequences $x_m=x_0+\eta\sum_{k=0}^{m-1}u(x_j)$ and $y_m=x_0+\eta\sum_{k=0}^{m-1}v(y_j)$ are increasing and diverging. Let's define $\mu(t)$ as the largest integer $j$ such that $x_j\le n!$ and $\nu(t)$ as the largest integer $j$ such that $y_j\le n!$. The point is to use the above identities and inequalities on $u$ and $v$ to show that, for even $n$ and $m=\mu(n!)$, the principal part in both the above sum is given by the indices $j$ such that $\mu(n!)\le j\le \mu((n+1)!)$, so that $y_m/x_m=O(1/n^2)$. Analogously, for odd $n$ and $m=\nu(n!)$, one should get $x_m/y_m=O(1/n^2)$.

$\endgroup$
10
  • $\begingroup$ Thanks! It is not clear to me why such $\phi,\psi$ (or $u,v$) exist (or how to find them), and why the inequalities imply the result in the end. $\endgroup$ Commented Oct 6, 2017 at 18:10
  • 1
    $\begingroup$ Yes, sorry, I should add more details. $\endgroup$ Commented Oct 6, 2017 at 18:21
  • 1
    $\begingroup$ Good question and nice conjecture! $\endgroup$ Commented Oct 7, 2017 at 14:18
  • 1
    $\begingroup$ If it is good question, then perhaps it should also be on MO. So here it is: mathoverflow.net/q/282934/44790 $\endgroup$ Commented Oct 7, 2017 at 15:08
  • 1
    $\begingroup$ But if you want an analytic counterexample, you can approximate $u$ and $v$ with decreasing real analytic functions $\mathbb{R}\to\mathbb{R}$ in such a way that their ratio at any $x$ stays between half and twice the ratio of $u(x)$ and $v(x)$ (apply to $u'$ and $v'$ Carleman's theorem quoted here mathoverflow.net/questions/26243/…). Also, you can build directly $u$ and $v$ as entire functions by means of conveniently defined lacunary series. $\endgroup$ Commented Mar 9, 2018 at 12:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .