Deep dive into Optimization: Proximal gradient descent (1)

 

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

 

이제 Deep dive into Optimization의 마지막 주제 'Proximal gradient descent'에 대해 이야기하고자 한다.

사실상 Convex optimization의 마지막 토픽이다.

 

Gradient descent는 objective function $f(x)$를 다음과 같은 iterative algorithm으로 최소화하는 방법을 이야기한다.

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

 

여기서는 현재 $f(x)$가 적어도 한 번 미분가능하다는 가정을 하고 있다.

하지만 만약 objective function이 미분 가능한 함수와 미분 불가능한 함수의 합으로 이뤄져 있다면 어떻게 될까?

다음과 같은 상황을 생각해보자.

$\min_x [f(x) := g(x) + h(x)]$

 

여기서 $g(x)$는 differentiable convex function이고, $h(x)$는 Non-differentiable convex function이다.

이러한 objective function $f(x)$는 어떻게 최소화할 수 있을까?

 

여기서 먼저 subgradient를 다시 간단하게 복습해보자.

subgradient는 다음과 같은 부등식을 만족하는 vectors $g$를 의미한다.

 

$f(v) \ge f(w) + \langle g, v - w \rangle$

 

subdifferential $\partial f(x)$는 $x$에서의 모든 subgradient의 집합이고, 만약 $f$가 미분이 가능하다면, subgradient는 gradient로 유일하다.

그렇다면 $f(x)$에서 $g(x)$는 미분 가능한 함수이므로 GD (또는 SGD) 등을 이용해서 최소화할 수 있고 $h(x)$는 subgradient를 이용하면 되지 않을까?

하지만 문제가 그렇게 단순하지 않은 것이 $h(x)$의 subgradient가 $g(x)$의 값을 오히려 증가시킬 수도 있다.

그렇기 때문에 단순하게 위와 같은 방법을 이용할 수는 없다.

 

그렇다면 어떻게 해야 할까?

우선 gradient descent가 유도된 식을 다시 한 번 보자.

 

$x_{t+1} = \arg \min_x f(x_t) + \langle \nabla f(x_t), x - x_t \rangle + \frac{1}{2 \eta} \lVert x - x_t \rVert^2$

 

위 식의 RHS 텀을 미분하고 $ = 0$으로 두어 방정식을 풀면 gradient descent 알고리즘이 유도된다.

하지만 우리는 지금 미분 불가능한 함수도 포함돼 있으므로 그것도 함께 고려해보자.

 

$x_{t+1} = \arg \min_x f(x_t) + \langle \nabla f(x_t),  x - x_t \rangle + \frac{1}{2 \eta} \lVert x - x_t \rVert^2 + h(x)$

$x_{t+1} = \arg \min_x \{ \frac{1}{2} \lVert x - (x_t - \eta \nabla f(x_t)) \rVert^2 + \eta h(x)$

 

 

첫 번째 등식에서 gradient descent 유도와 동일하게 미분 가능한 부분 (즉, $h(x)$를 제외한 부분)을 미분하였다.

두 번째 등식에서 $x - (x_t - \eta \nabla f(x_t)$를 최소화하는 $x$는 $x_t - \eta \nabla f(x_t)$이다.

하지만 우리는 동시에 $h(x)$도 최소화해야 하고 여기서 proximal operator를 도입하여 위 방정식의 해를 다음과 같이 표현한다.

 

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

 

위와 같은 방법을 우리는 proximal gradient algorithm이라 한다.

즉, 우선 $g(x)$를 최소화하기 위해 gradient descent를 수행한 이후, 나온 $x_t - \eta \nabla f(x_t)$에 대해서 proximal operator를 도입하여 연산해주는 것이다. 

이 알고리즘은 $g(x)$가 L-smooth할 때, 즉 $\nabla g(x)$가 Lipschitz continuous할 떄, step size $\eta < \frac{2}{L}$이면, $f(x)$의 최솟값을 향해 수렴하는 것이 증명돼 있다.

이러한 proximal gradient method의 가장 대표적인 예시가 Projected gradient method이다.

 

위의 $\min_x [f(x) = g(x) + h(x)]$에서 만약 h(x)가 다음과 같은 함수라고 생각해보자.

즉 어떤 convex set $C$에 대해서 $x$가 이 원소에 포함되면 $0$이고 만약 포함되지 않으면, $\infty$인 것이다.

이는 결국 constrained optimization problem $\min_{x \in C} f(x)$를 unconstrained optimization $\min_x f(x) + h(x)$로 바꿔 푸는 것이다. 그리고 이때 사용하는 방법이 projected gradient method이다.

 

$x_{t+1} = \arg \min_{x \in C} \lVert x - (x_t -\eta \nabla f(x_t)) \rVert^2$

 

즉, $x_t - \eta \nabla f(x_t)$로 gradient descent를 수행한 이후, set $C$로 projection 해주는 것이다.

이를 위 식에서는 거리가 제일 짧은 C 위의 임의의 원소 $x$를 찾는 것으로 표현한 것이다.

projection은 현재 위치에서 제일 거리가 짧은 지점으로 보내기 때문이다.

 

Projected gradient method

앞서 서술한 proximal gradient method를 다시 한 번 보자.

 

다음과 같이 표현된다.

 

$\min_x [f(x) := g(x) + h(x)]$

$x_{t + \frac{1}{2}} = x_t - \eta \nabla g(x_t)$

$x_{t+1} = \arg \min_x \{ \frac{1}{2} \lVert x - x_{t + \frac{1}{2}} \rVert^2 + \eta h(x) \}$

 

즉, $x_{t + \frac{1}{2}}$에서 너무 멀리 떨어지지 않은, 그러면서 $h(x)$를 최소화할 수 있는 $x$를 찾는 것이 proximal operator이다.

 

여기까지가 proximal gradient method의 소개였다.

다음 글에서는 가장 대표적인 예시인 ISTA에 대해서 설명하고자 한다.