Efficient Truncated Linear Regression with Unknown Noise Variance
Authors: Constantinos Costis Daskalakis
Patroklos Stefanou
Rui Yao
Emmanouil Zampetakis
Venue: NeurIPS 2021 Poster (2021)
Keywords: regression
theory of computation
truncated statistics
linear regression
truncation bias
stochastic gradient descent
asymptotic normality

Abstract: Truncated linear regression is a classical challenge in Statistics, wherein a label, $y = w^T x + \varepsilon$, and its corresponding feature vector, $x \in \mathbb{R}^k$, are only observed if the label falls in some subset $S \subseteq \mathbb{R}$; otherwise the existence of the pair $(x, y)$ is hidden from observation. Linear regression with truncated observations has remained a challenge, in its general form, since the early works of [Tobin'58, Amemiya '73]. When the distribution of the error is normal with known variance, recent work of [Daskalakis et al. '19] provides computationally and statistically efficient estimators of the linear model, $w$. 

In this paper, we provide the first computationally and statistically efficient estimators for truncated linear regression when the noise variance is unknown, estimating both the linear model and the variance of the noise. Our estimator is based on an efficient implementation of Projected Stochastic Gradient Descent on the negative log-likelihood of the truncated sample. Importantly, we show that the error of our estimates is asymptotically normal, and we use this to provide explicit confidence regions for our estimates.

Efficient Truncated Linear Regression with Unknown Noise Variance
Constantinos Daskalakis 'EECS and CSAIL, MIT costis@csail. mit. edu
Patroklos Stefanou EECS and CSAIL, MIT stefanou@mit edu
Rui Yao EECS and CSAIL, MIT rayyao@mit.c edu
Manolis Zampetakis EECS, UC Berkeley mzampet@berkelee edu
Abstract
Truncated linear regression is classical challenge in statistics, wherein label, y = w" x + E, and its corresponding feature vector, x E R are only observed if the label falls in some subset S S R; otherwise the existence of the pair (z, y) is hidden from observation. Linear regression with truncated observations has remained challenge, in its general form, since the early works of Tobin (1958); Amemiya (1973). When the distribution the error is normal with known variance, recent work of Daskalakis et al. (2019) provides computationally and statistically efficient estimators of the linear model, w. In this paper, we provide the first compu- tationally and statistically efficient estimators for truncated linear regression when the noise variance is unknown, estimating both the linear model and the variance of the noise. Our estimator based on an efficient implementation of Projected Stochastic Gradient Descent on the negative log- lieeliil of the truncated sample. Importantly, show that the error of our estimates is asymptotically normal, and we use this to provide explicit confidence regions for our estimates.
Introduction
common challenge facing statistical estimation the systematic omission of relevant data from the data used to train models. Data omission is a prominent form of dataset bias, which may occur for variety of reasons, including incorrect experimental design or data collection campaigns, which prevent certain sub-populations from being observed, instrument errors or saturation, which make certain measurements unreliable, societal biases, which may suppress the realization of certain samples, well as legal or privacy constraints, which might prevent the use of some data, In turn, it well-understood that failure account for the systematic omission of data in statistical inference may lead to incorrect models, and this has motivated long line of research in statistics, econometrics, and a range of other theoretical and applied fields, targeting statistical inference that robust to missing data; see e.g. Galton (1897); Pearson (1902); Pearson & Lee (1908); Fisher (1931); Tukey (1949); Tobin (1958); Amemiya (1973); Hausman & Wise (1977); Heckman (1979); Breen et al. (1996); Hajivassiliou & McFadden (1998); Mohan al. (2013); Balakrishnan & Cramer (2014).
In this paper, we revisit the classical challenge of truncated linear regression. As in the standard linear regression setting, we assume that the world produces pairs (ax(i), yy()) where each (1) IR*
"CD and PS were supported by NSF Awards 114-1741137, CCF-1617730, and CCF-1901292, by Simons Investigator Award, by the Simons Collaboration the Theory of Algorithmic Fairesss, by DSTA grant, 11 and by the DOE PhILMs project (No. DE-ACOS-76RLO11300
MZ was supported by NSF DMS- NMS-2023505 (FODSI)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is a feature vector drawn from some distribution P and its corresponding label y( is linearly related to 2((1) according to y() = w x + E(1), for both some unknown coefficient vector w' E IR and random noise e()) ~ NO, o²²), where o²² is unknown and c(() is i.i.d over all i. The difference to the standard setting is that we do not get to observe all pairs (xx*), ()) that the world produces. Rather, a pair (xx(), y()) is only observed if y()) E S, where S C IR is a fixed "observation set," that known or given to us via oracle access, i.c. we can query an oracle about whether or not some point belongs to S. If ( S, then (zx1), y)) is removed from observation. Our goal is to estimate w" and o from the pairs that survived removal, called "truncated samples."
Overview of our results. While both truncated and censored lincar regression are fundamental problems, which commonly arise in practice and have been studied in the literature since at least the 1950s (Tobin, 1958; Amemiya, 1973). there are no known statistical inference methods that are computationally efficient and enjoy statistical rates that scale with the dimension ic of the problem. Recent work of Daskalakis et al. (2019) has obtained such methods in the simpler setting where the noise variance 22 is known, Our goal here is to extend those results in two important ways. First, we study settings where x²2 is unknown, providing computationally and statistically efficient estimators for the joint estimation of w" and ~²² Moreover, we establish the asymptotic normality of estimators, and use this to derive confidence regions for our estimators. To achieve these stronger results we make some additional assumptions compared to Daskalakis et al. (2019). Namely, we assume that the covariates are sampled from some prior distributions, and we also make stronger assumption about the survival probability of our model as we discuss below. Other works that consider learning and regression problems with censored or truncated samples are Plevrakis (2021); Fotakis et al. (2020); Moitra et al. (2021); Ilyas et al. (2020).
We next provide informal statements of our results, postponing formal statements to Sections 3 and 5. It is important to note that, as shown in prior work (Daskalakis et al., 2018, 2019), for the model parameters to be identifiable from truncated samples, we need to place some assumptions that limit how aggressively the data is truncated. The assumptions we make are listed below, and stated more precisely in Section 2. They combine normalization assumptions (Assumption 1.1), assumptions that are needed even without truncation (Assumption 1.3), and assumptions that are needed for identifiability purposes in the presence of truncation (Assumption 1.2).
Assumption 1.1. We assume that ||w0112 S B and ||== < 1 for all i.
Assumption 1.2. For all (z(), ()) in the truncated dataset, conditioning on (0)), the probability that w² ( + E S, with respect to the randomness in e ~ NN(0, ²²), is larger than some a.
Assumption 1.3. If (a+0), ())) is the truncated dataset, we assume that the feature covariance matrix, X 1 n E ( (00((())) satisfies: Ez-p [X] = Fuwp((=""
b 7 for some b.
With these assumptions we prove our main results for the joint estimation of w" and x² listed as Informal Theorems 1.4-1.5 below, and respectively Theorems 3.2 and 5. in later sections.
Informal Theorem 1.4 (Estimation). Suppose we are given n samples (z(1), (1)0)))))))) from the truncated linear regression model with parameters w", o²2 and suppose Assumptions 1.1-1.3 hold. Then running Projected Stochastic Gradient Descent (Algorithm 1) on the conditional negative rogllikeldoood of the sample, using the projection set described in Definition 3.1, we obtain with probability at least 2/3 (which can be boosted to as large a constant as desirable) estimations v 8²
n 2 C (depending on the learning rate), where C₁ depends polynomially on B, 1/a and L/b, and C2 depends linearly in 1/b and exponentially in 3/a, where 3, and b are respectively the constants in Assumptions 1.1, 1.2
such that || w0 ll| + 102 -z2 S E. as long as n. > Ci (o/e))) or
and 1.3.
Informal Theorem 1.5 (Asymptotic Normality). Let úù 8² be the estimates of Informal Theorem 1.4. There exists matrix A that depends on u. o² (and is explicitly provided in Theorem 5.1) such that (x()) converges asymptotically a normal distribution with zero mean and covariance matrix A. Hence the a confidence region of (w, o²) can be computed using the matrix A and the quantiles of the chi-squared distribution.
the random vector vn((3))
Techniques. Our estimates are computed by running Projected Stochastic Gradient Descent (PSGD) on the population conditional negative log- likeliild of the truncated sample; convex function of

---

the parameters, after an appropriate reparameterizaaionn We provide two analyses of PSGD resulting in two different bounds that are more effective in different range of parameters, as we discuss next.
Our first analysis hinges on establishing a lower bound on the convexity of the conditional negative niglllkei function. We can't however, expect that strong bound holds over the whole parameter domain. For this reason, we add a projection step to our method, identifying a projection set wherein we show that the true parameters lie and wherein the conditional negative log-likelihood is strongly convex. This approach is similar to that of Daskalakis et al. (2019), except that the unknown noise variance introduces many challenges in identifying an appropriate projection set. The main result bounding the strong convexity of the conditional negative log likelihood function within the projection set is stated as Theorem 4.1. The main disadvantage of this analysis is that, when the variance is unknown, the bound on the strong convexity of the conditional negative log-likelihood becomes small and the resulting dependence of the sample size on the parameters / and 1/a of the problem exponential. On the other hand, the dependence of the sample size on 1 1/b is linear and its dependence on the required estimation accuracy is (1/=2), which is optimal. Our other analysis follows an approach that has not been pursued in prior work, and in particular does not rely global lower bound on the strong convexity of the conditional negative log-likelihood. Instead, we only bound the strong convexity at the optimum and use an upper bound on the smoothness of the objective function to prove the convergence of PSGD in terms of function value. Again, it is impossible to prove bound the smoothness over the whole domain, because large noise variance can lead to very bad smoothness bounds. Thus we use the same projection set as above and show that, within this set, we can get an upper bound on the smoothness that depends polynomially 19, 1 /a, 1 1/b, of the problem. The main drawback of this method is that the dependence on the accuracy is (log" (1/e)/E*). ). It is worth noting that obtaining an algorithm whose sample complexity has an optimal (1)/²²) dependence on the estimation accuracy, and also scales polynomially in 1/a is fundamental bottleneck, which is already present in the much simpler special case of our problem of estimating the variance of a I-dimensional truncated Gaussian, studied in Daskalakis al. (2018) 8).3
all parameters,
Finally, to help build intuition around the intricacies in estimating truncated linear regression models with unknown noise variance, let's 'ss consider why natural approaches of reducing this problem to estimating truncated linear regression models with known noise variance - which can be done using the algorithm of Daskalakis et al. (2019)- fail. A simple such reduction might compute the empirical variance of of the truncated sample, and plug that into the algorithm of Daskalakis et al. (2019) to estimate the linear model, pretending that of is the true noise variance. A more sophisticated approach might grid over candidate noise variances, plug each of these candidates into the algorithm of Daskalakis al. (2019) to estimate a linear model, and then select the (linear model, noise variance) pair that is most consistent, e.g. the pair whose noise variance is closest to the empirical variance of the residuals between the linear model's 's predictions and the observed labels. Both of these approaches fail, as suggested by the example below. Suppose that the ground truth is y = w x - w + E. where x is one-dimensional, (w", wū) = 0), and the noise variance is o²² = 1. Suppose also that we create a truncated dataset by, repeatedly, sampling x; from (00 1), generating y) according to the ground truth, and truncating the resulting pair (I,, Bi) unless y: 2 T, where J is some threshold. clear that, if we guess the true noise variance to be the empirical one, then as gets bigger, the empirical variance gets smaller, thus the linear model that would be estimated by treating the empirical variance as the true noise variance would have intercept that is close to 7 rather than O. So this naive approach would fail. Let us consider the more sophisticated one that grids over candidate noise variances. In particular, let us compare what happens when (1) we guess the noise variance to be of = o² and run the algorithm of Daskalakis et al. (2019) with this guess to get an estimate (u², ) and (2) when we guess the noise variance to be of = of (the empirical variance) and run the algorithm of Daskalakis et al. (2019) with this guess to get an estimate (ıī', ())). It is easy to see
- + E(w v x; w6)² (here, N is the number of samples. This holds even if N goes to infinity). Thus the selection criterion proposed above will fail to prefer (1) over (2), even though the guess of the noise variance under (1) is the correct one. Our approach in this paper amounts to using a different criterion, namely selecting the pair with the largest conditional log- likelihood. But analyzing when and how well this works, as well as obtaining an efficient algorithm to find the best pair is the main contribution of this work.
that, as T gets large, 0022 : En tx.; - =
'While Daskalakis et al. (2018) does not explicitly analyze the dependence of the sample complexity on a; by tracing through their bounds, one can that the dependence of the sample complexity on a is exponential.
3

---

Roadmap. We present the truncated linear regression setting and our assumptions in Section 2. We state and prove our main estimation results Section and 4, and prove the asymptotic normality of our estimators in Section 5. Finally, in Section 6 we assess the performance of our methods.
2 Models and assumptions
We study the truncated linear regression setting studied in Daskalakis al. (2019), with the additional complexity that the variance of the noise model is unknown, In particular, let S C R be measurable subset of the real line, which oracle access is provided. Assume samples (x((), y ( (we will split the samples into three, see 4.5), each generated according the following procedure, for some unknown w* E R and o² R that are fixed across different i's:
have N 3n truncated
1. sample (:()) from some distribution Po with support (Po)(Po) C RR; 2. generate y( according to the following model, where E ~ ~N(00, ( = w *T 20() +
(2.1)
3. if ( E then return (z(),, ())) as the ith sample, otherwise repeat from step 1.
After truncation, denote the distribution of x be P with the supp(P) supp(Po). The sam- pled x is still i.i.d, so we could only consider the distribution P. As already established in prior work (Daskalakis et al., 2018, 2019; Kontonis al., 2019), some assumptions must be placed on and its interaction with the unknown parameters (w* o²2) and the ( in order for the parameters to be identifiable. We state our assumptions after a useful definition.
Definition 2.1 (Survival Probability). Let S R be measurable, z, IR and R. We define a, the survival probability a(w, a, x. S) as ((w, a, S. S) = P (Y E S); where Y ~ NNww" x, o²).
When S is clear from context we may omit S from the arguments of a and simply write (w,, 0, x).
We are now ready to state our assumptions. Our first assumption gives an upper bound on the norm of the true parameters and the feature vectors.
Assumption 2.2 (Normalization/Dat Generation). Assume that || 12 S B. and ||0|| S for all E supp(P). We also assume oracle access for set S, i.e. we have an oracle which determines, for any y, whether y E
Our next assumption is the survival probability lower bound following Daskalakis et al. (2018, 2019). Assumption 2.3 (Constant Survival Probability). For all x E supp(P), we have a(w", ao,""" .x) > a.
Our final assumption is about the spectrum of the covariance matrix of the features and is classical in some other linear regression settings, such as in Daskalakis al. (2019).
Assumption 2.4 (Thickness of Feature Covariance). Let X E (0)) be the k k feature vector covariance matrix. We assume that, for some positive real number b, we have Egpp [X] Exwp(xn' > b I. Here we abuse the notation that the (z), y() are samples used for PSGD.
3 Main Result
When the variance parameter x2 is unknown, the conditional log-likelihood function of the plain linear regression becomes non-concave, and therefore not straightforward optimize. For this reason, we follow the common practice of reparameterizing the problem with respect to the parameters w/a² and À 1/o². The algorithm that we use is Projected SGD on the population negative log-likelihood function E(v, A) as presented in Algorithm 1. We formally define the loss function in Section 4.1.
Our goal is to apply the above algorithm to the conditional negative log- log-likelihood function of the truncated linear regression model. To execute the above algorithm in polynomial time, we need to solve the following algorithmic problems.
(a) initial feasible point: compute initial feasible point in some projection set D.

---

Algorithm 1 Projected SGD on !
Input: (x()), ())) for E [n], learning rates
1: (Wo, og) t OLS estimates using other samples; (q. 1()) + (wa/ /: 1/0
> (a) Initialization part
2: In terms of of define convex set D over pairs (v, A) as described in Definition 3.1
3: (0()) <- o -
D (a) Initialization part 2
4: for 1- 1,..,., n do
5: Sample gradient (1)) such that E [/ 1)((-1) 7 ((-11)
b (b) Unbiased Gradient Estimate. sampling method see Section B.1
6: (witt, )(1)) + (u(t-1),
111-1)) Tp (t
7: (vit), ,(()) t arg (i (1 (v(t), 110))1
(c) Efficient Projection
8: end for
9: (0, - (o(x), ((m)): return (20 + 10/2
(b) unbiased gradient estimation: sample unbiased estimate of Vé(v(t-1), (((-11)),
(c) efficient projection: design an algorithm to project to the set D.
Solving the computational problems (a)-(c) the first step in the proof of our main result. First define the appropriate projection set to use in our algorithm.
Definition 3.1 (Projection Set). We define the projection set to be the (v, A) satisfying
(v, = 02 o2
(u.
w
R
2
96
x
8(5 + 2 log(1/a))
where o is the estimated variance from solving the classical linear regression problem (using n samples) the data ignoring truncation.
This projection set contains two parts: the first part that restricts the weights and the second part that restricts the variance. For the second part, use the variance predicted using ordinary least squares.
Now we are ready to formally state our main theorem about the estimation the parameters w and from truncated samples under the Assumptions 2.2- 2.4.
Theorem 3.2. Let (z(1), ((.)..... (x((), (1())) be samples from the linear regression model (2.1) with ground truth w², o-² of Afsumpttionss 2.2- 2.4 hold, then used in Algorithm 1 such that, with success probability 2 2/3, 3, the output estimates w, 8² satisfy either one of the following bounds:
instantiate the learning rates
poly aa'''''' a' --0-) log(n) a.b
11 - w= + 00 -o? -0000
(3.1)
1//4
poly(a" +) exp poly( a.0
- Ø2 22
(3.2)
vn.
for some polynomials that we make explicit in the detailed proof of the theorem (Section B.7).
Remark 3.3. It is easy to that the probability of success in Theorem 3.2 can be boosted to 1 8 with an additional cost of order log(1/5) in the rates. We can achieve this using a folklore boosting technique for parameter estimation problems. In particular, log(1 /8) times independently and then we can pick the estimate that e close to at least the half of the of the estimates, where is the target estimation error. It is easy see that with this boosting technique we can get error at most 2a with probability of success at least - ô.
the al algorithm of Theorem 3.2
To prove Theorem 3.2 we provide two different analyses of the Algorithm The first analysis uses only the fact that the stochastic gradients of the population conditional negative log-likelihood function have bounded second moment and is based on the following theorem.
Theorem 3.4 (Theorem of Shamir Zhang (2013)).
& be a convex function with a minimizer (v", X*) and suppose that there exists constant p such that
5

---

ii) bounded step variance IE || S p² where w is the sampled step variance in algorithm 1,
bounded domain: (e)eel))) -², x")l s
(iii feasibility of optimal: the minimizer ;0)
then if we apply Algorithm I on i with learning rates = c/ V where c is an absolute constant then for every E [n] holds that IE (E(((((0),)))))
E(v" x²] poly(p)log(()
vt
For the second analysis of Algorithm 1 we also need to bound the strong convexity of É. This the reason that we get the exponential dependence some of the parameters of the problem, but we can also get a better consistency rate. For this second analysis we use the following theorem.
Theorem 3.5 (Lemma 1 of Rakhlin al. (2011)). Let be a convex function with a minimizer (v", X*) and suppose that there exist constants P. such that
ii) bounded step variance: E [| S p² where w(t) is the sampled step variance in algorithm!
(iii) feasibility of optimal: the minimizer (u* x0) E E
(iv) strong convexity: E is s-strongly convex
then if we apply Algorithm I on with learning rates 1/: 1/(5 .G.)) 1), then for every i E [n] it holds that
(0" -100
E
<
4p²
sum, the main challenges for proving Theorem 3.2 are solving computational problems (a)-(c) and proving mathematical properties (i)-(iv).
4 Overview of the proof of Theorem 3.2.
We provide overview of the proof of Theorem 3.2, postponing most technical details to the supplementary material. The main steps of the proof are the following.
1. In Section we derive the negative population conditional log-likelihood, its gradient, and its Hessian matrix.
2. In Section 4.2 we discuss the computational problems (a) (c).
3. In Section 4.3 we formally state our results that prove the properties (i), (ii), and (iv).
4. In Section 4.4 we state our results for property (iii), the feasibility of the optimal solution.
5. Finally in Section 4.5 we use all the above results to complete the proof of 3.2.
4.1 The Negative Population Conditional Log-Likelihood Function of Truncated Linear Regression
In this section we define the objective function that we use to apply our PSGD algorithm. This objec- tive function is derived by taking the negative expected value of the log-likelihood of y conditional on the value of z. Given a sample (x, y). the negative conditional log- log-likelihood that y is a sampled from the truncated linear regression with parameters w, o² given the value of is equal to
1 ] (2² 222-22 2yw x) tog (ʃ cxpl(
f(w,o2 ,3;
202 2 -2zu" x)))d)
202
we reparameterize with 1/02 and w/a², we have
1 (xy² 2y x) log
[(v, \; v)
exp( - (Ao² 220 x))dz
(4.1)

---

We define the distributions F5 = N(w" I, o. .) and Q₂ = N(w x, ,,, and the negative
population conditional bog-likelihodd function as follows
E(U,
E xrup
E y
(4.2)
We can then easily compute
08
de
E 2nPP
T
E gr
E
E
I
[22]
dv
ax
2 xnp
x x~@
From these we also compute the Hessian matrix which is
[- Var (x] Tmi
Covenex 22
H(v,)) A) = E
( 12 2/2
(4.3)
Var 220
Here, H is the expectation of covariance matrices, which is positive definite. Thus, i convex.
4.2 Computational Problems
The computational problems (a) - (c) can be tackled in the following way
(a) We start with computing (Wo, σo) by applying OLS to the truncated data.
(b) As we see from the expression of the gradient of É, we can compute an unbiased estimate of the gradient using one of our samples (x:(8, ,y()),))))))))))))) our sample access to distribution of x's and by doing rejection sampling until we find a point with (ar, z) with S. To bound the time needed for this step, we need to understand the mass of the survival set for some I P and some vector of parameters (v, E D. See Supplementary Material B.2.
(c) We show in the supplementary material that D is a convex set and define an efficient algorithm project our estimates D. It is elaborated Supplementary Material A.2
For more details the way we solve the computational problems (a) (c) we refer to the supplemen- tary material.
4.3 Bounded Step Variance, Bounded Domain, and Strong Convexity
In this section we present the statements that establish the properties (i), (ii), (iv) that we need in order to apply Theorem 3.4 and Theorem 3.5.
Theorem 4.1. For every (u, A) D. we have
E E[1(e - (1(0=))=113] s
tot). H(U, b-epp (-poly(1/a)(1+ { o
3
[ (
a
where, P. y Fg and 2 ~ Qu and H from (4.3).
The proof of Theorem 4.1 can be found in Supplementary Material B.3. Also, it is easy to see that the diameter of D is bounded: ||ll| ||w|l//o² < 8(5 log a) /3/00/0 and |\ < 1/0² <
8(5 aloga)/05
4.4 Feasibility of Optimal Solution
We need to calculate the probability for the optimal point to be in the projection set, i.c., w", o* e D.
Lemma 4.2. Under Assumptions 2.3 and 2.2 we have that, P(Ww", a²) E D) 2 13/16.
The proof of this Lemma can be found in Supplementary Material B.4.
4.5 Proof of Theorem 3.2
The algorithm that proves Theorem 3.2 starts with splitting the samples into three parts of equal size in order to avoid dependence. The first part of n/3 samples is used to compute the OLS estimates
7

---

Wo, where Wo is used in the initialization step. The second part of n/3 samples is used to compute the OLS estimate of o. where do used both initialize and define the projection set D, and used at every step where a projection to D is needed. The number of sample to define D is poly (='v / and our n itself will reach this bound (see Section B.4.) Finally, the third part of the n/3 samples used in our main PSGD algorithm. For the rest of the proof we abuse the notation and we use <- n/33 for simplicity. The next thing that we need to decide is the learning rates that we are going to use for the PSGD. We will analyze PSGD under two possible choices of its learning rate schedule, namely 1/ = c/ vt and пÿ 1/(5- t), and will show that it produces estimates for the ground
and A = poly(ao)-exp poly(y for some polynomials that we will make explicit in Section B.7.
poly( 20 1
"aren Ilg((n)
parameters that scale as A =
respectively,
1174
b/n
Analysis for learning schedule f = c/ eL. First, by combining Theorem 3.4 and Theorem 4.1, and noticing the relationship between do and a² in the projection set, we get the following corollary whose proof can be found in Section B.7.
Corollary 4.3. Suppose that (v" xx* (w" (w"/o"² /002 100002) D and E is defined in (4.2). Then, the output (6, X) of Algorithm satisfies E [[ 2) E(,0,,()) x²) I poly ani
a. (og(()
12/2
Our next step is utilize the above bound to so that our estimates achieve small errors in the parameter space. For this we use the strong convexity of l the optimum.
(002)
Lemma 4.4. The Hessian at the true (v", ,²) satisfies H(v", ,0)2
bxpoly(a) polyt1/a.8/0-2)
The proof of Lemma 4.4 can be found in Supplementary Material B.3.1. We also utilize the following lemma to calculate an upper bound on ((u",*")
Lemma 4.5. (Lemma 3 in Daskalakis al. (2019)) Let xz w R², a > 0, then o wf wTx)² 2²²² < (4 2 log aww, a, x))o?
By the above lemma, we have:
yy w xT2
((v",*))
E ZEP
20 + loogal"",'",, ,x) $4- - -2loog min alw",, ,0",,) x) S - 2 log a xEP
Applying Markov's inequality we have
((((e, (((t,A))E(o"x))) -0 < <
(4.4)
The inequality implies that, with least 6/7 probability, the actual difference is at most 7 times its expectation. Also, the probability that (o", X²) E D is at least 13/16 by Lemma 4.2. Combining these two, we have at least 13/16 1/7 > 2/3 probability hold:
E 2)- E(v",>') poly(
0- ) log(n)
ab 1/2
(4.5)
Now applying Lemma 4.4, since 0, Å converge to er, X3, when they have small distance, we have poly( -
ab ..) log(n)
||e - v 112 + x²)² < [((6,) 2) -(0))))(()-))) <
(4.6)
8. 1/2
where H(D", H((x,>*)= = 8I, and 8 = poly ( :.b. )
Finally, doing some simple calculations for the reparameterizzation ssee Section B.7 in supplementary material- we have that
|| wf 11 or2| / (10 w- 022 -0022") S poly(1/a, -
(u*,
(4.7)
Combining inequalities (4.4), (4.5). (4.6), (4.7), inequality (3.1) of Theorem 3.2 follows.
Analysis for learning schedule т) = =1/(Ct). We combine Theorem 3.5 and Theorem 4.1 to get the following corollary whose proof can be found in Section B.6.
8

---

Corollary 4.6. Suppose the tree parameters (o", X = (w" //////1////////////.//.... ) E D and i is defined as
equation (4.2). Then, for i, X being the output of Algorithm 1, it holds that
E ||(0.)) (0" (0,, ,,,) x3) S poly (3.0* g.. -. exp (poly(1/a) ( (1+
/ o+2 62n
3 1
Similarly details can be found in Section B.7 of the supplementary material- to those used to (t: 2) (v"; A*)
prove inequality (3.1) above, get that with probability 2/3 holds that
poly(o") eepp poly( ( Then, we can prove (3.2) using the definition of the projection set D.
Inference and Confidence Regions
We now prove the asymptotic normality of our estimates (Theorem 5.1), which we use to obtain their confidence regions (Corollary 5.2). For the proofs we refer to the Section B.8.
Theorem 5.1. Let (ir,0²) 0²) be the output of Algorithm I with to 1/(S t). Then, the vector Vns 1/2 (())) (rr)), asymptotically converges to N(, T++,), where
(1/021 0
-0/00)
S = : RR
-1/62)
E the matrix that satisfies (A-
-
= ))
H is the empirical estimation of the Hessian matrix defined by (4.3) at the point (6, 2).
-(v,A)= = : ay 0l(.,Aa s
Olv,A)
((v,))
Corollary 5.2. Let qa be the a quantile of distribution X2+11
Then the a asymptotic
confidence region of (w, o?) is ((w)
10
R
ER
2o
02
0²
8
(nn
Synthetic Experiments
Figure 1, we show how our algorithm performs against mod- els with large noise variances. For this experiment, sample
Sustc it 2000
2 dimensional ground-truth weight vector w" id.dd U(-1,1) and generate 1000 (x)(), (f))) pairs according to 2:(6) i.j.d. (() and y/ w. (+)) + el0; where e(() ON We fix w and x(1) .... (()) across all trials, but vary a² After adding Gaussian noise to our ground-truth predictions, we left truncate at zero, remov- ing all of the pairs who's (d)) is negative; retaining approximately 50% of the original samples. We vary x² over the interval [1, 20) and evaluate how well our procedure recovers w² and x2 compari- son to OLS, Daskalakis et al. (2019), assuming og is *2 Daskalakis et al. (2019), given σ²2, and truncreg, an R package for truncated regression. We acknowledge that when the noise variance is known, Daskalakis et al. (2019) performs the best, but both our algorithm and truncreg perform comparably under this simple truncation. We emphasize though that truncreg cannot be applied in settings where complicated that simple interval whereas
Dui. 20 saming
1.5
(a)
Agaittin
the truncation is our method can still be applied. Also notice that running Daskalakis et al. (2019) with incorrect x2 produces erroneous results.
(b)
Figure 1: Figure (a) shows t estimation errors and Figure (b) shows the 22 estimation errors for each x2
In Figure 2, we show that our theoretical error bounds hold in prac- tice. For this experiment, we set w" to ten dimensional weight

---

vector of ones, sample (z(), (0) pairs, where 200 iid. (o I) and e(1) sid NO 1), and right truncate at zero. We generate our data once. However, for each experiment, we randomly select a l samples that exceed zero, and run our experiment. We vary & over the interval [10, 5000). Our results show that the error bound asymptotically approaches zero at a rate that reaffirms our theoretical analysis.
16
als
our algorithm
14
b
10-
0.8
I
0.6
0.4
0.2
2000
3000
5000
Number of Samples in
Figure 2: Comparison of the proposed method with ordinary least squares.
7 Semi-Synthetic Experiment
Here we show results for an additional experiment that we conducted on semi semi-synthetic data. For this experiment, we used the Aldrin (2004) dataset. The Aldrin (2004) dataset was originally collected by the Norwegian Public Roads Administration for study of air pollution at road in Oslo, Norway. The dataset consists of 500 observations. Interestingly enough, it common for environmental data to be truncated because of problems in reliably measuring low concentrations.
For this experiment, we apply left truncation the dataset, varying truncation parameter C over the interval [1.0, 4.0]. We run our procedure total of 10 times and retain the trial that has the smallest gradient as our algorithm's 's prediction. We conduct the experiment with the same hyperparameters as for the synthetic data experiments. Below, we report our results.
In Figure (a), we show the L distance between the model parameters of each method and the ground-truth, which we take to be the OLS estimation without truncation. In this figure, we show that our method performs very comparably Croissant & Zeileis (2018). We also note that, at high values of the truncation, both methods exhibit non-monotonicity in their estimation error, which is presumably due to model misspecification and the truncation being too aggressive.
In Figure 3 (b), we report the L' distance between the predicted noise variance and the ground-trutt noise variance. Again, our method performs very comparably Croissant & Zeileis (2018), and we observe monomonotyyyyity at high values of the truncation.
1.4
undnown
uninown
suncreg
Suncrog
0.3
0.6
0.7
0.1
1.0
15
2.0
25
1.0
40
1.0
20
3.0
Trancation
Thuncation Parameter
(b)
Figure 3: Our method's performance on the semi-synthetic PM10 dataset.
10

---

Acknowledgements
CD and PS were supported by NSF Awards CCF-1901292, DMS-2022448 (FODST) and DMS- 2134108, by Simons Investigator Award, by the Simons Collaboration on the Theory of Algorithmic Fairness, by DSTA grant, and by the DOE PhILMs project (No. DE-ACU5-76RL01830) MZ was supported by NSF DMS-2023505 (FODSI).
References
Aldrin, M. Pm10 dataset, 2004. URL http://lib..st stat...ttt.......... cmu, edu/datasets/PML dat. PM particles Oslo, Norway.
Amemiya, T. Regression analysis when the dependent variable is truncated normal. Econometrica: Journal of the Econometric Society, pp. 997-1016, 1973.
Balakrishnan, N. and Cramer, E. The art of progressive censoring. Springer, 2014.
Breen, R. et al. Regression models: Censored, sample selected, truncated data, volume 1 111. Sage, 1996.
Carbery, A. and Wright. J. Distributional and l4 norm inequalities for polynomials over convex bodies in rú. Mathematical research letters, 8(3):233-244) -2222, 2001a.
Carbery, A. and Wright, J. Distributional and L norm inequalities for polynomials over convex bodies in R" Mathematical research letters, 8(3::233-248, 2001b.
Croissant, Y. and Zeileis, A. truncreg: Estimation models for truncated gaussian variables by max- imum likelihood, 2018. URL https: httpss///craat reimn.rrrrooo projrject. org/wer//ee httg//ebbpackagege htreeeerg/rrrr//////ee truncreg. pdf. R package version 1.8.0.
Daskalakis, C., Gouleakis, T., Tzamos, C., and Zampetakis, M. Efficient statistics, in high dimensions, from truncated samples. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 639-649. IEEE, 2018.
Daskalakis, C., Gouleakis, T., Tzamos, C., and Zampetakis, M. Computationally and statistically efficient truncated regression. In Conference on Learning Theory (COLT), pp. 955 955-960, 2019.
Fisher, Properties and applications of hh functions. Mathematical tables, 1:815-852, 1931.
Fotakis, D., Kalavasis, A., and Tzamos, C. Efficient parameter estimation of truncated boolean product distributions. In Conference Learning Theory, pp. 1586-1600. PMLR, 2020.
Galton, F. An examination into the registered speeds of american trotting horses, with remarks on their value hereditary data. Proceedings of the Royal Society of London, 62(379-387)310--355 1897.
Hajivassiliou, V. A. and McFadden, D. L.. The method of simulated scores for the estimation of ldv models. Econometrica, pp. 863-896, 1998.
Hausman. J. A. and Wise, D. A. Social experimentation, truncated distributions, and efficient estimation. Econometrica: Journal of the Econometric Society, pp. 919-938. 1977.
Heckman, J. Sample selection bias as specification enror. Econometrica: Journal of the econometric society, pp. 153-161, 1979.
Henningsen, A. and Toomet. O. maxlik: A package for maximum likelihood estimation R. Computational Statistics, 26(3):443-458 2011. doi: 00.10077:00010-0000021777 URL http: //dx. doi. org. 1000 10000000000000000000 -
Ilyas, A., Zampetakis. E., and Daskalakis, C. A theoretical and practical framework for regression and classification from truncated samples. In International Conference on Artificial Intelligence and Statistics, pp. 4463-4473. PMLR, 2020.

---

Kontonis, V., Tzamos, C., and Zampetakis, M. Efficient truncated statistics with unknown truncation. In 2019 IEEE 60th Annual Symposium Foundations of Computer Science (FOCS), pp. 1578- 1595. IEFF, 2019.
Leluc, R. and Portier, F. Towards asymptotic optimality with conditioned stochastic gradient descent. arXiv preprint arXiv:2006.02770 2020.
Mohan, K., Pearl, J., and Tian, J. Graphical models for inference with missing data. In Proceedings of the 26th Annual Conference Neural Information Processing Systems (NeurIPS), 2013.
Moitra, A., Mossel, E., and Sandon, C. Learning to sample from censored markov random fields. arXiv preprint arXiv:2101.06177 2021.
Pearson, K. On the systematic fitting of frequency curves. Biometrika, 2:2-7, 1902.
Pearson, K. and Lee, A. On the generalised probable emoor in multiple normal correlation. Biometrika, 6(1):59-68, 1908.
Plevrakis, O. Learning from censored and dependent data: The case linear dynamics. Conference Learning Theory- COLT, 2021.
Rakhlin, A., Shamir, O., and Sridharan, K. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv:1109.5647, 2011.
Shamir, O. and Zhang, T. Stochastic gradient descent for non-smooth optimization: Convergence
results and optimal averaging schemes. In International conference on machine learning, pp- 71-79. PMIR, 2013.
Tobin, J. Estimation of relationships for limited dependent variables. Econometrica: journal of the Econometric Society, pp. 24-36, 1958.
Tropp, J. A. An introduction to matrix concentration inequalities. arXiv preprint 151.011501.01571, 2015.
Tukey, W. Sufficiency, truncation and selection. The Annals of Mathematical Statistics, pp.
309-311, 1949.
12


Reviews:
[{"review_id": "q9OkK4TElTK", "reviewer": "Reviewer_Hgq6", "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.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nEven though the authors claimed their efforts in proofreading the paper, there are several issues that concern me in writing:\n  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.\n  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.\n  3. In assumption 2.4, there is a full stop missing. And there is a typo at Line 243.\n  4. Section 3 is called \"Log likelihood functions and feasibility\". But the content is about projected SGD and Theorem 3.2.\n  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.\n  \n\nI have the following two questions.\n  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)?\n  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.\n\n------ UPDATE ------\n\nThe authors have addressed my concerns. Thus I raised my score to 6.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have not known any potential negative societal impact of the present work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "pLe82DOwpfd", "reviewer": "Reviewer_nLxV", "summary": "# Summary\n\nThe paper studies truncated linear regression when the additive error follows a zero-mean normal distribution with unknown variance. \nThis setting generalizes the work of Daskalakis-Gouleakis-Tzamos-Zampetakis-2019, who assumed the knowledge of the variance of error.\nThis work provides two statistical rates for the joint estimation of the regressor (w) and the noise variance (\\sigma) in Theorem 3.2.\nThe 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.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\nAs 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).\n\nOverall, 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:\n\n\n+ 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. \n\n+ 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.\n\n\n**Minor points**\n\n+ As Leluc and Portier (2020) heavily influences the  asymptotic normality result, they should be cited appropriately in the main paper.\n\n+ The large length of some sentences affect readability; for example, Line 17-21. Line 28-33.\n\n+ Add a citation for the Line 157-158.\n\n+ 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. \n\n+ Refer to Algorithm 3.1 in the beginning of Theorem 3.5. It is not clear in the beginning what is $u^{(t)}$.\n\n\n+ 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.\n\n+ 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.\n\n+ Line 177: What is the difference in the notation? \n\n\n\n+ Assumption 1.2 seems stronger than Assumption 1 in Daskalakis et al. (2019).\n\n+ Lines 101-103: How does Lemma 7 in Daskalakis et al. (2019) imply the claim in Lines 101-103?\n\n\n\n+ Line 35: Typo: needed, \n\n+ Define $H_x$ in (4.3)?\n\n+ Line 253-254: Where is this in supplementary material. In general, please point to the specific section when referring to the supplementary material.\n\n+ Line 264: 'initial' should be replaced by 'optimal'.\n\n# Update\n\nI 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:\n1. Add as formal claims why obvious approaches won't work (with omitted details in the supplementary material).\n2. Improve the notation for asymptotic normality\n3. Changing the phrase statistical efficiency\n4. Improve the structure of the paper as other reviewer suggested\n5. Citing Leluc and Portier before stating Theorem 5.1 and Theorem 1.5. \n6. And other minor/major comments ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "D77Edl3z0Q2", "reviewer": "Reviewer_gvjA", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n2. 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.\n\n3. 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. \n\n### Minor comments\n- line 24: range instead of rage?\n- line 53: \"needed\" rather than \"need\"\n- line 203: what is \"folklore boosting\"? Is it just what's described in the next sentence? \n- line 255: where exactly in the appendix can we find details to solve the computational problem?\n- line 264: is \"initial point\" supposed to be \"optimal point\" here?\n\n### Major comments, clarifying questions\n- 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\n- line 93: is the strong convexity bounded at the optimum alone or in some neighborhood about it?\n- 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.\n- 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. \n- 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. \n- Section 4.2: specify where exactly in the supplement computation problems are discussed. Perhaps spend more time discussing computational issues. \n- Section 6:\n    * 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 )\n    * 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. \n    * 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? \n    * Reasonably, what size problem can be solved with this method? What is maximum dimension attempted\n    \n================================= \nUPDATE\n\nThank 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.\n\nWith the changes mentioned above, I have improved my rating from 6 to a 7. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

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)