Subgradient Methods

Subgradient methods minimize nondifferentiable convex functions by stepping along any subgradient, using a diminishing step size for convergence.

When the gradient does not exist

Functions like |x| or max(f_1, f_2) have kinks where no gradient is defined. At such points a convex function still has subgradients: vectors g such that f(y) >= f(x) + g^T(y - x) for all y. The set of all subgradients at a point is the subdifferential. Where the function is differentiable the subdifferential is just the single gradient.

The update

A subgradient method iterates x_{k+1} = x_k - t_k g_k, where g_k is any subgradient at x_k and t_k is a step size. Unlike gradient descent, a subgradient step is not guaranteed to decrease the objective at every iteration, because a subgradient need not point downhill. Convergence is instead tracked through the best objective value seen so far.

Step-size rules matter

Because individual steps can go uphill, the step size must shrink to control the noise. Standard choices are a diminishing but nonsummable schedule such as t_k = a/(b + k), or a square-summable schedule. With sum of t_k infinite and sum of t_k^2 finite, the best value converges to the optimum. A constant step size only guarantees convergence to a neighborhood of the minimum, whose size shrinks with the step.

• Constant t: fast early, settles near but not at the optimum
• Diminishing nonsummable: converges to the optimum, slowly
• Polyak step (needs the optimal value): often the fastest in practice

import numpy as np

def subgradient_l1_reg(A, b, lam, iters=2000, a=0.5):
    x = np.zeros(A.shape[1]); best = x.copy()
    fbest = np.inf
    for k in range(1, iters+1):
        g = A.T @ (A @ x - b) + lam*np.sign(x)  # subgradient (0 at x_i=0)
        x = x - (a/np.sqrt(k))*g
        f = 0.5*np.sum((A@x-b)**2) + lam*np.sum(np.abs(x))
        if f < fbest: fbest, best = f, x.copy()
    return best

Rate and role

Subgradient methods converge at O(1/sqrt(k)) for general convex functions, slower than gradient descent's O(1/k), which is the price of handling nonsmoothness with no extra structure. When the nonsmooth part has a known proximal operator, proximal gradient methods are far faster; subgradient methods are the fallback when it does not, and they remain the conceptual foundation for stochastic and online learning.