Efficient Truncated Statistics with Unknown Truncation
This addresses a core challenge in truncated statistics relevant for fields like econometrics and machine learning, offering a novel solution for unknown truncation sets, though it builds on prior work for known sets.
The paper tackles the problem of estimating Gaussian distribution parameters from samples truncated by an unknown set, providing a computationally and sample efficient algorithm whose performance depends on the Gaussian surface area of the truncation set, with results applicable to families like intersections of halfspaces and convex sets.
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 \R^d$. 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.