Week 7: Proximal Methods and ADMM

Composite Objectives#

Many machine learning problems have a composite structure: a smooth loss plus a nonsmooth regulariser:

$\min_x \; f(x) + g(x)$

where $f$ is smooth (e.g., squared loss, logistic loss) and $g$ is convex but possibly nonsmooth (e.g., $\ell_1$ norm, indicator of a convex set, nuclear norm). The prototypical example is the lasso:

$\min_\beta \; \tfrac{1}{2}\|X\beta - y\|_2^2 + \lambda \|\beta\|_1$

Gradient descent on the full objective fails because $g$ is not differentiable — the subgradient of $\|\beta\|_1$ at a coordinate where $\beta_j = 0$ is the entire interval $[-1, 1]$, giving no unique direction.

Proximal Operator#

The proximal operator of a convex function $g$ is:

$\operatorname{prox}_{t g}(v) = \arg\min_x \left[ g(x) + \frac{1}{2t}\|x - v\|_2^2 \right]$

The prox evaluates $g$ at $x$ while penalising distance from $v$. Intuitively, it takes a step toward minimising $g$ but stays close to the reference point $v$, with $t$ controlling the trade-off. The prox is well-defined for any closed convex $g$, even nondifferentiable ones.

Key examples:

• $g(x) = \|x\|_1$ (lasso penalty): $\operatorname{prox}_{t\|\cdot\|_1}(v) = \operatorname{soft}(v, t)$, where the soft-thresholding operator is $\operatorname{soft}(v, t) = \operatorname{sign}(v) \cdot \max(|v| - t, 0)$ applied coordinate-wise.

• $g(x) = I_C(x)$ (indicator of closed convex set $C$): $\operatorname{prox}_{I_C}(v) = \operatorname{proj}_C(v)$, the Euclidean projection onto $C$.

• $g(x) = 0$: $\operatorname{prox}_{0}(v) = v$ — prox of zero is the identity.

Worked soft-threshold example. Let $v = 3.7$, $t = 2.0$. Then $\operatorname{soft}(3.7, 2.0) = \operatorname{sign}(3.7) \cdot (3.7 - 2.0) = 1.7$. For $v = 0.5$ with $t = 2.0$: $\operatorname{soft}(0.5, 2.0) = 0$ (shrunk to exactly zero). The threshold $t$ acts as a "kill zone": any $|v| \leq t$ is mapped to zero, implementing sparsity.

ISTA and FISTA#

The Iterative Shrinkage-Thresholding Algorithm (ISTA) is the proximal equivalent of gradient descent for composite problems:

$x_{k+1} = \operatorname{prox}_{\eta g}\big(x_k - \eta \nabla f(x_k)\big)$

Each iteration: take a gradient step on the smooth $f$, then apply the prox of the nonsmooth $g$. For lasso with $f(\beta) = \tfrac{1}{2}\|X\beta - y\|_2^2$ and $g(\beta) = \lambda\|\beta\|_1$:

$\beta_{k+1} = \operatorname{soft}\big(\beta_k - \eta X^T(X\beta_k - y),\; \eta\lambda\big)$

ISTA converges at rate $O(1/k)$ — the same as gradient descent on smooth problems. This is remarkable: the nondifferentiable $\ell_1$ term does not degrade the worst-case rate.

FISTA (Fast ISTA) adds Nesterov momentum to achieve $O(1/k^2)$ — the optimal rate for first-order methods on this class:

$y_{k+1} = x_k + \frac{t_k - 1}{t_{k+1}}(x_k - x_{k-1}), \quad x_{k+1} = \operatorname{prox}_{\eta g}(y_{k+1} - \eta \nabla f(y_{k+1}))$

where $t_{k+1} = (1 + \sqrt{1 + 4 t_k^2})/2$ is the Nesterov sequence. The acceleration comes from extrapolation — evaluating the gradient at a point beyond the current iterate, extrapolated in the direction of recent progress.

Why slow convergence is acceptable for lasso. Lasso is typically solved once per $\lambda$ for a fixed dataset of moderate dimension. $O(1/k^2)$ with a well-tuned step size converges to high accuracy in hundreds of iterations — seconds in practice. The simplicity of ISTA/FISTA (no linear system solve) makes them the go-to first-order choice for structured convex problems.

Operator Splitting and ADMM#

ADMMAlternating Direction Method of Multipliers (Alternating Direction Method of Multipliers) solves problems of the form:

$\min_{x, z} \; f(x) + g(z) \quad \text{s.t.} \quad Ax + Bz = c$

where $f$ and $g$ are convex (possibly nonsmooth). The variables $x$ and $z$ are decoupled in the objective but coupled through a linear constraint. ADMM iterates: