Proximal Gradient Methods

Subgradient methods let you optimize functions with kinks, like an L1 penalty, but they're slow and finicky — they need a carefully shrinking step size and never quite reach an exact answer at the kink. Many practical problems, though, have a special structure worth exploiting: they're a sum of a smooth part (like squared prediction error) and a simple non-smooth part (like an L1 penalty). Proximal gradient methods handle each piece with the tool suited to it, rather than forcing one clumsy tool to handle both.

An analogy: two specialists instead of one generalist

Renovating a house that needs both structural engineering (smooth, well-understood physics) and custom stained-glass work (a fiddly, discontinuous craft) badly, you wouldn't hire one generalist to muddle through both. You'd have the structural engineer do her calculations (an ordinary "gradient step" on the smooth part), then hand the plan to a glass specialist who has one job: apply his craft's exact, well-known correction to fit around what she designed. Proximal gradient does exactly this — one step ordinary calculus handles well, one step a specialized "proximal" operator handles exactly, and they alternate.

The method, one symbol at a time

Suppose the objective splits as $f(x) = g(x) + h(x)$, where $g$ is smooth (has an ordinary gradient) and $h$ is convex but possibly non-smooth (like $\lambda|x|$). The update is two stages:

$$x_{k+1} = \mathrm{prox}_{\alpha h} \big( x_k - \alpha \nabla g(x_k) \big) ,$$

where the first part, $x_k - \alpha \nabla g(x_k)$, is just an ordinary gradient step on the smooth piece $g$. The proximal operator $\mathrm{prox}_{\alpha h}(v)$ then finds the point that best balances staying close to $v$ against keeping $h$ small — formally, $\mathrm{prox}_{\alpha h}(v) = \arg\min_x \left( h(x) + \frac{1}{2\alpha}\|x-v\|^2 \right)$. In plain English: take a normal downhill step on the easy part, then apply a specific, exactly-solvable correction that accounts for the difficult part, rather than trying to differentiate through it. For the L1 penalty specifically, this correction has a famous closed form called soft-thresholding: shrink each coordinate toward zero by $\alpha\lambda$, and if that would cross zero, snap it exactly to zero.

Worked example 1: soft-thresholding by hand

For $h(x) = \lambda|x|$, the proximal operator is $\mathrm{prox}_{\alpha\lambda|\cdot|}(v) = \mathrm{sign}(v)\max(|v| - \alpha\lambda, 0)$. Suppose after a gradient step on the smooth part, an intermediate value is $v = 0.15$, with $\alpha\lambda = 0.1$. Then $\mathrm{prox}(0.15) = \mathrm{sign}(0.15) \cdot \max(0.15 - 0.1, 0) = 1 \cdot 0.05 = 0.05$ — shrunk toward zero, but not eliminated, since $|v|$ exceeded the threshold. Now suppose a different coordinate has intermediate value $v = 0.07$, below the same threshold of $0.1$: $\mathrm{prox}(0.07) = \mathrm{sign}(0.07) \cdot \max(0.07 - 0.1, 0) = \max(-0.03, 0) = 0$. That coefficient is snapped exactly to zero — this is the mechanism that makes lasso regression produce genuinely sparse models, dropping features entirely rather than merely shrinking them.

Worked example 2: one full iteration on a lasso regression

A quant fits $f(\beta) = \tfrac12\|y - X\beta\|^2 + \lambda|\beta|$ for a single coefficient $\beta_0 = 0.3$, with smooth-part gradient at that point $\nabla g(\beta_0) = 0.4$, step size $\alpha = 0.5$, and $\lambda = 0.2$. The gradient step gives an intermediate value $v = 0.3 - 0.5(0.4) = 0.1$. The threshold is $\alpha\lambda = 0.5 \times 0.2 = 0.1$. Applying soft-thresholding: $\mathrm{sign}(0.1)\max(0.1 - 0.1, 0) = 0$. In one combined step, the coefficient has been driven exactly to zero — meaning this feature is effectively dropped from the model for this iteration, something plain gradient descent on the same objective (which can't handle the L1 kink at all) could never produce cleanly.

Picture the soft-thresholding rule as a function of the intermediate value $v$: it's flat at zero for $|v|$ below the threshold, then rises as a straight line shifted inward once past it — a visual for why small coefficients vanish completely while large ones merely shrink.

What this means in practice

Proximal gradient methods (and their accelerated version, FISTA) are the standard engine behind lasso regression, elastic-net factor selection, and any regularized model-fitting problem with a non-smooth penalty. They're also the building block inside ADMM for problems too complex to split this cleanly in one step. Anywhere a quant wants a model to automatically zero out irrelevant factors rather than just shrink them, this is the mechanism doing it.