Descenso de gradiente · Definición
Convergencia con gradiente Lipschitz
Cuando el gradiente no cambia demasiado de un punto a otro, el descenso de gradiente avanza de forma predecible. Esta regularidad permite cuantificar cuánto se acerca el valor de la función al óptimo tras cada iteración.
Definición
Resultado que garantiza que el descenso de gradiente con paso adecuado converge en funciones diferenciables cuyo gradiente \( \nabla f \) es Lipschitz continuo con constante \( L \).
La condición de Lipschitz \( \|\nabla f(x)-\nabla f(y)\| \le L\|x-y\| \) implica el lema de descenso \( f(y)\le f(x)+\nabla f(x)^T(y-x)+\frac{L}{2}\|y-x\|^2 \). Si además \( f \) es convexa, con paso \( t=1/L \) el método cumple \( f(x_k)-f^*\le \frac{L\|x_0-x^*\|^2}{2k} \), es decir, una tasa \( O(1/k) \). Este resultado sigue el tratamiento de Nesterov.
Considérese \( f(x)=\frac{1}{2}x^2 \) en \( \mathbb{R} \), donde \( \nabla f(x)=x \) y \( L=1 \). Con \( t=1 \) y \( x_0=2 \), el primer paso da \( x_1=2-2=0 \), que es el óptimo exacto, así que la cota se cumple con holgura. Este ejemplo ilustra que el paso \( 1/L \) es una elección natural.
Un error típico es usar un paso mayor que \( 2/L \), lo que puede hacer que la sucesión oscile o diverja aunque la función sea convexa. Otro error es aplicar la cota \( O(1/k) \) sin verificar que \( \nabla f \) sea realmente Lipschitz con constante \( L \).
Para pensar
¿Por qué la condición de Lipschitz sobre el gradiente no basta por sí sola para garantizar que \( f(x_k) \) se acerque al mínimo global, y qué hipótesis adicional hace falta?
Sin convexidad, el descenso con gradiente Lipschitz solo garantiza que el gradiente tienda a cero, es decir, un punto estacionario, no el mínimo global. La cota \( O(1/k) \) sobre \( f(x_k)-f^* \) necesita además que \( f \) sea convexa.
Ejercicios 10
- ¿Qué significa que \( \nabla f \) sea Lipschitz con constante \( L \)?
- Si \( \nabla f \) es Lipschitz con constante \( L \), ¿qué paso de gradiente es la elección estándar?
- ¿Cuál es la tasa de convergencia en valor de la función para descenso de gradiente convexo con paso \( 1/L \)?
- ¿Qué desigualdad es consecuencia de la condición de Lipschitz sobre el gradiente?
- Si \( \nabla f \) es Lipschitz, ¿qué implica que \( f \) sea convexa para la sucesión de descenso?
- Una función tiene \( L=4 \). ¿Qué paso \( t \) es seguro usar según la regla \( t=1/L \)?
- Para \( f(x)=x^2 \) en \( \mathbb{R} \), ¿cuál es la constante de Lipschitz \( L \) del gradiente?
- Si \( \nabla f \) es Lipschitz con \( L=3 \) y \( \|x_0-x^*\|=2 \), ¿qué cota da la tasa \( O(1/k) \) para \( k=6 \)?
- Para \( f(x)=\frac{1}{2}x^2 \) con \( t=1/L \), ¿qué valor tiene \( x_1 \) si \( x_0=4 \)?
- Sea \( f(x)=2x^2 \) en \( \mathbb{R} \), con \( x_0=1 \) y paso \( t=1/L \). ¿Cuál es \( x_1 \)?
Referencias
- Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
- Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.