Composite optimization separates a differentiable loss from a nonsmooth penalty or constraint. Proximal gradient linearizes only the smooth term and keeps the nonsmooth term exact.
The proximal quadratic model
Let \[ F(x)=f(x)+g(x), \] where \(f\) is convex and \(L\)-smooth and \(g\) is proper, closed, and convex. At \(x\), define \[ Q_L(z;x) =f(x)+\langle\nabla f(x),z-x\rangle +\frac L2\|z-x\|^2+g(z). \] Smoothness gives \(F(z)\le Q_L(z;x)\).
Definition. The proximal-gradient update is \[ x^+=\operatorname*{arg\,min}_zQ_L(z;x) =\operatorname{prox}_{g/L} \left(x-\frac1L\nabla f(x)\right). \] The gradient mapping is \(G_L(x)=L(x-x^+)\).
Composite stationarity. \(G_L(x)=0\) if and only if \(0\in\nabla f(x)+\partial g(x)\), equivalently \(x\) minimizes \(F\).
Proof. Proximal optimality gives \[ 0\in\nabla f(x)+L(x^+-x)+\partial g(x^+). \] If \(x^+=x\), this is the composite Fermat rule. Conversely, the Fermat rule makes \(x\) the unique minimizer of the strongly convex model, so \(x^+=x\).
Descent and the \(1/k\) rate
Composite three-point inequality. For every \(z\in\operatorname{dom}g\), \[ F(x^+)-F(z) \le\frac L2\bigl(\|x-z\|^2-\|x^+-z\|^2\bigr). \]
Proof. Strong convexity of \(Q_L(\cdot;x)\) and optimality of \(x^+\) give \[ Q_L(x^+;x)+\frac L2\|z-x^+\|^2\le Q_L(z;x). \] Use \(F(x^+)\le Q_L(x^+;x)\), and use convexity of \(f\) to replace \(f(x)+\langle\nabla f(x),z-x\rangle\) by at most \(f(z)\). Rearranging the remaining squared norms yields the result.
Proximal-gradient convergence. If \(x^\star\) minimizes \(F\), then \[ F(x_k)-F^\star \le\frac{L\|x_0-x^\star\|^2}{2k}. \] If \(F\) is \(\mu\)-strongly convex, the iterates converge geometrically, with a contraction factor bounded in terms of \(\mu/L\).
Proof. Apply the three-point inequality with \(z=x^\star\), sum over \(k\), and use monotonicity of \(F(x_k)\), exactly as in gradient descent. Under strong convexity, combine the same inequality with \(F(x)-F^\star\ge\frac\mu2\|x-x^\star\|^2\) to obtain a geometric recursion for distance and objective error.
FISTA acceleration
Accelerated composite rate. Set \(x_0=y_0\), \(t_0=1\), and \[ \begin{aligned} x_{k+1}&=\operatorname{prox}_{g/L} (y_k-L^{-1}\nabla f(y_k)),\\ t_{k+1}&=\frac{1+\sqrt{1+4t_k^2}}2,\\ y_{k+1}&=x_{k+1} +\frac{t_k-1}{t_{k+1}}(x_{k+1}-x_k). \end{aligned} \] Then \[ F(x_k)-F^\star \le\frac{2L\|x_0-x^\star\|^2}{(k+1)^2}. \]
Proof outline. Replace the smooth gradient-step three-point inequality in Nesterov's potential proof by the composite three-point inequality above. The same identity \(t_{k+1}^2-t_{k+1}=t_k^2\) cancels the extrapolation cross terms, making \(t_k^2(F(x_k)-F^\star)\) plus a squared-distance term nonincreasing. Since \(t_k\ge(k+1)/2\), the displayed bound follows.
Lasso as a proximal-gradient problem
Example. For \[ F(\beta)=\frac1{2n}\|y-X\beta\|^2+\lambda\|\beta\|_1, \] the smoothness constant is \(L=\|X^\top X/n\|_{\mathrm{op}}\). One iteration is \[ \beta^+ =S_{\lambda/L}\!\left( \beta+\frac1{nL}X^\top(y-X\beta) \right), \] with coordinatewise soft thresholding \(S\). The gradient step follows the least-squares loss; the proximal step imposes exact zeros.