\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}}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\datapoint}{\vz}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\feature}{x}
\newcommand{\featurespace}{\mathcal{X}}
\newcommand{\featurevec}{\vx}
\newcommand{\fixedpointop}{\mathcal{F}}
\newcommand{\hypospace}{\mathcal{H}}
\newcommand{\hypothesis}{h}
\newcommand{\iteridx}{t}
\newcommand{\labelspace}{\mathcal{Y}}
\newcommand{\learnthypothesis}{\widehat{\hypothesis}}
\newcommand{\lossfun}{L}
\newcommand{\lossfunc}[2]{L\left(#1,#2 \right)}
\newcommand{\pair}[2]{\left( #1,#2 \right)}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\timeidx}{t}
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\truelabel}{y}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\vz}[0]{{\bf z}}
\newcommand{\weight}{w}
\newcommand{\weights}{\vw}

\begin{document}

\section{empirical risk minimization (ERM)}

\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{Synonyms}
empirical loss minimization

\subsection{Abstract}
Empirical risk minimization (ERM) selects a hypothesis
		by minimizing the average loss on a given training set
		$\trainset$, the empirical risk. Machine learning (ML) methods aim at a
		hypothesis that incurs a small loss on any
		data point, and ERM replaces this unknown quantity by its
		average over the training set. Different ML methods arise from different
		choices of the model $\hypospace$ and the loss function
		$\lossfun$, both of which depend on the feature space
		$\featurespace$ and the label space $\labelspace$ of a given method.

\subsection{Definition}
A weather
		forecaster predicting tomorrow's maximum daytime temperature
		is useful only if its predictions are accurate on the
		large majority of days, not only on the days it was trained on.
		This forecaster is a hypothesis: it maps a day's
		features to a prediction of tomorrow's
		temperature, and its loss quantifies how far that
		prediction lies from the measured value. More generally,
		machine learning (ML) methods aim to find a
		hypothesis that incurs a small
		loss for any data point. The phrase \emph{any
		data point} is made precise by a probabilistic model for the
		generation of data points, as follows.
\par
		If data points are assumed to be drawn from a probability distribution, 
		then the risk of a hypothesis is defined as the
		expectation of its loss under that probability distribution.
		The ideal choice is then the hypothesis with minimal
		risk. However, in most ML applications, the
		underlying probability distribution is not known. Instead, only a
		finite training set $\trainset$ of data points is available. 
		ERM replaces the unknown risk with its sample-average 
		surrogate, the empirical risk on $\trainset$, and picks the hypothesis
		that minimizes this surrogate
		(Hastie et al., 2009; Murphy, 2012;
		Shalev-Shwartz and Ben-David, 2014; Vapnik, 2000).
\par
		For a fixed choice of loss function and hypothesis space, 
		ERM is a map $\algomap$ that reads
		in a training set
		$\trainset = \{\datapoint^{(\sampleidx)}\}_{\sampleidx=1}^{\samplesize}$
		of data points
		$\datapoint^{(\sampleidx)} = \pair{\featurevec^{(\sampleidx)}}{\truelabel^{(\sampleidx)}}$.
		The map returns a learned hypothesis
		$\learnthypothesis = \algomap(\trainset) \in \hypospace$
		that minimizes the empirical risk on $\trainset$,
		\[
			\learnthypothesis \in \argmin_{\hypothesis \in \hypospace}
			\frac{1}{\samplesize}
			\sum_{\sampleidx=1}^{\samplesize}
			\lossfunc{\datapoint^{(\sampleidx)}}{\hypothesis} \text{.}
		\]
		The hypothesis $\learnthypothesis$ is chosen from the underlying 
		hypothesis space (or model) $\hypospace$. For an ERM-based method, 
		model training is to compute $\algomap$.
\par
		Different ML methods arise from different design
		choices for the two components of the map $\algomap$: the
		model $\hypospace$ and the loss function
		$\lossfun$. Both depend on the
		nature of the data points, i.e., on the
		feature space $\featurespace$ and the label space
		$\labelspace$. For example, image data points with a
		high-dimensional feature space and a finite
		label space are typically handled by an artificial neural network (ANN) together
		with the logistic loss (Goodfellow et al., 2016, Ch.~9).
		Conversely, data points with
		few real-valued features and a real-valued
		label often allow for a linear model together with the
		squared error loss (Hastie et al., 2009, Ch.~3).
\par
		Fig.~\ref{fig_erm_dict} illustrates ERM for a linear model
		on data points with a single feature $\feature$
		and label $\truelabel$. Each hypothesis is a
		linear map
		$\hypothesis(\feature) = \weight_{1} \feature + \weight_{0}$
		with model parameters $\weight_{0}, \weight_{1}$. ERM
		picks the model parameters that minimize the empirical risk
		on $\trainset$.
		\begin{figure}[H]
			\begin{center}
			\begin{tikzpicture}[scale=1]
  			\def\slope{0.4}
 	 		\def\intercept{2.0}
  			\def\xmin{0}
 		 	\def\xmax{6.5}
  			\draw[->] (0,0) -- (7,0) node[right] {$\feature$};
			\draw[->] (0,0) -- (0,6.4) node[above] {$\truelabel$};
  			\draw[color=black, thick, dashed, domain=\xmin:\xmax, variable=\x] plot ({\x},{\slope*\x + \intercept}); 
			% Place label at the endpoint (xmax, h(xmax))
   			\coordinate (hend) at (\xmax,{\slope*\xmax + \intercept});
			\node[above right] at (hend) {$\learnthypothesis(\feature)$};
   			\foreach \i/\xval/\yval in {1/1.2/1.8, 2/3.0/2.6, 3/5.0/5.7} {
			% predicted label on the hypothesis line
			\coordinate (l\i) at (\xval, {\slope*\xval + \intercept});
			% actual label
			\coordinate (n\i) at (\xval, \yval);
			% draw data point
			\node[circle,draw,fill=blue,minimum size=6pt,scale=0.6] (pt\i) at (n\i) {};
			% residual arrow
			\draw[<->, color=blue, thick] (l\i) -- (n\i);
  			}
  			% Labels for data points
  			\node[anchor=west,below,yshift=-2pt] at (n1) {$\big(\feature^{(1)},\,\truelabel^{(1)}\big)$};
  			\node[anchor=west,below]        at (n2) {$\big(\feature^{(2)},\,\truelabel^{(2)}\big)$};
  			\node[anchor=west,above]   at (n3) {$\big(\feature^{(3)},\,\truelabel^{(3)}\big)$};
			\end{tikzpicture}
		\caption{ERM learns a hypothesis $\learnthypothesis \in \hypospace$ out of a 
		        model $\hypospace$ by minimizing the empirical risk (or 
				average loss) $\tfrac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \lossfunc{\datapoint^{(\sampleidx)}}{\hypothesis}$ 
				over candidate hypotheses $\hypothesis \in \hypospace$ on a 
				training set $\trainset$. The arrows indicate the 
				prediction errors incurred by the learned hypothesis 
			$\learnthypothesis$ (dashed line) for each data point in the
			training set (filled circles); the axes carry the feature
			$\feature$ and the label $\truelabel$} \label{fig_erm_dict}
			\end{center}
		\end{figure}
		In practice, the map $\algomap$ is computed by an iterative
		optimization method. Many of these
		optimization methods can be represented as a fixed-point iteration 
		that starts with an initial hypothesis $\hypothesis^{(0)}$
		and then repeatedly applies an update operator $\fixedpointop$
		(Bauschke and Combettes, 2011, Sect.~5.2, Cor.~27.9),
		$$\hypothesis^{(\iteridx+1)} = \fixedpointop\big( \hypothesis^{(\iteridx)} \big) \text{, for } \iteridx=0,1,\ldots \text{.}$$
		The update operator $\fixedpointop$ depends on the training set, the loss function,
		and the hypothesis space. It is chosen such that its fixed points are
		the stationary points of the empirical risk. These are its
		minimizers when the empirical risk is a convex function
		of the hypothesis (Boyd and Vandenberghe, 2004, Sect.~4.2.3), and
		need not be otherwise, e.g., for an ANN.
\par
		For ERM using a parametric model $\hypospace$,
		the fixed-point iteration can be formulated directly in terms of 
		the model parameters $\weights$ instead of the hypothesis 
		$\hypothesis$. In particular, starting with initial 
		model parameters $\weights^{(0)}$, the update operator 
		$\fixedpointop$ is applied repeatedly to the model parameters,
		$$\weights^{(\iteridx+1)} = \fixedpointop\big( \weights^{(\iteridx)} \big) \text{, for } \iteridx=0,1,\ldots \text{.}$$
		One example of such a fixed-point iteration is gradient descent (GD), 
		which updates the model parameters in the direction of the 
		negative gradient of the empirical risk (which needs to be 
		differentiable).
\par
		Two requirements delimit where ERM applies: full feedback on the
		loss and access to the whole training set at once. First,
		ERM presupposes that the loss
		$\lossfunc{\datapoint^{(\sampleidx)}}{\hypothesis}$ can be
		evaluated for every hypothesis
		$\hypothesis \in \hypospace$ and every training
		data point $\datapoint^{(\sampleidx)}$. This
		full-feedback requirement is what distinguishes ERM from
		reinforcement learning (RL) algorithms, which use
		partial feedback. In particular, at each time instant 
		$\timeidx = 1, 2, \ldots$, an RL
		algorithm chooses an action, the prediction of
		its current hypothesis $\learnthypothesis^{(\timeidx)}$,
		and observes only the loss incurred by that
		action. It has no information about the 
		loss that would have been incurred by any other 
		hypothesis $\hypothesis \in \hypospace \setminus 
		\{\learnthypothesis^{(\timeidx)}\}$.
\par
		Second, ERM uses the whole training set at once. This
		requirement can be relaxed: ERM can also be implemented as an
		online algorithm, which is useful when the data points
		in $\trainset$ can only be accessed sequentially. Such
		sequential access arises, for instance, when memory limits
		prevent loading the entire training set at once. The
		canonical online form of ERM is the Follow-The-Leader (FTL)
		algorithm, which, at every round, solves a partial ERM
		problem on all data points seen so far. Assuming that
		the data point $\datapoint^{(\timeidx)}$ arrives at
		time instant $\timeidx=1,2,\ldots$,
	    FTL updates the learned hypothesis 
		$\learnthypothesis^{(\timeidx)}$ by 
		$$ \learnthypothesis^{(\timeidx)} \in \argmin_{\hypothesis \in \hypospace}
		\frac{1}{\timeidx} \sum_{\sampleidx=1}^{\timeidx}
		\lossfunc{\datapoint^{(\sampleidx)}}{\hypothesis} \text{.}$$
		Implementing this partial ERM separately for each time 
		instant can become computationally expensive (and wasteful),
		as it does not exploit the similarity between consecutive 
		partial ERM problems. This similarity can be exploited by 
		online gradient descent (online GD), which performs a single GD step on the 
		new data point $\datapoint^{(\timeidx)}$ at every time 
		instant $\timeidx$ (Hazan, 2022, Sect.~3.1).

\subsection{Cross References}
empirical risk, risk, loss, training set, hypothesis space, hypothesis, GD, FTL, RL

\subsection{References}
\begin{enumerate}
  \item Bauschke and Combettes (2011). Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer Science+Business Media, New York, NY, USA.
  \item Boyd and Vandenberghe (2004). Convex Optimization. Cambridge Univ. Press, Cambridge, U.K.
  \item Goodfellow et al. (2016). Deep Learning. MIT Press, Cambridge, MA, USA.
  \item Hazan (2022). Introduction to Online Convex Optimization. 2nd ed., MIT Press, Cambridge, MA, USA.
  \item Murphy (2012). Machine Learning: A Probabilistic Perspective. MIT Press, Cambridge, MA, USA.
  \item Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, New York, NY, USA.
  \item Vapnik (2000). The Nature of Statistical Learning Theory. 2nd ed., Springer, 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}