I.3.8.4: Sublinear Convergence

Convergence can be sublinear.

$$\begin{align*} \psi(\omega,\xi)&=(\omega-\xi)^2+\omega^4,\notag \\ \mathcal{D}_1\psi(\omega,\xi)&=2(\omega-\xi)+4\omega^3,\notag\\ \mathcal{D}_2\psi(\omega,\xi)&=-2(\omega-\xi),\notag\\ \mathcal{D}_{11}\psi(\omega,\xi)&=2+12\omega^2,\notag\\ \mathcal{D}_{12}\psi(\omega,\xi)&=-2,\notag\\ \mathcal{D}_{22}\psi(\omega,\xi)&=2.\notag \end{align*}$$

It follows that coordinate descent updates $\omega^{(k)}$ by solving the cubic $\omega-\omega^{(k)}+2\omega^3=0.$ The sequence converges to zero, and by l'Hopitål's rule $$\lim_{k\rightarrow\infty}{\frac{\omega^{(k+1)}}{\omega^{(k)}}}=1.$$ This leads to very slow convergence. The reason is that the matrix of second derivatives of $\psi$ is singular at the origin.