Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: Building off recent work by Sur & Candes (2019), this paper proposes a method for computing point estimates and well-calibrated confidence intervals for high-dimensional logistic regression (specifically, when the ratio $d/n$ converges to a constant as $n \to \infty$). 

main_review: Originality: The method builds on the work of Sur & Candes (2019), but solves a critical issue with that work: how to reliably and quickly estimate a key quantity needed to construct the point estimate and confidence intervals. The approach is simple to use but seems quite original. 

Quality: The paper is quite non-trivial from a technical perspective. But the theory isn’t just there for theory’s sake, as it guarantees asymptotic validity of the proposed method. The strengths and limitations of the theory and method are addressed appropriately. The experiments do a good job of validating the correctness via simulations and practical benefits via real-data examples but don’t over-promise. Overall, I found the paper very compelling

Clarity: The paper is incredibly clear and well-motivated. 

Significance: Applying logistic regression when the number of predictors is of the same order as the number of observations is extremely common. I could imagine the proposed method being widely adopted in place of standard logistic regression point estimates and CIs. 

## Update after author response

I think the authors have done a good job addressing the other reviewers concerns, so I maintain my original score. 
limitations_and_societal_impact: These are appropriately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper is based on a work by Sur and Candès (2019) who propose a way to correct the bias of the MLE estimator and correct confidence intervals and p-values for logistic regression. The results in Sur Candes are asymptotic results n \to \infty but assume a fixed aspect ration $p / n = \kappa$ where p is the number of regression coefficients. The results have  been refined in Zhao et al (2020),: in Zhao, the regressors are Gaussian but with an arbitrary covariance matrix whereas the regressors are spherical Gaussian in Sur Candes  (the distribution of the regressor plays a key role to compute the correction factor). 

The original algorithm by Sur and Candes require to estimate the signal strength, defined as the $\gamma^2 = Var(\beta^T X)$. This is of course challenging because the parameter is unknown. The authors proposed to use the "corrupted signal strength, defined as $\Var(\hat{\beta}^T X)$ where $\hat{\beta}$ is the MLE (it is claimed that the corrupted signal strength has been introduced in Zhao (2020) but on the arxiv version of this paper I did not find such quantity). The correction factors can be computed by solving an equation to involving the corrupted signal strength. The purpose of this paper is to compute an estimator of the corrupted signal strength. 
main_review: 
Originality:  The paper follows on a very interesting problem (the corrections to MLE of logistic regression in the limit of large number of variables - large number of samples) that has been theoretically investigated by [1]. The corrections provided by [1] are computationally expensive and impractical. 
The main contribution of this work is providing a cheaper estimate of those corrections, making it more practical to high dimensional problems. The idea of viewing Var (X^{\top}\beta), the true signal strength, as a function of the estimated log-odds variance Var(X^{\top}\hat{\beta}) is powerful. This immediately helps the authors come up with a new estimator for the signal strength based on leave-one-out analysis. The main contribution is to realize that (3.2) is a consistent estimator of \eta^2. This is a neat idea. 

If considered as an applied paper, I think this paper has potential.  the numerical experiments should be more stressed with applications to multiple datasets to show the relevance of this work in practice, and theoretical computation of computational complexity with respect to [1]. 

minore comment: The authors propose to investigate the broader implications to ML but this is left for future works. This is definitely a good research program ! but very ambitious for a  9 pages paper !

Clarity: 
- The first half of the paper presents a synthesis of the results of Sur and Candes (in the case of spherical Gaussian regressors). 
The results are well presented and follow very closely the papers by Candes. 
- The action really starts on page 5 with the reparametrization and definition of the  corrupted signal strength. The paper refers to Lemma 3.1 of Zhao (2020) but Lemma 3.1 establishes the result presented in equations 2.6 and 2.7 and I did not find any reference to the notion of corrupted signal strength in Zhao's paper (or else this notion appears under another name, which is not excluded)
- The first result obtained by the authors is theorem 1, which establishes the consistency of the leave-one-out (LOO) estimator of the corrupted signal strength (in the case of correlated regressors). This is an interesting result (I did not have time to check the details of the proof). 
- Of course, the LOO estimator is impractical because it requires solving n logistic regression problems. The authors propose a feasible solution by "approximating" the LOO. . The approximation adopted and the discussion is classical (note that H does not seem to be defined in eq 3.3) - I do not really understand the meaning of remark 1 - 

Correctness: The paper is well written.  The theorem proofs should follow almost directly from the proofs of earlier results in Sur and Candes (2019). So, I would not say that theoretically there is much innovation. Again, I highlight that realizing Thm 1 is neat.

Minor comments-  authors use expressions such as: apparently (line 215), potentially (line 321) which give the impression of "guess work", while these assertions required to be properly justified. It would be better if the authors could rephrase those and take time to write detailed justifications of these claims.

Additional comments: 
- I would strongly recommend including the original references that introduced the leave-one-out analysis in high-dimensional statistics: https://www.pnas.org/content/110/36/14563 , https://www.jstor.org/stable/42713153 
The current lines 190-209 should cite them. 
(By the way the derivation in these lines seems exactly the same as some equations in Sur and Candes (2019) and not inspired by. In this light, I feel the authors should cite the appropriate places a bit better.) 

- The authors of the paper are probably not aware of the work [Mai] “A large scale analysis of logistic regression: asymptotic performance and new insights. X. Mai et al (ICASSP’19)”  as it is highly related to their work, and not cited. [Mai] addresses the problems tackled by this work, and even in a more general setting, with regularization and covering under-parametrized and over-parametrized regimes (in the high dimensional,  linearly proportional number of samples-dimension setup). In particular [Mai] consider an elliptical non-centered Gaussian distribution, a loss with regularization, and no restriction on whether (d>n or d<n). More importantly, from Theorem 1 in [Mai], the parameter \gamma (which the current work goal is to estimate) does not appear in the asymptotic distribution of \beta. All the parameters in Theorem 1 [Mai] can be estimated consistently and cheaply. Could the authors please provide in which way their work goes beyond [Mai]?
limitations_and_societal_impact: I do not see iany limitations or negative societal impact. The scope is limited (to logistic regression with correlated Gaussian covariate) but at least, the impacts are not negative
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose to make practical the high dimensional analysis of the logistic regression performed by [Sur and Candes]. Indeed, [Sur and Candes] proved that logistic regression in the classical regime (number of samples going to infinity while the dimensionality is fixed) is biased and must be corrected for modern applications where the number of samples and their size are of the same order of magnitude. However, in [Sur and Candes]'s paper, the asymptotic analysis depends on parameters that are difficult to estimate since they depend on ground truth parameters (regression parameter $\beta$). The authors of the present article propose a fast estimation method.
main_review: **** Overall review *****

1-Strong points

The article is well written and the motivation is quite clear. The code is also provided for reproducing the results.

2-Weak points

The originality of the work is quite low.  The large dimensional analysis performed in [Sur and Candes] represents the main novelty and the present paper only provides an estimate for a parameter that will only be valid for Logistic regression. The contributions for a conference like NIPS is either:

(a)-Provide a generic framework for estimating quantities involving quite huge dependence and apply it on more than one application  (more than just logistic regression in binary case) so that the impact is quite important

(b)- provide both the large dimensional+ Estimation procedure as performed in [Sur and Candès] and as is generally the case in the large dimensional analysis of machine learning algorithms. The large dimensional analysis is generally the most contributing part.

Due to the low theoretical part, the authors might compensate by more experiments (in the supplementary materials for example) to show the broader impact of their methods.

**** Detailed comments ******

-In Theorem 1, the notation $p$ has never been used previously. Isn't $d$ instead?

-In theorem 1, Ave_j should be defined.

-In line 188, the hessian should be defined directly after equation (3.3) and not defined in the proofs afterward.

-In line 325, that repeated

-The work did not mention multi-class classification which is of big interest.

-I think it is important to compare the algorithms from a performance point of view to ProbeFrontier.

-The authors should also plot the running time of the classical logistic regression in Figure 5 to justify that the proposed scheme has the same complexity as the classical one.

-The author should also discuss the invertibility of $H$? Does the method work in all the cases? (Specifically in high dimension low sample size regime ($n<d$))


limitations_and_societal_impact: The limitations of the work are not clearly mentioned. However, the authors could discuss more on the invertibility of H, the conditioning of H, discuss multi-class extension which is missing.
review_title: null

Meta-review: Following the discussion phase, the reviewers and myself have reached a consensus on this submission, and all agree on its interest to the NeurIPS community, its significance and its potential impact in disseminating earlier ideas to a broader group of practitioners, through an astute algorithm.

To quote from the discussion with the reviewers: the submission builds on the solid foundations of Sur and Candès, and delivers non-trivial theoretical insights on a new (provably correct) algorithm, which we anticipate will be impactful for practitioners of logistic regression in high dimensional settings.
Decision: Accept (Spotlight)