Subgradient Methods — Mathematics Knowledge System

Overview

Subgradient methods extend gradient descent to non-smooth convex functions. A subgradient of a convex function f at x is any vector g such that f(y) >= f(x) + g^T(y-x) for all y. When f is differentiable, the subgradient is unique (the gradient). For non-smooth f (like the L1 norm |x|_1 or the max function), there are multiple subgradients at non-differentiable points. The subgradient method updates x_{t+1} = x_t - alpha_t * g_t where g_t in partial f(x_t). Convergence is slower than gradient descent (O(1/sqrt(T)) vs O(1/T)) but works for non-smooth objectives crucial in sparse optimization and SVM training.

Intuition

At a kink of a non-smooth convex function (like the tip of |x|), the gradient doesn't exist. But there are many linear functions that touch the graph of f from below at that point -- these are the subgradients. The subdifferential partial f(x) is the set of all subgradients. The subgradient method uses any element of the subdifferential as a descent direction. Unlike gradient descent, a subgradient step might not decrease f -- but in the long run, the average iterates converge to the minimum.

Formal Definition

Definition

For a convex function f: R^d -> R, g in R^d is a subgradient of f at x if f(y) >= f(x) + <g, y-x> for all y in R^d. The subdifferential is partial f(x) = {g : g is a subgradient of f at x}. For f differentiable at x, partial f(x) = {nabla f(x)}. For f(x) = |x| at x=0: partial f(0) = [-1, 1]. Subgradient method: pick g_t in partial f(x_t), update x_{t+1} = x_t - alpha_t * g_t. With step sizes alpha_t = a/sqrt(t): convergence at rate f(x_best_T) - f* <= O(1/sqrt(T)).

g \in \partial f(x) \iff f(y) \ge f(x) + \langle g, y-x\rangle \;\forall y

Subgradient definition

\partial(f+g)(x) \supseteq \partial f(x) + \partial g(x)

Sum rule for subdifferentials

x_{t+1} = x_t - \alpha_t g_t,\quad g_t \in \partial f(x_t)

Subgradient method

f\!\left(\frac{1}{T}\sum_{t=1}^T x_t\right) - f^* \le \frac{R^2 + G^2 \sum_{t=1}^T \alpha_t^2}{2\sum_{t=1}^T \alpha_t}

Subgradient convergence bound

Notation

Notation	Meaning
$\partial f(x)$	Subdifferential of f at x (set of subgradients)
$g \in \partial f(x)$	g is a subgradient of f at x
$x_{\mathrm{best}}$	Best iterate: argmin_{t<=T} f(x_t)
$G$	Bound on subgradient norm: \|\|g\|\| <= G

Theorems

Theorem 1: Subgradient Convergence Theorem

For a convex function f with f* = min f(x), starting point x_1 with ||x_1 - x*|| <= R, and bounded subgradients ||g_t|| <= G, the subgradient method with step sizes alpha_t = R/(G*sqrt(t)) satisfies: min_{t<=T} f(x_t) - f* <= (R*G)*(1 + log T)/sqrt(T) = O(log T/sqrt(T)). With optimal averaging and alpha_t = R/(G*sqrt(T)), one gets: f(x_bar_T) - f* <= R*G/sqrt(T).

Theorem 2: Proximal Gradient Method

For f(x) = g(x) + h(x) with g smooth (L-Lipschitz gradient) and h convex (possibly non-smooth), the proximal gradient method updates x_{t+1} = prox_{alpha h}(x_t - alpha*nabla g(x_t)) where prox_{alpha h}(v) = argmin_x {h(x) + ||x-v||^2/(2alpha)}. This achieves O(1/T) convergence (matching gradient descent on g alone). For h = lambda*|x|_1 (LASSO), prox_{alpha h} = soft-thresholding.

Theorem 3: Subgradient Optimality Condition

A point x* is a global minimum of a convex function f if and only if 0 in partial f(x*) (zero is a subgradient at x*). For a constrained problem min_{x in C} f(x), x* is optimal iff there exists g in partial f(x*) such that g^T(x-x*) >= 0 for all x in C (the subgradient is an outward-pointing normal to C at x*).

Worked Examples

1
For x > 0: f is differentiable, f'(x) = 1. So partial f(x) = {1}.
2
For x < 0: f is differentiable, f'(x) = -1. So partial f(x) = {-1}.
3
At x = 0: a subgradient g satisfies |y| >= 0 + g*y for all y. This requires g*y <= |y| for all y, i.e., g <= 1 (from y>0) and -g <= 1 (from y<0), giving -1 <= g <= 1.
$\partial|x||_{x=0} = [-1, 1]$
4
Combining: partial |x| = {sign(x)} for x != 0 and [-1,1] at x=0.
$\partial|x| = \begin{cases}\{1\} & x>0\\ [-1,1] & x=0\\ \{-1\} & x<0\end{cases}$

✓ Answer

partial|x| = sign(x) for x != 0, and [-1,1] at x=0.

Practice Problems

Mediumfree response

Derive the proximal operator prox_{alpha || . ||_1}(v) (soft-thresholding) for the L1 norm.

Common Mistakes

Common Mistake

Thinking a subgradient step always decreases the function value.

Unlike gradient descent for smooth functions, a subgradient step may not decrease f(x_t) -- even with the correct step size. The subgradient method guarantees convergence of the best iterate or the running average, but individual iterates can oscillate. This is why subgradient methods track x_best = argmin_{t<=T} f(x_t) rather than x_T.

Quiz

The subdifferential partial f(x) of a convex function f is always:

A single vector (the gradient)A convex compact setAn empty set if f is non-smoothEqual to the gradient even at non-smooth points

Historical Background

Subgradients were formalized by Rockafellar in his 1970 monograph Convex Analysis. Shor (1962) introduced subgradient methods for non-smooth optimization. Polyak (1978) developed the subgradient method with diminishing step sizes and proved convergence. The proximal gradient method (combining subgradients with proximity operators) became foundational in sparse signal processing and machine learning (LASSO, SVMs) in the 2000s.

1962
Shor introduces subgradient methods for non-smooth optimization
Naum Shor
1970
Rockafellar publishes Convex Analysis, formalizing subgradients
Ralph Tyrell Rockafellar
1978
Polyak proves convergence of subgradient methods
Boris Polyak
2004
Proximal gradient methods developed for sparse optimization (LASSO, etc.)
Patrick Combettes, Jean-Christophe Pesquet

Summary

Subgradient g of convex f at x: f(y) >= f(x) + <g, y-x> for all y. Subdifferential partial f(x) = set of all subgradients.
Subgradient method: x_{t+1} = x_t - alpha_t*g_t where g_t in partial f(x_t). Rate O(1/sqrt(T)).
Optimality: x* is optimal iff 0 in partial f(x*).
Proximal gradient: for f=g+h (g smooth, h non-smooth), use x_{t+1}=prox_{alpha h}(x_t - alpha*nabla g(x_t)). Rate O(1/T).

References

BookRockafellar, R.T. Convex Analysis. Princeton, 1970.
BookBoyd, S. and Vandenberghe, L. Convex Optimization. Cambridge, 2004.
WebsiteWikipedia -- Subgradient method