Deep dive into Optimization : Duality and Mirror descent

 

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

 

오늘은 Fenchel conjugate의 마지막 글이자 Mirror descent를 시작하는 글이다.

 

Fenchel conjugate (= Convex conjugate)의 정의는 이제 다들 기억할 것이다.

$f(x)$의 conjugate을 $f^*(y)$라 하였을 때,

$f^*(y) := \sup_x \langle x, y \rangle - f(x)$

위의 식이 정의이다.

 

그리고 Fenchel biconjugate의 정의는 

$f^{**}(x) := \sup_y \langle x, y \rangle - f^*(y)$

이다.

 

몇 가지 중요한 성질로는 다음의 내용들이 있다.

 

$1$. $f$가 non-convex하더라도, $f^*$, $f^{**}$는 항상 convex이다.

$2$. $f$가 closed and convex라면, $f^{**} = f$이다.

$3$. $f$가 non-convex하다면, $f^{**}$는 $f$의 tightest convex lower bound이다. 

 

추가적인 Fenchel duality의 성질을 이야기하기 전에, "Subgradient"의 정의를 먼저 언급하고 넘어가자.

우리는 이 시리즈 초반부에서 '미분이 가능한' convex function의 정의를 배웠다.

$f(y) \ge f(x) + \langle \nabla f(x), y - x \rangle$

 

그렇다면 미분이 불가능하다면 어떻게 될까?

미분이 불가능한 convex function $f$의 subgradient는 다음과 같이 정의된다.

$f(y) \ge f(x) + \langle g, y - x \rangle$

 

위 부등식을 만족하는 $g = \partial f(x)$를 우리는 $f(x)$의 subgradient라고 부른다.

subgradient는 무수히 많이 있을 수 있으며, 미분이 가능할 때 subgradient는 유일하게 하나 존재하고, 그것이 gradient $\nabla f(x)$이다.

 

여기서 Fenchel conjugate의 'Subgradient'의 성질도 하나 나온다.

$\partial f^*(y) = \arg \max_x \langle x, y \rangle - f(x)$

 

만약 Fenchel conjugate이 미분 가능한 함수라면 Subgradient는 gradient로 유일하다.

위 등식이 의미하는 바는 conjugate의 gradient는 Conjugate을 최대화하는 Maximizer라는 의미이고, $\nabla f(x)$와 역함수 관계이다. 

 

다음은 Bregman divergence에 대해 이야기하겠다.

$f$가 convex하고 differentiable하다고 가정하자.

그렇다면 Bregman divergence는 다음과 같이 정의된다.

 

$D_f(u, v) = f(u) - f(v) - \langle \nabla f(v), u - v \rangle$

 

이때 $f(v)  + \langle \nabla f(v) , u - v \rangle$은 $f(x)$를 $v$에서 linearization한 것과 동일하다.

즉, Bregman divergence는 $f(u)$와 $f(x)를 linearization 한 직선의 $u$에서의 값과 차이로 정의된다.

 

여기서 우리는 convexity의 또 다른 필요충분 조건 관계를 유도할 수 있는데, 위의 convexity 정의를 고려하면, convex function에서 Bregman divergence는 항상 $0$ 이상임을 알 수 있다.

(하지만, Bregman divergence는 일반적으로 Symmetric이 성립하지 않고 따라서 'distance'로 볼 수 없다.)

 

또한 Dual norm에 대해서도 이전에 간단하게 정의를 언급하였었다.

어떤 norm $\lVert x \rVert$의 Dual norm은 다음과 같이 정의된다.

 

$\lVert y \rVert_* = \max_{\lVert x \rVert \le 1} \langle x, y \rangle$

 

그래서 L2-norm의 dual norm은 L2-norm이고, L1-norm의 dual norm은 L$\infty$-norm이다.

 

다음으로 Dual space에 대해 알아보자.

이는 선형대수학, 함수 해석학 등에서 나오는 개념으로 중요한 개념에 속한다.

 

일단 정의부터 이야기하면 다음과 같다.

어떤 Vector space $V$가 있을 때 이것의 Dual space는 모든 'linear functional' (선형 범함수)의 집합이다.

이때 linear function은 $v \in V$를 $\mathbb{R}$로 mapping해주는 함수를 의미한다. 그리고 이 linear functional을 다른 말로 'dual vector'라고 하고 이들은 dual space $V^*$의 원소들이다.

 

앞서 dual problem은 dual space에서 정의되는 optimization problem이다.

 

갑자기 Dual space는 왜 이야기했을까?

우리는 다음 글에서부터 Mirror descent를 살펴볼 예정인데 여기서 필요한 개념이기 때문이다.

Mirror descent는 두 공간, 즉 Primal space와 Dual space을 함께 고려하고 이 두 space는 'Mirror map'이라는 것으로 연결되어져 있다. 우리는 gradient descent를 통해서 Train loss function $\mathcal{L}(w)$을 최소화하는 알고리즘에 대해서 이전에 살펴보았다. 여기서 gradient는 현재 지점에서 가장 가파른 하강 방향을 가리키는 벡터이다.

 

그런데 이때 parameter가 이동하는 전체 지형, 즉 손실함수의 지형 (loss landscape)을 Mirror map을 통해서 바라본다면 어떨까? 그리고 이 Mirror map을 통해 변환된 공간 (Dual space)에서 gradient step을 진행하고 다시 원래의 primal loss landscape으로 돌아온다면?

이것이 Mirror descent의 핵심 아이디어이다.

즉, 일반적인 Gradient descent는 Loss landscape을 Primal space에서 정의한 채로 파라미터가 이동하는 것이고, Mirror descent는 Loss landscape을 Dual space에서 바라보고 파라미터가 이동하는 것이다.

 

 

https://www.semanticscholar.org/paper/Stochastic-Mirror-Descent-in-Variationally-Coherent-Zhou-Mertikopoulos/5cfc2401750216f189a2753f17ba7d392d386843

 

 

다음 글부터 Mirror descent를 본격적으로 이야기하도록 하겠다.