Deep dive into Optimization : Types of Convergence

 

 

모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다.

 

다음과 같이 최적화 문제를 정의하자.

 $\min_x f(x)$

 

Stochastic gradient를 쓰는 First-order optimization algorithms를 생각해보자.

그러면 우리는 자연스레 다음과 같은 질문을 던지게 될 것이다.

이 알고리즘들을 매 step (iteration)마다 반복적으로 (=iterative) 사용하여 $f(x)$를 최소화하면, 우리는 정말로 위의 최적화 문제를 풀 수 있는가?

즉, $f(x)$의 global minima를 찾을 수 있는가?

 

그리고 두 번째로 궁금한 것은 과연 그렇다면 얼마만큼의 비용이 필요한가? 

여기서의 비용 (cost)란 대다수의 경우에 gradient 계산 횟수와 연결된다.

즉, (stochastic) gradient 호출을 할 때마다, optimal parameter와의 distance (gap)이 얼만큼 감소하는가?  

또는 다음과 같이 이야기할 수도 있다. 

특정한 error 이하가 되기 위해선 얼마만큼의 gradient 호출 횟수가 필요한가?

 

이를 수식으로 표현하면 다음과 같다.

 

$\lVert x_T - x^{\star} \rVert \le f(T)$ 

$\lVert x_T - x^{\star} \rVert \le \epsilon$

$x^{\star} := \arg \min f(x)$이다.

$T$는 stochastic gradient를 호출한 횟수이다. 우리는 이를 주로 iteration (step)이라고 부른다.

위와 같은 bound를 유도하는 과정을 우리는 convergence analysis (수렴성 분석)이라고 한다.

이는 최적화 알고리즘을 평가하는 하나의 주요 척도이다.

(또는 다른 말로 iteration complexity라고도 한다.)

 

하지만 $f(x)$의 $x^{\star}$가 유일하지 않을 수도 있고, 아예 존재하지 않을 수도 있다.

이는 함수 $f(x)$의 성질에 따라 결정될텐데 우리는 이전에 strongly-convex, convex, non-convex에 대해 공부하였다.

함수가 non-convex한 경우에는 무수히 많은 local minima와 saddle point들이 존재하고, global minima가 존재하지 않을 수도 있다. 

그래서 우리는 convergence analysis를 다음과 같은 방식으로 유도한다.

 

$ \{ \lVert \nabla f(x_t) \rVert \}_{t} \rightarrow 0$

 

대다수의 논문들에서 보이는 convergence는 결국 "모든 limit point가 stationary point이다."라는 방식의 convergence를 보인다. 

즉, $\{ \lVert \nabla f(x_t) \rVert\}$ 수열을 생각해보았을 때 이 수열의 부분 수열 (subsequence)이 stationary point (gradient가 0인 지점)으로 수렴한다는 것을 보인다.

 

이는 두 가지의 문제점을 가지고 있다.

1. sequence가 하나 이상의 limit point를 가지고 있을 수 있다.

2. limit point가 존재하지 않을 수도 있다.

 

2번 문제점은 다음과 같은 논리를 생각해보면 된다. 

"모든 지구상에 존재하는 용은 초록색이다."라는 명제가 참일지라도, 지구상에 용이 존재하지 않을 수 있다.

"집합 A의 모든 원소는 집합 B에 포함된다."라는 명제가 참일지라도, 집합 A는 공집합일 수 있다.

 

1번과 2번의 문제점을 제거해서 하나의 유일한 stationary point로 수렴함을 보이는 것은 사실상 불가능에 가깝다.

 

하지만 $f(x)$가 lower bounded 되어져 있다면 우리는 $\nabla f(x)$가 0으로 수렴함을 보이는 것만으로도 충분하다.

 

즉, 단순히 부분수열이 0으로 수렴하는 것이 아닌, $\nabla f(x)$ 수열 자체가 0으로 수렴함을 보일 수 있다.

그리고 함수가 lower bounded돼 있다라는 것은 Machine learning이나 Neural network에서 그리 강한 (비현실적인) 가정이 아니다.

 

하지만, 또 다른 문제가 있다.

$x_t$가 stochastic process라는 점이다. 즉, 우리는 알고리즘을 시행할 때, 매 시행마다 (trial) 서로 다른 trajectory를 가진다는 점이다. 이러한 점에서 봤을 때 $\nabla f(x)$도 Random variable로 볼 수 있다.

그래서 대다수의 연구들에서 stochastic optimizer의 stationary point로의 convergence analysis를 보면 $\mathbb{E}$가 붙어있음을 쉽게 볼 수 있다.

Non-convex에 초점을 맞추어 예시를 들자면, 다음과 같은 값의 bound를 제시하는 형태이다.

 

$\mathbb{E} \min_{1 \le t \le T} \lVert \nabla f(x_t) \rVert$

$\mathbb{E} \lVert \nabla f(x_{\tau}) \rVert$

where $\tau := Unif \{1, 2, \cdots, T \}$  

 

즉, 위와 같은 방식으로 Expectation이 붙어 있는 항의 bound를 유도하는 것이 일반적인 convergence analysis이다.

Expectation이 붙는 이유는 $x_t$가 "stochastic process"이기 때문이다.

이러한 bound는 다음과 같은 의미를 함축하고 있다.

 

"위 알고리즘을 무수히 많이 시행하였을 때, 그 시행들이 전반적으로 이러한 bound를 가진다."

 

여기서 Expectation bound의 문제 (한계)점이 드러난다. 

"알고리즘을 무수히 많이 시행했을 때"라는 전제가 붙어있는 것이다.

하지만, 우리가 실제 Neural network를 학습시킬 때 학습을 무수히 많이 시키는 일은 잘 없다.

우리는 한 번 (또는 최소한 매우 적은 횟수)만에 학습이 잘 되기를 기대하고 있다.

그리고 Neural network를 학습시키는 것은 그 사이즈가 크면 클수록 상당한 시간 비용이 소모되는 작업이기 때문에 한 번에 우리는 stationary point로 수렴함이 보장된 알고리즘을 원한다.

그렇다면 이걸 어떻게 수학적으로 증명할 수 있을까?

 

여기서 등장하는 convergence type이 바로 'with a high probability convergence'와 'almost sure convergence'이다.

먼저 high probability bound의 의미는 다음과 같다.

 

모든 $\epsilon >0$에 대하여 $\lim_{t \rightarrow \infty} \mathbb{P}(|X_t - X| \ge \epsilon) = 0$일 때, 우리는 Random variable $X_t$가 $X$로 "확률수렴"한다고 이야기한다.

그리고 더 나아가서 그 속도 (convergence rate)가 $r(t, \delta)$이고 $t$에 대한 함수와 $\delta$에 대한 함수의 곱으로 분리될 때, 즉 $r(t, \delta) = r(t) p(\delta)$일 때, $p(\delta)$가 $\log (\frac{1}{\delta})$에 대한 다항식 형태로 표현되어지면 우리는 위 bound가 high probability bound라고 표현한다.

만약 $p(\delta)$가 $\frac{1}{\delta}$에 대한 다항식 형태로 표현되어지면 우리는 위 bound가 low probability bound라고 정의한다.

 

즉, high probability bound에서 중요한 것은 with probability at least $1 - \delta$로 성립하는 bound가 제시되어졌을 때, 이 bound에 $\log \frac{1}{\delta}$에 비례하는 term이 있어야 한다. 

만약 $\frac{1}{\delta}$에 비례하는 term이 있다면 이는 high probability가 아니다.

 

그렇다면 high probability는 매 시행마다 높은 확률로 우리는 stochastic optimizer가 stationary point로 수렴하게 함을 알게 해준다. 또한 almost surely는 매 시행마다 확률 1에 가깝게 stochastic optimizer가 stationary point로 수렴하게 함을 알게 해준다.

 

즉, 더 강력한 의미를 포함하는 결과라고 할 수 있다.