📂Optimization

FISTA: Fast Iterative Shrinkage-Thresholding Algorithm

Algorithm ¹

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

As a method to solve the above BPDN, or Lasso regression problem, the following update rule is called FISTA. $$ \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*} $$ Here $\alpha$ is the step size, and the vectorized soft-thresholding $S_{\lambda} : \mathbb{R}^{n} \to \mathbb{R}^{n}$ is the function that applies the soft thresholding $\eta_{S} \left( x ; \lambda \right)$ to each component of the vector. As initial values one can use $\gamma^{(1)} = \beta^{(0)}$ and $t_{1} = 1$.

Description

FISTA is a variant of the proximal gradient method that accelerates ISTA via a momentum technique. $\left( \gamma^{(k)} - \gamma^{(k-1)} \right)$ computes the inertial direction as-is and serves to accelerate the gradient descent.

In terms of performance, FISTA is substantially superior to ISTA, and its implementation is not very complicated, so it is widely used for solving Lasso problems. The paper introducing FISTA had been cited over 15,000 times as of 2025.