We study the following three fundamental problems about ridge regression: (1) what is the structure of the estimator? (2) how to correctly use cross-validation to choose the regularization parameter? and (3) how to accelerate computation without losing too much accuracy? We consider the three problems in a unified large-data linear model. We give a precise representation of ridge regression as a covariance matrix-dependent linear combination of the true parameter and the noise. We study the bias of K-fold cross-validation for choosing the regularization parameter, and propose a simple bias-correction. We analyze the accuracy of primal and dual sketching for ridge regression, showing they are surprisingly accurate. Our results are illustrated by simulations and by analyzing empirical data.
This paper presents a theoretical study of ridge regression, focusing on the practical problems of correcting for the bias of the cross-validation based estimate of the optimal regularisation parameter, and quantification of the asymptotic risk of sketching algorithms for ridge regression, both in the p / n -> gamma in (0, 1) regime (n = # data points, p = # dimensions). The authors derive most of their results exploiting their (AFAICT) new asymptotic characterisation of the ridge regression estimator which may be of independent interest. The whole study is complemented by a series of numerical experiments.
I am recommending this paper to be accepted for publication at ICLR. The paper is clearly written, makes several solid theoretical contributions, and recommends a simple and practical bias correction for CV-based estimates of the optimal ridge regulariser. While ICLR is biased towards deep learning focused publications, the work of Belkin, Hsu, Ma, Bartlett, Hastie, Montanari, Rakhlin, Liang and others (apologies to everyone whose name was omitted---it is for the sole reason of brevity) has recently shown that we can learn non-negligible amount about neural networks from study of linear models.
Comments:
- Most of the examples in the paper focus on the regime gamma < 1. Would you expect the observed behaviours to be significantly different when gamma > 1? I am asking specifically because of [1] which has found that the bias of the risk estimate obtained via cross-validation is often most extreme when p >> n, which makes me wonder about what would an experiment like those in fig.2 look like in the p >> n regime?
- I was somewhat confused when I first read the statement of thm.2.1. In particular, the definition of asymptotic equivalence requires (roughly speaking) that any series of projections of the difference between the two random vectors converges to zero a.s. However, within the theorem, you introduce Z without much explanation which confused me because not every Z ~ standard normal would be asymptotically equivalent. I needed to look at the proof to understand how Z is “coupled” with hat(beta), which I think should not be necessary. If possible, I would either say that there exists a (series of) Z (all standard normal) s.t. the asymptotic equivalence holds, or add some other clarification (possibly in the form of a footnote).
- When you are citing a book, please consider citing exact pages or at least chapters/sections (e.g., when citing the exact shortcut from Hastie et al. (2019)).
- In the definition of asymptotic equivalence (starting at the bottom of p.2), did you mean to assume limsup ||w|| < \infty a.s. (or is limsup not needed here)?
References:
[1] Tibshirani, R. J., & Tibshirani, R. (2009). A bias correction for the minimum error rate in cross-validation. The Annals of Applied Statistics, 822-829.