Descenso de gradiente · Calculus × Computing

¿Qué es?

Repetir $\theta \leftarrow \theta - \eta\,\nabla L(\theta)$ : dar un paso pequeño en contra del gradiente. Cauchy lo propuso en 1847; hoy (con sus variantes estocásticas y adaptativas) entrena prácticamente todas las redes neuronales.

¿Por qué existe?

Anular $\nabla L$ y despejar es imposible para una red con millones de parámetros y una pérdida no lineal. Pero evaluar $\nabla L$ en un punto es barato (retropropagación), y el gradiente dice en qué dirección baja más deprisa la pérdida. Se itera.

Intuición

Una bola que baja una ladera con niebla, paso a paso. El learning rate $\eta$ es la longitud del paso: demasiado pequeño y avanza a paso de tortuga; demasiado grande y se pasa, rebotando entre las paredes del valle o saliendo disparada. En un valle estrecho el gradiente apunta a través del valle y no a lo largo, así que el camino zigzaguea; prueba el cuenco alargado de la demo.

Definición formal

\theta_{k+1} = \theta_k - \eta\,\nabla L(\theta_k).

Si $\nabla L$ es $L$ -lipschitziano y $\eta \le 1/L$ , entonces $L(\theta_{k+1}) \le L(\theta_k) - \frac\eta2\norm{\nabla L(\theta_k)}^2$ (lema de descenso): la pérdida baja en cada paso y $\min_{j\le k}\norm{\nabla L(\theta_j)}^2 = O(1/k)$ . Si $L$ es $\mu$ -fuertemente convexa, la convergencia es lineal con razón $1 - \mu/L$ .

Fórmulas

$\theta_{k+1} = \theta_k - \eta\,\nabla L(\theta_k)$; $L(\theta - \eta g) \approx L(\theta) - \eta\,\norm{g}^2 \quad (g = \nabla L)$
por qué funciona: Taylor de primer orden

¿Cómo se calcula?

θ = valor inicial
para k en 1..K:
    g = ∇L(θ)          # retropropagación
    θ = θ − η · g
    si ‖g‖ < tol: parar

Visualización interactiva

f(x, y)optimizadorη

Pulsa en cualquier punto para soltar la bola ahí. El color es la altura (escala logarítmica) y las líneas son curvas de nivel; el gradiente es perpendicular a ellas. Prueba el valle estrecho con descenso de gradiente simple y después con momento.

¿Por qué importa?

Es el bucle interno de la industria de la IA: billones de pasos de gradiente al día. Todos los optimizadores usados en la práctica (SGD, momento, Adam) son modificaciones de esta línea.

Las matemáticas que hay detrás

Derivada★★★★★fundamental
Cada paso mueve el parámetro en contra de la derivada de la pérdida: $w \leftarrow w - \eta\,L'(w)$ .
Gradiente★★★★★fundamental
La actualización $\theta \leftarrow \theta - \eta\nabla L(\theta)$ es el gradiente usado como dirección.
Continuidad de Lipschitz★★★★★fundamental
El learning rate seguro lo fija la constante de Lipschitz del gradiente: $\eta < 2/L$ .
Convergencia de sucesiones★★★★★frecuente
Los teoremas de convergencia garantizan $f(x_k) \to f^\ast$ bajo condiciones sobre el tamaño de paso.
Puntos críticos y criterios de la derivada★★★★★fundamental
El descenso de gradiente se detiene donde se anula la derivada: en un punto crítico.
Orden y velocidad de convergencia★★★★★frecuente
En problemas fuertemente convexos el descenso de gradiente converge linealmente, a un ritmo fijado por el número de condición $L/\mu$ .
Polinomio de Taylor★★★★★fundamental
El modelo de primer orden $f(x - \eta g) \approx f(x) - \eta\norm g^2$ es la razón de que un paso pequeño cuesta abajo reduzca $f$ .
Derivada direccional★★★★★fundamental
Entre los pasos unitarios, $u = -\nabla f/\norm{\nabla f}$ minimiza $D_u f$ : la justificación del método.
Método de Euler★★★★★avanzada
El descenso de gradiente es Euler explícito sobre $\dot\theta = -\nabla L$ ; el learning rate es el paso de tiempo y hereda su límite de estabilidad.
Puntos de equilibrio y estabilidad★★★★★avanzada
Los mínimos estrictos son puntos fijos estables del descenso de gradiente exactamente cuando $\eta < 2/\lambda_{\max}(H)$ .
Sucesiones monótonas y acotadas★★★★★frecuente
Con un paso suficientemente pequeño la pérdida decrece de forma monótona y está acotada inferiormente, así que sus valores convergen.
Teorema del valor medio★★★★★avanzada
Las pruebas de convergencia acotan el descenso por paso aplicando el TVM al gradiente.

¿Dónde se utiliza?

Temas de informática a los que se llega desde aquí, con la cadena de ideas que lleva a ellos:

ℒ IA y machine learning

Learning rate (tasa de aprendizaje)★★★★★
Retropropagación (backpropagation)★★★★★
Descenso de gradiente estocástico (SGD)★★★★★
Paisaje de la pérdida (loss landscape)★★★★★
Aprendizaje por refuerzo★★★★★
Optimización de segundo orden (con hessiano)★★★★★
+5

⇄ Optimización y sistemas

Sistemas de recomendación★★★★★

Qué depende de él

Ejercicios

1IA

Para $L(\theta) = \frac a2\theta^2$ , demuestra que el descenso de gradiente converge si y solo si $0 < \eta < 2/a$ . ¿Qué pasa con $\eta = 1/a$ ?

Solución

$\theta_{k+1} = (1 - \eta a)\theta_k$ , que tiende a 0 si y solo si $|1 - \eta a| < 1$ . Con $\eta = 1/a$ salta al mínimo en un paso.