How to use cross-validation with regularization? I think I understand each of these concepts (cross-validation, regularization) independently, but I'm not quite clear on how they can be put together in practice. 
Loosely speaking, in cross-validation I will train my models on subsets of my data, and then choose the model that performs best on the reserved portion of data. In regularization I will heuristically choose some sort of regularizer function and then try to find the parameter $\lambda$ that gives the best results. Can we use cross-validation to pick $\lambda$? I think each different value of $\lambda$ can be seen as yielding a new model, but then don't we have infinitely many models to choose from?
 A: The procedure for cross-validated regularization parameter selection is the following : 


*

*Discretize your lambdas : $\lambda_0, \lambda_1, ..., \lambda_n$ (for example you may choose $\lambda = 10^{-3}, 3 \times 10^{-3}, 10^-2, ..., 10^3$, but this is up to you.

*Divide your dataset into $n$ subsamples, where $n$ is the number of cross-validation folds.

*For each $\lambda$, compute the cross-validated error when training your model with regularization parameter $\lambda$ (this is the cross-validation part : for each fold, train on all the other folds and compute the error on the reserved fold ; then average out the error).

*Choose the $\lambda$ which gave the lowest cross-validated error (alternatively, choose the smallest value of $\lambda$ within one standard deviation of the lowest cross-validated error if you want to be extra conservative). 

A: You generally do have infinitely many to choose from. There are two approaches to resolving this difficulty.


*

*You can attempt to be very creative and work out mathematics for estimating the full path of models as $\lambda$ varies.  This is only possible in some cases, but when it is, it is a powerful method indeed.  For example the LARS methodology for lasso linear regression is exactly of this type.  It is very beautiful when this works out.


But usually you can't or don't know how to do that, so:


*

*You simply discretize the problem by choosing an appropriate finite sequence of lambdas $\lambda_0 < \lambda_1 < \cdots < \lambda_N$ and working only with those values.  There is still some art to this, as determining what $\lambda_N$ (the maximum) and $\lambda_0$ (the minimum) should be depends on the problem being solved.  You often want to choose $\lambda_N$ to be the least value that collapses the model completely to predicting the average value of the response.  For example, this is the approach taken by the famed glmnet.

A: (Training Error and Test Error) versus (Model Complexity/Capacity) form a U-shaped relationship. In learning a model, there are 2 goals:


*

*Find the optimum on the model complexity axis where the U curve starts to go up again. This happens for the Test Error curve, even though the Training Error curve continues to go down overfitting the training data to the high-complexity model (marching towards interpolation).

*Reduce the gap between the two U curves, meaning, reduce the gap between training error and test error.


(1) is achieved by using cross validation - to find the fine balance between bias and variance
(2) is achieved by using regularization - to bring down the test error U curve closer to the training error curve.
