[P] Stochastic Gradient Descent

• Stochastic Gradient Descent
• Batch SGD / Cyclic SGD
• SGD Convergence Theorem

심층 신경망의 수학적 기초 2강 (9월 7일), 3강 (9월 9일) 에 기반합니다.

이 문서는 $\LaTeX$를 pandoc으로 변환하여 작성하였기 때문에, 레이아웃 등이 깔끔하지 않을 수 있습니다. 언젠가 pdf 버전의 노트를 공개한다면 그쪽을 참고하면 좋을 것 같습니다.

Stochastic Gradient Descent

ML에는 많은 Finite sum optimization이 있다. 우리는 $F(x) = \frac{1}{N} \sum_{i = 1}^{N} f_i(x)$ 를 최적화하고 싶다. 대표적으로, Gradient Descent를 쓸 수 있다. But, $N$이 매우 크면 이 함수를 한번 계산하는 시간이 매우 오래 걸린다.

위 식을, 이 함수의 기댓값 으로 이해할 수 있다. \(\underset{x \in \R^p}{\minimize}\ \E_I[f_I(x)], \ I \sim \uniform{1}{N}\)

이런 motivation을 통해, Stochastic (Random) Gradient Descent를 생각한다.

Algorithm (Stochastic Gradient Descent)
임의의 시작점 $x^0 \in \R^p$ 를 잡고, 적절한 $\alpha_k > 0$ 에 대해 다음을 반복한다. \(i(k) \sim \uniform{1}{N},\quad x^{k+1} = x^k - \alpha_k \nabla{f_{i(k)}(x^k)}\)

대략의 아이디어 :
GD처럼, Taylor expansion하고 Stochastic을 고려하여 Expectation을 씌운다.

$x^k$ 근처에서 $F(x) = \frac{1}{N} \sum_{i = 1}^{N} f_i(x)$를 테일러 전개하고 $x^{k+1}$ 대입하면, \(F(x^{k+1}) = F(x^k) - \alpha_k \nabla F(x^k)^T \nabla f_{i(k)}(x^k) + \order{\alpha_k^2}\) 이제, 양쪽에 $\E$ 를 씌운다. \(\expect{F(x^{k+1})} = \expect{F(x^k)} - \alpha_k \expect{\nabla F(x^k)^T \nabla f_{i(k)}(x^k)} + \order{\alpha_k^2}\) $\nabla F(x^k)^T$ 는 기댓값에 영향이 없고, $\nabla f_{i(k)}(x^k)$ 의 기댓값은 $\nabla F(x^k)$ 이므로, \(\expect{F(x^{k+1})} = \expect{F(x^k)} - \alpha_k \norm{\nabla F(x^k)}^2 + \order{\alpha_k^2}\) 적당히 $\alpha_k$를 충분히 작게 잡으면, 기댓값이 감소할 수 있을 것 같다.

• Stochastic Gradient Descent도 수렴성에 관한 정리를 기술할 수 있으나, 증명이 매우 Tedious하고 ML 세팅에서는 그렇게 중요하지 않다.

• 직접 구현해서 테스트해 보면, 초반에 SGD가 GD보다 수렴속도가 빠르지만, Eventually GD에게 따라잡힌다.

• 그러나, 우리는 ML을 공부하는데 있어 SGD를 Subroutine으로 쓸 것이고, 짧은 Training 시간의 환경에서 SGD가 in practice GD보다 잘 수렴한다.

• Stochastic Gradient Descent에서, $i(k)$ 자체의 성질은 전혀 활용하지 않았다.
• 실제로, SGD의 수렴성 증명에서 중요한 것은, 다음과 같은 Framework면 충분하기 때문.

Algorithm (Stochastic Gradient Descent)
임의의 시작점 $x^0 \in \R^p$ 를 잡고, 적절한 $\alpha_k > 0$ 에 대해 다음을 반복한다. \(i(k) \sim \uniform{1}{N},\quad x^{k+1} = x^k - \alpha_k g^k\) 이때, $g^k$ 는 Stochastic gradient로, $\nabla F(x^k)$ 의 Unbiased Estimator 이면 - 즉, 기댓값이 $\nabla F(x^k)$ 이면 충분하다.

Batch SGD / Cyclic SGD

• 예를 들어, $g^k$를 고르는 방법으로 Batch sampling with/without Replacement를 생각할 수 있다.
• 즉, $N$개 중 일부인 $B$개를 랜덤하게 계속 뽑아서, $\frac{1}{B}\sum_{b = 1}^{B} \nabla f_{i(k, b)}(x^k)$, 즉 $B$개의 batch에 대한 gradient의 평균을 쓰는 것.
• 이때, Batch를 뽑을 때 중복을 허용하는지 여부는 상관 없다 (둘 다 Unbiased estimator가 되기 때문). 중복을 허용하고 싶으면 random한 $B$개를 뽑고, 허용하고 싶지 않으면 random permutation의 첫 $B$개를 쓰면 된다.

특히, Batch 방법의 경우, GPU를 이용한 Parallel 연산에 유리하다는 추가적인 장점이 있다. GPU와 병렬처리를 최대한 활용하기 위해, GPU memory에 들어가는 최대 $B$를 이용하는 것이 가장 유리하다. Batch size는 noise 정도에 따라 성능이 달라지는데, noise가 클수록 large batch가 유리하다.

그런데…이 알고리즘에서, 원래 랜덤하지 않은 것을 억지로 랜덤하게 만들어서 풀고 있는 것 아닌가? Stochastic하게 뽑는 대신, 그냥 순서대로 돌리면서 쓰면 안 되나?

Algorithm : Cyclic SGD
임의의 시작점 $x^0 \in \R^p$ 를 잡고, 적절한 $\alpha > 0$ 에 대해 다음을 반복한다. \(x^{k+1} = x^k - \alpha_k \nabla{f_{(k \text{ mod } N + 1)}(x^k)}\)

이 방법은 stochastic한 부분이 사실 없다. 장단점은...

• (+) 확실하게 $N$개의 데이터를 $N$번마다 한번씩 정확하게 사용한다.
• (-) SGD의 수렴성에 대한 정리를 쓸 수 없다.
• (-) 일반 SGD에 비해 Theoretically / Empirically, some case에서는 잘 작동하지 않음.
• (-) Deep Learning으로 가면, Neural network가 이 순서(cyclic order)를 기억하는 경향 발생.

특히 기억하는 경향에 의한 overfitting이 큰 이슈이기 때문에, 이를 방지해야 한다. 적당히 섞어주면 어떨까?

Algorithm : Shuffled Cyclic SGD
임의의 시작점 $x^0 \in \R^p$ 를 잡고, 적절한 $\alpha > 0$ 에 대해 다음을 반복한다. \(x^{k+1} = x^k - \alpha \nabla{f_{\sigma^{(k/N)}(k \text{ mod } N + 1)}(x^k)}\)

즉, $N$번에 한 번씩, 인덱스들을 랜덤하게 permutation해버린 다음, 그 순서로 다음 $N$번의 iteration을 Cyclic하게 돌린다. 이렇게 하면, 정확하게 $N$개의 데이터를 한번씩 쓴다는 장점을 챙기면서도, neural network가 학습하는 일을 막을 수 있다. 기존에는 강한 theory가 별로 없었지만, recent breakthrough들이 이를 개선하고 있다.

그냥 일반적인 세팅에서는, Shuffled cyclic minibatch SGD without replacement 를 쓰면 되고, GPU가 허락하는 최대한 큰 Batch size를 잡으면 된다. Deep Learning의 많은 경우, 수학적인 분석이 실제 performance를 정확하게 예측하지 못하는 경향이 있는데, empirically this is best.

일반적인 expectation으로 표현된 최적화 문제, 예를 들어 확률변수 $\omega$에 대해 이런 문제들 \(\underset{x \in \R^p}{\minimize}\ \E_\omega[f_\omega(x)]\) 의 경우, 똑같이 SGD로 풀 수 있다. GD로도 할 수는 있지만, 일반적으로 ‘gradient의 기댓값’ 을 구하기가 어렵기 때문에...

참고 : Optimization / ML에서, 대충 ‘한바퀴’ 를 Epoch 라고 부른다. 대충 데이터들을 한바퀴 돌면 된다. Gradient descent면 한번 = 1 epoch, SGD면 $N$번, Batched SGD면 $N / B$ 번 정도.

SGD Convergence Theorem

상세하게 다루어야 할 내용은 아니지만, 앞서 공부한 Lipschitz Gradient Lemma 등을 이용해서 비슷한 증명을 쓸 수 있다.

$F : \R^n \to \R$ 이 미분가능하고, $\nabla F$ 가 $L$-Lipschitz 연속이며, $F$가 $-\infty$가 아닌 최소값을 가지며, $g^k$가 다음 조건 \(\E[g^k \di x^k] = \nabla F(x^k), \quad \quad \expect{\norm{g^k - \nabla F(x^k)}^2 \di x^k} \leq \sigma^2\) 을 만족할 때, 즉 $g^k$ 가 Gradient에 대한 Unbiased estimator이고 그 분산이 $\sigma^2$ 이하일 때, 다음이 성립한다. \(\frac{1}{M}\sum_{k = 0}^{M-1} \expect{\norm{\nabla F(x^k)}^2} \leq \frac{1}{\sqrt{M}}\left(2L(F(x^0) - F^*) + \sigma^2\right)\)

즉, Gradient의 크기의 평균이 $M$번의 iteration에 의해 $\order{\frac{1}{\sqrt{M}}}$로 감소한다.

Proof. 먼저, Lipschitz Gradient Lemma를 $x = x^k, \delta = -\alpha g^k$에 대해 쓰면, \(F(x^{k+1}) \leq F(x^k) -\alpha \nabla F(x^k)^T g^k + \frac{\alpha^2L}{2}\norm{g^k}^2\) $x^k$ 가 이미 주어졌을 때의 Conditional expectation을 쓴다. \(\expect{F(x^{k+1}) \di x^k} \leq F(x^k) - \alpha \norm{\nabla F(x^k)}^2 + \frac{\alpha^2 L}{2}\left(\norm{\nabla F(x^k)}^2 + \sigma^2\right)\) 이제 이를 다시 Total expectation을 취하면, \(\expect{F(x^{k+1})} \leq \expect{F(x^k)} - \alpha\left(1 - \frac{\alpha L}{2}\right) \expect{\nabla F(x^k)} + \frac{\alpha^2 \sigma^2 L}{2}\) 이를 $k = 0 \dots M-1$에 대해 양변을 더하여 \(\alpha\left(1 - \frac{\alpha L}{2}\right) \sum_{k = 1}^{M-1}\expect{\nabla F(x^k)} \leq (F(x^0) - F^*) + \expect{F(x^k) - F^*} + \frac{\alpha^2 \sigma^2 L}{2}\) 마지막으로, $\alpha = \frac{1}{L \sqrt{K}}$ 를 취하여 주어진 식을 얻는다. ◻