Subgradient Methods

Optimize nondifferentiable convex functions by stepping along any subgradient, trading speed for the ability to handle kinks.

When the gradient does not exist

Convex functions like the absolute value or the max of linear functions have kinks where no gradient exists. At such points a subgradient generalizes the gradient: a vector v is a subgradient of convex f at x if f(y) >= f(x) + v dot (y - x) for all y. The set of all subgradients is the subdifferential.

The subgradient method

The update mirrors gradient descent: x_{k+1} = x_k - a_k * v_k, where v_k is any subgradient at x_k. A crucial difference is that -v_k need not be a descent direction; the objective can increase in a single step. Convergence is measured by the best objective seen so far, not the last iterate.

Step sizes

• Constant step: converges only to a neighborhood of the optimum.
• Diminishing step with sum a_k = infinity and sum a_k^2 < infinity: converges to the optimum.
• Polyak step, when the optimal value is known, gives a good practical rate.

Slow but general

Subgradient methods converge at O(1/sqrt(k)) for general convex functions, slower than the O(1/k) or O(1/k^2) of smooth methods. Their appeal is generality and simplicity: they need only one subgradient per step and no line search, and they handle constraints via projection.

Better alternatives when structure exists

When the nonsmooth part has a known structure, proximal gradient methods handle it exactly and converge much faster. Subgradient methods remain the fallback for general nonsmooth convex problems and appear inside cutting-plane and bundle methods that build piecewise-linear models from accumulated subgradients.

for k in range(1, iters+1):
    v = subgradient(x)      # any element of the subdifferential
    x = x - (a0/k**0.5) * v
    best = min(best, f(x))

Subgradient methods provide a robust, general route to optimizing the nonsmooth objectives that appear in robust estimation and worst-case design.