Optimization 심화: Iterative Complexity

 

 

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

 

지난 번 글에서는 convergence type 3가지를 소개하였다.

첫 번째는 in-Expectation bound, 두 번째는 with a probability bound, 세 번째는 Almost sure bound이다.

각각 의미가 있지만, 이들 사이에는 중요한 차이점이 존재한다.

with a probability bound는 구체적으로 low probability와 high probability로 나뉘어져 있고,

in-Expectation bound는 concentration inequality (e.g. Markov inequality) 를 사용하면 low probability bound로 쉽게 바꿀 수 있다. 하지만 이는 single run (or few runs)에 대해서 bound가 상당히 vacuous하다는 한계를 가지고 있고,

이 때문에 high probability bound, Almost sure bound 등을 유도하는 것도 매우 중요하다.

위 둘은 single run에 대해서도 bound가 높은 확률로, 또는 확률 1에 가깝게 성립한다는 것을 보장하기 때문이다.

 

현재의 NN는 학습시키는 데 상당한 시간과 에너지가 소요되고 무수히 많이 학습을 시켜본다는 것 자체가 비현실적이다. 우리는 알고리즘을 한 번, 또는 적은 횟수만 시행했을 때도 파라미터가 stationary point (또는 그 근방)으로 수렴하길 원한다. 이를 이론적으로 보장해주는 bound가 with a high probability / almost sure bound이다.

이것이 지난 글의 주제였다.

 

오늘은 그럼 Iteration complexity에 대해서 알아보고 이를 토대로 first-order stochastic algorithm의 알려져 있는 lower bound를 살펴보고자 한다.

 

optimization problem 정의부터 시작하자.

 

$\min_{x \in \mathbb{R}^d} f(x)$

 

알고리즘의 목적은 다음과 같은 $\epsilon$-stationary point 를 찾는 것이다.

 

 

$\lVert \nabla f(x) \rVert \le \epsilon$

 

 

먼저 이 문제를 풀기 위해서는 함수 $f$에 대한 가정이 필요하다.

$p \in \mathbb{N}$번 미분 가능한가? convex한가? strongly-convex한가? $L_p$- smooth한가?

여기서 $L_p$ - smooth라 함은, $p$-th derivative에 대해서 다음이 만족함을 의미한다.

 

$\lVert \nabla^{p+1} f(x) \rVert \le L_p$

 

만약 $p = 1$이면, Hessian의 (spectral) norm이 constant $L_p$로 bound 돼 있음을 의미한다.

$p$는 자연수이고, 당연히 $p$의 값이 클 수록 더 강한 가정이다.

지금까지의 optimization 시리즈 글에서 우리는 일반적으로 $p=1$을 가정했다.

 

다음으로 알고리즘에 대한 엄밀한 정의를 필요로 한다.

(Iterative) 알고리즘은 Function $f$를 sequence of iterates $\{ x_t \}_{t=1}^{\infty}$로 매핑 (mapping)해주는 함수로 볼 수 있다. 

즉, 다음과 같이 표기할 수 있다.

 

$A[f] = \{ x_t \}_{t=1}^{\infty}$

 

이는 알고리즘 A가 함수 $f$에 대한 연산을 처리하여 sequece of iterates $\{ x_t \}$를 생성했다는 의미이다. 

 

다음은 우리가 활용 가능한 정보가 무엇이 있는지에 대한 가정 / 모델링을 필요로 한다.

 

(Information) Oracle이란 개념이 그것인데 이것이 우리가 유일하게 접근 가능한 (블랙박스) 모델이다.

우리는 Oracle에 정보를 요청하고, Oracle은 우리가 접근 가능한 정보를 제공해주는 모델이다.

그 외의 정보는 우리가 알 수 없다.

쉽게 이야기하면 우리는 함수 자체에 대해 알 수 없고, '함숫값/1차 미분값/ 2차 미분값 혹은 3차 이상의 고차 미분값'에 대해서만 알 수 있다는 것이다.

 

우리는 Oracle이 반환해주는 정보만 활용할 수 있고, 알고리즘이 그 정보를 어떻게 사용하는가에 대한 가정을 세운다. $p$차 미분값까지 반환해주는 oracle이라면 다음과 같이 표현할 수 있다.

 

$\nabla^{(0, 1, \cdots, p)} f(x) := \{ f(x), \nabla f(x), \nabla^2 f(x), \cdots, \nabla^p f(x) \}$

 

만약 1차 미분 정보까지만 oracle이 반환해주면 (= 우리가 접근이 가능하면) 우리들의 알고리즘은 함숫값, 1차 미분값 (gradient)만 활용 가능한 것이다. (즉, 2차 이상의 미분 정보는 활용이 불가능하다.)

 

자, 그러면 Deterministic algorithm과 Stochastic algorithm은 어떻게 정의할 수 있을까?

Deterministic algorithm은 다음과 같이 표현할 수 있을 것이다.

 

$x_t = A_t(\nabla^{(0, 1, \cdots, p)} f(x_1), \cdots, \nabla^{(0, 1, \cdots, p)} f(x_{t-1}))$

 

$f$라는 함수에 대해서 $A$라는 알고리즘은 $x_t$라는 iterates of sequence를 생성하는 알고리즘이고,

그때 활용 가능한 정보는 0차~$p$차 미분까지의 정보이다.

 

Randomized (Stochastic) algorithm은 다음과 같이 표현할 수 있을 것이다.

 

$p$-th order Randomized algorithm은 $p$-th order Deterministic algorithm에 분포라고 정의할 수 있다.

즉, uniform variable $\xi \sim Unif[0, 1]$이 있고, 이 uniform variable 하나를 sampling하면 deterministic algorithm에서부터 Randomized algorithm이 결정된다.

이는 결국 함수 $f$를 받아서 다음과 같은 iterate of sequence $\{ x_t \}$를 생성하는 것이라고 볼 수 있다. 

 

$x_t = A_t(\xi, \nabla^{(0, 1, \cdots, p)} f(x_1), \cdots, \nabla^{(0, 1, \cdots, p)} f(x_{t-1}))$

 

이때, $x_t$를 우리는 stochastic process (random process)라고 이야기한다.

이 또한 확률론에서 상당히 중요한 분야 중에 하나이다.

 

 

그러면 우리의 본론 Iteration complexity (measure)에 대한 엄밀한 정의를 살펴보자.

 

Iteration Complexity란 "Class $\mathcal{A}$에 속하는 알고리즘들이 class $\mathcal{F}$ 속하는 함수들에 대하여 달성할 수 있는 가장 최고의 성능은 어떻게 되는가?"를 의미한다.

만약, $f$의 stationary point를 찾는 것이 목적인 상황이라면, iteration의 횟수 ( = oracle queries) 가 그 평가 지표가 될 것이고 Deterministic sequence에 대해서는 다음과 같이 표기할 수 있다.

 

$T_{\epsilon} (\{x_t\}_{t \in \mathbb{N}}, f) := \inf \{ t \in \mathbb{N} | \lVert \nabla f(x_t) \rVert \le \epsilon \}$

 

만약 stochastic algorithm이라면 random process $\{x_t \}$에 대해서 다음과 같이 표기할 수 있다.

 

$T_{\epsilon}(P, f) := \inf \{t \in \mathbb{N} | \mathbb{P}(\lVert \nabla f(x_s) \rVert > \epsilon$ for all $s \le t ) \le \frac{1}{2} \}$

 

즉, $t$보다 작은 모든 time step $s$에 대해서 gradient의 norm이 $\epsilon$보다 클 확률이 $\frac{1}{2}$보다 작은 t의 infimum 값이다. 

그리고 위 두 iteration complexity는 Markov's inequality로 연결된다.

이 부분은 넘어가도록 하겠다. 

 

그러면 알고리즘 class $\mathcal{A}$의 성능 평가 지표는 다음과 같이 정의된다.

$T_{\epsilon}(\mathcal{A}, \mathcal{F}) := \inf_A \sup_f T_{\epsilon}(A, f)$

 

위 $T_{\epsilon}(\mathcal{A}, \mathcal{F})$의 upper bound, lower bound를 구하는 것이 convergence rate을 유도하는 과정이다.

 

가장 일반적인 bound는 upper bound형태이다.

하지만 lower bound를 보이는 것 또한 매우 의미있는 주제이다.

참고로 first-order Oracle model에 대해서는 stochastic algorithm은 $\Omega (\frac{1}{\epsilon^4})$를 lower bound로 가짐이 알려져 있다.

즉, 예를 들어, $\epsilon = 0.1$을 $\epsilon = 0.01$로 줄이기 위해서는 최소 $10,000$번의 Iteration이 추가적으로 더 필요하다는 의미이다.

 

왜 lower bound를 유도하는 게 의미가 있을까?

 

예를 들어서 설명해보겠다. $x \in \mathbb{R}$에 대한 정보를 얻고 싶다.

이에 대해서 UP & DOWN 게임을 하듯이 $x$에 대해 가장 근접한 값을 찾아나가는 방식을 생각해보자.

 

여기서 우리는 '신'을 가정해서 $x$의 값이 구체적으로 무엇인지 알고 있는 존재를 가정해보자.

우리가 숫자를 말하면 그는 우리에게 오직 'up' , 'down' 정보만 제공해준다.

자, 내가 숫자 3을 말했더니 '신'이 UP이라 하였다. 

이 말은 숫자 3은 $x$의 lower bound가 된다는 의미이다.

내가 이어서 숫자 5를 말했더니 '신'이 UP이라 하였다.

역시 숫자 5가 $x$의 lower bound이다.

 

내가 이제 숫자를 키워서 10을 말했더니 '신'이 Down이라 하였다.

이는 숫자 10은 $x$의 upper bound라는 의미이다.

 

그럼 우리는 $5 < x < 10$을 알 수 있다.

실수 $x$는 아무리 작아봤자 5보다 작을 순 없다. 또 아무리 커봤자 10보다 클 순 없다.

 

이를 Iteration complexity의 lower bound와 upper bound에 대입해보자.

우리는 어떤 알고리즘 클래스의 Iteration complexity의 lower bound를 알면, 이 알고리즘이 $\epsilon$-stationary points를 찾는데 필요한 oracle queries의 '최소' 횟수를 아는 것이다.

즉, 이것보다 더 적은 횟수만으로는 $\epsilon$-stationary point를 찾을 수 없음을 알게 된다.

또 바꿔 말하면, 최고의 상황에서의 Iteration complexity를 아는 것이다.

 

반대로 upper bound를 안다는 것은, oracle queries의 '최대' 횟수를 아는 것이고 이는 곧 최악의 상황을 아는 것이다.

해당 알고리즘 클래스가 특정한 클래스의 함수들에 대해서 $\epsilon$-stationary points에 도달하기 위해 필요한 iteration 횟수가 커봤자 특정 upper bound를 넘지 않는다는 것이다. 즉 최악의 상황에서의 Iteration complexity를 아는 것이다.

 

* 최고의 상황/최악의 상황은 함수의 성질, 알고리즘의 성질 등에 따라서 좌우된다.

 

그렇다면 $\mathcal{A}$의 $\mathcal{F}$에 대한 lower bound를 아는 상태에서 어떤 알고리즘 ($A \in \mathcal{A}$) 의 upper bound를 구했더니 그것이 $\mathcal{A}$의 Iteration complexity lower bound와 큰 차이가 난다면, 이 알고리즘은 최적의 알고리즘이 아닐 수도 있다는 것이다. 

즉, 더 좋은 알고리즘 (= 빠른 수렴 속도를 가진 알고리즘)을 찾을 필요가 있다는 결론을 도출해준다.

그렇기 때문에 Iteration complexity의 lower bound를 유도하는 것은 중요한 주제이다.