\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{\emprisk}[2]{\widehat{L}\big(#1|#2\big)} \newcommand{\feature}{x} \newcommand{\hypospace}{\mathcal{H}} \newcommand{\hypothesis}{h} \newcommand{\learnthypothesis}{\widehat{\hypothesis}} \newcommand{\lossfunc}[2]{L\left(#1,#2 \right)} \newcommand{\offset}{b} \newcommand{\polydegree}{p} \newcommand{\reals}{\mathbb{R}} \newcommand{\risk}[1]{\bar{L} \big( #1 \big) } \newcommand{\sampleidx}{r} \newcommand{\samplesize}{m} \newcommand{\trainerror}{E_{t}} \newcommand{\trainset}{\dataset^{(\rm train)}} \newcommand{\truelabel}{y} \newcommand{\vz}[0]{{\bf z}} \newcommand{\weight}{w} \begin{document} \section{training 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 training error of a hypothesis is its average loss over the training set, the empirical risk of the hypothesis on the data points used for training. For a hypothesis delivered by empirical risk minimization (ERM), it is the smallest empirical risk that any hypothesis of the hypothesis space attains. Because the same data points selected the hypothesis, the training error is often far below the risk, by a gap that grows with the size of the hypothesis space, so a hypothesis with zero training error can have a large risk. Under the independent and identically distributed assumption (i.i.d.\ assumption), the training error of every hypothesis is a noisy estimate of its risk, and ERM compares all of them at once, so a generalization guarantee for the ERM solution requires the deviation to be small uniformly over the hypothesis space. A training error far below the validation error indicates overfitting, and a large training error indicates underfitting. \subsection{Definition} Twenty of the $1827$ days of five years, 2020 to 2024, at the weather station Krems an der Donau (Austria), every $92$nd day, are drawn in Fig.~\ref{fig_trainerr_open} as a scatterplot. Each day is a data point: its feature $\feature$ is the morning minimum temperature, its label $\truelabel$ the maximum temperature of the day. Three of the days, drawn in black, form a training set, the days used for training, for two empirical risk minimization (ERM)-based methods that deliver the hypotheses $\learnthypothesis^{(1)}$ and $\learnthypothesis^{(2)}$. The hypothesis $\learnthypothesis^{(1)}$ is learned by ERM with the squared error loss over the hypothesis space of affine maps $\hypothesis(\feature) = \offset + \weight \feature$, the linear model. The dotted bars are its prediction errors on the three days, the differences between the recorded maximum and the value of $\learnthypothesis^{(1)}$, and the average of the three squared bars is its training error, $7.91$. \par The second hypothesis $\learnthypothesis^{(2)}$ is learned by ERM over the hypothesis space of all polynomials of degree at most two. Although the training error of $\learnthypothesis^{(2)}$ is zero, and therefore far below that of $\learnthypothesis^{(1)}$, it is the worse choice: averaged over all days of the five years, the loss of $\learnthypothesis^{(2)}$ is $42.90$ against $24.22$ for $\learnthypothesis^{(1)}$. \begin{figure}[H] \begin{center} \begin{tikzpicture} \begin{axis}[ width=0.92\linewidth, height=0.6\linewidth, axis lines=left, xlabel={morning minimum temperature in $^{\circ}$C (feature $\feature$)}, ylabel={maximum temperature in $^{\circ}$C (label $\truelabel$)}, xmin=-15, xmax=24, ymin=-5, ymax=54, 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] {trainerr_open_days_plot.csv}; \addlegendentry{data points $(\feature, \truelabel)$ of $20$ days} \addplot[black, thick] table[col sep=comma, x=tmin, y=tmax] {trainerr_open_line.csv}; \addlegendentry{linear hypothesis $\learnthypothesis^{(1)}$ learned by ERM} \addplot[black, thick, dashed] table[col sep=comma, x=tmin, y=tmax] {trainerr_open_poly.csv}; \addlegendentry{polynomial $\learnthypothesis^{(2)}$ learned by ERM} \addplot[draw=none, mark=none, forget plot, error bars/.cd, y dir=both, y explicit, error bar style={black, dotted, thick}] table[col sep=comma, x=tmin, y=line, y error plus=errplus, y error minus=errminus]{trainerr_open_err.csv}; \addplot[only marks, mark=*, mark size=2.4pt, black] table[col sep=comma, x=tmin, y=tmax] {trainerr_open_train.csv}; \addlegendentry{training set $\trainset$ (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 and the maximum temperature of the day as its label. The three black dots form the training set. The solid line is the hypothesis $\learnthypothesis^{(1)}$ that ERM learns from the three days over the linear model, and the dotted bars are its prediction errors on them; the average of the three squared bars is its training error. The dashed curve is the degree-two polynomial $\learnthypothesis^{(2)}$ that ERM learns over the polynomials of degree at most two, whose training error is zero; left of the coldest training day it falls below the frame. Data generated by \texttt{pythondemos/trainerr.py} \label{fig_trainerr_open}} \end{figure} Holding the intercept of $\learnthypothesis^{(1)}$ at the value ERM gave it and varying only its slope $\weight$ leaves the training error a function of one number. Fig.~\ref{fig_trainerr_curves} shows it with the risk, the expected loss over the probability distribution of a day, approximated by the average over the five years. The two functions have different minimizers: the training error is smallest at the slope that ERM picked, the risk at a smaller slope. At the slope ERM picked, the training error is a third of the risk. The training error is an average over the three days that determined the hypothesis; it does not measure the loss on a day outside the training set. \begin{figure}[H] \begin{center} \begin{tikzpicture} \begin{axis}[ width=10cm, height=6cm, axis lines=left, xlabel={slope $\weight$ of the hypothesis $\hypothesis^{(\weight)}$}, ylabel={average squared error loss}, xmin=0.6, xmax=1.5, ymin=0, ymax=78, label style={font=\scriptsize}, tick label style={font=\scriptsize}, legend style={draw=none, fill=none, font=\scriptsize, at={(0.03,0.97)}, anchor=north west}, legend cell align=left, ] \addplot[black, thick] table[col sep=comma, x=slope, y=train] {trainerr_curves.csv}; \addlegendentry{training error on the three days} \addplot[black!60, thick, dashed] table[col sep=comma, x=slope, y=risk] {trainerr_curves.csv}; \addlegendentry{average loss over the five years} \addplot[only marks, mark=*, mark size=2pt, black, restrict expr to domain={\coordindex}{0:0}] table[col sep=comma, x=slope, y=train] {trainerr_curves_min.csv}; \addlegendentry{slope used by the learned hypothesis} \addplot[only marks, mark=square, mark size=2.2pt, black, restrict expr to domain={\coordindex}{1:1}] table[col sep=comma, x=slope, y=risk] {trainerr_curves_min.csv}; \addlegendentry{slope with the smallest risk} \end{axis} \end{tikzpicture} \end{center} \caption{The training error (solid curve) and the risk (dashed curve) of the hypothesis $\hypothesis^{(\weight)}(\feature) = 10.21 + \weight \feature$ as functions of its slope $\weight$, for the three training days and the five years of Fig.~\ref{fig_trainerr_open}; the intercept is the one ERM gave $\learnthypothesis^{(1)}$. The training error is smallest at the slope that ERM picks (filled circle), where it is far below the risk; the risk is smallest at a smaller slope (open square). Data generated by \texttt{pythondemos/trainerr.py} \label{fig_trainerr_curves}} \end{figure} The training error $\trainerror$ of a hypothesis $\learnthypothesis$ is its average loss over the training set $\trainset = \{\datapoint^{(\sampleidx)}\}_{\sampleidx=1}^{\samplesize}$, \[ \trainerror = \frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \lossfunc{\datapoint^{(\sampleidx)}}{\learnthypothesis} \text{,} \] i.e., the empirical risk of $\learnthypothesis$ on the data points used for learning $\learnthypothesis$. The hypothesis is the output of a training method, a map $\algomap$ that reads in a training set and delivers $\learnthypothesis = \algomap(\trainset)$. For a hypothesis delivered by ERM, the training error is the smallest empirical risk that any hypothesis of the hypothesis space attains on $\trainset$, since ERM minimizes this average. \par The training error is computed on the same data points that selected $\learnthypothesis$, which limits its use as a measure of quality. The goal of a machine learning (ML) method is to learn a hypothesis that incurs a small loss on any data point, also those outside the training set, that is, to minimize the risk introduced above. The training error of the learned hypothesis is often a poor estimator for its risk, because the learned hypothesis has been adapted to the training set by minimizing the training error. A hypothesis with zero training error can therefore have a large risk, as $\learnthypothesis^{(2)}$ of Fig.~\ref{fig_trainerr_open} does. The difference between the risk and the training error is the generalization gap. \par Under the independent and identically distributed assumption (i.i.d.\ assumption), the training error becomes a random variable (RV), as it depends on the randomly generated training set. For one fixed hypothesis $\hypothesis \in \hypospace$, the empirical risk $\emprisk{\hypothesis}{\trainset}$ is an average of the $\samplesize$ loss values $\lossfunc{\datapoint^{(1)}}{\hypothesis}, \ldots, \lossfunc{\datapoint^{(\samplesize)}}{\hypothesis}$, which are realizations of independent and identically distributed (i.i.d.) RVs. It is therefore the realization of an RV with expectation $\risk{\hypothesis}$ and a variance proportional to $1/\samplesize$. ERM does not evaluate this estimate at one fixed hypothesis: it compares the estimates of all hypotheses in $\hypospace$ and picks the smallest. The estimates form the family $\{ \emprisk{\hypothesis}{\trainset} \}_{\hypothesis \in \hypospace}$, a stochastic process indexed by the hypothesis space: one RV for each hypothesis, all realized by the single draw of $\trainset$. The minimizer $\learnthypothesis$ of this process is itself an RV, and its training error $\trainerror = \emprisk{\learnthypothesis}{\trainset}$ is the minimum of many noisy estimates, so it is below $\risk{\learnthypothesis}$ on average. \par A guarantee of generalization for the ERM solution must therefore hold uniformly over the hypothesis space: if \begin{equation} \label{eq_trainerr_uniform} \sup_{\hypothesis \in \hypospace} \big| \emprisk{\hypothesis}{\trainset} - \risk{\hypothesis} \big| \leq \epsilon \text{,} \end{equation} then $\risk{\learnthypothesis} \leq \trainerror + \epsilon$, and the risk of $\learnthypothesis$ exceeds the smallest risk in $\hypospace$ by at most $2\epsilon$ (Shalev-Shwartz and Ben-David, 2014, Lemma~4.2). A hypothesis space for which the uniform deviation \eqref{eq_trainerr_uniform} falls below any $\epsilon$ with probability at least $1-\delta$ once $\samplesize$ is large enough has the uniform convergence property (Shalev-Shwartz and Ben-David, 2014, Def.~4.3). For a finite hypothesis space and a loss with values in $[0,1]$, a union bound over the hypotheses and Hoeffding's inequality give $\epsilon = \sqrt{\ln(2 |\hypospace| / \delta) / (2 \samplesize)}$ (Shalev-Shwartz and Ben-David, 2014, Cor.~4.6). For an infinite hypothesis space, $\ln |\hypospace|$ is replaced by a measure of its size such as the Vapnik–Chervonenkis dimension (VC dimension) or the Rademacher complexity (Shalev-Shwartz and Ben-David, 2014, Thm.~6.8, Thm.~26.5). \par In contrast, the validation error, computed as the average loss on data points not used in the training, is often a much better estimator for the risk of the learned hypothesis. For example, let the data points of the validation set be realizations of i.i.d. RVs, independent of the training set. Each summand of the validation error is then the loss on an independent draw from the probability distribution of a data point, whose expectation conditional on the training set is the risk of the learned hypothesis (Hastie et al., 2009, Eq.~(7.2)). The expectation of the validation error conditional on the training set is therefore that risk. Moreover, the validation error estimates the risk of the single hypothesis that $\algomap$ delivered, so one Hoeffding bound without $|\hypospace|$ suffices for it, and it concentrates around the risk at a rate that depends only on the size of the validation set, not on how the hypothesis was learned (Shalev-Shwartz and Ben-David, 2014, Thm.~11.1). \par Fig.~\ref{fig_trainerr_uniform} shows three deviations of a training error from a risk for one year of the Krems record: for one fixed hypothesis, for the hypothesis that ERM learns, and the largest deviation over the hypothesis space. The $366$ days of the year stand in for the probability distribution of a day, so the risk of a hypothesis is its average loss over the year, and a training set of $\samplesize$ days is drawn at random from the year, $300$ times for each $\samplesize \in \{10, 20, 40, 80\}$. The hypothesis space is the linear model, which consists of all hypothesis maps $\hypothesis(\feature) = \weight_{1} \feature + \weight_{0}$ with $\weight_{1}, \weight_{0} \in \reals$. \par The fixed hypothesis is the one with the smallest risk in the hypothesis space, the hypothesis learned by linear regression from all $366$ days; it does not depend on the draw. The ERM hypothesis is learned by linear regression from the drawn training set. The largest deviation over the hypothesis space, the uniform deviation \eqref{eq_trainerr_uniform}, is approximated by the maximum over a grid of $2500$ hypotheses around the learned one. Over the repeated draws, the deviation of the fixed hypothesis has mean zero. The training error of the ERM hypothesis is below its risk on average, and the largest deviation is several times the standard deviation of the fixed hypothesis' deviation. The gap of the ERM hypothesis never exceeds the largest deviation, as the uniform deviation \eqref{eq_trainerr_uniform} requires, and both decrease as the training set grows (\texttt{pythondemos/trainerr.py}). \begin{figure}[H] \begin{center} \begin{tikzpicture} \begin{axis}[ width=10cm, height=6cm, axis lines=left, xmode=log, enlarge x limits=0.08, enlarge y limits=0.08, xtick={10,20,40,80}, xticklabels={10,20,40,80}, ymax=60, xlabel={size $\samplesize$ of the training set}, ylabel={training error minus risk}, label style={font=\scriptsize}, tick label style={font=\scriptsize}, legend style={draw=none, fill=none, font=\scriptsize, at={(0.03,0.97)}, anchor=north west}, legend cell align=left, ] \addplot[black, only marks, mark=*, mark size=1.6pt, error bars/.cd, y dir=both, y explicit] table[col sep=comma, x expr=\thisrow{size}*0.92, y=fixed_mean, y error=fixed_spread] {trainerr_uniform.csv}; \addlegendentry{one fixed hypothesis} \addplot[black!60, only marks, mark=square*, mark size=1.6pt, error bars/.cd, y dir=both, y explicit] table[col sep=comma, x=size, y=erm_mean, y error=erm_spread] {trainerr_uniform.csv}; \addlegendentry{the hypothesis learned by ERM} \addplot[black, only marks, mark=triangle, mark size=2.2pt, error bars/.cd, y dir=both, y explicit] table[col sep=comma, x expr=\thisrow{size}*1.08, y=sup_mean, y error=sup_spread] {trainerr_uniform.csv}; \addlegendentry{largest deviation over the hypothesis space} \addplot[black!60, dotted, thick] coordinates {(9,0) (90,0)}; \end{axis} \end{tikzpicture} \end{center} \caption{Deviation of the training error from the risk over repeated random draws of a training set of fixed size from the days of 2024 at Krems an der Donau, mean and one standard deviation either side. For one fixed hypothesis (filled circles) the deviation has mean zero. For the hypothesis that ERM learns from the draw (filled squares) it is negative on average. The largest deviation over the hypothesis space (open triangles), the uniform deviation \eqref{eq_trainerr_uniform} approximated on a grid of $2500$ hypotheses, bounds the ERM gap in every draw and decreases with the size of the training set. Data generated by \texttt{pythondemos/trainerr.py} \label{fig_trainerr_uniform}} \end{figure} The size of the gap $\risk{\learnthypothesis} - \trainerror$ depends on the hypothesis space. The first day of each month from January to August 2024 forms a training set of eight days, and the rest of the year is held back. A hypothesis of the linear model learned from the eight days has a training error of $20.36$, only slightly below its average squared error of $21.60$ on the held-back days: the linear model has two model parameters and can adapt little to the particular eight days. Fig.~\ref{fig_trainerr_dict} shows the two errors for polynomials of prescribed maximum degree $\polydegree = 0, \ldots, 7$. Increasing the degree means a larger hypothesis space, a polynomial of degree $\polydegree$ being one of degree $\polydegree+1$ with a zero leading coefficient, so the training error never increases with the degree. In contrast, the average loss on the held-back days is smallest at degree one and grows for larger degrees, where the polynomial oscillates between the eight days it was learned from. \begin{figure}[H] \begin{center} \begin{tikzpicture} \begin{semilogyaxis}[ width=10cm, height=6cm, axis lines=left, xlabel={degree of the polynomial}, ylabel={average loss}, xtick={0,1,2,3,4,5,6,7}, label style={font=\scriptsize}, tick label style={font=\scriptsize}, legend style={draw=none, fill=none, font=\scriptsize, at={(0.03,0.97)}, anchor=north west}, ] \addplot[black, thick, mark=*, mark size=1.6pt] table[col sep=comma, x=degree, y=train] {trainerr_degree.csv}; \addlegendentry{training error on the eight training days} \addplot[black, dashed, thick, mark=square*, mark size=1.6pt] table[col sep=comma, x=degree, y=heldout] {trainerr_degree.csv}; \addlegendentry{average loss on the held-back days} \end{semilogyaxis} \end{tikzpicture} \end{center} \caption{Training error (solid line, filled circles) and held-back error (dashed line, filled squares) of a polynomial $\learnthypothesis(\feature)$ of prescribed maximum degree learned by ERM from eight days of 2024 at Krems an der Donau. The training error never increases with the degree, since increasing the degree means a larger hypothesis space. In contrast, the error on the days outside the training set is smallest at a low degree and grows for larger degrees. Data generated by \texttt{pythondemos/trainerr.py} \label{fig_trainerr_dict}} \end{figure} By comparing the training error of an ML method with the resulting validation error, two failures can be detected. A training error far below the validation error indicates overfitting (Bishop, 2006, Sect.~1.1). A large training error indicates underfitting: a hypothesis space too small, or an iterative optimizer that stopped too early, which restricts the effective hypothesis space. Fig.~\ref{fig_trainerr_dict} also shows the effect of regularization by model pruning: restricting the hypothesis space by using a small polynomial degree raises the training error a little and lowers the average loss on the held-back days. \subsection{Cross References} training set, validation set, empirical risk, ERM, loss, validation error, risk, generalization gap, overfitting, underfitting, hypothesis, i.i.d.\ assumption, generalization, stochastic process, concentration inequality, VC dimension \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}