fista

FISTA, short for Fast Iterative Shrinking-Thresholding Algorithm, is an optimization method designed to solve composite convex problems of the form minimize g(x) + h(x), where g is differentiable with a Lipschitz-continuous gradient and h is convex and proximable. It is an accelerated variant of ISTA (Iterative Shrinking-Thresholding Algorithm) and is widely used for sparse recovery and regularized learning.

The core idea of FISTA is to combine proximal gradient steps with Nesterov-style acceleration. At each iteration, a gradient descent step is taken on the smooth part g at an extrapolated point y_k, followed by a proximal operation with respect to h. A momentum term updates an auxiliary sequence y_k from the current and previous iterates to boost convergence. A typical update uses a sequence t_k governed by t_{k+1} = (1 + sqrt(1 + 4 t_k^2)) / 2, with x_k = prox_{gamma h}(y_k - gamma ∇g(y_k)) and y_{k+1} = x_k + ((t_k - 1)/t_{k+1})(x_k - x_{k-1}). The step size gamma often equals 1/L, where L is the Lipschitz constant of ∇g, and backtracking can be used to adapt gamma.

Convergence theory shows FISTA achieves an objective-value convergence rate of O(1/k^2), improving over ISTA’s O(1/k). This makes it particularly effective for large-scale problems such as L1-regularized least squares (lasso), compressed sensing, and various image processing tasks.

Variants exist, including backtracking FISTA, restart schemes to improve performance when strong convexity is present, and stochastic versions for large datasets. Limitations include sensitivity to the choice of L and potential oscillations if not properly restarted or if the problem is ill-conditioned.