Regularization (mathematics)

In mathematics, statistics, finance,[1] computer science, particularly in machine learning and inverse problems, regularization is the process of adding information in order to solve an ill-posed problem or to prevent overfitting.[2]

The green and blue functions both incur zero loss on the given data points. A learned model can be induced to prefer the green function, which may generalize better to more points drawn from the underlying unknown distribution, by adjusting ${\displaystyle \lambda }$, the weight of the regularization term.

Regularization applies to objective functions in ill-posed optimization problems. The regularization term, or penalty, imposes a cost on the optimization function for overfitting the function or to find an optimal solution.

In machine learning, regularisation is any modification we make to a learning algorithm that is intended to reduce its generalisation error but not its training error[3]

Classification

Empirical learning of classifiers (from a finite data set) is always an underdetermined problem, because it attempts to infer a function of any ${\displaystyle x}$ given only examples ${\displaystyle x_{1},x_{2},...x_{n}}$.

A regularization term (or regularizer) ${\displaystyle R(f)}$ is added to a loss function:

${\displaystyle \min _{f}\sum _{i=1}^{n}V(f(x_{i}),y_{i})+\lambda R(f)}$

where ${\displaystyle V}$ is an underlying loss function that describes the cost of predicting ${\displaystyle f(x)}$ when the label is ${\displaystyle y}$, such as the square loss or hinge loss; and ${\displaystyle \lambda }$ is a parameter which controls the importance of the regularization term. ${\displaystyle R(f)}$ is typically chosen to impose a penalty on the complexity of ${\displaystyle f}$. Concrete notions of complexity used include restrictions for smoothness and bounds on the vector space norm.[4]

A theoretical justification for regularization is that it attempts to impose Occam's razor on the solution (as depicted in the figure above, where the green function, the simpler one, may be preferred). From a Bayesian point of view, many regularization techniques correspond to imposing certain prior distributions on model parameters.[5]

Regularization can serve multiple purposes, including learning simpler models, inducing models to be sparse and introducing group structure into the learning problem.

The same idea arose in many fields of science. A simple form of regularization applied to integral equations (Tikhonov regularization) is essentially a trade-off between fitting the data and reducing a norm of the solution. More recently, non-linear regularization methods, including total variation regularization, have become popular.

Generalization

Regularization can be motivated as a technique to improve the generalizability of a learned model.

The goal of this learning problem is to find a function that fits or predicts the outcome (label) that minimizes the expected error over all possible inputs and labels. The expected error of a function ${\displaystyle f_{n}}$ is:

${\displaystyle I[f_{n}]=\int _{X\times Y}V(f_{n}(x),y)\rho (x,y)\,dx\,dy}$

where ${\displaystyle X}$ and ${\displaystyle Y}$ are the domains of input data ${\displaystyle x}$ and their labels ${\displaystyle y}$ respectively.

Typically in learning problems, only a subset of input data and labels are available, measured with some noise. Therefore, the expected error is unmeasurable, and the best surrogate available is the empirical error over the ${\displaystyle N}$ available samples:

${\displaystyle I_{S}[f_{n}]={\frac {1}{n}}\sum _{i=1}^{N}V(f_{n}({\hat {x}}_{i}),{\hat {y}}_{i})}$

Without bounds on the complexity of the function space (formally, the reproducing kernel Hilbert space) available, a model will be learned that incurs zero loss on the surrogate empirical error. If measurements (e.g. of ${\displaystyle x_{i}}$) were made with noise, this model may suffer from overfitting and display poor expected error. Regularization introduces a penalty for exploring certain regions of the function space used to build the model, which can improve generalization.

Tikhonov regularization

These techniques are named for Andrey Nikolayevich Tikhonov, who applied regularization to integral equations and made important contributions in many other areas.

When learning a linear function ${\displaystyle f}$, characterized by an unknown vector ${\displaystyle w}$ such that ${\displaystyle f(x)=w\cdot x}$, one can add the ${\displaystyle L_{2}}$-norm of the vector ${\displaystyle w}$ to the loss expression in order to prefer solutions with smaller norms. Tikhonov regularization is one of the most common forms. It is also known as ridge regression. It is expressed as:

${\displaystyle \min _{w}\sum _{i=1}^{n}V({\hat {x}}_{i}\cdot w,{\hat {y}}_{i})+\lambda \|w\|_{2}^{2}}$

In the case of a general function, the norm of the function in its reproducing kernel Hilbert space is:

${\displaystyle \min _{f}\sum _{i=1}^{n}V(f({\hat {x}}_{i}),{\hat {y}}_{i})+\lambda \|f\|_{\mathcal {H}}^{2}}$

As the ${\displaystyle L_{2}}$ norm is differentiable, learning can be advanced by gradient descent.

Tikhonov-regularized least squares

The learning problem with the least squares loss function and Tikhonov regularization can be solved analytically. Written in matrix form, the optimal ${\displaystyle w}$ is the one for which the gradient of the loss function with respect to ${\displaystyle w}$ is 0.

${\displaystyle \min _{w}{\frac {1}{n}}({\hat {X}}w-Y)^{T}({\hat {X}}w-Y)+\lambda \|w\|_{2}^{2}}$

${\displaystyle \nabla _{w}={\frac {2}{n}}{\hat {X}}^{T}({\hat {X}}w-Y)+2\lambda w}$

${\displaystyle 0={\hat {X}}^{T}({\hat {X}}w-Y)+n\lambda w}$    (first-order condition)

${\displaystyle w=({\hat {X}}^{T}{\hat {X}}+\lambda nI)^{-1}({\hat {X}}^{T}Y)}$

By construction of the optimization problem, other values of ${\displaystyle w}$ give larger values for the loss function. This can be verified by examining the second derivative ${\displaystyle \nabla _{ww}}$.

During training, this algorithm takes ${\displaystyle O(d^{3}+nd^{2})}$ time. The terms correspond to the matrix inversion and calculating ${\displaystyle X^{T}X}$, respectively. Testing takes ${\displaystyle O(nd)}$ time.

Early stopping

Early stopping can be viewed as regularization in time. Intuitively, a training procedure such as gradient descent tends to learn more and more complex functions with increasing iterations. By regularizing for time, model complexity can be controlled, improving generalization.

Early stopping is implemented using one data set for training, one statistically independent data set for validation and another for testing. The model is trained until performance on the validation set no longer improves and then applied to the test set.

Theoretical motivation in least squares

Consider the finite approximation of Neumann series for an invertible matrix A where ${\displaystyle \|I-A\|<1}$:

${\displaystyle \sum _{i=0}^{T-1}(I-A)^{i}\approx A^{-1}}$

This can be used to approximate the analytical solution of unregularized least squares, if γ is introduced to ensure the norm is less than one.

${\displaystyle w_{T}={\frac {\gamma }{n}}\sum _{i=0}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}}$

The exact solution to the unregularized least squares learning problem minimizes the empirical error, but may fail. By limiting T, the only free parameter in the algorithm above, the problem is regularized for time, which may improve its generalization.

The algorithm above is equivalent to restricting the number of gradient descent iterations for the empirical risk

${\displaystyle I_{s}[w]={\frac {1}{2n}}\|{\hat {X}}w-{\hat {Y}}\|_{\mathbb {R} ^{n}}^{2}}$

with the gradient descent update:

${\displaystyle {\begin{aligned}w_{0}&=0\\w_{t+1}&=(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})w_{t}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\end{aligned}}}$

The base case is trivial. The inductive case is proved as follows:

${\displaystyle {\begin{aligned}w_{T}&=(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}}){\frac {\gamma }{n}}\sum _{i=0}^{T-2}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\\&={\frac {\gamma }{n}}\sum _{i=1}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\\&={\frac {\gamma }{n}}\sum _{i=0}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}\end{aligned}}}$

Regularizers for sparsity

Assume that a dictionary ${\displaystyle \phi _{j}}$ with dimension ${\displaystyle p}$ is given such that a function in the function space can be expressed as:

${\displaystyle f(x)=\sum _{j=1}^{p}\phi _{j}(x)w_{j}}$

A comparison between the L1 ball and the L2 ball in two dimensions gives an intuition on how L1 regularization achieves sparsity.

Enforcing a sparsity constraint on ${\displaystyle w}$ can lead to simpler and more interpretable models. This is useful in many real-life applications such as computational biology. An example is developing a simple predictive test for a disease in order to minimize the cost of performing medical tests while maximizing predictive power.

A sensible sparsity constraint is the ${\displaystyle L_{0}}$ norm ${\displaystyle \|w\|_{0}}$, defined as the number of non-zero elements in ${\displaystyle w}$. Solving a ${\displaystyle L_{0}}$ regularized learning problem, however, has been demonstrated to be NP-hard.[6]

The ${\displaystyle L_{1}}$ norm (see also Norms) can be used to approximate the optimal ${\displaystyle L_{0}}$ norm via convex relaxation. It can be shown that the ${\displaystyle L_{1}}$ norm induces sparsity. In the case of least squares, this problem is known as LASSO in statistics and basis pursuit in signal processing.

${\displaystyle \min _{w\in \mathbb {R} ^{p}}{\frac {1}{n}}\|{\hat {X}}w-{\hat {Y}}\|^{2}+\lambda \|w\|_{1}}$

Elastic net regularization

${\displaystyle L_{1}}$ regularization can occasionally produce non-unique solutions. A simple example is provided in the figure when the space of possible solutions lies on a 45 degree line. This can be problematic for certain applications, and is overcome by combining ${\displaystyle L_{1}}$ with ${\displaystyle L_{2}}$ regularization in elastic net regularization, which takes the following form:

${\displaystyle \min _{w\in \mathbb {R} ^{p}}{\frac {1}{n}}\|{\hat {X}}w-{\hat {Y}}\|^{2}+\lambda (\alpha \|w\|_{1}+(1-\alpha )\|w\|_{2}^{2}),\alpha \in [0,1]}$

Elastic net regularization tends to have a grouping effect, where correlated input features are assigned equal weights.

Elastic net regularization is commonly used in practice and is implemented in many machine learning libraries.

Proximal methods

While the ${\displaystyle L_{1}}$ norm does not result in an NP-hard problem, the ${\displaystyle L_{1}}$ norm is convex but is not strictly diffentiable due to the kink at x = 0. Subgradient methods which rely on the subderivative can be used to solve ${\displaystyle L_{1}}$ regularized learning problems. However, faster convergence can be achieved through proximal methods.

For a problem ${\displaystyle \min _{w\in H}F(w)+R(w)}$ such that ${\displaystyle F}$ is convex, continuous, differentiable, with Lipschitz continuous gradient (such as the least squares loss function), and ${\displaystyle R}$ is convex, continuous, and proper, then the proximal method to solve the problem is as follows. First define the proximal operator

${\displaystyle \operatorname {prox} _{R}(v)=\operatorname {argmin} \limits _{w\in \mathbb {R} ^{D}}\{R(w)+{\frac {1}{2}}\|w-v\|^{2}\},}$

and then iterate

${\displaystyle w_{k+1}=\operatorname {prox} \limits _{\gamma ,R}(w_{k}-\gamma \nabla F(w_{k}))}$

The proximal method iteratively performs gradient descent and then projects the result back into the space permitted by ${\displaystyle R}$.

When ${\displaystyle R}$ is the ${\displaystyle L_{1}}$ regularizer, the proximal operator is equivalent to the soft-thresholding operator,

${\displaystyle S_{\lambda }(v)f(n)={\begin{cases}v_{i}-\lambda ,&{\text{if }}v_{i}>\lambda \\0,&{\text{if }}v_{i}\in [-\lambda ,\lambda ]\\v_{i}+\lambda ,&{\text{if }}v_{i}<-\lambda \end{cases}}}$

This allows for efficient computation.

Group sparsity without overlaps

Groups of features can be regularized by a sparsity constraint, which can be useful for expressing certain prior knowledge into an optimization problem.

In the case of a linear model with non-overlapping known groups, a regularizer can be defined:

${\displaystyle R(w)=\sum _{g=1}^{G}\|w_{g}\|_{2},}$ where ${\displaystyle \|w_{g}\|_{2}={\sqrt {\sum _{j=1}^{|G_{g}|}(w_{g}^{j})^{2}}}}$

This can be viewed as inducing a regularizer over the ${\displaystyle L_{2}}$ norm over members of each group followed by an ${\displaystyle L_{1}}$ norm over groups.

This can be solved by the proximal method, where the proximal operator is a block-wise soft-thresholding function:

${\displaystyle \operatorname {prox} \limits _{\lambda ,R,g}(w_{g})={\begin{cases}(1-{\frac {\lambda }{\|w_{g}\|_{2}}})w_{g},&{\text{if }}\|w_{g}\|_{2}>\lambda \\0,&{\text{if }}\|w_{g}\|_{2}\leq \lambda \end{cases}}}$

Group sparsity with overlaps

The algorithm described for group sparsity without overlaps can be applied to the case where groups do overlap, in certain situations. This will likely result in some groups with all zero elements, and other groups with some non-zero and some zero elements.

If it is desired to preserve the group structure, a new regularizer can be defined:

${\displaystyle R(w)=\inf \left\{\sum _{g=1}^{G}\|w_{g}\|_{2}:w=\sum _{g=1}^{G}{\bar {w}}_{g}\right\}}$

For each ${\displaystyle w_{g}}$, ${\displaystyle {\bar {w}}_{g}}$ is defined as the vector such that the restriction of ${\displaystyle {\bar {w}}_{g}}$ to the group ${\displaystyle g}$ equals ${\displaystyle w_{g}}$ and all other entries of ${\displaystyle {\bar {w}}_{g}}$ are zero. The regularizer finds the optimal disintegration of ${\displaystyle w}$ into parts. It can be viewed as duplicating all elements that exist in multiple groups. Learning problems with this regularizer can also be solved with the proximal method with a complication. The proximal operator cannot be computed in closed form, but can be effectively solved iteratively, inducing an inner iteration within the proximal method iteration.

Regularizers for semi-supervised learning

When labels are more expensive to gather than input examples, semi-supervised learning can be useful. Regularizers have been designed to guide learning algorithms to learn models that respect the structure of unsupervised training samples. If a symmetric weight matrix ${\displaystyle W}$ is given, a regularizer can be defined:

${\displaystyle R(f)=\sum _{i,j}w_{ij}(f(x_{i})-f(x_{j}))^{2}}$

If ${\displaystyle W_{ij}}$ encodes the result of some distance metric for points ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$, it is desirable that ${\displaystyle f(x_{i})\approx f(x_{j})}$. This regularizer captures this intuition, and is equivalent to:

${\displaystyle R(f)={\bar {f}}^{T}L{\bar {f}}}$ where ${\displaystyle L=D-W}$ is the Laplacian matrix of the graph induced by ${\displaystyle W}$.

The optimization problem ${\displaystyle \min _{f\in \mathbb {R} ^{m}}R(f),m=u+l}$ can be solved analytically if the constraint ${\displaystyle f(x_{i})=y_{i}}$ is applied for all supervised samples. The labeled part of the vector ${\displaystyle f}$ is therefore obvious. The unlabeled part of ${\displaystyle f}$ is solved for by:

${\displaystyle \min _{f_{u}\in \mathbb {R} ^{u}}f^{T}Lf=\min _{f_{u}\in \mathbb {R} ^{u}}\{f_{u}^{T}L_{uu}f_{u}+f_{l}^{T}L_{lu}f_{u}+f_{u}^{T}L_{ul}f_{l}\}}$

${\displaystyle \nabla _{f_{u}}=2L_{uu}f_{u}+2L_{ul}Y}$

${\displaystyle f_{u}=L_{uu}^{\dagger }(L_{ul}Y)}$

Note that the pseudo-inverse can be taken because ${\displaystyle L_{ul}}$ has the same range as ${\displaystyle L_{uu}}$.

Regularizers for multitask learning

In the case of multitask learning, ${\displaystyle T}$ problems are considered simultaneously, each related in some way. The goal is to learn ${\displaystyle T}$ functions, ideally borrowing strength from the relatedness of tasks, that have predictive power. This is equivalent to learning the matrix ${\displaystyle W:T\times D}$ .

Sparse regularizer on columns

${\displaystyle R(w)=\sum _{i=1}^{D}\|W\|_{2,1}}$

This regularizer defines an L2 norm on each column and an L1 norm over all columns. It can be solved by proximal methods.

Nuclear norm regularization

${\displaystyle R(w)=\|\sigma (W)\|_{1}}$ where ${\displaystyle \sigma (W)}$ is the eigenvalues in the singular value decomposition of ${\displaystyle W}$.

Mean-constrained regularization

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{t=1}^{T}\|f_{t}-{\frac {1}{T}}\sum _{s=1}^{T}f_{s}\|_{H_{k}}^{2}}$

This regularizer constrains the functions learned for each task to be similar to the overall average of the functions across all tasks. This is useful for expressing prior information that each task is expected to share with each other task. An example is predicting blood iron levels measured at different times of the day, where each task represents an individual.

Clustered mean-constrained regularization

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{r=1}^{C}\sum _{t\in I(r)}\|f_{t}-{\frac {1}{I(r)}}\sum _{s\in I(r)}f_{s}\|_{H_{k}}^{2}}$ where ${\displaystyle I(r)}$ is a cluster of tasks.

This regularizer is similar to the mean-constrained regularizer, but instead enforces similarity between tasks within the same cluster. This can capture more complex prior information. This technique has been used to predict Netflix recommendations. A cluster would correspond to a group of people who share similar preferences.

Graph-based similarity

More generally than above, similarity between tasks can be defined by a function. The regularizer encourages the model to learn similar functions for similar tasks.

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{t,s=1,t\neq s}^{T}\|f_{t}-f_{s}\|^{2}M_{ts}}$ for a given symmetric similarity matrix ${\displaystyle M}$.

Other uses of regularization in statistics and machine learning

Bayesian learning methods make use of a prior probability that (usually) gives lower probability to more complex models. Well-known model selection techniques include the Akaike information criterion (AIC), minimum description length (MDL), and the Bayesian information criterion (BIC). Alternative methods of controlling overfitting not involving regularization include cross-validation.

Examples of applications of different methods of regularization to the linear model are:

Model	Fit measure	Entropy measure[4][7]
AIC/BIC	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \|\beta \|_{0}}$
Ridge regression[8]	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \|\beta \|_{2}}$
Lasso[9]	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \|\beta \|_{1}}$
Basis pursuit denoising	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \lambda \|\beta \|_{1}}$
Rudin–Osher–Fatemi model (TV)	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \lambda \|\nabla \beta \|_{1}}$
Potts model	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \lambda \|\nabla \beta \|_{0}}$
RLAD[10]	${\displaystyle \|Y-X\beta \|_{1}}$	${\displaystyle \|\beta \|_{1}}$
Dantzig Selector[11]	${\displaystyle \|X^{\top }(Y-X\beta )\|_{\infty }}$	${\displaystyle \|\beta \|_{1}}$
SLOPE[12]	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \sum _{i=1}^{p}\lambda _{i}|\beta |_{(i)}}$

See also

• Bayesian interpretation of regularization
• Bias–variance tradeoff
• Matrix regularization
• Regularization by spectral filtering
• Regularized least squares
• Lagrange multiplier

Notes

1. Kratsios, Anastasis (2020). "Deep Arbitrage-Free Learning in a Generalized HJM Framework via Arbitrage-Regularization Data". Risks: . doi:10.3390/risks8020040. Term structure models can be regularized to remove arbitrage oppertunities. Cite journal requires |journal= (help)
2. Bühlmann, Peter; Van De Geer, Sara (2011). "Statistics for High-Dimensional Data". Springer Series in Statistics: 9. doi:10.1007/978-3-642-20192-9. ISBN 978-3-642-20191-2. If p > n, the ordinary least squares estimator is not unique and will heavily overfit the data. Thus, a form of complexity regularization will be necessary. Cite journal requires |journal= (help)
3. "Deep Learning Book". www.deeplearningbook.org. Retrieved 2021-01-29.
4. Bishop, Christopher M. (2007). Pattern recognition and machine learning (Corr. printing. ed.). New York: Springer. ISBN 978-0387310732.
5. For the connection between maximum a posteriori estimation and ridge regression, see Weinberger, Kilian (July 11, 2018). "Linear / Ridge Regression". CS4780 Machine Learning Lecture 13. Cornell.
6. Natarajan, B. (1995-04-01). "Sparse Approximate Solutions to Linear Systems". SIAM Journal on Computing. 24 (2): 227–234. doi:10.1137/S0097539792240406. ISSN 0097-5397.
7. Duda, Richard O. (2004). Pattern classification + computer manual : hardcover set (2. ed.). New York [u.a.]: Wiley. ISBN 978-0471703501.
8. Arthur E. Hoerl; Robert W. Kennard (1970). "Ridge regression: Biased estimation for nonorthogonal problems". Technometrics. 12 (1): 55–67. doi:10.2307/1267351.
9. Tibshirani, Robert (1996). "Regression Shrinkage and Selection via the Lasso" (PostScript). Journal of the Royal Statistical Society, Series B. 58 (1): 267–288. MR 1379242. Retrieved 2009-03-19.
10. Li Wang, Michael D. Gordon & Ji Zhu (2006). "Regularized Least Absolute Deviations Regression and an Efficient Algorithm for Parameter Tuning". Sixth International Conference on Data Mining. pp. 690–700. doi:10.1109/ICDM.2006.134.
11. Candes, Emmanuel; Tao, Terence (2007). "The Dantzig selector: Statistical estimation when p is much larger than n". Annals of Statistics. 35 (6): 2313–2351. arXiv:math/0506081. doi:10.1214/009053606000001523. MR 2382644.
12. Małgorzata Bogdan, Ewout van den Berg, Weijie Su & Emmanuel J. Candes (2013). "Statistical estimation and testing via the ordered L1 norm". arXiv:1310.1969 [stat.ME].CS1 maint: multiple names: authors list (link)

References

• Neumaier, A. (1998). "Solving ill-conditioned and singular linear systems: A tutorial on regularization" (PDF). SIAM Review. 40 (3): 636–666. doi:10.1137/S0036144597321909.