Meaning of affine invariance of Newton's method

1.2k Views Asked by At

Newton's method is affine invariant in the following sense. Suppose that $f$ is a convex function. Consider a linear transformation $y\mapsto Ay$, where $A$ is invertible. Define function $g(y)=f(Ay)$. Denote by $x^{(k)}$ the $k$-th iterate of Newton's method performed on $f$. Denote by $y^{(k)}$ the $k$-th iterate of Newton's method performed on $g$. If $y^{(0)}=A^{-1}x^{(0)}$, then we have that $$ Ay^{(k)}=x^{(k)} $$ and $\lambda (y^{(k)})=\lambda(x^{(k)})$, where $\lambda(x)$ is the Newton decrement. Intuitively, this means that we can recover one minimizing sequence from another and the stopping criterion is not affected by the linear transform.

Is $f(x^{(k)})-f(x^*)$ going to be the same as $g(y^{(k)})-g(y^*)$, where $x^*$ is the minimizer of $f$ and $y^*=A^{-1}x^*$? How about $\|x^{(k)}-x^*\|_2$ and $\|y^{(k)}-y^*\|_2$?

I would say that the answer is negative. Even if the linear transformation does not affect the minimizing sequence, the convergence rate of the minimizing sequence might be different. Is this correct?