mlsanityData to 7 Oct 2026

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

arXiv 2410.01656 ↗First posted 2 Oct 2024math.ST cs.DS cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

26 of 78 references.

References · 26

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  3. 2016Agnostic Estimation of Mean and Covariancecited by 131
  4. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  5. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  6. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
  7. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  8. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  9. 2018Efficient Statistics, in High Dimensions, from Truncated Samplescited by 28
  10. 2020Computationally and Statistically Efficient Truncated Regressioncited by 23
  11. 2019Efficient Truncated Statistics with Unknown Truncationcited by 22
  12. 2022A Proximal Algorithm for Samplingcited by 21
14 more
  1. 2019Estimating Density Models with Truncation Boundaries using Score Matchingcited by 20
  2. 2023Provable benefits of score matchingcited by 18
  3. 2020Efficient Parameter Estimation of Truncated Boolean Product Distributionscited by 13
  4. 2020Truncated Linear Regression in High Dimensionscited by 13
  5. 2019Optimal Learning of Mallows Block Modelcited by 12
  6. 2019On the Analysis of EM for truncated mixtures of two Gaussianscited by 10
  7. 2021A Computationally Efficient Method for Learning Exponential Family Distributionscited by 10
  8. 2022Efficient Truncated Linear Regression with Unknown Noise Variancecited by 10
  9. 2021Learning from Censored and Dependent Data: The case of Linear Dynamicscited by 9
  10. 2022What Makes A Good Fisherman? Linear Regression under Self-Selection Biascited by 7
  11. 2024Detecting Low-Degree Truncationcited by 7
  12. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  13. 2019Learning from satisfying assignments under continuous distributionscited by 4
  14. 2023Learning Mixtures of Gaussians with Censored Datacited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 3.

6 papers.

  1. 2025Smoothed Analysis of Learning from Positive Samplescited by 2
  2. 2025What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundednesscited by 2
  3. 2025Private Statistical Estimation via Truncationcited by 1
  4. 2026Mean Testing under Truncation beyond Gaussiancited by 0
  5. 2026Towards a holistic understanding of Selection Bias for Causal Effect Identificationcited by 0
  6. 2026Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescuecited by 0