Dictionary of Applied Machine Learning: 147 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here
Updated on 2026-11-08
Readiness 94/100
See also deep net decision tree linear regression regularization explainable artificial intelligence Hilbert space
A Sobolev space is a set of functions whose derivatives, taken in a generalized sense, have bounded size. Machine learning (ML) methods whose hypothesis space is a ball in a Sobolev space with a bound on the gradient enforce a well-defined quantitative notion of robustness. Any hypothesis map in such a ball can be locally approximated by a linear map with bounded slope. A small change of the features of a data point therefore changes the prediction by at most a proportional amount. The generalized derivative is needed because hypothesis maps such as those of a deep net with rectified linear unit (ReLU) activation functions have kinks. A decision tree, whose hypothesis map jumps, belongs to no Sobolev space and admits no such guarantee. Linear regression whose hypothesis space is a ball in a Sobolev space, rather than the linear maps, is nonparametric regression. Sobolev norms also serve as regularizers, and they describe the reproducing kernel Hilbert space (RKHS) of a Matérn kernel.

sobolevspace.py, which recomputes what the entry states: the script block by block · open in ColabB-weakderivA weather service forecasts the
maximum temperature of a day from its minimum temperature.
Fig. 1(a) shows $20$ of the $366$ days of $2024$ at
the station Krems an der Donau of GeoSphere Austria as the data points of a
scatterplot, with
the minimum temperature of a day as its feature and the
maximum temperature as its label. The panel also shows
three hypotheses learned from these data points:
the non-linear map of a
deep net with rectified linear unit (ReLU) activation functions, the step
function of a depth-$2$ decision tree, and the curve of
linear regression with a Sobolev penalty term. A trustworthy
forecaster must not change its prediction, the forecast,
abruptly: a thermometer error of half a degree in
the minimum temperature must not move the forecast by several
degrees. Sobolev spaces make this requirement precise. They
consist of the functions whose derivatives have
bounded size (Evans, 2010, Ch. 5). A bound on the
derivative is a bound on how fast the forecast can change.
pythondemos/sobolevspace.pypythondemos/sobolevspace.py).
For $p \in [1,\infty]$, the Sobolev space $W^{1,p}(\Omega)$ consists of the functions whose weak derivatives exist and have finite $L^{p}$ norm $\left\lVert \cdot \right\rVert_{p}$. The case $p = 2$ gives the Hilbert space $H^{1}(\Omega)$, and the spaces $W^{k,p}(\Omega)$ require weak derivatives up to order $k$ (Adams and Fournier, 2003, Ch. 3, Thm. 3.6).
B-lipschitzThe case that matters most for machine learning (ML) is $W^{1,\infty}$, the functions with a bounded weak gradient. On a convex set $\Omega$, a function $f$ belongs to it with $\operatorname{ess\,sup}_{{\mathbf x} \in \Omega} \left\lVert \nabla f({\mathbf x}) \right\rVert_{2} \leq L$ precisely when it is Lipschitz continuous with constant $L$ (Evans, 2010, Sect. 5.8). Perturbing a feature vector by $\boldsymbol{\delta}$ then changes $f$ by at most $L \left\lVert \boldsymbol{\delta} \right\rVert_{2}$: convexity keeps the segment from ${\mathbf x}$ to ${\mathbf x} + \boldsymbol{\delta}$ inside $\Omega$, and integrating the gradient along it bounds the change by $L \left\lVert \boldsymbol{\delta} \right\rVert_{2}$. Conversely, the gradient of a Lipschitz continuous $f$ exists almost everywhere, and where it exists its length is the slope of $f$ in its own direction, at most $L$. The deep net of Fig. 1 has $L = 2.44$, so an error of $0.5\,^{\circ}$C in the minimum temperature moves its forecast by at most $1.22\,^{\circ}$C; the largest change among $20000$ random perturbations of that size was $1.21\,^{\circ}$C. The guarantee comes from the bound, not from the space: $W^{1,\infty}$ contains functions with every value of $L$. An ML method whose hypothesis space is the ball of functions with slope at most $L$ learns a robust hypothesis by construction, whatever the training set. The choice $p = \infty$ is what makes the bound hold at every feature vector; $H^{1}$ bounds the slope only on average. The bound concerns perturbations of the features only; robustness against perturbations of the training set is a property of the training map (see stability).
B-locallinearThe bound also says that near almost every feature vector the hypothesis agrees with a linear map whose slope is at most $L$ (Rademacher's theorem, Evans, 2010, Sect. 5.8.3, Thm. 6). This linear map is the explanation that gradient-based explainable artificial intelligence (XAI) delivers and that local interpretable model-agnostic explanations (LIME) fits from perturbed data points. For the forecast, it reads: one additional degree in the minimum adds $s(x)$ degrees to the forecast, with the slope $s(x)$ of Fig. 1(b) between $0$ and $2.44$. Since the deep net is piecewise linear, the approximation is exact whenever no kink lies between $x$ and $x + \delta$ for a perturbation $\delta$ of the minimum temperature, which is the case for most pairs with $|\delta| \leq 0.1\,^{\circ}$C.
B-spectralFor the deep net, the weak gradient is bounded by the product of the spectral norms of its weight matrices, i.e., of their largest singular values (Tsuzuku et al., 2018, Sects. 5.1 and 5.2), here $46.0$ against the true $2.44$: valid but loose. For a classifier that takes the sign of such an $f$, the bound certifies that no perturbation of Euclidean norm below $|f({\mathbf x})|/L$ changes the prediction, since $|f({\mathbf x} + \boldsymbol{\delta}) - f({\mathbf x})| \leq L \left\lVert \boldsymbol{\delta} \right\rVert_{2} < |f({\mathbf x})|$ leaves the sign of $f$ unchanged (Tsuzuku et al., 2018, Prop. 2). The decision tree of Fig. 1(a) has no such bound: at its root threshold of $5.5\,^{\circ}$C, a change of $2 \cdot 10^{-9}\,^{\circ}$C in the minimum temperature moves the forecast by $7.81\,^{\circ}$C. A jump has no weak derivative that is a function (Evans, 2010, Sect. 5.2, Example 2), so no Sobolev space contains the tree.
B-nonparamSobolev spaces also serve as hypothesis spaces in their own right.
Plain linear regression minimizes the average squared error loss over the
linear maps. Replacing the linear maps by a ball in $H^{1}$, or
equivalently adding the squared $H^{1}$ seminorm
$\int_{\Omega} \left\lVert \nabla f({\mathbf x}) \right\rVert_{2}^{2} \, \mathrm{d}{\mathbf x}$
as a penalty term, a norm that ignores constant shifts of
$f$ (see regularization), gives
nonparametric regression (Wainwright, 2019, Sects. 13.1.2 and 13.4). The
dotted curve of Fig. 1(a) minimizes the
training error plus ten times that seminorm; it reaches a
training error of $18.03$, below the $18.66$ of the deep net,
with slope at most $3.05$ (pythondemos/sobolevspace.py).
A computer cannot search all of $H^{1}$, and it need not. For a scalar feature, where $\Omega$ is an interval of the real line, a minimizer of the training error plus the seminorm is piecewise linear with kinks at the $m$ data points, since between two data points the straight line has the smallest seminorm for given end values (a consequence of the Cauchy–Schwarz inequality). The search therefore runs over $m$ numbers, the values at the kinks; this is kernel ridge regression with the reproducing kernel Hilbert space (RKHS) of $H^{1}$ (Wainwright, 2019, Sect. 12.5.2 and Example 12.16). For a piecewise linear function the seminorm is a sum of squared slopes, one per segment and weighted by its length, so the normal equations of the penalized problem form one linear system.
B-graphThe seminorm expresses the smoothness assumption. Its counterpart for a function on the nodes of a graph replaces the gradient by differences across edges, 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 (Chambolle and Pock, 2016, Sect. 7.1; Rudin et al., 1992). The RKHS of a Matérn kernel is a Sobolev space $W^{s,2}(\Omega)$ whose order $s$ is set by the smoothness parameter of the kernel (Kanagawa et al., 2018, Example 2.6). A kernel method with that kernel is therefore again nonparametric regression over a Sobolev ball, the setting of Wainwright (2019, Ch. 13) above.
Finally, a bound $L$ is also of regulatory interest. Article 15 of the EU AI Act requires a high-risk artificial intelligence system (high-risk AI system) to be robust and to have its accuracy metrics declared in the instructions for use (European Parliament and Council of the European Union, 2024). A Lipschitz constant is such a metric: it states, as a single number, how much a perturbation of a feature vector can change the prediction.
See also: Lipschitz continuity, robustness, stability, deep net, decision tree, linear regression, regularization, explainable artificial intelligence, local interpretable model-agnostic explanations, smoothness assumption, generalized total variation, generalized total variation minimization, reproducing kernel Hilbert space, Hilbert space, differentiable.
@misc{dictml_sobolevspace,
author = {Jung, Alexander},
editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
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-11-20},
url = {https://dictionaryofml.org/terms/sobolevspace.html}
}