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) set. 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.

Authors

• Vasilis Kontonis
• Christos Tzamos
• Manolis Zampetakis

Keywords

• Complexity theory
• Gaussian distribution
• Estimation
• History
• Area measurement
• Method of moments
• Standards
• Normal Distribution
• Efficient Algorithm
• Convex Set
• Family Settings
• Complex Settings
• Gaussian Parameters
• Positive Samples
• Diagonal Matrix
• Total Distance
• Stochastic Gradient Descent
• Finite-dimensional
• Set Of Classes
• True Parameter
• Probability 1
• Positive Semidefinite
• Hyperacusis
• Goal Of This Section
• Affine Function
• Truncated Normal
• Gaussian Measurement
• Total Variation Distance
• Hermite Polynomials
• Strongly Convex
• Empirical Risk Minimization
• Absolute Constant
• Unknown Mean
• Original Distribution
• Covariance Matrix
• Manhattan Distance
• Borel Set
• Truncated Statistics
• Statistics
• Learning Theory
• Unknown Truncation Set