Algoritmo del método de Newton para mínimos cuadrados lineales

Question

Sección 4.5 Ejemplo: Mínimos cuadrados lineales del libro de texto Aprendizaje profundo de Goodfellow, Bengio y Courville, dice lo siguiente:

Supongamos que queremos encontrar el valor de $\mathbf{x}$ que minimiza

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

Los algoritmos especializados de álgebra lineal pueden resolver este problema de forma eficiente; sin embargo, también podemos explorar cómo resolverlo utilizando la optimización basada en el gradiente como ejemplo sencillo de cómo funcionan estas técnicas.

En primer lugar, debemos obtener el gradiente:

$$\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}$$

A continuación, podemos seguir este gradiente cuesta abajo, dando pequeños pasos. Véase el algoritmo 4.1 para más detalles.

---

Algoritmo 4.1 Un algoritmo para minimizar $f(\mathbf{x}) = \dfrac{1}{2}||\mathbf{A} \mathbf{x} - \mathbf{b}||_2^2$ con respecto a $\mathbf{x}$ mediante descenso gradiente, partiendo de un valor arbitrario de $\mathbf{x}$ .

---

Ajuste el tamaño del paso ( $\epsilon$ ) y la tolerancia ( $\delta$ ) a números pequeños y positivos.

mientras que $||\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})$

fin mientras

---

También se puede resolver este problema utilizando el método de Newton. En este caso, como la función verdadera es cuadrática, la aproximación cuadrática empleada por el método de Newton es exacta, y el algoritmo converge al mínimo global en un solo paso.

Empecé a investigar sobre el método de Newton, y me encontré con este artículo, titulado Método de Newton para funciones cuadráticas :

Esta página analiza cómo funciona el método de Newton como algoritmo de búsqueda de raíces para funciones cuadráticas de una variable.

Tenga en cuenta que no es lo mismo que utilizar el método de Newton para la cuadrática optimización . Aplicar el método de Newton para la optimización de una función de una variable a una función cuadrática significa básicamente aplicar el método de Newton como algoritmo de búsqueda de raíces a la derivada de la función cuadrática, que es una función lineal. Y el método de Newton debería converger en un solo paso para esa función.

Después de todo esto, me surgen las siguientes preguntas:

1. ¿Qué quieren decir los autores cuando afirman que la "verdadera función es cuadrática"? ¿Qué significa "función verdadera"?
2. Ese artículo me confundió, ya que ambos casos de lo que describe suena como lo que los autores están describiendo en el libro de texto. ¿Cuál de estos "métodos de Newton" es el relevante para el algoritmo en cuestión?
3. ¿Cuál sería la versión análoga del método de Newton de este algoritmo?

Agradecería enormemente que la gente se tomara la molestia de aclarar estos puntos.

Answer 1

Supongo que la "verdadera función" a la que se refieren es la $L^2$ que han definido como $f(\mathbf{x})$ .

El método Newton no es más que un algoritmo de búsqueda de raíces. Creo que en el artículo que has citado, sólo se distingue entre el contexto de aplicarlo a una función frente a aplicarlo a la derivada de una función. Dado que el método de Newton es sólo una aproximación lineal de la función original, dará la respuesta exacta cuando se aplica a la derivada de una función cuadrática. De hecho, si haces clic en el enlace que aparece en el segundo artículo, la fórmula iterativa que dan es idéntica a la iteración estándar del método Newton, sólo que aplicada a $f'$ en lugar de $f$ .

En cuanto al punto 3, tengo entendido que sólo existe un método Newton, sólo que se utiliza en contextos diferentes. En este caso, ya que el objetivo es encontrar un mínimo de su función, que estaría haciendo la búsqueda de raíces en $f'$ en lugar de en $f$ .