# Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

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

- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2207.00486/) (2022)
- [Small coresets via negative dependence: DPPs, linear statistics, and concentration](https://mlsanity.com/paper/2411.00611/) (2024)
- [Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes](https://mlsanity.com/paper/2109.00727/) (2021)
- [Online MAP Inference and Learning for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2111.14674/) (2021)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Nonparametric estimation of continuous DPPs with kernel methods](https://mlsanity.com/paper/2106.14210/) (2021)
- [DPP-TTS: Diversifying prosodic features of speech via determinantal point processes](https://mlsanity.com/paper/2310.14663/) (2023)
- [Bypassing orthogonalization in the quantum DPP sampler](https://mlsanity.com/paper/2503.05906/) (2025)
- [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)

Determinantal point processes (DPPs) have attracted significant attention in machine learning for their ability to model subsets drawn from a large item collection. Recent work shows that nonsymmetric DPP (NDPP) kernels have significant advantages over symmetric kernels in terms of modeling power and predictive performance. However, for an item collection of size M, existing NDPP learning and inference algorithms require memory quadratic in M and runtime cubic (for learning) or quadratic (for inference) in M, making them impractical for many typical subset selection tasks. In this work, we develop a learning algorithm with space and time requirements linear in M by introducing a new NDPP kernel decomposition. We also derive a linear-complexity NDPP maximum a posteriori (MAP) inference algorithm that applies not only to our new kernel but also to that of prior work. Through evaluation on real-world datasets, we show that our algorithms scale significantly better, and can match the predictive performance of prior work.