Deep dive into optimization : Momentum (1) - Updated

 

"모바일 앱 환경에서는 latex이 깨져서 나타나므로, 가급적 웹으로 봐주시길 바랍니다."

 

https://kyteris0624.tistory.com/24

Deep dive into optimization: Gradient descent (3)

지난 포스팅에서는 GD와 SGD의 convergence analysis / convergence rate을 살펴보았다.

이때 SGD는 GD와 달리 학습속도가 떨어짐을 알 수 있는데, $O(\frac{1}{T}), O(\frac{1}{\sqrt{T}})$,

이는 SGD의 stochasticity로 인해 true gradient와의 차이, 즉 noise가 존재하고 이를 완화하기 위해서는 constant step-size가 아닌 diminishing step-size로 학습을 진행해야 하기 때문에 생기는 현상이었다.

이를 보완하기 위해 SGD에서 변형된 많은 학습 알고리즘들이 등장하였는데, 크게 두 가지 부류로 나눠볼 수 있다.

첫 번째는 현재 iteration에서 파라미터 업데이트 방향을 보완하는 것,
두 번째는 learning-rate를 모든 파라미터에 동일한 값을 적용하는 것이 아니라, 각 파라미터 별로 다른 값을 적용하는 것, 즉 adaptive learning-rate를 적용하는 것이다.

 

이번 글에서는 파라미터가 이동하는 방향인 gradient의 방향을 SGD에서 다르게 변형한 것에 대해 살펴보자. 

대표적인 방식이 Momentum이다. mometum을 적용한 알고리즘에서도 다양한 알고리즘이 존재하는데 이 포스팅 시리즈에서는 가장 기본적인 알고리즘인 Heavy-ball과 Nesterov momentum 두 가지를 살펴볼 것이다.

 

 Momentum을 본격적으로 이야기하기 전에 먼저 특수한 평균에 대해 이야기하고 넘어가자.

 

현재 iteration을 $t$라 하였을 때, 그때의 stochastic gradient를 $g_t$라 하자.

파라미터 $w \in \mathbb{R}^n$를 갖는 Loss function $f : \mathbb{R}^n \rightarrow \mathbb{R}$의 stochastic gradient $g_t := \nabla f(w_t ; \psi_t)$이며, Deterministic gradient의 unbiased estimator라고 하자.

그렇다면 $g_t$의 방향을 보완하는 가장 쉬운 방법은 무엇일까? 바로 이전 gradient들을 사용하는 것이다.

즉, $w_{t+1} = w_t - \eta_t g_t$가 아닌, $w_{t+1} = w_t - \frac{1}{t} \eta_t \frac{1}{t} \sum_{i=1}^t g_i$를 사용하는 것이다.

하지만, 이렇게 되면 현재 파라미터에서의 gradient가 이전 gradient의 방향에 의해 많이 상쇄되기 때문에 또 다른 문제들이 생길 수 있다. 그렇다면 최근 gradient에 더 큰 가중치를 부여하고, 과거의 gradient들에는 상대적으로 작은 가중치를 부여하는 방법은 없을까?

그것이 바로 moving average이다.

$v_t= \beta v_{t-1} + g_t$로 현재 파라미터를 업데이트하면 어떻게 될까?

 

 

 

$\beta$가 0과 1 사이의 상수 일 때, 즉, $\beta \in (0,1)$일 때, 과거의 gradient에는 지수적으로 가중치가 작아지고, 현재의 gradient에는 상대적으로 큰 가중치가 부여되기 때문에 과거 정보 (history)를 반영하면서 동시에 현 gradient의 방향과 큰 차이를 만들지는 않을 수 있다.

 

$v_t$를 이용해서 parameter를 업데이트하면, 여러 상황에서 accelration 효과가 발생하고 그로 인해 학습 속도가 빨라진다. 그리고 실제로 현재 딥러닝에서 momentum은 Default로 쓰이는 학습 알고리즘이며 결과도 상당히 잘 나오고 있다.

가장 대표적인 예시로 ill-condition problem에서 momentum의 가속 효과가 상당히 잘 나타나는데 예시를 통해 살펴보자.

위 함수를 살펴보자. 

$w_1, w_2$를 파라미터로 갖는 loss function이고 minimum은 $(0,0)$이다.

이 함수에 대해 gradient descent를 적용하면 어떻게 될까?

 

$w_1$보다 $w_2$방향에서 gradient는 크기가 매우 크고, 그렇기 때문에 더 급격하게 방향이 바뀐다.

(위 함수를 편미분해보면 쉽게 알 수 있다.)

gradient도 vector이기 때문에 파라미터는 $w_1$방향의 gradient 성분과 $w_2$방향의 gradient 성분이 합쳐진 방향으로 이동하는데, 한 성분이 다른 성분에 비해 크기가 크기 때문에 위 아래로 크게 진동하는 것과 같은 모습을 보이는 것이다.

이는 loss function 자체의 성질 때문에 발생하는 현상인데 이를 ill-condition 이라고 한다.
여기에 만약 momentum을 적용하면 어떻게 될까?

결과를 보기 전에 먼저 추측해보자.

momentum이란 결국 과거 gradient의 history를 현재 업데이트에 반영하는 것이라 하였다.

$w_1$의 gradient 방향은 일관되기 때문에 (계속 오른쪽으로 이동함) 점점 가속이 붙을 것이고, 

$w_2$의 gradient 방향은 변동폭이 크기 때문에 (위 아래로 이동함) 평균을 내면 변동폭이 상쇄될 것이다.

즉, oscilliation (진동)의 정도가 완화될 것이다.

위에서 $\beta$를 0.5로 하였을 때 결과는 다음과 같다.

동일한 epoch만큼 돌렸을 때 optimal point, 즉 $(0,0)$에 더 가깝게 이동했음을 알 수 있고, 진동이 완화되면서 accelerated효과가 발생했음을 알 수 있다.

 

이것이 momentum의 가장 큰 장점이다. 결국 ill-conditioned problem에서 zigzagging / oscilliation 현상이 완화되는 것이다.

 

momentum을 수식적으로 표현하는 여러 방법이 있는데 이것들에 대해 알아보자.

가장 흔한 표기법은 다음과 같다.

위 수식을 조금 정리하면 아래와 같이 바꿔 표현할 수도 있다.

이를 heavy-ball momentum이라고도 한다.

 

또 다른 momentum 표현법으로는 iterate-moving-average라고도 불리는 방법이 있는데 이는 momentum을 이론적으로 분석하기에 편리하다는 장점이 있다. 

앞서 heavy-ball에서의 파라미터 $\beta, \gamma$가 위 iterate-moving-average에서의 파라미터 $\lambda, \eta$ 사이의 모종의 관계식들이 성립하면 위 3가지 momentum에서의 iteration 결과, 즉 ${w_t}$는 항상 같다. 

마지막으로 convex, smooth 상황에서의 momentum의 convergence rate을 살펴보고 마치도록 하겠다.

 

<Theorem>

$f(w) := \frac{1}{n} \sum_{i=1}^n f_i(w)$이고 각각의 $f_i(w)$가 convex하며 smooth하다고 하자.

그리고 $\eta \le \frac{1}{4L_{max}}$이며, $\beta_t = \frac{t}{t+2}, \gamma_t = \frac{2 \eta}{t+3}$이라 하자.

그러면 다음이 성립한다.

 

$\sigma^*$ 정의는 이전 포스팅 글을 참조하길 바란다.

위 Theorem의 유도는 iterate-moving-average 방식의 momentum의 convergence analysis를 통해서 나온 결과인데, 결국 Optimality gap의 (Upper) bound가 $(f(w_t) - \inf f)$ $O(\frac{1}{t})$임을 알 수 있다.

 

이론적으로 SGD와 동일한 상황, 즉 convex and smooth 상황에서 중요한 차이가 하나 존재하는데 convergence rate이 $O(\frac{1}{\sqrt{t}})$에서 $O(\frac{1}{t})$로 빨라짐과 동시에 SGD에서는 $\mathbb{E}[f(\bar{w}_t) - \inf f]$ 꼴이었다면 위에서는 $\mathbb{E}[f(w_t) - \inf f]$이다.

즉, SGD에서는 average of the iterates (정확히는 Polyak-Ruppert averaging) 에 대한 결과만 알 수 있는 반면 momentum에서는 현재 iterate에서의 upper bound를 유도한 것이다.

 

다음 포스팅에서는 Nesterov momentum에 대해 이야기하고 momentum을 마무리짓도록 하겠다.