Subgradients and Subdifferentials

Why This Matters

Most modern ML objectives are not smooth. The L1 penalty in lasso regression is not differentiable at zero. The hinge loss in support vector machines kinks at the margin. The ReLU activation has no derivative at zero. The total-variation regularizer has gradient discontinuities at every level set.

Standard gradient-based optimization assumes the gradient exists, which is exactly what fails on these problems. The right replacement is the subgradient, which generalizes the gradient to convex but non-smooth functions. Every convex function has a non-empty subdifferential at every interior point of its domain, even where the gradient does not exist. This is what makes proximal gradient methods, the lasso, hinge-loss SVMs, and ADMM work as theory rather than heuristics.

This page is the foundational reference. Convex-optimization-basics covers the smooth case; this page covers the non-smooth case that nearly every sparsity-inducing or regularized ML method actually uses.

Definition

Definition

Subgradient

Let $f : \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ be convex. A vector $g \in \mathbb{R}^d$ is a subgradient of $f$ at $x$ if $f(y) \geq f(x) + \langle g, y - x \rangle \quad \text{for all } y \in \mathbb{R}^d.$ The set of all subgradients of $f$ at $x$ is the subdifferential: $\partial f(x) = \{g \in \mathbb{R}^d : f(y) \geq f(x) + \langle g, y - x\rangle \ \forall y\}.$

A subgradient is any vector $g$ such that the affine function $y \mapsto f(x) + \langle g, y - x\rangle$ stays below $f$ everywhere and touches it at $x$. This is the convex-analytic generalization of the tangent line: at a smooth convex function, only one such affine support exists (the tangent), and $g = \nabla f(x)$. At a kink, an entire family of supporting affine functions exists, and $\partial f(x)$ is the set of their slopes.

Examples

Absolute value $f(x) = |x|$ on $\mathbb{R}$.

$\partial f(x) = \begin{cases} \{1\} & x > 0 \\ [-1, 1] & x = 0 \\ \{-1\} & x < 0 \end{cases}$

Away from zero, $f$ is differentiable and the subdifferential is the singleton containing the derivative. At zero, every slope in $[-1, 1]$ gives a supporting line that stays below $|x|$. The subdifferential at the kink is the closed interval of all such slopes.

$\ell_1$ norm $f(x) = \|x\|_1 = \sum_i |x_i|$ on $\mathbb{R}^d$.

$\partial f(x) = \{g \in \mathbb{R}^d : g_i = \text{sign}(x_i) \text{ if } x_i \neq 0, \ g_i \in [-1, 1] \text{ if } x_i = 0\}.$

Coordinate-wise: each $g_i$ is the sign of $x_i$ at non-zero coordinates and any value in $[-1, 1]$ at zero coordinates. This is the subdifferential that drives soft-thresholding in proximal methods.

Hinge loss $f(x) = \max(0, 1 - x)$.

$\partial f(x) = \begin{cases} \{-1\} & x < 1 \\ [-1, 0] & x = 1 \\ \{0\} & x > 1 \end{cases}$

The slope is $-1$ in the loss region, $0$ in the no-loss region, and the entire interval $[-1, 0]$ at the kink. The kink at $x = 1$ is exactly the SVM margin.

Indicator function $\delta_C$ of a closed convex set $C$.

$\partial \delta_C(x) = \{g : \langle g, y - x\rangle \leq 0 \ \forall y \in C\} = N_C(x)$

This is the normal cone to $C$ at $x$: the set of outward-pointing directions that do not enter $C$. At interior points, $N_C(x) = \{0\}$; on the boundary, the normal cone is non-trivial. This is how convex constraints enter optimality conditions.

Smooth convex $f$. $\partial f(x) = \{\nabla f(x)\}$ at every point of differentiability.

Existence

Theorem

Existence of Subgradients

Statement

For any proper convex $f : \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ and any point $x$ in the relative interior of $\text{dom}\, f$, the subdifferential $\partial f(x)$ is non-empty, closed, convex, and bounded.

If $f$ is differentiable at $x$, then $\partial f(x) = \{\nabla f(x)\}$.

If $x$ is on the boundary of $\text{dom}\, f$ or $f$ is not lower semicontinuous at $x$, the subdifferential may be empty.

Intuition

Geometrically: a convex function has supporting hyperplanes at every interior point of its domain (this is the supporting hyperplane theorem applied to the epigraph). Each supporting hyperplane has a normal vector whose first $d$ coordinates form a subgradient. The set of such normals forms a closed convex bounded set, which is exactly the subdifferential.

Proof Sketch

Apply the supporting hyperplane theorem to the epigraph $\text{epi}\, f = \{(x, t) : t \geq f(x)\}$ at the boundary point $(x, f(x))$. The supporting hyperplane has normal $(g, -1)$ for some $g \in \mathbb{R}^d$ (the $-1$ is forced by the epigraph being "$t$-monotone"). The supporting condition becomes $f(y) - f(x) \geq \langle g, y - x\rangle$ for all $y$, which is exactly the subgradient inequality. Closure and convexity of $\partial f(x)$ follow because it is an intersection of half-spaces. Boundedness on the interior follows from $f$ being locally Lipschitz on the relative interior of its domain.

Why It Matters

Existence on the interior is what licenses every algorithm that picks "any subgradient" at each step. Without existence you could not even define a subgradient method, let alone analyze it. The boundary caveat matters for indicator functions of constraints, where the subdifferential at constraint boundaries is the normal cone (which can be unbounded).

Failure Mode

The subdifferential is empty at points outside $\text{dom}\, f$, and can be empty at boundary points where $f$ jumps from finite to $+\infty$. Example: $f(x) = -\sqrt{x}$ for $x \geq 0$, $f(x) = +\infty$ for $x < 0$. At $x = 0$, every "subgradient" $g$ would need $-\sqrt{y} \geq g \cdot y$ for all $y \geq 0$, which forces $g \leq -\sqrt{y}/y \to -\infty$ as $y \to 0^+$. No finite $g$ works, so $\partial f(0) = \emptyset$.

Optimality Condition

The single most important consequence of the subdifferential framework: it gives a clean optimality condition for non-smooth convex minimization.

Theorem

Subdifferential Optimality Condition

Statement

$x^*$ is a global minimizer of $f$ if and only if $0 \in \partial f(x^*).$ This is the non-smooth analogue of $\nabla f(x^*) = 0$ for smooth convex functions.

Intuition

The subgradient inequality $f(y) \geq f(x^*) + \langle g, y - x^*\rangle$ with $g = 0$ becomes $f(y) \geq f(x^*)$ for all $y$, which is exactly the definition of $x^*$ being a global minimizer. Conversely, if $x^*$ is a global minimizer, the constant subgradient $g = 0$ satisfies the defining inequality.

Proof Sketch

If $0 \in \partial f(x^*)$: By the subgradient inequality at $g = 0$, $f(y) \geq f(x^*) + 0 = f(x^*)$ for all $y$. So $x^*$ is a global minimizer.

If $x^*$ is a global minimizer: Take $g = 0$. Then $f(y) \geq f(x^*) = f(x^*) + \langle 0, y - x^*\rangle$ holds for all $y$, so $0 \in \partial f(x^*)$.

Why It Matters

This is the optimality condition used to derive the soft-thresholding operator (the proximal operator of the $\ell_1$ norm), to prove KKT conditions for constrained problems, and to characterize lasso solutions. For lasso $\min_w \tfrac{1}{2} \|y - Xw\|_2^2 + \lambda \|w\|_1$, the optimality condition $0 \in \partial f(w^*)$ becomes $X^\top(y - Xw^*) \in \lambda \, \partial \|w^*\|_1$, which gives the explicit characterization that $|X_j^\top(y - Xw^*)| \leq \lambda$ for zero coordinates of $w^*$ and equality with the right sign for non-zero coordinates.

Failure Mode

This optimality condition characterizes global minimizers; for non-convex $f$, $0 \in \partial f(x^*)$ (with $\partial$ generalized to Clarke subgradients) is necessary but not sufficient for local minimality, and saddle points satisfy it. The full strength of "iff global minimum" requires convexity.

Subgradient Calculus

The subdifferential satisfies calculus rules analogous to gradient rules, with a few caveats around equality versus containment.

Sum rule. For convex $f, g$, $\partial f(x) + \partial g(x) \subseteq \partial(f + g)(x)$, with equality if $\text{relint}(\text{dom}\, f) \cap \text{relint}(\text{dom}\, g) \neq \emptyset$.

Scalar multiplication. For $\alpha > 0$, $\partial(\alpha f)(x) = \alpha \, \partial f(x)$.

Affine pre-composition. For $f$ convex and $A \in \mathbb{R}^{m \times d}$, $b \in \mathbb{R}^m$, $\partial(f(Ax + b))(x) = A^\top \partial f(Ax + b)$.

Pointwise maximum. For convex $f_1, \ldots, f_m$ and $f(x) = \max_i f_i(x)$, $\partial f(x) = \text{conv}\!\left(\bigcup_{i \in I(x)} \partial f_i(x)\right)$ where $I(x) = \{i : f_i(x) = f(x)\}$ is the set of "active" functions at $x$.

The maximum-rule is what gives the subdifferential of the hinge loss and the dual norm, and it is the source of the convex hull appearing in many non-smooth optimality conditions.

The Subgradient Method

The simplest non-smooth optimization algorithm replaces the gradient in gradient descent with any subgradient.

Algorithm. Choose step sizes $\eta_k > 0$. At iteration $k$:

1. Pick any $g_k \in \partial f(x_k)$.
2. Update $x_{k+1} = x_k - \eta_k \, g_k$.

Unlike gradient descent on smooth functions, the subgradient method is not a descent method: $f(x_{k+1})$ can exceed $f(x_k)$ even with optimal step sizes. The standard guarantee is on the best iterate.

Convergence. For $f$ convex with subgradients of bounded norm $\|g\| \leq G$, and step sizes $\eta_k = c / \sqrt{k}$: $\min_{0 \leq j \leq k} f(x_j) - f^* = O\!\left(\frac{1}{\sqrt{k}}\right).$

This $O(1/\sqrt{k})$ rate is provably slower than the $O(1/k)$ rate of gradient descent on smooth convex functions, and the gap cannot be closed without exploiting structure. The slower rate is what motivates proximal methods: when the non-smooth term is a "simple" function (like the $\ell_1$ norm) whose proximal operator has a closed form, proximal-gradient methods recover the $O(1/k)$ rate by handling the smooth part with gradient descent and the non-smooth part exactly.

Common Confusions

Watch Out

Subgradient method is not a descent method

For smooth convex functions with gradient descent, every step reduces the objective. For non-smooth convex functions with the subgradient method, the objective can increase between iterations. The convergence guarantee is on the best iterate seen so far, $\min_{j \leq k} f(x_j)$, not on $f(x_k)$. This is why averaging schemes (Polyak averaging, Nemirovski-Yudin) are common in subgradient analyses.

Watch Out

Subgradients are only defined for convex functions

For non-convex functions, the convex-analytic subgradient does not exist in general. The Clarke subdifferential and the limiting subdifferential extend the concept to locally Lipschitz non-convex functions and provide necessary conditions for minimality, but the clean "iff global min" of the convex case is lost. ReLU networks are not convex, so the "subgradients" used in their training are Clarke subgradients (any element of the convex hull of limit-of-gradient sequences), not the subgradients defined here.

Watch Out

The subdifferential of a sum can be larger than the sum of subdifferentials

$\partial f + \partial g \subseteq \partial (f + g)$, with equality only under a constraint qualification (relint domain intersection non-empty). Without it, you can have a strict containment. Example: take $f(x) = -x$ on $(-\infty, 0]$ extended by $+\infty$, and $g(x) = x$ on $[0, \infty)$ extended by $+\infty$. Then $f + g$ is the indicator of $\{0\}$, and $\partial(f + g)(0) = \mathbb{R}$. But $\partial f(0) + \partial g(0)$ is computed at the boundary of each domain, where neither is finite. The qualification "relint domains intersect" rules this out.

Summary

• A subgradient of a convex $f$ at $x$ is any $g$ such that $f(y) \geq f(x) + \langle g, y - x\rangle$ for all $y$. The set of subgradients is the subdifferential $\partial f(x)$.
• Subdifferentials exist (non-empty, closed, convex, bounded) at every point in the relative interior of $\text{dom}\, f$.
• $x^*$ is a global minimizer of convex $f$ iff $0 \in \partial f(x^*)$. This is the non-smooth analogue of $\nabla f(x^*) = 0$.
• Subgradient calculus rules (sum, chain, pointwise max) follow gradient rules with constraint-qualification caveats.
• The subgradient method runs at $O(1/\sqrt{k})$, slower than gradient descent on smooth functions; proximal methods recover $O(1/k)$ when the non-smooth term has a tractable proximal operator.

Exercises

ExerciseCore

Problem

Compute the subdifferential of $f(x) = \max(0, x)$ (the ReLU function viewed as a univariate convex function) at every point. Then verify the optimality condition $0 \in \partial f(x^*)$ for the global minimizer.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Derive the soft-thresholding operator from the subdifferential optimality condition. Specifically, show that the unique solution to $\min_x \tfrac{1}{2}(x - z)^2 + \lambda |x|$ for $\lambda > 0$ is given by $x^* = \text{sign}(z) \max(|z| - \lambda, 0).$ This is the proximal operator of $\lambda |\cdot|$ at the point $z$.

Hint

Reveal Solution

References

Canonical:

• Rockafellar, "Convex Analysis" (Princeton, 1970), Sections 23-25
• Hiriart-Urruty and Lemarechal, "Fundamentals of Convex Analysis" (Springer, 2001), Chapter D
• Boyd and Vandenberghe, "Convex Optimization" (Cambridge, 2004), Section 3.1.5 (gradient and subgradient overlap), Appendix C

Convergence theory:

• Nesterov, "Introductory Lectures on Convex Optimization" (Springer, 2004), Section 3.2 (subgradient method)
• Bubeck, "Convex Optimization: Algorithms and Complexity" (Foundations and Trends in ML, 2015), Sections 3.1-3.2

ML applications:

• Beck, "First-Order Methods in Optimization" (SIAM, 2017), Chapters 3, 6, 10 (proximal operators, subgradient computations for ML losses)
• Parikh and Boyd, "Proximal Algorithms" (Foundations and Trends in Optimization, 2014)

Next Topics

• Proximal gradient methods: how to use subgradient structure efficiently when the non-smooth term is "simple"
• Lasso regression: the canonical application via soft-thresholding
• Convex duality: KKT conditions are subgradient optimality conditions for the Lagrangian