Suppose we have a $f \in C^{3} (U)$ where $U$ is an open subset (not necessarily convex) of $\mathbb R^n$ and for some $x_0 \in U$, the sublevel set $S = \{x: f(x) \le f(x_0)\}$ is compact. Further suppose the set of local minimizers of this function is not empty and every minimizer is locally strict, i.e., for any local minimizer $x^*$, there is an open neighborhood $V \subseteq U$ of $x$, such that $f(y) > f(x)$ for all $y \in V$ and $y \neq x$. Further assume the Hessian of all local minimizers is positive definite.

I am interested to know if we start at $x_0$, the convergence rate of the sequence $\{x_k\}$ generated by gradient descent with exact line search, i.e., \begin{align*} x_{k+1} = x_k - \gamma_k \nabla f(x_k), \qquad \gamma_k = \text{argmin}_{\gamma \ge 0} f(x_k - \gamma \nabla f(x_k) ). \end{align*} We only consider this as a thought experiment and so we assume in every iteration, the subproblem can be perfectly solved. This is a discussion here on the conditions to guarantee convergence for a differentiable convex function. I am putting stronger conditions and interested to know the convergence rate.

First, on the compact set $S$, $\|\cdot\| \circ \nabla^2 f: U \to \mathbb R$ is continuous and achieves maximum, so the gradient is Lipschitz. By results from convex optimization, the convergence rate should be at least $\frac{1}{k}$. Secondly, suppose $x_k \to x^*$ (might need to take a subsequence, but I think my assumptions should be enough to guarantee convergence) and by assumption every minimizer has the property $\nabla^2 f(x^*) \succ 0$. Let $F = \lambda_1 \circ \nabla^2 f$ where $\lambda_1$ is the function taking the smallest eigenvalue of a symmetric matrix. $F$ should be continuous and so there must be a neighborhood $W$ of $x^*$ s.t., $F(y) > \delta > 0$ for all $y \in W$. Then it seems like the restriction $f|_W$ should be convex and indeed strongly convex, and gradient descent should converge linearly in $W$.

Is my argument correct above? And is there more we can say about the convergence of sequence $\{x_k\}$ before it entering the open set $W$?

  • $\begingroup$ The function $x \mapsto x^4$ has a strict $\min$ at $x=0$ but the Hessian is zero. Generally you need some sort of positive definiteness (or suitably generalised condition) to get a rate. $\endgroup$ – copper.hat May 18 '18 at 4:31
  • $\begingroup$ @copper.hat: Thanks. I should've thought about this example. I will modify the assumption and assume all local minimizers have positive definite Hessian. Will this be enough to talk about rate? $\endgroup$ – user1101010 May 18 '18 at 4:42
  • $\begingroup$ You should have quadratic convergence to these points then. $\endgroup$ – copper.hat May 18 '18 at 4:48
  • $\begingroup$ Why is it quadratic? I can only see linear. Also should this quadratic convergence only happens in the neighborhood $W$ as I argued above? Thanks $\endgroup$ – user1101010 May 18 '18 at 4:52
  • $\begingroup$ I think I know why it is quadratic. Is it because the exact line search will perform at least as well as Newton iteration? $\endgroup$ – user1101010 May 18 '18 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.