Michal Derezinski, University of California, Berkeley

Abstract

Given a positive semi-definite n x n matrix L, we study the complexity of sampling from a distribution over all index subsets of the set 1,...,n where the probability of a subset S is proportional to the determinant of the submatrix of L with rows and columns indexed by S. Known as a determinantal point process, this distribution is widely used in machine learning and stochastic optimization to induce diversity in subset selection. It also provides optimal low-rank reconstruction guarantees for row/column subset selection and is used in combinatorial approximation algorithms for experimental design. In practice, we often wish to sample multiple subsets S with small expected size k = E[|S|] << n from a very large matrix L, so it is important to minimize the preprocessing cost of the procedure (performed once) as well as the sampling cost (performed repeatedly). To that end, we propose a new algorithm which, given access to L, samples exactly from a determinantal point process while satisfying the following two properties: (1) its preprocessing cost is n x poly(k) (sublinear in the size of L) and (2) its sampling cost is poly(k) (independent of the size of L). Prior to this work, state-of-the-art exact samplers required O(n^3) preprocessing time and sampling time either linear in n or dependent on the spectral properties of L. Our algorithm relies on a new regularized determinantal point process (R-DPP), which serves as an intermediate distribution in the sampling procedure by reducing the number of rows from n to poly(k). Crucially, this intermediate distribution does not distort the probabilities of the target sample. Our key novelty in defining the R-DPP is the use of a Poisson random variable for controlling the probabilities of different subset sizes, leading to new determinantal formulas such as the normalization constant for this distribution. Our experimental results show that the algorithm performs well even against approximate samplers which trade-off accuracy for speed. Based on joint work with Daniele Calandriello and Michal Valko.

Video