Proximal methods (ISTA, FISTA) and ADMM

Before this lesson: lesson 03 (the step $1/L$ and the $O(1/k)$ rate), lesson 04 (Nesterov momentum, which FISTA uses), lesson 08 (KKT conditions, projections, the lasso dual); why the $\ell_1$ norm gives sparse solutions (linear algebra 11). Time: about 75 minutes, plus the notebook.

---

Why this matters #

Many objectives in ML and science have the form $F(x) = f(x) + g(x)$, with a smooth data term $f$ and a simple nonsmooth term $g$:

• the lasso $\tfrac12\|Ax - b\|^2 + \lambda\|x\|_1$ and sparse logistic regression (feature selection);
• total variation $\|Dx\|_1$ in imaging, denoising and geophysical inversion;
• constraints: bounds on physical parameters, nonnegative factors, probability vectors.

The subgradient method handles the kink of $|x|$ only slowly (error $O(1/\sqrt k)$ after $k$ steps) and gives no exact zeros. The proximal gradient method keeps the $O(1/k)$ rate of gradient descent, gives exact zeros, and accelerates to $O(1/k^2)$. ADMM splits a problem into pieces that are each easy. This is how large inverse problems, distributed fitting, and "plug-and-play" priors (a learned denoiser, even a diffusion model, used in place of a proximal step) are solved.

1. Predict first #

2. The picture #

2.1 A smooth part plus a simple part #

Write $F(x) = f(x) + g(x)$, where

• $f$ is convex and $L$-smooth (lesson 02): its gradient exists and does not change faster than $L$;
• $g$ is convex but may be nonsmooth or even take the value $+\infty$, and it is simple: the small problem in section 2.2 has a cheap, exact solution.

The indicator function of a set $C$ is $\iota_C(x) = 0$ if $x \in C$ and $+\infty$ otherwise. Adding $\iota_C$ to $f$ turns "minimize $f$ over $C$" into "minimize $f + \iota_C$ over everything". So constraints are a special case of a nonsmooth $g$.

Why not use gradient descent with a subgradient of $g$ (a slope of a supporting line, section 3)? At a kink the subgradient jumps, the step size must shrink to 0, and the iterates jump around 0 without landing on it. The method is slow and the solution is never exactly sparse.

2.2 The proximal operator #

The proximal operator of $g$ with step $\eta > 0$ is

Read it as: move from $v$ to a point where $g$ is small, but do not go far. A small $\eta$ keeps you close to $v$; a large $\eta$ cares mostly about $g$. For convex $g$ the objective in $u$ is strongly convex, so the minimizer exists and is unique.

Three cases in one dimension.

• $g = \iota_{[l, h]}$, the indicator of an interval: the prox is the closest point of the interval, $\operatorname{clip}(v, l, h)$. A prox generalizes a projection.
• $g(u) = |u|$: the prox moves $v$ toward 0 by $\eta$ and stops at 0 if it would cross it. This is soft thresholding:

Every $v \in [-\eta, \eta]$ is mapped to exactly 0. This is where exact sparsity comes from.

• $g(u) = \tfrac{c}{2}u^2$: the prox is $v/(1 + \eta c)$, a shrinkage by a constant factor. It never reaches 0 unless $v = 0$.

Interactive figure: loading…

2.3 Proximal gradient: a gradient step, then a prox step #

Recall the descent lemma (lesson 02): for an $L$-smooth $f$ and a step $\eta \le 1/L$, the parabola

lies above $f$ and touches it at $u = x$. Keep $g$ exact, replace $f$ by this upper bound, and minimize over $u$. Complete the square (the terms that do not depend on $u$ drop out):

So the minimizer of "upper bound of $f$" $+ g$ is

A gradient step on $f$, then a prox step on $g$. Because we minimize an upper bound of $F$ that touches $F$ at $x$ (this is called majorize–minimize), $F$ cannot go up: $F(x^+) \le F(x)$. In numerical-analysis words, it is a forward (explicit) Euler step on $f$ and a backward (implicit) Euler step on $g$: forward–backward splitting. The implicit step handles the kink of $g$ stably.

Projected gradient. If $g = \iota_C$ for a closed convex set $C$, the prox is the projection $P_C$, and the method becomes projected gradient descent:

Examples of cheap projections: a box (clip each entry), the nonnegative orthant ($\max(v, 0)$, the ReLU), a ball (rescale), the probability simplex (lesson 08).

Interactive figure: loading…

3. Definitions and main results #

Subgradients and the optimality condition #

For a convex function $g$, a vector $s$ is a subgradient of $g$ at $x$ if

The line (or plane) with slope $s$ through $(x, g(x))$ lies below the graph. The set of all subgradients is the subdifferential $\partial g(x)$. If $g$ is differentiable at $x$, $\partial g(x) = \{\nabla g(x)\}$. For the absolute value:

At the kink, every slope between $-1$ and $1$ gives a supporting line. Two facts we use:

• A convex $F$ has a global minimum at $x^\star$ if and only if $0 \in \partial F(x^\star)$. (Take $s = 0$ in the definition: $F(y) \ge F(x^\star)$ for all $y$.)
• If $f$ is convex and differentiable, $\partial(f + g)(x) = \nabla f(x) + \partial g(x)$.

Lemma (prox optimality) #

For a closed, proper, convex $g$ (its graph has no gaps at the boundary, and it is not $+\infty$ everywhere), the minimizer $p = \operatorname{prox}_{\eta g}(v)$ is unique, and

Proof. The prox objective $g(u) + \frac{1}{2\eta}\|u - v\|^2$ is strongly convex, so it has exactly one minimizer. By the sum rule its subdifferential is $\partial g(u) + (u - v)/\eta$. The minimizer is where this set contains 0, that is $(v - p)/\eta \in \partial g(p)$. $\blacksquare$

Soft thresholding from the lemma. Take $g = \lambda|\cdot|$ in one dimension and write $t = \eta\lambda$. We need $v - u \in t\,\partial|u|$. Check the three cases:

1. $u > 0$: $v - u = t$, so $u = v - t$. This is consistent only if $v > t$.
2. $u < 0$: $v - u = -t$, so $u = v + t$. Consistent only if $v < -t$.
3. $u = 0$: we need $v \in [-t, t]$.

Together: $\operatorname{prox}_{t|\cdot|}(v) = \operatorname{sign}(v)\max(|v| - t, 0) = S_t(v)$. The $\ell_1$ norm is a sum over coordinates, so its prox acts coordinate by coordinate.

Projection from the definition. If $g = \iota_C$, the prox objective is $\frac{1}{2\eta}\|u - v\|^2$ on $C$ and $+\infty$ outside. So $\operatorname{prox}_{\eta\iota_C} = P_C$ for every $\eta > 0$.

Theorem (minimizers are fixed points) #

Let $f$ be convex and differentiable, and $g$ closed, proper and convex. For any $\eta > 0$,

Why it is true (intuition). At a minimizer, the gradient step wants to move by $-\eta\nabla f(x^\star)$, and the prox step pulls back by exactly the same amount. The two forces balance, as in the KKT picture of lesson 08.

Proof.

1. Apply the lemma with $v = x^\star - \eta\nabla f(x^\star)$ and $p = x^\star$. The fixed-point equation holds if and only if $(v - x^\star)/\eta = -\nabla f(x^\star) \in \partial g(x^\star)$.
2. That is, $0 \in \nabla f(x^\star) + \partial g(x^\star) = \partial(f + g)(x^\star)$, by the sum rule.
3. For a convex function, $0 \in \partial F(x^\star)$ is exactly the condition for a global minimum. $\blacksquare$

The step $\eta$ does not change the fixed points; it changes only how fast you reach them. For the lasso, step 1 reads coordinate by coordinate:

• if $x_i^\star \ne 0$: $\big(A^\top(b - Ax^\star)\big)_i = \lambda\operatorname{sign}(x_i^\star)$;
• if $x_i^\star = 0$: $\big|\big(A^\top(b - Ax^\star)\big)_i\big| \le \lambda$.

These are the lasso KKT conditions. A feature stays at 0 as long as its correlation with the residual is at most $\lambda$.

ISTA and FISTA for the lasso #

Let $f(x) = \tfrac12\|Ax - b\|^2$, so $\nabla f(x) = A^\top(Ax - b)$ and $L = \|A\|_2^2 = \lambda_{\max}(A^\top A)$. Here $\lambda$ is the lasso penalty and $\lambda_{\max}(\cdot)$ is an eigenvalue. Use the step $\eta = 1/L$, and write $F = f + \lambda\|\cdot\|_1$, $F^\star = \min_x F(x)$.

• ISTA (iterative shrinkage-thresholding):

• FISTA (Beck and Teboulle, 2009): start with $y_1 = x_0$, $t_1 = 1$; for $k \ge 1$,

The point $y_{k+1}$ is a Nesterov extrapolation (lesson 04). The cost per step is the same as for ISTA: one product with $A$ and one with $A^\top$.

Theorem (rates; Beck and Teboulle 2009, theorems 3.1 and 4.4). Let $f$ be convex and $L$-smooth, $g$ closed and convex, the step $1/L$, and $x^\star$ any minimizer. Then

ISTA is monotone: $F(x_{k+1}) \le F(x_k)$. If $f$ is $\mu$-strongly convex, ISTA also converges linearly: $\|x_k - x^\star\|^2 \le (1 - \mu/L)^k\|x_0 - x^\star\|^2$. FISTA is not monotone: the momentum can overshoot. The ISTA proof is the $O(1/k)$ proof of lesson 03 with $\nabla f$ replaced by the gradient mapping $G(x) = (x - x^+)/\eta$; the FISTA proof is Nesterov's (Vandenberghe's lectures below). The method still converges for steps $\eta < 2/L$, but the majorize–minimize argument and the bounds above need $\eta \le 1/L$; if $L$ is unknown, use backtracking.

The rates on a 2D example. Take $A = \operatorname{diag}(1, 0.1)$, $b = (2, 0.3)$, $\lambda = 0.01$. Then $A^\top A = \operatorname{diag}(1, 0.01)$, so $L = 1$, $\mu = 0.01$ and $\kappa = 100$; per coordinate, $x^\star = (1.99, 2)$. From $x_0 = 0$:

• ISTA first reaches $F(x_k) - F^\star \le 10^{-8}$ at $k = 722$.
• FISTA first reaches it at $k = 100$, but then oscillates; it stays below $10^{-8}$ only from $k = 405$.
• FISTA with a function-value restart (when a step would raise $F$, set $t_k = 1$ and redo the step from the previous point; O'Donoghue and Candès 2015) stays below from $k = 67$.

Both methods converge linearly here because the problem is strongly convex. The general bounds above ignore $\mu$ and promise only $k \approx 4 \cdot 10^8$ (ISTA) and $4 \cdot 10^4$ (FISTA). They are the right guarantee when $\mu = 0$, for example a lasso with more features than samples.

Interactive figure: loading…

The lasso path #

How does $\lambda$ control sparsity? At $x = 0$ the optimality condition of the lasso reads $\|A^\top b\|_\infty \le \lambda$. So for $\lambda \ge \lambda_{\max} = \|A^\top b\|_\infty$ the solution is exactly 0 (lesson 08, check yourself 6). As $\lambda$ decreases, features enter the model one by one, and sometimes one leaves again. The curve $\lambda \mapsto x^\star(\lambda)$ is the lasso path; it is piecewise linear in $\lambda$. Solvers compute it from large to small $\lambda$, starting each fit at the previous solution (warm start).

Interactive figure: loading…

ADMM: split the problem into easy pieces #

ADMM (the alternating direction method of multipliers) solves

Make a copy $z$ of $x$, give $f$ to $x$ and $g$ to $z$, and force them to agree. The augmented Lagrangian is the Lagrangian of lesson 08 plus a quadratic penalty $\rho > 0$:

ADMM minimizes over $x$, then over $z$, then takes a gradient ascent step on the multiplier $y$. With the scaled dual variable $u = y/\rho$, the three updates are

The vector $u$ is the running sum of the disagreements $x - z$: it keeps pushing $x$ and $z$ together.

ADMM for the lasso (Boyd et al. §6.4). With $f = \tfrac12\|Ax - b\|^2$ and $g = \lambda\|\cdot\|_1$:

• The $x$-update is a ridge regression with a fixed matrix. Factor $A^\top A + \rho I$ once (Cholesky); then each iteration costs two triangular solves.
• The $z$-update is the soft threshold, so $z$ is exactly sparse; $x$ is only close to sparse.
• Stop when the primal residual $\|x_k - z_k\|$ and the dual residual $\rho\|z_k - z_{k-1}\|$ are both small (Boyd et al. §3.3).

Convergence (Boyd et al. §3.2). If $f$ and $g$ are closed, proper and convex, and the (unaugmented) Lagrangian has a saddle point, then for every $\rho > 0$: $x_k - z_k \to 0$, $f(x_k) + g(z_k) \to p^\star$, and $y_k \to y^\star$. In practice ADMM reaches modest accuracy in a few tens of iterations, but it can be slow to reach high accuracy, and $\rho$ changes the speed (not the solution).

When splitting is the better tool.

• The prox of each piece is easy, but the prox of their sum is not: $\|Dx\|_1$ (total variation, the generalized lasso; split $z = Dx$), or a penalty plus constraints.
• The data are spread over machines: consensus ADMM fits local models and combines them in the $z$-step (Boyd et al. §7–8).
• The $x$-update is cheap to repeat (a cached factorization, an FFT), while gradient steps would be slow because $\kappa$ is large.

When $g$ has a cheap prox and $f$ is smooth, FISTA is simpler and has no $\rho$ to tune. When you need high accuracy, use a Newton-type or interior-point method.

Plug-and-play priors

In the $z$-update, $\operatorname{prox}_{g/\rho}(v) = \arg\min_z g(z) + \frac{\rho}{2}\|z - v\|^2$ is a denoising problem: find a $z$ close to the noisy $v$ that the prior $g$ likes. Plug-and-play ADMM (Venkatakrishnan, Bouman and Wohlberg, 2013) replaces this step by any good denoiser, for example a trained neural network, without ever writing $g$ down. DiffPIR (Zhu et al., 2023) uses a diffusion model as the denoiser, inside a related splitting method. This is one way to put a learned prior, such as a diffusion model of seismic or climate fields, into a physical inverse problem.

Answers to section 1. (1) $u^\star = 0$ exactly, because $S_1(0.4) = 0$ ($|0.4| \le 1$). The subgradient method with decreasing steps moves around 0 and comes closer, but in general it never lands exactly on 0. The prox gets there in one step. (2) No. The momentum can overshoot, so $F(x_k)$ can go up (section 4 shows it). Only the bound decreases.

4. Worked example #

$A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix}$, $b = (1, 2, -0.5)$, $\lambda = 1$: the lasso of lesson 08, section 4(c). Here $A^\top A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ (eigenvalues 1 and 3) and $A^\top b = (3, 0.5)$. So $L = 3$, $\mu = 1$, the step is $1/3$ and the threshold is $\lambda/L = 1/3$. At the start, $F(0) = \tfrac12\|b\|^2 = \tfrac12(1 + 4 + 0.25) = 2.625$.

ISTA by hand. $\nabla f(x) = A^\top A x - A^\top b$.

• $k = 1$: $\nabla f(0) = (-3, -0.5)$. Gradient step: $0 - \tfrac13(-3, -0.5) = (1, 1/6)$. Threshold by $1/3$: $x_1 = (1 - 1/3,\ 0) = (2/3, 0)$, because $|1/6| \le 1/3$.
• $k = 2$: $\nabla f(x_1) = (2 \cdot \tfrac23 - 3,\ \tfrac23 - 0.5) = (-5/3, 1/6)$. Gradient step: $(2/3 + 5/9,\ -1/18) = (11/9, -1/18)$. Threshold: $x_2 = (8/9, 0)$.

The second coordinate stays 0, because $|-1/18| \le 1/3$. On the line $x_2 = 0$ the update is $x_1 \leftarrow x_1 - \tfrac13(2x_1 - 3) - \tfrac13 = x_1/3 + 2/3$, so $x_{k,1} = 1 - 3^{-k}$ and $x_k \to x^\star = (1, 0)$.

Optimality check (theorem above). $\nabla f(x^\star) = (2 - 3,\ 1 - 0.5) = (-1, 0.5)$.

• Coordinate 1 is nonzero, and $-\nabla_1 f = 1 = \lambda\operatorname{sign}(1)$ ✓.
• Coordinate 2 is zero, and $|\nabla_2 f| = 0.5 \le 1$ ✓.

The optimal value is $F^\star = \tfrac12(0 + 1 + 0.25) + 1 = 1.625$.

The rate on this example. On the line $x_2 = 0$, $F(x) - F^\star = (x_1 - 1)^2$, so $F(x_k) - F^\star = 9^{-k}$ ($0.111$, $0.0123$, …). This is far below the $O(1/k)$ bound $L\|x_0 - x^\star\|^2/(2k) = 1.5/k$, and even faster than the strongly convex factor $1 - \mu/L = 2/3$. The reason: the zero pattern is found at step 1, and then ISTA is gradient descent on the support alone, with curvature $(A^\top A)_{11} = 2$ and factor $1 - 2/3 = 1/3$ per step.

FISTA by hand. $x_1 = (2/3, 0)$ as for ISTA. Then $t_2 = (1 + \sqrt5)/2 \approx 1.618$ and $(t_1 - 1)/t_2 = 0$, so $y_2 = x_1$ and $x_2 = (8/9, 0)$. Next $t_3 \approx 2.194$ and the momentum factor is $(t_2 - 1)/t_3 \approx 0.282$, so $y_3 \approx 0.889 + 0.282 \cdot 0.222 = 0.9515$ and $x_3 \approx (0.9838, 0)$, closer than ISTA's $0.9630$. But the momentum keeps growing: $x_4 \approx 1.0083$ overshoots, and $F$ goes up between $k = 7$ and $k = 8$ ($1.4 \cdot 10^{-7} \to 4.8 \cdot 10^{-7}$ above $F^\star$). With $\kappa = 3$, ISTA is even ahead at $k = 5$ ($1.7 \cdot 10^{-5}$ against $5.1 \cdot 10^{-5}$). Acceleration helps when $\kappa$ is large.

ADMM by hand ($\rho = 1$). Start from $x = z = u = 0$. The matrix is $A^\top A + I = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}$, with inverse $\frac18\begin{pmatrix} 3 & -1 \\ -1 & 3 \end{pmatrix}$.

• $x_1 = \frac18\begin{pmatrix} 3 & -1 \\ -1 & 3 \end{pmatrix}(3, 0.5) = \frac18(8.5, -1.5) = (1.0625, -0.1875)$.
• $z_1 = S_1(x_1 + u_0) = (0.0625, 0)$: exactly sparse, while $x_1$ is not.
• $u_1 = u_0 + x_1 - z_1 = (1, -0.1875)$.

The iterates converge to $x = z = (1, 0)$ and $u = (1, -0.5)$. At a fixed point, $u^\star = -\nabla f(x^\star)/\rho$ and $u^\star \in (\lambda/\rho)\,\partial\|x^\star\|_1$: the scaled dual variable is the subgradient that certifies optimality.

5. In code #

NumPy checks the hand results; scikit-learn solves the same lasso by coordinate descent. The notebook asks you to write these methods yourself.

import numpy as np
from scipy.optimize import minimize_scalar
from sklearn.linear_model import Lasso

def soft(v, t):                                   # prox of t*|.|: soft thresholding
    return np.sign(v) * np.maximum(np.abs(v) - t, 0)

# (a) soft thresholding, and a brute-force check of one entry
v = np.array([2.5, -0.3, 0.8, -1.5])
print(soft(v, 1.0) + 0.0)                         # [ 1.5  0.   0.  -0.5]
print(round(minimize_scalar(lambda u: abs(u) + 0.5 * (u - 2.5) ** 2).x, 6))   # 1.5

# (b) the worked example: ISTA with step 1/L
A = np.array([[1.0, 1.0], [1.0, 0.0], [0.0, 1.0]])
b = np.array([1.0, 2.0, -0.5])
lam = 1.0
L = np.linalg.norm(A, 2) ** 2                     # 3.0
F = lambda x: 0.5 * np.sum((A @ x - b) ** 2) + lam * np.sum(np.abs(x))
x = np.zeros(2)
for k in range(3):
    x = soft(x - A.T @ (A @ x - b) / L, lam / L)
    print(k + 1, x.round(4) + 0.0)                # 1 [0.6667 0.]  2 [0.8889 0.]  3 [0.963 0.]

# FISTA: the gap F(x_k) - F* for k = 6..9 goes up between k = 7 and k = 8
x, y, t, gaps = np.zeros(2), np.zeros(2), 1.0, []
for k in range(10):
    x_old, x = x, soft(y - A.T @ (A @ y - b) / L, lam / L)
    t_new = (1 + np.sqrt(1 + 4 * t * t)) / 2
    y, t = x + (t - 1) / t_new * (x - x_old), t_new
    gaps.append(F(x) - 1.625)
print(np.array(gaps[5:9]))                        # [4.53e-06 1.37e-07 4.85e-07 9.62e-08]

# (c) scikit-learn minimizes F/m with alpha = lam/m
m = A.shape[0]
x_star = Lasso(alpha=lam / m, fit_intercept=False, tol=1e-12, max_iter=100_000).fit(A, b).coef_
print(x_star.round(8) + 0.0, F(x_star))           # [1. 0.] 1.625

# (d) x* is a fixed point of the proximal gradient map for every step
grad = A.T @ (A @ x_star - b)
print(grad.round(8) + 0.0)                        # [-1.   0.5]
for a in [1 / 3, 0.1, 1.0]:
    print(soft(x_star - a * grad, a * lam).round(8) + 0.0)   # [1. 0.] each time

# (e) ADMM with rho = 1
rho = 1.0
M = np.linalg.inv(A.T @ A + rho * np.eye(2))      # tiny here; in practice factor once (Cholesky)
x = z = u = np.zeros(2)
for k in range(100):
    x = M @ (A.T @ b + rho * (z - u))
    z = soft(x + u, lam / rho)
    u = u + x - z
print(z.round(6) + 0.0, u.round(6) + 0.0)         # [1. 0.] [ 1.  -0.5]

6. Where it shows up #

• Sparse models and inverse problems. Daubechies, Defrise and De Mol (2004) proved that iterative soft thresholding converges for linear inverse problems with a sparsity penalty. $\ell_1$ and total-variation penalties are standard in compressed sensing, MRI reconstruction, imaging and geophysical inversion.
• Constraints in training. p.data.clamp_(lo, hi) after each SGD step is projected (stochastic) gradient descent on a box: physical bounds on parameters, nonnegative factors, weight clipping in the original Wasserstein GAN.
• Weight decay as a prox. The prox of $\frac{c}{2}\|x\|^2$ is $x/(1 + \eta c)$, and decoupled weight decay $x \leftarrow (1 - \eta c)x$ is its first-order version. AdamW can be read as an approximate proximal method (Zhuang et al., 2022; lesson 06).
• Unrolled and learned algorithms. LISTA (Gregor and LeCun, 2010) unrolls a few ISTA steps into a network and learns the matrices and thresholds. Plug-and-play ADMM and diffusion-based solvers put a learned denoiser in place of the prox (see the folded block above).
• Distributed fitting. Consensus ADMM fits one model on data split over many machines; each machine solves its own small problem, and the $z$-step averages.
• Sparse inverse covariance. The graphical lasso estimates a sparse precision matrix with an $\ell_1$ penalty; ADMM is one standard solver (Boyd et al. §6.5).

7. Common mistakes #

• Thresholding at $\lambda$ instead of step × $\lambda$. ISTA thresholds at $\lambda/L$ for the step $1/L$; ADMM thresholds at $\lambda/\rho$.
• Using scikit-learn's alpha as $\lambda$. scikit-learn divides the data term by the number of rows $m$: it minimizes $\frac{1}{2m}\|Ax - b\|^2 + \alpha\|x\|_1$, so $\alpha = \lambda/m$.
• Expecting FISTA to be monotone. It is not. Plot $F$ on a log scale, and restart if needed.
• Refactoring in every ADMM iteration. $A^\top A + \rho I$ does not change; factor it once. If you change $\rho$ during the run, refactor and rescale $u$.
• Returning ADMM's $x$. $z$ is exactly sparse; $x$ is only close to sparse.
• A step above $1/L$ without a line search. The bounds need $\eta \le 1/L$. If $L$ is unknown, use backtracking.

8. Check yourself #

1. What is the prox of the indicator of the nonnegative orthant $\{x : x \ge 0\}$?
   Answer

   The projection onto the orthant, $\max(v, 0)$ entry by entry: the ReLU.
2. Compute $\operatorname{prox}_{t\|\cdot\|_1}(v)$ for $v = (0.4, -2, 1)$ and $t = 0.5$.
   Answer

   $(0, -1.5, 0.5)$. The first entry has $|0.4| \le 0.5$, so it becomes exactly 0; the others move toward 0 by 0.5.
3. Show that the prox of $\frac{c}{2}\|u\|^2$ with step $\eta$ is $v/(1 + \eta c)$. Can it give exact zeros?
   Answer

   The objective $\frac{c}{2}\|u\|^2 + \frac{1}{2\eta}\|u - v\|^2$ is smooth with gradient $cu + (u - v)/\eta$. Setting it to 0 gives $u(1 + \eta c) = v$, so $u = v/(1 + \eta c)$. It shrinks every entry by the same factor, so an entry is 0 only if it was 0 in $v$.
4. For $\min f(x)$ over a closed convex set $C$, what does $x^\star = P_C(x^\star - \eta\nabla f(x^\star))$ mean geometrically?
   Answer

   A projection satisfies $p = P_C(v) \iff (v - p)^\top(z - p) \le 0$ for all $z \in C$. With $p = x^\star$ and $v - p = -\eta\nabla f(x^\star)$, this gives $\nabla f(x^\star)^\top(z - x^\star) \ge 0$ for all $z \in C$: no feasible direction decreases $f$ to first order. Equivalently, $-\nabla f(x^\star)$ points out of $C$ (it lies in the normal cone of $C$ at $x^\star$). In the interior of $C$ it means $\nabla f(x^\star) = 0$.
5. $L = 10$, $\|x_0 - x^\star\| = 1$, and you want $F(x_k) - F^\star \le 10^{-4}$. After how many iterations do the ISTA and FISTA bounds guarantee it?
   Answer

   ISTA: $10/(2k) \le 10^{-4}$ gives $k \ge 50{,}000$. FISTA: $20/(k + 1)^2 \le 10^{-4}$ gives $k + 1 \ge \sqrt{2 \cdot 10^5} \approx 447.2$, so $k \ge 447$.
6. In ADMM for the lasso, what changes when you increase $\rho$?
   Answer

   The threshold $\lambda/\rho$ gets smaller, and the $x$-update is pulled harder toward $z - u$. The primal residual $\|x - z\|$ tends to get smaller and the dual residual $\rho\|z_k - z_{k-1}\|$ larger. The solution does not change, only the speed. You must refactor $A^\top A + \rho I$, and rescale $u = y/\rho$ if $\rho$ changes during the run.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Define the proximal operator $\operatorname{prox}_{\eta g}(v)$.

   Show answer

2. Give the soft-thresholding formula, the prox of $t|\cdot|$.

   Show answer

3. Compute $\operatorname{prox}_{\eta|\cdot|}(0.4)$ for $\eta = 1$.

   Show answer

4. What is the prox of the indicator of a closed convex set $C$?

   Show answer

5. Write the proximal gradient update for $F = f + g$.

   Show answer

6. What is the subdifferential of $|x|$ at $x = 0$?

   Show answer

7. How are the minimizers of $f + g$ related to the proximal gradient map?

   Show answer

8. State the rates of ISTA and FISTA with step $1/L$.

   Show answer

9. Why is FISTA not monotone?

   Show answer

10. Name the three ADMM updates for the lasso.

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Why does $\ell_1$ give exact zeros and $\ell_2$ does not?" — The prox of $\ell_1$ maps the whole interval $[-t, t]$ to 0; the prox of $\ell_2^2$ only scales. Geometrically, the $\ell_1$ ball has corners on the axes.
• "What is a proximal operator?" — $\arg\min_u g(u) + \frac{1}{2\eta}\|u - v\|^2$. A projection is the case of an indicator function.
• "How would you solve a lasso with $10^6$ features?" — Coordinate descent (scikit-learn, glmnet) or FISTA, with a duality-gap stop; ADMM if the data are distributed or the penalty is $\|Dx\|_1$.
• "Why is FISTA faster, and what does it cost?" — Nesterov momentum: $O(1/k^2)$ instead of $O(1/k)$ at the same cost per step, but it is not monotone.
• "You need $x \ge 0$ in PyTorch. Simplest correct method?" — Projected gradient: clamp after each step.
• "What does $\rho$ do in ADMM?" — It weights the agreement penalty. It changes the speed and the balance of primal and dual residuals, not the solution.

10. Practice #

The notebook for this lesson runs in Colab. Each exercise has a check cell and a folded solution.

1. Soft thresholding and the prox of $\tfrac c2 u^2$; check them against brute-force 1D minimization.
2. Projected gradient onto a box for bound-constrained least squares; compare with scipy.optimize.lsq_linear.
3. ISTA and FISTA for the lasso on the diabetes data; compare with scikit-learn's Lasso (mind the $1/(2m)$ scaling), and plot $F(x_k) - F^\star$ on a log scale.
4. ADMM for the lasso with one Cholesky factorization, stopping on the primal and dual residuals.
5. Check the lasso optimality (subgradient) conditions of a solution, coordinate by coordinate.

11. Watch and read #

5.1 Proximal and Projected Gradient DescentConstantine Caramanis · UT Austin, Optimization · 35 min

The proximal operator, and projected gradient descent as a special case of proximal gradient.

5.4 ISTA and FISTAConstantine Caramanis · UT Austin, Optimization · 28 min

The lasso, iterative shrinkage-thresholding, and the accelerated version.

The proximal operator of the L1 normDaniel O'Connor · 44 min

How to compute the prox of the ℓ1 norm, which gives soft thresholding.

Lecture 8: Proximal Gradient Descent and AccelerationRyan Tibshirani · CMU 10-725 Convex Optimization · 80 min

Proximal gradient, its convergence analysis, and acceleration, with many examples.

lecture 23: dual methods and admmRyan Tibshirani · CMU 10-725 Convex Optimization · 77 min

From dual methods to the augmented Lagrangian and ADMM, with applications.

• Parikh and Boyd, Proximal Algorithms, free: §2.3 (fixed points), §4.2 (proximal gradient), §4.3 (acceleration), §4.4 (ADMM), §6.5.2 (prox of the $\ell_1$ norm).
• Boyd, Parikh, Chu, Peleato and Eckstein, Distributed Optimization and Statistical Learning via ADMM, free: §3.1–3.3 (algorithm, convergence, stopping rules), §6.4 (lasso), §7–8 (consensus).
• Vandenberghe, UCLA ECE236C, Proximal gradient method (the $O(1/k)$ proof) and Accelerated proximal gradient methods (FISTA and the $2L/(k + 1)^2$ bound).
• Ryan Tibshirani, CMU 10-725, lecture notes on proximal gradient descent and ADMM.
• Beck and Teboulle, "A fast iterative shrinkage-thresholding algorithm for linear inverse problems", SIAM Journal on Imaging Sciences 2(1), 2009 (the FISTA paper and its rates).