Descenso de gradiente y sus variantes

Matemática · Lección 16

L3 From scratch Fase F1 Libro MML §7.1 Prereqs Convexidad · Hessiana y Taylor

Objetivo

Al terminar esta lección se puede:

  1. Definir el paso de descenso de gradiente y demostrar que con un paso suficientemente corto la función baja.
  2. Definir la suavidad de Lipschitz del gradiente y demostrar el lema de descenso, que convierte «baja» en una cantidad medible.
  3. Demostrar que en una cuadrática el error se contrae por el factor \max_i|1-\eta\lambda_i|, y deducir de ahí el paso óptimo, el paso límite y la tasa (\kappa-1)/(\kappa+1).
  4. Explicar por qué el número de condición —y no la dimensión— es lo que decide la velocidad, y qué le añade el momento.

De dónde viene

  • Matemática 15: la convexidad. El método encuentra un mínimo local, y la Proposición 15.5 es lo que lo convierte en la respuesta buscada.
  • Matemática 14: el desarrollo de Taylor. El lema de descenso es la cota cuadrática de ese desarrollo escrita con una constante global en lugar de una hessiana evaluada en un punto intermedio.
  • Matemática 13: la dirección de máximo descenso de la Proposición 13.9, que es exactamente la dirección que este método toma en cada paso.
  • Matemática 10 y 12: la diagonalización ortogonal y los eigenvalores, que aquí desacoplan el método en n recursiones independientes.

Para qué sirve después

  • Matemática 17: el método de Newton cambia el paso fijo \eta por la inversa de la hessiana, y con eso vuelve la tasa independiente del número de condición.
  • Matemática 18: el descenso proyectado y las condiciones KKT extienden todo esto a problemas con restricciones.
  • Estadística 8 y 16: la regresión logística y la calibración por isotónica no tienen solución cerrada, y se ajustan con este método o con una variante suya.

Notación

Símbolo Se lee Significado
\eta eta El paso, o tasa de aprendizaje
x_k equis sub ka El punto tras k iteraciones
e_k = x_k-x^\star error en el paso ka La distancia con signo al minimizador
L ele La constante de Lipschitz del gradiente
\lambda_1\ge\dots\ge\lambda_n lambdas Eigenvalores de la hessiana, todos positivos
\kappa=\lambda_1/\lambda_n kappa El número de condición
\rho(\eta) rho de eta El factor de contracción por iteración
\beta beta El coeficiente de momento

1. El paso, y por qué baja

Definición 16.1 (descenso de gradiente). Dado un punto inicial x_0 y un paso \eta>0, el descenso de gradiente genera la sucesión x_{k+1} = x_k - \eta\,\nabla f(x_k), \qquad k=0,1,2,\dots

Proposición 16.2 (el paso corto siempre baja). Si f es diferenciable en x_k y \nabla f(x_k)\ne0, existe \eta_0>0 tal que f\big(x_k-\eta\nabla f(x_k)\big) < f(x_k) \qquad\text{para todo } 0<\eta<\eta_0.

Demostración. Sea v=-\nabla f(x_k)/\|\nabla f(x_k)\|, unitario. Por la Proposición 13.9 aplicada al mínimo, D_vf(x_k) = \nabla f(x_k)\cdot v = -\|\nabla f(x_k)\| < 0. Por la Definición 13.6 ese número es el límite de [f(x_k+tv)-f(x_k)]/t cuando t\to0, así que existe t_0>0 tal que el cociente es negativo para todo 0<t<t_0; multiplicando por t>0, f(x_k+tv) < f(x_k) \qquad (0<t<t_0). Y x_k+tv = x_k-\eta\nabla f(x_k) con \eta = t/\|\nabla f(x_k)\|, de modo que basta tomar \eta_0 = t_0/\|\nabla f(x_k)\|. ∎

La Proposición 16.2 garantiza que existe un paso que sirve, pero no dice cuál ni cuánto baja. Para eso hace falta una hipótesis sobre cuánto puede cambiar el gradiente.

2. El lema de descenso

Definición 16.3 (gradiente Lipschitz). El gradiente de f es L-Lipschitz en un conjunto C si \|\nabla f(y)-\nabla f(x)\| \;\le\; L\,\|y-x\| \qquad\text{para todos } x,y\in C. Se dice entonces que f es L-suave. Para una cuadrática con hessiana A, la menor L que sirve es \lambda_1, el mayor eigenvalor.

Proposición 16.4 (lema de descenso). Si \nabla f es L-Lipschitz en un conjunto convexo C, entonces para todos x,y\in C f(y) \;\le\; f(x) + \nabla f(x)\cdot(y-x) + \frac{L}{2}\|y-x\|^2. En consecuencia, el paso de la Definición 16.1 con 0<\eta\le1/L cumple f(x_{k+1}) \;\le\; f(x_k) - \frac{\eta}{2}\,\|\nabla f(x_k)\|^2.

Demostración. Sea \phi(t)=f\big(x+t(y-x)\big), con \phi'(t)=\nabla f\big(x+t(y-x)\big)\cdot(y-x) por la regla de la cadena. Por el teorema fundamental del cálculo —que se da por conocido—, f(y)-f(x) = \phi(1)-\phi(0) = \int_0^1 \nabla f\big(x+t(y-x)\big)\cdot(y-x)\,dt. Restando \nabla f(x)\cdot(y-x)=\int_0^1\nabla f(x)\cdot(y-x)\,dt, f(y)-f(x)-\nabla f(x)\cdot(y-x) = \int_0^1 \big[\nabla f\big(x+t(y-x)\big)-\nabla f(x)\big]\cdot(y-x)\,dt. Acotando el integrando con Cauchy-Schwarz (Proposición 4.5) y después con la Definición 16.3, cuyo desplazamiento es t\|y-x\|, \big[\nabla f(x+t(y-x))-\nabla f(x)\big]\cdot(y-x) \;\le\; L\,t\,\|y-x\|\cdot\|y-x\| = L\,t\,\|y-x\|^2. Integrando esa cota entre 0 y 1 sale \tfrac{L}{2}\|y-x\|^2, que es el lema.

Para la consecuencia, tómese y=x_{k+1}=x_k-\eta\nabla f(x_k), de modo que y-x_k=-\eta\nabla f(x_k) y \|y-x_k\|^2=\eta^2\|\nabla f(x_k)\|^2. Sustituyendo, f(x_{k+1}) \le f(x_k) - \eta\|\nabla f(x_k)\|^2 + \frac{L\eta^2}{2}\|\nabla f(x_k)\|^2 = f(x_k) - \eta\Big(1-\frac{L\eta}{2}\Big)\|\nabla f(x_k)\|^2. Con \eta\le 1/L se tiene L\eta/2\le\tfrac12, luego 1-L\eta/2\ge\tfrac12 y el paréntesis se puede sustituir por \tfrac12 sin invalidar la desigualdad. ∎

La segunda parte es una garantía cuantitativa: cada paso baja al menos \tfrac{\eta}{2}\|\nabla f\|^2. Mientras el gradiente no sea pequeño, el progreso no se detiene.

La cota aguanta los 20 000 pares con L=\lambda_1 y falla en casi la mitad de ellos en cuanto se la rebaja a L/2: la Definición 16.3 no admite una constante más pequeña.

3. La cuadrática, donde todo se puede calcular

Proposición 16.5 (contracción exacta en el caso cuadrático). Sea f(x)=\tfrac12x^\top Ax-b^\top x con A simétrica definida positiva, x^\star=A^{-1}b y e_k=x_k-x^\star. Entonces

  1. e_{k+1}=(I-\eta A)\,e_k, y por tanto \|e_k\|\le\rho(\eta)^k\|e_0\| con \rho(\eta)=\max_i|1-\eta\lambda_i|;
  2. el método converge desde todo arranque si y solo si 0<\eta<2/\lambda_1;
  3. el mínimo de \rho se alcanza en \eta^\star=\dfrac{2}{\lambda_1+\lambda_n} y vale \rho(\eta^\star)=\dfrac{\kappa-1}{\kappa+1}, con \kappa=\lambda_1/\lambda_n.

Demostración. (1) Como \nabla f(x)=Ax-b=A(x-x^\star)=Ae, restando x^\star en la Definición 16.1, e_{k+1} = x_k-\eta Ae_k-x^\star = e_k-\eta Ae_k = (I-\eta A)e_k. Por el teorema espectral (Proposición 10.4) A=Q\Lambda Q^\top con Q ortogonal, así que I-\eta A = Q(I-\eta\Lambda)Q^\top. Escribiendo y_k=Q^\top e_k —que tiene la misma norma, porque Q es ortogonal— cada coordenada evoluciona por separado: y_{k+1,i} = (1-\eta\lambda_i)\,y_{k,i}, \qquad\text{de donde}\qquad y_{k,i}=(1-\eta\lambda_i)^k y_{0,i}. El método se parte en n recursiones de una sola variable, cada una con su propio factor. Tomando normas y acotando cada factor por el mayor sale \|e_k\|\le\rho(\eta)^k\|e_0\|.

(2) Si \rho(\eta)<1, la cota de (1) tiende a cero. Y si |1-\eta\lambda_j|\ge1 para algún j, basta arrancar con e_0=q_j para que esa coordenada no decrezca nunca. Luego la convergencia desde todo arranque equivale a |1-\eta\lambda_i|<1 para todo i, es decir a 0<\eta<2/\lambda_i para todo i; la más restrictiva es la del mayor eigenvalor, 0<\eta<2/\lambda_1.

(3) Como \eta\mapsto|1-\eta\lambda| es decreciente en \lambda mientras 1-\eta\lambda>0 y creciente después, el máximo sobre los \lambda_i lo alcanzan siempre los extremos: \rho(\eta)=\max\big\{|1-\eta\lambda_n|,\;|1-\eta\lambda_1|\big\}. En el rango útil la primera decrece con \eta y la segunda crece, así que el mínimo del máximo está donde se cruzan: 1-\eta\lambda_n = \eta\lambda_1-1 \quad\Longrightarrow\quad \eta^\star=\frac{2}{\lambda_1+\lambda_n}. Sustituyendo, \rho(\eta^\star) = 1-\frac{2\lambda_n}{\lambda_1+\lambda_n} = \frac{\lambda_1-\lambda_n}{\lambda_1+\lambda_n} = \frac{\kappa-1}{\kappa+1}. \;\;[\blacksquare]

El apartado (3) es el resultado que hay que recordar: la velocidad no depende de la dimensión ni de la escala global, solo del cociente entre el mayor y el menor eigenvalor. Con \kappa=100 la mejor tasa posible es 99/101\approx0{,}98, y hacen falta unos 230 pasos para ganar un solo dígito.

Las dos últimas columnas coinciden en las cuatro cifras, incluido el caso \eta=0{,}45 donde el factor pasa de uno y el método se aleja: la Proposición 16.5 da el factor exacto, no una cota holgada.

Al 99\,\% del límite todavía converge, aunque despacio; al 101\,\% ya se aleja, y al 120\,\% el error crece dieciséis órdenes de magnitud en 120 pasos. El umbral de la Proposición 16.5 es una frontera, no una recomendación.

4. Momento

El zigzag del visual tiene una causa concreta: en la dirección empinada el paso corrige de más y en la plana, de menos. El momento promedia la dirección con la del paso anterior, lo que cancela parte de la oscilación y acumula avance en la dirección que se repite.

Definición 16.6 (descenso con momento). Con x_{-1}=x_0 y un coeficiente \beta\in[0,1), x_{k+1} = x_k - \eta\,\nabla f(x_k) + \beta\,(x_k-x_{k-1}). Con \beta=0 se recupera la Definición 16.1.

Con el mismo paso óptimo, \beta=0{,}5 recorta los 125 pasos a 53. Pero \beta=0{,}8 sube a 155: el momento no es un parámetro que convenga subir sin mirar, y la elección buena depende de \kappa. Lo que la Definición 16.6 no arregla es el problema de fondo —que la tasa siga dependiendo del número de condición—, y eso es lo que ataca la lección 17 cambiando el paso escalar por una matriz.

Ejercicios

Ejercicio 1 — El paso que la teoría recomienda y el que va mejor

El lema de descenso pide \eta\le1/L, pero la Proposición 16.5 dice que el óptimo es 2/(\lambda_1+\lambda_n), que es mayor. Comprobar que los dos son válidos, medir cuántos pasos ahorra el segundo, y explicar por qué no se contradicen.

Ejercicio 2 — Qué le hace el número de condición

Generar matrices con número de condición controlado y comprobar que los pasos necesarios crecen como \kappa, no como la dimensión.

Reto

En proyectos/notebooks/F1-retos.ipynb, sección Mat 16:

  1. Implementar descenso(f, grad, x0, eta, pasos) con registro del camino, y añadirle búsqueda de línea: en cada iteración, probar \eta,\eta/2,\eta/4,\dots hasta que el lema de descenso de la Proposición 16.4 se cumpla con la constante medida. Comparar pasos totales y evaluaciones de f contra el paso fijo.
  2. Reproducir la tabla del Ejercicio 2 dibujando pasos frente a \kappa en escala log-log, y estimar la pendiente. Comprobar si sale 1, como predice (\kappa-1)/(\kappa+1) para \kappa grande.
  3. Implementar el momento de Nesterov —que evalúa el gradiente en el punto adelantado x_k+\beta(x_k-x_{k-1})— y comparar con la Definición 16.6 sobre el mismo problema mal condicionado. Anotar en 50-Errores/ con qué \beta cada uno empieza a oscilar.

Del libro

Mathematics for Machine Learning trata este material en §7.1 Optimization Using Gradient Descent, dentro del capítulo 7 sobre optimización continua. El libro tiene copyright y no es descargable desde el entorno en que se escribió esta página, así que se cita número y título y no se le atribuye ninguna frase.

Preguntas para leer §7.1 con lápiz:

  1. La sección presenta el descenso de gradiente con paso fijo y después con momento. Con la Proposición 16.5, ¿por qué el paso máximo admisible depende del mayor eigenvalor de la hessiana y no de su determinante ni de su traza?
  2. §7.1 menciona el descenso estocástico, donde el gradiente se estima con una parte de los datos. ¿Qué parte de la demostración de la Proposición 16.4 deja de valer cuando \nabla f(x_k) se sustituye por una estimación ruidosa, y por qué eso obliga a hacer decrecer \eta con k?
  3. El capítulo usa la palabra learning rate para \eta. Con el Ejercicio 1, ¿por qué la recomendación \eta\le1/L es segura pero conservadora, y qué información extra hace falta para poder subirla hasta 2/(\lambda_1+\lambda_n)?

Para el Cerebro

Nota nueva en 10-Conceptos/descenso-de-gradiente.md, enlazada a [[convexidad]], [[hessiana]] y [[numero-de-condicion]]. Conviene rehacer a mano la Proposición 16.5: la diagonalización parte el método en n recursiones de una variable, y de ahí sale todo lo demás —paso límite, paso óptimo y tasa— sin ninguna cuenta más.

¿Cuál es el paso del descenso de gradiente?::x_{k+1} = x_k − η∇f(x_k)
¿Por qué baja con η pequeño?::Porque −∇f es la dirección de máximo descenso y su derivada direccional es −‖∇f‖ < 0
¿Qué es un gradiente L-Lipschitz?::Uno que cumple ‖∇f(y)−∇f(x)‖ ≤ L‖y−x‖; para una cuadrática, L = λ₁
¿Qué dice el lema de descenso?::f(y) ≤ f(x) + ∇f(x)·(y−x) + (L/2)‖y−x‖²
¿Cuánto baja cada paso con η ≤ 1/L?::Al menos (η/2)‖∇f(x_k)‖²
¿Cómo evoluciona el error en una cuadrática?::e_{k+1} = (I−ηA)e_k, y cada coordenada propia se multiplica por (1−ηλᵢ)
¿Cuál es el factor de contracción?::ρ(η) = maxᵢ|1−ηλᵢ|
¿Cuál es el paso límite?::2/λ₁; por encima de ahí el método se aleja
¿Cuál es el paso óptimo?::2/(λ₁+λₙ)
¿Cuál es la mejor tasa posible?::(κ−1)/(κ+1), con κ = λ₁/λₙ
¿De qué depende la velocidad?::Del número de condición κ, no de la dimensión ni de la escala global
¿Qué hace el momento?::Suma β(x_k−x_{k−1}) al paso: cancela zigzag y acumula avance en la dirección repetida
¿Conviene subir β sin mirar?::No: con κ=20, β=0,5 recorta 125 pasos a 53, pero β=0,8 sube a 155

Fuentes

Lo que esta página demuestra sola. Las Proposiciones 16.2, 16.4 y 16.5 se demuestran aquí a partir de la dirección de máximo descenso de la lección 13, de Cauchy-Schwarz de la lección 4 y de la diagonalización ortogonal de la lección 10. Se comprueban además numéricamente: el lema de descenso en 20 000 pares con L=\lambda_1, y su rotura en 9424 de ellos al rebajar la constante a la mitad; el factor de contracción medido contra \max_i|1-\eta\lambda_i| para cinco pasos distintos, coincidiendo en las cuatro cifras, incluido el caso divergente; el umbral 2/\lambda_1 recorrido al 90, 99, 101 y 120 por ciento; el efecto del momento con cuatro valores de \beta; y el crecimiento de los pasos con \kappa a dimensión fija frente a su indiferencia a la dimensión con \kappa fijo. Los dos visuales se contrastaron antes de publicarse contra las fórmulas en todo el rango de sus controles.

Lo que se usa de otras lecciones sin repetir. La Proposición 13.9 —dirección de máximo descenso— y la Definición 13.6 de derivada direccional. La desigualdad de Cauchy-Schwarz es la Proposición 4.5. El teorema espectral y la escritura A=Q\Lambda Q^\top son la Proposición 10.4. Que un mínimo local de una función convexa es global es la Proposición 15.5, y es lo que da sentido a buscar con este método.

Lo que se enuncia sin demostrar. El teorema fundamental del cálculo, usado en la Proposición 16.4 para escribir f(y)-f(x) como integral de \phi'. La aceleración del momento se muestra midiendo pero no se demuestra: la tasa óptima del método con momento sobre una cuadrática es (\sqrt{\kappa}-1)/(\sqrt{\kappa}+1), y ese análisis queda fuera de esta lección. En la Definición 16.3 se afirma que para una cuadrática la menor constante válida es \lambda_1, que sale de \|A v\|\le\lambda_1\|v\| por el mismo argumento de la Proposición 12.4 y no se detalla.

Lo que viene de los libros.

  • Mathematics for Machine Learning (Deisenroth, Faisal & Ong, Cambridge University Press, 2020), §7.1 Optimization Using Gradient Descent — citada por número y título, sin transcribir texto.

Lo que es mío, no del libro. El orden que va de la garantía cualitativa (Proposición 16.2) a la cuantitativa (16.4) y de ahí al factor exacto (16.5), para que se vea qué añade cada hipótesis. El primer visual, que pone el paso en unidades del límite 2/\lambda_1 en lugar de en valor absoluto: así el mismo control sirve para cualquier \kappa y la frontera de divergencia queda siempre en el mismo sitio del deslizador. Y la honestidad del segundo visual y de la última celda sobre \beta=0{,}8, que empeora en lugar de mejorar.

Índices verificados el 12-09-2026 contra el índice publicado del PDF oficial.

→ Siguiente: Método de Newton