\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{\defeq}{:=}
\newcommand{\expcoeff}{\beta}
\newcommand{\feature}{x}
\newcommand{\featuredim}{d}
\newcommand{\featureidx}{j}
\newcommand{\featuremtx}{\mX}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\newcommand{\innerprod}[2]{\langle #1, #2 \rangle}
\newcommand{\labelvec}{\vy}
\newcommand{\mX}[0]{{\bf X}}
\newcommand{\metric}[2]{d(#1,#2)}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\pair}[2]{\left( #1,#2 \right)}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\regparam}{\alpha}
\newcommand{\samplesize}{m}
\newcommand{\sphere}[1]{\mathbb{S}^{(#1)}}
\newcommand{\truelabel}{y}
\newcommand{\vecspace}{\mathcal{V}}
\newcommand{\vu}[0]{{\bf u}}
\newcommand{\vv}[0]{{\bf v}}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\vy}[0]{{\bf y}}
\newcommand{\weight}{w}
\newcommand{\weights}{\vw}

\begin{document}

\section{norm}

\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 norm on a vector space is a function that
		assigns each vector a nonnegative number, its length. A
		norm is definite and homogeneous, and it satisfies the triangle
		inequality. Every norm defines a metric via the norm of
		the difference of two vectors, and every
		inner product induces a norm, but not every norm is induced
		by one. The $\ell_{p}$-norms on $\reals^{\featuredim}$ include
		the $\ell_{1}$-norm, the Euclidean norm, and the
		$\ell_{\infty}$-norm; among them only the Euclidean norm is
		induced by an inner product. In machine learning (ML),
		norms are used to construct loss functions and regularizers.

\subsection{Definition}
The hourly temperature recordings of one day at a weather
	station form the feature vector $\featurevec \in \reals^{\featuredim}$
	of that day, with one entry per hour. Many machine learning (ML)
		methods use a measure for the size of such a vector or for the
		distance between two of them. A norm provides both: it assigns
		each vector a length, and the length of the difference of two
		vectors is their distance.
\par
		Formally, a norm
		$\normgeneric{\, \cdot \,}{}$ on a vector space $\vecspace$ over the
		field $\reals$ is a function
		$\normgeneric{\, \cdot \,}{}: \vecspace \to \reals_{+}$
		that satisfies the conditions below (Horn and Johnson, 2013).
		These conditions hold for all vectors $\vu, \vv \in \vecspace$
		and all scalars $\expcoeff \in \reals$, with $|\expcoeff|$ the
		absolute value of $\expcoeff$:
		\begin{itemize}
			\item Definiteness: $\normgeneric{\vu}{} = 0 \iff \vu = \mathbf{0}$;
			\item Homogeneity: $\normgeneric{\expcoeff \vu}{} = |\expcoeff| \cdot \normgeneric{\vu}{}$;
			\item Triangle inequality: $\normgeneric{\vu + \vv}{} \leq \normgeneric{\vu}{} + \normgeneric{\vv}{}$.
		\end{itemize}
		The same conditions define a norm on a vector space over the
		field of complex numbers $\mathbb{C}$, with $\expcoeff \in
		\mathbb{C}$ and $|\expcoeff|$ its modulus. A function that
		satisfies homogeneity and the triangle inequality but assigns the
		value zero to some nonzero vector is a seminorm, not a norm:
		on $\reals^{2}$, the map $\vu = (u_{1}, u_{2})^{\top} \mapsto |u_{1}|$,
		which keeps only the first entry, is a seminorm that is zero on
		$(0,1)^{\top}$.
\par
		Every norm defines a metric by
		$\metric{\vu}{\vv} \defeq \normgeneric{\vu - \vv}{}$,
		making $\pair{\vecspace}{\metric{\cdot}{\cdot}}$ a metric space.
		Some norms are induced by an inner product
		$\innerprod{\cdot}{\cdot}$, a function of two vectors
		that is symmetric, linear in each argument, and positive-definite
		(on $\reals^{\featuredim}$, $\innerprod{\vu}{\vv} = \vu^{\top} \vv$). On an inner product
		space, $\normgeneric{\vu}{} \defeq \sqrt{\innerprod{\vu}{\vu}}$ is a
		norm (Axler, 2024, Thm.~6.14 and Thm.~6.17), and the norm of a
		Hilbert space is of this form. An
		induced norm satisfies the parallelogram identity
		$\normgeneric{\vu + \vv}{}^{2} + \normgeneric{\vu - \vv}{}^{2}
		= 2 \normgeneric{\vu}{}^{2} + 2 \normgeneric{\vv}{}^{2}$, obtained
		by expanding $\innerprod{\vu \pm \vv}{\vu \pm \vv}$.
\par
		For the vector space $\vecspace = \reals^{\featuredim}$ of
		feature vectors $\featurevec = (\feature_{1}, \ldots,
		\feature_{\featuredim})^{\top}$ and a number $p \geq 1$, the
		$\ell_p$-norm of $\featurevec$ is defined as
		$\normgeneric{\featurevec}{p} = \left( \displaystyle \sum_{\featureidx=1}^{\featuredim} |\feature_{\featureidx}|^p \right)^{1/p}$.
		It satisfies the triangle inequality by Minkowski's inequality and
		is therefore a norm (Horn and Johnson, 2013, Sect.~5.2, Eq.~(5.2.4)).
		Its instances include the $\ell_1$-norm
		$\normgeneric{\featurevec}{1} = \sum_{\featureidx=1}^{\featuredim} |\feature_{\featureidx}|$
		and the $\ell_2$-norm
		$\normgeneric{\featurevec}{2} = \big( \sum_{\featureidx=1}^{\featuredim} \feature_{\featureidx}^{2} \big)^{1/2}$
		(the Euclidean norm); the limit $p \to \infty$ yields the
		$\ell_\infty$-norm
		$\normgeneric{\featurevec}{\infty} = \max_{\featureidx = 1, \ldots, \featuredim} |\feature_{\featureidx}|$.
		The $\ell_2$-norm is induced by the inner product
		$\vu^{\top} \vv$, and it is the only $\ell_p$-norm induced by an
		inner product. For $\vu = (1, 0)^{\top}$ and
		$\vv = (0, 1)^{\top}$ in $\reals^{2}$, both $\vu + \vv$ and
		$\vu - \vv$ have $\ell_p$-norm $2^{1/p}$, so the left-hand side of
		the parallelogram identity is $2 \cdot 2^{2/p}$ while the
		right-hand side is $4$, and the two agree only for $p = 2$. The
		left-hand side equals $8$ for the $\ell_1$-norm and $2$ for the
		$\ell_\infty$-norm.
		The three norms differ in which vectors they count as
		having unit length. The unit sphere
		$\sphere{1} \defeq \big\{ \vu \in \reals^{2} : \normgeneric{\vu}{} = 1 \big\}$
		of a norm on $\reals^{2}$ contains those vectors, and
		Fig.\ \ref{fig:norms_unit_balls_dict} shows it for the $\ell_1$-,
		the $\ell_2$-, and the $\ell_\infty$-norm.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}[scale=1.5]
			% Axes
			\draw[->] (-1.4,0) -- (1.4,0) node[right] {$u_1$};
			\draw[->] (0,-1.4) -- (0,1.4) node[above] {$u_2$};
			% L-infinity (Square)
			\draw[thick, densely dotted] (-1,-1) rectangle (1,1);
			\node at (1.22, 0.8) {$\ell_\infty$};
			% L2 (Circle)
			\draw[thick] (0,0) circle (1);
			\node at (0.72, 0.85) {$\ell_2$};
			% L1 (Diamond)
			\draw[thick, dashed] (1,0) -- (0,1) -- (-1,0) -- (0,-1) -- cycle;
			\node at (0.32, 0.32) {$\ell_1$};
		\end{tikzpicture}
		\caption{Unit spheres $\sphere{1}$ of the $\ell_p$-norms on $\reals^{2}$,
			for vectors $\vu = (u_{1}, u_{2})^{\top}$ and
			$p=1$ (dashed diamond), $p=2$ (solid circle), and
			$p=\infty$ (dotted square)}
			\label{fig:norms_unit_balls_dict}
		\end{figure}
		ML methods use norms to construct loss functions and 
		regularizers. In linear regression, the label vector
		$\labelvec \in \reals^{\samplesize}$ stacks the labels of a
		training set of size $\samplesize$ and the feature matrix
		$\featuremtx \in \reals^{\samplesize \times \featuredim}$ stacks
		its feature vectors. The average squared error loss of a linear
		hypothesis with model parameters $\weights$ is then the scaled
		squared Euclidean norm
		$(1/\samplesize) \normgeneric{\labelvec - \featuremtx \weights}{2}^{2}$
		of the residual $\labelvec - \featuremtx \weights$.
		Ridge regression adds the penalty term
		$\regparam \normgeneric{\weights}{2}^{2}$ to this training error,
		with a hyperparameter $\regparam > 0$, while
		the least absolute shrinkage and selection operator (Lasso) adds $\regparam \normgeneric{\weights}{1}$
		(Tibshirani, 1996).
\par
		The choice of the norm determines the learned hypothesis by empirical risk minimization (ERM). 
		Consider the two optimization problems
		\[
			\min_{\weights \in \reals^{\featuredim}}
			\normgeneric{\labelvec - \featuremtx \weights}{2}
			\quad \text{ and } \quad
			\min_{\weights \in \reals^{\featuredim}}
			\normgeneric{\labelvec - \featuremtx \weights}{1} \text{,}
		\]
		which differ only in the norm of the residual. Squaring the
		$\ell_2$-norm does not change the set of minimizers, so
		minimizing the $\ell_2$-norm of the
		residual is equivalent to minimizing the average
		squared error loss. The distinction between induced and other norms
		matters here. An induced norm defines angles and
		orthogonal projections, and the squared $\ell_2$-norm of the
		residual is a quadratic function of $\weights$, so the
		least squares problem has a closed-form solution, obtained
		from the normal equations
		(Boyd and Vandenberghe, 2004, Sect.~1.2). This is why the $\ell_2$-norm is
		the norm of the loss function of linear regression. Minimizing the
		$\ell_1$-norm of the residual is a linear program
		(Boyd and Vandenberghe, 2004, Sect.~6.1.1), which has no closed-form
		solution and is solved iteratively, as is the Lasso problem
		with its $\ell_1$-norm penalty.
\par
		Fig.~\ref{fig:norm_mlfit_dict}
		shows a training set of four data points, one of which
		is an outlier, and two linear hypotheses
		$\hypothesis(\feature) = \weight \feature$ learned from it.
		Minimizing the squared $\ell_2$-norm of the residual gives the
		slope $\widehat{\weight} = 46/30$. This solution is moved
		toward the outlier because squaring makes the largest
		residual the main part of the training error. Minimizing the
		$\ell_1$-norm yields $\widehat{\weight} = 1$, which predicts the
		three remaining data points exactly and leaves a single
		large residual at the outlier. The hypothesis learned
		with the $\ell_1$-norm is robust to the outlier in the
		sense that one unusual data point barely moves it
		(Boyd and Vandenberghe, 2004, Sect.~6.1.2), while the
		one learned by minimizing the squared $\ell_2$-norm is not
		(see robustness). Both slopes are learned from the
		training set; which of the two hypotheses has the
		smaller risk on data points outside it depends on
		whether outliers are present there as well.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{axis}[
			width=7.5cm, height=5.2cm,
			axis lines=left,
			xlabel={feature $\feature$},
			ylabel={label $\truelabel$},
			xmin=0, xmax=5.9, ymin=0, ymax=9.6,
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.5,-0.3)}, anchor=north, legend columns=3,
				column sep=6pt},
			legend cell align=left]
			\addplot[black, thick] table[col sep=comma, x=x, y=l2]
				{norm_fits.csv};
			\addlegendentry{$\ell_2$-norm of the residual}
			\addplot[black, thick, dashed] table[col sep=comma, x=x, y=l1]
				{norm_fits.csv};
			\addlegendentry{$\ell_1$-norm of the residual}
			\addplot[black, only marks, mark=*, mark size=1.8pt]
				table[col sep=comma, x=x, y=y]{norm_points.csv};
			\addlegendentry{training set of $4$ data points}
			\draw[densely dotted, black] (axis cs:4,4) -- (axis cs:4,8);
			\node[font=\scriptsize, anchor=west] at (axis cs:4.05,6)
				{residual};
			\node[font=\scriptsize, anchor=south] at (axis cs:4,8.2)
				{outlier};
		\end{axis}
		\end{tikzpicture}
		\caption{Two linear hypotheses
			$\hypothesis(\feature) = \weight \feature$ learned from the
			same training set of four data points (filled circles)
			by minimizing a norm of the residual. The squared $\ell_2$-norm
			yields the solid line with slope $\widehat{\weight} = 46/30$,
			moved toward the outlier; the $\ell_1$-norm yields the
			dashed line with slope $\widehat{\weight} = 1$, which predicts the three remaining
			data points exactly and leaves one large residual
			(dotted vertical segment) at the outlier. Data generated by
			\texttt{pythondemos/norm.py}
			\label{fig:norm_mlfit_dict}}
		\end{figure}

\subsection{Cross References}
vector space, metric, metric space, Euclidean space, Hilbert space, inner product, Euclidean norm, regularizer, linear regression, Lasso

\subsection{References}
\begin{enumerate}
  \item Axler (2024). Linear Algebra Done Right. 4th ed., Springer, Cham, Switzerland.
  \item Boyd and Vandenberghe (2004). Convex Optimization. Cambridge Univ. Press, Cambridge, U.K.
  \item Horn and Johnson (2013). Matrix Analysis. 2nd ed., 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.
\end{enumerate}

\end{document}