# Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 78 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 26 of 26)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Estimating Density Models with Truncation Boundaries using Score Matching](https://mlsanity.com/paper/1910.03834/) (2019)
- [Provable benefits of score matching](https://mlsanity.com/paper/2306.01993/) (2023)
- [Efficient Parameter Estimation of Truncated Boolean Product Distributions](https://mlsanity.com/paper/2007.02392/) (2020)
- [Truncated Linear Regression in High Dimensions](https://mlsanity.com/paper/2007.14539/) (2020)
- [Optimal Learning of Mallows Block Model](https://mlsanity.com/paper/1906.01009/) (2019)
- [On the Analysis of EM for truncated mixtures of two Gaussians](https://mlsanity.com/paper/1902.06958/) (2019)
- [A Computationally Efficient Method for Learning Exponential Family Distributions](https://mlsanity.com/paper/2110.15397/) (2021)
- [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)
- [What Makes A Good Fisherman? Linear Regression under Self-Selection Bias](https://mlsanity.com/paper/2205.03246/) (2022)
- [Detecting Low-Degree Truncation](https://mlsanity.com/paper/2402.08133/) (2024)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Learning from satisfying assignments under continuous distributions](https://mlsanity.com/paper/1907.01619/) (2019)
- [Learning Mixtures of Gaussians with Censored Data](https://mlsanity.com/paper/2305.04127/) (2023)

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

- [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)
- [Private Statistical Estimation via Truncation](https://mlsanity.com/paper/2505.12541/) (2025)
- [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)
- [Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue](https://mlsanity.com/paper/2607.22889/) (2026)
- [Efficient Learning of Survival Analysis Models Under Outcome-Dependent Truncation and Censoring](https://mlsanity.com/paper/2610.12538/) (2026)

## Abstract (arXiv)

We study the estimation of distributional parameters when samples are shown only if they fall in some unknown set S subseteq ℝd. Kontonis, Tzamos, and Zampetakis (FOCS'19) gave a dpoly(1/varepsilon) time algorithm for finding varepsilon-accurate parameters for the special case of Gaussian distributions with diagonal covariance matrix. Recently, Diakonikolas, Kane, Pittas, and Zarifis (COLT'24) showed that this exponential dependence on 1/varepsilon is necessary even when S belongs to some well-behaved classes. These works leave the following open problems which we address in this work: Can we estimate the parameters of any Gaussian or even extend beyond Gaussians? Can we design poly(d/varepsilon) time algorithms when S is a simple set such as a halfspace? We make progress on both of these questions by providing the following results: 1. Toward the first question, we give a dpoly(ℓ/varepsilon) time algorithm for any exponential family that satisfies some structural assumptions and any unknown set S that is varepsilon-approximable by degree-ℓ polynomials. This result has two important applications: 1a) The first algorithm for estimating arbitrary Gaussian distributions from samples truncated to an unknown S; and 1b) The first algorithm for linear regression with unknown truncation and Gaussian features. 2. To address the second question, we provide an algorithm with runtime poly(d/varepsilon) that works for a set of exponential families (containing all Gaussians) when S is a halfspace or an axis-aligned rectangle. Along the way, we develop tools that may be of independent interest, including, a reduction from PAC learning with positive and unlabeled samples to PAC learning with positive and negative samples that is robust to certain covariate shifts.