# Scalable Sampling for Nonsymmetric Determinantal Point Processes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 65 references that are in the map.
- First posted on arXiv 20 Jan 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [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)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [GDPP: Learning Diverse Generations Using Determinantal Point Process](https://mlsanity.com/paper/1812.00068/) (2018)
- [Diversity Networks: Neural Network Compression Using Determinantal Point Processes](https://mlsanity.com/paper/1511.05077/) (2015)
- [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016)
- [Expectation-Maximization for Learning Determinantal Point Processes](https://mlsanity.com/paper/1411.1088/) (2014)
- [Exact sampling of determinantal point processes with sublinear time preprocessing](https://mlsanity.com/paper/1905.13476/) (2019)
- [Determinantal Point Processes for Coresets](https://mlsanity.com/paper/1803.08700/) (2018)
- [Sampling from a k-DPP without looking at all items](https://mlsanity.com/paper/2006.16947/) (2020)
- [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)
- [Faster Greedy MAP Inference for Determinantal Point Processes](https://mlsanity.com/paper/1703.03389/) (2017)
- [Fixed-point algorithms for learning determinantal point processes](https://mlsanity.com/paper/1508.00792/) (2015)
- [Low-Rank Factorization of Determinantal Point Processes for Recommendation](https://mlsanity.com/paper/1602.05436/) (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)
- [Exact Sampling of Determinantal Point Processes without Eigendecomposition](https://mlsanity.com/paper/1802.08429/) (2018)
- [Stochastic Conditional Gradient++](https://mlsanity.com/paper/1902.06992/) (2019)
- [Composable Core-sets for Determinant Maximization Problems via Spectral Spanners](https://mlsanity.com/paper/1807.11648/) (2018)
- [Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More](https://mlsanity.com/paper/2102.02708/) (2021)
- [On largest volume simplices and sub-determinants](https://mlsanity.com/paper/1406.3512/) (2014)
- [On Sampling and Greedy MAP Inference of Constrained Determinantal Point Processes](https://mlsanity.com/paper/1607.01551/) (2016)
- [Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration](https://mlsanity.com/paper/1707.02757/) (2017)
- [Learning Determinantal Point Processes by Corrective Negative Sampling](https://mlsanity.com/paper/1802.05649/) (2018)

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

- [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022)
- [Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2207.00486/) (2022)

## Abstract (arXiv)

A determinantal point process (DPP) on a collection of M items is a model, parameterized by a symmetric kernel matrix, that assigns a probability to every subset of those items. Recent work shows that removing the kernel symmetry constraint, yielding nonsymmetric DPPs (NDPPs), can lead to significant predictive performance gains for machine learning applications. However, existing work leaves open the question of scalable NDPP sampling. There is only one known DPP sampling algorithm, based on Cholesky decomposition, that can directly apply to NDPPs as well. Unfortunately, its runtime is cubic in M, and thus does not scale to large item collections. In this work, we first note that this algorithm can be transformed into a linear-time one for kernels with low-rank structure. Furthermore, we develop a scalable sublinear-time rejection sampling algorithm by constructing a novel proposal distribution. Additionally, we show that imposing certain structural constraints on the NDPP kernel enables us to bound the rejection rate in a way that depends only on the kernel rank. In our experiments we compare the speed of all of these samplers for a variety of real-world tasks.