09-02 Convergence analysis

Convergence analysis

이 절에서는 proximal gradient descent의 수렴을 분석한다.

Convergence Analysis

Objective 함수 $f(x)=g(x)+h(x)$에 대해 다음 사항을 가정한다.

• $g$는 convex, differentiable하며 dom$(g)={\mathbb{R}}^n$, $\mathrm{\nabla }g$는 Lipschitz continuous하다 ($L>0$).
• $h$는 convex이고 ${\text{prox}}_t(x)=\underset{z}{\text{argmin}}\{\parallel x-z{\parallel }_2^2/(2t)+h(z)\}$가 계산되어야 한다.

Convergence Theorem

Proximal gradient descent는 fixed step size $t\le 1/L$에 대해 다음 식을 만족한다. $$\begin{array}{r}f(x^{(k)})-f^{\ast }\le \frac{\Vert x^{(0)}-x^{\ast }{\Vert }_2^2}{2tk}\end{array}$$

Proximal gradient descent는 $O(1/k)$ 또는 $O(1/ϵ)$의 수렴 속도를 갖는데 이는 gradient descent와 동일한 성능이다. 단, 이 성능은 반복 횟수 기준이지 연산 횟수 기준이 아니라는 점을 유념하자. (연산 횟수는 함수 $h$에 따라 적을수도 많을 수도 있다.)

Backtracking line search

Proximal gradient descent의 backtracking line search 방법은 gradient descent와 비슷하지만 함수 $f$가 아닌 smooth 파트인 $g$에 대해서만 작동한다.

먼저 파라미터를 $0<\beta <1$로 설정하고 $t=1$로 시작한다. 각 반복에서 다음 조건을 만족하는 동안 $t$를 $t=\beta t$로 줄이고, 다음 조건을 만족하지 않으면 proximal gradient descent를 update한다.

$$\begin{array}{r}g(x-t{G}_t(x))>g(x)-t\mathrm{\nabla }g(x{)}^T{G}_t(x)+\frac{t}{2}\parallel G_t(x){\parallel }_2^2\end{array}$$

이 backtracking 조건은 다음 step 위치인 $x-t{G}_t(x)$에서의 함수 $g$의 값이 함수 $g$의 Taylor 2차 근사 함수의 값보다 클 때를 의미한다.

이 식에서 $G_t(x)=\mathrm{\nabla }g(x)$이라면 $g(x-t\mathrm{\nabla }g(x))>g(x)-\alpha t\Vert \mathrm{\nabla }g(x){\Vert }_2^2$가 되므로 gradient descent의 backtracking 조건과 동일해진다는 것을 알 수 있다.

참고 : Gradient descent의 backtracking에 대한 자세한 내용은 06-02-02 backtracking line search 참조

Backtracking line search 알고리즘

이 내용을 알고리즘으로 정리하면 다음과 같다. (단, $\mathrm{\nabla }x=-t{G}_t(x)$)

1. 파라미터를 초기화한다. ($0<\beta <1$, $0<\alpha \le 1/2$)
2. 각 반복에서 $t=t_{\text{init}}$로 초기화 한다. ($t_{\text{init}}=1$)
3. 조건 $g(x-t{G}_t(x))>g(x)-t\mathrm{\nabla }g(x{)}^T{G}_t(x)+\frac{t}{2}\parallel G_t(x){\parallel }_2^2$을 만족하면 $t=\beta t$로 줄인다. 이 조건이 만족되는 동안 3을 반복한다.
4. Gradient descent update $x^{+}=x-t{G}_t(x)={\text{prox}}_t(x-t\mathrm{\nabla }g(x))$를 실행한다.
5. 종료 조건을 만족하지 않으면 2로 간다.

Proximal gradient descent에서 backtracking을 할 때 $G_t(x)$이 반복적으로 계산되기 때문에 실제 $G_t(x)$ 안에 포함된 proximal mapping이 반복적으로 계산된다. Proximal mapping은 계산 비용이 매우 높기 때문에 전체적인 backtracking 계산 비용은 높다고 할 수 있다.

Convergence Theorem

앞의 가정과 동일한 가정 하에 backtracking line search 방식도 같은 성능을 구할 수 있다.

Proximal gradient descent는 backtracking line search에 대해 다음 식을 만족한다. Step size는 $t_{\text{min}}=\text{min}\{1,\beta /L\}$이다.

$$f(x^{(k)})-f^{\star }\le \frac{\Vert x^{(0)}-x^{\star }{\Vert }_2^2}{2t_{min}k},t_{\text{min}}=\text{min}\{1,\beta /L\}$$