¿Por qué mis pasos se hacen más pequeños cuando uso un tamaño de paso fijo en descenso de gradiente?

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

Si trazamos el rastro de en cada iteración, obtenemos la siguiente figura. ¿Por qué los puntos se vuelven "mucho más densos" cuando usamos un tamaño de paso fijo ? Intuitivamente, no parece un tamaño de paso fijo, sino un tamaño de paso decreciente.$x$

---

PD: R Code incluye plot.

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")

Deje donde es simétrico y positivo definido (creo que esta suposición es segura según su ejemplo). Entonces y podemos diagonalizar como . Use el cambio de base . Entonces tenemos $f(x) = \frac 12 x^T A x$$A$$\nabla f(x) = Ax$$A$$A = Q\Lambda Q^T$$y =Q^T x$

$$f(y) = \frac 12 y^T \Lambda y \implies \nabla f(y) = \Lambda y.$$

$\Lambda$ es diagonal, por lo que obtenemos 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 gobierna la convergencia, y solo obtenemos convergencia si . En su caso, tenemos entonces $1 - \alpha \lambda_i$$|1 - \alpha \lambda_i| < 1$

$$\Lambda \approx \left(\begin{array}{cc} 10.5 & 0 \\ 0 & 2.5\end{array}\right)$$ $$I - \alpha \Lambda \approx \left(\begin{array}{cc} 0.89 & 0 \\ 0 & 0.98\end{array}\right).$$

Obtenemos una convergencia relativamente rápida en la dirección correspondiente al vector propio con valor propio como se ve por cómo los iterados descienden la parte más empinada del paraboloide bastante rápido, pero la convergencia es lenta en la dirección del vector propio con el valor propio más pequeño porque está tan cerca de . Entonces, aunque la tasa de aprendizaje es fija, las magnitudes reales de los pasos en esta dirección decaen de acuerdo con aproximadamente$\lambda \approx 10.5$$0.98$$1$$\alpha$$(0.98)^n$que se vuelve más y más lento Esa es la causa de esa desaceleración de aspecto exponencial en el progreso en esta dirección (sucede en ambas direcciones, pero la otra dirección se acerca lo suficientemente pronto como para que no nos demos cuenta o no nos importe). En este caso, la convergencia sería mucho más rápida si se incrementara .$\alpha$

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

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

Debido a que su esquema de actualización es , la magnitudcontrola el tamaño del paso. En el caso de su cuadrática también (solo calcule la arpillera de la cuadrática en su caso). Tenga en cuenta que esto no siempre tiene que ser cierto. Por ejemplo, intente el mismo esquema en . Entonces el tamaño de su paso es siempre por lo tanto, nunca disminuirá. O, lo que es más interesante, , donde el gradiente va a 0 en la coordenada y, pero no en la coordenada . Vea la respuesta de Chaconne para la metodología para las cuadráticas.| ∇ f | El | Δ f | → 0 f ( x ) = x α f ( x , y ) = x + y 2$\alpha \nabla f$$|\nabla f|$$|\Delta f|\rightarrow 0$$f(x)=x$$\alpha$$f(x,y)=x+y^2$$x$