Почему мои шаги становятся меньше при использовании фиксированного размера шага при градиентном спуске?

9

Предположим, что мы делаем игрушечный пример с градиентом приличия, минимизируя квадратичную функцию , используя фиксированный размер шага α = 0,03 . ( A = [ 10 , 2 ; 2 , 3 ] )xTAxα=0.03A=[10,2;2,3]

Если мы построим трассировку на каждой итерации, мы получим следующий рисунок. Почему точки становятся «намного плотнее», когда мы используем фиксированный размер шага? Интуитивно понятно, что это выглядит не как фиксированный размер шага, а как уменьшающийся размер шага.x

введите описание изображения здесь


PS: код R включает сюжет.

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")
Хайтау Ду
источник
alpha=3e-20.01

Ответы:

12

f(x)=12xTAxAf(x)=AxAA=QΛQTy=QTx

f(y)=12yTΛyf(y)=Λy.

Λ

y(n+1)=y(n)αΛy(n)=(IαΛ)y(n)=(IαΛ)n+1y(0).

1αλi|1αλi|<1

Λ(10.5002.5)
IαΛ(0.89000.98).

λ10.50.981α(0.98)nα

Для лучшего и более подробного обсуждения этого я настоятельно рекомендую https://distill.pub/2017/momentum/ .

JLD
источник
y
11

f=0

αf|f||Δf|0f(x)=xαf(x,y)=x+y2x

Алекс Р.
источник