Optimization 심화 1 : SGD (1)

 

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

 

오늘부터는 Optimization에 대한 조금 더 깊이 있게 들어가보고자 한다.

그 첫 번째 주제로 SGD를 선택하였다. 

SGD에 대한 기본적인 내용의 글은 다음의 링크들을 참고하면 된다.

 

https://kyteris0624.tistory.com/22

Deep dive into optimization : Gradient descent (2)

https://kyteris0624.tistory.com/24

Deep dive into optimization: Gradient descent (3)

 

먼저 optimization problem부터 정의하도록 하자. 다음과 같은 일반적인 Finite sum으로 문제가 정의되어져 있다.

 

$\min_x f(x) := \sum_{i=1}^n f_i(x)$

 

여기서 training sample $n$개 중 우리는 1개씩을 매 iteration 마다 무작위적으로 뽑아서 파라미터를 업데이트하는 알고리즘, 즉 Stochastic gradient descent (SGD)에 관심이 있다.

이 알고리즘은 다음과 같이 진행된다.

 

$x_{t+1} = x_t - \eta_t \nabla f_i(x_t)$ 

 

만약 매 iteration마다 각각의 sample을 뽑을 확률이 uniform distribution이라면, stochastic gradient $\nabla f_i(x)$는 unbiased estimator이다.

즉, 다음이 성립한다.

 

$\mathbb{E} [f_i(x)] = \nabla f(x)$

 

하지만, Random reshuffling (또는 Without replacement sampling)이라면 위 가정은 깨져 버린다.

일단 이번 시리즈에서는 우리는 uniform sampling으로 데이터 추출이 이뤄진다고 가정할 것이다.

 

자, 그러면 본격적으로 SGD의 성질을 알아보자.

우선 함수 $f(x)$가 L-smooth하다는 가정을 하도록 하자. 즉, 다음이 성립한다.

 

$\lVert \nabla f(x) - \nabla f(y) \rVert_2 \le \lVert x - y \rVert_2$

$f(x) \le f(y) + \langle \nabla f(y), x - y \rangle + \frac{L}{2} \lVert x- y \rVert_2^2$

 

L-smooth에 대한 글은 이전에 자세하게 다뤘으므로 넘어가도록 하겠다.

 

우리는 위 식에서 두 번째 식으로부터 시작할 것이다. $x$ 자리에 $x_{t+1}$, $y$ 자리에 $x_t$를 집어넣자.

그러면 이렇게 정리된다.

 

$f(x_{t+1}) \le f(x_t) + \langle \nabla f(x_t), - \eta_t \nabla f_i (x_t) \rangle + \frac{L}{2} \lVert (- \eta_t \nabla f_i(x_t)) \rVert_2^2$

 

위 식을 정리하면 다음과 같이 된다.

 

$f(x_{t+1}) \le f(x_t) - \eta_t \langle f(x_t), \nabla f_i(x_t) \rangle + \frac{L \eta_t^2}{2} \lVert \nabla f_i (x_t) \rVert_2^2$

 

위 식에 이제 Expectation을 취하도록 하자.

왜 Expectation을 취하는 것일까?

$ \{ x_t \}_{t=1}^T $는 random process (= Stochastic process)로 생성되는 수열로 볼 수 있다.

즉, 위 파라미터의 trajectory는 무수히 많은 가능성들이 존재하기 때문에 우리는 이 모든 가능성들에 대해 다 고려하기 힘들다. 물론, 이렇게 모든 trajectory에 대해서도 거의 확실하게 (almost surely) 수렴이 가능하다는 것을 증명한 논문들도 여럿 있다. 

이를 우리는 almost sure convergence라 부른다.

(자세한 건 Random process 또는 확률변수의 수렴 주제를 공부하면 된다)

 

하지만 현재 convergence analysis의 일반적인 형태는 이러한 randomness에 대해서는 Expectation을 취한 형태로 되어져 있다. 

즉 $\mathbb{E}(f(x_{t+1}|x_t)$ 형태로 볼 수 있는데 이는 $\{ x_i \}_{i=1}^t$까지는 고정시켜놓고 어떤 $x_t$가 주어졌을 때 거기서 stochastic gradient로 업데이트된 $x_{t+1}$에서의 함숫값을 의미하는 것이다. 

 

위의 식에 Expectation을 취하면 다음과 같이 정리된다.

$\mathbb{E}[f(x_{t+1}] \le f(x_t) - \eta_t \mathbb{E} [\langle \nabla f(x_t) \nabla f_i(x_t) \rangle] + \frac{L \eta_t^2}{2} \mathbb{E}[\lVert \nabla f_i(x_t) \rVert_2^2]$

 

 

현재 우리는 stochastic gradient를 활용해서 함숫값이 감소해나가서 어떤 optimal point로 수렴하기를 기대하고 있다.

즉, 다음이 성립하길 기대한다.

$\mathbb{E} f(x_{t+1}) \le f(x_t)$

 

 

그렇다면 위 식의 우변에서 2번째 항은 음수가 나와야만 한다.

$\mathbb{E} [\nabla f_i(x_t)] = \nabla f(x_t)$이므로, 우변을 다음과 같이 바꿔쓸 수 있다.

 

$f(x_t) - \alpha_t \lVert \nabla f(x_t) \rVert^2 + \frac{L \eta_t^2}{2} \mathbb{E} \lVert \nabla f_i(x_t) \rVert_2^2$

 

 

만약 stochastic gradient가 unbiased estimator가 아니라면, 우리는 두 gradient (즉, stochastic gradient와 True gradient)의 inner product가 0보다 크길 기대해야 한다. 이것은 convergence analysis의 아주 중요한 부분이다.

자, 그렇다면 우변의 3번째 항을 보자.

이 부분은 항상 양수이다. 즉 이 값은 가능한 작아야 하고, 만약 이 값이 너무 커져버리면 $f(x_{t+1})$ 이 $f(x_t)$보다 더 값이 커지는 경우가 생겨버릴 수 있다.

이 부분은 stochastic gradient의 second moment (또는 Variance)와 step-size의 제곱, 립시츠 상수 $L$로 이뤄져 있다.

 

여기서 우리는 stochastic gradient의 second moment가 다음과 같이 bounded돼 있다고 가정할 것이다.

 

$\mathbb{E} [\lVert \nabla f_i(w) \rVert_2^2] \le \sigma^2$

 

이 가정은 다음의 stochastic gradient의 variance 가정과 상당히 유사한데 다만 위 가정이 아래의 가정보다 더 강한 가정이다. 왜냐하면 위 가정은 True gradient가 bounded돼 있다 = 원래의 함수가 립시츠 연속이다. 라는 가정을 포함하고 있기 때문이다.

 

$\mathbb{E} [\lVert \nabla f_i(w) - \nabla f(w) \rVert_2^2] \le \sigma^2$

 

 자, 그렇다면 위 가정 (second moment 가정)을 활용해서 다시 이어서 진행을 해보자.

 

$\eta_t \lVert \nabla f(x_t) \rVert_2^2 \le f(x_t) - \mathbb{E}[f(x_{t+1}] + \eta_t^2 \frac{L \sigma^2}{2}$

 

위 식의 양변을 $t=1$부터 $T$까지 다 더해주는 Sigma를 취해주자. 그렇다면 다음과 같은 식을 얻는다.

 

$\sum_{t=1}^T \eta_t \mathbb{E} \lVert \nabla f(x_t) \rVert_2^2 \le f(x_0) - \mathbb{E} f(x_{t+1}) + \frac{L \sigma^2}{2} \sum_{t=1}^T \eta_t^2$

 

좌변의 $\mathbb{E} \lVert \nabla f(x_t) \rVert_2^2$는 $\min_{k = 1, 2, \cdots, T} \mathbb{E} \lVert \nabla f(x_k) \rVert_2^2$로 lower bound를 잡을 수 있고, $\mathbb{E}f(x_{t+1})$은 함수의 최솟값 $f^{\star}$보다는 크거나 같으므로, 이를 활용하여 다음과 같은 결론을 얻을 수 있다.

 

$\min_{k = 1, 2, \cdots, T} \mathbb{E} \lVert \nabla f(x_k) \rVert_2^2 \le \frac{f(x_1) - f^{\star}}{\sum_{t=1}^T \eta_t} + \frac{L \sigma^2}{2} \frac{\sum_{t=1}^T \eta_t^2}{\sum_{t=1}^T \eta_t}$

 

위 upper bound가 수렴하기 위해서는 결국 step size의 series가 step size 제곱의 series보다 더 빠르게 증가해야 한다.

만약 step size가 $\eta_t = \frac{\eta_0}{t}$라면 이 조건을 만족한다. 

만약 step size가 상수라면 second term은 0이 되지 않기 때문에  SGD가 어떤 stationary point로 수렴함을 보일 수 없다.

다만 그 근방의 bounded region으로 수렴함은 보일 수 있다. 

여기서 SGD가 stationary point로 수렴할 수 있음을 보일 수 있는 방법이 있는데 그것은 다음이 성립한다고 가정하는 것이다.

 

만약, $\nabla f(x^{\star}) = 0$이라면, 모든 $i$에 대해서 $\nabla f_i(x^{\star})$가 0이다.

 

그리고 이 가정은 data에 완전히 fitting할 수 있는, 대다수의 overparameterized model에 대해서는 들어맞는다. 

결국 이 가정은 stochastic gradient의 noise에 대한 개념, 그리고 second moment에 대한 가정의 발전과 관련이 되는데, 이에 대해서 다음 글에서 살펴보고자 한다.