Dlaczego moje kroki stają się coraz mniejsze, gdy używam ustalonego rozmiaru kroku podczas opadania gradientu?

Załóżmy, że robimy zabawkowy przykład na przyzwoitym gradiencie, minimalizując funkcję kwadratową , stosując ustalony rozmiar kroku . ( A = [10, 2; 2, 3] )$x^TAx$$\alpha=0.03$$A=[10, 2; 2, 3]$

Jeśli wykreślimy ślad $x$ w każdej iteracji, otrzymamy następujący rysunek. Dlaczego punkty stają się „gęste”, gdy używamy ustalonego rozmiaru kroku? Intuicyjnie nie wygląda jak stały rozmiar kroku, ale malejący rozmiar kroku.

---

Kod PS: R obejmuje działkę.

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

Niech gdzie jest symetryczne i dodatnio określone (myślę, że to założenie jest bezpieczne na podstawie twojego przykładu). Następnie i może diagonalize jako . Użyj zmiany podstawy . Następnie mamy $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$ jest ukośna, więc otrzymujemy nasze aktualizacje jako

$$y^{(n+1)} = y^{(n)} - \alpha \Lambda y^{(n)} = (I - \alpha \Lambda)y^{(n)} = (I - \alpha \Lambda)^{n+1}y^{(0)}.$$

Oznacza to, że zarządza konwergencją, a my uzyskujemy konwergencję tylko wtedy, gdy . W twoim przypadku mamy więc $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).$$

Względnie szybko uzyskujemy zbieżność w kierunku odpowiadającym wektorowi własnemu o wartości własnej co widać po tym, jak iteraty dość szybko schodzą z bardziej stromej części paraboloidu, ale zbieżność jest powolna w kierunku wektora własnego o mniejszej wartości własnej, ponieważ jest tak blisko . Więc nawet jeśli szybkość uczenia się jest stała, rzeczywiste wielkości kroków w tym kierunku zanikają zgodnie z około$\lambda \approx 10.5$$0.98$$1$$\alpha$$(0.98)^n$który staje się coraz wolniejszy. To jest przyczyną tego wykładniczo spowolnionego postępu w tym kierunku (dzieje się to w obu kierunkach, ale drugi kierunek zbliża się wystarczająco szybko, abyśmy nie zauważyli ani nie przejmowali się). W takim przypadku konwergencja byłaby znacznie szybsza, gdyby zwiększono .$\alpha$

Aby uzyskać znacznie lepszą i dokładniejszą dyskusję na ten temat, zdecydowanie polecam https://distill.pub/2017/momentum/ .

Dla płynnej funkcji $\nabla f=0$ według lokalnych minimów.

Ponieważ twój schemat aktualizacji to $\alpha \nabla f$, wielkość $|\nabla f|$kontroluje rozmiar kroku. W przypadku twojego kwadratu$|\Delta f|\rightarrow 0$również (po prostu oblicz hessian kwadratyki w twoim przypadku). Pamiętaj, że nie zawsze musi to być prawda. Na przykład wypróbuj ten sam schemat$f(x)=x$. Twój rozmiar kroku jest zawsze$\alpha$dlatego nigdy się nie zmniejszy. Lub, co ciekawsze,$f(x,y)=x+y^2$, gdzie gradient idzie do 0 we współrzędnej y, ale nie do $x$koordynować. Zobacz odpowiedź Chaconne na metodologię dla kwadratów.