Deep dive into Optimization : Mirror descent (2)

 

 

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

 

 

 

오늘부터는 본격적으로 Mirror descent에 대한 글을 시작하고자 한다.

 

예전 Gradient descent 챕터에서 이야기하였듯이 Gradient descent는 objective function $f(x)$를 First-order approximation한 함수를 최소화하는 알고리즘이다.

 

RHS의 $f(x_t) + \langle \nabla f(x_t), x - x_t \rangle$이 First-order approximation이고 $\frac{1}{2} \lVert x - x_t \rVert^2$는 First order approximation의 오차가 매우 커지는 것을 방지하기 위해 $x$가 $x_t$와 너무 멀리 떨어지는 것을 방지하는 term이다. 

 

여기서 parameter들 사이의 distance는 L2-norm 즉 Euclidean distance이다.

여기서 Euclidean distance를 Bregman divergence로 바꿔본다면 어떻게 될까? 앞선 글에서 이야기하였듯 Convex function $f$에서의 Bregman divergence는 다음과 같이 정의된다.

 

$D_f(y||x) := f(y) - f(x) - \langle \nabla f(x), y - x \rangle$

 

즉 원래의 함숫값과 First-order approximation 함수의 함숫값의 '차이'를 Bregman divergence로 정의하고 convex function은 이 값이 항상 Non-negative하다는 성질이 있다. 또한 Bregman divergence를 $y$를 변수로 하는 함수로 본다면 이 함수 또한 convex function이다.

 

그러면 Gradient descent에서 $\frac{1}{2} \lVert x - x_t \rVert^2$를 Bregman divergence로 바꾸면 어떻게 될까?

 

역시나 RHS term을 최소화하기 위해 이를 미분해서 $= 0$으로 두고 풀면 다음과 같이 나온다.

 

$x_{t+1} = \nabla h^{-1} (\nabla h(x_t) -  \nabla f(x_t))$

 

지금은 일단 step-size는 무시하자. 

 

여기서 Bregman divergence를 정의하는 convex function $h$를 어떤 것으로 정의하냐에 따라 구체적인 알고리즘이 나오게 되는 것이다.

 

여기까지는 parameter distance를 'Bregman divergence'로 정의한다는 관점에서 Mirror descent를 정의하였다.

이제는 다른 관점에서 Mirror descent를 정의해보자.

사실 앞선 글에서 이미 한 번 이야기하였었다.

 

일반적인 Gradient descent는 다음과 같이 Parameter update가 진행된다.

$x_{t+1} = x_t - \eta \nabla f(x_t)$

 

하지만 여기서 Gradient는 선형 범함수 (linear functional)로서 원래의 Parameter space ( = Primal space)가 아닌, dual space에서 정의된다. Gradient decsent는 primal space가 L2-norm을 기반으로 한 Euclidean space이고 dual norm 또한 L2-norm이기 때문에 primal space의 원소 $x_t$와 dual space의 원소 $\nabla f(x_t)$를 함께 연산하여도 괜찮았다.

하지만 다른 norm들에 대해서는 $x_t$와 $\nabla f(x_t)$를 바로 더하는 연산을 하는 것은 문제를 야기할 수 있다.

 

그래서 Mirror descent에서는 'Mirror map'을 이용하여 dual space에서 parameter update를 진행한다.

 

구체적인 알고리즘은 다음과 같다.

 

$1$. primal space $x_t$를 dual space $\theta_t$로 mirror map을 이용하여 mapping한다.

 

$2$. dual space에서 gradient step을 진행한다.

$\theta_{t+1} = \theta_t - \eta \nabla f(x_t)$

 

$3$. mirror map의 inverse를 이용해서 $\theta_{t+1}$을 $x_{t+1}$로 mapping한다.

 

$4$. 만약 constrained optimization problem이라면 $x_{t+1}$을 feasible region set으로 Projection한다.

이때 우리는 Bregman divergence를 사용해서 Projection을 한다.

 

자, 그러면 여기서 Mirror map은 어떻게 정의해야 할까?

먼저 norm의 정의를 만족하는 임의의 norm이 있고, 이 norm에 대해서 $\alpha$-strongly convex function $h$가 있다고 하

자. (norm의 정의, dual norm의 정의는 이전 글에서 이야기하였으므로 넘어가자.) 

 

이전에도 이야기하였듯 $\alpha$- strongly convex하다는 것은 다음과 같은 inequality를 만족하는 함수이다.

 

$h(y) \ge h(x) + \langle \nabla h(x), y - x \rangle + \frac{\alpha}{2} \lVert y - x \rVert^2$

 

여기서 $\lVert y - x \rVert^2$는 L2-norm일수도 있지만, 임의의 norm일 수도 있다.

 

고정된 norm 함수와 $h$에 대해 mirror map은 다음과 같이 정의된다.

 

$\nabla h : \mathbb{R}^n \rightarrow \mathbb{R}^n$

 

그렇다면 $\theta_t$와 $x_t$ 사이의 mapping도 다음과 같이 정의된다.

 

$\theta_t = \nabla h(x_t)$, $x_{t+1} = (\nabla h)^{-1} (\theta_{t+1})$

 

여기서 $h$는 distance-generating function이라고 부른다.

 

정리하면 Mirror map은 다음을 만족하는 함수 $ h : \mathcal{D} \rightarrow \mathbb{R}$이다.

여기서 $\mathcal{D}$는 convex open set이다.

 

$1$. $h$는 strong convex하며 differentiable하다.

$2$. $\nabla h$는 $\mathcal{D}$의 boundary에서는 발산한다. 즉, 다음과 같다.

$\lim_{x \rightarrow D} \lVert \nabla h(x) \rVert = + \infty$

 

이처럼 Mirror descent는 L2-norm 기반의 Euclidean distance를 일반화된 norm에 대한 distance $h$로 대체한 알고리즘이라 할 수 있다. 

 

 

다음 글에서는 Proximal gradient에 대해 이야기하도록 하겠다. 이제 Deep dive into optimization 시리즈도 끝이 보인다..