23-04 Example: Pathwise coordinate descent for lasso

이번 절에서는 Pathwise coordinate descent for lasso에 대한 개요를 간단히 소개하도록 한다 [Friedman et al. (2007)] [Friedman et al. (2009)].

Lasso regression problem: $\underset{\beta }{min}\frac{1}{2}\Vert y-X\beta {\Vert }_2^2+\lambda \Vert \beta {\Vert }_1$

07-03-03 Example: Lasso Optimality Condition에서 lasso regression 문제에 대한 optimality condition을 유도해 보았다. 위 문제에 대한 최적해는 다음의 조건을 만족한다.

$$\begin{array}{rl}{X}_1^T(y-X\beta )& =\lambda v_1\\ X_2^T(y-X\beta )& =\lambda v_2\\ \dots \\ X_p^T(y-X\beta )& =\lambda v_p\end{array}$$

Note: $X_i,i\in \{1,2,\dots ,p\}$는 주어진 행렬 $X$의 $i$번째 열(column) 데이터를 의미한다.

여기서 $v=(v_1,v_2,\dots ,v_p)$는 $\beta =({\beta }_1,{\beta }_2,\dots ,{\beta }_p)$에 대한 subgradient다.

$$v_i,i\in \{1,2,\dots ,p\}=\{\begin{array}{ll}\{1\}& \text{if }{\beta }_i>0\\ \{-1\}& \text{if }{\beta }_i<0\\ [-1,1]& \text{if }{\beta }_i=0\end{array}$$

이 optimality condition에 의해 $\beta$의 각 원소가 현재 최적상태에 해당하는지 파악할 수 있다. Coordinate descent 알고리즘을 이용하면 아직 최적상태에 도달하지 못한 원소만을 업데이트하는 방식으로 좀 더 효율적으로 lasso 문제를 푸는 것이 가능해진다. 또한 $\lambda$의 값이 클수록 lasso regression 문제에서 coordinate descent 알고리즘이 더 빨리 동작하는 경향성을 활용하여 $\lambda$를 점점 줄여가는 방식(warm start)으로 해에 더욱 빠르게 접근한다.

Algorithm

Outer loop (pathwise strategy):

• ${\lambda }_1>{\lambda }_2>\cdots >{\lambda }_r$의 순서를 따라 최적해를 계산한다.
• Tuning parameter ${\lambda }_k$에서 계산된 결과를 ${\lambda }_{k+1}$에 대한 coordinate descent algorithm을 초기화하는데 사용한다. (warm start)

Inner loop (active set strategy):

• 하나 혹은 적은 수의 coordinate cycle을 시행한다. 그리고 0이 아닌 $\beta$의 원소를 active set $A$에 기록한다.
• $A$에 기록된 원소들에 대해서만 수렴할 때까지 coordinate cycle을 시행한다.
• $\beta$의 모든 원소들에 대해 optimality condition을 확인한다. 조건을 만족하지 않는 원소가 있으면 $A$에 추가하고 step 1으로 다시 돌아간다.

Notes

• 통상적으로 pathwise strategy는 문제에서 주어진 $\lambda$에 대한 해를 바로 구하는 것보다 훨씬 효율적으로 동작한다.
• Active set strategy는 sparsity에 대해 이점이 있다. 이 때문에 coordinate descent는 ridge regression보다 lasso regression에서 훨씬 더 빠르게 동작한다. (참고: ridge regression과 lasso regression의 경향성 분석)
• Pathwise coordinate descent for lasso는 lasso regression 문제에 대해 가장 빠르다고 알려진 다른 알고리즘들에 비견될만큼 빠르게 동작한다.