Efficient Sampling for k-Determinantal Point Processes

Abstract

Determinantal Point Processes (DPPs) are elegant probabilistic models of repulsion and diversity over discrete sets of items. But their applicability to large sets is hindered by expensive cubic-complexity matrix operations for basic tasks such as sampling. In light of this, we propose a new method for approximate sampling from discrete $k$-DPPs. Our method takes advantage of the diversity property of subsets sampled from a DPP, and proceeds in two stages: first it constructs coresets for the ground set of items; thereafter, it efficiently samples subsets based on the constructed coresets. As opposed to previous approaches, our algorithm aims to minimize the total variation distance to the original distribution. Experiments on both synthetic and real datasets indicate that our sampling algorithm works efficiently on large data sets, and yields more accurate samples than previous approaches.

References in corpus (9)

• Learning Determinantal Point Processes
• Fast Randomized Kernel Methods With Statistical Guarantees
• Fast DPP Sampling for Nyström with Application to Kernel Methods
• Learning the Parameters of Determinantal Point Process Kernels
• Expectation-Maximization for Learning Determinantal Point Processes
• Fast Mixing for Discrete Point Processes
• Diversifying Sparsity Using Variational Determinantal Point Processes
• Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models
• Notes on using Determinantal Point Processes for Clustering with Applications to Text Clustering

Cited by in corpus (14)

• Diversity Networks: Neural Network Compression Using Determinantal Point Processes
• Fast DPP Sampling for Nyström with Application to Kernel Methods
• Exact Sampling of Determinantal Point Processes without Eigendecomposition
• Kronecker Determinantal Point Processes
• Determinantal Point Processes for Mini-Batch Diversification
• Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
• Active Mini-Batch Sampling using Repulsive Point Processes
• Unbiased estimators for random design regression
• A Polynomial Time MCMC Method for Sampling from Continuous DPPs
• Structured Monte Carlo Sampling for Nonisotropic Distributions via Determinantal Point Processes
• Faster Greedy MAP Inference for Determinantal Point Processes
• Approximately Optimal Subset Selection for Statistical Design and Modelling
• Sampling from a $k$-DPP without looking at all items
• Learning from DPPs via Sampling: Beyond HKPV and symmetry