Ridge Regression: Structure, Cross-Validation, and Sketching
Authors: Sifan Liu
Edgar Dobriban
Venue:  (2020)
Keywords: ridge regression
sketching
random matrix theory
cross-validation
high-dimensional asymptotics

Abstract: 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.

Published as a conference paper at ICLR 2020
RIDGE REGRESSION:
STRUCTURE,
CROSS-
VALIDATION, AND SKETCHING
Sifan Liu
Edgar Dobriban
Department of Statistics Stanford University Stanford, CA 94305, USA sfliu@atanford.eer edu
Department of Statistics
University of Pennsylvania
Philadelphia, PA 19104, USA
upenn. edu
ABSTRACT
We study the following three fundamental problems about ridge regression: (I) what the structure of the estimator? (2) how to correctly use crossvaaldattin 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 precise representation of ridge regression 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 regulariza- tion parameter, and propose a simple bias-correction. We analyze the accuracy of primal and dual sketching for ridge regression, showing they surprisingly accurate. Our results are illustrated by simulations and by analyzing empirical data.
INTRODUCTION
Ridge fz-regularized regression is widely used method for prediction and estimation when the data dimension is large compared to the number of datapoints n. This is especially so in problems with many good features, where sparsity assumptions may not be justified. A great deal known about ridge regression. It is Bayes optimal for any quadratic loss in Bayesian linear model where the parameters and noise are Gaussian. The asymptotic properties of ridge have been widely studied (e.g., Tulino & Verdú, 2004; Serdobolskii, 2007: Couillet & Debbah, 2011; Dicker, 2016; Dobriban & Wager, 2018, etc). For choosing the regularization parameter in practice, cross- validation (CV) is widely used. In addition, there is exact shortcut (e.g., Hastie al., 2009, p. 243), which has good consistency properties (Hastie et al., 2019). There is also a lot work on fast approximate algorithms for ridge, e.g., using sketching methods (e.g., el Alaoui & Mahoney, 2015; Chen et al., 2015; Wang et al., 2018; 8; Chowdhury et al., 2018, among others).
Here seek to develop deeper understanding of ridge regression, going beyond existing work in multiple aspects. We work in linear models under a popular asymptotic regime where n, - oo at the same rate (Marchenko & Pastur, 1967; Serdobolskii, 2007: Couillet & Debbah, 2011; Yao al., 2015). In this framework, we develop a fundamental representation for ridge regression, which shows that it is well approximated by linear scaling of the true parameters perturbed by noise. The scaling matrices are functions of the population- covariance of the features. As consequence, we derive formulas for the training error and birianar tradeoff of ridge.
Second, we study commonly used methods for choosing the regularization parameter. Inspired by the observation that CV has bias for estimating the error rate (e.g., Hastie et al., 2009, p. 243), we study the bias of CV for selecting the regularization parameter. We discover surprisingly simple form for the bias, and propose a downward scaling bias correction procedure. Third, we study the accuracy loss of a class of randomized sketching algorithms for ridge regression. These algorithms approximate the sample covariance matrix by sketching or random projection. We show they can be surprisingly accurate, e.g., they sometimes cut computational cost in half, only incurring 5% extra error. Even more, they can sometimes improve the MSE suboptimal regularization parameter is originally used.

---

Published as a conference paper at ICLR 2020
Our work leverages recent results from asymptotic random matrix theory and free probability theory. One challenge in our analysis is to find the limit of the trace tr (Σ1 + Σし 1 >)'/pp where Σ1 and Σn p p independent sample covariance matrices of Gaussian random vectors. The calculation requires nontrivial aspects of freely additive convolutions (e.g.. Voiculescu et al., 1992; Nica & Speicher, 2006).
Our work is connected to prior works on ridge regression in high-dimensional statistics (Serdobol- skii, 2007) and wireless communications (Tulino & Verdú, 2004; Couillet & Debbah, 201 1). Among other related works, El Karoui & Kösters (2011) discuss the implications of the geometric sensitivity of random matrix theory for ridge regression, without considering our problems. El Karoui (2018) and Dicker (2016) study ridge regression estimators, but focus only on the risk for identity covari- ance. Hastie et al. (2019) study "ridgeless" regression, where the regularization parameter tends to zero.
Sketching is an increasingly popular research topic, see Vempala (2005); Halko al. (2011); Ma- honey (2011); Woodruff (2014); Drineas & Mahoney (2017) and references therein. For sketched ridge regression, Zhang et al. 3a;b) study the dual problem in a complementary sinite-sample setting, and their results are hard to compare. Chen et al. (2015) propose algorithm combining sparse embedding and the subsampled randomized Hadamard transform (SRHT), proving relative approximation bounds. Wang al. (2017) study iterative sketching algorithms from an optimization point of view, for both the primal and the dual problems. Dobriban & Liu (2018) study sketching using asymptotic random matrix theory. but only for unregularized linear regression. Chowdhury et al. (2018) propose data-dependent algorithm in light of the ridge leverage scores. Other related works include Sarlos (2006); Ailon & Chazelle (2006); Drineas et al. (2006; 2011); Dhillon et al. (2013); Ma et al. (2015); Raskutti & Mahoney (2016); Gonen et al. (2016); Thanei et al. (2017); Ahfock et al. (2017); Lopes et (2018); Huang (2018).
The structure of the paper is as follows: We state our results on representation. risk, and bias- variance tradeoff in Section 2. We study the bias of cross-validation for choosing the regularization parameter in Section 3. We study the accuracy of randomized primal and dual sketching for both orthogonal and Gaussian sketches in Section We provide proofs and additional simulations in the Appendix. Code reproducing the experiments in the paper are available at https: / /tggttgttttt hiub. com/ fom/liusf15.. htt.://///eieeeeeessss...
RIDGE REGRESSION
We work in the usual linear regression model Y = X3 e, where each row x; of X gxxp is datapoint in p dimensions, and so there are p features. The corresponding element y; of Y E R" its continous response (or outcome). We assume mean zero uncorrelated noise, so EE and Cov [e] o² I.. We estimate the coefficient B RP by ridge regression, solving the optimization problem
B arg min - Y x x,81 SERe ni
2 + 111312
where À > is regularization parameter. The solution has the closed form
(I) We work in a "big data" asymptotic limit, where both the dimension and the sample size n tend infinity, and their aspect ratio converges constant, p/n + 7 E oo). Our results can be interpreted for any n and using p/n n as an approximation.
8 = XxTx/nn + xIp) -
We recall that the empirical spectral distribution (ESD) of p symmetric matrix Σ is the distribu- tion EE= 5x, where \; i = 1,..., P are the eigenvalues of Σ, and 6 is the point mass at z. This is a standard notion in random matrix theory, see e.g.. Marchenko & Pastur (1967); Tulino & Verdú (2004); Couillet & Debbah (201 Yao et al. (2015). The ESD is a convenient tool to summarize all information obtainable from the eigenvalues of matrix. For instance, the trace of Σ is proportional to the mean of the distribution, while the condition number is related to the range of the support. As is common, we will work in models where there is sequence of covariance matrices Σ = Σp- and their ESDs converges in distribution to a limiting probability distribution. The results become simpler, because they depend only on the limit.
2

---

Published as a conference paper at ICLR 2020
By extension, say that the ESD of the n x p matrix X is the ESD of X X/n. We will consider some very specific models for the data, assuming it is of the form X UΣ where U has iid entries of zero mean and unit variance. This means that the datapoints, i.c., the rows of X, have the form 2; = E4/2u, = I,...,P, where u, have iid entries. Then Σ is the "true" covariance matrix of the features, which is typically not observed. These types of models for the data are very common random matrix theory, see the references mentioned above.
Under these models, it is possible to characterize precisely the deviations between the empirical covariance matrix Σ = n - X and the population covariance matrix Σ, dating back to the well known classical Marchenko-Pastne law for eigenvectors (Marchenko & Pastur, 1967), extended to more general models and made more precise, including results for eigenvectors (see e-g.. Tulino & Verdú, 2004; Couillet & Debbah, 2011; 1; Yao et al., 2015, and references therein). This has been used to study methods for estimating the true covariance matrix, with several applications (e.g., Paul & Aue, 2014; Bun et al., 2017). More recently, such models have been used to study high dimensional statistical learning problems, including classification and regression (e.g., Zollanvari & Genton, 2013;
Dobriban & Wager, 2018). Our work falls in this line.
We start by finding precise representation of the ridge estimator. For random vectors un v, of growing dimension, we say uh and Un are deterministic equivalents, if for any sequence of fixed (or random and independent of un vp)) vectors w., such that lim || ll < oo almost surely, we have I (un en)l + O almost surely. We denote this by Un X Un- Thus linear combinations of Un are well approximated by those of Up. This is a somewhat non-standard definition, but it turns need to prior results from random matrix theory such as from
out that it is precisely the (Rubio& & Mestre, 2011).
We extend scalar functions f : IR- + R to matrices in the usual way by functional calculus, applying them to the eigenvalues and keeping the eigenvectors. If M = VAVT is a spectral decomposition of M, then we define ((M) == V ((A)V, where ((A) is the diagonal matrix with entries / (Axz).
For a fixed design matrix X, we can write the estimator as
(5 (S+ X
i E +
However, for a random design, we can find a representation that depends on the true covariance E, which may be simpler when E is simple, e.g., when Σ Ip is isotropic.
Theorem 2.1 (Representation of ridge estimator). Suppose the data matrix has the form U2 where U E R2xp has iid entries of zero mean, unit variance and finite 8 + c-th moment for some > 0, and Σ = Ep E RPxP is a deterministic positive definite matrix. Suppose that n. + oo with p/n 7 O. Suppose the ESD of the sequence of Es converges in distribution to a probability measure with compact support bounded away from the origin. Suppose that the noise is Gaussian, and that 9 = 3p an arbitrary sequence of deterministic vectors, such that lim sup ||,311 < oc.
Then the ridge regression estimator is asymptotically equivalent to random vector with the follow- ing representation:
B(E,)) Z
D!/2'
Here Z ~ NNO. Ip) is a random vector that is stochastically dependent only on the noise e, and A, B are deterministic matrices defined by applying the sealar functions below to E:
A(x, X) (C..I + X)- (c, + c,)xr.
B(x, X) (C.I 2) Cp..
Here Cp = c(n, p, E,, A) the unique positive solution of the fixed point equation
C2 tr [1)
1 1 cp
(2)
This result gives precise representation of the ridge regression estimator. It is sum of two terms: the true coefficient vector 3 scaled by the matrix A(E, A), and the noise vector Z scaled by the matrix B(S E, X). The first term captures to what extent ridge regression recovers the "signal". Morever, the
3

---

Published as a conference paper at ICLR 2020
Y-
0.5
0.5
Blas²
Var
0.4
0.5
0.4
0.1
0.2
0.3
00
1.0
1.5
2.3
2.5
2.0
Figure 1: Ridge regression bias-variance tradeoff. Left: = p/n = 0.2; right: 7 = 2. The data matrix X has iid Gaussian entries. The coefficient 3 has distribution & ~ NNO,, Ip/p), while the noise E Ip).
noise term Z is directly coupled with the noise in the original regression problem, and thus also the estimator. The result would not hold for an independent noise vector Z.
However, the coefficients are not fully explicit, as they depend the unknown population covari- ance matrix Σ, as well as on the fixed-point variable Ep.
Some comments are in order:
Strueture of the proof. The proof is quite non-elementary and relies on random matrix theory. Specifically, it uses the language of the recently developed "calculus of determin- istic equivalents" (Dobriban & Sheng, 2018), and results by (Rubio & Mestre, 2011). A general takeaway that for n not much larger than the empirical covariance matrix E is not a good estimator of the true covariance matrix Σ. However, the deviation of linear functionals Σ, can be quantified. particular, we have
+ = (c
in the sense that linear combinations of the entries of the two matrices close (see the proof for more details).
2. Understanding the resolvent bias factor Cz. Thus, Cp can be viewed resolvent bias factor, which tells us by what factor Σ is multiplied when evaluating the resolvent (L + A1)-1. and comparing it to its naive counterpart (Σ + A/) - It is known that Gp is well defined, and this follows by a simple monotonicity argument, see Hachem et al. (2007); Rubio & Mestre (2011). Specifically, the left hand side of (2) is decreasing in Cp. while the right hand size is increasing in Also é is the derivative of c,. when viewing a function of == -X. An explicit expression is provided in the proof in Section A.1, but is not crucial right now.
Here we discuss some implications of this representation.
For uncorrelated features, Σ = 4,, A, B reduce to multiplication by scalars. Hence, each coor- dinate of the ridge regression estimator is simply scalar multiple of the corresponding coordinate of 3. One can use this to find the bias in each individual coordinate.
Training error and optimal regularization parameter. This theorem has implications for under- standing the training eτror, and optimal regularization parameter of ridge regression. As it stands, the theorem itself only characterizes the behavior og linear combinations of the coordinates of the estimator. Thus, can be directly applied to study the bias EE3(x) - 3 of the estimator. How- ever, it cannot directly be used to study the variance; as that would require understanding quadratic functionals of the estimator. This seems to require significant advances in random matrix theory, going beyond the results of Rubio & Mestre (2011). However, show below that with additional assumptions on the structure of the parameter B, we can derive the MSE of the estimator other ways.

---

Published as a conference paper at ICLR 2020
We work in random-effect, model, where the p-dimensional regression parameter is random, each coefficient has zero mean E,; = O, and is normalized so that Var3, = a²/p. This ensures that the signal strength @|| a² is fixed for any p. The asymptotically optimal À in this setting is always X = ya² 2 /a2 see e.g., Tulino & Verdú (2004); Dicker (2016); Dobriban & Wager (2018). The ridge regression estimator with À pa² (no²) ) is the posterior mean of B3 when and normal random variables.
For distribution F, define the quantities
0,(2)= - (Ir X)' dF,
(
(i = 1,,,.....) These are the moments of the resolvent and its derivatives (up to constants). We use the following loss functions: mean squared estimation error: Mß) = E 3112 and residual or training enror: R(()- E [ -
Theorem 2.2 (MSE and training enror of ridge). Suppose 3 has iid entries with E3; O, Var [8:] /²/p. p.. = ... and 3 independent of X and E. Suppose X an arbitrary n x p matrix and p. and the ESD of X converges weakly to a deterministic distribution F as n.p + oo and p/n + n.. Then the asymptotic MSE and residual error of the ridge regression estimator 3(A) has the form
depending
lim M({(A)) = a² a²2202 + y0² -182],
(3)
R-00
lim R(((A)) a²x2 102] 02 [1 71 101 A²02)]
Bias-variance tradeoff. Building on this, we can also study the bias-variance tradeoff of ridge regression. Qualitatively, large À leads to more regularization, and decreases the variance. However, it also increases the bias. Our theory allows us to find the explicit formulas for the bias and variance as function of X. See Figure I for plot and Sec. A.3 for the details. As far as we know, this is one of the few examples of high-dimensional asymptotic problems where the precise form of the bias and variance can be evaluated.
varianer tradeoff at optimal X = 770///2// (see Figure 6) This can be viewed as the "pure" effect of dimensionality ertics. The variance first increases, then decreases with y. In the "classical" low-dimensional case, most of the risk is due to variance, while in the "modern" high-ddmensiioal case, most of it is due to bias. This consistent with other phenomena proportional- between population and sample eigenvalue distributions is asymptotically deterministic (Marchenko & Pastur, 1967).
the problem, keeping all other parameters fixed, and has intriguing prop-
asymptotics, e.g.. that the map
Future applications. This fundamental representation may have applications important statistical inference questions. For instance, inference on the regression coefficient / and the noise variance o² are important and challenging problems. Can we use our representation develop debiasing techniques for this task? This will be interesting to explore in future work.
CROSS VALIS-VALI
How can we choose the regularization parameter? In practice, cross-validation (CV) is the most popular approach. However, it is well known that CV has a bias for estimating the envor rate, because uses a smaller number of samples than the full data size (e.g.. Hastie et al., 2009, p- 243). In this section, study related questions, proposing bias-correction method for the optimal regularization parameter. This is closely connected to the previous section, because relies on the same random-effects theoretical framework. In fact, our conclusions here direct consequence of the properties of that framework.
Setup. Suppose we split the datapoints (samples) into K equal-sized subsets, each containing 74 n/K K samples. We use the k-th subset (X,,, Yx) as the validation set and the other K subsets (X -k, Y-k), with total sample size n. (K 1)m/ K the training set. We find the ridge
5

---

Published as a conference paper at ICLR 2020
MSD CV
Flight CV
Test
Test
0.24
CV min 0.849
CV min 0.145
0.142
Test arror min 0.848
Test error min 0.135
Theary 0.851
CV toost arron
orrorbar
CV 0.00
CV errorhar
0.20
0.10
0.34
D1024 0.038
Figure 2: Left: Cross-validation the Million Song Dataset (MSD, Bertin-Mahieux et al., 2011). For the error bar, we take n = 1000, = 90, K = 5, and average over 90 different sub-datasets. For the test error, we train on 1000 training datapoints and fit on 9000 test datapoints. The debiased À reduces the test error by 0.00024, and the minimal test error is 0.8480 Right: Cross-validation on the flights dataset Wickham (2018). For the error bar, we take = 300, p= 21, K 5, and average over 180 different sub-datasets. For the test error, we train on 300 datapoints and fit 27000 test datapoints. The debiased reduces the test error by 0.0022, and the minimal test error is 0.1353.
regression estimator 3_k, i.e.
a (XI+X= + m1)p)) -X, Y_
The expected cross-validation error is, for isotropic covariance, i.c., E I,
K V (2)12())l1/mm) = =0² 2 + +E [13= -9113]
= =CA)) =
K
Bias CV. When n, tend to infinity so that p/n - 7 > O, and in the random effects model with E,; 0, Var3; a² /p described above, the minimizer of CV()) tends to X 500 /a", where y is the limiting aspect ratio of X-k, i.c. 7 = >K/(K 1). Since the aspect ratios of X_ and X differ, the limiting minimizer of the vross-validation estimator of the test error is biased for the limiting minimizer of the actual test error, which is X = /a2
Bias-correction. Suppose we have found Åz the minimizer of (V()). Afterwards, we usually refit ridge regression on the entire dataset, i.e., find
0(x²) = (X X x'n
Based on our bias calculation, we propose to use bias-corrected parameter
X := K -
K
So if we use 5 folds, we should multiply the CV-optimal À by 0.8. We find it surprising that this theoretically justified bias-correction does not depend on any unknown parameters, such as 3, a², p. o² While the bias of CV is widely known, we are not aware that this bias-correction for the regularization parameter has been proposed before.
Numerical examples. Figure 2 shows on two empirical data examples that the debiased estima- tor gets closer to the optimal than the original minimizer of the CV. However, this case does not significantly improve the test error. Simulation results in Section A.4 also show that the bias-correction correctly shrinks the regularization parameter and decreases the test error. We also consider examples where p (i.e., 7 1), because this is setting where it is known that the bias of CV can be large (Tibshirani & Tibshirani, 2009). However, in this case, we do not see a significant improvement.
Extensions. The same bias-corrottion idea also applies to train-test validation. In addition, there special fast "short-cut" for leave-one-out cross-validation in ridge regression (e.g.. Hastie al.,

---

Published as a conference paper at ICLR 2020
2009, p. 243), which has the same cost ridge regression. The minimizer converges to X (Hastie et al., 2019). However, we think that the bias-correction idea is still valuable, as the idea applies beyond ridge regression: CV selects regularization parameters that too large. See Sec- tion A.5 for more details and experiments comparing different ways of choosing the regularization parameter.
SKETCHING
A final important question about ridge regression is how to compute it in practice. In this section, study that problem in the same high-dimensional model used throughout our paper. The computa- tion complexity of ridge regression, Ompp pi)(n.p)), can be intractable in modern large-scale data analysis. Sketching is popular approach to reducing the time complexity by reducing the sample size and/or dimension, usually by random projection or sampling (e.g. Mahoney, 2011; Woodruff, 2014: Drineas & Mahoney. 2016). Specifically, primal sketching approximates the sample covari- ance matrix X X/n by X I.X/n, where I. is an m x n sketching matrix, and m < n. is chosen as a suitable random matrix, then this can still approximate the original sample covariance matrix. Then the primal sketched ridge regression estimator is
Bp = (x L LX/n M1p) X Y/nn.
(5)
Dual sketching reduces 2, instead. An equivalent expression for ridge regression is B '
n n-xx (xx) /n+ + Ar.) ' 'Y. Y. Dual sketched ridge regression reduces the computation cost of the Gram matrix XXT, approximating it by X RR X" for another sketching matrix R E Rxxd (d < p), so
= (XRR X /n + Y/n.
The sketching matrices R and L are usually chosen random matrices with iid entries (e.g., Gaus- sian ones) or as orthogonal matrices. In this section, we study the asymptotic MSE for both or- thogonal (Section 4.1) and Gaussian sketching (Section 4.2). We also mention full sketching, which performs ridge after projecting down both X and Y. In section A, we find its MSE. However, the other two methods have better tradeoffs, and we can empirically get better results for the same computational cost.
4.1 ORTHOGONAL SKETCHING
First we consider primal sketching with orthogonal projections. These can be implemented by subsampling, Haar distributed matrices, subsampled randomized Hadamard transforms (Sarlos, 2006). We recall that the standard Marchenko-Pasiie (MP) law is the probability distribution which is the limit of the ESD of X X/n, when the n p matrix X has iid standard Gaussian entries, and n. + Do so that p/n + > O, which has an explicit density (Marchenko & Pastur, 1967; Bai & Silverstein, 2010).
Theorem 4.1 (Primal orthogonal sketching). Suppose 3 has iid entries with E3 O. Var [B.] = a²2pp /p, i == 1,...., and (3 is independent of X and e. Suppose X has iid standard normal entries.
We compute primal sketched ridge regression (5) with m orthogonal matrix L (m n, LL = =Im). Let n, p and m tend to infinity with p/n + E oc) and m/n + & E (0, 1). Then the MSE of (x) has the limit
1A+ 1)2 + (11 [))
7 ( 02
50i (2.2) (A+ - -1)02 (7 >
M()) a
+ 702
2
E
where (,(7,)) f(x +) (F) and F,, is the standard Marchenko-Paste law with aspect ratio
Structure of the proof. The proof is in Section A.6, with explicit formulas in Section 1. The 0: are related to the resolvent of the MP law and its derivatives. In the proof, we decompose the
7

---

Published as a conference paper at ICLR 2020
Primal sketching MSE
Primal sketching bias and variance
1.00
Theary
16-
Bias
275
Simulaaion
Var
2.50
(SE(L,J/MEEI
10
2.60
1.90
4-
2
100
5
Figure 3: Primal orthogonal sketching with = 500, 7 = 1.5, a 3, 1. Left:
MSE of primal sketching normalized by the MSE of ridge regression. The error bar is the standard deviation over 10 repetitions. Right: Bias and variance of primal sketching normalized by the bias and variance of ridge regression, respectively.
MSE the sum of variance and squared bias, both of which further reduce the traces of certain random matrices, whose limits are determined by the MP law F, and x. The two terms on the RHS of Equation (7) are the limits of squared bias and variance, respectively. There is an additional key step in the proof, which introduces the orthogonal complement Ta of the matrix I. such that T. 1 L.TT, L = Ja. which leads to some Gaussian random variables appearing in the proof, and simplifies calculations.
Simulations. simulation Figure 3 (left) shows a good match with our theory. It also shows that sketching does not increase the MSE too much. In this case, by reducing the sample size to half the original one, we only increase the MSE by a factor of 1.05. This shows sketching can be very effective. We also in Figure (right) that variance is compromised much more than bias.
Robustness to tuning parameter. The reader may wonder how strongly this depends on the choice of the regularization parameter A. Perhaps ridge regression works poorly with this X. so sketching cannot worsen too much? What happens we take the optimal X instead of a fixed one? In experiments in Section A.12 show that the behavior is quite robust the choice of regularization parameter.
The next theorem states result for dual orthogonal sketching.
Theorem 4.2 (Dual orthogonal sketching). Under the conditions of Theorem 4.1, we compute the dual sketched ridge regression with an orthogonal p d sketching matrix R (d & p. R R Ta). Let n, and go infinity with p/n + 7 00) and d/n - Ç (0,7). Then the MSE of Ba(A) has the limit
a
1--1=A- (7 o (O - - (A+5S-))B((
where (1- (()=))/) and Fş is the standard Marchenko-Paste law.
Proof structure and simulations. The proof in Section A.7 follows similar path to the previous one. Here 0, comes in because of the companion Stieltjes transform of MP law. The simulation results shown in Figure 11 agrees well with our theory. They are similar to the ones before: sketching has favorable properties, and the bias increases less than the variance.
Optimal tuning parameters. For both primal and dual sketching, the optimal regularization pa- rameter minimizing the MSE seems analytically intractable. Instead, in our experiments, based on a binary search. Since this is one-dimensional problem, there are no numerical issues. See Figure 13 in Section 1.1..3.
numerical approach
8

---

Published as a conference paper at ICLR 2020
Relative efficiency of marginal regression
Gaussian dual sketch
y= y=
40
Theory
173
No sketching
Relative efficiency
y=3
588
+
Simulation
3.6
Blas"
3.4
3.2
3.0
2.2
2.5
SNR
din
Figure 4: Left: Ratio of optimal MSE of marginal regression to that of optimally tuned ridge regres- sion, for three values of 7 p/n, as a function of the SNR a²/0². Right: Gaussian dual sketch when there is no noise. 7 0.4, a 1, = (both for original and sketching). Standard error over 50 experiments.
4.1.1 EXTREME PROJECTION MARGINAL REGRESSION
It is of special interest to investigate extreme projections, where the sketching dimension is much reduced compared to the sample size, so m < n. This corresponds to This can also be viewed as scaled marginal regression estimator, i.e., 3 x X For dual sketching, the same case can be recovered with Ç 0. Another interest of studying this special case is that the formula for MSE simplifies a lot.
Theorem 4.3 (Marginal regression). Under the same assumption Theorem 4.1. let 0. Then the form of the MSE is M()) = |a² [(>- 1)² +7] + o2'1/X2. Moreover, the op- timal X" that minimizes this equals 702 2a2 + + and the optimal MSE is M(A*) = to²1).
a² (1 - a22
The proof is in Section A.8. When is the optimal MSE of marginal regression small? Compared to the MSE of the zero estimator a², is small when 7(02/(r /a² + we compare marginal and ridge regression for different aspect ratios and SNR. When the signal to noise ratio (SNR) a² a²/o" /02 is small or the aspect ratio 7 is large, marginal regression does not increase and ? 0.7, the marginal MSE is 1 1/2.4 ze 0.58. The optimal ridge MSE is about 0.52, so their ratio is only ca. 0.58/0.33 = 1.1. work well.
1)= + +1
large. In Figure (left),
the MSE much. As concrete example, if we take a²
It seems quite surprising that simple-me simple-minded method like marginal regression However, the reason is that when the SNR is small, we cannot expect ridge regression to have good performance. Large Y also be interpreted small SNR, where ridge regression works poorly and sketching does not harm performance too much.
4.2 GAUSSIAN SKETCHING
In this section, we study Gaussian sketching. The following theorem states the bias of dual Gaussian sketching. The bias is enough to characterize the performance in the high SNR regime where a/a oo, and we discuss the extension low SNR after the proof.
Theorem 4.4 (Bias of dual Gaussian sketch). Suppose X is an n. X standard Gaussian random matrix. Suppose also that R a p matrix with i.i.d. NOO,, 1/d) entries. Then the bias of dual sketch has the expression Bias (Ba) = a² + a2277 [m'(2) 2m(=)) Ia=o: where m is a function described below, and m' mz) denotes the derivative of w.r.t. Below, we use the branch of the square root with positive imaginary part.
The function m is characterized by its inverse function, which has the explicit formula m -1()
1/(1 + =/{] by v(r 1)2 AAz)/(2)) for complex with positive imaginary part.
9

---

Published as a conference paper at ICLR 2020
About the proof. The proof is in Section Ae mention that the same result holds when the matrices involved have iid non-Gaussian entries, but the proof is more technical. The current proof is based on free probability theory (e.g., Voiculescu et al., 1992; Hiai & Petz, 2006; Couillet & Debbah, 201 The function m is the Stieltjes transform of the free additive convolution of a standard MP law FI/E and a scaled inverse MP law 1/7- F1/7 (see the proof).
Numeries. To evaluate the formula, we note that m - (m))) Also, (0)/0dd equals 1/(dm-(yy) /ddylymm()) the reciprocal of the derivative of m evaluated m0) We use binary search to find the numerical solution. The theoretical result agrees with the simulation quite well, see Figure 4.
m(0) is root of m-
Somewhat unexpectedly, the MSE of dual sketching can be below the MSE of ridge regression, see Figure 4. This can happen when the original regularization parameter is suboptimal. As d grows, the MSE of Gaussian dual sketching converges to that of ridge regression.
We have also found the bias of primal Gaussian sketching. However, stating the result requires free probability theory, and so we present in the Appendix, see Theorem A.1. To further validate our results, we present additional simulations in Sec. A.12, for both fixed and optimal regularization parameters after sketching. A detailed study of the computational cost for sketching in Sec. A.13 concludes, expected, that primal sketching can reduce cost when p < while dual sketching can reduce it when p > n, and also provides a more detailed analysis.
ACKNOWLEDGMENTY
The authors thank Ken Clarkson for helpful discussions and for providing the reference Chen et al. (2015). ED was partially supported by NSF BIGDATA grant IIS 1837992. SL. was partially sup- ported by a Tsinghua University Summer Research award. A version of our manuscript is available on arxiv at ht https::///// /ttps///axxvvvvia orgg abs 1910. 02373.
REFERENCES
Daniel Ahfock, William J Astle, and Sylvia Richardson. Statistical properties sketching algorithms. arXiv preprint arXiv: /006. 01117706666666 03665, 2017.
Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson-lindenstrane transform. In Proceedings of the thirty-eighth annual ACM symposium Theory of computing, pp. 557-563. ACM, 2006.
Greg Anderson, Alice Guionnet, and Ofer Zeitouni. An Introduction to Random Matrices. Number 118.
Cambridge University Press, 2010.
Theodore W Anderson. An Introduction to Multivariate Statistical Analysis. Wiley New York, 2003. Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices. Springer Series in Statistics. Springer, New York, 2nd edition, 2010.
Thierry Bertin-Mahiin Mahieuxx Daniel P.W. Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Proceedings of the 12th International Conference Music Information Retrieval (ISMIR 2011), 2011.
Joel Bun, Jean- Philippe Bouchaud. and Mare Potters. Cleaning large correlation matrices: tools from random
matrix theory. Physics Reports, 166:1-109, 2017.
Shouyuan Chen, Yang Liu, Michael R Lyu, Irwin King, and Shengyu Zhang. Fast relative-error approximation
algorithm for ridge regression. In UAL. pp. 201-210, 2015.
Agniva Chowdhury, Jiasen Yang, and Petros Drineas. An iterative, sketching- framework for ridge re- gression. In International Conference on Machine Learning, pp. 988-997, 2018. Romain Couillet and Merouane Debbah. Random Matrix Methods for Wireless Communications. Cambridge University Press, 2011.
Paramveer Dhillon, Yichao Lu, Dean Foster, and Lyle Ungar. New subsampling algorithms for fast least squares regression. In Advances in neural information processing systems, pp. 360-368, 2013.
Lee H Dicker. Ridge regression and asymptotic minimax estimation over spheres of growing dimension. Bernoulli, 22(1):1133 2016. Edgar Dobriban and Sifan Liu. new theory for sketching in linear regression. arXiv preprint
arXiv: /xX0:08/00006089 NewrlPS 2019, 2018.
Edgar Dobriban and Yue Sheng. Distributed linear regression by averaging. arXiv preprint 1110v01110.00411.
2018.
Edgar Dobriban and Yue Sheng. One-shot distributed ridge regression in high dimensions. arXiv preprint
htt::/903.09322 2019.
Edgar Dobrihan and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classifi-
cation. The Annals of Statistics, 46(1):247-279, 2018.
10

---

Published as a conference paper at ICLR 2020
Petros Drineas and Michael W Mahoney. RandNLA: randomized numerical linear algebra. Communications of ACM, 59(6):80-90 90, 2016.
Petros Drineas and Michael W Mahoney. Lectures on randomized numerical linear algebra. arXiv preprint
arXiv:/712.088800 2017.
Petros Drineas, Michael W Mahoney, and Muthukrishnan. Sampling algorithms for I 2 regression and ap- plications. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp.
1127-1136. Society for Industrial and Applied Mathematics, 2006.
Petros Drineas, Michael W Mahoney, S Muthukrishnan, and Tamás Sarlós. Faster least squares approximation.
Numerische mathematik, 1 17(22)219-249, 2011.
Ahmed Alaoui and Michael W Mahoney. Fast randomized kemnel ridge regression with statistical guarantees. In Advances in Neural Information Procesing Systems, pp. 775-783, 2015.
Noureddine EI Karoui. On the impact of predictor geometry the performance on nigh-dinensionl ridge- regularized generalized robust regression estimators. Probability Theory and Related Fields, 170( 1-2):955 175, 2018.
Noureddine EI Karoui and Holger Kösters. Geometric sensitivity of random matrix results: consequences for shrinkage estimators of covariance and related statistical methods. arXiv preprint arXiv: 10.. 2011 1. Alon Gonen, Francesco Orabona, and Shai Shalev-Shwarte Solving ridge regression using sketched precondi- tioned svrg. In International Conference on Machine Learning, pp. 1397-1405, 2016.
Walid Hachem, Philippe Loubaton, and Jamal Najim. Deterministic equivalents for certain functionals of large random matrices. The Annals of Applied Probubility. 17(3):875-930, 2007.
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, (vview,532):2277223 53(2):217-288, 2011. Trevor Hastic, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning. Springer series in
statistics, 2009.
Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high-dimensional ridge-
less least squares interpolation. arXiv preprint 1rXiv:1903. 08566, 2019.
Fumio Hiai and Dénes Petz. The semicircle law, free random variables and entropy. Number 77. American Mathematical Soc., 2006.
Zengfeng Huang. Near optimal frequent directions for sketching dense and sparse matrices. In International
Conference on Machine Learning, pp. 2053-2066 2018,
Miles E Lopes, Shusen Wang, and Michael W Mahoney. Error estimation for randomized least-squares algo- rithms via the bootstrap. arXiv preprint arXiv: 08001, 2018.
Ping Ma, Michael W Mahoney, and Bin Yu. A statistical perspoctive on algorithmic leveraging. The Journal of Machine Learning Research, 16(1))861-911, 2015.
Michael W Mahoney. Randomized algorithms for matrices and data. Foundations and Trends Machine Learning, 3()): 2011.
Vladimir A Marchenko and Leonid A Pastur. Distribution of eigenvalues for some sets of random matrices.
Mat. Sh., 117(4)5507-336 1967.
RobbJ J Muirhead. Aspects of multivariate statistical theory, volume 197. John Wiley & Sons. 2009. Alexandru Nica and Roland Speicher. Lectures on the combinatorics free probability, volume 13. Cambridge
University Press, 2006.
Debashis Paul and Alexander Aue. Random matrix theory in statistics: A review. Journal of Statistical Planning
and Inference, 150:1-29, 2014.
Garvesh Raskutti and Michael W Mahoney. A statistical perspective on randomized sketching for ordinary least-squares. The Journal of Machine Learning Research, 17(1):7008-7536 2016.
Francisco Rubio and Xavier Mestre. Spectral convergence for general class of random matrices. Statistics & Probability Letters, (5):)9592-66 -022, 2011.
Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pp. 143-152, IEEE, 2006.
Vadim Ivanovich Serdobolskii. Multiparametric Statistics. Elsevier, 2007.
Gian-Andrea Thanci, Christina Heinze, and Nicolai Mcinshausen. Random projections for large-scale regres-
sion. In Big and complex data analysis, pp. 51-68. Springer, 2017.
Ryan J Tibshirani and Robert Tibshirani. bias correction for the minimum error rate in cross-validation. The Annals of Applied Statistics, pp. 822-829, 2009.
Antonio M Tulino and Sergio Verdú. Random matrix theory and wireless communications. Communications
and Information theory, 1(1):1 182, 2004.
Santosh S Vempala. The random projection method, volume 65. American Mathematical Soc., 2005, Dan V Voiculescu, Ken J Dykema, and Alexandru Nica. Free random variables. Number 1. American Mathe- matical Soc., 1992.
Jialei Wang, Jason Lee, Mehrdad Mahdavi, Mladen Kolar, and Nathan Srebro. Sketching meets random projection in the dual: A provable recovery algorithm for big and high-dimensional data. Electronic Journal of Statistics, 11())489644944 2017.
Shusen Wang, Alex Gittens, and Michael W Mahoney. Sketched ridge regression: Optimization perspective, statistical perspective, and model averaging. Journal of Machine Learning Research, 18:1-50 2018.
11

---

Published as a conference paper at ICLR 2020
Hadley Wickham. nyeflights13: Flights that Departed NYC 2013, 2018.
URL https:/ //CAN.
R-pro ject wwt.oo////aaaa ptspppckaae-nyccliggheee
package version 1.0.0.
David P Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends in Theoretical
Computer Science, 10(1-2):1-157, 2014.
Jianfeng Yao, Zhidong Bai, and Shurong Zheng. Large Sample Covariance Matrices and High-Dimensiones
Data Analysis. Cambridge University Press, New York, 2015.
Lijun Zhang. Mchrdad Mahdavi, and Rong Jin. Linear convergence with condition number independent access of full gradients. In Advances in Neural Information Processing Systems, pp. 980-9880 2013a.
Lijun Zhang, Mehrdad Mahdavi, Rong Jin, Tianbao Yang. and Shenghuo Zhu. Recovering the optimal solution by dual random projection. Conference on Learning Theory, pp. 135-157, 2013b.
Amin Zollanvari and Marc G Genton. On Kolmogorov asymptotics of estimators the misclassification eroor rate in linear discriminant analysis. Sankhya A, 75(2):300- 326, 2013.
A
APPENDIX
A.1 PROOF OF THEOREM 2.1
If p/n - 7 and the spectral distribution of Σ converges to H, we have by the general Marchenko- Pastur (MP) theorem of Rubio and Mestre (Rubio & Mestre, 2011), that
{ + (c,
where cp == c(n,p, E, A) is the unique positive solution of the fixed point equation
c S2 ur [E(
Here, using the terminology of the calculus of deterministic equivalents (Dobriban & Sheng, 2018), two sequences of (not necessarily symmetric) equivalent, and we write
matrices A,, B, of growing dimensions are
An Bn
if Lo tr (A,, Bn) 0 almost surely, for any sequence On of (not necessarily symmet- ric) n X n deterministic matrices with bounded trace norm, i... such that lim sup ||Culler < oo (Dobriban & Sheng. 2018). Informally, linear combinations of the entries of An can be approxi- mated by the entries of B,.
We start with
X (XB+E)
8= X 112)
X/- A1p) X X X1,)
n
= (5 + 1,) - + (5. X,) X
Then, by the general MP law written in the language of the calculus of deterministic equivalents
( = 1p- X A1p)~
M) = AI)-
By the definition of equivalence for vectors,
+ +
We note a subtle point here. The rank of the matrix M = ( -1 is at most n, and so can be full rank matrix. not full rank matrix when < p. In contrast, +.E(EE+AAT Therefore, for the vectors in the null space of E, which is also the null space of X, we certainly have that the two sides are not equal. However, here we assumed that the matrix X is random, and so its null space a random max(p n, 0) dimensional linear space. Therefore, for any fixed vector 3, the random matrix M will not contain it in its null space with high probability, and so there is no contradiction.
We should also derive asymptotic equivalent for
X
S
AIp)
12

---

Published as a conference paper at ICLR 2020
of 3=0.2=3000
Theory Simulation
0--
Figure 5: Simulation for ridge regression. We take n 1000, À = 0.3. Also, X has iid (0.,) 1) entries, 3, ~nd (0, /p), miid W(0,²²), with a 3, a 1. The standard deviations are over 50 repetitions. The theoretical lines are plotted according to Theorem 2.2. The MSE is normalized by the norm of 3.
Suppose we have Gaussian noise, and let Z N/(0, Ip). Then can write
X
= ( + AIp) -81/2 oZ
n//2"
So the question reduces to finding a deterministic equivalent for h(ā), where h(x) = (x + A)-2xx Note that
= (x
A(x + X)-
By the calculus of determinstic equivalents: the limit of the second part was recently calculated in (Dobriban & Sheng, 2019). This used the so-called "differentiation rule" of the calculus of deterministic equivalents to find
Moreover, fortunately
{) x -1- c)
The derivative = /z has been found in Dobriban & Sheng (2019), in the proof of Theorem 3.1, part 2b. The result is (with 7pp p/n, Hp the spectral distribution of E, and T random variable distributed according to Hp))
T 6 -1 + 2p2E H, (2)2
1p Bp (2)-
T
So, find the final answer
Mc - 6,2).
A (1
A.2
RISK ANALYSIS
Figure 5 shows simulation result. We see a good match between theory and simulation.
A.2.1 PROOF OF THEOREM 2.2
Proof.
The MSE of 9 has the form
E B -112 bias? 82.
where
[x X/n X/Txn++Alp x xx/nn8 - -8/
bias =E
82 = -0
X/xx//n X/n [X
A1p) n- x
13

---

Published as a conference paper at ICLR 2020
We assume that X has iid entries of zero mean and unit variance, and that E3 0, Var [8] a² /ppp. As p/n + r as n goes to infinity, the ESD of X X converges to the MP law F.. So we have
bias = x//nxx/nn-)
X/n +
$
X/n xr/ +Xp) -91 + a²22² ʃ
1 (o () 1\2 (F)())))
= -
and
0²
[r((x X/n AZ))
11) 2 xTx]
n²
0²
[tr((X X/n++ NT) -
-x(x x/n XTp) "]] (x+ ( dz)
72
/
x x dz,(x) - /
o2y
Denoting (7)
- [x+x)7 (FF.( (z), then
AMSE(3) = a²220 + 70? - A02].
For the standard Marchenko-Pastee law (i.e., when E Ip), we have the explicit forms of 01 and 02. Specifically,
/
1 dFx(z)=
1 2(1 + A)
2
01
+
22 VFX
x x+ A
x7
where
1
(VT+ 1 x + V /VV+ V
1 1+>12=
22-4 4
2
It is known that the limiting Stieltjes transform mF == my of E has the explicit form (Marchenko
& Pastur, 1967):
1) (=+
-=+7-- 1)2 427
m, (2)
-227
As usual in the area, we use the principal branch of the square root of complex numbers. Hence 01 ( Also 22y
02(7, = ʃ
1
dF,(z)= dF,(z)= d
dd x + X (x)
(x + ))2
d
1 d 22
01
dd
722
VF dd A
(VT
L+ v
+ ++1
1
A X+
7x2
2
2
72
WV++ 4
X2
For the residual,
1 Y x31111
-²>2-- trl(xT X/n+ + +1,) -X
- X/n -X A1p $9
E
71
p
22 1 (Ir((t) - 2ur (XT x/n X1,) (xTxxxXxr xTx/n+ ( (xTx/=+A11)) x xx/x))
14

---

Published as a conference paper at ICLR 2020
Next,
1 E
tr (x*x X/n + x1p) xxxxxxxx xxxx/))
=E
[
[
-A
X/n XXXxXXXX+xtx Alp) -1)
p
P
-1-2 2201 -2202.
Therefore
E
Y x311
22220101 - A02] + 2 2011 +(1 2201 + +x202)
= a222981 - 182) + 7(1 + A01 - -1282)
A.3
BIAS- VARS-VARIANCE TRADEOFF
The limiting MSE decomposes into a limiting squared bias and variance. The specific forms of these
bias a²
X (a + x\2 dl (2),
var =0²²
/
x (or ))2
dF, (x))
See Figure I for a plot. We can make several observations.
1. The bias increases with X, starting out at zero for x 0 (linear regression), and increasing to a² as A - oo (zero estimator).
2. The variance decreases with from y0² f /d=1 to zero.
3. In the setting plotted the figure, when a² and o² are roughly comparable, there are additional qualitative properties
investigate. When y is small, the regularization parameter À influences the bias more strongly than the variance (i.e., the derivative of the normalized quantities in the range plotted is generally larger for the normalized squared bias). In contrast when 7 is large, the variance is influenced more.
Next consider how bias and variance change with y the optimal X = 702/0² This can be viewed as the "pure" effects of dimensionality on the problem, keeping all other parameters fixed. Ineed, a² o² can be viewed as the signal-to-noise ratio (SNR), and is fixed. This analysis allows us to study for the best possible estimator (ridge regression, a Bayes estimator), behaves with the dimension. We refer Figure 6, where we make some specific choices of and a.
1. Clearly the overall risk increases, as the problem becomes harder with increasing dimen- sion. This is in line with our intuition.
2. The classical bias-variance tradcoff can be summarized by the equation
bias? 2 (X) + var(A)= > M M*
where we made explicit the dependence of the bias and variance on X, and where Ma ?) is the minimum MSE achievable, also known as the Bayes error, for which there are explicit formulas available (Tulino & Verdú, 2004; Dobriban & Wager, 2018).
3. The variance first increases, then decreases with 7. This shows that in the "classical" low-dimensional case, most of the risk is due to variance, while in the "modern" high- dimensional case, most of it is due to bias. This observation consistent with other phe- nomena in proportional-limit asymptoties, for instance that the map between population and sample eigenvalue distributions is asymptotically deterministic (Marchenko Pastur, 1967; Bai & Silverstein, 2010).
A.4 SIMULATIONS WITH CROSS- VALIDAIOLN
See Figure 7. We consider both small and large 7 Our bias-correction procedure shrinks the À to the correct direction and decreases the test error. It is also shown that the ime-standard-mmm rule (e.g., Hastie et al., 2009) does not perform well here.
15

---

and test set Published as a conference paper at ICLR 2020
Blaz vas-variance at optimal
Blas
Var
Figure 6: Bias-variance tradeoff at optimal X = 702 when 3,
CV lest y 0.7
Test error
CV min
min
Test error min
CV best error
CV arrorber
1.8
1.4
CV test emor, y 5
2.5
3.0
CV test error
8.5
8.0
One S13
CV
Debipsed CV min Test
CV errorber
Figure 7: Left; we generate a training set (n 1000. p 700, 0.7,
(Niest = 500) from the same distribution. We split the training set into K = 5 equally sized folds and do cross-validation. The blue error bars plot the mean and standard error of the K test errors. location. The green dashed line indicates
The red dotted line indicates the the optimal Xōv obtained by k-fold cross-var validation, while the red dashed-dotted line indicates debiased version K K= The orange line plots the test error when training on the whole training set and fit the whole test set, and the purple dashed-dotted line indicates the minimal X The K-1 test error is 1.513 at Noy and 1.510 at K Aev. So the bias-correction decreases the test error by about 0.003. Right: we take n 200, p = 1000, 7 = 5, a 3, 1. The bias-correction decreases the test error from 8.92 to 8.89, so it decreases by 0.03.
16

---

Published as a conference paper at ICLR 2020
A.5 CHOOSING THE REGULARIZATION PARAMETER- ADDITIONAL DETAILS
Another possible prediction method is to use the average of the ridge estimators computed during cross-validation. Here it is also natural to the CV-optimal regularization parameters, averaging {_x(A i.c.
K a (21)-
Bang (2
K
This has the advantage that does not require refitting the ridge regression estimator, and also that use the optimal regularization parameter.
A.5.1 TRAIN-TEST VALIDATION
The same bias in the regularization parameter also applies to train-test validation. Since the num- ber of samples is changed when restricting to the training set, the optimal chosen by train-test validation is also biased for the true regularization parameter minimizing the test error. We will later see simulations (Figure 8) that retraining the ridge regression estimator on the whole data will still significantly improve the performance (this is expected based prediction, here we can also use ridge regression on the training set. This effectively reduces sample size Atraann where Terain the sample size of the training However, if the training set grows such that ntrriain + while Atrain + oc, the train-test split has asymptotically optimal performance.
results on CV). For
A.5.2 LEAVE-ONE-OUT
There is special "short-cut" for leave-one-out in ridge regression, which saves from burdensome computation. Write loo(A) for the leave-one-out estimator of prediction error with parameter A. Instead of doing ridge regression times, we can calculate the error explicitly as
1 loo(A) = Σ
Y x B(A) - (A)
where S(A) X(XTX nAI) The minimizer of loo(A) is asymptotically optimal, i.e., it converges to X (Hastie et al., 2019). However, the computational cost of this shortcut is the same as that of a train-test split. Therefore, the method described above has the same asymptotic performance.
1-
122
103
Test error
10
reft 8f
refefft
bic
Figure 8: Comparing different ways of doing cross- cross-validation We take n 500, p 550, a 20, = 1. K = 5. As for train-test validation, we take 80% of samples to be training set and the rest 20% be test set. The error bars are the mean and standard deviation over 20 repetitions.
Simulations: Figure 8 shows simulation results comparing different cross cross-validatee validation methods:
1. kf k-fold cross-valls cross-validation by taking the average of the ridge estimators at the CV-optimal regularization parameter.
17

---

Published as a conference paper at ICLR 2020
2. kf refit k-fold cross-validation by refitting ridge regression on the whole dataset using the CV-optimal regularization parameter.
3. kf k-fold vrossvvaliattion by refitting ridge regression the whole dataset using the
CV-optimal regularization parameter, with bias correction.
4. tt train-test validation, by using the ridge estimator computed the train data, the validation-optimal regularization parameter. Note: we expect this to be similar, but worse than the "kf" estimator.
5. tt refit train-test validation by refitting ridge regression on the whole dataset, using the validation-optimal regularization parameter. Note: we expect this be similar, but slightly worse than the "kf refit" estimator.
6. it bic - train-test validation by refitting ridge regression on the whole dataset using the CV-optimal regularization parameter, with bias correction.
7. loo leave-onc-out
Figure shows that the naive estimators (kf and tt) can be quite inaccurate without refitting or bias correction. However, we either refit or bias-correct, the accuracy improves. In this case, there seems to be no significant difference between the various methods.
A.6 PROOF OF THEOREM 4.
Proof. Suppose m/n
+ & as n goes to infinity. For åp. we have
[X LX/n MIp) x 1
bias = E
n 82 = 0²B [[[ T.X/ "
Alp) the resolvent of the sketched matrix. We further assume that X has iid /N00, 1) entries and LLT Im. Let L1 be an orthogonal complementary matrix of L, such that L L + L L1 Ln. We also denote N X L. L,X
Denote M (
Then
X LX + X LX = Ip AM + MN.
MX X/n =M
Therefore, using that Cov [3] a²/p Lp. we find the bias
bias?
E tr(M IMM Tp)]
A [M] +E lr M (X LT
2AE [Lr N
n²
By the properties of Wishart matrices (e.g.. Anderson, 2003; Muirhead, 2009), we have
E [N]] n
m Ip.
EE [())] = n
W Wisharrt(pp.) m)²]
n² [n m p - m) + (n - m
Recalling that m, n + 0o such that m/n - E, and that 01(7, = f(x + (x),
a²
x + n m + p(n m) + (n - -m)² 22 n2 - m
bias
E
tr [r(
p
n²
+ a²
==2(() + - 1)2 + 711
Moreover,
82
E
[u(MMx x]]
n²
0²
E [tr[M]] - xE [tr[ E [trlare2]]]]
10 - 102 + +1 E))
18

---

Published as a conference paper at ICLR 2020
Here used the additional definitions
(,( / /
/ (Ex + A)
dl (5
0,(7, A) - 0,(7,5=-111 = =1, 1,
Note that these can be connected to the previous definitions by
ʃ
dF dFa)e(1) = 1
2 A
01(7:5:)) = 3
= E- E
+
A/E
1
Y 2)
02(7)5,)) =
2
8²
5- E
Therefore the AMSE of 8p is
AMSE(3p) (AA + - 1)2 71 - (7, A, -4 -A4-)))))- 1)02(7,
ad? + -5-1 1)2 +1(1 = 0₂
7 A
yo² 1 0 E く - + 1) 1)
2 A
1 0g
2 A
(10)
52
A.6.1 ISOTROPIC CASE
Consider the special case where I' = I, that is, X has iid M( 1) entries. Then Fy is the standard MP law, and we have the explicit forms for 02 = 0,(7, A) = (=
(1(7,)) 1 1+1 A
1+1 (V5+
(V7+ 1+ 1 3- 4),
7d
2
V7
V7
02(7,2) 1
7+1
1
X+1
1
1 X
+1)
+
(V7+
V7 )2
712
27
2
7
W + v7
2/7
(1(C,A) = (O((S, A) + 1 5-5
X
B2(S,A) = (02(S, 2) + 1 S-1 X²
The results obtained by the contour integral formula
/ f(x)dFF(()) = 4wi f
[(=))F
f(11 + 72 () - 22
|+1=1 2² + v=z)(z + vF) dz.
See Proposition 2.10 of Yao et al. (2015).
A.7 PROOF OF THEOREM 4.2
Proof. Suppose d/p + { as goes to infinity. For Ba. we have
bias² 2 E - (XRR x /n Ahn) x3 - B
8² 3= o² o x /n+ + AI,) -2 XXT
n²
Denote M (XRR X /n + AI.)) Note that, using that Cov [8] = a2/p. I
a² E Er /mj3|
2 2² Ee
/n| + a²
bias?
[u
tr((p).
p
p
19

---

Published as a conference paper at ICLR 2020
Moreover, letting R1 to be an orthogonal complementary matrix of R, such that RR +R In, and N XR, R, x
1 p
1
E
Lr[xXX
/ml
tr(nn AE [ [MNN]
p
1
/ f x x+ト 1 dFc(z) + 7-5
dFc()))
?
x. +
where F5 is the companion MP law, that is, F5 (1 - 7000 + FFg. The third term calculated by using that X and X R are independent for a Gaussian random matrix X, so that M, N are independent, and that E [N] = 2-d In. Thus
tr M /
1 X x
E
-
p
7 7
1
A
A+C+ ?
1 1-5
(CB((G.A)
7
7
Then
L
E
tr|xxx
/n1
E [tr[[, + X + MNMN 2AM + 2MN AM AMNM.
P
p
Note that
E
B = M(e d) +
+ + d)/
+ (p - d)² M2
p-d tr(M)
n²
n²
SO
E p
tr|MXX
/n|²
+ 1 [11+222- -22-22226 - (7
7
(r- -1 (S)
Thus find the following exprssion for the limiting squared bias:
bias - by - 1 (A - c) + (7 - C)09).
With similar calculations (that we omit for brevity), we can find
8² o2 (f,((, - (A+ -
Therefore the AMSE of 33 is
2
AMSE
7 h 1+ (1 () + -)] + 0² 10(0((())) -2+0(-))2( A)].
(11)
n
A.8 PROOF OF THEOREM 4.3
Proof. Recall that we have m, n + oo, such that m/n - E. Then we need to take + 0. However, we find it more convenient to do the calculation directly from the finite sample results as m, n, p > do with m/n + 0, p/n + 7, It is not hard to check that computing the results in the other way (i.c., interchanging the limits), leads to the same results. Starting from our bias formula for primal sketching, we first get
bias
a
2 n- m + p(n m) + (n- m) p
2x n m
E tr (x((X "L LX/n AIP) {1p)~21 -3]
n²
2 [11 1)2 + 71/22.
20

---

Published as a conference paper at ICLR 2020
The limit of the trace term is not entirely trivial, but it can be calculated by (1) observing that the m x p sketched data matrix P = LX has iid normal entries (2) thus the operator norm of PT P/n vanishes, (3) and so by simple matrix perturbation argument the trace concentrates around p/ p/A?. This gives the rough steps of finding the above limit. Moreover,
o² n²
8
LX/n+ X1) - -xxxxx x xi] tr(( L
=======²²=
So the MSE is = a²((>~ 1)² 71/12 + 0² 7/22. From this it is elementary to find the optimal À and its objective value.
A.9 PROOF OF THEOREM 4.4
Proof. Note that the bias can be written as
a
XRR
X
XXT
bias
E
tr
+A1s)
nd 12
p
nd
a²
[ur[(XRR X /n Al)) XXT /nl] +
E
P
Write G = XXT. Since RR ~ WppTps d), we have XRR X W. So XRR XT _ G//2 where W (n,,
XRR X
-1 XX /n]
tr
+ AIn
= E [u][C)/WW" n\), G
nd
W tri( A 1
E
+
d
n
& So we need to find the law of W. - - Suppose first that G = XXT Wn(In,)) p). Then W and G-1 asymptotically freely independent. The l.s.d. of W/d is the MP law Fi/s while the l.s.d. of G/p is the MP law Fi/-- We need to find the additive free convolution W B G, where a=AG
Recall that the R-transform of a distribution F defined by
R=(2)= = (-2) 1
where (z) is the inverse function of the Stieltjes transform of F' (e.g.. Voiculescu et al., 1992; Hiai & Petz, 2006; Couillet & Debbah, 2011). We can find the R-transform by solving
mr(Rr(z) + + =-2
Note that the R-transform of W/d
Rw(2) = 1 - 2/E
The Stieltjes transform of G-1 is
(z- = /
1/1 dF1/9(x) = 1 1
1
1 1
+
(1 + + 1)2
z
2
1 1
1 +
(1 +
1
7
2
21

---

Published as a conference paper at ICLR 2020
Dual Gaussian sketching
16-
dual Gaussian
No sketching
34
Blas
3.2
3.
29
Figure 9: Dual Gaussian sketch improves MSE.
Then the R-transform of G-1 is
Rg-1(2) = - + 7 1
v (x+ 1)3
47
2z
7- v(7 1)2
477z
2z
Since we have the property that Ray (z) = ally:(az),
Rg = R2 (2)-1(2)= 7
(7
1)2 4A=
2z
Hence we have
1
7
V(r 1 1)2 - 4Az
RWBG = Rw + Rg 1 2/C
2z
Moreover, the Stieltjes transform of f W E G satisfies
((1 1)2 + 4hz
m. (z) = m (2) RF(-2)= 1 z/E
-2z
Note that
XRRTX XT
a²
a²
tr
+ +AI
XXT
/nl
-
E
2
lim m(2),
nd
7
=
2
X.R.RXX T
XXT
a
1
a
d
E
trl
+ Aln
12
E
lim
m(2).
p
nd
nd
7
x2
7
2 +
dz
So it suffices to find mz(2 and d m=) evaluated zero.
This result can characterize the performance of sketching in the high SNR regime, where a >> O. To understand the lower SNR regime, we need to study the variance, and thus we need to calculate
var = v
22LB
1 tr
XRRT X + AT.) XXT /m) - oFR
=
W + irl
d 7 -
nd
where XXX W, (In, p) is a Wishart distribution, and XRR T =, /1/2 with W. (T, This seems to be quite challenging, and we leave it to future work.
22

---

Published as a conference paper at ICLR 2020
A.10 RESULTS FOR PRIMAL GAUSSIAN SKETCHING
The statement requires some notions from free probability, see e.g., Voiculescu et al. (1992); Hiai Petz (2006); Nica & Speicher (2006); Anderson et al. (2010); Couillet & Debbah (2011) for references
Theorem A.1 (Bias of primal Gaussian sketch). Suppose X is an p standard Gaussian random matrix. Suppose also that is a x n matrix with i.i.d. _N(,, 1/d) entries. Then the bias of primal sketch has the expression (3) = a² - (((( b-) - ( where and b two free random variables, that freely independent in non-commutative probability space, and is their trace. Specifically, the law of is the MP law F1/g and b Ab, where the law of is the MP law Fijr
Proof of Theorem A.I. Note that
bias 2 = -E [|(XT L. LX/(nd) + +T,) (X X/n)3 -8 -
LXX - and (XTLLXX LX/(XX()) + AIp) -1 -x-- = XXLXXXXX LXXT((XX)) + + Thus
LXXXT
bias E XT(
+ 3
nd
n1
a² + a
E[tr[( XXTLLI
XXT LXXX
XXT -XXT
+ +
nd + A1,)
p
nd
LXXT
XXT
2r(
nd + AAa)
I1.
First we find the Ls.d. of (L_TxxI + *1,))= 1 -1xxx 1
Write W L. XXT. Then
n
LXXX
nd -Ix) - XXT WG
G = G-1 6 d
W G -
nd + AI,)
A
which is similar to WWW + -()--11--1 So it suffices find the l.s.d. of ( (1)-1)-
By the definition, W (n. d) Wh p). therefore the ls.d. of W/d converges to the MP law F1Ş5 and the l.s.d. of G/p converges to the MP law F1/r-
Also note that
X
XXT
L
XX
W 1n + AnG \nG-11-'GG (
W
(aa)
+ +AA)
nd
71
nd
n
We write A d
B A
Then it suffices find
2 E B(A
We will find an expression for this using free probability. For this we will need to use some series expansions. There are cases, depending whether the operator of BA- is less than greater than unity, leading to different series expansions. We will work out below the first case, but the second case is similar and leads to the same answer.
ir((A -) B(A + B) B tr 'T BA- -(T BA BA-
Since the operator norm of BA- is less unity, have the von Neumann series expansion
[ + BA
BA-
Σ
- BA-
1=
23

---

Published as a conference paper at ICLR 2020
then we have
tr((A + ([(++B) B(A B)- =
Σ
(BB
1,220
Σ
(-1)
A B=
1,220
Since and B are asymptotically freely independent in the free probability space arising in the limit (e.g., Voiculescu al., 1992; Hiai & Petz, 2006; Couillet & Debbah, 2011). and the polynomial (a (a=1t)ttttaa 1-1 involves an alternating sequence of a, b, we have
1 tr((A- A-1B- A + r[(a bb)
n
where a and the b are free random variables and T their law. Specifically, free random variable with the MP law Fifç and is 2 2b-1, where a free n.v. with MP law Fiyy- Moreover, they are freely independent.
Hence, we have
1 tr((A + B) B)- n
Σ 11) 16)+1
Σ (11)((a (b b-11
120
120
ri(a
+ +a (1) -1)
Ti(a + -)
Therefore,
bias a a²
+ BA - + BJ BJ-1)
7
a
=0 + ? [r((a + b) --)-))----- b(a + b) 2r((a + b)-
A.11 RESULTS FOR FULL SKETCHING
The full sketch estimator projects down the entire data, and then does ridge regression on the sketched data. It has the form
LY
B ( L'LXX
We have
bias 2
222
dF (F))5(x) a²x²_ 02
7 1
Exr + X
E &
/
Eor X dF dF) - /
1
var 7
(Er + 212 cl (e)))())))))))
7 A
1
(1
1
01
02
E {)
62
E {
therefore
Y A
A g2 E 2
AMSE(3))= = x²>²
=2> 02
02
+
o29
01
E E
-
-
02
2
The optimal X for full sketch is always X
, the same as ridge regression. Some simulation results shown in Figure 10, and they show the expected shape (e.g.. they decrease with E
24

---

Published as a conference paper at ICLR 2020
MSE full sketch
Theory Am0.3
Theory A-0.5
Simulation A-0.3
Simulation A=0.5
MSE(Bp)
Figure 10: Simulation results for full sketch, with 1000, ? 0.1. The simulation results are averaged over 30 independent experiments.
Dual sketching MSE
Dual sketching bias and varia
7.75
Theory
Blas
230
Simulation
Var
2.25
MSE MSE/Bg./MSEi
1.00
[
Figure 11: Dual orthogonal sketching with = 1,5,A = 1, 3, 1. Left: MSE of dual sketching normalized by the MSE of ridge regression. The standard deviation is over 50 repetitions. Right: Bias and variance of dual sketching normalized by the bias and variance of ridge regression, respectively.
A.12
NUMERICAL. RESULTS
A.12.1 DUAL ORTHOGONAL SKETCHING
See Figure 11 for additional simulation results for dual orthogonal sketching.
12.2 PERFORMANCE AT A FIXED REGULARIZATION PARAMETER
First fix the regularization parameter the optimal value for original ridge regression. The results are visualized in Figure 12. On the æ axis, we plot the reduction in sample size m/n for primal sketch, and the reduction in dimension d/p for dual sketch. In this case, primal and dual sketch will increase both bias and variance, and empirically in the current case, dual sketch increases them more. So in this particular case, primal sketch is preferred.
1.1 PERFORMANCE AT THE OPTIMAL REGULARIIZATION PARAMETER
We find the optimal regularization parameter À for primal and dual orthogonal sketching. Then use the optimal regularization parameter for all settings, see Figure 13. Both primal and dual sketch increase the bias, but decrease the variance. It is interesting to note that, for equal parameters & and
25

---

Published as a conference paper at ICLR 2020
16
minal
variarce Dual variance Original verience
Dual MSE
Dual bias
Original MSE
original bibs
C
Variance 1.
02-
15
04
Figure 12: Fixed regularization parameter = 0.7, optimal for original ridge, in a setting where 7 0.7, and a² a².
MSE, y=0.7
Bias, y=0.7
Primal sketch
0.9
Primal sketch
Dual sketch
Dual sketch
Full sketch
0.8
Full sketch
Original
Original
MSE
0.7
0.5
0.4
0.5
0.3
0.1
Variance, y=0.7
Optimal A, y=0.7
0.20
2.2
Primal sketch
0.18
Dual sketch
2,0
Full sketch
1.8
1.6
var
0.12
1.4
0.10
0.00
Primal sketch
1.2
Dual sketch
1.0
Full sketch
0.04
Original
0.8
5
Figure 13: Primal and dual sketch at optimal X. We take 7 0.7 and let range between 0.001 and 1, where for primal sketch ş = r/n while for dual sketch = d/p.
26

---

Published as a conference paper at ICLR 2020
and in our particular preferred bias or MSE is important, but dual sketch is more desired when one wants smaller variance. All in all, dual sketch has larger MSE than primal sketch in the current setting. It can also be that this specific example, the optimal for primal skerch smaller than that of dual sketch. However these results hard to interpret, because there is natural correspondence between the two parameters & and Ç.
dual sketch has smaller variance, but larger bias. So primal sketch is
A.13 COMPUTATIONAL COMPLEXITY
Since sketching a method to reduce computational complexity, is important to discuss how much computational efficiency we gain. Recall our three estimators
= 8 (x X/n X1, X Y//n=n= (Xx /n +nn) A Y,
8, (xT L LX/n+ MdP X Y/nn
3. - (XRR") X /n AA.) Y,
Their computational complexity, when computed in the usual way, is:
No sketch (Standard ridge): if p n, computing X ' Y and X requires (mp)) and (np²) flops, then solving the linear equation
+ Alp) = x Y requires
(p²)) flops by the LU decomposition. is (mpp²) flops total.
If p n,
the second formula for 3, and the total flops O(pn²).
Primal sketch: for the Hadamard sketch (and other sketches based on the FFT), computing LX by FFT requires mplog n, computing (LX) T LX requires mp?, so the total flops is Op² + mp(log n + p)). So the primal sketch can reduce the computation cost only when
< n.
Dual sketch: computing X XT requires nd (logr + n) flops by FFT, solving (XRR X /n
+ AI,) requires (n flops, the matrix- multiplication of X and (XRR" X /n+ -ly requires (np) flops, so the total flops is O +nd(logp p+
n)). Dual sketching reduce the computation cost only when p
27


Reviews:
[{"review_id": "rygXNl-qtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI 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.\n\n\nComments:\n\n- 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?\n\n- 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).\n\n- 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)).\n\n- 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)?\n\n\nReferences:\n\n[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.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BkgrXByTYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper deals with 3 theoretical properties of ridge regression. First, it proves that the ridge regression estimator is equivalent to a specific representation which is useful as for instance it can be used to derive the training error of the ridge estimator. Second, it provides a bias correction mechanism for ridge regression and finally it provides proofs regarding the accuracy of several sketching algorithms for ridge regression.\n \nThe paper addresses an important problem and puts itself nicely in context of previous work. However, it comes across as three papers stapled together, that were submitted to some journal and have now been put into ICLR format. Most of the important results are in the appendix. The main body of the paper is just a smattering of theorems with some text flowing around them and too much notation. There is little or no intuition provided for the proofs in the paper. Moreover, the connection between the 3 theoretical properties of ridge regression studied is also unclear. There could very well be 2 or 3 conference papers written out of this one paper. \n\nAs far as the technical merit is concerned, I checked some theory and it appears correct, however some things were unclear. For example, the Theorem 2.1 is proven under a random design setting; how would the proven ridge representation look under a fixed design setting? Or can we even prove something in that case?\n\nI think the paper definitely has some merit but the presentation makes it hard to assess it. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies theoretical properties of ridge regression, and in particular how to correct for the bias of the estimator. 

The reviewers appreciated the contribution and the fact that you updated the manuscript to make it clearer.

I however advise the authors to think about the best way to maximize impact for the ICLR audience, perhaps by providing relevant examples from the ML literature.
Decision: Accept (Spotlight)