Can we globally optimize cross-validation loss? Quasiconvexity in ridge regression
Authors: William T. Stephenson
Zachary Frangella
Madeleine Udell
Tamara Broderick
Venue: NeurIPS 2021 Poster (2021)
Keywords: Cross-validation
local optima
optimization
quasiconvexity
ridge regression
linear regression

Abstract: Models like LASSO and ridge regression are extensively used in practice due to their interpretability, ease of use, and strong theoretical guarantees. 
Cross-validation (CV) is widely used for hyperparameter tuning in these models, but do practical methods minimize the true out-of-sample loss? 
A recent line of research promises to show that the optimum of the CV loss matches the optimum of the out-of-sample loss (possibly after simple corrections). 
It remains to show how tractable it is to minimize the CV loss.
In the present paper, we show that, in the case of ridge regression, the CV loss may fail to be quasiconvex and thus may have multiple local optima. 
We can guarantee that the CV loss is quasiconvex in at least one case: when the spectrum of the covariate matrix is nearly flat and the noise in the observed responses is not too high. More generally, we show that quasiconvexity status is independent of many properties of the observed data (response norm, covariate-matrix right singular vectors and singular-value scaling) and has a complex dependence on the few that remain. We empirically confirm our theory using simulated experiments.

Can we globally optimize cross-validation loss? Quasiconvexity in ridge regression
William Stephenson'
Zachary Frangella Cornell zjf40cornell.com edu
Madeleine Udell
Tamara Broderick
MIT
Cornell udell@
MIT tbroderick@mit.cco edu
wtstephe@mit.eom edu
Abstract
Models like LASSO and ridge regression extensively used in practice due to their interpretability, case use, and strong thcoretical guarantees. Cross- validation (CV) is widely used for hyperparameter tuning in these models, but do practical optimization methods minimize the true out-of-sample loss? A recent line of research promises to show that the optimum of the CV loss matches the optimum of the out-of-sample loss (possibly after simple corrections). It remains to show how tractable it to minimize the CV loss. In the present paper, we show that, in the case of ridge regression, the CV loss may fail to be quasiconvex and thus may have multiple local optima. We can guarantee that the CV loss quasiconvex in at least one case: when the spectrum of the covariate matrix is nearly flat and the noise in the observed responses is not too high. More generally, we show that quasiconvexity status is independent of many properties of the observed data (response norm, covariate-manee matrix right singular vectors, and singular-val value scaling) and has a complex dependence on the few that remain. We empirically confirm our theory using simulated experiments.
Introduction
Linear models, including LASSO and ridge regression, widely used for data analysis across diverse applied disciplines. Linear models are often preferred since they are straightforward to apply in various senses. partieular, (1) their parameters are readily interpretable. (2) They have strong theoretical guarantees on quality. And (3) standard optimization tools are often assumed to find useful parameter and hyperparameter values. Despite their seeming simplicity, though, mysteries remain about the quality of inference in linear models. Consider cross-vaid validation (CV) [Stone] 1974 Allen 1974), the de facto standard for hyperparameter selection across machine learning methods Musgrave et al. 2020). CV is an susy-to-evaluate proxy for the true out-of-o of-sample loss. Is it good proxy? [Homrighausen and McDonald 2014 2013 Chetverikov et al.. 2020 Hastie et al. 2020 Patil et al. 2021 give conditions under which the global minimum of the CV loss (possibly with some mild corrections) matches the optimum of the oft-of-s loss in LASSO and ridge regression. To complete the picture, must understand whether standard methods for minimizing the CV loss find a global minimum.
It would be easy to find a unique minimum of the CV loss if the CV loss were convex. Alas (though perhaps unsurprisingly), we show below that essentially every case of interest the CV loss is not convex. Indeed, the usual introductory cartoon of CV loss (left panel of Fig. []] see also Fig. 5.9 of Hastie al. 2017] or Fig. Rad and Maleki 2020 is not convex. But the cartoon CV loss still exhibits a single global minimum and would be easy to globally minimize with popular approaches like gradient- based methods (Do et al. 2007 Maclaurin et al. 2015 Pedregosal 2016 Lorraine et al.,
2020 or grid search [Bergstra and Bengio 2012 Pedregosa et al. 201 Hsu et al. 2003 Indeed,
Alternate email: wtstephe @ggmall.omm
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Cartoon LOOCV
Life expectancy, N 2938, 15
Wine dataset, 50 = 11
0.06
38
LOOCV less
Out sampa loss
LOOCV(A)
90
0.64
LOOO
34-
0.62
32
60-
0.60
30
0.58
28
10-1
102
10-7
10
10 10:
1050
Figure 1: (Left): Idealized illustration of the leave-one-out CV loss L (blue) and the true out-of- sample loss (black). The minimizer of each curve is marked with vertical line of the corresponding color. (Center): CV loss for a life-expectancy prediction problem after some standard data pre- processing (Condition of Section 2 (Right): CV loss for wine-quality prediction problem on subset of N = 50 data points after standard data rre-processing (Condition I of Section 2
more plausible possibility (which holds for the typical cartoon CV loss) is that the CV loss might be quasiconver; i.c. its level sets are convex. The benefit of quasiconvexity is that, in one dimension, any local optimum is global optimum.
Unfortunately, this cartoon need not hold in general, even in simple models like é éz-regularized linear regression (i.e. ridge regression). Consider minimizing leave-one-out CV (LOOCV) loss as function of the ridge regularization parameter; we denote this loss by L. Wilson et al. [2020] Fig. I] detail a simulated example in which L can be non-quasiconvex. We first demonstrate that L can be non-quasiconvex in real-data examples; see the middle and right panel of Fig. [ which we describe in detail Section We next characterize which aspects of the covariate matrix and observed responses affect quasiconvexity. We prove that the norm of the responses, the scale of the singular values of the covariate matrix, and the right singular vectors of the covariate matrix all have no effect on the quasiconvexity of C. While this result places substantial constraints quasiconvexity of L. we show that the quasiconvexity of L is unfortunately still a complex function of the remaining quantities. Our third contribution is prove conditions under which L is guaranteed to be quasiconvex. In particular, we show that if (1) the covariate matrix has a singular value spectrum sufficiently close to uniform, (2) the least-squares estimator fits the training data sufficiently well, and (3) the left singular vectors of the covariate matrix are sufficiently regular, then L is guaranteed to be quasiconvex. While the conditions of our theory deterministic, we show that they have natural probabilistic interpretations; as a corollary to our theory, we demonstrate that many of our conditions are satisfied either empirically or theoretically by well-speeified linear regression problems with i..dd sub-Gaus Gabs-aan covariates and moderate signal-to-noise ratios. Through empirical studies, we validate the conclusions of our theory and the necessity of our assumptions.
what drives the
2 Setup and notation
For n. E (1,..., N). we observe covariates on E Tr. and responses yn E R. We are interested in learning linear model between the covariates and responses, (5n, 0) R Yn. for some parameter 0 E D. In ridge regression, i.c. lz-regularized linear regression, we take some X > 0 and estimate:
(K 0) vn,) A
(()) arg min
100
BERD
The regularization parameter typically chosen by minimizing the cross-validation (CV) loss. Here we study the lcave-one-out CV (LOOCV) loss:
(())= Σ (x), -mn)
where ())(A) is the solution to Eq. 1 with the nth datapoint left out.
Let the covariate matrix X NxD be the matrix with rows w,, and let vector Y R be the vector with entries Yn- We consider the low to modest-dimensional case where D < N and assume the covariate matrix X full-rank. We further assume X and Y have undergone standard data pre-processing, described next.

---

Condition 1. Y is zero-mean, and X has zero-mean, unit variance columns. Equivalently, where 1 RN is the vector of all ones, Y and 1 0 RD and for all d L....... En = =
Preprocessing X and Y to satisty Condition 1 represents standard best practice for ridge regression. First, using an unregularized bias parameter in Eq. ①I and setting Y to be zero-mean are equivalent; we choose make Y zero-mean, as it simplifies our analysis below. The conditions on the covariate matrix X are important to ensure the use of b2 fy-regularization is sensible. In particular, Eq. ① penalizes all coordinates of 0 equally. If e. some columns of X are measured different scales or are centered differently, this uniform penalty will be inappropriate.
3 LOOCV loss is typically not convex and need not be quasiconvex
If the LOOCV loss L were convex or quasiconvex in X, then any local minimum of L would be global minimum, and we could trust gradient-based optimization methods or grid search methods to return value near global minimum. We next see that unfortunately L is typically not convex and is often not even quasiconvex. First we show that, in essentially all cases of interest, L is not convex.
Proposition 1. If = oc is not minimum of C. then L is not convex function.
Proof. For the sake of contradiction, assume L is convex and À = 30 is not a minimum of C. This implies that there is some maximal X < oo such that ['(x)) 0. Let 5 == C'(X* + 1). By
convexity, L" 2 0, so we know that > and that for À 2 X + 1, we have (* 2 8. Thus for A 2 X" 1, we have ((A) 5() X 1). So lima [(A) cc. However, inspection of L
shows limm ((A)= = Σn Ph oc, which is a contradiction.
We say that the result covers essentially all cases of interest: if L continues to decrease as À - oc, then there is so little signal in the data that the zero model 0 = 0 E R is the optimal predictor according to LOOCV.
Although L is generally not convex, L(A) might still be easy to optimize if satisfies an appropriate generalized notion of convexity. To that end, we recall the definition of quasiconvexity.
Definition 1. A function f RPP + R is quasiconvex if its level sets are convex.
In one dimension (i.e. p in Definition D. quasiconvexity guarantees that any local optimum is a global optimum, just as convexity does. This property often the key consideration in practical optimization algorithms. Moreover, it is not unreasonable to hope that the CV loss is quasiconvex: typical illustrations of the CV loss are not convex but are quasiconvex; see e.g. Hastie et al. (2015) Fig. 5.91, Rad and Maleki [220 Fig. 1]. the left panel of Fig. I Illustrations of the out-of-sample loss are also typically quasiconvex; see e.g. Fig. 3.6 of Bishop 2006].
Unfortunately, we next demonstrate that the CV loss derived from real data analysis problems can be non-quasiconvex. Our first dataset contains N 2.938 observations of life expectancy, along with D = 20 covariates such as country of origin or alcohol use; see ?? for a full description. In this case, after pre-proced prepreeeesing according to Condition [ C for the full dataset is quasiconvex. But now consider some additional standard data prepprocessing. Practitioners often perform principal component regression (PCR) with the aim of reducing noise in the estimated 0. That is, they take the singular value decomposition of X = USS and produce an N x R dimensional covariate matrix X' by retaining just the top R singular values of X: X' = S With this pre- pre-processing, the resulting LOOCV curve L is non-quusiconvex for many values of R; in the center panel of Fig. I we show one example for R = 15.
Our second dataset consists of recorded wine quality of N = 1, 1,599 red wines. The goal is to predict wine quality from D 11 observed covariates relating to the chemical properties of each wine; see ?? for full description. We find that subsets of this dataset often exhibit non-quasiconvex L. In the right panel of Fig. [ we show L for subset of size N 50. We see that this plot contains least two local optima, with substantially different values of À and substantially different values of the loss. gradient- algorithm initialized sufficiently far to the left would not find the global optimum, and grid search without sufficiently large values would not find the global optimum.
3

---

Now we know that L can be non-quasiconvex for real data. Given the difficulty of optimizing a function with several local minima, we next seek understand when C is quasiconvex or not.
4 What does the quasiconvexity of L depend on?
We have seen that L can be quasiconvex or non-quasiconvex, depending on the data at hand. If we could determine the quasiconvexity L from the data, we might better understand how to efficiently tune hyperparameters from the CV loss. In what follows, we start by showing that the quasiconvexity of C is, in fact, independent of many aspects of the data (Proposition 2). We will see, however, that the dependence of quasiconvexity
the remaining aspects (though they few) is complex.
linear regression problem has number of moving parts. The response vector Y may be an arbitrary vector in RR,, and the covariate matrix X can be written in terms of its singular values and left and right singular vectors. More precisely, let X the covariate matrix X, where U E R N x D is an N x D matrix with orthonormal columns, S E R a vector with positive entries, and
diag(S) be the singular value decomposition of
IR D D is an orthonormal matrix. Note we use the "compact" singular value decomposition, where U is N x D matrix, rather than a full N x N matrix. With this notation in hand, we can identify aspects of the problem that do not contribute to quasiconvexity in the following result, which is proved in ??.
Proposition 2. The quasiconvexity of C is independent of
1. the matrix of right singular vectors, V,
2. the norm of the responses, || and
3. the scaling of the singular values (i.e. changing S into S/cfor c Ryoh.
in the sense that altering any of these quantities does not change whether or not L is quasiconvex. Remark 1. Assume Condition I hholds. Then by Proposition 2 without loss of generality we may (and do) assume that V = ID and that Y is a vector on the unit (N - 1)-sphere.
Recall X has zero-mean columns by pre- pre-proeessing the data (Condition Tp. By Proposition 2 we assume without loss of generality V Ip- Thus, the columns of X have zero mean when U 0, where 1 E TR-VV is the vector of all ones. Also, while Remark I notes that we can consider Y to be from Condition alloow us further constrain Y to he parameterized by vector on the unit (N - 2)-sphere. Hence the quasiconvexity of three quantities: (1) the matrix of left singular vectors, U, orthonormal matrix with 1 E IRVV in its left null-space, (2) the (normalized) vector Y which sits on the unit (N 2)-sphere, and (3) the (normalized) singular values.
on the unit (N 1) )-sphere, note that the condition 1 I'y
f. depends
Now that we know the quasiconvexity of depends on only three quantities, we might hope that quasiconvexity would be simple function of the three. To investigate this dependence, we consider the case of = 3 and D = 2, since this case is particularly easy to visualize. To see why it is easy to visualize, first note that Y is a three-dimensional vector; thus by our discussion above, we can parameterize Y by a vector on the unit circle (i.e. scalar hetween Ô and 2Tr. Second, note that the matrix of left singular vectors U is parameterized by two orthonormal vectors, U., and U.2, each on the unit 2-sphere. As both vectors must be orthogonal to E RR3, we can parameterize U.₁ and U.2 by two orthonormal vectors on the unit circle. We parametrize U.1 by a scalar that determines U.2 up to rotation of U.2 by π We fix a rotation for U.2 relative to U., so that, for fixed singular values S, the quasiconvexity of C is parameterized by two scalars.
Fig. 2 is the resulting visualization. Precisely, to make Fig. we fix an orientation between U. and U2 here, rotation of T 7/2 on the unit circle. We create uniform grid over the unit circles for U. and Y. Fig. visualizes the severity of non-quasicnnvexitt
L as we move over this grid for three different settings of the singular values. To define the severity of non-quasiconvexity let Awarsts X², and Xwarst-min correspond to the À maximizing L. the À minimizing C, and the À corresponding to the local minimum with largest L, respectively. We then compute
severity = [(Awarst min) - L(X*)
(3)
[(Xwona) - C(x*)

---

2 = 2-4e-0. 0, ; 7.7e-3
2n²
2,4e+0, 52 7.7e-2
2 = =2:1e+++0.. 5: 1.2e+0
urit circle
U. on urit circle
U3 on unit circle
0.50
0.50
0.25
0.25
0.90
0.00
0.00
0
π
217
2m
π Y on unit circle
2
on unit circle
on unit circle
Figure 2: How does quasiconvexity depend on Y and U, for data with N = and D = 2? The left, center, and right panels each correspond different setting of the singular values S. We divide the unit circle for each of U and Y into 225 equally spaced points. We examine the severity of non-quasiconvexity C over this 225 225 grid. Each grid point colored by Eq. (3), where dark purple corresponds to quasiconvexity (no local minima).
If the severity is near then finding the worst local minimum is nearly bad selecting the worst possible A. In Fig.2we color pixels according to this measure of severity and do fact see values near 1. We
that, in general, U, Y. and S have complicated interaction determine the quasiconvexity of C. The values of that produce quasiconvexity depend on U. No setting of Y or U guarantees quasiconvexity.
Fig. demonstrates the poor performance of a hypothetical optimizer that always finds the worst local minimum. In ??, show that poor performance is not just hypothetical; in particular, the most commonly used methods for optimizing L- grid search and gradient descent encounter difficulties due non-quasiconvexity. Issues due to hon-quasiconvexity performance in terms C nor to optimizing the LOOCV loss. In ??, we show that the K--ood CV loss also suffers from qunquuaiiconvxxtty and that computing Eq. with the test loss instead of L also exhibits issues due to non-quasiconvexity.
also not specific measuring
Despite the complexity of Fig. 2 one trend does seem clear: the singular values become more similar (moving from left to right in the panels of Fig. 2 the fraction Y values and values that correspond quasiconvexity (dark purple regions) grows. Based on this behavior, might conjec- ture that sufficiently uniform spectrum the covariate matrix could guarantee the quasiconvexity of L.
Quasiconvexity of L with nearly uniform spectrum S
We now build on the conjecture of the previous section to show that we can, in fact, guarantee quasiconvexity in certain cases. In particular, we will show conditions under which sufficiently uniform spectrum S of the covariate matrix guarantees that L is quasiconvex.
One might hope that for large N, eventually any Y or U would yield quasiconvexity. However, even when S is exactly uniform, our experiments Section show that we cannot expect such a statement. Rather, will devise conditions on Y and U to avoid "extreme" settings for either quantity. With these conditions, our main theorem will show that a sufficiently flat spectrum does indeed guarantee quasiconvexity of L. When theorem applies, at the first local minimum of L that we discover.
safely terminate optimization procedure
We first establish notation and then state our assumptions.
Definition 2. Let θ (XTX)-l XTY be the least-squares estimate. Define the least-squares residuals = Y XQ. Let én be the rith entry of E.
Note that Ô is well-defined since have assumed that D < N and that is full-rank. For the tractability of our theory, all of our assumptions and conclusions will be asymptotic in N; in particular, our assumptions will use big-O and little-o statements, which are to be taken with respect to N growing large. In our discussion of these assumptions, we assume that D is fixed. There is nothing in our proofs or assumptions that requires to be fixed; however the validity of our assumptions not clear if D grows with N, we do not consider this case here. Since LOOCV is useful precisely for
5

---

finite N, we are careful to show in our experiments (Section 6 that these asymptotics take hold for small N.
Our first assumption concerns the magnitude of the residuals É.
Assumption 1. (1/N) ea is O(1 (i.e. it does not grow with N).
This assumption is fairly lax. For example, suppose our linear model is well-specified. In particular, suppose there exists some 0* RD such that Vn. (Ir, 0*) + E,, where the E,, are i..d. (N, o²) for some σ Stack the En into a vector E' E IR Then || = [1 _U < || Since (1/N) ( E is O(1) with high probability, it follows that Assumption holds with high probability in this well-specified linear model. We emphasize that Assumption depends on the residuals of the least squares estimate, not (directly) on the noise in the observations.
Our next assumption governs the size of the least squares estimate Assumption 2. |||]| is ((1) (i.e. does not grow with N).
Again, this is a lax assumption. For example, given any statistical model for which Ô is a consistent estimator for some quantity, Assumption holds.
Our next assumption constrains the uniformity of the left-singular value matrix U with rows Un R
Assumption 3. We have max, [ || == |max 2 O(N P) for some p 1/2.
Assumption B is an assumption about the coherence of the U matrix, a quantity of importance in compressed sensing and matrix completion [Candés and Recht 2009). In particular, Assumption requires that the coherence of U decay sufficiently fast as a function of N. Suppose we remove the condition that U have zero-mean columns (see Condition Iariiioonaano and the discussion after Remark [1 and assume a uniform distribution over valid U (i.e. matrices with orthonormal columns); then Assumption 3 is known to hold with high probability for any p E (1/2, 1) [Candés and Recht 2009 Lemma 2.2].
There do exist matrices U with orthonormal zero-mean columns that do not satisfy Assumption 3 For instance, take some small Ng (say N, 5) and a valid U' for this Ng. Then, for N No, form U by appending 0 R.VN-N)xD to the bottom of U". This construction yields an N x D matrix U with orthonormal and zero-mean columns for which || 2| is constant as N grows. Still, in our experiments in Section and ??, confirm that, for a uniform distribution over orthonormal U with zero-mean columns, Assumption 3 holds with high probability.
Our final assumption is a technical assumption relating 1|u,.1l,66,, én. and 0.
Assumption 4, The following quantity is positive and ((1) (i.e. is bounded away from zero and does not grow with N): |1012 En ||u,,11 ((ums 0) 263
Roughly, this assumptions means that the largest ||u,.| and E values do not occur for the same
values of n. To see this relation, note that Assumption 3 implies ||²| Σn ||u, (u, 0,2 > (1- --N If we assume that ||0]2 @(1) (i.c. Assumption holds and i does not converge 0 RP),, then find |0||2 Σn ||u, 3 0)2 (1). So, need only that Σn |,, 1 2 = o(1)
) for Assumption 4 to hold; e.g. we need that the largest values of ||,,, || and the
largest values of E? typically do not occur for the same values of n.
With our assumptions in hand, we now state main theorem. Our theorem relates the uniformity of the spectrum of X to the quasiconvexity of L. As we have shown in Proposition the scaling of the singular values does not matter for the quasiconvexity of L. We therefore take the spectrum be nearly uniform around 1 E P.
Theorem 1. Consider a series of regression problems with N growing to infinity, where the Nth problem uses data (X (N), Y(N)). Assume this sequence satisfies Assumptions 1 to 4 Let the covariate matrix of the Nth regression problem have SVD ( U(N) diag( diag(S(N) (NV) There is a No > O and neighborhood A of E RDD such that if N No and the spectrum S(N) A, then is quasiconvex.

---

0.6
N=20
Extrema of [Ig[[
0.0
Assum. violated
Fraction non-QVX
0.5
N=35
Assum. holds
N=50
-0.5
0.3
-1.0
-1.5
0.1
-2.0
-1.5
-1.0
1.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
logi|s
1/h
log(N)
Fraction non-QVX
0.0005
Assum. violated Assum. holds
0.0003
0.0001
100
150
300
N
Figure 3: (Upper lefty: We generate many datasets and plot the fraction that are non-quasiconvex ("non-QVX"), varying N and the distance of the spectrum from uniformity (IS -1S'-1
1) 1 right): We generate two sets (orange, blue) of left-singular vector matrices U. In the blue case, we check that the maximum of log || 2 across all U for particular N decreases roughly linearly on log-log plot (i.e. the blue set satisfies A Assumption 3) In the orange case, we check that the minimum of log [|umax]] across all U for a particular N roughly constant (i.e. the orange set does not satisfy Assumption 3). (Lower): For all the U matrices from the upper right plot, we generate many datasets and plot fraction that are not quasiconvex.
(Upper
Proof sketch: For one-dimensional functions L, a sufficient condition for quasiconvexity is that for all À such that (A) O, we have (X) 0 [Boyd and Vandenberghe 2009 Chapter 3.4]. We first show can be zero only for a bounded set of A. We then show that for any À within this set with C'(A) 0, have ("(X) 0. See ?? for full proof.
In Section showed it can be difficult guess when L is quasiconvex. But Theorem T yields one condition that guarantees L is quasiconvex: when X has a nearly uniform spectrum. A natural question then is: when is the spectrum of nearly uniform? As happens, uniform spectrum occurs under standard assumptions, for example, when the and are i.i.d. sub-Gaussian random variables.
Definition (e.g. /Vershynin 2018)). A random variable Q is mub-Gaussian if there exists a constant > such that E. eep (Q%
Corollary 1. Take any series of regression problems satisfying Assumptions and Assume the series of regression problems
drawn from well-specified linear model for some 6* R
yn (NN) = (z (N) 0*) + E.. where en. 4.1.d. (0, If a is sufficiently small, is consistent for 0-, and the entries of the covariate matrices x and are i.i.d. aab-Gaussian random variables, then L is quasiconvex with probability tending to I as N cc.
(N)
Proof sketch: Assumptions I and hold for well-specified linear model. If the entries of X are i.i.d. sub-Gaussian random variables, standard concentration inequalities imply that its spectrum nearly uniform with high probability; hence the result of Theorem I applies. See ?? for full proof. L

---

6 Theorem
1 in practice
In Section 5 we established number of assumptions that we then required in Theorem T to prove that L is quasiconvex. A few questions remain about our theorem in practice: (1) how large is the neighborhood A, (2) how necessary are our assumptions, and (3) how large do we require N to be? We explicitly answer (1) and (2) with experiments below. (3) is particularly concerning, as regularization has minimal impact when N > D. That is, there is little performance gain by using regularizer, which removes the need for hyperparameter tuning. To show that our theorem holds when N ~ D, the majority of our experiments validating Theorem use N that is at most an order of magnitude larger than D.
Throughout our experiments, we check for non-quasiconvexity numerically and use a shortcut formula to compute L that takes advantage of the fact that the right singular vectors of X are V = LD; see ??
for details. The only software dependency for our experiments NumPy (Harris et al. 2020 which uses the BSD 3-Clause "New" or "Revised" License.
How do we know S is in the neighborhood A in Theorem I While theorem does not give an explicit size of the neighborhood A, we can show empirically that A is substantial, even for small to moderate N. We fix D 5. To generate various spectra of X, set St = ead/ /eaD. For a + O, we get S + 1; we vary a from zero to one to generate spectra of varying distances from uniformity. For each a, sample 100 left-singular-value matrices U from the uniform distribution over orthonormal U with column means equal to O; see ?? for how to generate such matrices. We fix unit-norm o I. D and for each U, we generate data from a well-specified linear model, yn, = (In, 0*) En. where the é, are drawn i..dd from (O, o²) with variance o² = 0.5. In particular, for each setting of U, we generate 100 vectors Y. For each setting of U and Y, we compute L and check whether it is quasiconvex. In the top left panel of Fig. 3 we report the fraction of problems (out of the 100 100 10,000 datasets for the corresponding a value) with a non-quasiconvex C versus the distance from uniformity, ||S 1/1 We see that, even for N = 20, the fraction of non-quasiconvex
problems quickly hits zero as |S - 1|1 shrinks.
To provide a rough practical heuristic, we observe from Fig. 3 that when N = 50 and ||S 155-1p 1 ||1 ~ 2, non-quasiconvexity occurs less than 1% of the time. In Fig. 3 A appears to grow slightly with N. so Fig. 3 seems to suggest that we should expect to see little quasiconvexity if |SS - 1 S 2 and N 50. In practice, how should we access the spectrum to check this condition? When N and D are small enough we can directly compute 5 via the singular value decomposition; however, in practice, N or D may be large. If N is large and D small, we can access the spectrum as the square root of the eigenvalues of X If N is very large, formation of X X can be expensive; in this case, we suggest the use of randomized sketching to obtain a randomized approximation to the spectrum of X WWodrruff et al. 2014]. Finally, when both N and D are large, we can use spectral density estimation, which gives an estimate of the density of a matrix's eigenvalues [Lin et al. 2016), and has been shown to successfully scale to large problems [Ghorbani et al., 2019 Yao et al. 2020
Importance of Assumption 3. We now establish the necessity of Assumption 3 on the decay of ||M 1| with N. To do so, we generate two sets of matrices U as N grows. We generate the first set to satisfy Assumption g] and we generate the second violate Assumption In both cases, we will take D = 5 and ten settings of N between N = 10 and N = 300.
To generate the eisumption-satistyyi matrices U from the uniform distribution over orthonormal U matrices with column means equal to 0. For each N. we plot the maximum value of ||Mmmx|| across these 500 U matrices in Fig. 3 (top-right) as a blue dot. We fit a line to these values on a log-log plot, and find the slope is -0.74. This confirms that these matrices satisfy Assumption
matrices U, we proceed as follows. For each N, we draw 500
To generate assumption-violatin
matrices U, we proceed as follows. Recall that the smallest N is 10 and D = 5. 100 times, we randomly draw Usuall E 8x5 We then construct each U by appending N 8 8 x D zeros to Usmall- For each N. we plot the minimum value of |#mmax] 1|2 across these 100 U matrices in Fig. 3 (top-right) as orange dot. Since the minimum of [[umax]] is constant with N, Assumption is violated.
Now we check quasiconvexity. To that end, we randomly select a fixed unit-norm vector 0* E ERP For each N, we generate 100 noise vectors F. E RRN where the entries F,, are drawn i.i.d. from (0, 0.5). For each U and E, construct Y = US + E, where S = 1 E RD. We then compute
8

---

V w/o non-OVX
0.9
Fraction non- non-QVX QVV
0.0010
20
10
0.0008
0.7
0.0006
0.6
0.0004
0.4
0.0002
0.3
0.0000
14
16
22
24
0.00
0.25 0.50 0.75 1.00 1.25 2.00
Norm
Figure 4: Checking Assumption [ (Left): For each N and each V/ =- we generate many datasets and check if there is any non-quasiconvex ("non-QVX") L. We plot the largest for which find only quasiconvex L. The growth is roughly linear, which suggests Assumption [ cannot be loosened. (Righf): For each N and each v = [E we generate many data sets and plot the fraction of L that non-quasiconvex. Vertical lines show Uaar for each N.
the fraction of these (100 100 10,000) losses C that are non non-quasiconvex. the lower panel of Fig. 3 we plot this fraction against N for both for the assumption-sstiiffe essumpiion-voolatin case (orange) in Assumption 3 When the assumption satisfied (blue), we see that the conclusion of Theorem T holds: beyond a certain N, there are settings of U or Y that generate a non -unnquusic C. We see that in practice, the boundary N small or moderate (below 50). When the assumption is violated (orange dots), fails to hold: as grows, there are still settings U and Y for which quasiconvexity fails to hold. Finally, we call attention to the vertical axis. Even in the fraction non-quasiconvex losses is small. It follows that, even for our degenerate U's, nearly every combination of noise and U leads to quasiconvex L. An interesting challenge for future work is to provide a precise characterization of this effect.
case (blue) and the
that the conclusion of Theorem
-oiiuttioo-volltiing case, the
Do the é need to be small (Assumption) I Finally, we demonstrate the necessity of Assumption [ which can be restated as requiring that [E] grows at most linearly in N. But also find suggestion that there may be even more permissive assumptions interest. To this end, we vary N from 10 to 30. For each N, generate 4,000 settings of U, each uniform over orthonormal U with column means equal to O. For each U, we generate 250 unit vectors R such that U (each generated uniformly over such R; see ??). Separately, we consider 60 different norms for the vector e equally spaced between 0 and 2; these the across N. We generate single unit-norm 8* E R.
For each setting of U, R, and responses Y U1#* + É, where É := vR. We record whether L is quasiconvex problem. For a particular and particular error-norm V/, we check whether any of the L (across 4,000+250 1,000,000 problems) were non-quasiconvex. Finally, for each N, we find the maximum error-norm N such that for all v < Vmax,N every regression problem is quasiconvex. We plot dot at (N, Mmax,N) in the left panel of Fig. We see that in fact the boundary of allowable norms does grow about linearly in N.
consider the regression problem with covariate matrix U1 and
not for this
Our next plot lends additional insight into how the boundary Mmax,N varies with and is also suggestive of other potential variations on Assumption I that might of interest. particular, in the right panel of Fig. [ we consider two particular values of N: N = 10 (blue) and N = 20 (red). For each setting of on the horizontal axis, we compute the fraction non-quasiconvex losses L over all settings of U and R (4.000 250 = 1,000,000 problems for each v). We see that, as expected from the left panel of Fig. 4 the boundary Vmaax.N is higher for N 20 than for N 10. Surprisingly, we also see that at high values of v2, the fraction of conn-uaaiccovvx cases decreases again. We conjecture that general (i.e. beyond these two particular N), large amounts of noise leads little
or no non-quasiconvexity Finally, we note that, as in the bottom panel of Fig. 3 the fraction of non-quasiconvex cases across low. Again, this small fraction suggests a direction for future work.

---

7
Discussion
We have shown that the LOOCV loss C for ridge regression can be non-quasiconvex in real-data problems. Local optima need not be global optima. These multiple local optima may pose a practical problem for common hyperparameter tuning methods like gradient-based optimizers, which may get stuck in a local optimum, and grid search, for which upper and lower bounds need to be set.
We proved that the quasiconvexity of C is determined by only a few aspects of a linear regression problem. But we also showed that the quasiconvexity of L is still a complicated function of the remaining quantities, and as of this writing the nature of this function is far from fully understood. Nonetheless, we have provided theory that guarantees at least some useful cases when L is quasicon-
vex: when the spectrum of the covariate matrix is sufficiently flat, the least-squares fit 0 fits the data reasonably well, and the left singular vectors of the covariate matrix are regular. In our experiments, we have confirmed that these assumptions are necessary to some extent: when they are not satisfied, L can be non-quasiconvex Still, our empirical results make it clear there is more to be explored. We describe some of the directions we believe are most interesting for future work below.
Sharper characterization when L is quasiconvex. Fig. shows that non-quasiconvexity disap- pears as the spectrum of X becomes uniform; however, it is clear that there is very regular behavior to the pattern of quasiconvexity even when the singular values of X are non-uniform. We are not able to characterize these patterns at this time but believe these patterns pose a fascinating challenge for future work. Relatedly, our experiments (Section ( show that when our assumptions are violated, quasiconvexity of C is not guaranteed. However, we have observed that even when L is not guaranteed to be quasiconvex, many settings of U and Y still give quasiconvexity. In many of our experiments, the fraction of non-quasiconvex losses L was extremely small.
How many local optima and how bad are they? Without the guarantee of single, global optimum, it is not clear that we can ever know that we have globally (near- jeear-Joptimize L. However, notice that our examples in Fig. aall have most two local optima. In simulated experiments, we also typically encountered two local optima in non-quasiconvex losses, although we have not studied this behavior systematically. L were guaranteed to have only two or some small number of optima, optimization might again be straightforward, even in the case of non-quasiconvexxity; an algorithm could search until it finds the requisite number of optima and then report the one with the smallest value of C. Alternatively, one might hope that all local optima have CV loss (and ideally out-of- sample error) close in value to that of the global optimum. Indeed, Kawaguchi (2016) argue that this property holds for certain losses in deep learning. Presumably it is not universally the case that local optima exhibit similar loss since the right panel of Fig. | seems to give a counterexample. But might be widely true, true under mild conditions. Meanwhile, in the absence of such guarantees, optimization of L should proceed with caution.
Beyond ridge regression. We have shown in our opinion surprising non-quasiconvexity for the LOOCV loss for ridge regression. Do similar results hold for simple models outside ridge regression? The regularization parameter in other & or & E1-regularized generalized linear models is often tuned by minimizing a cross- cross-validation loss. In preliminary experiments, we have found non-quasiconvexity in fy-regularized logistic regression. To what extent do empirical results like those in Fig. or theoretical results like those in Theorem Thold for other models and regularizers?
Acknowledgements
We thank the anonymous reviewers for suggesting valuable additional experiments and very carefully checking (and correcting) our proofs. WS and TB thank an NSF Career Award and an ONR Early Career Grant for support. MU and ZF gratefully acknowledge support from NSF Award IIS- 1943131, the ONR Young Investigator Program, and the Alfred P. Sloan Foundation.
References
D. M. Allen. The relationship between variable selection and data agumentation and method for prediction. Technometrics, 16(1): Feb 1974.
Bergstra and Y. Bengio. Random search for hyper-parameter optimization, Journal of Machine Learning Research, 13(2), 2012.
10

---

C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2009.
Foundations of D. Chetverikov, Z. Liao, and V. Chernozhukov. On cross-validated Lasso in high dimensions. arXiv Preprini, February 2020.
E. J. Candés and B. Recht. Exact matrix completion via convex optimization. Computational Mathematics, 9, 2009.
C. Do, C. Foo, and A. Y. Ng. Efficient multiple hyperparameter learning for log-linear models. In Neural Information Processing Systems (NIPS), 2007.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via Hessian eigenvalue density. In International Conference on Machine Learning, pages 2232- 2241. PMLR, 2019.
C. R. Harris, K. Jarrod Millman, S. J. van der Walt, R. Gommers, P. Virtanen, David C. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. Fernández del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant. Array programming with NumPy, Nature, 585(7825)3357-322 September 2020.
T. Hastie, R. Tibshirani, and M. Wainwright. Statistical learning with sparsity: the Lasso and generalizations. Chapman and Hall CRC, 2015.
T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer, Jan 2017.
T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint, Dec 2020.
D. Homrighausen and J. McDonald. The lasso, persistence, and cross-validation. International Conference in Machine Learning (ICML), 2013.
D. Homrighausen and D. J. McDonald. Leave-one-out cross-validation is risk consistent for Lasso. Machine Learning, 97(1-2)x65-78, October 2014.
C. Hsu, C. Chang, and C. Lin. practical guide to support vector classification, 2003.
K. Kawaguchi. Deep learning without poor local minima. In Neural Information Processing Systems (NIPS), 2016.
Lin Lin, Yousef Saad, and Chao Yang. Approximating spectral densities of large matrices. SIAM review, 58( 1):33465,,, 2016.
J. Lorraine, P. Vicol, and D. Duvenaud. Optimizing millions of hyperparameters by implicit dif- ferentiation. International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
D. Maclaurin, D. Duvenaud, and R. P. Adams. Gradient-based hyperparameter optimization through reversible learning. In International Conference on Machine Learning (ICML), 2015.
K. Musgrave, Belongie, and S. N. Lim. A machine learning reality check. In European Conference Computer Vision (ECCV), 2020.
Patil, Y. Wei, A. Rinaldo, and R. J. Tibshirani. Uniform consistency of cross-validation estimators for high-dimensional ridge regression. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference in Machine Learning (ICML), 2016.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pret- tenhofer, R. Weiss, and Dubourg. Scikit-learn: Machine learning python. The Journal of Machine Learning Research, 12:2825-2834 2011.

---

K. R. Rad and A. Maleki. A scalable estimate of the out-of-sample prediction error via approximate leave-one-out cross-validation. Journal of the Royal Statistical Society Series June 2020.
M. Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the American Statistical Association, 36(2):1 1 11-147, 1974.
R. Vershynin. Hiihh-dimensional Probability: An Introduction with Applications Data Science. Cambridge University Press, August 2018.
A. Wilson, M. Kasy, and L. Mackey, Approximate cross-validation: guarantees for model assessment and selection. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-177, 2014.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of the Hessian. In 2020 IEEE International Conference on Big Data, pages 581-590. IEEE, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative socictal impacts your work? [No] Our work focuses pointing out flaws with existing methodology and understanding when these flaws do not occur. As these flaws exist independent of any kind of malicious action, is hard for us find any negative societal impact of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We refer to the relevant part of the appendix after each stated result.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [Yes] See ?? for our experiments replicated with error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] As we are not proposing new method that others might use themselves, we do not think compute time is relevant in our experiments.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Section 6
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
We do create new assets besides the code from question 3a.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] See ??.
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See ??.
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We do not use crowdsoureing or human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] We do not use crowdsourcing human subjects.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We do not use crowdsourcing or human subjects.
13


Reviews:
[{"review_id": "iFdTU4fIlG5", "reviewer": "Reviewer_MpnJ", "summary": "The authors consider the problem of analyzing the shape of the leave-one-out cross-validation loss, and establish sufficient conditions in terms of properties of the observation matrix $X$ under which the loss is quasi-convex, in a finite sample setting with assumptions related to the Fisherian ($n \\rightarrow \\infty$, $p$ fixed) asymptotic. The theoretical results are illustrated through some simulations.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "I found the paper to be well-written and easy to follow. However, I found the results to be non-surprising if not straightforward interpretations of well-known properties of ridge regression, and as such I believe that this contribution is not sufficiently significant for publication. I will detail my comments below.\n\nOn proposition 1 and 2. Propositions 1 and 2 are immediate from straightforward properties of the least-squares estimator: proposition 1 by noting that convex functions are lower-bounded by all their sub-tangents, and proposition 2 by the classical result that the specified quantities do not affect the loss up to scaling (as proved by the authors).\n\nOn the form of the assumptions and statement of theorem 1. The statement of the assumptions and the theorem could be improved by stating theorem 1 as a quantitative bound over the quantities defined in the assumptions, as the current “asymptotic” setup is not necessary to obtain the result, and is somewhat unnecessarily confusing due to the fact that no particular sequence of problems is described.\n\nOn the “asymptotic” setup. The current setup considered by the authors (with the requirement that $n \\rightarrow \\infty$ for $p$ fixed) is of limited interest for the problem at hand. Indeed, in such a context, the importance of regularization is much diminished (as there is no bias-variance trade-off), and it is not clear to me that this corresponds to typical settings of interest for hyper-parameter selection. Instead, it seems that the high-dimensional asymptotic $n \\rightarrow \\infty$, $n / p \\rightarrow c$ is more appropriate for this problem, and given the existence of consistency result for the LOOCV estimator [1], it is not unreasonable to expect that similar results for quasi-convexity exist.\n\nOn the title of the paper. I would suggest the authors amend their title to de-emphasize the optimization aspect and highlight their contribution to characterizing the shape of the LOOCV loss for ridge regression, as there are no difficulty optimization difficulties in the problems highlighted by the authors. Indeed, in models like the ridge or LASSO which contain a scalar tuning parameter (or perhaps a couple of tuning parameters), grid search is a perfectly appropriate strategy for minimization and used in practice. Additionally, I note that for many such models, obtaining the solution path is not necessarily more expensive than obtaining a single solution (e.g. see [2], section 2.5), and hence grid search does not necessarily entail a heavy computational burden.\n\n[1] \"Error bounds in estimating out-of-sample prediction error using leave-one-out cross-validation in high dimensions\". Rad, Zhou, Maleki. AISTATS 2020\n\n[2] \"Regularization Paths for Generalized Linear Models via Coordinate Descent\". Friedman, Hastie, Tibshirani. J. Stat. Soft. 2010\n\nEdit after author response\n\nI would like to thank the authors for their response addressing my questions in detail. Unfortunately, I overall still feel that this contribution is somewhat too minor for this venue. To clarify some of the points I made in the review:\n- on proposition 1 / 2: as the authors correctly point out, I was sloppy in my description of the invariance. What I meant is that all of the described quantities can be accounted for through straightforward change of variables in the presentation of the loss (scaling, rotation of $\\beta$, and global scaling of $\\beta$ which corresponds to a scaling of $\\lambda$). I do believe that these are well-known properties of the OLS / ridge estimator.\n- on the asymptotics: although I agree with the authors that parametric asymptotics may be useful in giving indicative behavior for finite sample problems, I am not currently convinced that their exists a finite sample regime where i) regularization is necessary and ii) parametric asymptotics are a good description of the problem. See e.g. empirical and theoretical analysis presented in [1]. Similarly, believe that high-dimensional asymptotics would provide a much more faithful representation of the behavior in finite sample regimes of interest.\n\n[1]: A modern maximum-likelihood theory for high-dimensional logistic regression, Sur and Candes. PNAS 2019\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation of this work are centered around the $p$ fixed $n \\rightarrow \\infty$ setup, which is of limited interest in the context of penalized regression. In particular, this limitation is apparent in the assumption that the empirical spectral distribution of the Gram matrix $X^\\top X$ must be close to a point mass at 1. I would hope that the authors could address this by considering a high-dimensional setup with $n / p \\rightarrow c$ and adjusting the assumptions accordingly.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Umkg1aT-Uv9", "reviewer": "Reviewer_zWsE", "summary": "### Update\n\nI have read the author response; I'd like to thank the authors for the detailed comments and clarifications.\n\n- I am convinced from the authors' response that all of the theoretical issues I raised in my review can be fixed/clarified. Indeed, the response above does exactly this and need only be integrated into the main paper.\n\n- I like the proposed experiments illustrating that GD on the LOO-CV loss can get stuck in local minima. This will be a nice demonstration of why the theoretical results matter in practice --- especially if the resulting test accuracies are quite different between the local min and the global solution.\n\nIn light of the response, I have decided to increase my score to a 6.\n\n==========\n\nThe authors conduct a theoretical and empirical investigation of the _quasi-convexity_ of the leave-one-out cross validation (CV) metric for $\\ell_2$-regularized least-squares regression (aka ridge-regression).\nThe main theoretical results are: i) counter-examples for general (quasi-)convexity of the CV metric, ii) an enumeration of dataset properties which do not effect quasi-convexity (scaling of the singular values of $X$, scaling of the targets $Y$, and the right singular vectors), and iii) sufficient conditions for quasi-convexity to hold. \nThe empirical component of the submission validates the sufficient conditions for quasi-convexity --- thus confirming the theoretical developments --- and examines sensitivity of the main result to their violation. \nInterestingly, these experiments show that quasi-convexity is highly sensitive to the singular-value spectrum, but relatively robust to irregularity in the residuals and left singular vectors.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "# Update\n\nThe authors provided detailed clarifications on the theoretical issues that I raised in my review. In addition, they have promised to provide additional experiments illustrating the practical consequences of quasi-convexity of the LOO-CV loss. As as result, I have increased my score to a 6.\n\n# Detailed Comments\n\nThis submission develops an interesting perspective on model selection for $\\ell_2$ least-squares by CV.\nThe main motivation is direct optimization of the CV loss, either by grid-search or by gradient method.\nSuch optimization comes with optimality guarantees if the CV loss is quasi-convex, leading to the main effort of the paper. \nI think this is a great problem that moves past ERM towards more direct optimization of the risk. \n\nI believe the theoretical work is sound, but not groundbreaking. \nSome areas of the proofs are unclear and missing details/steps which would both aid the reader and make verifier the results much easier.\nSee \"Theory\" below for further discussion of these issues.\nThe submission does not develop any tools/proof techniques that I think are immediately useful elsewhere, since most of the analysis proceeds by comparisons with quadratic functions.\nFurthermore, use of such proof techniques means the result is probably hard to extend beyond least-squares regression, where the gradient of the CV loss will deviate more significantly from a quadratic. \n\nThe experiments are do a good job of confirming the theoretical developments. \nIn particular, it really does seem that regularity of the singular value spectrum is critical for quasi-convexity. \nThe major downside of the experiments is that they are limited to sensitivity analysis; \nno progress is made towards using quasi-convexity for model selection. \nIn other words, the consequences of the theoretical results are not explored at all.\n\nOverall, I feel this submission is borderline.\nIt makes a nice, but small contribution to our understanding of cross validation that I feel is unlikely to effect current practice.\nI am willing to increase my score if the authors can clarify some of their proofs and provide (or just detail) some interesting experiments showing how we could use their results in practice. \nSome potential areas to explore could be:\n\n1. Practical ways to ensure the singular value spectrum is near-uniform. \n2. A demonstration of gradient-descent on the CV loss for a quasi-convex instance. How does the computational cost compare to grid-search? \n\n## Writing\n\nThe writing in the main text is polished. \nThe appendix has many small typographic mistakes --- see \"Minor Comments\" below. \n\n## Theory \n\n### Proposition 1\n\nThe proposition is correct, but I can't follow the proof as given.\nHow is the inequality $\\mathcal{L}(\\lambda) \\geq \\lambda \\delta$ established?\nThe first-order definition of convexity gives\n$$\n\\begin{aligned}\n\\mathcal{L}(\\lambda) &\\geq \\mathcal{L}(\\lambda^*) + \\mathcal{L}'(\\lambda^*)(\\lambda - \\lambda*)\\\\\\\\\n&\\geq \\mathcal{L}(\\lambda^*) + \\delta(\\lambda^* + 1 - \\lambda*)\\\\\\\\\n&= \\mathcal{L}(\\lambda^*) + \\delta\\\\\\\\\n&= \\delta.\n\\end{aligned}\n$$\nwhich is not stated inequality.\nPerhaps the intention was to define $\\lambda = \\lambda^* + \\lambda'$, which then gives,\n$$\n\\mathcal{L}(\\lambda) \\geq \\mathcal{L}(\\lambda^*) + \\delta \\lambda' \\geq \\delta \\lambda'.\n$$\nThis diverges as $\\lambda' \\rightarrow \\infty$ (and thus $\\lambda \\rightarrow \\infty$), as desired.\n\n### Remark 1\n\nWhy is Condition 1 necessary here? It is not used in the proof of Prop. 2, which seems sufficient to make Remark 1 WLOG.\n\n### Proposition 3 \n\nPlease add a line to the proposition statement clarifying that it is proved when $\\hat \\theta$ is the solution the unregularized problem ($\\lambda = 0$)?\nThe claimed equality $\\hat E^\\top U \\hat \\theta$ is easily verified for $\\lambda = 0$, but does not hold for $\\lambda > 0$ even if $S = I$.\nAlso, I assume that it is in fact $\\hat E$ which is intended here, rather than $E$, as written in Line 536.\nSimilar clarification would be appropriate in Line 566.\n\n### Lemma 2\n\nThe inequality in the first display of the proof is should be $\\leq$ instead of $\\geq$.\nThat, or negative signs are missing on both signs of the inequality.\n\n### Equations 13 and 19:\n\nThese equations are difficult to check because all of the calculations have been omitted.\nI suggest you include some additional details in the derivation (both for reviewing and for futer readers).\n\n### Lemma 3\n\n**Line 582**: How did you conclude that $\\xi_{\\cdot, 3} < 0$?\nClearly the first term is negative, but the second term has sign which depends on $\\hat \\epsilon_n \\langle u_n, \\hat \\theta_n$.\nMoreover, as $N \\rightarrow \\infty$ it is not clear which of the two terms decays faster.\n\n**Display after Line 582**: this only includes the first term of $\\xi_{\\cdot, 3}$.\nHow was\n$$\n\\sum_n \\left(\\frac{1}{(1 - \\|u_n\\|^2)^3} - 1\\right) \\left((1 - \\|u_n\\|^2) \\hat \\epsilon_n \\langle u_n, \\hat \\theta \\rangle \\right)\n$$\ncontrolled?\nProposition 3 shows the sum $\\sum_n |(1 - \\|u_n\\|^2) \\hat \\epsilon_n \\langle u_n, \\hat \\theta \\rangle|$ is $o(1)$. \nI suppose that Assumption 3 implies $\\left(\\frac{1}{(1 - \\|u_n\\|^2)^3} - 1\\right) \\rightarrow 1$ as $N \\rightarrow \\infty$; upper-bounding this by $\\left(\\frac{1}{(1 - \\|u_{max}\\|^2)^3} - 1\\right)$ and pulling it out of the sum should allow you to use Prop. 2 to obtain that this term is $o(1)$ as well. \nIs this the intended argument? \nPlease either include a similar argument in the manuscript or provide an explanation for your reasoning.\n\n\n### Lemma 4\n\n**Line 603**: How did you conclude that $\\lambda_Q' = \\lambda_Q + O(1)$?\nI see that \n$$\n\\lambda_Q' = \\lambda_Q + \\frac{b + \\xi_{\\cdot, 2} - [\\xi_{\\cdot, 2}^2 - 4 \\xi_{\\cdot, 1} \\xi_{\\cdot, 3}]^{1/2} + [b^2 + 4 \\xi_{\\cdot, 1} c]^{1/2}}{2 \\xi_{\\cdot, 1}},\n$$\nwhere $c \\geq - \\xi_{\\cdot, 3}$ for sufficiently large $N$.\nThus, $[b^2 + 4 \\xi_{\\cdot, 1} c]^{1/2} - [\\xi_{\\cdot, 2}^2 - 4 \\xi_{\\cdot, 1} \\xi_{\\cdot, 3}]^{1/2} \\geq 0$ for large $N$ and\nthe goal becomes showing $[b + \\xi_{\\cdot, 2}] / 2 \\xi_{\\cdot, 1} \\in O(1)$?\n\nI guess an alternative is to show, \n$$\n\\frac{- [\\xi_{\\cdot, 2}^2 - 4 \\xi_{\\cdot, 1} \\xi_{\\cdot, 3}]^{1/2} + [b^2 + 4 \\xi_{\\cdot, 1} c]^{1/2}}{2 \\xi_{\\cdot, 1}} \\in O(1).\n$$\nIt seems that $\\xi_{\\cdot, 3} \\in o(1)$ by Assumptions 1, 3, in which case the difference is $O(1)$;\ndid you establish that $\\xi_{\\cdot, 1} \\in O(1)$ at some point?\n\nRegardless of the above, please provide more details for this step of the proof.\n\n## Experiments\n\n### Figure 3\n\nThe top-left hand plot is great confirmation of the theoretical developments. Very nice!\n\nHow did you check that the datasets were quasi-convex? \nThis could be accomplished by evaluating the CV loss on a fine grid and checking for convexity of the sub-level sets, but this is somewhat unattractive, since there may always be false negatives. \nI am curious if the authors have a better procedure.\n\n## Minor Comments\n\n- Figure 1: the labels and other figure elements are too small to read. \n\n- Remark 1: $Y$ is a vector on the $N - 1$ dimensional unit sphere since $Y$ is $N$ dimensional.\n\n- Figure 2: \"How does quasiconvexity depend on Y and U , for data with N = 3 and D = 2?\" --- rhetorical questions are bad style.\n    Try something like \"Dependence of quasi-convexity on Y and U for data with N = 3 and D = 2\".\n\n- Line 124: I would emphasize that this is the \"truncated\" or \"compact\" SVD.\n    I was a bit confused later, since $\\|u_n\\| = 1$ for the \"full\" SVD and Assumption 3 is then absurd.\n\n- Line 137: $U^\\top 1 = 0$ is only a sufficient condition for $X$ to have mean-zero columns. \n    If $X$ is not full rank, then some singular values may be zero and $U^\\top 1 \\neq 0$ can hold.\n    However, it is a necessary condition _if_ you further assume $X$ is full rank.\n\n- Line 140: what do you mean by \"normalized\" with respect to the singular values?\n    The diagonal values of $X^\\top X$ are exactly $N$ because of the unit-variance assumption.\n    Since the singular values of $X$ are the square-roots of the eigenvalues of $X^\\top X$, it holds that $\\sigma_0(X)^2 \\leq N^2$ (consider a simple bound based on the trace) and $\\sigma_N(X)^2 \\geq 1$. \n    Moreover, I don't believe you can conclude anything stronger on the distribution of the spectrum, except that $\\sum_{i} \\sigma_i(X)^2 \\leq N^2$.\n    I would not usually call this normalized, which I think of as between $0$ and $1$.\n\n- Line 170: There has been no assumption that $X$ is full rank until now (see my earlier comment).\n    In fact, is the only time \"full-rank\" is used in the manuscript as far as I can tell.\n\n- Line 185: It is not true that $\\|E\\|^2 / N \\in O(1)$ almost surely.\n    That is, for every finite $N$, the event $\\mathcal{E} = \\|E\\|^2 \\geq N \\log(N)$ has non-zero probability.\n    To see this, consider that the $e_i$ are independent, so a lower-bound on the probability of $\\mathcal{E}$ is $\\prod_i^N P(e_i^2 \\geq \\log(N))$, which is clearly non-zero for every finite $N$.\n    Thus, it is only correct to say that $\\|E\\|^2 / N \\in O(1)$ with _high probability_.\n    \n- Theorem 1: it is an abuse of notation to write $S \\in \\Delta$, since $S$ is a matrix. \n    I suppose the intent is $\\text{Diag}(S) \\in \\Delta$.\n    Note that this notation is used frequently throughout.\n\n- Figure 3: the labels and other figure elements are somewhat small and low-resolution.\n\n- Eq. (5) (Appendix): Why does the intermediate expression have a $c^2$ multiple? The $c^2$ terms from the numerator and denominator cancel. Maybe this is an oversight?\n\n- Eq. (6) (Appendix): This expression is missing an inverse sign.\n\n- Line 495 (Appendix): again, $Y$ is vector on the $N - 1$ dimensional unit sphere, not $D$.\n\n- Line 608 (Appendix): \"We first give state a theorem...\" -> \"We first state a theorem...\"\n\n- Line 612 (Appendix): The definition of $s_D$ should come before or in the statement of Theorem 2.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, this is a theoretical paper with limited negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "NLbHVdhtl-6", "reviewer": "Reviewer_tmqa", "summary": "The manuscript characterizes conditions under which the leave-one-out cross-validation error of ridge regression as a function of the ridge hyper-parameter has quasi-convex shape. The quasi-convexity would make the search for an optimal hyper-parameter value easier due to its single global optimum. Provided that certain mild technical assumptions about the data hold, quasi-convexity tends to emerge when the singular value spectrum of the training data is uniform enough. The effect of the assumptions and their violations are experimentally analysed with simulations.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The manuscript is clearly written which made reading enjoyable, and I did not spot any problems with the math or experimental analysis. To my knowledge, the presented detailed analysis of the quasi-convexity conditions of the ridge regression's leave-one-out cross-validation error as a function of the ridge hyper-parameter is original work and the observations are interesting at least from the theoretical point of view. Perhaps the biggest issue is that the results may not yet form a practical enough entity that would provide comprehensive guidelines for CV based ridge selection, such that would also cover cases when the considered conditions do not apply, especially the non-uniform spectra. Further studies and results, for example, about the number of severity of the possible local optima, are anticipated in the discussion section, and the current manuscript is indeed a good step towards that direction.\n\nAs a particular detail that would improve the paper, while the authors refer to several articles showing that CV is a good proxy for the out-of-sample error, I would still prefer to also see the out-of-sample error plots as a function of ridge parameter in addition to the CV plots, especially when there is a large enough data available for testing, because that would illuminate better how much practical importance it would have to find the global optimum of CV curve rather than a local one. Moreover, as said above, since the motivation for the study is very practical, I would prefer to see at least some sort of guidelines about how to carry out ridge selection with CV, given the results of this paper. For example, how to confirm that the conditions hold and then how to do the search when they hold and when they do not.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed properly and there are no negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Can not estimate as the work was distributed into too many distinct time slots."}, "extra_text": {}}, {"review_id": "BDfSUUPAMH", "reviewer": "Reviewer_YgJz", "summary": "This paper demonstrates that leave-one-out cross-validation (LOOCV) risk estimate for ridge regression can have multiple local minima (both in real data and in simulations). It then goes on to prove that under some restrictive set of conditions the LOOCV loss is quasiconvex and only has one local=global minimum.\n\nThe paper is easy to follow and fun to read. The fact that LOOCV curve can have local minima was pretty surprising to me (but I may be unaware of some relevant literature). Not sure it's a perfect fit specifically for NeurIPS, but I vote for acceptance.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "This paper demonstrates that leave-one-out cross-validation (LOOCV) risk estimate for ridge regression can have multiple local minima (both in real data and in simulations). It then goes on to prove that under some restrictive set of conditions the LOOCV loss is quasiconvex and only has one local=global minimum.\n\nThe paper is easy to follow and fun to read. The fact that LOOCV curve can have local minima was pretty surprising to me (but I may be unaware of some relevant literature). Not sure it's a perfect fit specifically for NeurIPS, but I vote for acceptance.\n\n\nMAJOR ISSUES\n\n* The paper claims that LOOCV loss may fail to be quasiconvex in the n<p regime (N<D in the paper notation). I would like to see the following questions at least discussed in the Discussion (perhaps for some of them the authors can even show non-quasiconvexity example in a simulation?):\n\n  a) Can the true out-of-sample risk be non-quasiconvex?\n  b) Can the k-fold CV loss be non-quasiconvex (for k \\ne N)?\n  c) Can the LOOCV loss be non-quasiconvex when n>p?\n\n  (a) and (c) are most interesting. For (c), there is recent work showing that surprising phenomena can happen in that regime: https://jmlr.org/papers/v21/19-844.html. I wonder how this situation manifests itself with LOOCV. That would be worth discussing.\n\n* It's a bit unclear if the authors think quasiconvexity is common or not *in practice*. Line 54 seems to suggest that it is rare (i.e. assumptions to prove quasiconvexity are common). However, in my experience, most often the spectrum of X is very non-flat and fast-decaying, with strong initial singular values. This goes against the assumptions needed to prove quasiconvexity, so I would actually expect non-quasiconvexity to be the typical situation in practice then, is that right? A bit surprising then that nobody noticed it until now...\n\n* Section 2 fails to mention the standard explicit formula for LOOCV risk (1\\n \\sum e_i^2 / (1-h_i)^2). Did the authors actually use LOOCV for experiments (i.e. fit N separate models)? I guess not -- so this formula should be in here.\n\n* Experiments shown in Figure 1b-c are interesting, and it would be interesting to have a fuller investigation described in the text: line 106 says \"for many values of R\" -- for which? What happens for R on a grid from 1 to 20? line 110 says \"a subset of size N=50\". Which subset? Random? How often does one get non-quasiconvexity for N=50? What about other N sizes? This does not have to be a figure, but at least some fuller empirical description in the text.\n\n* Whenever the authors say that they checked quasiconvexity (as in Figure 2) -- how was it done? This is never described.\n\n\nMINOR ISSUES\n\n* line 25: this recent paper http://proceedings.mlr.press/v130/patil21a.html should probably be cited here too. And it may make sense to look into the references cited in there to see if there are other important citations.\n\n* line 34: here and below \"gradient-based\" optimisation is mentioned a few times. I am not aware of anybody optimizing ridge penalty using gradient descent. Is there an expression for the gradient? If not, how would one implement it?\n\n* Figure 1: fonts are too small. Make sure the figures are readable when printed out.\n\n* line 37 -- \"a\" is a typo.\n\n* Figure 2: maybe label axes in units of \\pi?\n\n* line 142-143: this sounds very naive. Proposition 2 is almost obvious, and it is clear that U and S are actually the variables of interest here.\n\n* Figure 3: panel 2 goes together with panel 3. I would put them in one row, or even better split this figure into two separate ones.\n\n* line 257: use \\cdot instead of * ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not discussed (but not really needed in this case, imho).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for the additional clarifications provided in the rebuttal. The reviewers were satisfied with the authors' response about theoretical concerns and the appreciated the additional experiments. All reviewers also agreed that the overall problem discussed in this work is of interest to the community and that the paper makes a novel contribution, albeit that its importance is narrow.
Decision: Accept (Poster)