# Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes

arXiv: https://arxiv.org/abs/2207.00486 · HTML: https://mlsanity.com/paper/2207.00486/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 32 references that are in the map.
- First posted on arXiv 1 Jul 2022.

## Builds on (most cited first, 18 of 18)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Improving Adversarial Robustness via Promoting Ensemble Diversity](https://mlsanity.com/paper/1901.08846/) (2019)
- [Generating Personalized Recipes from Historical User Preferences](https://mlsanity.com/paper/1909.00105/) (2019)
- [Multi-Agent Determinantal Q-Learning](https://mlsanity.com/paper/2006.01482/) (2020)
- [Batched Gaussian Process Bandit Optimization via Determinantal Point Processes](https://mlsanity.com/paper/1611.04088/) (2016)
- [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016)
- [Determinantal Point Processes for Coresets](https://mlsanity.com/paper/1803.08700/) (2018)
- [Learning Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/1905.12962/) (2019)
- [Fast DPP Sampling for Nystr"om with Application to Kernel Methods](https://mlsanity.com/paper/1603.06052/) (2016)
- [Fast determinantal point processes via distortion-free intermediate sampling](https://mlsanity.com/paper/1811.03717/) (2018)
- [Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2006.09862/) (2020)
- [Improving Sequential Determinantal Point Processes for Supervised Video Summarization](https://mlsanity.com/paper/1807.10957/) (2018)
- [Learning Determinantal Point Processes in Sublinear Time](https://mlsanity.com/paper/1610.05925/) (2016)
- [Determinantal Point Processes for Mini-Batch Diversification](https://mlsanity.com/paper/1705.00607/) (2017)
- [Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More](https://mlsanity.com/paper/2102.02708/) (2021)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [On the Complexity of Constrained Determinantal Point Processes](https://mlsanity.com/paper/1608.00554/) (2016)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)

## Built on by (most cited first, 4 of 4)

- [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022)
- [Small coresets via negative dependence: DPPs, linear statistics, and concentration](https://mlsanity.com/paper/2411.00611/) (2024)
- [Generalized Determinantal Point Processes for Attraction and Repulsion with Distinct Interaction Kernels](https://mlsanity.com/paper/2610.12894/) (2026)
- [Identication and Estimation of Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2610.14520/) (2026)

## Abstract (arXiv)

A determinantal point process (DPP) is an elegant model that assigns a probability to every subset of a collection of n items. While conventionally a DPP is parameterized by a symmetric kernel matrix, removing this symmetry constraint, resulting in nonsymmetric DPPs (NDPPs), leads to significant improvements in modeling power and predictive performance. Recent work has studied an approximate Markov chain Monte Carlo (MCMC) sampling algorithm for NDPPs restricted to size-k subsets (called k-NDPPs). However, the runtime of this approach is quadratic in n, making it infeasible for large-scale settings. In this work, we develop a scalable MCMC sampling algorithm for k-NDPPs with low-rank kernels, thus enabling runtime that is sublinear in n. Our method is based on a state-of-the-art NDPP rejection sampling algorithm, which we enhance with a novel approach for efficiently constructing the proposal distribution. Furthermore, we extend our scalable k-NDPP sampling algorithm to NDPPs without size constraints. Our resulting sampling method has polynomial time complexity in the rank of the kernel, while the existing approach has runtime that is exponential in the rank. With both a theoretical analysis and experiments on real-world datasets, we verify that our scalable approximate sampling algorithms are orders of magnitude faster than existing sampling approaches for k-NDPPs and NDPPs.