Efficient Truncated Statistics with Unknown Truncation
  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.
