\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{\cumreward}{G}
\newcommand{\datapoint}{\vz}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\hypospace}{\mathcal{H}}
\newcommand{\hypothesis}{h}
\newcommand{\iteridx}{t}
\newcommand{\learnthypothesis}{\widehat{\hypothesis}}
\newcommand{\lrate}{\eta}
\newcommand{\timeidx}{t}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vz}[0]{{\bf z}}
\newcommand{\weights}{\vw}

\begin{document}

\section{training}

\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}
model fitting, fitting

\subsection{Abstract}
Training is the process of choosing a useful
		hypothesis out of a hypothesis space, or model, by
		solving an optimization problem whose objective function a training method
		builds from the data points it reads. In
		supervised learning, the
		objective function is the average loss over data points
		whose label values are known, such as the average
		squared error loss. In unsupervised learning, it measures
		structure instead, such as the clustering error incurred by a
		choice of cluster centroids. In reinforcement learning (RL),
		it is the expected cumulative reward collected by a
		policy. Training methods differ also in how they access
		data points: offline methods require the training set up
		front, while online methods update the hypothesis whenever
		new data points arrive. Many training methods iterate an
		operator on the model parameters of a parametric model: a
		gradient step where the objective function is differentiable,
		and one sweep of alternating optimization in the
		$k$-means and expectation–maximization (EM) algorithms. An offline method
		applies the same operator at every step and stops at a
		fixed point of it, while an online method applies an
		operator that the arriving data point changes. These
		operators make the objective function small on the
		data points the method is given, and controlling the
		loss on data points outside the training set is a
		challenge that no choice of optimization method removes.

\subsection{Definition}
A shop forecasts daily bread demand
		from the weather with a linear model. It trains that
		linear model by gradient descent (GD) on a year of past records. To let the
		forecaster follow a changing clientele instead, it trains the same
		linear model by online GD on each new day's sales: the same
		model and the same objective function, with a different form of
		data access. The shop trains in both cases. Training is the
		process by which a machine learning (ML) method picks one hypothesis
		out of a hypothesis space. The hypothesis space $\hypospace$, or
		model, is the set of candidate maps the method may choose
		from. Training selects
		the single hypothesis $\learnthypothesis$ that the method
		then uses for inference: the training phase learns
		$\learnthypothesis$, and the inference phase applies
		$\learnthypothesis$, unchanged, to newly arriving
		data points to deliver predictions. What
		makes one candidate better than another is an objective function, so
		training amounts to solving an optimization problem.
\par
		Training methods differ in two respects. The first is the
		objective function. In supervised learning, each data point
		carries a label, and the objective function is the average
		loss of a hypothesis over the training set, its
		empirical risk, such as the average squared error loss in
		linear regression. In
		unsupervised learning, no label is given, so the
		objective function measures a structural quantity instead, such as the
		clustering error incurred by a choice of
		cluster centroids in hard clustering. In
		reinforcement learning (RL), there is no fixed training set at
		all: the objective function is the expected cumulative reward
		$\cumreward$ collected by a policy that interacts with an
		environment.
\par
		The second respect is the form of data access, offline or online.
		A training method is an
		algorithm $\algomap$ that reads in a dataset $\dataset$
		of data points, constructs the objective function from them
		together with the chosen
		model and loss, and delivers the hypothesis
		making that objective function small,
		$\learnthypothesis = \algomap(\dataset)$. An offline
		algorithm reads in all data points at once, computes,
		and delivers $\learnthypothesis$. An online algorithm reads
		in new data points as they arrive, updating the current
		hypothesis at each time instant
		$\timeidx = 1, 2, \ldots$ instead of waiting for a complete
		training set. The hypotheses it produces form a
		Markov chain, since each one depends on the dataset
		only through its predecessor and the data point that just
		arrived (Fig.~\ref{fig_training_access_dict}).
		\begin{figure}[H]
		\centering
		\begin{minipage}[b]{0.33\linewidth}
			\centering
			\begin{tikzpicture}[font=\small, >=Stealth,
				box/.style={draw, rounded corners, align=center,
					inner sep=4pt, minimum height=0.8cm}]
				\node[box] (D) at (0,0) {dataset $\dataset$};
				\node[box] (A) at (0,-1.45) {$\algomap$};
				\node (H) at (0,-2.9) {$\learnthypothesis$};
				\draw[->] (D) -- (A);
				\draw[->] (A) -- (H);
			\end{tikzpicture}
			\\ {\small (a) offline: the whole dataset at once}
		\end{minipage}\hfill
		\begin{minipage}[b]{0.62\linewidth}
			\centering
			\begin{tikzpicture}[font=\small, >=Stealth,
				st/.style={draw, circle, inner sep=1.5pt,
					minimum size=1.05cm}]
				\node[st] (h1) at (0,-1.45) {$\learnthypothesis^{(\timeidx)}$};
				\node[st] (h2) at (2.9,-1.45) {$\learnthypothesis^{(\timeidx+1)}$};
				\node (hd) at (5.3,-1.45) {$\cdots$};
				\draw[->] (h1) -- node[below, font=\scriptsize] {$\algomap$} (h2);
				\draw[->] (h2) -- (hd);
				\node (z1) at (1.45,-0.05) {$\datapoint^{(\timeidx)}$};
				\node (z2) at (4.1,-0.05) {$\datapoint^{(\timeidx+1)}$};
				\draw[->] (z1) -- (1.45,-1.1);
				\draw[->] (z2) -- (4.1,-1.1);
			\end{tikzpicture}
			\\ {\small (b) online: one data point per time instant}
		\end{minipage}
		\caption{Two forms of data access. In (a) an offline
			algorithm $\algomap$ reads in the entire dataset
			$\dataset$ and delivers a learned hypothesis
			$\learnthypothesis$. In (b) an online algorithm holds a
			current hypothesis $\learnthypothesis^{(\timeidx)}$,
			which the data point $\datapoint^{(\timeidx)}$ arriving
			at time instant $\timeidx$ moves to
			$\learnthypothesis^{(\timeidx+1)}$. The hypotheses in
			(b) therefore form a Markov chain: the next one depends
			on the dataset only through the current one and the
			arriving data point
			\label{fig_training_access_dict}}
		\end{figure}
		Inference and online training both act on a newly arriving
		data point, and that data point plays a different role
		in each. Inference applies a hypothesis that training
		has already delivered and leaves it as it is, so the arriving
		data point supplies only the features to predict
		from. Online training keeps changing the hypothesis, so the
		arriving data point supplies the loss that decides the
		next hypothesis. An online method does both in each round:
		it commits to a hypothesis and predicts with it, the
		loss of that hypothesis is then revealed, and the
		next hypothesis is chosen from the losses revealed so
		far (Hazan, 2022, Sect.~1.1).
\par
		For a parametric model, each hypothesis
		$\hypothesis^{(\weights)}$ is fixed by a choice of
		model parameters $\weights$, so training searches over
		$\weights$. Many training methods amount to iterating an operator
		on those model parameters,
		\[
			\weights^{(\iteridx+1)} = T(\weights^{(\iteridx)})
			\text{, for } \iteridx = 0,1,\ldots \text{,}
		\]
		and the two forms of data access appear here as two forms of the
		operator. An offline method builds its objective function once, from
		the whole dataset, so $T$ is fixed: the same map is applied
		at every step, and training stops at, or near, a fixed point
		of $T$, where a further iteration leaves the
		model parameters unchanged. An online method has no fixed
		objective function. Its operator reads in the arriving data point,
		\[
			\weights^{(\iteridx+1)} = T\big(\weights^{(\iteridx)},
			\datapoint^{(\timeidx)}\big) \text{,}
		\]
		so the map changes from step to step, and in general there is no
		single fixed point to stop at. The model parameters keep
		changing for as long as new data points arrive. The learned hypothesis
		$\learnthypothesis$ is the one that the final model parameters
		define.
\par
				What $T$ does is decided by the shape of the objective function. When
		the objective function is differentiable in all
		model parameters at once, $T$ is a gradient step,
		$T(\weights) = \weights - \lrate \nabla f(\weights)$ with
		step size $\lrate$ (Boyd and Vandenberghe, 2004, Sect.~9.3). The
		form of data access then decides which objective function the
		gradient is taken of, so a single operator yields
		three different training methods. Offline
		empirical risk minimization (ERM) takes the gradient of the average loss
		$f(\weights)$ over the whole training set. When that
		training set is too large to pass through at every step,
		stochastic gradient descent (SGD) replaces $\nabla f(\weights)$ by the gradient
		of the average loss over a few data points
		(Bottou, 2010). Its operator is drawn at random at each
		step, from a distribution that the training set fixes, so it is
		fixed in expectation rather than fixed outright. In
		online learning, there is no training set at all, and online
		GD takes one gradient step on the loss of the
		arriving data point alone (Zinkevich, 2003).
\par
		Some objective functions arising in training methods can be minimized
		easily once a subset of the model parameters is held fixed. Then
		$T$ is one sweep of alternating optimization, a minimization over
		each subset in turn (Beck, 2017, Ch.~14). The $k$-means
		algorithm alternates between assigning each data point
		to the nearest cluster and recomputing the cluster
		means (Lloyd, 1982). The expectation–maximization (EM) algorithm is the
		probabilistic instance: training a Gaussian mixture model (GMM), it alternates between
		the responsibilities of the mixture components for each
		data point and the parameters of those components
		(Dempster et al., 1977). What separates EM from a plain
		alternation is that each step minimizes a surrogate, a bound on the
		objective function rather than the objective function itself, which is why
		the likelihood function cannot decrease
		(Bishop, 2006, Sect.~9.4). Both are offline. The $k$-means
		algorithm reaches a fixed point of its operator after
		finitely many steps, since every step lowers the objective function and
		there are finitely many assignments (Bishop, 2006, Sect.~9.1); for
		EM, under a mild continuity condition, the likelihood function
		converges and every limit point of the iterates is a stationary point
		of it (Wu, 1983, Thm.~2). Neither is guaranteed to reach the
		smallest loss available in $\hypospace$: $k$-means can stop at
		a local minimum of its objective function (Bishop, 2006, Sect.~9.1),
		and a stationary point of the likelihood function need not maximize it.
\par
		A gradient step and a sweep of alternating optimization
		both make the objective function small on the data points the
		training method is given, and that is all either of them does.
		Controlling the discrepancy between the loss on the
		training set and the loss on data points outside it
		is one of the main challenges in ML, and no choice of
		optimization method removes it (Goodfellow et al., 2016).

\subsection{Cross References}
optimization problem, inference, supervised learning, unsupervised learning, RL, ERM, GD, SGD, online learning, EM, GMM, $k$-means, fixed point, model, model parameter, loss

\subsection{References}
\begin{enumerate}
  \item Beck (2017). First-Order Methods in Optimization. SIAM-Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
  \item Bishop (2006). Pattern Recognition and Machine Learning. 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 Lloyd (1982). Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2), pp.~129--137.
  \item Wu (1983). On the convergence properties of the EM algorithm. Ann. Statist., 11(1), pp.~95--103.
  \item Zinkevich (2003). Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In: Proc. 20th Int. Conf. Mach. Learn., pp.~928--936.
  \item Bottou (2010). Large-scale machine learning with stochastic gradient descent. In: Proceedings of COMPSTAT'2010, pp.~177--186. Springer.
  \item Dempster et al. (1977). Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statist. Soc.: Ser. B (Methodological), 39(1), pp.~1--22.
\end{enumerate}

\end{document}
