This paper studies a generally formulated problem about recovering a low-rank matrix from samples. As a special case, the authors work captures the problem of leaning a k x k probability matrix M given access to samples from M, under the assumption that M is low-rank (rank r). The authors show how to solve this problem up to TV distance epsilon using kr/eps^2 * log(r/eps) samples, which is tight up to the log factor improving on a recent ITCS paper. Their algorithm also applies to a number of related sampling problems, which have applications in recommender systems, community detection, etc. The reviewers were convinced of the contributions of this paper (though recommended adding experimental analysis of the algorithm on practical data). I am pleased to recommend accepting this paper to NeurIPS.