The Subdifferential: Subgradients of Convex Functions

The precise definition and what it claims

Let f: ℝⁿ → ℝ ∪ {+∞} be a convex function (a proper one — not identically +∞ and never −∞), and let x be a point where f(x) is finite. A vector g ∈ ℝⁿ is a subgradient of f at x if the affine minorant it defines lies below the graph:

• f(y) ≥ f(x) + ⟨g, y − x⟩ for all y ∈ ℝⁿ.

The subdifferential ∂f(x) is the collection of all such g. The inequality says: the hyperplane through (x, f(x)) with slope g is a global affine lower bound touching the graph at x — a supporting hyperplane of the epigraph.

Three structural facts follow immediately. First, ∂f(x) is always a closed convex set (an intersection of closed half-spaces, one per y). Second, it may be empty, a singleton, or a fat set. Third — the punchline — g = 0 satisfies the inequality precisely when f(y) ≥ f(x) for all y, so 0 ∈ ∂f(x) if and only if x is a global minimizer. This is Fermat's rule for the nonsmooth world.

The geometric picture: supporting lines at a kink

Picture the graph of a convex function as a bowl. At a smooth point there is exactly one tangent line, and it lies below the whole curve — that unique slope is ∇f(x), so ∂f(x) is a single point. But at a corner, like the vertex of |x|, no single tangent exists. Instead a whole fan of lines pivots through the kink, each staying below the graph.

For |x| at 0, every line y = gx with slope g ∈ [−1, 1] satisfies |y| ≥ g·y, so ∂f(0) = [−1, 1]. As you slide the slope from −1 up to +1 you sweep out all the supporting lines that touch the vertex. The endpoints are the one-sided derivatives: the left slope f′₋(0) = −1 and the right slope f′₊(0) = +1.

This is general in one dimension: for a finite convex f, ∂f(x) = [f′₋(x), f′₊(x)], the closed interval between the left and right derivatives. The gradient fails to exist exactly when this interval has positive length — when the two one-sided slopes disagree.

The mechanism: existence via a supporting hyperplane

Why does ∂f(x) ever contain anything? The engine is the Hahn–Banach / supporting hyperplane theorem applied to the epigraph epi f = {(y, t) : t ≥ f(y)}, which is a convex set in ℝⁿ⁺¹.

The construction: fix a point x in the relative interior of dom f. The point (x, f(x)) sits on the boundary of epi f, since you cannot go any lower. Because epi f is convex, the supporting hyperplane theorem provides a nonzero (a, β) ∈ ℝⁿ × ℝ with ⟨a, y⟩ + βt ≥ ⟨a, x⟩ + β f(x) for all (y, t) ∈ epi f. Pushing t → +∞ forces β ≥ 0; a short argument using x ∈ ri(dom f) rules out β = 0 (a vertical hyperplane would separate an interior point, contradiction). Normalizing so β = 1 and setting g = −a yields exactly the subgradient inequality.

The conclusion is the nonemptiness theorem: if x ∈ ri(dom f), then ∂f(x) ≠ ∅. The relative-interior hypothesis is doing real work — it is what guarantees the separating hyperplane is not vertical.

Worked example: the max of finitely many affine functions

Take f(x) = max{ ⟨a₁, x⟩ + b₁, …, ⟨aₘ, x⟩ + bₘ }, a piecewise-linear convex function — the building block of linear programming and of hinge losses. Let I(x) = { i : the i-th term achieves the max at x } be the active index set.

The Danskin / max-rule gives the subdifferential exactly as a convex hull:

• ∂f(x) = conv{ aᵢ : i ∈ I(x) }.

Where a single affine piece is strictly on top, I(x) is a singleton and ∂f(x) = {aᵢ}: f is differentiable there. On the ridge where two pieces tie, ∂f(x) = [aᵢ, aⱼ] is the segment between their gradients — a fat set, and the graph has a crease.

Concretely, f(x) = max(x, −x) = |x| has a₁ = 1, a₂ = −1; at 0 both are active, so ∂f(0) = conv{1, −1} = [−1, 1], recovering the interval. This example is why the subdifferential is central to subgradient descent: at a kink you simply pick any g ∈ ∂f(x) and step opposite to it.

Why the hypotheses matter — and where it breaks

Convexity is essential. The defining inequality demands a global affine minorant; only convex functions have one at every interior point. For f(x) = −|x|, no line through the vertex stays below the graph, so ∂f(0) = ∅ — the subdifferential machinery simply does not apply to nonconvex f (the Clarke subdifferential is the correct generalization there).

The relative interior matters. At the boundary of the domain the subdifferential can be empty even for a nice convex function: extend f(x) = −√(1 − x²) by +∞ outside [−1, 1]; at x = 1 the tangent is vertical, no finite-slope line supports the graph, and ∂f(1) = ∅.

The sum rule needs a qualification. Always ∂f(x) + ∂g(x) ⊆ ∂(f + g)(x). The reverse inclusion — the Moreau–Rockafellar theorem — requires a constraint qualification such as ri(dom f) ∩ ri(dom g) ≠ ∅. Without it, equality can fail: two functions whose domains meet only at a single boundary point can have ∂f + ∂g strictly smaller than ∂(f+g).

Why it matters: optimality, duality, and algorithms

The subdifferential is the load-bearing concept of modern nonsmooth optimization.

• Fermat's rule. The clean statement 0 ∈ ∂f(x) ⟺ global minimum turns optimality into an inclusion. Adding constraints, ∂(f + δ_C)(x) ∋ 0 recovers the KKT conditions via the normal cone N_C.
• Duality. The subdifferential is the inverse of the gradient of the convex conjugate: g ∈ ∂f(x) ⟺ x ∈ ∂f*(g) ⟺ f(x) + f*(g) = ⟨g, x⟩ (the Fenchel–Young equality). This bijection is the backbone of Fenchel and Lagrangian duality.
• Algorithms. Subgradient methods, the proximal operator prox_f (defined via (I + ∂f)⁻¹, a genuine single-valued map because ∂f is a maximal monotone operator), ADMM, and mirror descent all run on subgradients. The proximal step is exactly resolvent of the subdifferential.

In machine learning this is why you can 'differentiate' the ℓ₁ penalty, the hinge loss (SVMs), and ReLU networks: each has a well-defined subdifferential, and optimizers select an element of it. The concept, developed by Jean-Jacques Moreau and R. Tyrrell Rockafellar around 1963–1970, made non-smooth convexity as computable as the smooth case.

The subdifferential across canonical convex functions on ℝ (at the interesting point)

Function f(x)	Point x	∂f(x)	Interpretation
|x|	0	[−1, 1]	Kink: an interval of slopes; 0 ∈ [−1,1] certifies 0 is a global minimizer of |x| (strictness is a separate fact not implied by 0 ∈ ∂f(0))
|x|	x > 0	{1}	Smooth region: subdifferential is the single derivative
max(x, 0) (ReLU)	0	[0, 1]	Convex combinations of the left slope 0 and right slope 1
Indicator δ_C(x) of convex set C	x ∈ C	Normal cone N_C(x)	Subdifferential of a set-membership penalty is its normal cone
x²	any x	{2x}	Differentiable everywhere: gradient recovered exactly
−√(1 − x²) extended by +∞ off [−1,1]	x = 1	∅	Boundary of domain with vertical tangent: subdifferential can be empty