# Truncated Linear Regression in High Dimensions

arXiv: https://arxiv.org/abs/2007.14539 · HTML: https://mlsanity.com/paper/2007.14539/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2020.

## Built on by (most cited first, 13 of 13)

- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)
- [Private Statistical Estimation via Truncation](https://mlsanity.com/paper/2505.12541/) (2025)
- [Linear Regression under Missing or Corrupted Coordinates](https://mlsanity.com/paper/2509.19242/) (2025)
- [High-Dimensional Gaussian Mean Estimation under Realizable Contamination](https://mlsanity.com/paper/2603.16798/) (2026)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)
- [Mean Testing under Truncation beyond Gaussian](https://mlsanity.com/paper/2605.01335/) (2026)

## Abstract (arXiv)

As in standard linear regression, in truncated linear regression, we are given access to observations (Ai, yi)i whose dependent variable equals yi= Airm T · x^* + ηi, where x^* is some fixed unknown vector of interest and ηi is independent noise; except we are only given an observation if its dependent variable yi lies in some "truncation set" S subset ℝ. The goal is to recover x^* under some favorable conditions on the Ai's and the noise distribution. We prove that there exists a computationally and statistically efficient method for recovering k-sparse n-dimensional vectors x^* from m truncated samples, which attains an optimal ℓ2 reconstruction error of O(√(k log n)/m). As a corollary, our guarantees imply a computationally efficient and information-theoretically optimal algorithm for compressed sensing with truncation, which may arise from measurement saturation effects. Our result follows from a statistical and computational analysis of the Stochastic Gradient Descent (SGD) algorithm for solving a natural adaptation of the LASSO optimization problem that accommodates truncation. This generalizes the works of both: (1) [Daskalakis et al. 2018], where no regularization is needed due to the low-dimensionality of the data, and (2) [Wainright 2009], where the objective function is simple due to the absence of truncation. In order to deal with both truncation and high-dimensionality at the same time, we develop new techniques that not only generalize the existing ones but we believe are of independent interest.