Subgradient Methods

Gradient descent needs a well-defined slope at every point, but many important loss functions have sharp corners where the ordinary derivative simply doesn't exist — the absolute-value penalty $|x|$ used in L1 regularization has a kink at zero, and the hinge loss used in support vector machines has one at its margin boundary. At that exact corner, "the slope" is ambiguous: approaching from the left gives one value, from the right gives another. Subgradient methods answer the question: what do you do when you can't compute the gradient because there isn't a single one?

An analogy: the crease of a folded card

Picture a V-shaped valley, like a book folded open and turned upside down. Everywhere except the crease at the bottom, the slope is well-defined and a ball rolls downhill normally. Right at the crease, though, the surface has no single tilt: it's tilting one way just to the left and another way just to the right. Any direction "between" those two tilts — including straight down along the crease — is a reasonable stand-in for "the slope" there, even though none of them is uniquely correct. A subgradient is exactly this: any valid stand-in for a slope at a point where the true slope isn't unique.

The method, one symbol at a time

For a convex function $f$ that may not be differentiable everywhere, a vector $g$ is a subgradient of $f$ at point $x$ if, for every other point $y$,

$$f(y) \geq f(x) + g^T (y - x) .$$

In plain English: $g$ defines a straight line (or plane) through $(x, f(x))$ that lies entirely below the function everywhere else — it's a valid "supporting" slope even if it isn't the unique tangent slope. The set of all such valid $g$ at a point is called the subdifferential. Where $f$ is smooth, this set contains exactly one vector — the ordinary gradient — and everything reduces to normal gradient descent. At a kink, the set contains a whole range of valid slopes, and the subgradient method simply picks any one of them and takes a step:

$$x_{k+1} = x_k - \alpha_k \, g_k, \qquad g_k \in \partial f(x_k) .$$

Unlike ordinary gradient descent, the step size $\alpha_k$ must typically shrink over iterations (rather than stay fixed), because a subgradient doesn't guarantee the function actually decreases at every single step — only that, on average over many steps, progress is made toward the minimum.

Worked example 1: minimizing $|x|$ by hand

Minimize $f(x) = |x|$, whose subdifferential is $\{-1\}$ for $x<0$, $\{+1\}$ for $x>0$, and the interval $[-1,1]$ at $x=0$. Starting at $x_0=3$ with shrinking step $\alpha_k = 1/(k+1)$: at $x_0=3$, subgradient $g_0=1$, so $x_1 = 3-1(1)=2$. At $x_1=2$: $g_1=1$, $\alpha_1=1/2$, $x_2=2-0.5=1.5$. At $x_2=1.5$: $g_2=1$, $\alpha_2=1/3$, $x_3\approx1.17$. The sequence keeps shrinking toward the true minimum at $x=0$, but — unlike gradient descent on a smooth bowl — it approaches slowly and never lands exactly on 0 in finitely many steps; the shrinking step size is what eventually gets it arbitrarily close.

Worked example 2: an L1-regularized regression step

A quant fitting a sparse factor-selection regression minimizes squared error plus an L1 penalty, $f(\beta) = \tfrac12(\hat y - y)^2 + \lambda|\beta|$. Suppose at the current coefficient $\beta = 0.02$ with $\lambda = 0.1$, the squared-error part contributes a gradient of $-0.05$, and since $\beta > 0$ the penalty's subgradient is exactly $+\lambda = 0.1$. The combined subgradient is $-0.05 + 0.1 = 0.05$. With step size $\alpha = 0.1$, the update is $\beta_{\text{new}} = 0.02 - 0.1(0.05) = 0.015$. Note the coefficient moved toward zero even though the squared-error term alone was pulling it up — this is the L1 penalty's subgradient at work, and it's exactly the mechanism (formalized more efficiently via proximal gradient methods) that drives L1-regularized coefficients to become exactly zero rather than merely small.

Compare a smooth curve against a V-shaped kink: notice that away from the kink the "slope" behaves normally, but at the kink itself any line between the left- and right-hand slopes stays below the curve — that whole range is valid.

What this means in practice

Subgradient methods (or their more refined descendant, proximal gradient methods) are what make L1-regularized regression (lasso), support-vector-machine training, and any loss function with a hard threshold or absolute-value term optimizable with gradient-based tools at all. Without this generalization, a kink in the loss would simply break standard gradient descent at that exact point.