Por que minhas etapas estão diminuindo ao usar tamanho fixo de etapa em descida de gradiente?

Suponha que estejamos fazendo um exemplo de brinquedo decente em gradiente, minimizando uma função quadrática , usando tamanho de passo fixo . ( )α = 0,03 A = [ 10 , 2 ; 2 , 3 $x^TAx$$\alpha=0.03$$A=[10, 2; 2, 3]$

Se traçarmos o traço de $x$ em cada iteração, obteremos a figura a seguir. Por que os pontos ficam "muito densos" quando usamos tamanho de passo fixo ? Intuitivamente, ele não se parece com um tamanho de etapa fixo, mas com um tamanho de etapa decrescente.

---

Código PS: R inclui 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")

Seja onde é simétrico e positivo definido (acho que essa suposição é segura com base no seu exemplo). Em seguida, e podemos diagonalizar como . Use a mudança de base . Então temos A∇f(x)=AxAA=QΛQTy=QTxf(y)=$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$ é diagonal, portanto, recebemos nossas atualizações como

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

Isso significa que governa a convergência e só obtemos convergência se . No seu caso, temos então | 1 - α λ i | < 1 Ganhe muitos ≈ ( 10,5 0 0 2,5 ) I - ct Ganhe muitos ≈ ( 0,89 0 0 0,98 )$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).$$

Obtemos convergência relativamente rapidamente na direção correspondente ao vetor próprio com autovalor como visto pelas iterações descendo rapidamente a parte mais íngreme do parabolóide, mas a convergência é lenta na direção do vetor próprio com o autovalor menor porque é tão próximo de . Portanto, mesmo que a taxa de aprendizado seja fixa, as magnitudes reais dos passos nessa direção decaem de acordo com aproximadamente0,98 1 α ( 0,98 ) n$\lambda \approx 10.5$$0.98$$1$$\alpha$$(0.98)^n$que se torna cada vez mais lento. Essa é a causa dessa desaceleração de aparência exponencial no progresso nessa direção (acontece nas duas direções, mas a outra direção chega perto o suficiente o suficiente para que não notemos nem nos importemos). Nesse caso, a convergência seria muito mais rápida se fosse aumentado.$\alpha$

Para uma discussão muito melhor e mais aprofundada disso, recomendo fortemente https://distill.pub/2017/momentum/ .

Para uma função suave, nos mínimos locais.$\nabla f=0$

Como o seu esquema de atualização é , a magnitudecontrola o tamanho da etapa. No caso do seu quadrático também (apenas calcule o hessian do quadrático no seu caso). Observe que isso nem sempre precisa ser verdade. Por exemplo, tente o mesmo esquema em . Então o tamanho do seu passo é sempre portanto, nunca diminui. Ou, mais interessante, , em que o gradiente vai para 0 na coordenada y, mas não na coordenada . Veja a resposta de Chaconne para a metodologia quadrática.| ∇ f | | Δ 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$