\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{\E}[0]{{\mathbb{E}}}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\eigval}[1]{\lambda_{#1}}
\newcommand{\feature}{x}
\newcommand{\featuredim}{d}
\newcommand{\featureidx}{j}
\newcommand{\featuremtx}{\mX}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\newcommand{\labelvec}{\vy}
\newcommand{\mI}{\mathbf{I}}
\newcommand{\mU}{\mathbf{U}}
\newcommand{\mV}{\mathbf{V}}
\newcommand{\mX}[0]{{\bf X}}
\newcommand{\mvnormal}[2]{\mathcal{N}\left(#1,#2\right)}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\pair}[2]{\left( #1,#2 \right)}
\newcommand{\perturbation}[1]{{\bm \varepsilon}^{(#1)}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\regparam}{\alpha}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\truelabel}{y}
\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{ridge regression}

\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}
Tikhonov regularization, weight decay

\subsection{Abstract}
Ridge regression learns a linear hypothesis map
		by minimizing the average squared error loss on a training set
		plus a penalty term proportional to the squared
		Euclidean norm of the model parameters. The penalty term
		enforces regularization: it prevents overfitting when
		the number of features exceeds the number of
		data points, or when features are nearly collinear.
		In contrast to least absolute shrinkage and selection operator (Lasso), ridge regression uses an
		objective function with a unique minimizer, given in closed form by one
		system of linear equations, for any training set. In the
		basis of the singular vectors of the feature matrix,
		ridge regression shrinks each component of the linear regression
		solution by a factor between $0$ and $1$ that is small for a small
		singular value, which bounds the noise amplification of
		linear regression. The penalty term represents the increase of the
		average squared error loss under data augmentation with random
		feature perturbations. Ridge regression on transformed
		feature vectors constructed from a kernel is
		kernel ridge regression.

\subsection{Definition}
Predicting the maximum temperature
		of tomorrow at Krems an der Donau from the $24$ hourly temperatures
		of today is a machine learning (ML) application. A data point is one day,
		its feature vector $\featurevec \in \reals^{24}$ lists the
		hourly temperatures of the day, and its label $\truelabel$ is
		the maximum temperature of the next day (GeoSphere Austria, 2026). A
		training set of $\samplesize = 20$ days of July 2024 has fewer
		data points than features, $\featuredim = 24$, and the
		features are nearly collinear: the temperatures at 13:00
		and at 14:00 have correlation $0.93$. Linear regression then
		learns a linear model that reproduces the $20$ training
		labels exactly and predicts the maximum temperatures of
		August 2024, the test set, with a mean squared error (MSE) of $141$. Ridge
		regression learns a linear model from the same training set
		with a training MSE of $5.4$ and an MSE of
		$8.3$ on the test set (see Fig.~\ref{fig_ridge_krems_dict}).
\par
		Ridge regression learns the model parameters $\weights$ of a
		linear hypothesis map
		$\hypothesis^{(\weights)}(\featurevec) = \weights^{\top}\featurevec$,
		as does linear regression. It minimizes the penalized average
		squared error loss on a training set
		$\trainset = \big\{ \pair{\featurevec^{(\sampleidx)}}{\truelabel^{(\sampleidx)}} \big\}_{\sampleidx=1}^{\samplesize}$
		(Hoerl and Kennard, 1970),
		\begin{equation}
		\label{eq:ridge_rerm}
		\widehat{\weights}^{(\regparam)} = \argmin_{\weights \in \reals^{\featuredim}}
		\frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize}
		\big( \truelabel^{(\sampleidx)} - \weights^{\top}\featurevec^{(\sampleidx)} \big)^{2}
		+ \regparam \normgeneric{\weights}{2}^{2} \text{.}
		\end{equation}
		The optimization problem can be written more compactly using the
		feature matrix $\featuremtx$ and the label vector $\labelvec$,
		\[
			\featuremtx = \big(\featurevec^{(1)},\,\ldots,\,\featurevec^{(\samplesize)}\big)^{\top}
			\in \reals^{\samplesize \times \featuredim} \text{,} \qquad
			\labelvec = \big( \truelabel^{(1)},\,\ldots,\,\truelabel^{(\samplesize)} \big)^{\top}
			\in \reals^{\samplesize} \text{.}
		\]
		In terms of $\featuremtx$ and $\labelvec$, the ridge regression
		problem \eqref{eq:ridge_rerm} reads
		\[
			\widehat{\weights}^{(\regparam)} = \argmin_{\weights \in \reals^{\featuredim}}
			\frac{1}{\samplesize} \normgeneric{\labelvec - \featuremtx \weights}{2}^{2} + \regparam \normgeneric{\weights}{2}^{2} \text{.}
		\]
\par
		Ridge regression is obtained from linear regression by adding a
		penalty term to the average squared error loss. The penalty term
		is the scaled squared Euclidean norm $\regparam \normgeneric{\weights}{2}^{2}$
		with a regularization parameter $\regparam > 0$
		(Hastie et al., 2009, Sect.~3.4.1, Eq.~(3.41)). The
		resulting method is an instance of regularized empirical risk minimization (RERM). The purpose of
		the penalty term is regularization. It prevents
		overfitting in the high-dimensional regime, where the number of
		features $\featuredim$ exceeds the number of data points
		$\samplesize$ in the training set
		(Hastie et al., 2009, Sect.~18.1), as it does for the
		$20$ days with $24$ hourly temperatures each. An alternative
		method for regularization is least absolute shrinkage and selection operator (Lasso), which differs from
		ridge regression in the construction of the penalty term:
		Lasso uses the $\ell_{1}$-norm $\normgeneric{\weights}{1}$
		instead of the squared Euclidean norm
		$\normgeneric{\weights}{2}^{2}$.
\par
		In contrast to Lasso, whose objective can have several
		minimizers, the ridge regression objective function has, for any
		feature matrix $\featuremtx$ and label vector $\labelvec$,
		the unique minimizer
		\begin{equation}
		\label{eq:ridge_closedform}
		\widehat{\weights}^{(\regparam)} = \big( \featuremtx^{\top}\featuremtx
		+ \regparam \samplesize \mI \big)^{-1} \featuremtx^{\top}\labelvec \text{.}
		\end{equation}
		The normal equations of plain linear regression, by
		comparison, can have infinitely many solutions, as they do for the
		$20$ days of July: every one of them reproduces the training
		labels. Training is a one-shot computation: ridge
		regression requires no iterative optimization method, and hence no
		fixed-point interpretation, only the solution of the
		$\featuredim \times \featuredim$ system of linear equations
		$\big( \featuremtx^{\top}\featuremtx + \regparam \samplesize \mI \big) \weights = \featuremtx^{\top}\labelvec$
		with an invertible matrix, the
		zero-gradient condition of the penalized objective function. For
		many features, gradient descent (GD) on the penalized objective function is the
		alternative, and the penalty term adds $\regparam \samplesize$
		to every eigenvalue of $\featuremtx^{\top}\featuremtx$,
		which lowers the condition number that sets the convergence rate of
		GD.
\par
		The singular value decomposition (SVD) of the feature matrix shows why the linear regression
		solution amplifies the noise in the labels and how the
		penalty term bounds the amplification. Write
		$\featuremtx = \mV \bm{\Lambda} \mU^{\top}$ with
		singular values $\eigval{1} \geq \ldots \geq \eigval{p} > 0$,
		where $p$ is the rank of $\featuremtx$, with left singular
		vectors $\vv^{(\featureidx)}$ and right singular
		vectors $\vu^{(\featureidx)}$. The solution of linear regression
		with the smallest Euclidean norm is
		\[
		\widehat{\weights} = \sum_{\featureidx=1}^{p}
		\frac{(\vv^{(\featureidx)})^{\top}\labelvec}{\eigval{\featureidx}}
		\, \vu^{(\featureidx)} \text{.}
		\]
		Two properties of this solution cause its large test error. A
		component of $\labelvec$ along
		$\vv^{(\featureidx)}$ is divided by $\eigval{\featureidx}$, so a
		small singular value amplifies the noise in $\labelvec$ by the
		factor $1/\eigval{\featureidx}$. Small singular values arise
		from nearly collinear features: the singular values
		of the $20$ days of hourly temperatures run from $504$ down to
		$0.21$. And a direction $\vu^{(\featureidx)}$ with
		$\featureidx > p$, which exists whenever $\featuredim > \samplesize$,
		leaves $\featuremtx \weights$ unchanged, so the training set does
		not determine the component of $\weights$ along it.
\par
		Inserting the SVD into the closed form \eqref{eq:ridge_closedform} gives
		(Hastie et al., 2009, Sect.~3.4.1, Eq.~(3.47))
		\[
		\widehat{\weights}^{(\regparam)} = \sum_{\featureidx=1}^{p}
		\frac{\eigval{\featureidx}^{2}}{\eigval{\featureidx}^{2}
		+ \regparam \samplesize} \cdot
		\frac{(\vv^{(\featureidx)})^{\top}\labelvec}{\eigval{\featureidx}}
		\, \vu^{(\featureidx)} \text{.}
		\]
		Ridge regression multiplies each component of
		$\widehat{\weights}$ in the basis of the right singular
		vectors by the shrinkage factor
		$\eigval{\featureidx}^{2} / (\eigval{\featureidx}^{2} + \regparam
		\samplesize)$, which lies strictly between $0$ and $1$. For
		$\eigval{\featureidx}^{2} \gg \regparam \samplesize$ the factor is
		close to $1$ and the component is kept. For
		$\eigval{\featureidx}^{2} \ll \regparam \samplesize$ the component
		is shrunk toward $0$. The product of the factor and
		$1/\eigval{\featureidx}$ is
		$\eigval{\featureidx} / (\eigval{\featureidx}^{2} + \regparam
		\samplesize)$, which never exceeds $1/(2\sqrt{\regparam
		\samplesize})$, so the noise amplification is bounded: for the
		$20$ days and $\regparam = 1$, the bound is $0.11$, where
		$1/\eigval{\featureidx}$ reaches $4.9$. The undetermined
		components with $\featureidx > p$ are set to $0$, which is why the
		minimizer is unique for any feature matrix. Fig.~\ref{fig_ridge_krems_dict}
		shows the effect on the learned model parameters: those of
		linear regression swing between $-4.1$ and $4.9$ from one hour to the
		next, those of ridge regression stay within $\pm 0.4$.
		\begin{figure}[H]
			\centering
			\begin{tikzpicture}
			\begin{axis}[
				name=panelA,
				width=0.48\linewidth, height=0.4\linewidth,
				xlabel={hour $\featureidx$ of the day\\(a) learned model parameters},
				ylabel={model parameter $\weight_{\featureidx}$},
				xmin=-0.7, xmax=23.7, xtick={0,6,12,18,23},
				axis lines=left,
				label style={align=center, font=\small},
				tick label style={font=\small},
				legend style={draw=none, fill=none, font=\small,
					at={(0.5,-0.45)}, anchor=north, legend columns=1},
				]
				\addplot[dashed, mark=o, mark size=1.5pt]
					table[col sep=comma, x=hour, y=ls]{ridgeregression_weights.csv};
				\addlegendentry{linear regression}
				\addplot[thick, mark=*, mark size=1.2pt]
					table[col sep=comma, x=hour, y=ridge]{ridgeregression_weights.csv};
				\addlegendentry{ridge regression}
			\end{axis}
			\begin{axis}[
				at={(panelA.east)}, anchor=west, xshift=1.1cm,
				width=0.48\linewidth, height=0.4\linewidth,
				xmode=log, ymode=log,
				xlabel={regularization parameter $\regparam$\\(b) MSE of ridge regression},
				ylabel={MSE},
				axis lines=left,
				label style={align=center, font=\small},
				tick label style={font=\small},
				legend style={draw=none, fill=none, font=\small,
					at={(0.5,-0.45)}, anchor=north, legend columns=1},
				]
				\addplot[dashed]
					table[col sep=comma, x=alpha, y=train]{ridgeregression_alpha.csv};
				\addlegendentry{training set (July 1--20)}
				\addplot[thick]
					table[col sep=comma, x=alpha, y=test]{ridgeregression_alpha.csv};
				\addlegendentry{test set (August)}
			\end{axis}
			\end{tikzpicture}
		\caption{Ridge regression for the maximum temperature of the next
			day at Krems an der Donau, learned from the $24$ hourly
			temperatures of $\samplesize = 20$ days of July 2024. Panel (a)
			shows the $24$ model parameters of the linear model learned by
			linear regression (dashed line, open circles) and by ridge regression
			with $\regparam = 1$ (solid line, dots). Panel (b) shows the
			MSE of ridge regression on the training set (dashed
			curve) and on the $31$ days of August 2024 (solid curve) over the
			regularization parameter $\regparam$. Data generated by
			\texttt{pythondemos/ridgeregression.py}
			\label{fig_ridge_krems_dict}}
		\end{figure}
		The penalty term $\regparam \normgeneric{\weights}{2}^{2}$ has an
		interpretation as a form of data augmentation
		(Bishop, 1995, Eqs.~(10)--(11)). In particular,
		adding the penalty term to the average squared error loss
		of the hypothesis $\hypothesis^{(\weights)}$ is equivalent to
		computing its average squared error loss on an augmented training set
		(see Fig.~\ref{fig_ridge_regression_dict}).
		This augmented training set is obtained from the original
		training set. For each data point
		$\pair{\featurevec^{(\sampleidx)}}{\truelabel^{(\sampleidx)}}$,
		$\sampleidx=1,\ldots,\samplesize$,
		the feature vector $\featurevec^{(\sampleidx)}$ is replaced by
		realizations of infinitely many independent and identically distributed (i.i.d.) random variables (RVs)
		$\featurevec^{(\sampleidx)} + \perturbation{\sampleidx}$ with
		Gaussian random variables (Gaussian RVs)
		$\perturbation{\sampleidx} \sim \mvnormal{\mathbf{0}}{\regparam \mI}$,
		i.e., each feature is perturbed independently with variance
		$\regparam$.
		The label $\truelabel^{(\sampleidx)}$ is left unchanged.
		\begin{figure}[H]
			\begin{center}
				\begin{tikzpicture}[scale = 1]
					% Axes
					\draw[->, very thick] (0,0.5) -- (7.7,0.5) node[right] {feature $\feature$};       % X-axis
					\draw[->, very thick] (0.5,0) -- (0.5,4.2) node[above] {label $\truelabel$};   % Y-axis
					\draw[color=black, thick, dashed, domain = -1: 6.2, variable = \x]  plot ({\x},{\x*0.4 + 2.0}) ;
					\node at (6.7,4.5) {$\hypothesis^{(\weights)}(\feature)$};
					\coordinate (l1)   at (1.1, 2.48);
					\coordinate (l2) at (1.4, 2.56);
					\coordinate (l3)   at (1.7,  2.68);
					\coordinate (l4)   at (2.1, 2.1*0.4+2.0);
					\coordinate (l5) at (2.4, 2.4*0.4+2.0);
					\coordinate (l6)   at (2.7,  2.7*0.4+2.0);
					\coordinate (l7)   at (3.9,  3.9*0.4+2.0);
					\coordinate (l8) at (4.2, 4.2*0.4+2.0);
					\coordinate (l9)   at (4.5,  4.5*0.4+2.0);
					\coordinate (n1)   at (1.1, 1.8);
					\coordinate (n2) at (1.4, 1.8);
					\coordinate (n3)   at (1.7,  1.8);
					\coordinate (n4)   at (2.1, 3.8);
					\coordinate (n5) at (2.4, 3.8);
					\coordinate (n6)   at (2.7,  3.8);
					% augmented data points obtained by perturbing the feature, not the label
					\coordinate (n7)   at (3.9, 2.6);
					\coordinate (n8) at (4.2, 2.6);
					\coordinate (n9)   at (4.5,  2.6);
					\node at (n1)  [rectangle,draw=red,thick,fill=white,minimum size=9pt,scale=0.6, name=c1] {};
					\node at (n2)  [circle,draw,fill=blue,minimum size=9pt, scale=0.6, name=c2] {};
					\node at (n3)  [rectangle,draw=red,thick,fill=white,minimum size=9pt,scale=0.6,  name=c3] {};
					\node at (n4)  [rectangle,draw=red,thick,fill=white,minimum size=9pt, scale=0.6, name=c4] {};
					\node at (n5)  [circle,draw,fill=blue,minimum size=9pt,scale=0.6,  name=c5] {};
					\node at (n6)  [rectangle,draw=red,thick,fill=white,minimum size=9pt, scale=0.6, name=c6] {};
					\node at (n7)  [rectangle,draw=red,thick,fill=white,minimum size=9pt,scale=0.6,  name=c7] {};
					\node at (n8)  [circle,draw,fill=blue,minimum size=9pt, scale=0.6, name=c8] {};
					\node at (n9)  [rectangle,draw=red,thick,fill=white,minimum size=9pt, scale=0.6, name=c9] {};
					\draw [<->] ($ (n7) + (0,-0.3) $)  --  ($ (n9) + (0,-0.3) $) node [pos=0.5, below] {$\propto\sqrt{\regparam}$};
					\draw[<->, color=red, thick] (l1) -- (c1);
					\draw[<->, color=blue, thick] (l2) -- (c2);
					\draw[<->, color=red, thick] (l3) -- (c3);
					\draw[<->, color=red, thick] (l4) -- (c4);
					\draw[<->, color=blue, thick] (l5) -- (c5);
					\draw[<->, color=red, thick] (l6) -- (c6);
					\draw[<->, color=red, thick] (l7) -- (c7);
					\draw[<->, color=blue, thick] (l8) -- (c8);
					\draw[<->, color=red, thick] (l9) -- (c9);
					\draw[fill=blue] (6.2, 3.7)  circle (0.1cm) node [anchor=west,black,xshift=0.1cm] {original data point $\pair{\feature}{\truelabel}$};
					\draw[red, thick, fill=white] (6.1, 3.1) rectangle (6.3, 3.3);
					\node [anchor=west,black] at (6.3, 3.2) {perturbed copy $\pair{\feature + \varepsilon}{\truelabel}$};
				\end{tikzpicture}
			\caption{For a linear model with one feature, adding the
				penalty term $\regparam \normgeneric{\weights}{2}^2$ to the
				average squared error loss is equivalent to computing the average
				squared error loss on an augmented training set: each original
				data point (blue circle) is replaced by copies (red squares)
				whose feature is perturbed by a Gaussian RV $\varepsilon$
				with variance $\regparam$, keeping the label. The
				vertical arrows show the error
				$\truelabel - \hypothesis^{(\weights)}(\feature)$ of each
				data point \label{fig_ridge_regression_dict} }
			\end{center}
		\end{figure}
		The penalty term $\regparam \normgeneric{\weights}{2}^{2}$ is
		exactly the amount by which the average squared error loss of
		$\hypothesis^{(\weights)}$ over the infinitely many perturbed
		copies of a data point exceeds its squared error loss on the
		original data point. Since
		$\E \{ \perturbation{\sampleidx} \} = \mathbf{0}$, the increase is
		\[
			\E \big\{ \big( \weights^{\top} \perturbation{\sampleidx} \big)^{2} \big\}
			= \weights^{\top} \E \big\{ \perturbation{\sampleidx} \big(\perturbation{\sampleidx}\big)^{\top} \big\} \weights
			= \regparam \normgeneric{\weights}{2}^{2} \text{.}
		\]
		This increase of the average loss under data augmentation is an
		estimate for the generalization gap
		(Hastie et al., 2009, Sect.~7.4). Ridge regression
		applied to transformed feature vectors constructed from a
		kernel is kernel ridge regression, which learns a
		nonlinear hypothesis in closed form; the perturbation then
		acts on the transformed feature vectors.

\subsection{Cross References}
regression, linear regression, Lasso, regularization, penalty term, SVD, condition number, data augmentation, kernel ridge regression

\subsection{References}
\begin{enumerate}
  \item Bishop (1995). Training with Noise is Equivalent to Tikhonov Regularization. Neural Computation, 7(1), pp.~108--116.
  \item GeoSphere Austria (2026). GeoSphere Austria climate station archive. Data hub, station historical resource klima-v2-1d. URL: https://dataset.api.hub.geosphere.at/v1/station/historical/klima-v2-1d.
  \item Hoerl and Kennard (1970). Ridge Regression: Biased Estimation for Nonorthogonal Problems. Technometrics, 12(1), pp.~55--67.
  \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}
