El descenso de gradiente

Bajar la pendiente

El descenso de gradiente repite un único movimiento: avanzar contra el gradiente, $\mathbf w_{k+1}=\mathbf w_k-\eta\,\nabla f(\mathbf w_k)$ . El número $\eta>0$ es el paso, a menudo llamado tasa de aprendizaje. Un $\eta$ pequeño es seguro pero lento. Un $\eta$ grande se pasa del valle y las iteraciones pueden alejarse cada vez más.

f(w)=\tfrac12 a\,w^{2}\ \Rightarrow\ w_{k+1}=(1-\eta a)\,w_k,\qquad |1-\eta a|<1\iff 0<\eta<\frac{2}{a}

(1)

En el cuenco más simple la actualización multiplica $w$ por $1-\eta a$ cada vez, así que las iteraciones tienden a cero justo cuando $|1-\eta a|<1$ , es decir $\eta<2/a$ . La elección $\eta=1/a$ cae en el mínimo en un paso, y cualquier $\eta$ entre $1/a$ y $2/a$ aún converge pero cambia de signo por el camino. Más allá de $2/a$ el factor supera uno en valor absoluto y las iteraciones explotan.

Tres pasos sobre f = 3x²Aquí

f'(x)=6x

, así que

a=6

. Partimos de

x_0=4

con

\eta=0.1

: el factor es

1-0.6=0.4

, de modo que

x_1=1.6

x_2=0.64

x_3=0.256

. El límite de estabilidad es

2/6=0.333

. Con

\eta=0.5

el factor es

1-3=-2

, las iteraciones son

4,-4,8,\dots

y duplican su tamaño en cada paso.

En varias variables la curvatura cambia según la dirección. El mayor valor propio $L$ del hessiano limita el paso utilizable ( $\eta<2/L$ ) y el menor $\mu$ fija lo lento que es cruzar la dirección más plana. Su cociente $\kappa=L/\mu$ es el número de condición. Con el mejor paso fijo $\eta=2/(L+\mu)$ el error se multiplica por unos $(\kappa-1)/(\kappa+1)$ en cada paso, así que un $\kappa$ grande da un factor cercano a uno y un zigzag lento por un valle largo y estrecho. Para la matriz de covarianza de doce grandes acciones de EE. UU. desde 2010, $\kappa$ es de unos $33$ : el factor es $0.941$ y reducir el error cien veces requiere unos 76 pasos.

\eta^{*}=\frac{2}{L+\mu},\qquad \lVert\mathbf w_k-\mathbf w^{*}\rVert\ \lesssim\ \Big(\frac{\kappa-1}{\kappa+1}\Big)^{k}\lVert\mathbf w_0-\mathbf w^{*}\rVert,\qquad \kappa=\frac{L}{\mu}

(2)

Paso seguro: $\eta<2/L$ , con $L$ el mayor valor propio del hessiano; si no, las iteraciones divergen.
Velocidad: la fija el número de condición $\kappa=L/\mu$ ; cuanto mayor, más lento el descenso.
Parada: detener cuando $\lVert\nabla f\rVert$ baje de una tolerancia, con un tope de iteraciones.

Escale las variablesUn número de condición grande suele venir de variables con escalas muy distintas, por ejemplo un peso entre 0 y 1 junto a una volatilidad en puntos básicos. Reescalar cada variable a un tamaño parecido reduce

\kappa

y puede convertir miles de iteraciones en decenas. El precondicionamiento es la forma general de la misma idea.

Lab: qué se califica

El primer paso15 pts
El segundo paso10 pts
El mayor paso estable15 pts
Un paso demasiado grande15 pts
Un número de condición15 pts
El mejor factor de contracción15 pts
Por qué el mal condicionamiento es lento15 pts

Bajar la pendiente

f(w)=\tfrac12 a\,w^{2}\ \Rightarrow\ w_{k+1}=(1-\eta a)\,w_k,\qquad |1-\eta a|<1\iff 0<\eta<\frac{2}{a}

(1)

Tres pasos sobre f = 3x²Aquí

f'(x)=6x

, así que

a=6

. Partimos de

x_0=4

con

\eta=0.1

: el factor es

1-0.6=0.4

, de modo que

x_1=1.6

x_2=0.64

x_3=0.256

. El límite de estabilidad es

2/6=0.333

. Con

\eta=0.5

el factor es

1-3=-2

, las iteraciones son

4,-4,8,\dots

y duplican su tamaño en cada paso.

\eta^{*}=\frac{2}{L+\mu},\qquad \lVert\mathbf w_k-\mathbf w^{*}\rVert\ \lesssim\ \Big(\frac{\kappa-1}{\kappa+1}\Big)^{k}\lVert\mathbf w_0-\mathbf w^{*}\rVert,\qquad \kappa=\frac{L}{\mu}

(2)

Paso seguro: $\eta<2/L$ , con $L$ el mayor valor propio del hessiano; si no, las iteraciones divergen.
Velocidad: la fija el número de condición $\kappa=L/\mu$ ; cuanto mayor, más lento el descenso.
Parada: detener cuando $\lVert\nabla f\rVert$ baje de una tolerancia, con un tope de iteraciones.

\kappa

y puede convertir miles de iteraciones en decenas. El precondicionamiento es la forma general de la misma idea.

Lab: qué se califica

El primer paso15 pts
El segundo paso10 pts
El mayor paso estable15 pts
Un paso demasiado grande15 pts
Un número de condición15 pts
El mejor factor de contracción15 pts
Por qué el mal condicionamiento es lento15 pts

Bajar la pendiente

Lab: qué se califica

Inicia sesión para ejecutar tu código.

El descenso de gradiente

Bajar la pendiente

Lab: qué se califica

Inicia sesión para ejecutar tu código.