Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: ### Update

I have read the author response; I'd like to thank the authors for the detailed comments and clarifications.

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

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

In light of the response, I have decided to increase my score to a 6.

==========

The 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).
The 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. 
The 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. 
Interestingly, 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.
main_review: # Update

The 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.

# Detailed Comments

This submission develops an interesting perspective on model selection for $\ell_2$ least-squares by CV.
The main motivation is direct optimization of the CV loss, either by grid-search or by gradient method.
Such optimization comes with optimality guarantees if the CV loss is quasi-convex, leading to the main effort of the paper. 
I think this is a great problem that moves past ERM towards more direct optimization of the risk. 

I believe the theoretical work is sound, but not groundbreaking. 
Some areas of the proofs are unclear and missing details/steps which would both aid the reader and make verifier the results much easier.
See "Theory" below for further discussion of these issues.
The 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.
Furthermore, 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. 

The experiments are do a good job of confirming the theoretical developments. 
In particular, it really does seem that regularity of the singular value spectrum is critical for quasi-convexity. 
The major downside of the experiments is that they are limited to sensitivity analysis; 
no progress is made towards using quasi-convexity for model selection. 
In other words, the consequences of the theoretical results are not explored at all.

Overall, I feel this submission is borderline.
It makes a nice, but small contribution to our understanding of cross validation that I feel is unlikely to effect current practice.
I 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. 
Some potential areas to explore could be:

1. Practical ways to ensure the singular value spectrum is near-uniform. 
2. A demonstration of gradient-descent on the CV loss for a quasi-convex instance. How does the computational cost compare to grid-search? 

## Writing

The writing in the main text is polished. 
The appendix has many small typographic mistakes --- see "Minor Comments" below. 

## Theory 

### Proposition 1

The proposition is correct, but I can't follow the proof as given.
How is the inequality $\mathcal{L}(\lambda) \geq \lambda \delta$ established?
The first-order definition of convexity gives
$$
\begin{aligned}
\mathcal{L}(\lambda) &\geq \mathcal{L}(\lambda^*) + \mathcal{L}'(\lambda^*)(\lambda - \lambda*)\\\\
&\geq \mathcal{L}(\lambda^*) + \delta(\lambda^* + 1 - \lambda*)\\\\
&= \mathcal{L}(\lambda^*) + \delta\\\\
&= \delta.
\end{aligned}
$$
which is not stated inequality.
Perhaps the intention was to define $\lambda = \lambda^* + \lambda'$, which then gives,
$$
\mathcal{L}(\lambda) \geq \mathcal{L}(\lambda^*) + \delta \lambda' \geq \delta \lambda'.
$$
This diverges as $\lambda' \rightarrow \infty$ (and thus $\lambda \rightarrow \infty$), as desired.

### Remark 1

Why is Condition 1 necessary here? It is not used in the proof of Prop. 2, which seems sufficient to make Remark 1 WLOG.

### Proposition 3 

Please add a line to the proposition statement clarifying that it is proved when $\hat \theta$ is the solution the unregularized problem ($\lambda = 0$)?
The 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$.
Also, I assume that it is in fact $\hat E$ which is intended here, rather than $E$, as written in Line 536.
Similar clarification would be appropriate in Line 566.

### Lemma 2

The inequality in the first display of the proof is should be $\leq$ instead of $\geq$.
That, or negative signs are missing on both signs of the inequality.

### Equations 13 and 19:

These equations are difficult to check because all of the calculations have been omitted.
I suggest you include some additional details in the derivation (both for reviewing and for futer readers).

### Lemma 3

**Line 582**: How did you conclude that $\xi_{\cdot, 3} < 0$?
Clearly the first term is negative, but the second term has sign which depends on $\hat \epsilon_n \langle u_n, \hat \theta_n$.
Moreover, as $N \rightarrow \infty$ it is not clear which of the two terms decays faster.

**Display after Line 582**: this only includes the first term of $\xi_{\cdot, 3}$.
How was
$$
\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)
$$
controlled?
Proposition 3 shows the sum $\sum_n |(1 - \|u_n\|^2) \hat \epsilon_n \langle u_n, \hat \theta \rangle|$ is $o(1)$. 
I 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. 
Is this the intended argument? 
Please either include a similar argument in the manuscript or provide an explanation for your reasoning.


### Lemma 4

**Line 603**: How did you conclude that $\lambda_Q' = \lambda_Q + O(1)$?
I see that 
$$
\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}},
$$
where $c \geq - \xi_{\cdot, 3}$ for sufficiently large $N$.
Thus, $[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
the goal becomes showing $[b + \xi_{\cdot, 2}] / 2 \xi_{\cdot, 1} \in O(1)$?

I guess an alternative is to show, 
$$
\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).
$$
It seems that $\xi_{\cdot, 3} \in o(1)$ by Assumptions 1, 3, in which case the difference is $O(1)$;
did you establish that $\xi_{\cdot, 1} \in O(1)$ at some point?

Regardless of the above, please provide more details for this step of the proof.

## Experiments

### Figure 3

The top-left hand plot is great confirmation of the theoretical developments. Very nice!

How did you check that the datasets were quasi-convex? 
This 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. 
I am curious if the authors have a better procedure.

## Minor Comments

- Figure 1: the labels and other figure elements are too small to read. 

- Remark 1: $Y$ is a vector on the $N - 1$ dimensional unit sphere since $Y$ is $N$ dimensional.

- Figure 2: "How does quasiconvexity depend on Y and U , for data with N = 3 and D = 2?" --- rhetorical questions are bad style.
    Try something like "Dependence of quasi-convexity on Y and U for data with N = 3 and D = 2".

- Line 124: I would emphasize that this is the "truncated" or "compact" SVD.
    I was a bit confused later, since $\|u_n\| = 1$ for the "full" SVD and Assumption 3 is then absurd.

- Line 137: $U^\top 1 = 0$ is only a sufficient condition for $X$ to have mean-zero columns. 
    If $X$ is not full rank, then some singular values may be zero and $U^\top 1 \neq 0$ can hold.
    However, it is a necessary condition _if_ you further assume $X$ is full rank.

- Line 140: what do you mean by "normalized" with respect to the singular values?
    The diagonal values of $X^\top X$ are exactly $N$ because of the unit-variance assumption.
    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$. 
    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$.
    I would not usually call this normalized, which I think of as between $0$ and $1$.

- Line 170: There has been no assumption that $X$ is full rank until now (see my earlier comment).
    In fact, is the only time "full-rank" is used in the manuscript as far as I can tell.

- Line 185: It is not true that $\|E\|^2 / N \in O(1)$ almost surely.
    That is, for every finite $N$, the event $\mathcal{E} = \|E\|^2 \geq N \log(N)$ has non-zero probability.
    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$.
    Thus, it is only correct to say that $\|E\|^2 / N \in O(1)$ with _high probability_.
    
- Theorem 1: it is an abuse of notation to write $S \in \Delta$, since $S$ is a matrix. 
    I suppose the intent is $\text{Diag}(S) \in \Delta$.
    Note that this notation is used frequently throughout.

- Figure 3: the labels and other figure elements are somewhat small and low-resolution.

- 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?

- Eq. (6) (Appendix): This expression is missing an inverse sign.

- Line 495 (Appendix): again, $Y$ is vector on the $N - 1$ dimensional unit sphere, not $D$.

- Line 608 (Appendix): "We first give state a theorem..." -> "We first state a theorem..."

- Line 612 (Appendix): The definition of $s_D$ should come before or in the statement of Theorem 2.

limitations_and_societal_impact: Yes, this is a theoretical paper with limited negative societal impacts.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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.

On 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).

On 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.

On 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.

On 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.

[1] "Error bounds in estimating out-of-sample prediction error using leave-one-out cross-validation in high dimensions". Rad, Zhou, Maleki. AISTATS 2020

[2] "Regularization Paths for Generalized Linear Models via Coordinate Descent". Friedman, Hastie, Tibshirani. J. Stat. Soft. 2010

Edit after author response

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

[1]: A modern maximum-likelihood theory for high-dimensional logistic regression, Sur and Candes. PNAS 2019

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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

The 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.
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.

The 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.


MAJOR ISSUES

* 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?):

  a) Can the true out-of-sample risk be non-quasiconvex?
  b) Can the k-fold CV loss be non-quasiconvex (for k \ne N)?
  c) Can the LOOCV loss be non-quasiconvex when n>p?

  (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.

* 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...

* 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.

* 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.

* Whenever the authors say that they checked quasiconvexity (as in Figure 2) -- how was it done? This is never described.


MINOR ISSUES

* 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.

* 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?

* Figure 1: fonts are too small. Make sure the figures are readable when printed out.

* line 37 -- "a" is a typo.

* Figure 2: maybe label axes in units of \pi?

* 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.

* 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.

* line 257: use \cdot instead of * 
limitations_and_societal_impact: Not discussed (but not really needed in this case, imho).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

As 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.



limitations_and_societal_impact: Limitations are discussed properly and there are no negative societal impacts.
review_title: null

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)