Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
Jane H. Lee, Anay Mehrotra, Manolis Zampetakis · 2024
We study the estimation of distributional parameters when samples are shown only if they fall in some unknown set. Kontonis, Tzamos, and Zampetakis (FOCS'19) gave an algorithm for finding parameters for the special case of Gaussian distributions with diagonal covariance matrix. Recently, Diakonikolas, Kane, Pittas, and Zarifis (COLT'24) showed that an exponential dependence on the inverse of the accuracy parameter is necessary even when the set 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 the results beyond Gaussians? Can we design polynomial-time algorithms when for simple sets such as a halfspace? Toward the first question, we provide an estimation algorithm for any exponential family that satisfies some structural assumptions and any unknown set that is approximable by polynomials. This result has two important applications: (a)The first algorithm for estimating arbitrary Gaussian distributions (even with non-diagonal covariance matrix) from samples truncated to unknown set; and (b)The first algorithm for linear regression with unknown truncation and Gaussian features. To address the second question, we provide an algorithm with polynomial sample and time complexity that works for a set of exponential families (that contains multivariate Gaussians) when the unknown survival set is a halfspace or an axis-aligned rectangle.11A preliminary version of this paper incorrectly claimed the result for finite unions of axis-aligned rectangles. The result only holds for a single axis-aligned rectangle. This is the first fully polynomial time algorithm for estimation with an unknown truncation set. Along the way, we develop new tools that may be of independent interest, including: (c)The first polynomial time algorithm for learning halfspaces using only positive examples when the samples have an unknown Gaussian distribution; and (d)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.