Regularized least squares

Regularized least squares (RLS) is a family of methods for solving the least-squares problem while using regularization to further constrain the resulting solution.
RLS is used for two main reasons. The first comes up when the number of variables in the linear system exceeds the number of observations. In such settings, the ordinary least-squares problem is ill-posed and is therefore impossible to fit because the associated optimization problem has infinitely many solutions. RLS allows the introduction of further constraints that uniquely determine the solution.
The second reason that RLS is used occurs when the number of variables does not exceed the number of observations, but the learned model suffers from poor generalization. RLS can be used in such cases to improve the generalizability of the model by constraining it at training time. This constraint can either force the solution to be "sparse" in some way or to reflect other prior knowledge about the problem such as information about correlations between features. A Bayesian understanding of this can be reached by showing that RLS methods are often equivalent to priors on the solution to the least-squares problem.
General formulation.
Consider a learning setting given by a probabilistic space formula_1, formula_2. Let formula_3 denote a training set of formula_4 pairs i.i.d. with respect to formula_5. Let formula_6 be a loss function. Define formula_7 as the space of the functions such that expected risk: 
is well defined. 
The main goal is to minimize the expected risk:
Since the problem cannot be solved exactly there is a need to specify how to measure the quality of a solution. A good learning algorithm should provide an estimator with a small risk.
As the joint distribution formula_5 is typically unknown, the empirical risk is taken. For regularized least squares the square loss function is introduced:
However, if the functions are from a relatively unconstrained space, such as the set of square-integrable functions on formula_12, this approach may overfit the training data, and lead to poor generalization. Thus, it should somehow constrain or penalize the complexity of the function formula_13. In RLS, this is accomplished by choosing functions from a reproducing kernel Hilbert space (RKHS) formula_14, and adding a regularization term to the objective function, proportional to the norm of the function in formula_14:
Kernel formulation.
Definition of RKHS.
A RKHS can be defined by a symmetric positive-definite kernel function formula_17 with the reproducing property:
where formula_19. The RKHS for a kernel formula_20 consists of the completion of the space of functions spanned by formula_21: formula_22, where all formula_23 are real numbers. Some commonly used kernels include the linear kernel, inducing the space of linear functions:
the polynomial kernel, inducing the space of polynomial functions of order formula_25:
and the Gaussian kernel:
Note that for an arbitrary loss function formula_28, this approach defines a general class of algorithms named Tikhonov regularization. For instance, using the hinge loss leads to the support vector machine algorithm, and using the epsilon-insensitive loss leads to support vector regression.
Arbitrary kernel.
The representer theorem guarantees that the solution can be written as:
The minimization problem can be expressed as:
where, with some abuse of notation, the formula_32 entry of kernel matrix formula_20 (as opposed to kernel function formula_34) is formula_35.
For such a function,
The following minimization problem can be obtained:
As the sum of convex functions is convex, the solution is unique and its minimum can be found by setting the gradient w.r.t formula_38 to formula_39:
where formula_41.
Complexity.
The complexity of training is basically the cost of computing the kernel matrix plus the cost of solving the linear system which is roughly formula_42. The computation of the kernel matrix for the linear or Gaussian kernel is formula_43. The complexity of testing is formula_44.
Prediction.
The prediction at a new test point formula_45 is:
Linear kernel.
For convenience a vector notation is introduced. Let formula_12 be an formula_48 matrix, where the rows are input vectors, and formula_49 a formula_50 vector where the entries are corresponding outputs. In terms of vectors, the kernel matrix can be written as formula_51. The learning function can be written as:
Here we define formula_53. The objective function can be rewritten as:
The first term is the objective function from ordinary least squares (OLS) regression, corresponding to the residual sum of squares. The second term is a regularization term, not present in OLS, which penalizes large formula_55 values.
As a smooth finite dimensional problem is considered and it is possible to apply standard calculus tools. In order to minimize the objective function, the gradient is calculated with respect to formula_55 and set it to zero:
This solution closely resembles that of standard linear regression, with an extra term formula_59. If the assumptions of OLS regression hold, the solution formula_60, with formula_61, is an unbiased estimator, and is the minimum-variance linear unbiased estimator, according to the Gauss–Markov theorem. The term formula_62 therefore leads to a biased solution; however, it also tends to reduce variance. This is easy to see, as the covariance matrix of the formula_55-values is proportional to formula_64, and therefore large values of formula_65 will lead to lower variance. Therefore, manipulating formula_65 corresponds to trading-off bias and variance. For problems with high-variance formula_55 estimates, such as cases with relatively small formula_4 or with correlated regressors, the optimal prediction accuracy may be obtained by using a nonzero formula_65, and thus introducing some bias to reduce variance. Furthermore, it is not uncommon in machine learning to have cases where formula_70, in which case formula_71 is rank-deficient, and a nonzero formula_65 is necessary to compute formula_73.
Complexity.
The parameter formula_65
controls the invertibility of the matrix formula_75.
Several methods can be used to solve the above linear system,
Cholesky decomposition being probably the method of choice, since the matrix formula_75 is symmetric and positive definite. The complexity of this method is formula_77 for training and
formula_78 for testing. The cost formula_77 is essentially that of computing formula_80, whereas the inverse computation (or rather the solution of the linear system) is roughly formula_81.
Feature maps and Mercer's theorem.
In this section it will be shown how to extend RLS to any kind of reproducing kernel K. Instead of linear kernel a feature map is considered
formula_82 for some Hilbert space formula_7, called the feature space. In this case the kernel is defined as: The matrix formula_12 is now replaced by the new data matrix formula_85, where formula_86, or the formula_87-th component of the formula_88.
It means that for a given training set formula_90. Thus, the objective function can be written as:
This approach is known as the kernel trick. This technique can significantly simplify the computational operations. If formula_7 is high dimensional, computing formula_93 may be rather intensive. If the explicit form of the kernel function is known, we just need to compute and store the formula_94 kernel matrix formula_95.
In fact, the Hilbert space formula_7 need not be isomorphic to formula_97, and can be infinite dimensional. This follows from Mercer's theorem, which states that a continuous, symmetric, positive definite kernel function can be expressed as:
formula_98
where formula_99 form an orthonormal basis for formula_100, and formula_101. If feature maps is defined formula_102 with components formula_103, it follows that formula_104. This demonstrates that any kernel can be associated with a feature map, and that RLS generally consists of linear RLS performed in some possibly higher-dimensional feature space. While Mercer's theorem shows how one feature map that can be associated with a kernel, in fact multiple feature maps can be associated with a given reproducing kernel. For instance, the map formula_105 satisfies the property formula_104 for an arbitrary reproducing kernel.
Bayesian interpretation.
Least squares can be viewed as a likelihood maximization under an assumption of normally distributed residuals. This is because the exponent of the Gaussian distribution is quadratic in the data, and so is the least-squares objective function. In this framework, the regularization terms of RLS can be understood to be encoding priors on formula_55. For instance, Tikhonov regularization corresponds to a normally distributed prior on formula_55 that is centered at 0. To see this, first note that the OLS objective is proportional to the log-likelihood function when each sampled formula_109 is normally distributed around formula_110. Then observe that a normal prior on formula_55 centered at 0 has a log-probability of the form
where formula_113 and formula_114 are constants that depend on the variance of the prior and are independent of formula_55. Thus, minimizing the logarithm of the likelihood times the prior is equivalent to minimizing the sum of the OLS loss function and the ridge regression regularization term.
This gives a more intuitive interpretation for why Tikhonov regularization leads to a unique solution to the least-squares problem: there are infinitely many vectors formula_55 satisfying the constraints obtained from the data, but since we come to the problem with a prior belief that formula_55 is normally distributed around the origin, we will end up choosing a solution with this constraint in mind.
Other regularization methods correspond to different priors. See the list below for more details.
Specific examples.
Ridge regression (or Tikhonov regularization).
One particularly common choice for the penalty function formula_118 is the squared formula_119 norm, i.e.,
The most common names for this are called Tikhonov regularization and ridge regression. 
It admits a closed-form solution for formula_55:
The name ridge regression alludes to the fact that the formula_124 term adds positive entries along the diagonal "ridge" of the sample covariance matrix formula_71.
When formula_126, i.e., in the case of ordinary least squares, the condition that formula_127 causes the sample covariance matrix formula_71 to not have full rank and so it cannot be inverted to yield a unique solution. This is why there can be an infinitude of solutions to the ordinary least squares problem when formula_127. However, when formula_130, i.e., when ridge regression is used, the addition of formula_124 to the sample covariance matrix ensures that all of its eigenvalues will be strictly greater than 0. In other words, it becomes invertible, and the solution becomes unique.
Compared to ordinary least squares, ridge regression is not unbiased. It accepts little bias to reduce variance and the mean square error, and helps to improve the prediction accuracy. Thus, ridge estimator yields more stable solutions by shrinking coefficients but suffers from the lack of sensitivity to the data.
Lasso regression.
The least absolute selection and shrinkage (LASSO) method is another popular choice. In lasso regression, the lasso penalty function formula_118 is the formula_133 norm, i.e.
Note that the lasso penalty function is convex but not strictly convex. 
Unlike Tikhonov regularization, this scheme does not have a convenient closed-form solution: instead, the solution is typically found using quadratic programming or more general convex optimization methods, as well as by specific algorithms such as the least-angle regression algorithm.
An important difference between lasso regression and Tikhonov regularization is that lasso regression forces more entries of formula_55 to actually equal 0 than would otherwise. In contrast, while Tikhonov regularization forces entries of formula_55 to be small, it does not force more of them to be 0 than would be otherwise. Thus, LASSO regularization is more appropriate than Tikhonov regularization in cases in which we expect the number of non-zero entries of formula_55 to be small, and Tikhonov regularization is more appropriate when we expect that entries of formula_55 will generally be small but not necessarily zero. Which of these regimes is more relevant depends on the specific data set at hand.
Besides feature selection described above, LASSO has some limitations. Ridge regression provides better accuracy in the case formula_140 for highly correlated variables. In another case, formula_141, LASSO selects at most formula_142 variables. Moreover, LASSO tends to select some arbitrary variables from group of highly correlated samples, so there is no grouping effect.
"ℓ"0 Penalization.
The most extreme way to enforce sparsity is to say that the actual magnitude of the coefficients of formula_55 does not matter; rather, the only thing that determines the complexity of formula_55 is the number of non-zero entries. This corresponds to setting formula_146 to be the formula_147 norm of formula_55. This regularization function, while attractive for the sparsity that it guarantees, is very difficult to solve because doing so requires optimization of a function that is not even weakly convex. Lasso regression is the minimal possible relaxation of formula_147 penalization that yields a weakly convex optimization problem.
Elastic net.
For any non-negative formula_150 and formula_151 the objective has the following form:
Let formula_153, then the solution of the minimization problem is described as:
Consider formula_156 as an Elastic Net penalty function.
When formula_157, elastic net becomes ridge regression, whereas formula_158 it becomes Lasso. formula_159 Elastic Net penalty function doesn't have the first derivative at 0 and it is strictly convex 
formula_160 taking the properties both lasso regression and ridge regression.
One of the main properties of the Elastic Net is that it can select groups of correlated variables. The difference between weight vectors of samples formula_161 and formula_162 is given by:
If formula_161 and formula_162 are highly correlated ( formula_167), the weight vectors are very close. In the case of negatively correlated samples ( formula_168) the samples formula_169 can be taken. To summarize, for highly correlated variables the weight vectors tend to be equal up to a sign in the case of negative correlated variables.
Partial list of RLS methods.
The following is a list of possible choices of the regularization function formula_170, along with the name for each one, the corresponding prior if there is a simple one, and ways for computing the solution to the resulting optimization problem.