FISTA

Definition ($L$-smoothness). Let $L\ge0$. A function $f:E\to(-\infty,+\infty]$ is said to be $L$-smooth over a set $D\subseteq E$ if it is differentiable over $D$ and satisfies $$\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\| \quad \forall x,y\in D$$

lemma4 (descent lemma): Let $f:E\to(-\infty,\infty]$ be $L-$smooth function over a given convex set $D$. Then $$\forall x,y\in D \quad f(y)\le f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\|x-y\|_2^2$$

proof Set $h(t)=f\big(x+t(y-x)\big)$ $$\int_0^1 h'(t)dt = h(1)-h(0)=f(y)-f(x)$$ $$=\int_0^1 \langle y-x,\nabla f\big(x+t(y-x)\big)\rangle dt$$

So $$f(y)-f(x)-\langle\nabla f(x),y-x\rangle=\int_0^1 \big\langle y-x,\nabla f(x+t(y-x))-\nabla f(x)\big\rangle dt$$

(Since $L$-smoothness) $$\le \int_0^1 \|y-x\|_2\cdot\big\|\nabla f(x+t(y-x))-\nabla f(x)\big\|_2 dt$$ $$\le \int_0^1 \|y-x\|_2 \cdot L\|t(y-x)\|_2 dt$$ $$=\int_0^1 Lt\|y-x\|_2^2 dt$$ $$=\frac{L}{2}\|x-y\|_2^2$$

So $$f(y)\le f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\|x-y\|_2^2$$

Iteration of ISTA is $$x^{k+1}=\mathrm{prox}_{\beta g}\big(x^k-\beta\nabla f(x^k)\big)$$ $$x^{k+1}=\mathop{\arg\min}_u\left\{\frac12\big\|u-(x^k-\beta\nabla f(x^k))\big\|_2^2+\beta g(u)\right\}$$

Set $\beta=\frac1L$ $$x^{k+1}=\mathop{\arg\min}_u\left\{\frac12\left\|u-x^k+\frac1L\nabla f(x^k)\right\|_2^2+\frac1Lg(u)\right\}$$

$$=\mathop{\arg\min}_u\left\{\frac12\left(\|u-x^k\|_2^2+\frac1{L^2}\|\nabla f(x^k)\|_2^2+2\frac1L\langle u-x^k,\nabla f(x^k)\rangle\right)+\frac1Lg(u)\right\}$$

$$=\mathop{\arg\min}_u\left\{\frac L2\|u-x^k\|_2^2+\langle u-x^k,\nabla f(x^k)\rangle+g(u)+f(x^k)\right\}$$

Set $$Q_L(u,z)=f(z)+\langle u-z,\nabla f(z)\rangle+\frac L2\|u-z\|_2^2+g(u)$$ $$P_L(z)=\mathop{\arg\min}_u Q_L(u,z)$$

$$F(x)=f(x)+g(x)$$ $f$ is $L$-smooth convex, $g$ non‑smooth iteration is $x^{k+1}=P_L(x^k)$

by lemma 4 $$f(P_L(z))\le f(z)+\langle P_L(z)-z,\nabla f(z)\rangle+\frac L2\|P_L(z)-z\|_2^2$$ $$F(P_L(z))\le Q_L(P_L(z),z)$$

lemma 5: $\forall x\in\mathbb R^n,\ z\in\mathbb R^n,\ L>0$ $$F(x)-F(P_L(z))\ge\frac L2\|P-z\|_2^2+L\langle z-x,\,P-z\rangle$$

proof: by Theorem 1. $p=P_L(z)=\mathop{\arg\min}_u Q_L(u,z)$ $$0\in\partial Q_L(p,z)$$ $$0\in\nabla f(z)+L(p-z)+\partial g(p)$$ $$\iff -\big(\nabla f(z)+L(p-z)\big)\in\partial g(p)$$

Set $\gamma(z)=-\big(\nabla f(z)+L(p-z)\big)$

Since $(f,g)$ are convex so $$f(x)\ge f(z)+\langle\nabla f(z),x-z\rangle$$ $$g(x)\ge g(p)+\langle\gamma(z),x-p\rangle$$

$$F(x)\ge f(z)+g(p)+\langle\nabla f(z),x-z\rangle+\langle\gamma(z),x-p\rangle$$

Since $F(p)\le Q_L(p,z)$ $$F(x)-F(p)\ge F(x)-Q_L(p,z)$$

$$\ge \langle\nabla f(z),x-z\rangle+\langle\gamma(z),x-p\rangle-\langle p-z,\nabla f(z)\rangle-\frac L2\|p-z\|_2^2$$

$$=\langle x-p,\nabla f(z)\rangle+\langle x-p,\gamma(z)\rangle-\frac L2\|p-z\|_2^2$$ $$=\langle x-p,\nabla f(z)+\gamma(z)\rangle-\frac L2\|p-z\|_2^2$$ $$=\langle x-p,-L(p-z)\rangle-\frac L2\|p-z\|_2^2$$ $$=-L\langle x-p,p-z\rangle-\frac L2\|p-z\|_2^2$$

$$=L\langle p-x,z+p-z\rangle-\frac L2\|p-z\|_2^2$$ $$=L\|p-z\|_2^2+L\langle z-x,p-z\rangle-\frac L2\|p-z\|_2^2$$ $$=\frac L2\|p-z\|_2^2+L\langle z-x,p-z\rangle$$

So $$F(x)-F(P_L(z))\ge\frac L2\|p-z\|_2^2+L\langle z-x,p-z\rangle$$

Set $x^*\in\arg\min F,\ z=x^k,\ P_L(z)=x^{k+1}$

by lemma 5 $$F(x^*)-F(x^{k+1})\ge\frac L2\|x^{k+1}-x^k\|_2^2+L\langle x^k-x^*,\,x^{k+1}-x^k\rangle$$ $$=\frac L2\Big(\|x^{k+1}-x^k\|_2^2+2\langle x^k-x^*,\,x^{k+1}-x^k\rangle\Big)$$ $$=\frac L2\Big(\|x^{k+1}-x^*\|_2^2-\|x^k-x^*\|_2^2\Big)$$

$$\frac2L\big(F(x^*)-F(x^{k+1})\big)\ge\|x^{k+1}-x^*\|_2^2-\|x^k-x^*\|_2^2$$

Set $z=x^k$ $$F(x^k)-F(x^{k+1})\ge\frac L2\big(\|x^{k+1}-x^k\|_2^2\big)$$

$$\sum_{k=0}^{n-1}\big(F(x^*)-F(x^{k+1})\big)\cdot\frac2L$$ $$=\frac2L\Big[nF(x^*)-\sum_{k=0}^{n-1}F(x^{k+1})\Big]$$ $$\ge\|x^n-x^*\|_2^2-\|x^0-x^*\|_2^2$$

$$\sum_{k=0}^{n-1}k\big(F(x^k)-F(x^{k+1})\big)\cdot\frac2L\ge\sum_{k=0}^{n-1}k\|x^{k+1}-x^k\|_2^2$$

$$\frac L2\cdot\text{LHS}=F(x^1)-F(x^2)+2F(x^2)-2F(x^3)+\dots+(n-1)F(x^{n-1})-(n-1)F(x^n)$$ $$=F(x^1)+F(x^2)+\dots+F(x^{n-1})-(n-1)F(x^n)$$ $$=F(x^1)+F(x^2)+\dots+F(x^{n-1})+F(x^n)-nF(x^n)$$ $$=\sum_{k=0}^{n-1}F(x^{k+1})-nF(x^n)$$

So $$\frac2L\Big(\sum_{k=0}^{n-1}F(x^{k+1})-nF(x^n)\Big)\ge\sum_{k=0}^{n-1}k\|x^{k+1}-x^k\|_2^2$$

Adding these two inequalities gives $$\frac2L\big(nF(x^*)-nF(x^n)\big)\ge\|x^n-x^*\|_2^2-\|x^0-x^*\|_2^2+\sum_{k=0}^{n-1}k\|x^{k+1}-x^k\|_2^2$$ $$\ge-\|x^0-x^*\|_2^2$$

$$F(x^n)-F(x^*)\le\frac{L\|x^0-x^*\|_2^2}{2n}$$

So ISTA has a worst‑case complexity result of $O(1/k)$.

$\tilde{x}$ s.t. $F(\tilde{x})-F(x^*)\le\varepsilon$ is at most $\lceil C/\varepsilon\rceil$ step where $C=\dfrac{L\|x^0-x^*\|_2^2}{2}$

Iterative of FISTA

Set $y^1=x^0,\ t_1=1$ $$x^k=P_L(y^k)$$ $$t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2}$$ $$y^{k+1}=x^k+\frac{t_k-1}{t_{k+1}}\big(x^k-x^{k-1}\big)$$

We can see that $$2t_{k+1}=1+\sqrt{1+4t_k^2}$$ $$1+4t_k^2=4t_{k+1}^2+1-4t_{k+1}$$ $$t_{k+1}^2-t_{k+1}=t_k^2$$

$$V_k=F(x^k)-F(x^*)$$ $$u_k=t_kx^k-(t_k-1)x^{k-1}-x^*$$

lemma 6. For the sequence $\{x_k,y_k\}$ via FISTA, $k\ge1$ $$\frac2Lt_k^2V_k-\frac2Lt_{k+1}^2V_{k+1}\ge\|u_{k+1}\|_2^2-\|u_k\|_2^2$$

proof By lemma 5.

Let $z=y^{k+1},\ p=x^{k+1}$ $$F(x)-F(x^{k+1})\ge\frac L2\|x^{k+1}-y^{k+1}\|_2^2+L\langle y^{k+1}-x,\,x^{k+1}-y^{k+1}\rangle$$

Let $x=x^k$ $$F(x^k)-F(x^{k+1})\ge\frac L2\|x^{k+1}-y^{k+1}\|_2^2+L\langle y^{k+1}-x^k,\,x^{k+1}-y^{k+1}\rangle$$

Let $x=x^*$ $$F(x^*)-F(x^{k+1})\ge\frac L2\|x^{k+1}-y^{k+1}\|_2^2+L\langle y^{k+1}-x^*,\,x^{k+1}-y^{k+1}\rangle$$

$$V_k-V_{k+1}\ge\frac L2\|x^{k+1}-y^{k+1}\|_2^2+L\langle y^{k+1}-x^k,\,x^{k+1}-y^{k+1}\rangle$$

$$-V_{k+1}\ge\frac L2\|x^{k+1}-y^{k+1}\|_2^2+L\langle y^{k+1}-x^*,\,x^{k+1}-y^{k+1}\rangle$$

Multiplying the first inequality by $(t_{k+1}-1)$ and adding the second gives

$$(t_{k+1}-1)V_k-(t_{k+1}-1)V_{k+1}-V_{k+1}$$ $$=(t_{k+1}-1)V_k-t_{k+1}V_{k+1}\ge t_{k+1}\cdot\frac L2\|x^{k+1}-y^{k+1}\|_2^2+L\big[(t_{k+1}-1)(y^{k+1}-x^k)+(y^{k+1}-x^*)\big]\cdot(x^{k+1}-y^{k+1})$$

$$\ge t_{k+1}\frac L2\|x^{k+1}-y^{k+1}\|_2^2+L(x^{k+1}-y^{k+1})\big[(t_{k+1}-1)(y^{k+1}-x^k)+(y^{k+1}-x^*)\big]$$

$$=t_{k+1}\frac L2\|x^{k+1}-y^{k+1}\|_2^2+L(x^{k+1}-y^{k+1})\big(t_{k+1}y^{k+1}-t_{k+1}x^k+x^k-x^*\big)$$

$$\iff \frac2L\Big[\big(t_{k+1}^2-t_{k+1}\big)V_k-t_{k+1}^2V_{k+1}\Big]\ge t_{k+1}^2\|x^{k+1}-y^{k+1}\|_2^2+2t_{k+1}\big(t_{k+1}y^{k+1}-t_{k+1}x^k+x^k-x^*\big)\cdot(x^{k+1}-y^{k+1})$$

LHS is $\displaystyle\frac2L\big(t_k^2V_k-t_{k+1}^2V_{k+1}\big)$

RHS is $\displaystyle\|t_{k+1}x^{k+1}-t_{k+1}y^{k+1}\|_2^2+2\big(t_{k+1}x^{k+1}-t_{k+1}y^{k+1}\big)\big(t_{k+1}y^{k+1}-(t_{k+1}-1)x^k-x^*\big)$

$$t_{k+1}y^{k+1}=t_{k+1}x^k+(t_k-1)(x^k-x^{k-1})$$

So set $b=t_{k+1}x^{k+1},\ a=t_{k+1}y^{k+1},\ c=(t_{k+1}-1)x^k+x^*$

$$\|b-a\|_2^2+2(b-a)\cdot(a-c)$$

$$=\|b-a\|_2^2+2(b-a)\cdot(a-c)$$

$$=\|b-c\|_2^2-\|a-c\|_2^2$$

$$=\Big\|t_{k+1}x^{k+1}-(t_{k+1}-1)x^k-x^*\Big\|_2^2-\Big\|t_kx^k-(t_k-1)x^{k-1}-x^*\Big\|_2^2$$

$$=\|u_{k+1}\|_2^2-\|u_k\|_2^2$$

So $$\frac2L\big(t_k^2V_k-t_{k+1}^2V_{k+1}\big)\ge\|u_{k+1}\|_2^2-\|u_k\|_2^2$$

Set $a_k=\frac2Lt_k^2V_k,\ b_k=\|u_k\|_2^2,\ c=\|x^0-x^*\|_2^2$

By lemma 6 $$a_k-a_{k+1}\ge b_{k+1}-b_k$$ $$a_k+b_k\ge a_{k+1}+b_{k+1}$$

So $a_k+b_k$ decrease

$a_1=\frac2Lt_1^2V_1,\ b_1=\|u_1\|_2^2=\|x^1-x^*\|_2^2$

By lemma 5 $$F(x^*)-F(x^1)\ge\frac L2\|x^1-x^0\|_2^2+L\langle x^0-x^*,\,x^1-x^0\rangle$$

$$\iff \frac2L(-V_1)\ge\|x^1-x^*\|_2^2-\|x^0-x^*\|_2^2$$ $$\frac2LV_1\le\|x^0-x^*\|_2^2-\|x^1-x^*\|_2^2$$ $$\frac2LV_1+\|x^1-x^*\|_2^2\le\|x^0-x^*\|_2^2$$

$$a_1+b_1\le c$$

So $a_k\le a_k+b_k\le c$

$$\frac2Lt_k^2V_k\le\|x^0-x^*\|_2^2$$

lemma 7 $$t_k\ge\frac{k+1}{2}$$

when $k=1,\ t_1=1$

assume $k\ge1,\ t_k\ge\frac{k+1}{2}$

then $$t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2}\ge\frac{1+\sqrt{1+(k+1)^2}}{2}\ge\frac{k+2}{2}\ge\frac{k+1}{2}$$

So $t_k\ge\frac{k+1}{2}\quad\forall k$

So $$\frac2Lt_k^2V_k\le\|x^0-x^*\|_2^2$$

$$F(x^k)-F(x^*)\le\frac{L\|x^0-x^*\|_2^2}{2t_k^2}\le\frac{2L\|x^0-x^*\|_2^2}{(k+1)^2}$$

So FISTA has worst‑case complexity result of $O(1/k^2)$