\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{\algomap}{\mathcal{A}}
\newcommand{\datapoint}{\vz}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\expect}{\mathbb{E} }
\newcommand{\feature}{x}
\newcommand{\hypospace}{\mathcal{H}}
\newcommand{\hypothesis}{h}
\newcommand{\learnthypothesis}{\widehat{\hypothesis}}
\newcommand{\lossfunc}[2]{L\left(#1,#2 \right)}
\newcommand{\risk}[1]{\bar{L} \big( #1 \big) }
\newcommand{\testset}{\dataset^{(\rm test)} }
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\truelabel}{y}
\newcommand{\valerror}{E_{v}}
\newcommand{\valset}{\dataset^{(\rm val)}}
\newcommand{\vz}[0]{{\bf z}}

\begin{document}

\section{validation error}

\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}
The validation error $\valerror$ of a learned
		hypothesis is its average loss over a validation set.
		For a fixed hypothesis and data points that are
		realizations of independent and identically distributed (i.i.d.) random variables (RVs), the validation error
		is an unbiased estimator of the risk. If the training set
		is itself modelled as random, the learned hypothesis becomes
		an RV too, and the validation error is unbiased conditioned
		on the learned hypothesis. The validation error
		characterizes a learned hypothesis that some machine learning (ML) method
		obtained from a training set. It can therefore be used to choose
		between different models or, more generally, between
		different ML methods. The validation error also helps to
		diagnose an ML method and to guide its revision.

\subsection{Definition}
The weather station Krems an der Donau
	(Austria) recorded the morning minimum and the maximum temperature of
	every day from 2020 to 2024. Each day is a data point: its
	feature $\feature$ is the morning minimum temperature, its
	label $\truelabel$ the maximum temperature of the day.
	Fig.~\ref{fig_valerr_open} shows twenty of them as a
	scatterplot and singles out six. Three of the days,
	drawn in black, form
		the training set. The hypothesis
		$\learnthypothesis^{(2)}$ learned from them is a degree-two
		polynomial through all three days, so its training error is zero.
		Three further days, drawn as red triangles, form a validation set.
		The dotted bars are the prediction errors of the polynomial
		on them, the differences between the recorded maximum and the
		value of the curve. The average of the three squared bars is the
		validation error of the polynomial, $42.58$.
		\begin{figure}[H]
		\begin{center}
		\begin{tikzpicture}
		\begin{axis}[
			width=0.92\linewidth, height=0.6\linewidth,
			axis lines=left,
			xlabel={$\feature$},
			ylabel={$\truelabel$},
			xmin=-15, xmax=24, ymin=-5, ymax=60,
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.02,0.98)}, anchor=north west},
			legend cell align=left,
			tick label style={font=\small}, label style={font=\small}]
			\addplot[only marks, mark=*, mark size=1.4pt, color=black!40]
				table[col sep=comma, x=tmin, y=tmax]
				{valerr_open_days_plot.csv};
			\addlegendentry{data points $(\feature, \truelabel)$ of $20$ days}
			\addplot[black, thick, dashed]
				table[col sep=comma, x=tmin, y=tmax]
				{valerr_open_poly.csv};
			\addlegendentry{polynomial $\learnthypothesis^{(2)}$ learned from the three days}
			\addplot[draw=none, mark=none, forget plot, error bars/.cd,
				y dir=both, y explicit,
				error bar style={red, dotted, line width=1.3pt}]
				table[col sep=comma, x=tmin, y=poly, y error plus=errplus,
				y error minus=errminus]{valerr_open_err.csv};
			\addplot[only marks, mark=*, mark size=2.4pt, black]
				table[col sep=comma, x=tmin, y=tmax]
				{valerr_open_train.csv};
			\addlegendentry{training set $\trainset$ (three days)}
			\addplot[only marks, mark=triangle, mark size=3pt, red, thick]
				table[col sep=comma, x=tmin, y=tmax]
				{valerr_open_val.csv};
			\addlegendentry{validation set $\valset$ (three days)}
		\end{axis}
		\end{tikzpicture}
		\end{center}
		\caption{Twenty of the $1827$ days at Krems an der Donau, 2020 to
			2024 (every $92$nd day), each a gray dot with the morning minimum
			temperature as its feature $\feature$ and the maximum
			temperature of the day as its label $\truelabel$. The three black dots form the
			training set, and the dashed curve is the degree-two
			polynomial $\learnthypothesis^{(2)}$ learned from them; it
			passes through all three, so its training error is zero. The
			three red triangles indicate days that form the validation set,
			and the dotted bars are the prediction errors of the
			polynomial on them. The average of the three squared bars is
			the validation error. Data generated by
			\texttt{pythondemos/valerr.py}
			\label{fig_valerr_open}}
		\end{figure}
		The validation error is the average loss of
		$\learnthypothesis^{(2)}$ on days that did not belong to the
		training set. The training error carries no information about
		such days: the polynomial passes through the three training
		days by construction. The validation error is close to the average
		squared error loss of $\learnthypothesis^{(2)}$ over
		all days of the five years, $42.90$. A hypothesis with a larger
		training error can be the better one: the linear hypothesis that
		empirical risk minimization (ERM) delivers from the same three days over the
		linear model has a training error of $7.91$ and a validation
		error of $6.98$.
\par
		The validation error $\valerror$ of a hypothesis
		$\learnthypothesis$ is its average loss over a validation set
		$\valset$,
		\[
			\valerror = \frac{1}{|\valset|} \sum_{\datapoint \in \valset}
			\lossfunc{\datapoint}{\learnthypothesis} \text{.}
		\]
		Because no data point of
		$\valset$ entered the training, $\valerror$ estimates the
		risk of $\learnthypothesis$. The training error, computed over
		the training set whose average loss ERM minimized, is
		below it on average: the same data points both selected
		$\learnthypothesis$ and assessed it
		(Hastie et al., 2009, Sect.~7.4).
\par
		The validation error is an average of $|\valset|$ losses. For
		data points that are realizations of independent and identically distributed (i.i.d.)
		random variables (RVs), $\valerror$ is the realization of an
		RV whose expectation is the risk of
		$\learnthypothesis$, since each summand has that expectation.
		The validation error is therefore an unbiased estimator of that
		risk. Its
		variance is the variance of a single loss divided by
		$|\valset|$, so its standard deviation decreases as $|\valset|$ grows.
\par
		In practice
		$\learnthypothesis = \algomap(\trainset)$ is the output of a
		training method, a map $\algomap$ that reads in the
		training set $\trainset$, so it is itself the realization
		of an RV: a different realization of $\trainset$ would
		have delivered a different hypothesis. The validation error is
		then unbiased conditioned on the learned hypothesis. If the
		data points of $\valset$ are independent of those of
		$\trainset$, and hence of $\learnthypothesis$
		(Shalev-Shwartz and Ben-David, 2014, Sect.~11.2.1), the conditional expectation of
		$\valerror$ given $\learnthypothesis$ is the risk of that
		hypothesis,
		\[
		\expect \big\{ \valerror \mid \learnthypothesis \big\}
		= \risk{\learnthypothesis} \text{.}
		\]
		The training error has no
		such property: conditioned on $\learnthypothesis$, the
		data points of $\trainset$ are no longer i.i.d.
		realizations of the probability distribution of a data point,
		because $\learnthypothesis$ was chosen to make its average
		loss on them small.
\par
		A guarantee for the validation error concerns one
		hypothesis only: for a loss with values in $[0,1]$,
		Hoeffding's inequality gives
		$|\valerror - \risk{\learnthypothesis}| \leq
		\sqrt{\ln(2/\delta) / (2 |\valset|)}$ with probability at
		least $1-\delta$, with no term for the hypothesis space
		$\hypospace$ (Shalev-Shwartz and Ben-David, 2014, Thm.~11.1). A guarantee for the
		training error of the ERM solution must hold uniformly over
		$\hypospace$, since ERM compares all its hypotheses
		(Shalev-Shwartz and Ben-David, 2014, Sects.~4.1 and~11.2.1).
\par
		A numerical experiment shows how much the validation error varies
		when the validation set is chosen at random. Consider the
		hypothesis
		\[
			\learnthypothesis(\feature) = 10.47 + 1.05 \, \feature \text{,}
		\]
		obtained by linear regression from forty data points of the
		same station record, every ninth day of 2024. The
		data points of $306$ further days of that year, none of them
		used for training, are collected in a dataset, the
		test set $\testset$. Here $\testset$ serves only as the pool from which
		each validation set is drawn at random; its own role, assessing a
		selected hypothesis, is taken up at the end.
\par
		Fig.~\ref{fig_valerr_dict} shows the value range of the validation
		error of $\learnthypothesis$ over repeated draws of a validation set
		of prescribed size from $\testset$. The standard deviation of the
		validation error decreases with increasing size of the
		validation set. The decrease follows the $1/\sqrt{|\valset|}$ form
		of the bound from Hoeffding's inequality above, though the
		bound itself does not apply, since the squared error loss is not
		confined to $[0,1]$.
		\begin{figure}[H]
		\begin{center}
		\begin{tikzpicture}
		\begin{axis}[
			width=10cm, height=6cm,
			axis lines=left,
			xmode=log,
			enlarge x limits=0.06,
			enlarge y limits=0.08,
			xtick={5,10,20,40,80},
			xticklabels={5,10,20,40,80},
			xlabel={size $|\valset|$ of the validation set},
			ylabel={validation error $\valerror$},
			label style={font=\scriptsize},
			tick label style={font=\scriptsize},
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.97,0.97)}, anchor=north east},
		]
			\addplot[black, only marks, mark=*, mark size=1.6pt,
				error bars/.cd, y dir=both, y explicit]
				table[col sep=comma, x=size, y=mean, y error=spread]
				{valerr_spread.csv};
			\addlegendentry{mean $\pm$ one standard deviation}
			\addplot[black, dashed, thick]
				table[col sep=comma, x=size, y=risk]
				{valerr_risk.csv};
			\addlegendentry{average loss on $\testset$}
		\end{axis}
		\end{tikzpicture}
		\end{center}
		\caption{Spread of the validation error computed for the
			hypothesis
			$\learnthypothesis(\feature) = 10.47 + 1.05 \, \feature$. The
			validation errors are computed for different validation sets
			that are, for a given size, randomly selected from $\testset$.
			The dataset $\testset$ consists of data points that
			have not been used to learn $\learnthypothesis$. Each bar spans
			one standard deviation either side of the mean. The dashed curve is the
			average loss computed over all of $\testset$. The
			standard deviation decreases as $|\valset|$ grows. Data generated by
			\texttt{pythondemos/valerr.py} \label{fig_valerr_dict}}
		\end{figure}
		Beyond estimating the risk of one hypothesis, the
		validation error is compared with the training error and across
		models. A training error far below the validation error
		indicates overfitting
		(Hastie et al., 2009, Sect.~7.2).
		Comparing the validation errors of several candidate models
		is model selection (Bishop, 2006, Sect.~1.3). A model
		has no validation error of its own. The phrase is short for the
		validation error of the hypothesis that $\algomap$ delivers
		from that model, since $\valerror$ is the average loss
		of a single hypothesis. The selected model is the one
		whose hypothesis attains the smallest of the compared
		validation errors, so that validation error is biased downward as an
		estimate of the risk, and a test set is kept apart for
		the final assessment (Bishop, 2006, Sect.~1.3;
		Hastie et al., 2009, Sect.~7.2).

\subsection{Cross References}
validation set, validation, training set, test set, training error, loss, risk, hypothesis, ERM, overfitting, model selection, generalization gap, conditional expectation, i.i.d.\ assumption, unbiased estimator

\subsection{References}
\begin{enumerate}
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, New York, NY, USA.
  \item Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed., Springer Science+Business Media, New York, NY, USA.
\end{enumerate}

\end{document}