[P] Stochastic Gradient Descent
์ฌ์ธต ์ ๊ฒฝ๋ง์ ์ํ์ ๊ธฐ์ด 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}}$ ๋ฅผ ์ทจํ์ฌ ์ฃผ์ด์ง ์์ ์ป๋๋ค.ย โป