Linear Regression with Unknown Truncation Beyond Gaussian Features

In truncated linear regression, samples $(x,y)$ are shown only when the outcome $y$ falls inside a certain survival set $S^\star$ and the goal is to estimate the unknown $d$-dimensional regressor $w^\star$. This problem has a long history of study in Statistics and Machine Learning going back to the works of (Galton, 1897; Tobin, 1958) and more recently in, e.g., (Daskalakis et al., 2019; 2021; Lee et al., 2023; 2024). Despite this long history, however, most prior works are limited to the special case where $S^\star$ is precisely known. The more practically relevant case, where $S^\star$ is unknown and must be learned from data, remains open: indeed, here the only available algorithms require strong assumptions on the distribution of the feature vectors (e.g., Gaussianity) and, even then, have a $d^{\mathrm{poly} (1/\varepsilon)}$ run time for achieving $\varepsilon$ accuracy. In this work, we give the first algorithm for truncated linear regression with unknown survival set that runs in $\mathrm{poly} (d/\varepsilon)$ time, by only requiring that the feature vectors are sub-Gaussian. Our algorithm relies on a novel subroutine for efficiently learning unions of a bounded number of intervals using access to positive examples (without any negative examples) under a certain smoothness condition. This learning guarantee adds to the line of works on positive-only PAC learning and may be of independent interest.

When we collect data in the real world, we often only observe part of the picture. A clinical trial might only enroll patients whose symptoms exceed a certain severity; a salary survey might only capture workers who responded to the questionnaire. When data are filtered this way — a phenomenon called "truncation" — standard methods for learning patterns in data can give highly inaccurate answers. Hence, the problem of accurately learning under truncation has a long history of study in the theory of statistics and machine learning. However, most existing theoretical works either assume that the truncation mechanism is known or that the data come from specific types of distributions. These assumptions are not realistic in many practical settings. In our work, we study the case where our data can be formulated via a popular statistical framework for modeling relationships in data, called "linear regression". Compared to previous works, we assume the data are truncated in an unknown way, and allow for significantly broader types of data distributions. We develop an algorithm that learns the true relationships in our data, and we formally prove that it is computationally efficient. Our approach relies on a novel way to infer the truncation mechanism from data, which is generally a challenging task. Thus, we resolve an interesting open question in the theory of statistics and machine learning, while also developing new learning techniques that might be of independent interest.