Newton's method is affine invariant

ProofIntermediate⏱ 30 minAdvanced Optimizationnewtonaffine invarianceconditioning

Theory: Newton, Quasi-Newton and Conjugate Gradient →

Problem

Let $T$ be invertible and $\tilde f(z) = f(Tz)$ . Show that the Newton iterates of $\tilde f$ from $T^{-1}x_0$ are exactly $T^{-1}$ times those of $f$ from $x_0$ , and that no analogous statement holds for gradient descent. Explain the consequence for step-size tuning.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Frobenius versus operator norm for random matrices	Random Matrices	Numerical	Intermediate	30 min
Implement ridge and find the optimal lambda run	Classical ML	Coding	Intermediate	1 hour
IRLS is a weighted least-squares solve	Classical ML	Proof	Intermediate	30 min
Conjugate gradient and Krylov optimality	Advanced Optimization	Proof	Advanced	1 hour
Local quadratic convergence of Newton's method	Advanced Optimization	Proof	Advanced	1 hour