\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{algorithm,algpseudocode}
\usepackage{bm}
\usepackage{hyperref}
\usepackage{float}
\usepackage{subcaption}
\usepackage{enumitem}
\usepackage{xcolor}
\definecolor{darkgreen}{rgb}{0.0, 0.5, 0.0}
\definecolor{aaltoBlue}{RGB}{0, 51, 102}
\definecolor{pinegreen}{cmyk}{0.92,0,0.59,0.25}
\definecolor{royalblue}{cmyk}{1,0.50,0,0}
\definecolor{lavander}{cmyk}{0,0.48,0,0}
\definecolor{violet}{cmyk}{0.79,0.88,0,0}
\definecolor{lightblue}{RGB}{173, 216, 230}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{calc,arrows.meta,positioning,fit,shapes.geometric,shapes.misc,intersections,patterns,decorations.pathreplacing,backgrounds,matrix}
\usepgfplotslibrary{fillbetween,groupplots}
\setcounter{secnumdepth}{-\maxdimen}
% Long unbreakable tokens (the ISO/IEC author names in citations, term names
% in the title) otherwise overflow the margin by a few points; a modest
% emergency stretch lets TeX loosen the paragraph instead.
\emergencystretch=2em
\usepackage{mleftright}
% Project macros used by this entry (auto-extracted).
\newcommand{\feature}{x}
\newcommand{\featuredim}{d}
\newcommand{\featureidx}{j}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\newcommand{\learnthypothesis}{\widehat{\hypothesis}}
\newcommand{\lipschitzconstant}{L}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrfeatures}{\featuredim}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\samplesize}{m}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{Sobolev space}

\subsection*{Author and editors}
Alexander Jung\textsuperscript{*}, Department of Computer Science, Aalto University, Espoo, Finland (ORCID \mbox{\href{https://orcid.org/0000-0001-7538-0990}{0000-0001-7538-0990}}) \\
Editors: Konstantina Olioumtsevits (ORCID \mbox{\href{https://orcid.org/0000-0003-2697-8659}{0000-0003-2697-8659}}), Ekkehard Schnoor (ORCID \mbox{\href{https://orcid.org/0000-0001-8252-1499}{0000-0001-8252-1499}}), Aalto University, Espoo, Finland \\
\textsuperscript{*}Corresponding author: \href{mailto:alex.jung@aalto.fi}{alex.jung@aalto.fi}



\subsection{Abstract}
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\'ern kernel.

\subsection{Definition}
A weather service forecasts the
		maximum temperature of a day from its minimum temperature.
		Fig.~\ref{fig_sobolev_dict}(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.
		\begin{figure}[H]
			\begin{center}
			\begin{tikzpicture}
			\begin{axis}[
				name=panelA,
				width=0.47\linewidth, height=0.42\linewidth,
				axis lines=left,
				xlabel={minimum temperature of the day ($^{\circ}$C)},
				ylabel={maximum temperature of the day ($^{\circ}$C)},
				ymin=-8, ymax=40,
				tick label style={font=\scriptsize},
				label style={font=\scriptsize},
				legend style={draw=none, fill=none, font=\scriptsize,
					at={(0.0,-0.3)}, anchor=north west},
				legend cell align=left,
				]
				\addplot[only marks, mark=o, mark size=1.5pt, color=black!45]
					table[col sep=comma, x=tmin, y=tmax]{sobolevspace_scatter_plot.csv};
				\addlegendentry{every 19th day}
				\addplot[thick]
					table[col sep=comma, x=tmin, y=pred]{sobolevspace_net.csv};
				\addlegendentry{deep net}
				\addplot[thick, dashed]
					table[col sep=comma, x=tmin, y=pred]{sobolevspace_tree.csv};
				\addlegendentry{decision tree}
				\addplot[thick, dotted]
					table[col sep=comma, x=tmin, y=pred]{sobolevspace_spline.csv};
				\addlegendentry{penalized linear regression}
			\end{axis}
			\node[font=\scriptsize] at ([yshift=-28mm]panelA.south) {(a)};
			\begin{axis}[
				name=panelB, at={(panelA.east)}, anchor=west, xshift=1.3cm,
				width=0.47\linewidth, height=0.42\linewidth,
				axis lines=left,
				xlabel={minimum temperature of the day ($^{\circ}$C)},
				ylabel={slope of $\learnthypothesis$},
				ymin=-0.3, ymax=3.4,
				tick label style={font=\scriptsize},
				label style={font=\scriptsize},
				legend style={draw=none, fill=none, font=\scriptsize,
					at={(0.0,-0.3)}, anchor=north west},
				legend cell align=left,
				]
				\addplot[thick]
					table[col sep=comma, x=tmin, y=slope]{sobolevspace_net.csv};
				\addlegendentry{weak derivative}
				\addplot[dotted, thick] coordinates {(-11.1,2.44) (21.8,2.44)};
				\addlegendentry{Lipschitz bound}
				\addplot[dashed, ->, thick] coordinates {(0.25,0) (0.25,2.0)};
				\addlegendentry{jumps of the tree}
				\addplot[dashed, ->, thick, forget plot] coordinates {(5.5,0) (5.5,2.0)};
				\addplot[dashed, ->, thick, forget plot] coordinates {(11.85,0) (11.85,2.0)};
			\end{axis}
			\node[font=\scriptsize] at ([yshift=-28mm]panelB.south) {(b)};
			\end{tikzpicture}
			\end{center}
		\caption{Forecasting the maximum temperature of a day at Krems an der Donau
			from its minimum temperature. (a) Scatterplot of every
			$19$th day of $2024$, $20$ of the $366$ days (circles), and three
			hypotheses learned from all $366$ days: the non-linear
			map of a deep net with ReLU activation functions (solid
			curve), the step function of a depth-$2$ decision tree
			(dashed curve), and the curve of linear regression with a Sobolev
			penalty term (dotted curve).
			(b) The slope of the deep net hypothesis
			$\learnthypothesis$ is a step function, its weak
			derivative, and stays below the bound
			$\lipschitzconstant = 2.44$ (dotted line), so a perturbation $\delta$ of the minimum temperature
			moves the forecast by at most $2.44\,|\delta|$. The tree has no
			such bound: at each of its thresholds (arrows) the forecast
			jumps. Data generated by \texttt{pythondemos/sobolevspace.py}
			\label{fig_sobolev_dict}}
		\end{figure}
		The derivative is understood in a generalized sense,
		since the deep net of Fig.~\ref{fig_sobolev_dict}(a) has kinks
		and no classical derivative exists there. The generalized derivative starts from integration instead
		of differentiation. On the real line, a function with
		$f(x) = f(a) + \int_{a}^{x} g(t) \, \mathrm{d}t$ is the integral of
		its slope $g$, and $g$ is
		called a weak derivative of $f$. On an open set
		$\Omega \subseteq \reals^{\nrfeatures}$, consider an infinitely
		differentiable test function $\varphi$ that vanishes
		outside a bounded subset of $\Omega$. A function
		$g_{\featureidx}$ is a weak partial derivative of $f$ if, for
		every such $\varphi$
		(Evans, 2010, Sect.~5.2),
		\[
			\int_{\Omega} f(\featurevec) \frac{\partial \varphi(\featurevec)}{\partial \feature_{\featureidx}} \, \mathrm{d}\featurevec
			= - \int_{\Omega} g_{\featureidx}(\featurevec) \varphi(\featurevec) \, \mathrm{d}\featurevec \text{.}
		\]
		This is integration by parts with all derivatives moved onto
		$\varphi$. It holds when $f$ is the integral of $g_{\featureidx}$
		along the $\featureidx$th coordinate, and it does not require a
		derivative of $f$ at any particular point. The slope of the deep net, the step
		function of Fig.~\ref{fig_sobolev_dict}(b), satisfies it for
		every test function tried
		(\texttt{pythondemos/sobolevspace.py}).
\par
		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 $\normgeneric{\cdot}{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).
\par
		The 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}_{\featurevec \in \Omega} \normgeneric{\nabla f(\featurevec)}{2} \leq \lipschitzconstant$
		precisely when it is Lipschitz continuous with constant
		$\lipschitzconstant$ (Evans, 2010, Sect.~5.8). Perturbing a
		feature vector by $\boldsymbol{\delta}$ then changes $f$ by at
		most $\lipschitzconstant \normgeneric{\boldsymbol{\delta}}{2}$:
		convexity keeps the segment from $\featurevec$ to
		$\featurevec + \boldsymbol{\delta}$ inside $\Omega$, and integrating
		the gradient along it bounds the change by
		$\lipschitzconstant \normgeneric{\boldsymbol{\delta}}{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 $\lipschitzconstant$. The
		deep net of Fig.~\ref{fig_sobolev_dict} has
		$\lipschitzconstant = 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 $\lipschitzconstant$. An ML method whose
		hypothesis space is the ball of functions with slope at most
		$\lipschitzconstant$ 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).
\par
		The bound also says that near almost every feature vector the hypothesis
		agrees with a linear map whose slope is at most
		$\lipschitzconstant$ (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.~\ref{fig_sobolev_dict}(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.
\par
		For 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(\featurevec)|/\lipschitzconstant$ changes the prediction,
		since $|f(\featurevec + \boldsymbol{\delta}) - f(\featurevec)| \leq \lipschitzconstant \normgeneric{\boldsymbol{\delta}}{2} < |f(\featurevec)|$
		leaves the sign of $f$ unchanged
		(Tsuzuku et al., 2018, Prop.~2). The decision tree of
		Fig.~\ref{fig_sobolev_dict}(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.
\par
		Sobolev 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} \normgeneric{\nabla f(\featurevec)}{2}^{2} \, \mathrm{d}\featurevec$
		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.~\ref{fig_sobolev_dict}(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$ (\texttt{pythondemos/sobolevspace.py}).
\par
		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 $\samplesize$ 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
		$\samplesize$ 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.
\par
		The 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\'ern
		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.
\par
		Finally, a bound $\lipschitzconstant$ 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.

\subsection{Cross References}
Lipschitz, robustness, stability, deep net, decision tree, linear regression, regularization, XAI, LIME, smoothness assumption, GTV, GTVMin, RKHS, Hilbert space, differentiable

\subsection{References}
\begin{enumerate}
  \item Adams and Fournier (2003). Sobolev Spaces. 2nd ed., Academic Press, Amsterdam, The Netherlands.
  \item SarcheshmehPour et al. (2023). Clustered Federated Learning via Generalized Total Variation Minimization. IEEE Trans. Signal Process., 71, pp.~4240--4256.
  \item European Parliament and Council of the European Union (2024). Regulation (EU) 2024/1689 of the European Parliament and of the Council of 13 June 2024 laying down harmonised rules on artificial intelligence and amending Regulations (EC) No 300/2008, (EU) No 167/2013, (EU) No 168/2013, (EU) 2018/858, (EU) 2018/1139 and (EU) 2019/2144 and Directives 2014/90/EU, (EU) 2016/797 and (EU) 2020/1828 (Artificial Intelligence Act) (Text with EEA relevance). Official Journal of the European Union, L series, Jul. 12. URL: https://eur-lex.europa.eu/eli/reg/2024/1689/oj/eng.
  \item Wainwright (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, Cambridge, UK.
  \item Evans (2010). Partial Differential Equations. 2nd ed., American Mathematical Society, Providence, RI, USA.
  \item Kanagawa et al. (2018). Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences. URL: https://arxiv.org/abs/1807.02582.
  \item Chambolle and Pock (2016). An introduction to continuous optimization for imaging. Acta Numer., 25, pp.~161--319.
  \item Rudin et al. (1992). Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 60(1--4), pp.~259--268.
  \item Tsuzuku et al. (2018). Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks. In: Adv. Neural Inf. Process. Syst. (NeurIPS), pp.~6541--6550.
\end{enumerate}

\end{document}
