1. 경사하강법의 수렴 Convergence of GD Method
Gradient Descent의 수렴은 다음과 같이 판단한다. 수렴의 판단 기준은 각자가 골라서 설정한다.
여기서 Convergence란 정확히 0이 되는 것이 아니라, 위 수식에서 나타난 것처럼 아주 작은 특정 값(입실론)을 직접 설정하고, 이보다 작으면 Stop하는 것을 말한다.
2. Convergence Theorem
지금부터 다룰 내용은, "과연 Gradient Descent를 이상적인(local minimum이 곧 global minimum인) convex function에서 무한번 반복하면 정말로 0에 수렴할까? GD를 무한번 반복하면 정말 optimal solution이 나오나?"에 대한 증명이다.
증명에 대한 자세한 이해는 나중에 하도록 하고 우선은 의미만 알아가자.
f(x)의 차원은 다음과 같고,
L-Lipschitz continuous gradient인 convex function이라고 하자.
목표하는 값인 w*를 다음과 같이 설정한다면,
다음 식을 만족한다. k는 반복 횟수이다.
다음의 Preliminary를 참고하자.
위 그림 A에서 우리가 가져갈 것은 step size L과 initial value w0에 대한 내용이다.
- 목표하는 값 w*와 초기값 w0가 가까울 수록 이 둘의 오차가 작아지므로 계산이 쉬워진다.
따라서 초기값 w0의 설정이 중요하다.
3. Step-Size
위 그림 A의 수식에서 볼 수 있듯이,
- Step size가 작으면: 수렴하는 데 너무 오래 걸린다.
- Step size가 크면: 발산할 수도 있다.
따라서, L : step size가 크면 빨리 GD 결과 얻을 수 있지만, 무작정 크면 안 된다는 것을 알 수 있다.
다음은, Local minimum이 Global minimum이 되는 정말 이상적인 Convex 상황에서도 Step-Size가 크다면 Divergence (발산)할 수도 있다는 것을 보여준다.
다음은, Step-Size가 너무 작으면 minimum까지 가는 데에 오랜 시간이 걸린다는 것을 보여준다.
