Proximal Gradient Method (ISTA) and FISTA
Proximal Gradient Method (ISTA) and its acceleration (FISTA)
Goal of this page
We derive the proximal gradient method (ISTA), which solves a composite minimization whose objective is a sum of a smooth term and a nonsmooth term $F(x)=f(x)+g(x)$ without breaking the gradient method, together with its accelerated version FISTA. Starting from the optimality condition expressed through subdifferentials, the method arises naturally as forward-backward splitting. In one article we cover the convergence rates (ISTA is $O(1/k)$, FISTA is $O(1/k^2)$), implementation techniques, and applications such as Lasso, total variation, and compressed sensing.
Prerequisites
- Proximal operator — definition, properties, and closed forms of the proximal map $\operatorname{prox}_{\lambda g}$ (the central tool of this article)
- Convergence rates and acceleration in numerical optimization — the gradient method and Nesterov acceleration in the smooth case, and the rate framework
- Basics of convex analysis (the subdifferential $\partial g$, $L$-smoothness, $\mu$-strong convexity)
1. The stage: composite minimization
In modern optimization the objective is very often written as a sum of two terms with different natures:
$$\min_{x\in\mathbb{R}^n}\; F(x) = f(x) + g(x).$$Here $f$ is a smooth convex function (differentiable with an $L$-Lipschitz gradient, e.g. the squared error $\tfrac12\|Ax-b\|^2$), while $g$ is a nonsmooth convex function (convex but with points where it is not differentiable, e.g. the $\ell_1$ norm $\|x\|_1$, or the indicator function $\iota_C$ of a convex set).
There is a reason $g$ appears. The $\ell_1$ regularizer makes the solution sparse (Lasso), total variation (TV) preserves the edges of an image, and an indicator function encodes a constraint. Each of them "enforces a desired structure," but the price is a corner where the function is not differentiable.
Why the gradient method cannot be used directly
Since $g$ is not differentiable, $\nabla F = \nabla f + \nabla g$ is undefined, so gradient descent $x_{k+1}=x_k-\eta\nabla F(x_k)$ cannot be written. The subgradient method (replacing $\nabla g$ by a subgradient) can be used, but because of the nonsmoothness it converges slowly, at $O(1/\sqrt{k})$. We need a different tool that handles the structure of $g$ whole——that tool is the proximal map.
2. Optimality condition and forward-backward splitting
A minimizer $x^\star$ of $F=f+g$ satisfies the optimality condition expressed with the subdifferential,
$$0 \in \nabla f(x^\star) + \partial g(x^\star)$$(the gradient for the smooth $f$, the subdifferential for the nonsmooth $g$). Rewriting this inclusion with an arbitrary step size $\eta>0$ inserted gives
$$0 \in \eta\nabla f(x^\star) + \eta\,\partial g(x^\star) \;\Longleftrightarrow\; x^\star - \eta\nabla f(x^\star) \in x^\star + \eta\,\partial g(x^\star) = (I+\eta\partial g)(x^\star).$$Applying the resolvent $(I+\eta\partial g)^{-1}=\operatorname{prox}_{\eta g}$ (the proximal map; see Proximal operator §5) to both sides shows that $x^\star$ satisfies the following fixed-point equation:
Theorem 2.1 (Fixed-point characterization of composite optimality)
For a proper closed convex function $g$ and $\eta>0$, $x^\star$ is a minimizer of $F=f+g$ if and only if
$$x^\star = \operatorname{prox}_{\eta g}\!\bigl(x^\star - \eta\nabla f(x^\star)\bigr).$$The right-hand side has two stages. The quantity $x-\eta\nabla f(x)$ is a forward (explicit) gradient step along $f$, and $\operatorname{prox}_{\eta g}$ is a backward (implicit) step along $g$. This decomposition is called forward-backward splitting. The essential point is that the optimality condition is exactly the fixed point of the "step forward, then step backward" map; iterating this map approaches a minimizer——that is the proximal gradient method of the next section.
3. The proximal gradient method (ISTA)
We use the fixed-point map of Theorem 2.1 directly as an iteration:
Algorithm 3.1 (Proximal gradient method / ISTA)
Initial point $x_0$, step size $\eta=1/L$ ($L$ is the Lipschitz constant of $\nabla f$). For $k=0,1,2,\ldots$,
$$x_{k+1} = \operatorname{prox}_{\eta g}\!\bigl(x_k - \eta\nabla f(x_k)\bigr).$$Each iteration is just "take a step with the gradient of $f$, then pull back with the proximal map of $g$." If the proximal map of $g$ is available in closed form (e.g. soft thresholding for $\ell_1$), then one iteration costs about the same as a gradient method (the evaluation of $\nabla f$ dominates). When $g=\|\cdot\|_1$, the iteration repeats shrinkage and thresholding, and is called ISTA (Iterative Shrinkage-Thresholding Algorithm).
Theorem 3.2 (Convergence of ISTA)
If $f$ is $L$-smooth convex, $g$ is proper closed convex, and $\eta=1/L$, then the function-value gap satisfies
$$F(x_k) - F(x^\star) \le \dfrac{L\,\|x_0 - x^\star\|^2}{2k}$$That is, $O(1/k)$ convergence, the same order as the gradient method for smooth convex functions. If in addition $f$ is $\mu$-strongly convex, the convergence becomes linear, $O\bigl((1-\mu/L)^k\bigr)$.
The proximal step seen through the Moreau envelope
The proximal map is equivalent to a gradient step of the Moreau envelope $M_{\eta g}$, a smooth rounding of $g$ (see Proximal operator §8). Hence ISTA can be read as "a gradient step on $f$ plus a (virtual) gradient step on $g$," pulling the nonsmooth $g$ into the framework of smooth minimization. This is why it attains the same $O(1/k)$ speed as the smooth case.
4. Acceleration——FISTA
In the smooth case, Nesterov's accelerated gradient method (NAG) improved $O(1/k)$ to $O(1/k^2)$ merely by introducing an extrapolation (momentum) term (see Convergence rates and acceleration §4). Transplanting the same extrapolation idea into the proximal gradient method yields FISTA (Fast ISTA, Beck & Teboulle 2009).
Algorithm 4.1 (FISTA)
Initialization: $x_0$, $y_1=x_0$, $t_1=1$. For $k=1,2,\ldots$,
- $x_k = \operatorname{prox}_{(1/L)g}\!\bigl(y_k - \tfrac{1}{L}\nabla f(y_k)\bigr)$ (forward-backward step at the predicted point $y_k$)
- $t_{k+1} = \dfrac{1+\sqrt{1+4t_k^2}}{2}$
- $y_{k+1} = x_k + \dfrac{t_k-1}{t_{k+1}}\,(x_k - x_{k-1})$ (extrapolation = momentum)
The only difference from ISTA is that the gradient and proximal steps are evaluated not at the current point $x_k$ but at the predicted point $y_k$ extrapolated from the difference with the previous step. This single extra effort makes the convergence one order faster:
Theorem 4.2 (Convergence of FISTA)
$$F(x_k) - F(x^\star) \le \dfrac{2L\,\|x_0 - x^\star\|^2}{(k+1)^2}$$That is, $O(1/k^2)$. It is the same order as NAG in the smooth case, and the number of iterations required for an $\varepsilon$-optimal solution improves from ISTA's $O(1/\varepsilon)$ to $O(1/\sqrt{\varepsilon})$.
A note on monotonicity
Because of the extrapolation, the function value $F(x_k)$ of FISTA does not necessarily decrease monotonically (it may oscillate). In practice one often recovers monotonicity with a monotone variant (MFISTA) or with the restart of the next section.
At a glance, ISTA and FISTA compare as follows.
| ISTA | FISTA | |
|---|---|---|
| Convergence rate (convex $F$) | $O(1/k)$ | $\mathbf{O(1/k^2)}$ |
| Cost per iteration | one $\nabla f$ + one $\operatorname{prox}$ | same (one $\nabla f$ + one $\operatorname{prox}$) |
| Extrapolation (momentum) | none | yes (evaluated at the predicted point $y_k$) |
| Monotonicity of $F$ | monotone decrease | nonmonotone (may oscillate) → restored by restart |
| Iterations for an $\varepsilon$-optimal solution | $O(1/\varepsilon)$ | $O(1/\sqrt{\varepsilon})$ |
5. Placing the convergence rates
We organize the speeds of first-order methods for composite problems in correspondence with the smooth case (Convergence rates and acceleration).
| Method | Convex $F$ | Strongly convex $F$ | Remark |
|---|---|---|---|
| Subgradient method | $O(1/\sqrt{k})$ | $O(1/k)$ | does not use the structure of $g$ |
| Proximal gradient (ISTA) | $O(1/k)$ | $O((1-\mu/L)^k)$ | same as the smooth gradient method |
| FISTA | $\mathbf{O(1/k^2)}$ | $O((1-\sqrt{\mu/L})^k)$ | same optimal order as Nesterov acceleration |
The important fact is that nonsmoothness does not harm the speed of convergence. Because the proximal map handles $g$ whole, ISTA attains the same $O(1/k)$ as the smooth gradient method, and FISTA attains the same $O(1/k^2)$ as Nesterov. The rate $O(1/k^2)$ is asymptotically optimal for first-order methods in light of the Nemirovski-Yudin lower bound (Convergence rates and acceleration §6), and FISTA carries that optimal order over to nonsmooth composite problems unchanged.
6. Implementation techniques
6.1 Automatic step-size adjustment (backtracking)
When the Lipschitz constant $L$ is unknown, or a global $L$ is too large, one searches for a local $L$ at each iteration. Doubling a trial value $\hat L$, one redoes the shrunken step until the following descent lemma holds:
$$F(x_{k+1}) \le f(y_k) + \langle \nabla f(y_k),\, x_{k+1}-y_k\rangle + \tfrac{\hat L}{2}\|x_{k+1}-y_k\|^2 + g(x_{k+1}).$$This preserves $O(1/k^2)$ without knowing $L$ in advance (the backtracking version of Beck & Teboulle 2009).
6.2 Restart
To suppress the nonmonotone oscillation of FISTA, a restart that resets the extrapolation coefficient to $t_k\leftarrow 1$ is effective. The lighter the test, the better:
- Function-value restart: restart once $F(x_{k+1})>F(x_k)$
- Gradient restart: restart if $\langle y_k-x_{k+1},\,x_{k+1}-x_k\rangle>0$ (no re-evaluation of the function value is needed, so it is light)
Even when strong convexity is unknown, FISTA with restart often shows an almost linear rate in practice.
6.3 When the proximal map has no closed form (inexact prox)
When the proximal map of $g$ cannot be obtained analytically (e.g. overlapping group regularization, TV), one solves a small optimization inside to approximate the proximal map. If the approximation error decreases to $0$ fast enough along the iterations, the outer $O(1/k^2)$ is preserved (inexact proximal gradient). In large-scale learning where $\nabla f$ is available only stochastically, the stochastic proximal gradient method (prox-SGD) is used.
7. Representative applications and their proximal maps
The proximal gradient method is practical because the proximal maps of representative regularizers $g$ can be written in closed form (derivations and a list are in Proximal operator §7).
| Problem | Nonsmooth term $g$ | $\operatorname{prox}_{\eta g}$ |
|---|---|---|
| Lasso regression | $\lambda\|x\|_1$ | soft thresholding $S_{\eta\lambda}(v)$ |
| Group Lasso | $\lambda\sum_g\|x_g\|_2$ | group soft thresholding (block by block) |
| Nonnegativity-constrained regression | $\iota_{\{x\ge 0\}}(x)$ | $\max(v,0)$ (componentwise projection) |
| Box constraints | $\iota_{[l,u]}(x)$ | $\operatorname{clip}(v,l,u)$ |
| Total variation (TV) image restoration | $\lambda\,\mathrm{TV}(x)$ | no closed form → inexact prox (§6.3) |
Example 7.1 (Lasso with ISTA/FISTA)
For Lasso, $f(x)=\tfrac12\|Ax-b\|^2$ ($L=\lambda_{\max}(A^\top A)$) and $g(x)=\lambda\|x\|_1$. One iteration of ISTA is
$$x_{k+1} = S_{\eta\lambda}\!\bigl(x_k - \eta A^\top(Ax_k-b)\bigr),$$that is, "take a step with the gradient of the residual, then crush small components to $0$ by soft thresholding." Accelerating this with the extrapolation of FISTA gives the standard algorithm widely used in compressed sensing and sparse regression.
Summary
Key points of this chapter
- Composite minimization $F=f+g$ ($f$ smooth convex, $g$ nonsmooth convex) cannot use the gradient method directly
- The optimality condition $0\in\nabla f+\partial g$ is equivalent to the fixed point of the forward-backward map $\operatorname{prox}_{\eta g}(x-\eta\nabla f(x))$
- Iterating this map is the proximal gradient method (ISTA), with $O(1/k)$ convergence (the same as the smooth gradient method)
- Adding Nesterov's extrapolation gives FISTA with $O(1/k^2)$, the optimal order for first-order methods
- Nonsmoothness does not harm the speed——because the proximal map handles $g$ whole
- The implementation essentials are backtracking, restart, and inexact prox
- Lasso, group Lasso, TV, constrained problems, and more: applicable at large scale as long as the proximal map is computable
References
- Beck, A., & Teboulle, M. (2009). "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems". SIAM J. Imaging Sciences, 2(1), 183–202.
- Parikh, N., & Boyd, S. (2014). Proximal Algorithms. Foundations and Trends in Optimization, 1(3), 127–239. Online
- Combettes, P. L., & Wajs, V. R. (2005). "Signal Recovery by Proximal Forward-Backward Splitting". Multiscale Modeling & Simulation, 4(4), 1168–1200.
- Nesterov, Y. (2013). "Gradient methods for minimizing composite functions". Mathematical Programming, 140(1), 125–161.
- Beck, A. (2017). First-Order Methods in Optimization. SIAM.
Frequently asked questions
Q1. What is the proximal gradient method (ISTA)?
It is an iterative method for composite minimization whose objective is the sum $F=f+g$ of a smooth convex function $f$ and a nonsmooth convex function $g$. One iteration is $x_{k+1}=\operatorname{prox}_{\eta g}(x_k-\eta\nabla f(x_k))$: a forward (gradient) step on $f$ and a backward (proximal) step on $g$ (forward-backward splitting). With $\eta=1/L$ it converges at $O(1/k)$. The case $g=\|\cdot\|_1$ is specifically called ISTA.
Q2. Why is FISTA faster than the proximal gradient method?
FISTA is the accelerated version obtained by adding Nesterov's extrapolation (momentum) term to ISTA. By evaluating the gradient and proximal steps at the predicted point $y_k$ rather than the current point, it improves the rate one step, from $O(1/k)$ to $O(1/k^2)$. This is the same optimal order as Nesterov's accelerated gradient method in the smooth case, and the per-iteration cost is essentially the same as ISTA.
Q3. What problems is the proximal gradient method used for?
It is used for composite minimization with a nonsmooth regularizer or constraint. Typical examples are Lasso ($\ell_1$ regularization, whose proximal map is soft thresholding), group Lasso (group soft thresholding), image restoration by total variation, compressed sensing, and constrained problems expressible as a projection onto a convex set. As long as the proximal map is available in closed form or is cheap to evaluate, the method applies to large-scale problems at the same cost as a gradient method.