Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors study M-estimators with convex penalties. They give algebraic forms for derivatives of the estimator with respect to response $y$ and the design matrix $X$. They describe the distribution of residuals or certain functions of residuals. Given a loss function and penalty (with tuning parameters) they propose a criterion that can effectively approximate the out-of-sample error. This criterion can be computed without the knowledge of the covariance matrix $\Sigma$ (rows of $X \sim N(0,\Sigma)$). They give finite sample bounds that show how fast the criterion converges to the out-of-sample error. 


main_review: The main results are all interesting. The manuscript sets up and explains the results in good detail. 

Following are some limitations of the work. The design matrix $X$ is assumed to have Gaussian rows. This may not be true in practice, and it is not clear how good the criterion is without this assumption. The penalty $-\beta^T \Sigma \beta$ is assumed to be strongly convex. Therefore the results are not applicable when the estimator uses $\ell_1$ type of penalties.

Even with these limitations, the contributions are significant.

limitations_and_societal_impact: I cannot see any negative societal impact due to this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the derivatives of regularized M-estimators and distribution of the residual. 
These results give rises to a new novel adaptive criterion for tuning loss and penalty function.
Numerical experiments are conducted on various models to validate the theoretical result.
main_review: This paper is well-written and mostly clear.
The theory and method in this paper has many benefits, including general loss and penalty, $\Sigma$ and $\varepsilon_i$ agnostic criterion.
I am not an expert in this area and cannot judge the novelty and significance.

Question:
1. In the Theorem 3.1, it says $Z_i\sim N(0,1)$, but the dependency between $Z_i$ and $X$ is not clarified. Is it better to say  $(X_1,...,X_n,Z_i)\sim \otimes_{i=1}^n N(0,\Sigma)\otimes N(0,1)$ to explicitly show the dependency?
2. In line 417, how Proposition 7.1 is applied in the proof?

UPDATE: I thank the authors for addressing my questions and I decided to keep my score.
limitations_and_societal_impact: This article clearly describes the assumptions needed for each theoretical result.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper is dedicated to the analysis of robust linear regression, where the proposed estimation is based on sparse M-estimation. The statistical criterion corresponds to a penalised M-estimation problem, where both the non-penalised loss function and penalty function are assumed convex. The contributions of the paper can be summarised as follows:
- the authors provide a criterion for the optimal selection of the non-penalised loss and penalty function so that some out-of-sample distance, say D, is minimal. 
- the authors quantify the behaviour of the penalised estimator \hat\beta using quantities depending on the observations only (idest no unknown quantities such as true sparse support) in a regime where p/n has finite limit.
- some explicit derivative formulas of the penalised estimator are provided. 
- the distribution of the estimated residuals is provided, which allows for a selection of the tuning parameter for regularization.
- the authors derive an approximation formula of the distance D. 

main_review: As a general comment, the idea of proposing a criterion for an optimal choice of both penalty and loss functions is interesting. There was an effort to derive theoretical results. That being said, I would have several concerns. I hope my comments will be useful.
- On the clarity: 
1) I feel there is a significant lack of details supporting the underlying motivation and intuition of the proposed methodology. What is clearly the purpose? Do the authors aim at selecting a penalty function so that variable selection can be satisfied in a high-dimensional regime? Or rather than interpreting the model, do the authors aim at gaining prediction accuracy? 
2) On the related works: the authors mention in the abstract "adaptive criterion to selection tuning parameters of penalised M-estimators". In the rest of the paper, I would have expected to find some theoretical results giving some explicit rates of \lambda to ensure the consistency of the penalised parameter. With this in mind, Loh's work (2017, "Statistical consistency and asymptotic normality for high-dimensional robust M-estimators") treated the problem of robust estimation with sparsity assumption and proposed a penalised M-estimation setting with non-convex penalisation. It would be relevant to discuss this further.
3) The simulation experiment seems like an afterthought and lacks further explanations: what properties of the proposed methodology are illustrated by the simulations?  
- On the model assumptions: the key assumption is the convexity of both the loss function and the penalty function. The problem of convex penalty functions is that they do not provide good performances in terms of bias and variable selection. There are two ways to solve this issue: considering a two step procedure for incorporating stochastic adaptive weights in the penalty and alter the rate of \lambda; considering non-convex penalty functions as in Loh (2017). Should a non-convex penalty be chosen, the theoretical analysis might probably be altered. Would it be possible to consider non-convex penalty functions? How would it change the theoretical framework? 
I am also wondering if this would be possible to relax the convexity of the loss function (which is not guaranteed especially in a high-dimensional regime) and assume alternative regularity conditions (such as restricted eigenvalue conditions).
- On the theoretical results:
The authors stated in Section 1.2 that their work is within the regime "p/n ---> finite limit". In assumption 1, the authors assume p/n <= \gamma, for \gamma >0. In theorem 3.2., a large sample distribution is provided when n --> \infty. How is the dimension p treated? Does the theorem hold when n,p --> \infty with the scaling behaviour p/n --> \gamma? It would be relevant to discuss this issue further.
In Theorem 3.1, the matrix \hat{A} is given by Theorem 2.1: there, a specific assumption is stated on \|\Sigma^1/2 \hat{A} \Sigma^1/2\|_op: such quantity depends on the dimension p; how does the inequality \|\Sigma^1/2 \hat{A} \Sigma^1/2\|_op <= 1/(n\mu) behave with respect to p? 


limitations_and_societal_impact: I think the authors proposed a interesting way to specify a criterion for loss/penalty functions and their method is supported by some theoretical results. Please see my comments above concerning the limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Finding the right parameter when doing robust estimation is a recurring problem in the robust community. This article propose to choose the parameters in a robust regularized linear regression model by minimizing a completely data-driven criterion. This criterion is shown to be a good approximation to the out of sample error, this is also illustrated on practical experiments.
main_review: The article is clear and well written, the results are very important in the robust machine learning community as it is often a problem to tune the estimators to a specific dataset. Most tuning procedures require knowledge on the variance of the inliers or a large computational effort (for instance through Lepski's method). In this article, the tuning is computationally tractable and the theory prove that this tuning is efficient with respect to the out of sample error.
limitations_and_societal_impact: The main use for M-estimator is in robust statistics, however there are some limitations for the use of these results in robust statistics.  The article suppose Gaussian design matrix which is rather restrictive in practice and which shows that this article is about robustness in the target space but not in the feature space. A very important extension of this work would be when the design is heavy-tailed. Similarly, even though the error $\varepsilon$ can be anything as long as its distribution is continuous, there cannot be outliers because the outliers would change the $\beta^*$ and the criterion would then be non robust (for instance . This is a limitation for use in robust machine learning), this article is only valid for Gaussian design and uncorrupted, heavy-tailed target variable $y$.  This can be seen by the fact that the criterion depends on $r$ and if $y$ is corrupted or $X$ is corrupted, there can be some very large values of $r$.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies M-estimators in linear models, with convex and gradient-Lipschitz loss function and a convex penalty. 

Main contributions: 
1. The authors provide a criterion to select tuning parameters (the loss function and the penalty function) of M-estimators, such that minimizing the criterion provides a proxy for minimizing the out-of-sample error, since the criterion is an approximation of the out-of-sample error up to a constant shift. One advantage of this criterion is that it does not require the prior knowledge of the covariance matrix of the design and the noise distribution. 
2. The authors provide simulation results that confirm theoretical findings.
main_review: The paper is well organized. Some comments:

1. The criterion in Eq (2) exists for general $(\rho, g)$, while in the experiments it is only used for tuning the parameter with Huber loss and with Elastic-Net penalty. Some related questions on this: (1) If there exists an optimal estimator $\hat{\beta}$ that minimize the out-of-sample error? Does it has the form as Eq (1) for some $(\rho_0, g_0)$? (2) If the answers to (1) are both 'yes', is it possible to show that $(\rho_0, g_0)$ minimizes the criterion (over some space of $(\rho, g)$)?
2. The simulation part demonstrates how the criterion is calculated and its approximation accuracy of the out-of-sample error. One important missing part is the comparison with other parameter tuning methods: could this method outperform other parameter tuning methods?
3. The simulations in the appendix suggests that the results generalize to non-Gaussian design. What is the main technical difficulty of extending the results to non-Gaussian design?


limitations_and_societal_impact: N/A
review_title: null

Meta-review: All the reviewers agree that the paper makes interesting contributions to the field of high-dimensional statitics. The authors provided informative answers to the questions raised by the area chair and the reviewers as well. The area chair has a positive view of the paper as well and believes that the paper should be eventually published at Neurips or similar venues. However, the paper suffers from a weakness; It missed some of the related work that seemed quite related to the contributions of the paper. The authors provided interesting conceptual comparisons in their response to the reviewers' comments. However, for the following two reasons the paper is rated below the other papers presented at Neurips:

1. A proper and more detailed comparison with related work should be part of the original paper so that all the reviewers can judge the paper better. 

2. A more quantitative and numeric comparison is required to help reviewers see how the paper's contributions are compared with the existing methods. 

Based on these issues, the reviewers and the area chair have rated this paper slightly below the other papers that have been accepted at Neurips. However, we would like to encourage the authors to submit this paper to future venues. It seems that the paper can become a major contribution to the field of high-dimensional statistics. 
Decision: Reject