Let us consider a function $f\in C^2$, and convex such that the Hessian $H\le LI$. We consider following minimization problem: $$\min_{x\in \mathbb{R}^n }f(x)$$ Let us consider the following iterative process for estimating the minimizer, $$x^{k+1}=x^k-A \nabla f(x^k)$$ where the matrix $A$ can be singular. It is well known, that if $A=\mu I$, a suitable Lyapunov function to use for checking convergence, is the function $f$ itself, as in that setting we have $$f(x^{k+1})\le f(x^k)-(\mu-\mu^2L/2)\|\nabla f(x^k)\|_2^2 $$ which shows descent property for $0<\mu <2/L$.

My question is,

Is it possible to choose such a suitable Lyapunov function for the general case when $A$ might be singular. Of course, we could choose $f$, but then to have descent property we need to have $A-L/2 A^tA$ positive definite. I just want to know if there are better functions that might impose weaker restrictions on $A$ and still have a descent property.

Any reference to literature and existing techniques will be highly appreciated. Thanks in advance.

Edit: Another observation that I have made is that, if we have some $x^\star$ such that $\nabla f(x^\star)=0$, we can write the following $${x}^{n+1}-{x}^\star=({I-AG}({x}^\star,\ {x}^n))({x}^n-{x}^\star)$$ where $$G({x}^\star,\ {x}^n)=\int_0^1 \nabla^2f(x^\star+\tau(x^n-x^\star))d\tau$$ Then, analyzing convergence of the sequence $\{x^n\}$ is equivalent to finding suitable conditions on the minimum and maximum eigenvalues of $AG({x}^\star,\ {x}^n)$. Does the function $\|x-x^\star\|_2$ then qualify as a Lyapunov function? Even if it is true, I can not find an analog of $f(\cdot)$ which acts a Lyapunov function for the general case. I have read a few sections of the paper that @dohmatob referred in the comments, but I think I cannot find a Lyapunov function for this problem using the techniques introduced in that paper. The matrix $A$ is creating the problem.

  • $\begingroup$ If $f$ is strongly convex w.r.t to some $h$ in the Breg-divergence sense (e.g $h=\frac{1}{2}\|.\|_2^2$ for ordinary strong convexity), then you can construct a time-varying Lyaponov function which does the job. Take a look at sections 3 and 5 of this paper arxiv.org/pdf/1611.02635.pdf. $\endgroup$
    – dohmatob
    Aug 7, 2017 at 21:38
  • $\begingroup$ @dohmatob, I actually recently downloaded this paper before posting this question and skimmed through it to find any mention of this Newton-type algorithms, with the gradient pre-multiplied by some matrix. However, the paper seems to be on finding Lyapunov functions for momentum methods, which differ in structure from the problem I posted. Stil I will have a closer look to see if it is of any help to me. Thanks! $\endgroup$ Aug 8, 2017 at 7:31


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.