4
$\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^*$.

When a finite minimizer $x^*$ does not exist (i.e., when $\forall x \in \mathbb{R}^d : \nabla f(x)\neq 0$), one might expect that $x_n/||x_n||$ should converge to a finite solution. However, there are counterexamples to this claim.

Question: What additional assumptions (as "light" as possible) do we need to add to have on $f$ so that $x_n/||x_n||$ would converge (for a sufficiently small $\eta$)? The counterexample above suggests that the Hessian of $f$ perhaps should have a bounded eigenvalue ratio. Is this enough?

Thanks in advance!

$\endgroup$
3
  • $\begingroup$ You mean the "hessian" should have a bounded eigenvalue ratio, right? This is definitely a sufficient condition as it implies that the function is then strongly convex and thus have a unique global minimizer. So your gradient descend will converge to this solution. $\endgroup$
    – Surb
    Commented Oct 7, 2017 at 19:34
  • 1
    $\begingroup$ Yes, 'Hessian' would be clearer here, corrected. I don't think it is this easy though. The Hessian can vanish to zero at infinity, yet the ratio can remain bounded. $\endgroup$ Commented Oct 7, 2017 at 19:42
  • $\begingroup$ I think you may need to require $f$ to be a $C^1$ semi-algebraic function. $\endgroup$ Commented Nov 21, 2022 at 2:52

0

You must log in to answer this question.