Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This submission derives new generalization bounds for tuning the regularization parameters for ridge-regression, LASSO, and the elastic net methods. 
In particular, the authors study two settings: (i) tuning based on multiple draws of train/test splits from a fixed (but arbitrary) problem distribution and (ii) online learning, where new train/test splits are provided as problem instances at each time step.
In the former setting, the authors show $\tilde O(p^3/\\epsilon^2)$ problem samples are required to come within $\\epsilon$ of the best (expected) loss.
In the latter setting, the authors impose a smoothness assumptions on the adversary in order to provide a continuous version of the multiplicative weights algorithm with sub-linear regret. 
Both results rely on a novel characterization of the tuning objective as a piecewise rational function with boundaries given by polynomial curves.
The submission concludes with extensions to linear classification problems with a fixed decision threshold and squared loss.
strengths_and_weaknesses: This is a highly novel paper which tackles an excellent problem: how to properly tune regularization parameters for common algorithms. 
The standard approach to tuning ridge regression, LASSO, or the elastic net methods is grid-search. 
However, as the authors note in the classification setting, some model choices, like thresholding, can induce discontinuities in the tuning objective and make grid-search unreliable.
Thus, developing better alternatives to grid-search is a important topic. 

The theoretical bounds are novel and cover a range of important settings.
I was particularly interested to see the online-learning results.
The only two potential issues I see with this work are implementability and the focus on problem-sample complexity, rather than example-sample complexity.
The apparent non-implementability of the actual methods for tuning the regularization parameters is somewhat disappointing, but not too surprising given the nature of the results.
And, while the authors state that problem-sample complexity is more common, I think the problem sampling (which covers cross-validation) to be far more interesting. 

### Writing

The paper is very well written. 
I found only a few typos (see Minor Issues below).
I particularly appreciate that the authors take care to give intuition for each theoretical result as well as discuss their implications. 
Congratulations on a very well-written paper.

### Theory

**Soundness**: This paper is outside of my core research area, so I'm not an expert on the theory. However, I briefly looked through the appendices and saw no major issues. 

**Implementability**: My understanding from the discussion is that the methods for tuning $\\lambda$ are not implementable (see Questions). 
Thus, while the paper presents "efficient algorithms" (Line 402), efficiency is only in the sense of sample complexity, rather than computational complexity.
I don't think this is an important issue, but I suggest the authors either comment on the complexity of tuning $\\lambda$ in practice, or clarify that they mean efficiency only in terms of samples. 


### Experiments

N/A


### Minor Comments and Typos: 

- Line 263: "rational functions of bounded degrees ." -- remove extra space before the period.
- Line 286: "$\epsilon$-approximation of the loss corresponding parameter selection with arbitrarily..."  --- I don't understand this sentence; perhaps a word is missing?
- Line 369: "only polynomially many problem samples to generalize well..." -> "only polynomially many problem samples are required to generalize well"
questions: - Theorem 3.2/Theorem A.1: Is this result constructive or does it only give the existence of an algorithm?
    For instance, I agree with the claim that "our results answer the question ‘how much 288 cross-validation is enough’ to effectively implement the above techniques", but this is separate from carrying out the optimization procedure in practice. 

- Algorithm 1: The optimization domain $C$ appears to be an uncountable set, in which case the density function $w_i$ defines an improper distribution (at least initially) and maybe highly discontinuous during execution of the algorithm. 
    As a result, Algorithm 1 appears to be unimplementable --- is this correct?

- Are there any lower bounds for the sample complexity of learning $\lambda$ in the distributional setting (regression of classification)? If so, it would be excellent to compare Theorem 3.2 to these rates. If not, it might be nice to comment on the challenges in developing these bounds. 
limitations: The limitations are properly addressed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the validation loss of the elastic net as a function of its two hyperparameters, $\lambda_1, \lambda_2$. The authors allow "validation loss" to be fairly general: it is a function that maps a dataset and a setting of $(\lambda_1, \lambda_2)$ to the validation loss of the elastic net. They characterize this function as a piecewise rational polynomial as a function of $(\lambda_1, \lambda_2)$. They use this characterization to show that, given a set of validation losses and a distribution over this set (e.g. in leave-one-out cross-validation, the validation losses are the leave-one-out losses with the uniform distribution), a possibly small number of draws from this distribution are needed to minimize the average validation loss within $\epsilon$ accuracy. The authors go on to show that validation losses can be minimized in an online setting, where we view each validation loss one-by-one. Finally, the authors prove similar results for binary classification, where classification is done by thresholding the predictions of the elastic net.
strengths_and_weaknesses: **Strengths**
I think the technical contributions of this paper are pretty strong and original. As far as I know, no one has given this exact a characterization of the loss landscape of things similar to cross-validation for the elastic net. I can see some interesting future work building off of this paper -- e.g. what do the individual pieces of the loss look like? The author's observation about how much subsampling of leave-one-out CV is needed to get an accurate approximation is interesting as well. I actually think this is one of the most immediately practical pieces of advice from this paper, and might warrant a little more highlighting (e.g. as a corollary). I can't really comment on the strengths of their results about online learning, as I'm not as familiar with that literature (in particular, $\sqrt{T}$ expected regret for $T$ problems sounds like a lot, but maybe this is near the best you can do?).

**Weaknesses**
I think there are two main directions for improvement of the paper. First, I think the authors have slightly oversold the weakness of their assumptions, and should tone down those claims a little bit. Second, the writing was pretty dense and could use some more discussion and careful definitions.

On the assumptions required for the authors' results:
- The abstract states that the results do not require "strong assumptions on the data distribution". Assumption 1 (that the covariates and responses are all bounded) is definitely not a weak assumption. I think it wouldn't be unfair to say this is a "strong" assumption, as this disallows, say, a well-specified model in which responses are linear functions of the covariates with Gaussian noise.
- The results are stated as being completely independent of data distribution (e.g. in "Theorem 1.1 (Informal)"). However, a number of the lemmas used (Lemmas B.2, B.3, and C.1) require the columns of the data matrix $X$ to be in general position. First, this condition should be stated in the results using these lemmas (e.g. in the statement of Lemma 2.1). Second, it should be clarified in exposition that the paper's results only apply to sets of problems / distributions over problems with covariate matrices with columns in general position. 


On the writing being dense: The paper is pretty technical and uses a number of concepts from algebraic geometry and learning theory. These concepts are sometimes unexplained (e.g. just a definition is given) or lack a definition altogether. I think the results in this paper could be of interest beyond the learning theory community or algebraic statistics community, and so these concepts should be better explained (I think this is especially true of the concepts from algebraic geometry, which I suspect very few NeurIPS readers / attendees have experience with). Here are the things that stood out to me:
- Piecewise structured functions could use a simple English description.
- Pseudo-dimension should be defined and briefly explained. The abbreviation PDIM should also be explicitly defined.
- Semi-algebraic sets and algebraic curves should be defined.
- A precise statement of Bezout's theorem should be given in the form that is applied here (or, at least, a reference).
- I thought the definition and explanation of $\beta$-dispersion was really clear and helpful. 

**Miscellaneous things**
- I think Lemma C.2 needs some conditions to ensure $A^T A + \lambda I$ is invertible (what if $A$ is low rank? what if $\lambda = -5345$?)
- Line 215: "based on the observation above" there are many observations preceding this statement; it's not immediately clear which one this refers to.
- What are the asterisks in the proof of Lemma 2.1 (around line 218)? Are these just typos? An asterisk appears on $\lambda_1$ around line 223 as well, and then disappears in the next equation.
- "Using simple algebra, the denominator..." Definitely $\mathcal{E}$ depends on $\lambda_1$ and $\lambda_2$, and it's not immediately clear to me why that dependence gets canceled out in this expression. I think a proof should be given here.
- Algorithm 1 is actually never discussed in the paper. I'm guessing it's the algorithm from Theorem 3.3, but this should really be made clear (and discussed).


questions: - Can the authors provide a proof for the statement "using simple algebra, the denominator..."? 

I also have a few questions relating to the meaning of the author's results.
- Is the algorithm in Theorem 3.3 just Algorithm 1? It's probably worth stating this if so. As-is, Algorithm 1 isn't really discussed in the paper.
- One of the claims of Theorem 3.3 is about the $\beta$-dispersion of a series of functions. Why is this something readers should care about (i.e. why have the authors put this in the theorem's statement)?
- On lines 235-237, the authors state that they have solved the problem of optimizing the complex validation loss as a function of $(\lambda_1, \lambda_2)$. Which of their results back up this statement? It seems like Theorem 3.2 is about the number of validation samples required, and Theorem 3.3 has error growing with the square root of the number of samples.
- The authors state that their "assumption of smoothness [on $y$] is much weaker than sub-Gaussian noise assumptions in the literature." But this smoothness assumption is paired with assuming $y$ is a bounded random variable; isn't this much weaker than sub-Gaussianity, as boundedness implies sub-Gaussianity? 
- What exactly does it mean in Theorem 3.3 that $l_1, \dots, l_T$ are "independent"? Are we assuming the existence of some distribution $\mathcal{D}$ over losses, and $l_t$ are sampled i.i.d. from $\mathcal{D}$? This should be stated more precisely.
limitations: I think the authors have addressed the limitations of their work, with the exception of a few of the points already discussed above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors introduce a theoretical result that bounds the number of problems
needed to obtain a particular accuracy of $\lambda_1$ and $\lambda_2$ in
hyper-parameter optimization for the elastic net for both offline and online
learning.
strengths_and_weaknesses: - The paper seems to be theoretically sound and follows a logical progression.
- The literature section on exact (homotopy) methods for the elastic net and
  lasso is lacking and only insofar as I can see included the LARS paper at the
  moment.
- ~Section 2.1 and Lemma 2.1 seem to me to be related to the work in [1] and it is not quite clear what
  the novelty and enhancements of the current work are.~
- The bound on the number of problems needed for a certain accuracy in
  estimating $\lambda_1$ and $\lambda_2$ would be a useful addition, although it
  is not clear that the bound is useful in practice.
- Section 4 does not seem to address a useful problem. Classification with the
  ordinary (least-squares) elastic net is not a standard (or indeed useful) approach
  to classification as compared to elastic net-regularized logistic regression.

[1]: J. Mairal and B. Yu, “Complexity analysis of the lasso regularization path,”
    in Proceedings of the 29th International Conference on Machine Learning,
    Edinburgh, United Kingdom, Jun. 2012, pp. 1835–1842. [Online]. Available:
    https://icml.cc/2012/papers/202.pdf
questions: - ~The authors in [1] state that the regularization path has at worst $(3^p +
  1)/2$ segments. But you say, if I am understanding correctly, that it is
  exactly $3^p$ (l. 587). Perhaps I am missing something, but why is your result
  different? Should there be an O there?~
- ~Why is there only a proof sketch and not a full proof for theorem 3.1?~
- If I understand correctly, you arrive at your bound on the number of problems
  needed by assuming the worst-case situation in terms of path complexity. What
  is the impact of this on the tightness of the bound (and practical
  usefulness)? I would assume that this would make the bound conservative (since
  in practice no paths for real data contain $3^p$ segments).
limitations: - Consider demonstrating with a simple example what your results imply in terms
  of the number of problems you need to solve for some real data set. Also show
  via some simple experiment that standard approaches (such as 10-fold CV) can
  fail (as you claim they do) and that your method solves this problem.
- Move section 4 to the appendix since ordinary lasso classification is not a
  standard or useful model.
- ~State clearly what your contributions are in relation to previous work such as
  [1, 2, 3, 4] and cite their work where appropriate. In particular there
  seems to be overlap with [1] that isn't accounted for in the work.~
- ~Consider amending the literature section in the paper by including some or
  all of [1, 2, 3], and [4] regarding homotopy methods for the lasso.~
- Include at the very least [5] in your literature section on hyper-parameter
  tuning for the lasso.
- It is not standard to call the Elastic Net (or elastic net) ElasticNet.
  Consider adding a space.
- l. 58. There should be a period at the end of the sentence.
- l. 77. w.h.p. is not a standard abbreviation. Consider spelling it out.
- l. 208. There should be a period at the end of the equation.
- l. 271. There should be a period after $\epsilon$.
- l. 386. There is an extra space after "values".

[2] P. Garrigues and L. Ghaoui, “An homotopy algorithm for the lasso with online
    observations,” in Advances in neural information processing systems 21,
    Vancouver, Canada, Dec. 2008, vol. 21, pp. 489–496. [Online]. Available:
    https://proceedings.neurips.cc/paper/2008/file/38af86134b65d0f10fe33d30dd76442e-Paper.pdf

[3] D. M. Malioutov, M. Cetin, and A. S. Willsky, “Homotopy continuation for
    sparse signal representation,” in Proceedings. (ICASSP ’05). IEEE
    International Conference on Acoustics, Speech, and Signal Processing, 2005,
    Philadelphia, USA, Mar. 2005, vol. 5, pp. v733–v736. doi:
    10.1109/ICASSP.2005.1416408.

[4] M. Osborne, B. Presnell, and B. Turlach, “A new approach to variable
    selection in least squares problems,” IMA Journal of Numerical Analysis,
    vol. 20, no. 3, pp. 389–403, Jul. 2000, doi: 10.1093/imanum/20.3.389.

[5] Q. Bertrand, Q. Klopfenstein, M. Blondel, S. Vaiter, A. Gramfort, and J.
    Salmon, “Implicit differentiation of Lasso-type models for hyperparameter
    optimization,” in Proceedings of the 37th International Conference on
    Machine Learning, Nov. 2020, pp. 810–821. Accessed: Jun. 27, 2022. [Online].
    Available: https://proceedings.mlr.press/v119/bertrand20a.html
review_title: null

Meta-review: metareview: The reviewers agreed that this paper should be accepted -- it studies an interesting and in someways "overlooked" problem and seems like it could be a starting point for others to build on. The paper did have some weaknesses. For example, we feel that the lack of experimental results is a missed opportunity -- the reviewers feel the paper would be made stronger by including at least a simple example where the standard approach of grid search + CV fails. Without such an example, it is a bit hard to be convinced of the importance of the problem being studied. 
confidence: Certain
Decision: Accept