Why when a function is quadratic, the approximation by Newton's method is exact, and the algorithm converges to the global minimum in a single step?

Question

Suppose we want to find the value of $x$ that minimizes $$ f(x)=\frac{1}{2}\|A x-b\|_{2}^{2} . $$ Specialized linear algebra algorithms can solve this problem efficiently; however, we can also explore how to solve it using gradient-based optimization as a simple example of how these techniques work. First, we need to obtain the gradient: $$ \nabla_{x} f(x)=A^{\top}(A x-b)=A^{\top} A x-A^{\top} b . $$ We can then follow this gradient downhill, taking small steps.

\begin{array}{} \hline \text{Algorithm $4.1$ An algorithm to minimize} f(x)=\frac{1}{2}\|A x-b\|_{2}^{2} \text{ with respect to $x$} \\ \text{using gradient descent, starting from an arbitrary value of $x$.} \\ \hline \text{Set the step size $(\epsilon)$ and tolerance $(\delta)$ to small, positive numbers. }\\ \text{while $\left\|A^{\top} A x-A^{\top} b\right\|_{2}>\delta$ do} \\ \quad x \leftarrow x-\epsilon\left(A^{\top} A x-A^{\top} b\right) \\ \text{end while} \end{array}

One can also solve this problem using Newton's method. In this case, because the true function is quadratic, the quadratic approximation employed by Newton's method is exact, and the algorithm converges to the global minimum in a single step.

Deep Learning, Bengio and al. page 94

I don't get this very last point. Indeed, we set the step size $(\epsilon)$ and tolerance $(\delta)$ to small, positive numbers and we don't even have something like an adaptative step size that would augment if we are far from the target. So would it truly converge to the global minimum in a single step? Don't we need to iterate quite a lot rather?

I am a dumb programmer and slow math learner, don't hesitate to explain it to me as if I was a teenager.

Answer 1

When the book wrote that Newton's method converges in a single step, it is correct. If you look at the specification of Newton's method, you will notice no $\epsilon$ or $\delta$ to set. (There is no need for a tolerance $\delta$ here as it converges in one step, and in any case, even if you set one, it would terminate after one step no matter what $\delta$ you set.) Newton's method is not the same as gradient descent. To see why it converges in a single step for a quadratic function, try writing a general quadratic function (say $f(x)=ax^2+bx+c$), compute what Newton's method gives you after one step, and compare to the actual minimum of this function.