Introduction to Optimization / Gradient Descent
์ฌ์ธต ์ ๊ฒฝ๋ง์ ์ํ์ ๊ธฐ์ด 1๊ฐ (9์ 2์ผ) ์ ๊ธฐ๋ฐํฉ๋๋ค.
์ด ๋ฌธ์๋ $\LaTeX$๋ฅผ pandoc์ผ๋ก ๋ณํํ์ฌ ์์ฑํ์๊ธฐ ๋๋ฌธ์, ๋ ์ด์์ ๋ฑ์ด ๊น๋ํ์ง ์์ ์ ์์ต๋๋ค. ์ธ์ ๊ฐ pdf ๋ฒ์ ์ ๋ ธํธ๋ฅผ ๊ณต๊ฐํ๋ค๋ฉด ๊ทธ์ชฝ์ ์ฐธ๊ณ ํ๋ฉด ์ข์ ๊ฒ ๊ฐ์ต๋๋ค.
Intro to Optimization
์ฐ๋ฆฌ๋ ๋ค์๊ณผ ๊ฐ์ ์ต์ ํ ๋ฌธ์ ๋ฅผ ์๊ฐํ๋ค.
์ต์ ํ ๋ฌธ์ ๋, ์ด๋ค Decision variable $x$๋ฅผ ์กฐ์ ํ์ฌ Objective function $f$๋ฅผ ์ต์ํ / ์ต๋ํ ํ๋ ๋ฌธ์ ๋ฅผ ๋งํ๋ค. ์ด๋, equality ๋๋ inequality constraint (์ ์ฝ์กฐ๊ฑด) ๋ค์ด ์ฃผ์ด์ง ์ ์๋ค. ์ฆ ๋ค์๊ณผ ๊ฐ์ ํํ์ ๋ฌธ์ ๋ค. \(\underset{x \in \R^p}{\minimize} \ f(x) \ \subto \ h(x) = 0,\ g(x) \leq 0\)
์ด์ฐจํผ ์ต์ํ์ ์ต๋ํ๋ ๋ถํธ๋ฅผ ๋ฐ๊พธ๋ฉด ๋์น์ด๋ฏ๋ก, ์์ผ๋ก๋ ์ต์ํ ๋ฌธ์ ๋ง ์๊ฐํ๋ค.
๋ชจ๋ ์ ์ฝ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์ ์ Feasible point๋ผ ํ๋ค. Feasible point๊ฐ ์์ ์๋ ๊ฒฝ์ฐ infeasibleํ๋ค.
์ต์ ํ ๋ฌธ์ ๋ฅผ Constraint ์ ๋ฌด์ ๋ฐ๋ผ Unconstrained / Constrained๋ก ๋๋๋ค.
์ต์ ํ ๋ฌธ์ ์ ๋ต์ Optimal value $p^\star$ ์ solution $x^\star$๋ฅผ ์ฐพ๋ ๊ฒ์ด๋ค. ์ฆโฆ \(p^* = \inf \Setcond{f(x)}{x \in \R^n, x \text{ feasible }}, \quad f(x^*) = p^*\) ML ์ธํ ์์๋, $0 \leq p^* < \infty$ ์ธ ๊ฒฝ์ฐ๋ฅผ ์ฃผ๋ก ์๊ฐํ๋ค.
์์ : Curve-Fitting, ์ฆ ์ ๋ ฅ ๋ฐ์ดํฐ $x_1 \dots x_n$ ๊ณผ ๊ทธ label $y_1 \dots y_n$์ ๋ํด, ์ ๋ ฅ๊ฐ๊ณผ label์ ๊ด๊ณ๋ฅผ ์ฐพ๋ ๋ฌธ์ . ๋ํ์ ์ผ๋ก, Least square ๋ฌธ์ ๋ฅผ ์๊ฐํ ์ ์๋ค. ์ฃผ์ด์ง ์ ๋ ฅ๊ณผ ๊ฒฐ๊ณผ๋ฅผ ๊ฐ์ฅ ๊ฐ๊น๊ฒ ๊ทผ์ฌํ๋ ์ผ์ฐจํจ์ ์ฐพ๊ธฐ.
์ต์ ํ ๋ฌธ์ ์์๋ ๊ทน์ (Local minima) ์ ์ต์ (Global minima) ๋ฅผ ์๊ฐํด์ผ ํ๋ค. ์ผ๋ฐ์ ์ผ๋ก, non-convex ํจ์์ global minima๋ฅผ ์ฐพ๋ ๊ฒ์ ์ด๋ ต๋ค.
Gradient Descent
๋ฏธ๋ถ๊ฐ๋ฅํ ํจ์ $f$์ ๋ํด, ๊ฐ์ฅ ๊ฐ๋จํ unconstrained optimization problem์ ํด๊ฒฐํ๊ณ ์ ํ๋ค. \(\underset{x \in \R^p}{\minimize} \ f(x)\) ML ์ธํ ์์๋ almost everywhere differentiable์ด๋ฉด ๋์ถฉ ๋ฏธ๋ถ๊ฐ๋ฅํ๋ค๊ณ ๋งํ๋ ๊ฒฝ์ฐ ๋ง์.
Algorithm (Gradient Descent)
- ์์์ ์์์ $x^0 \in \R^p$ ๋ฅผ ์ก๊ณ , ์ ์ ํ $\alpha_k > 0$ ์ ๋ํด ๋ค์์ ๋ฐ๋ณตํ๋ค. \(x^{k+1} = x^k - \alpha_k \nabla{f(x^k)}\)
๋๋ต์ ์์ด๋์ด : $x^k$ ๊ทผ์ฒ์์ $f$๋ฅผ ํ ์ผ๋ฌ ์ ๊ฐํ๋ฉด, \(f(x) = f(x^k) + \nabla f (x^k)^T (x - x^k) + \order{\norm{x - x^k}^2}\) ์ฆ, $x = x^{k+1} = x^k - \alpha_k \nabla{f(x^k)}$ ๋์ ํ๋ฉด, \(f(x^{k+1}) = f(x^k) - \alpha_k \norm{\nabla{f(x^k)}}^2 + \order{\alpha_k^2}\) ์ ๋นํ $\alpha_k$๋ฅผ ์ถฉ๋ถํ ์๊ฒ ์ก์ผ๋ฉด, $f(x^{k+1})$ ์ด $f(x^k)$๋ณด๋ค ์๊ฒ ํ ์ ์์ ๊ฒ ๊ฐ๋ค.
์ผ๋ฐ์ ์ผ๋ก, Gradient Descent๋ Global ํ ์ต์ ํด๋ฅผ ๋ณด์ฅํ์ง ์๋๋ค. Localํ ์ต์ ํด๋ฅผ ์ฐพ์๊ฐ๋ค๋ ๊ฒ๋ ์ผ๋ฐ์ ์ธ ์กฐ๊ฑด์์๋ ์ ๋๊ณ โฆ ๋์ ์, ์กฐ๊ฑด์ด ์ถฉ๋ถํ ์ข์ผ๋ฉด ๊ฑฐ์ ๋น์ทํ ๋ช ์ , $\nabla f(x^k) \to 0$ ์ ๋ณด์ผ ์ ์๋ค.
์ ๋ฆฌ (Gradient Descent์ ์๋ ด์ฑ)
$f : \R^n \to \R$ ์ด ๋ฏธ๋ถ๊ฐ๋ฅํ๊ณ , $\nabla f$ ๊ฐ $L$-Lipschitz ์ฐ์์ด๋ฉฐ,
$f$๊ฐ $-\infty$๊ฐ ์๋ ์ต์๊ฐ์ ๊ฐ์ง ๋, Gradient descent
\(x^{k+1} = x^k - \alpha \nabla{f(x^k)}\) ์,
$\alpha \in \left(0, \frac{2}{L}\right)$์ ๋ํด, $\nabla f(x^k) \to 0$
์ ๋ณด์ฅํ๋ค.
Remark $L$-Lipschitz ์กฐ๊ฑด์ด ํ์ํ ์ด์ ๋, $\nabla f$ ๊ฐ ์ ๋นํ smooth ํด์ผ ํ ์ผ๋ฌ ์ ๊ฐ์ ๊ทผ์ฌ๊ฐ ์ ๋ง๊ธฐ ๋๋ฌธ.
์ด ์๊ฐ์ ๋ณด์กฐ์ ๋ฆฌ๋ก ํ์ฉํ๋ค.
Lemma (Lipschitz Gradient Lemma)
- $f : \R^n \to R$ ์ด ๋ฏธ๋ถ๊ฐ๋ฅํ๊ณ , $\nabla f$ ๊ฐ $L$-Lipschitz ์ฐ์์ด๋ฉด, ๋ค์์ด ์ฑ๋ฆฝํ๋ค. \(f(x + \delta) \leq f(x) + \nabla f(x)^T \delta + \frac{L}{2}\norm{\delta}^2\)
Lemma์ ์ฆ๋ช (์ด์ง Roughํ๊ฒ)
- $g(t) = f(x + t\delta)$ ๋ก ๋๋ฉด, $gโ(t) = \nabla f(x + t\delta)^T \delta$ ๊ฐ ๋๋ค. ์ด๋ $gโ$๋ ์ง์ ๊ณ์ฐํด ๋ณด๋ฉด $L\norm{\delta}^2$-Lipschitz ์์ ์ ์ ์๋ค.
- ์ด์ , $f(x + \delta) = g(1)$ ์, ๋ค์๊ณผ ๊ฐ์ด ๊ณ์ฐํ๋ค. \(f(x + \delta) = g(1) = g(0) + \int_{0}^{1} g'(t) \dd{t} \leq f(x) + \int_{0}^{1} (g'(0) + L\norm{\delta}^2 t) \dd{t} = f(x) + \nabla f(x)^T \delta + \frac{L}{2}\norm{\delta}^2\)
- ๋ฐ๋ผ์ ์ฃผ์ด์ง ๋ถ๋ฑ์์ด ์ฑ๋ฆฝํ๋ค.ย โป
์ํ์ ์ผ๋ก ๊น๋ํ๊ฒ ์ฆ๋ช
ํ๊ธฐ ์ํด, ๋ณด์กฐ์ ๋ฆฌ๋ฅผ ํ๋ ๋ ์ฐ์.
Lemma (Summability Lemma)
- Non-negative sequence $V_i$, $S_i$ ๊ฐ $V_{k+1} \leq V_k - S_k$ ๋ฅผ ๋ง์กฑํ ๋, $S_k \to 0$ ์ด๋ค.
Lemma์ ์ฆ๋ช
- $V_{k+1} + \sum_{i = 0}^{k} S_i \leq V_0$์์, $k \to \infty$ ๋ฅผ ์ทจํ๋ฉด, $\sum_{i = 0}^{\infty} S_i \leq V_0 < \infty$ ์ด๋ค. ๊ธ์๊ฐ ์๋ ดํ ๋, ์ผ๋ฐํญ์ด 0์ผ๋ก ์๋ ดํจ์ด ์๋ ค์ ธ ์์ผ๋ฏ๋ก, ์ฃผ์ด์ง ๋ช ์ ๊ฐ ์ฑ๋ฆฝํ๋ค. โป
์ด์ ๋ง์ง๋ง์ผ๋ก ์์ ์ ๋ฆฌ - Gradient Descent์ ์๋ ด์ฑ ๋น์ทํ ์ ๋ฆฌ - ๋ฅผ ์ฆ๋ช ํ๋ค.
- Lipchitz Gradient Lemma์ ์ํด, $f(x^{k+1}) \leq f(x^k) - \alpha\left(1 - \frac{\alpha L}{2}\right)\norm{\nabla(x^k)}^2$ ์ด๋ค.
- ๋ํ, $V_k = f(x^k) - f(x^\star)$, $S_k = \alpha\left(1 - \frac{\alpha L}{2}\right)\norm{\nabla(x^k)}^2$ ๋ผ ํ๋ฉด, ์ฃผ์ด์ง ์์ด๋ค์ด ์์๊ฐ ์๋๋ฉฐ Summability Lemma์ ์กฐ๊ฑด์ ๋ง์กฑํจ์ ์๋ค. ๋ฐ๋ผ์, $S_k \to 0$, ์ฆ $\norm{\nabla(x^k)}^2 \to 0$ ์ด๋ฏ๋ก $\nabla f(x^k) \to 0$ ์ด๋ค. โป