Deep dive into optimization: Gradient descent (3) - Updated

 

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

 

지난 포스팅에서는 gradient descent, stochastic gradient descent, Mini-batch gradient descent에 대해서 이야기를 진행하였고, 오늘은 이 알고리즘이 실제로 optimal point로 수렴하는지, 그리고 그 속도는 어떻게 되는지를 수식으로 살펴보고자 한다.

 

먼저 Gradient descent부터 시작하자.

 

<Theorem 1>

Objective function $f$가 convex하고 $\beta$-smooth하다고 가정하자.

그리고 $(x_t)_{t \ge 0}$이 Gradient descent iteration에 의해 생성되는 sequence라고 하고 step-size는 $0 \le \eta \le \frac{1}{\beta}$이라고 하자. 그러면 $x^* \in \arg \min f(x)$에 대하여 다음을 만족한다.

 

위 Theorem 1을 바꿔 이야기하면 iteration number $t$에 대해 오차 ($f(x_t) - \inf f$)가 $O (\frac{1}{t})$의 속도로 감소한다는 의미이고, 또 어떤 작은 양수 $\epsilon$에 대하여, $f(x_T) - \inf f \le \epsilon$을 만족하기 위해서는, 최대 $T \le \frac{\beta}{\epsilon} \frac{\lVert x_0 - x^* \rVert^2}{2}$를 만족해야 한다고 표현할 수 있다.

 

다음은 Stochastic Gradient desecent이다.

GD에서 SGD의 convergence rate으로 넘어가기 전에 $f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x)$라 하자.

이 챕터에서 주로 다루는 것은 convex한 상황이므로, $f_i$가 convex하다고 가정할 것이다. 그러면 $f(x)$는 Sum of convex function이다. 또한 각각의 $f_i$가 $L$-smooth하다고 하자. 그렇다면 $L_{max} := \max_{1, \cdots, n}L_i$가 존재할 것이고, $L_{avg} := \frac{1}{n} \sum_{i=1}^n L_i$가 존재할 것이다.

그러면 다음이 성립하고 이는 smoothness의 성질과 삼각부등식으로 쉽게 증명할 수 있다.

 

<Lemma 1>

$f_i$가 L-smooth하다면, $f$는 $L_{avg}$-smooth하다.

 

<Lemma 2>

$f_i$가 L-smooth하다면, $f$는 $L_{max}$-smooth (in expecation sense)하다.

 

다음은 gradient noise (variance)에 대한 가정이다. 역시나 Lemma2가 성립하는 상황에서는 아래와 같은 Variance 가정을 할 수 있다.

 

<Lemma 3>

$\mathbb{E} [\lVert \nabla f_i(x) \rVert^2] \le 4L_{max} (f(x) - \inf f) + 2\sigma^*$.

여기서 $\sigma^*$는 $\inf \mathbb{V}[\nabla f_i(x^*)]$이다. 

 

자, 이제 SGD의 convergence rate을 유도하자. 

 

<Theorem 2>

Lemma 2, Lemma 3이 성립하고, $0 < \eta < \frac{1}{2 L_{max}}$라 하자. 

 

여기서 결국 중요한 영향을 미치는 요소는 step-size이다. 즉, $\sum_{k=0}^{t-1} \eta_k$가 속도에 영향을 미치면서 우리가 실질적으로 컨트롤할 수 있는 요소인데, 문제는 두 항에서 왼쪽에는 분모에 term이 들어가 있고, 오른쪽에는 분자/분모 모두에 term이 들어가 있다는 점이다. t에 대해서 위 upper bound가 결국 줄어들게 하기 위해서는 다음과 같은 가정이 필요하다.

 

<Step-size assumption> (A.K.A. Robbins-Monro condition)

1. $\sum_{k=0}^{\infty} \eta_k = \infty$

2. $\sum_{k=0}^{\infty} \eta_k^2 < \infty$

 

자, 이것이 의미하는 바는 무엇일까?

$1$번 조건, 즉 step-size의 무한 급수가 발산한다는 조건은 step-size가 constant, diminish form ($\frac{1}{t^{\alpha}}$)인 상황에서 성립한다. 여기서 $\alpha$의 조건은 $\sigma^*$에 따라서 달라지는데, 이를 좀 더 자세히 살펴보자.

 

두 번째 term에서 $\sigma^* = 0$이라면, 첫 번째 term에 의해서만 convergence rate이 영향을 받으므로, constant step size 상황에서는 $O(\frac{1}{t}$의 rate을 갖게 된다. 

만약 step-size가 $\frac{1}{t^{\alpha}}$로 감소하는 상황이라면, convergence rate은 $O(\frac{1}{t^{1 - \alpha}})$가 된다.

즉, $\sigma^*=0$이라면, SGD는 GD와 비슷한 속도의 성능을 가지게 된다.

 

하지만 만약 $\sigma^*$가 0이 아니라면, 우측의 $\frac{\sum_{k=0}^{t-1} \eta_k^2}{\sum_{k=0}^{t-1}\eta_k}$에 의해 convergence rate이 영향을 받게 된다.

그렇다면 우리는 $\eta_t$가 최대한 천천히 감소하여서 분모는 충분히 큰 동시에 $\eta_t$가 최대한 빠르게 감소해서 분자는 최대한 작게 되기를 바랄 것이다. 

여기서 일종의 trade-off가 발생하게 된다. 

만약 step-size가 constant라면, 우리의 이 바램이 충족되지 않으므로, step size는 감소해야 한다.

그래서 두 번째 조건 step-size의 제곱의 무한급수는 수렴한다는 조건이 필요하게 된다.

 

만약 $\eta_t = \frac{1}{t^{\alpha}}$라면, $0 < \alpha \le \frac{1}{2}$에 대해서 $O(\frac{1}{t^{\alpha}})$가 되고, $\frac{1}{2} \le \alpha < 1$에 대해서는 $O(\frac{1}{t^{1 - \alpha}})$가 된다. 즉, 최고의 $\alpha$값은 $\frac{1}{2}$이다.

즉, convergence rate이 $\frac{1}{\sqrt{t}}$가 된다. 

 

이것이 가장 convex, smooth한 상황에서 GD와 SGD의 가장 일반적인 결과이다.

다음은 SGD의 stochasticity (=noise) 때문에 우리는 step-size를 점점 줄여나가야 하고, 이 때문에 convergence rate의 감소가 발생하는데 이를 해결하기 위해 나온 method에 대해 이야기해보고자 한다.

 

** 본 글은 Guillaume Garrigos et al. "Handbook of Convergence Theorems for gradient methods" (arXiv 2023)을 참고하였습니다.