Distribution Learning from Truncated Samples

Abstract

This thesis is concerned with the fundamental problem of learning distributions from truncated samples. In this setting the purpose is to estimate a probability distribution based only on truncated samples. That means that samples falling outside a specific, unknown set are not available. The challenge becomes greater when we demand that these estimations are given by an efficient -in terms of sample and traditional complexity- algorithm. We study the learnability of two specific distributions in this setting: the Poisson Binomial Distribution and the Mallows Distribution. We are interested in those conditions on the truncation set that care both sufficient and necessary to learn these distributions. In the first case, we are faced with an impossible problem that becomes easier as the distribution gains structure, thus indicating an interesting transition on the difficulty of the problem. For the Mallows Model we give a sufficient condition and recognise the sub-optimality of a well-established method in the field of rank aggregation.