Deep dive into optimization : Adam - Updated

 

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

 

오늘은 ADAM에 대해 조금 더 자세하게 이야기해보고자 한다.

ADAM은 현재까지도 가장 많이 쓰이는 optimizer 중 하나이며, 아직 이론적으로 연구가 계속해서 진행되고 있고, Adam을 약간 변형한 알고리즘들도 계속해서 논문이 나오고 있다.

 

우선, Adam 알고리즘을 다시 한 번 살펴보자.

Kingma and Lei Ba, "ADAM : A method for stochastic optimization" (ICLR 2015)

 

오늘은 Adam을 소개한 논문, "Adam : A method for stochastic optimization" (ICLR 2015) 논문에 제시된 Adam의 convergence analysis를 이야기하고자 한다. 본 convergence analysis가 나온 이후, 여러 번의 수정 작업이 있었고, 실제로 Adam이 발산하는 경우, non-convex 상황에서의 convergence analysis 등에 대한 논문이 계속해서 나오고 있다.

최적화를 연구해보고자 하는 사람이라면 아래 논문은 추후 반드시 읽어보기 바란다.

"Reddi, S.G et al. "On the convergence of adam and beyond", ICLR 2018"

이 논문은 Adam이 발산할 수 있는 경우에 대해서 분석한 논문으로서 상당히 유명한 논문이다.

하지만, optimization 초심자가 읽기에는 좀 어려울 수 있다.

 

어쨌든, 본 포스팅은 convex optimization 기본들에 대해 설명하는 것이 주 목적이므로 Adam의 원래 논문에서 이야기한 convergence analysis에 대해서만 이야기를 진행하겠다.

 

먼저 간단한 용어 하나 정하자. 

(Online learning) Regret

 

원 논문에서는 online learning 상황을 가정하고 있다.

위에서 $f_t(\theta)$는 convex cost function을 의미한다. 우리의 목표는 우리가 매 시점 $t$에서 구한 파라미터 $\theta_t$가 최적의 파라미터 $\theta^*$와 가능한 가까운 것이다. 즉, 매 시점에서의 $f_t(\theta_t) - f_t(\theta^*)$가 최소화되기를 의미한다. 그것을 첫 번째 시점 $t=1$에서 마지막 시점 $t=T$까지 다 더한 것이 결국 우리의 알고리즘을 평가하는 지표가 될 것이고, 그것을 "Regret"이라고 정의하였다.

 

 여러 가정을 통해 다음의 Theorem이 유도된다.

표기에서 $g_{1:T, i}$는 stochastic gradient $g$의 첫 번째 itearation에서 T번째 iteration까지의 i번째 index, 성분을 모아놓은 벡터이다. 즉, $[g_{1,i}, g_{2, i}, g_{3,i} \cdots, g_{t,i}]$이다.

 

위 Theorem에서의 여러 가정들은 convergence를 유도하기 위해 필요한 가정들이며, optimization literature들에서 일반적으로 많이 쓰이는 가정들이다. 

유도된 inequality를 보면 $R(T)$, 즉 regret이 복잡해 보이는 항들의 합으로 upper bound가 돼 있음을 알 수 있다.

위 upper bound에서 T와 관련된 지점만 보고 big-O notation으로 근사시켜서 표현하면, $O(\sqrt{T})$가 된다.

즉, Adam은 $O(\sqrt{T})$의 regret bound를 가지고 있음을 저자들이 증명하였다.

 또한, step-size $\alpha_t$는 t에 대해서 감소하는 것으로 가정하였고, first-moment의 하이퍼 파라미터 $\beta_{1,t}$도 (위 알고리즘 표 참고) $\lambda^{t-1}$로 감소하는 것을 가정하였는데, 위와 같은 가정이 있어야 Theorem 4.1을 유도할 수 있다.

또한, gradient ($\nabla f_t(\theta)$)의 norm이 bounded 돼 있다고 가정하였는데, 이 가정 또한 일반적으로 많이 쓰이는 가정이다. 참고로, gradient의 norm이 bounded 돼 있다는 가정은 이전 포스팅에서도 이야기하였듯 함수가 미분 가능하다면 원래 함수가 Lipschitz continuous하다는 가정과 동일하다. (즉, $f_t(\theta)$가 G Lipschitz constant를 갖는다.)

(물론, 위 가정을 사용하지 않고 optimization algorithm의 convergence analysis를 유도한다면 더 좋을 것이다.)

 

자, 결국 위 upper bound가 의미하는 것은 무엇일까? Average regret, 즉 $\frac{R(T)}{T}$에 대해서 Adam 알고리즘을 사용하면 converge한다는 것이다. $O(\sqrt{T})$는 그 속도 (convergence rate)을 나타내는 것이고, 결국 Adam은 converge한다는 것을 의미한다. ($\lim_{T \rightarrow \infty} \frac{R(T)}{T} = 0$)

 

 

위 가정들에서 중요한 것은 $\beta_1, \beta_2$에 대한 가정들이다. Adam에서 하이퍼파라미터 3개가 있는데, step-size 그리고 first-order moment와 second-order moment의 coefficients ($\beta_1, \beta_2$)가 있고, 당연히 이 모든 hyper-parameter들이 Adam의 성능에 상당히 큰 영향을 미치는 중요한 하이퍼파라미터들이다.

그 중, 위 Theorem에서 $\beta_1, \beta_2$에 대한 여러 가정들이 있는데, 이것이 실제 practical한 상황에서 Adam을 사용할 때와 얼마나 잘 부합하는진 여러 의문이 있다.

실제로 앞에서 소개했던 논문, "On the convergence of adam and beyond"도 $\beta_1, \beta_2$가 특정한 범위에 있을 때, Adam이 발산할 수 있음을 보여주었다. (특히 $\beta_2$가 작을 때)

하지만, 실제로 Adam은 잘 수렴하는 경우가 훨씬 더 많고 $\beta$가 충분히 큰 경우에는 학습이 잘 진행되는 상황들이 훨씬 더 많다. 이러한 현상에 대해서 이론적으로 수렴성을 분석한 논문은 다음과 같은 것들이 있다.

 

Yushun Zhang et al, "Adam can converge without any modification on update rules", Neurips 2022)

Bohan wang et al, "Closing the gap between the upper bound and lower bound of Adam's iteration complexity (Neurips 2023)

이처럼 Adam은 현재까지도 매우 활발하게 연구되고 있는 알고리즘이고, 앞으로도 그러할 것이다. 

 

다음 글에서는 Second order optimization에 대해서 이야기해보고자 한다.