# Newton's method algorithm for linear least squares

Section 4.5 Example: Linear Least Squares of the textbook Deep Learning by Goodfellow, Bengio, and Courville, says the following:

Suppose we want to find the value of $$\mathbf{x}$$ that minimizes

$$f(\mathbf{x}) = \dfrac{1}{2}||\mathbf{A} \mathbf{x} - \mathbf{b}||_2^2 \tag{4.21}$$

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_{\mathbf{x}} f(\mathbf{x}) = \mathbf{A}^T (\mathbf{A}\mathbf{x} - \mathbf{b}) = \mathbf{A}^T \mathbf{A} \mathbf{x} - \mathbf{A}^T \mathbf{b} \tag{4.22}$$

We can then follow this gradient downhill, taking small steps. See algorithm 4.1 for details.

Algorithm 4.1 An algorithm to minimise $$f(\mathbf{x}) = \dfrac{1}{2}||\mathbf{A} \mathbf{x} - \mathbf{b}||_2^2$$ with respect to $$\mathbf{x}$$ using gradient descent, starting form an arbitrary value of $$\mathbf{x}$$.

Set the step size ($$\epsilon$$) and tolerance ($$\delta$$) to small, positive numbers.

while $$||\mathbf{A}^T \mathbf{A} \mathbf{x} - \mathbf{A}^T \mathbf{b}||_2 > \delta$$ do

$$\ \ \ \mathbf{x} \leftarrow \mathbf{x} - \epsilon(\mathbf{A}^T \mathbf{A} \mathbf{x} - \mathbf{A}^T \mathbf{b})$$

end while

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.

I started doing research on Newton's method, and I came across this article, titled Newton's method for quadratic functions:

This page discusses how Newton's method fares as a root-finding algorithm for quadratic functions of one variable.

Please beware that this is not the same as using Newton's method for quadratic optimization. Applying Newton's method for optimization of a function of one variable to a quadratic function basically means applying Newton's method as a root-finding algorithm to the derivative of the quadratic function, which is a linear function. And Newton's method should converge in a single step for that function.

After all of this, I have the following questions:

1. What do the authors mean when they say that the "true function is quadratic"? What is "true function" supposed to mean?
2. That article confused me, since both instances of what it describes sounds like what the authors are describing in the textbook. Which one of these "Newton's methods'" is the one that is relevant to the algorithm in question?
3. What would the analogous Newton's method version of this algorithm be?

I would greatly appreciate it if people would please take the time to clarify these points.

• The "true function" they are referring to is $f(x) = (1/2) \| Ax-b\|^2$. They call it the "true function" because the basic idea behind Newton's method to minimize a function $f$ is to approximate $f$ locally by a quadratic function, then minimize the quadratic approximation to $f$, and then to repeat the previous two steps until convergence. If $f$ happens to be a quadratic function already, then our quadratic approximation to $f$ is just $f$ itself. – littleO Jan 15 '20 at 9:58
• @littleO I understand. Thank you for the clarification. – The Pointer Jan 15 '20 at 10:02

I would assume the 'true function' they are referring to is the $$L^2$$ norm, which they have defined to be $$f(\mathbf{x})$$.
The Newton method is just a root finding algorithm. I believe in the article you quoted, it is just distinguishing between the context of applying it to a function vs applying it to the derivative of a function. Since the Newton method is just a linear approximation of the original function, it will give the exact answer when applied to the derivative of a quadratic function. In fact if you click on the link given in the second article, the iterative formula they give is identical to the standard Newton method iteration, just applied to $$f'$$ rather than $$f$$.
To point 3, it is my understanding that there is only one Newton method, just used in different contexts. In this case since the goal is finding a minimum of your function, you would be doing root finding on $$f'$$ rather than on $$f$$.
• Thanks for the answer. With regards to 1., since $\dfrac{1}{2}||\mathbf{A} \mathbf{x} - \mathbf{b}||_2^2$ is squared, which is then eliminated by the square root, I was wondering how it could still be considered a quadratic, but then I realised that $f(\mathbf{x}) = \dfrac{1}{2}||\mathbf{A} \mathbf{x} - \mathbf{b}||_2^2 = \dfrac{1}{2} \left( \sqrt{(\mathbf{A} \mathbf{x} - \mathbf{b})^2} \right)^2 = \dfrac{1}{2} (\mathbf{A} \mathbf{x} - \mathbf{b})^2$ (it's still a quadratic), so that's my mistake. – The Pointer Jan 14 '20 at 21:07