Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: # Summary

The paper studies truncated linear regression when the additive error follows a zero-mean normal distribution with unknown variance. 
This setting generalizes the work of Daskalakis-Gouleakis-Tzamos-Zampetakis-2019, who assumed the knowledge of the variance of error.
This work provides two statistical rates for the joint estimation of the regressor (w) and the noise variance (\sigma) in Theorem 3.2.
The rates in Theorem 3.2 are achieved using a SGD-without-replacement algorithm on the negative log likelihood after a suitable re-parameterization, which is also used in Daskalakis-Gouleakis-Tzamos-Zampetakis-2019.


main_review: I think the paper studies an important problem of generalizing the work of Daskalakis et al. (2019) to the setting of unknown variances. As the paper claims, this requires non-trivial ideas and natural approaches fail.
As the joint optimization of w and sigma is non-convex, the paper performs a re-parameterization of the variables to induce convexity. This re-parameterization is similar to the one used in Daskalakis et al. (2018).

Overall, I think the paper has a few good ideas but needs additional work in terms of presentation and clarity. Some important details are not clear and  details are hard to follow. Thus I recommend weak reject for now, and I will improve my score if the following comments are addressed:


+ Lines 104-131: I really liked the idea of  explaining why natural approaches to extend Daskalakis et al. (2019) fail. However, a lot of details in these lines are not clear to me. In particular, the sentences: (i) "It is clear that (Line 118)..." and (ii) "It is easy to see that (Line 125) ...". I would appreciate if the authors can explain these cases as formal claims in the supplementary text with the omitted details. 

+ Theorem 1.5 (Asymptotic normality): What does it mean for a random variable $X$ to converge to a Gaussian with a covariance that depends on $X$? That is, $X \to^d \mathcal{N} (\mu, \Sigma_X^2)$? How can the covariance matrix itself be random? I skimmed through Leluc and Portier (2020) and they show convergence to a normal distribution that depends on the true optimizer.


**Minor points**

+ As Leluc and Portier (2020) heavily influences the  asymptotic normality result, they should be cited appropriately in the main paper.

+ The large length of some sentences affect readability; for example, Line 17-21. Line 28-33.

+ Add a citation for the Line 157-158.

+ Please add the details for the convexity of $D_r$ after Definition 3.1 (or point to the supplementary material). It is not obvious (to me at least) at the first look. 

+ Refer to Algorithm 3.1 in the beginning of Theorem 3.5. It is not clear in the beginning what is $u^{(t)}$.


+ I am not sure if the phrase "statistically efficient" (without any quantifier) can be used to describe the rates in Theorem 3.2 as they may not be optimal, i.e., may not achieve efficiency.

+ Add a small claim for the typical values of b (and the corresponding sample complexity) in Assumption 2.4 for the (rescaled) multivariate normal distribution.

+ Line 177: What is the difference in the notation? 



+ Assumption 1.2 seems stronger than Assumption 1 in Daskalakis et al. (2019).

+ Lines 101-103: How does Lemma 7 in Daskalakis et al. (2019) imply the claim in Lines 101-103?



+ Line 35: Typo: needed, 

+ Define $H_x$ in (4.3)?

+ Line 253-254: Where is this in supplementary material. In general, please point to the specific section when referring to the supplementary material.

+ Line 264: 'initial' should be replaced by 'optimal'.

# Update

I thank the authors for their detailed response and discussion.I am thus raising my score from 5 to 7. Repeating the sentiment from my original review, I would strongly suggest improving the presentation and clarity ---both technical and non-technical aspects. If the paper is accepted or for the new submission, I hope the authors would follow the suggestions pointed out in all of the reviews to improve clarity and presentation. In particular, I suggest the following:
1. Add as formal claims why obvious approaches won't work (with omitted details in the supplementary material).
2. Improve the notation for asymptotic normality
3. Changing the phrase statistical efficiency
4. Improve the structure of the paper as other reviewer suggested
5. Citing Leluc and Portier before stating Theorem 5.1 and Theorem 1.5. 
6. And other minor/major comments 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper extends the study of Daskalakis et al. (2019) into the setting where the noise variance is unknown, and gives two theoretical contributions. First, the paper proves the convergence of the projected SGD algorithm when applied to minimizing the population negative log-likelihood function. Second, the paper provides the asymptotic normality of their estimator, from which the confidence regions for the estimator can be computed.


main_review: As a direct extension of Daskalakis et al. (2019), the novelty of the paper seems moderate, while this is somewhat compensated by a clear discussion on the difference from Daskalakis et al. (2019) in the beautifully written intro, and by nontrivial theoretical development using statistics and optimization. 

Even though the authors claimed their efforts in proofreading the paper, there are several issues that concern me in writing:
  1. The authors use both n and N to represent the number of samples. For example, it is n in Assumptions 1.3, but it is N at Lines 126 and 139. Moreover, they use N to represent normal distribution at Lines 335, 342, and 343. Finally, they use N to mean the number of iterations at Line 68 (I guess), and n at Line 346 to mean convergence rate. In Algorithm 1, do the authors mean n samples and N iterations? These are very confusing, please clarify.
  2. There are certain repetitions on writing. For example, the assumptions are repeated. In Theorems 3.5 and 3.6, (i) and (iii) are repeated. In Theorem 3.6, one can simply reference (i) and (iii) of Theorem 3.5. Lines 171-173 can be simply replaced by Lines 247-256.
  3. In assumption 2.4, there is a full stop missing. And there is a typo at Line 243.
  4. Section 3 is called "Log likelihood functions and feasibility". But the content is about projected SGD and Theorem 3.2.
  5. I would define the log-Likelihood function much earlier, rather than in Section 4.1, and I would put the computation of its gradient and Hessian into the supplementary.
  

I have the following two questions.
  1. Please explain the definition of D_r. In particular, how does the semidefinite constraint arise? What is the intuition here or does it follow directly from Daskalakis et al. (2019)?
  2. At the beginning of Section 4.5, please explain why to split the samples into 3 parts. Is it more natural to compute the OLS and run the SGD using all samples? If this can not be explained theoretically, please have an ablation study on splitting or not.

------ UPDATE ------

The authors have addressed my concerns. Thus I raised my score to 6.

limitations_and_societal_impact: I have not known any potential negative societal impact of the present work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors investigate truncated linear regression, i.e., inferring the linear model parameters when only a subset of the data can be observed. The primary contribution is that they provide error bounds on the estimators for model parameters when the noise variance is unknown and show that there exists a polynomial time algorithm to find the estimate (noise variance included).   They validate their results on synthetic data. 
main_review: 1. Originality/significance: the topic of truncated regression is an interesting one that comes up in practice (whether or not practitioners consider it) and is certainly worthy of study. As the authors acknowledge and adequately cite, their work is an extension of Daskalakis et al. Although the main ideas are drawn from the work of others, the novelty of having unknown variance is significant and interesting.

2. Quality: in general, the quality of the work is good with technical rigor and writing that is easy to understand (with a caveat, see clarity below). The quality of the synthetic experiments leaves something to be desired since it isn't clear if performance is based on well chosen examples or the merit of the method. More details can be found in comments below. Since there is a theoretical basis to their work, this might not be much of a concern.

3. Clarity: although the writing is clear, the arguments and structure of the paper are circuitous and at times hard to follow. For instance, in section _3 Log likelihood functions and feasibility_ on line 167 it states that the log likelihood function is defined in Section 4.1; why include a section title as such only to defer until later? There are other issues such as restating assumptions in a similar form multiple times. The layout/placement of theorems and their connection to one another is difficult to follow. For instance, include theorems 3.5 and 3.6 in Section 4 and move computation considerations to discussion of algorithms. The paper's structure seems to be its primary weakness at the moment. 

### Minor comments
- line 24: range instead of rage?
- line 53: "needed" rather than "need"
- line 203: what is "folklore boosting"? Is it just what's described in the next sentence? 
- line 255: where exactly in the appendix can we find details to solve the computational problem?
- line 264: is "initial point" supposed to be "optimal point" here?

### Major comments, clarifying questions
- assumption 1.1: is $\beta$ generally known _a priori_ or is it chosen to be conservative? Given that theorem 1.4 depends exponentially on it, this seems like it could be an issue
- line 93: is the strong convexity bounded at the optimum alone or in some neighborhood about it?
- Section 2: much of the detail in this section is repetitive and could be treated more thoroughly/merged with the introduction. The detail is not so technical that it requires a new section.
- Section 3: the section title is _Log likelihood functions and feasibility_ but the log likelihood isn't introduced until section 4.1. Discussion of the algorithm here also seems out of place since the form of the objective, its gradient, and constraints haven't been introduced yet. Maybe introduce the log likelihood and feasible set here wait on discussion of algorithms until after the form of the problem has been set. 
- Section 4.1: see comment above. Also, in line 240, explicity stating the pdf for the truncated Gaussian is helpful for general reader and will also clarify where the MLE comes from. 
- Section 4.2: specify where exactly in the supplement computation problems are discussed. Perhaps spend more time discussing computational issues. 
- Section 6:
    * Experiment for figure 1: since $w*$ is fixed, what is it here and does the performance vary considerable for different $w*$? Also, it seems that given the symmetry in the problem, less might be lost by truncation. Does the performance deteriorate if truncated on both tails, e.g., $S = \{-1.5 \le y \le  2\}$? (is "unknown" is fig 3-5 in supplement the proposed algorithm )
    * I think figure 2a is intended to address issue above, but it is impossible to draw any conclusions from the image. Please include an image or data illustrating that is more easily interpreted. 
    * Experiments for figure 2: using different noise model, i.e., Laplacian, changes the MLE (example no longer agrees with theory) so I don't necessarily expect the algorithm to perform well. However, it is surprising that _truncreg_ outperforms as it does. What is the reason for this? 
    * Reasonably, what size problem can be solved with this method? What is maximum dimension attempted
    
================================= 
UPDATE

Thank you to the authors for their response to reviewer comments; they have helped improve understanding. I also agree that "statistical efficiency" is confusing and should be changed.

With the changes mentioned above, I have improved my rating from 6 to a 7. 


limitations_and_societal_impact: N/A
review_title: null

Meta-review: This paper studies high-dimensional linear regression in a truncated setting, where only examples with labels in a given set are observed.
Learning from truncated samples is a classical topic in statistics that has received renewed interest in the last few years. Prior work had given an efficient algorithm for this problem under the assumption that the additive observation noise has known variance. This paper gives an efficient algorithm for the broader, more realistic, setting that the variance of the noise is *unknown*. Handing unknown variance turns out to require non-trivial new ideas. After extensive discussion internally and with the authors, the reviewers agreed that this contribution merits acceptance to NeurIPS.
Decision: Accept (Poster)