Deep dive into Optimization : Proximal gradient descent (2)

 

 

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

 

 

오늘은 Proximal operator를 사용한 Proximal gradient descent 중 가장 대표적인 알고리즘인 ISTA에 대해 이야기하고자 한다.

우선 Proximal gradient descent는 다음과 같은 상황을 풀 때 적용되는 gradient descent의 일반화된 알고리즘이라 할 수 있다.

 

$\min F(x) = f(x) + g(x)$

 

여기서 $f(x)$는 convex하고 differentiable한 함수이며 L-smooth하다.

$g(x)$는 convex하지만 non-differentiable하다.

 

위 objective function인 $F(x)$를 minimize할 때, 우리는 Proximal operator를 사용할 수 있다.

Proximal operator의 정의는 다음과 같다.

 

$prox_g(v) = \arg \min_x \{ g(x) + \frac{1}{2} \lVert x - v \rVert^2 \}$

 

즉, 함수 $g(x)$에 대해서 proximal operator $prox_g(v)$는 $g(x)$를 최소화하면서 동시에 $v$에서 멀리 떨어져 있지 않은, 거리가 최소인 $x$를 의미한다.

 

구체적으로 예를 들어서 살펴보면 만약 $g(x)$가 벡터 $x$의 L1-norm 함수라고 하자.

L1-norm은 $x$의 각 성분들의 절댓값의 합이다.

 

$g(x) := \lVert x \rVert_1 := |x_1| + |x_2| + \cdots + |x_n|$

 

이 함수 $g(x)$에 대한 proximal operator는 어떻게 될까?

이는 soft-threshodling이라는 아주 유명한 개념과 연결된다.

우선, L1-norm을 최소화하는 것은 결국 각 성분들이 0에 가까워지게 만드는 것을 의미하고, 벡터 $x$가 sparse하게 되도록 만든다.

즉, $g(x)$에 대한 proximal operator는 $x$의 각 성분들이 0에 가까워지게 (sparse) 만드는 연산이 된다.

어떤 threshold $\lambda$에 대해서 soft-thresholding operator $S_{\lambda}(x_i)$는 다음과 같이 정의된다.

 

$S_{\lambda}(x_i) = sign(x_i) \times \max \{ |x_i| - \lambda, 0 \}$

 

 연산에서 $\max \{ |x_i| - \lambda , 0  \}$ 부분은 $x_i$가 $\lambda$보다 작을 때 $0$이 나오고, 그렇지 않으면 $|x_i| - \lambda$가 나올 것이다.

그 다음으로 sign$(x_i)$는 $x_i$의 부호함수로서 양수이면 $+1$, 음수이면 $-1$이 된다.

즉, 원래 벡터의 방향 (각 성분의 부호)를 유지해주면서 최대한 작게 만들어나가는 것이다.

(만약 벡터의 성분이 우리가 정의한 작은 값, 즉 threshold $\lambda$보다 작다면 그 성분은 $0$이 될 것이고 우리가 앞서 살펴본 L1-norm을 최소화하는 것은 해당 벡터를 sparse하게 만든다는 것과 일치하게 된다.)

 

그렇다면 다음과 같은 $F(x)$를 최소화하는 optimization problem을 가정해보자.

 

$\min_x F(x) := \min_x \{ \frac{1}{2} \lVert Ax - b \rVert_2^2 + \lambda \lVert x \rVert_1 \}$

 

이 문제는 사실 잘 알려진 문제인데, Lasso problem이라고 한다.

여기서 $A$는 matrix, $x, b$는 vector, $\lambda$는 L1-regularization의 강도를 결정하는 non-negative scalar이다.

여기서 $f(x) = \lVert Ax - b \rVert_2^2$는 미분이 가능하며, $g(x) = \lVert x \rVert_1$은 미분이 불가능하다.

 

ISTA 알고리즘은 다음과 같이 문제를 푼다. ($\eta$를 step-size라 해보자.)

 

$1$. $x_0$ 시작점으로 초기화를 한다. (initialization)

$2$. 수렴할 때까지 매 iteration $t = 0, 1, \cdots, $마다 다음 과정을 반복한다.

• $f(x)$의 $x_t$에서의 gradient를 계산한다. ($\nabla f(x_t)$)
• $x_t - \eta \nabla f(x_t)$를 수행한다. 이 지점을 $y$라 하자.
• $y$에서 $g(x)$에 대해 proximal operator 연산을 수행한다. 즉, $x_{t+1} = prox_{\eta \lambda \times g}(y)$이다.

 

여기서 proximal operator $prox_{\lambda \times g}(y)$는 $y$의 각 성분들 $y_i$에 대해 다음과 같이 정의된다.

$sign(y_i) \times \max \{ |y_i| - \eta \lambda , 0 \}$

 

이를 우리는 ISTA 알고리즘이라고 한다.

 

ISTA는 매우 유명한 알고리즘으로서, 좋은 성능을 가지고 있지만 단점이 있다.

그건 수렴 속도 (convergence rate)이 매우 느리다는 점이다. 이러한 문제를 다루기 위해, Faster ISTA (FISTA)도 있는데 이는 convergence rate을 빠르게 하기 위해 momentum을 활용했다.

본 글에서 이것까지 다루지는 않겠다.

 

이로서 Proximal gradient descent를 마무리하게 되었다.