# Efficient Truncated Statistics with Unknown Truncation

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

## Key facts

- Cited by 22 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 2 Aug 2019.

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

- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Efficient Truncated Linear Regression with Unknown Noise Variance](https://mlsanity.com/paper/2208.12042/) (2022)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [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)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Learning Thresholds with Latent Values and Censored Feedback](https://mlsanity.com/paper/2312.04653/) (2023)
- [Unraveling overoptimism and publication bias in ML-driven science](https://mlsanity.com/paper/2405.14422/) (2024)
- [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025)
- [What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness](https://mlsanity.com/paper/2506.04194/) (2025)
- [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)
- [Mean Testing under Truncation beyond Gaussian](https://mlsanity.com/paper/2605.01335/) (2026)
- [Towards a holistic understanding of Selection Bias for Causal Effect Identification](https://mlsanity.com/paper/2605.13430/) (2026)
- [Surprises in Proper Positive-Only Learning](https://mlsanity.com/paper/2606.28309/) (2026)
- [Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue](https://mlsanity.com/paper/2607.22889/) (2026)

## Abstract (arXiv)

We study the problem of estimating the parameters of a Gaussian distribution when samples are only shown if they fall in some (unknown) subset S subseteq Rd. This core problem in truncated statistics has long history going back to Galton, Lee, Pearson and Fisher. Recent work by Daskalakis et al. (FOCS'18), provides the first efficient algorithm that works for arbitrary sets in high dimension when the set is known, but leaves as an open problem the more challenging and relevant case of unknown truncation set. Our main result is a computationally and sample efficient algorithm for estimating the parameters of the Gaussian under arbitrary unknown truncation sets whose performance decays with a natural measure of complexity of the set, namely its Gaussian surface area. Notably, this algorithm works for large families of sets including intersections of halfspaces, polynomial threshold functions and general convex sets. We show that our algorithm closely captures the tradeoff between the complexity of the set and the number of samples needed to learn the parameters by exhibiting a set with small Gaussian surface area for which it is information theoretically impossible to learn the true Gaussian with few samples.