📂최적화이론

FISTA: 고속 반복 소프트 쓰레숄딩 알고리즘

알고리즘 ¹

$$ \argmin_{\beta} \left( {{ 1 } \over { 2 }} \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{1} \right) $$

위와 같은 BPDN, 혹은 라쏘 회귀 문제를 푸는 방법으로써, 다음의 업데이트 룰을 FISTA^{Fast Iterative Soft Thresholding Algorithm}라 한다. $$ \begin{align*} \gamma^{(k)} =& S_{\lambda} \left( \beta^{(k)} - \alpha X^{T} \left( X \beta^{(k)} - Y \right) \right) \\ t_{k+1} =& {{ 1 + \sqrt{ 1 + 4 t_{k}^{2} }} \over { 2 }} \\ \beta^{(k+1)} =& \gamma^{(k)} + \left( {{ t_{k} - 1 } \over { t_{k+1} }} \right) \left( \gamma^{(k)} - \gamma^{(k-1)} \right) \end{align*} $$ 여기서 $\alpha$ 는 스텝 사이즈^{step size}고, 벡터화된^vectorized 소프트 쓰레숄딩 $S_{\lambda} : \mathbb{R}^{n} \to \mathbb{R}^{n}$ 는 벡터의 각 성분별로 소프트 쓰레숄딩 $\eta_{S} \left( x ; \lambda \right)$ 을 적용하는 함수다. 초기값으로는 $\gamma^{(1)} = \beta^{(0)}$ 와 $t_{1} = 1$ 을 사용할 수 있다.

설명

FISTA는 프락시멀 그래디언트 메서드의 일종으로, 모멘텀 기법을 통해 ISTA를 발전시킨 알고리즘이다. $\left( \gamma^{(k)} - \gamma^{(k-1)} \right)$ 는 생긴 그대로 관성의 방향을 계산해서 경사하강을 가속하는 역할을 한다.

성능적으로는 FISTA가 ISTA보다 훨씬 뛰어나고, 실제로 구현도 그리 복잡하지 않아 라쏘 문제를 풀 때 굉장히 많이 쓰인다. FISTA를 소개한 논문은 2025년 기준 인용수가 15000회를 넘었다.