Dictionary of Applied Machine Learning
Typeset PDF version — the authoritative form of this entry
Python demo — a script that recomputes what this entry states and prints one line per check
A supplier of a high-risk artificial intelligence system (high-risk AI system), such as a classifier that screens medical images, must be able to state how much a prediction can change when the feature vector of a data point is perturbed slightly. Sobolev spaces make such a statement precise: they consist of the functions whose derivatives, in a generalized sense, have bounded size (Evans, 2010, Ch. 5).
P-weakderivThe generalization is needed because the functions of interest are typically not differentiable everywhere. A function $g_{\featureidx}$ is a weak partial derivative of $f: \Omega \to \reals$, on an open set $\Omega \subseteq \reals^{\nrfeatures}$, if \[ \int_{\Omega} f(\featurevec) \frac{\partial \varphi(\featurevec)}{\partial \feature_{\featureidx}} \, \mathrm{d}\featurevec = - \int_{\Omega} g_{\featureidx}(\featurevec) \varphi(\featurevec) \, \mathrm{d}\featurevec \] holds for every infinitely differentiable $\varphi$ that vanishes outside a bounded subset of $\Omega$ (Evans, 2010, Sect. 5.2). The identity is integration by parts, with all derivatives moved onto $\varphi$. Both sides are Lebesgue integrals, so $f$ and $g_{\featureidx}$ need only be integrable on bounded subsets of $\Omega$. For an integer $k \geq 1$ and $p \in [1,\infty]$, the Sobolev space $W^{k,p}(\Omega)$ consists of the functions whose weak derivatives up to order $k$ exist and have finite $\normgeneric{\cdot}{p}$; the case $p=2$ gives the Hilbert space $H^{k}(\Omega) = W^{k,2}(\Omega)$.
P-certifiedThe case that matters most for machine learning (ML) is $W^{1,\infty}$, the
functions with a bounded weak gradient. A
function $f$ belongs to it, with
\[
\sup_{\featurevec \in \Omega} \normgeneric{\nabla f(\featurevec)}{2} \leq L
\text{,}
\]
precisely when it is Lipschitz continuous with constant
$L$ (Evans, 2010, Sect. 5.8). The bound therefore reads as a
robustness guarantee: perturbing a feature vector by
$\boldsymbol{\delta}$ changes the value of $f$ by at most
$L \normgeneric{\boldsymbol{\delta}}{2}$. Fig. 1
contrasts a function with a bounded weak gradient and one
without.
P-jumpAn artificial neural network (ANN) with rectified linear unit (ReLU) activation functions is the case that makes the
weak derivative indispensable: such a hypothesis is
piecewise linear, so its classical gradient does not exist along
the kinks, while its weak gradient exists and is bounded by the
product of the largest singular values of the weight matrices.
For a two-layer ReLU ANN on $\reals^{2}$, that
product gives $L \leq 4.94$ while the smallest valid constant is
$2.12$: the bound holds but is loose. Drawing $60000$ perturbations
inside the certified radius $\gamma / L$ produced no change of the
prediction (pythondemos/sobolevspace.py). By contrast, a decision tree is piecewise
constant with jumps and has no bounded weak gradient at all: in
the same experiment, a stump changes its prediction across a
perturbation of Euclidean norm $2 \cdot 10^{-9}$, so no certified
radius exists for it, however large the margin.
A certified radius is also of regulatory interest. Article 15 of the EU AI Act requires a high-risk AI system to reach an appropriate level of robustness and to perform consistently, to be as resilient as possible to errors and inconsistencies, and to have its accuracy levels and metrics declared in the instructions for use (Parliament and Union, 2024). A certified radius is such a metric: it states, as a single number, how large a perturbation of a feature vector the prediction provably survives.
P-graphSobolev spaces also underlie two regularizers used in ML.
Penalizing the squared $H^{1}$ seminorm
\[
\int_{\Omega} \normgeneric{\nabla f(\featurevec)}{2}^{2} \, \mathrm{d}\featurevec
\]
expresses the smoothness assumption; its counterpart for a function
defined on the nodes of a graph replaces the gradient by
differences across edges, which is the form used by generalized total variation (GTV) and
generalized total variation minimization (GTVMin) (SarcheshmehPour et al., 2023). Penalizing the
gradient in $L^{1}$ instead gives total variation
regularization, which allows jumps: as a transition of width
$\varepsilon$ sharpens, its squared $H^{1}$ seminorm grows without
bound, while its total variation stays at the height of the limiting jump
(pythondemos/sobolevspace.py). This is why total variation
regularization is used in image denoising
(Rudin et al., 1992). Kernels connect to
Sobolev spaces as well. For a Mat\'ern kernel with smoothness
parameter $\nu > 0$ on a domain
$\Omega \subseteq \reals^{\nrfeatures}$ with Lipschitz boundary,
and for $s \defeq \nu + \nrfeatures/2$ an integer, the reproducing kernel Hilbert space (RKHS) of
the kernel is $W^{s,2}(\Omega)$ as a set of functions,
and the two norms are equivalent: there are
$c_{1}, c_{2} > 0$ with
$c_{1} \normgeneric{f}{W^{s,2}(\Omega)} \leq
\normgeneric{f}{\hilbertspace_{\kernel}} \leq
c_{2} \normgeneric{f}{W^{s,2}(\Omega)}$
for every $f$ in the RKHS
(Rasmussen and Williams, 2006, Eq. 4.15;
Wendland, 2005, Cor. 10.48;
Kanagawa et al., 2018, Example 2.6).
The penalty term of the corresponding regularized empirical risk minimization (RERM) is therefore a
Sobolev norm, and the smoothness it enforces is again weak: the
functions of this RKHS have weak derivatives up to
order $s$, while they are guaranteed to be differentiable in the
classical sense only up to order $\nu$
(Kanagawa et al., 2018, Remark 2.11).
See also: Lipschitz continuity, robustness, smoothness assumption, generalized total variation, generalized total variation minimization, reproducing kernel Hilbert space, Hilbert space, differentiable, Lebesgue integral.
@misc{dictml_sobolevspace,
author = {Jung, Alexander},
title = {Sobolev space},
howpublished = {Dictionary of Applied Machine Learning (course edition)},
year = {2026},
doi = {10.5281/zenodo.21569296},
note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-08-17},
url = {https://dictionaryofml.org/terms/sobolevspace.html}
}