¿Por qué se fijan mis pasos cada vez más pequeñas cuando se usa el tamaño de paso en pendiente gradiente?

Question

Supongamos que estamos haciendo un juguete ejemplo en gradiente decente, la minimización de una función cuadrática $x^TAx$, fija el tamaño de paso de $\alpha=0.03$. ($A=[10, 2; 2, 3]$)

Si graficamos la traza de $x$ en cada iteración, se obtiene la siguiente figura. ¿Por qué los puntos de "mucho densa" cuando utilizamos fija tamaño de paso? Intuitivamente, no se ve como un paso fijo tamaño, pero una disminución en el tamaño del paso.

---

PS: R Código de incluir en la trama.

A=rbind(c(10,2),c(2,3))
f <-function(x){
  v=t(x) %*% A %*% x
  as.numeric(v)
}
gr <-function(x){
  v = 2* A %*% x
  as.numeric(v)
}

x1=seq(-2,2,0.02)
x2=seq(-2,2,0.02)
df=expand.grid(x1=x1,x2=x2)
contour(x1,x2,matrix(apply(df, 1, f),ncol=sqrt(nrow(df))), labcex = 1.5, 
        levels=c(1,3,5,10,20,40))
grid()

opt_v=0
alpha=3e-2
x_trace=c(-2,-2)
x=c(-2,-2)
while(abs(f(x)-opt_v)>1e-6){
  x=x-alpha*gr(x)
  x_trace=rbind(x_trace,x)
}
points(x_trace, type='b', pch= ".", lwd=3, col="red")
text(x_trace, as.character(1:nrow(x_trace)), col="red")

Answer 1

Deje $f(x) = \frac 12 x^T A x$ donde $A$ es simétrica y definida positiva (creo que esta suposición es seguro basado en el ejemplo). A continuación, $\nabla f(x) = Ax$ y podemos diagonalize $A$$A = Q\Lambda Q^T$. Utilizar el cambio de base de a $y =Q^T x$. Entonces tenemos $$ f(y) = \frac 12 y^T \Lambda y \implica \nabla f(y) = \Lambda y. $$

$\Lambda$ es diagonal para que nos recibe nuestras actualizaciones como $$ y^{(n+1)} = y^{(n)} - \alpha \Lambda y^{(n)} = (I - \alpha \Lambda)y^{(n)} = (I - \alpha \Lambda)^{n+1}y^{(0)}. $$

Esto significa que $1 - \alpha \lambda_i$ rigen la convergencia, y que sólo se consigue la convergencia si $|1 - \alpha \lambda_i| < 1$. En su caso le han $$ \Lambda \approx \left(\begin{array}{cc} 10.5 & 0 \\ 0 & 2.5\end{array}\right) $$ así $$ I - \alpha \Lambda \approx \left(\begin{array}{cc} 0.89 & 0 \\ 0 & 0.98\end{array}\right). $$

Tenemos convergencia relativamente rápido en la dirección correspondiente al vector propio con autovalor $\lambda \approx 10.5$ como se ve por la forma de las recorre en descenso por la pendiente más pronunciada de la parte del paraboloide con bastante rapidez, pero la convergencia es lenta en la dirección del vector propio con el menor autovalor porque $0.98$ está tan cerca de $1$. Así que, aunque la tasa de aprendizaje $\alpha$ es fijo, el real de las magnitudes de los pasos en esta dirección, la decadencia de acuerdo a aproximadamente $(0.98)^n$ que se vuelve más lento y más lento. Que es la causa de que la exponencial de aspecto desaceleración en el progreso en esta dirección (esto ocurre en ambas direcciones, pero la otra dirección se acerca el tiempo suficiente que no notamos o de atención). En este caso la convergencia sería mucho más rápido si $\alpha$ fue en aumento.

Para una mejor y más completa discusión de este, lo recomiendo encarecidamente https://distill.pub/2017/momentum/.

Answer 2

Para una función suave, $\nabla f=0$ a de los mínimos locales.

Debido a su actualización de esquema es $\alpha \nabla f$, la magnitud $|\nabla f|$ controla el tamaño del paso. En el caso de su cuadrática $|\Delta f|\rightarrow 0$ (sólo calcular la hessiana de la cuadrática en su caso). Tenga en cuenta que esto no siempre tiene que ser verdad. Por ejemplo, pruebe el mismo esquema en $f(x)=x$. A continuación, su tamaño de paso es siempre $\alpha$ por lo tanto nunca va a disminuir. O más interesante, $f(x,y)=x+y^2$, donde la pendiente se va a 0 en el eje de coordenadas, pero no la $x$ coordinar. Ver Chacona de la respuesta de la metodología para cuadráticas.