Efficient Parameter Estimation of Truncated Boolean Product
  Distributions
  We study the problem of estimating the parameters of a Boolean product
distribution in $d$ dimensions, when the samples are truncated by a set $S
\subset \{0, 1\}^d$ accessible through a membership oracle. This is the first
time that the computational and statistical complexity of learning from
truncated samples is considered in a discrete setting.
  We introduce a natural notion of fatness of the truncation set $S$, under
which truncated samples reveal enough information about the true distribution.
We show that if the truncation set is sufficiently fat, samples from the true
distribution can be generated from truncated samples. A stunning consequence is
that virtually any statistical task (e.g., learning in total variation
distance, parameter estimation, uniformity or identity testing) that can be
performed efficiently for Boolean product distributions, can also be performed
from truncated samples, with a small increase in sample complexity. We
generalize our approach to ranking distributions over $d$ alternatives, where
we show how fatness implies efficient parameter estimation of Mallows models
from truncated samples.
  Exploring the limits of learning discrete models from truncated samples, we
identify three natural conditions that are necessary for efficient
identifiability: (i) the truncation set $S$ should be rich enough; (ii) $S$
should be accessible through membership queries; and (iii) the truncation by
$S$ should leave enough randomness in all directions. By carefully adapting the
Stochastic Gradient Descent approach of (Daskalakis et al., FOCS 2018), we show
that these conditions are also sufficient for efficient learning of truncated
Boolean product distributions.
