Lipschitz Continuity

How it works — the slope-cone picture

Pick any two points (x, f(x)) and (y, f(y)) on the graph of f. The Lipschitz condition says the slope of the secant line connecting them is bounded — its absolute value never exceeds L. Equivalently: for any point p on the graph, the entire rest of the graph lies inside a double cone of slope ±L emanating from p. Slide the cone along the graph; the graph never escapes.

This is exactly the failure mode of √x at x = 0: the secant slope from (0, 0) to (h, √h) is √h / h = 1/√h, which blows up as h → 0. No finite L works, so √x is not Lipschitz on [0, 1] (it is, however, ½-Hölder there). It is the failure mode of any cusp, vertical tangent, or unbounded-derivative singularity — geometrically a slope cone with finite L cannot contain the graph through such a point.

The Lipschitz constant of f is the smallest L that works:

Lip(f) = sup { |f(x) − f(y)| / |x − y| : x ≠ y }

If f is differentiable, Lip(f) = sup|f′|. If f is convex, the supremum is attained as the limit of secant slopes as the endpoints push apart — convex Lipschitz functions are characterized by bounded subgradients.

Proof sketch — Lipschitz ⇔ bounded derivative (compact case)

Suppose f: [a, b] → ℝ is C¹ with |f′(x)| ≤ M for all x. By the mean value theorem, for any x, y ∈ [a, b] there exists c between them with f(x) − f(y) = f′(c)(x − y), so |f(x) − f(y)| = |f′(c)| · |x − y| ≤ M |x − y|. Hence f is M-Lipschitz. Conversely, if f is L-Lipschitz and differentiable at x, then |f′(x)| = lim |f(x + h) − f(x)|/|h| ≤ L. So the Lipschitz constant equals the supremum of |f′| over the differentiability set — and by Rademacher this is almost-everywhere.

For Picard-Lindelöf: define the integral operator T(y)(t) = y₀ + ∫_{t₀}^t f(s, y(s)) ds on a sufficiently small interval [t₀, t₀ + h] and the closed ball B around y₀ in sup-norm. If f is L-Lipschitz in y, then:

|T(y₁)(t) − T(y₂)(t)| ≤ ∫ L · |y₁(s) − y₂(s)| ds ≤ L · h · ‖y₁ − y₂‖_∞

Pick h < 1/L; then T is a strict contraction on the Banach space C([t₀, t₀ + h]). The Banach fixed-point theorem gives a unique fixed point, which is the unique solution to the ODE. The Lipschitz constant L controls the largest interval h on which uniqueness holds.

Variants and related conditions

• Locally Lipschitz. f is L-Lipschitz on a neighbourhood of every point but L may depend on the neighbourhood. Examples: every C¹ function on an open set. Many results (including Picard-Lindelöf in extended form) only need local Lipschitz.
• Hölder continuous. α-Hölder if |f(x) − f(y)| ≤ C|x − y|^α with 0 < α ≤ 1. Lipschitz is α = 1. Brownian motion is α-Hölder for every α < ½ but not for α = ½.
• Contraction. Lipschitz with L < 1. Banach's fixed-point theorem applies to contractions on complete metric spaces.
• Bi-Lipschitz. Both f and its inverse f⁻¹ are Lipschitz. Bi-Lipschitz maps preserve metric structure up to a multiplicative constant — closer to a coarse isometry than a homeomorphism.
• Lipschitz on a metric space. Same condition with d_X and d_Y replacing absolute values. Bounded linear operators on Banach spaces are Lipschitz with constant ‖T‖.
• Lipschitz gradient (L-smooth). The function is C¹ with ‖∇f(x) − ∇f(y)‖ ≤ L‖x − y‖. Equivalently, the Hessian (when it exists) has spectral norm ≤ L. The fundamental smoothness assumption in convex optimization.
• Cocoercive. A stronger condition: ⟨∇f(x) − ∇f(y), x − y⟩ ≥ (1/L) ‖∇f(x) − ∇f(y)‖². Equivalent to L-smoothness for convex f and gives sharper convergence rates.

Numerical examples

Examples and non-examples on [0, 1] or all of ℝ:

f(x) = 3x + 1               Lipschitz with L = 3 (any linear function: L = |slope|)
f(x) = sin x                 Lipschitz with L = 1 (since |cos x| ≤ 1)
f(x) = x²                    Lipschitz on [-M, M] with L = 2M (unbounded on ℝ)
f(x) = |x|                   1-Lipschitz on ℝ — but NOT differentiable at 0
f(x) = √x  on [0, 1]         NOT Lipschitz — slope unbounded near 0; is ½-Hölder
f(x) = x · sin(1/x)          continuous on (0, 1] extended by f(0) = 0,
                             continuous on [0, 1] but NOT Lipschitz (oscillation)
ReLU                         1-Lipschitz on ℝ
softmax                      1-Lipschitz on ℝⁿ in ℓ₂ norm
Conv layer with kernel K     Lipschitz with L = ‖K‖_2 (spectral norm)

Gradient descent example: minimize f(x) = ½xᵀAx − bᵀx where A is positive definite with eigenvalues in [μ, L] (μ is strong convexity, L is gradient-Lipschitz constant). Step size 1/L gives:

‖x_k − x*‖² ≤ (1 − μ/L)^k · ‖x₀ − x*‖²

So the error halves every L/μ · log 2 ≈ 0.69 L/μ iterations. The condition number κ = L/μ determines the rate. For badly conditioned problems (κ = 10⁴), 10⁴ iterations per digit of accuracy. Acceleration (Nesterov's method) improves this to O(√κ) per digit. L is the rate-determining hyperparameter.

Common pitfalls

• "Continuous on a compact set ⇒ Lipschitz." False. Continuous on a compact set ⇒ uniformly continuous (Heine-Cantor), but not Lipschitz. √x on [0, 1] is the standard counterexample.
• "Differentiable ⇒ Lipschitz." Only on compact sets, or where the derivative is bounded. f(x) = x² is differentiable everywhere on ℝ but its derivative 2x is unbounded — hence not globally Lipschitz on ℝ.
• "Lipschitz constant is the supremum of slopes between nearby points." No — it's the supremum over all pairs, near or far. A bounded oscillation can still produce a large secant slope between far-apart points.
• "Pointwise sup |f′| equals Lipschitz constant always." True for C¹ on intervals (mean value theorem). For nondifferentiable Lipschitz functions, you must take sup of |f′| over its differentiability set (a.e. by Rademacher), or use the essential supremum.
• "Lipschitz suffices for everything Picard-Lindelöf needs." You also need continuity in t (the first argument) — typically uniform Lipschitz in y and continuous in t, or measurable in t plus Lipschitz in y for Carathéodory ODEs.
• "Lipschitz on a domain extends to its closure." True for the boundary points by continuity, but be careful: the function √x · sin(1/x) is bounded and continuous on (0, 1], extends continuously to [0, 1], but is not Lipschitz anywhere.

Where Lipschitz shows up

• ODE theory. Picard-Lindelöf: Lipschitz right-hand side guarantees existence and uniqueness of solutions. Local Lipschitz suffices for local existence. Without it, the example y′ = √|y|, y(0) = 0 admits two solutions and dynamics is ambiguous.
• Convex optimization. L-smoothness (Lipschitz gradient) gives O(1/k) convergence for gradient descent and O(1/k²) for accelerated methods. Lipschitz constant on the objective sets the step size and dictates the iteration count to reach target accuracy.
• Probability theory. Wasserstein-1 distance W₁(μ, ν) = sup{∫f dμ − ∫f dν : f 1-Lipschitz}. The Kantorovich-Rubinstein duality. Used in optimal transport, generative modelling (WGAN), and concentration inequalities.
• Concentration of measure. Lipschitz functions of independent random variables concentrate sharply: McDiarmid's inequality bounds tail probabilities of any L-Lipschitz function of n independent inputs by exp(−2t²/(nL²)). Foundation of statistical learning bounds.
• Adversarial robustness. A classifier with Lipschitz constant L can change its output by at most L·δ when input is perturbed by δ. Certified robustness radius is r = margin / L. Spectral normalization in deep networks aims to minimize L.
• Computer graphics and geometry processing. Lipschitz maps preserve metric structure up to scale; bi-Lipschitz parameterizations are sought for texture mapping with bounded distortion.
• Computational complexity. Lipschitz functions on the hypercube can be approximated to ε in O(1/ε)ⁿ samples (curse of dimensionality), but with strong-Lipschitz or low-effective-dimension structure the bound improves dramatically.
• PDE regularity. Solutions to elliptic and parabolic PDEs are typically Lipschitz or Hölder on the boundary; Schauder and Calderón-Zygmund estimates upgrade Hölder to higher regularity.