Maximum likelihood probability measures over sets: Existence, computation, and convergence

We consider maximum likelihood estimation of a distribution over a general measurable space where realizations of the uncertainty are not directly observable but instead are known to lie within observable sets. We show that maximum likelihood estimates concentrate on a collection of maximal intersections (CMI) and can be found by solving a convex optimization problem whose size is linear in the size of the CMI. We provide an enumerative algorithm to compute the estimates and show that there are estimates that assign positive weight only to T+1 elements of the CMI (T being the number of observed sets). Motivated by this, we provide a column generation algorithm to compute the estimates that avoids enumerating the CMI. Under the assumption that either the observed sets are mixed-integer representable, or that the range of the underlying distribution is finite and known, we provide formulations of the algorithms that can be solved with commercial solvers. We study convergence properties of the maximum likelihood estimate both in terms of traditional notions of converge, as well as in terms of Wasserstein distances. Our results show that convergence to the underlying distribution cannot be guaranteed in general, but we identify sufficient conditions for convergence. We also perform numerical experiments that show that the estimates can be computed within minutes, that column generation can significantly reduce computational times, and that there is convergence even in cases where no theoretical guarantees are known.