Introduction to Optimization / Gradient Descent

• Intro 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$ 이다. ◻