\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{\dataset}{\mathcal{D}}
\newcommand{\effdim}[1]{d_{\rm eff} \left( #1 \right)}
\newcommand{\featuredim}{d}
\newcommand{\featuremtx}{\mX}
\newcommand{\featurevec}{\vx}
\newcommand{\hypospace}{\mathcal{H}}
\newcommand{\hypothesis}{h}
\newcommand{\labelvec}{\vy}
\newcommand{\mX}[0]{{\bf X}}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\pinv}[1]{{#1}^{+}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\regparam}{\alpha}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\truelabel}{y}
\newcommand{\valset}{\dataset^{(\rm val)}}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\vy}[0]{{\bf y}}
\newcommand{\weights}{\vw}

\begin{document}

\section{high-dimensional regime}

\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 machine learning (ML) method operates in the high-dimensional regime when the
		effective dimension of its hypothesis space exceeds the sample size
		$\samplesize$ of the training set. For a linear model, the regime
		begins where the number $\featuredim$ of features passes the
		number $\samplesize$ of data points. The feature matrix then has
		rank at most $\samplesize$, so the least squares solution is
		not unique and every solution interpolates the training set. A
		training error of zero therefore carries no information about the
		risk, so
		the regime removes the usual evidence about generalization.
		Regularization and dimensionality reduction restore a usable method, the first
		by adding a penalty term to the training error and the second by
		shrinking the hypothesis space. High-dimensional statistics develops
		theory and methods for this regime, and its guarantees need a structural
		assumption such as sparsity.

\subsection{Definition}
Consider a weather
		service at Krems an der Donau (Austria) that predicts the
		maximum daytime temperature of a day from the maxima of the
		previous $\featuredim$ days. Each day is a
		data point with feature vector $\featurevec \in
		\reals^{\featuredim}$ and label $\truelabel \in \reals$,
		and a linear model $\hypothesis(\featurevec) =
		\weights^{\top} \featurevec$ is learned by least squares
		on a training set $\trainset$ of $\samplesize = 30$ days of
		$2023$. For $\featuredim = 1$, the training error is $12.4$ and
		the validation error on the validation set $\valset$ of the $366$ days
		of $2024$ is $10.1$ squared degrees. For $\featuredim = 29$, the
		two numbers are $1.7$ and $100.4$, and for $\featuredim = 30$
		they are $0$ and $13444$.
		Once the number of features reaches the number of
		data points in $\trainset$, the training error carries no
		information about the loss on days outside $\trainset$.
		Fig.~\ref{fig_highdimregime_errors_dict} draws both errors for
		every $\featuredim$ from $1$ to $60$.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}[scale=0.95, font=\small]
		\begin{axis}[axis lines=left, width=10.4cm, height=5.2cm,
			scale only axis, ymode=log,
			xlabel={number $\featuredim$ of features},
			ylabel={average squared error loss},
			xmin=0, xmax=61, ymin=3e-4, ymax=3e5,
			tick label style={font=\scriptsize},
			label style={font=\scriptsize},
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.5,-0.22)}, anchor=north},
			legend cell align=left]
			\addplot[thick, black]
				table[col sep=comma, x=d, y=trainplot]{highdimregime_errors.csv};
			\addlegendentry{training error (solid curve)}
			\addplot[dashed, black]
				table[col sep=comma, x=d, y=valerr]{highdimregime_errors.csv};
			\addlegendentry{validation error (dashed curve)}
			\addplot[dotted, black] coordinates {(30,3e-4) (30,3e5)};
			\addlegendentry{feature count equal to the sample size (dotted line)}
		\end{axis}
		\end{tikzpicture}
		\caption{The training error (solid curve) and the validation error
			(dashed curve) of a linear model that predicts the
			maximum daytime temperature of a day at Krems from the
			maxima of the previous $\featuredim$ days, learned by
			least squares on $\samplesize = 30$ days of $2023$ and
			evaluated on the $366$ days of $2024$. The training error
			is drawn at the axis floor $10^{-3}$ wherever it is zero.
			The dotted line marks the feature count $\featuredim =
			\samplesize = 30$ at which the high-dimensional regime
			begins. Data generated by
			\texttt{pythondemos/highdimregime.py}
			\label{fig_highdimregime_errors_dict}}
		\end{figure}
		A machine learning (ML) method operates in the high-dimensional regime when
		the effective dimension of its hypothesis space $\hypospace$ exceeds
		the sample size $\samplesize$ of the training set,
		\begin{equation}
			\label{equ_highdimregime_condition_dict}
			\effdim{\hypospace} > \samplesize \text{.}
		\end{equation}
		For the linear model above, the condition
		\eqref{equ_highdimregime_condition_dict} reads $\featuredim >
		\samplesize$. Empirical risk minimization (ERM) with the squared error loss delivers a
		solution of the least squares problem
		\begin{equation}
			\label{equ_highdimregime_leastsquares_dict}
			\min_{\weights \in \reals^{\featuredim}}
			\frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize}
			\big( \truelabel^{(\sampleidx)} - \weights^{\top}
			\featurevec^{(\sampleidx)} \big)^{2} \text{.}
		\end{equation}
		Here, the feature matrix $\featuremtx \in
		\reals^{\samplesize \times \featuredim}$ stacks the
		feature vectors of $\trainset$ as its rows and the
		vector $\labelvec \in \reals^{\samplesize}$ stacks their
		labels.
\par
		The rank of $\featuremtx$ is at most
		$\samplesize$, so for $\featuredim > \samplesize$ the
		nullspace of $\featuremtx$ holds a nonzero vector
		and the solution of the least squares problem
		\eqref{equ_highdimregime_leastsquares_dict} is not unique: its
		minimizers form an affine set of dimension at least
		$\featuredim - \samplesize$. The pseudoinverse picks the
		one of smallest Euclidean norm, $\widehat{\weights} =
		\pinv{\featuremtx} \labelvec$. Every minimizer drives the
		training error to zero, which is interpolation of
		$\trainset$. The curse of dimensionality is a separate
		consequence of a large $\featuredim$: the data points
		spread thin over the feature space $\reals^{\featuredim}$
		however many of them there are, while the high-dimensional
		regime compares two counts.
\par
		Generalization is the performance of a learned
		hypothesis on data points outside $\trainset$, and
		the regime removes the evidence that a small training error
		usually provides about it. A hypothesis that interpolates
		$\trainset$ has a training error of zero whichever
		labels the data points of $\trainset$ carry, so a
		zero training error leaves the risk undetermined and
		overfitting cannot be diagnosed from $\trainset$ alone.
		A large artificial neural network (ANN) is trained in the same regime, with far more
		trainable model parameters than data points
		(Zhang et al., 2017, Sect.~1). A deep network reaches a
		training error of zero even on a training set whose
		labels have been replaced by random ones
		(Zhang et al., 2017, Sect.~2). Learning theory measures
		the size of $\hypospace$ by its Vapnik–Chervonenkis dimension (VC dimension) and by its
		Rademacher complexity. The sample size that a
		generalization guarantee needs grows in proportion to the
		VC dimension (Shalev-Shwartz and Ben-David, 2014, Thm.~6.8).
\par
		Two routes restore a usable method on the same features,
		and both are forms of regularization. Adding the
		penalty term $\regparam \normgeneric{\weights}{2}^{2}$ to
		the training error gives ridge regression. With $\regparam
		= 100$, the validation error of the weather example stays between
		$10.2$ and $22.9$ squared degrees for every $\featuredim$ from
		$1$ to $60$. Dimensionality reduction shrinks $\hypospace$ instead:
		least squares on the first $\featuredim' = 5$ principal
		directions of the feature vectors of $\trainset$, which is
		principal component analysis (PCA), keeps the validation error between $9.8$ and $22.1$. At
		$\featuredim = \samplesize$ neither learned hypothesis
		interpolates $\trainset$: the training error is $4.2$ with the
		penalty term and $11.2$ after the reduction.
		Fig.~\ref{fig_highdimregime_restored_dict} draws the
		validation error of both against the validation error of
		least squares on all $\featuredim$ features.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}[scale=0.95, font=\small]
		\begin{axis}[axis lines=left, width=10.4cm, height=5.2cm,
			scale only axis, ymode=log,
			xlabel={number $\featuredim$ of features},
			ylabel={validation error},
			xmin=0, xmax=61, ymin=5, ymax=3e5,
			tick label style={font=\scriptsize},
			label style={font=\scriptsize},
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.5,-0.22)}, anchor=north},
			legend cell align=left]
			\addplot[dashed, black]
				table[col sep=comma, x=d, y=leastsquares]{highdimregime_restored.csv};
			\addlegendentry{least squares (dashed curve)}
			\addplot[thick, black]
				table[col sep=comma, x=d, y=ridge]{highdimregime_restored.csv};
			\addlegendentry{least squares with a penalty term (solid curve)}
			\addplot[densely dotted, black]
				table[col sep=comma, x=d, y=reduced]{highdimregime_restored.csv};
			\addlegendentry{least squares after dimensionality reduction (dotted curve)}
		\end{axis}
		\end{tikzpicture}
		\caption{The validation error of the same linear model at Krems
			against the number $\featuredim$ of features, for
			least squares (dashed curve), for least squares
			with the penalty term at $\regparam = 100$ (solid
			curve), and for least squares on the first
			$\featuredim' = 5$ principal directions (dotted curve).
			Data generated by \texttt{pythondemos/highdimregime.py}
			\label{fig_highdimregime_restored_dict}}
		\end{figure}
		High-dimensional statistics is the branch of mathematical
		statistics that develops theory and methods for this regime
		(Bühlmann and Geer, 2011; Wainwright, 2019, Sect.~1.1).
		Without a structural assumption on the model parameters, no
		method estimates them consistently once $\featuredim$ exceeds
		$\samplesize$ (Wainwright, 2019, Sect.~7.1.1). One such
		assumption is sparsity, which says that few model parameters
		are nonzero. The least absolute shrinkage and selection operator (Lasso) exploits it with a
		penalty term built from the $\ell_{1}$-norm
		(Tibshirani, 1996). The regime is
		common wherever features are cheap and data points
		are not: a gene-expression dataset with $2308$
		features and $63$ data points needs
		regularization before any classifier can be learned
		on it (Hastie et al., 2009, Sect.~18.2).

\subsection{Cross References}
effective dimension, curse of dimensionality, interpolation, overfitting, generalization, regularization, dimensionality reduction, ridge regression, Lasso, VC dimension

\subsection{References}
\begin{enumerate}
  \item Bühlmann and Geer (2011). Statistics for High-Dimensional Data: Methods, Theory and Applications. Springer-Verlag, Berlin, Germany.
  \item Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, New York, NY, USA.
  \item Tibshirani (1996). Regression Shrinkage and Selection via the Lasso. J. Roy. Statist. Soc.: Ser. B (Methodological), 58(1), pp.~267--288.
  \item Wainwright (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Univ. Press, Cambridge, U.K.
  \item Zhang et al. (2017). Understanding deep learning requires rethinking generalization. In: Int. Conf. Learn. Represent. (ICLR).
  \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}
