# Hardness of Maximum Likelihood Learning of DPPs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 89 references that are in the map.
- First posted on arXiv 24 May 2022.

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

- [Multi-Agent Determinantal Q-Learning](https://mlsanity.com/paper/2006.01482/) (2020)
- [Exact expressions for double descent and implicit regularization via surrogate random design](https://mlsanity.com/paper/1912.04533/) (2019)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016)
- [Learning the Parameters of Determinantal Point Process Kernels](https://mlsanity.com/paper/1402.4862/) (2014)
- [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)
- [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)
- [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)
- [Computational Limits for Matrix Completion](https://mlsanity.com/paper/1402.2331/) (2014)
- [Reverse iterative volume sampling for linear regression](https://mlsanity.com/paper/1806.01969/) (2018)
- [Large-Margin Determinantal Point Processes](https://mlsanity.com/paper/1411.1537/) (2014)
- [Fast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling](https://mlsanity.com/paper/1608.01008/) (2016)
- [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)
- [Kronecker Determinantal Point Processes](https://mlsanity.com/paper/1605.08374/) (2016)
- [Approximate Inference in Continuous Determinantal Point Processes](https://mlsanity.com/paper/1311.2971/) (2013)
- [Fast Mixing for Discrete Point Processes](https://mlsanity.com/paper/1506.02194/) (2015)
- [Wasserstein Learning of Determinantal Point Processes](https://mlsanity.com/paper/2011.09712/) (2020)
- [Determinantal Clustering Processes - A Nonparametric Bayesian Approach to Kernel Based Semi-Supervised Clustering](https://mlsanity.com/paper/1309.6862/) (2013)
- [Testing Determinantal Point Processes](https://mlsanity.com/paper/2008.03650/) (2020)

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

- [Duality induced by an embedding structure of determinantal point process](https://mlsanity.com/paper/2404.11024/) (2024)
- [A simple estimator of the correlation kernel matrix of a determinantal point process](https://mlsanity.com/paper/2505.14529/) (2025)
- [Adaptive Quality-Diversity Trade-offs for Large-Scale Batch Recommendation](https://mlsanity.com/paper/2602.02024/) (2026)
- [Scalable Learning of Determinantal Point Processes with Kernel-Structured Interactions](https://mlsanity.com/paper/2610.12829/) (2026)

## Abstract (arXiv)

Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs have been successfully employed in Machine Learning applications to select a diverse, yet representative subset of data. In these applications, a set of parameters that maximize the likelihood of the data is typically desirable. The algorithms used for this task to date either optimize over a limited family of DPPs, or use local improvement heuristics that do not provide theoretical guarantees of optimality. In his seminal work on DPPs in Machine Learning, Kulesza (2011) conjectured that the problem is NP-complete. The lack of a formal proof prompted Brunel et al. (COLT 2017) to suggest that, in opposition to Kulesza's conjecture, there might exist a polynomial-time algorithm for computing a maximum-likelihood DPP. They also presented some preliminary evidence supporting a conjecture that they suggested might lead to such an algorithm. In this work we prove Kulesza's conjecture. In fact, we prove the following stronger hardness of approximation result: even computing a left(1-O(frac1log9N)right)-approximation to the maximum log-likelihood of a DPP on a ground set of N elements is NP-complete. From a technical perspective, we reduce the problem of approximating the maximum log-likelihood of a DPP to solving a gap instance of a textsc3-Coloring problem on a hypergraph. This hypergraph is based on the bounded-degree construction of Bogdanov et al. (FOCS 2002), which we enhance using the strong expanders of Alon and Capalbo (FOCS 2007). We demonstrate that if a rank-3 DPP achieves near-optimal log-likelihood, its marginal kernel must encode an almost perfect ``vector-coloring" of the hypergraph. Finally, we show that these continuous vectors can be decoded into a proper 3-coloring after removing a small fraction of ``noisy" edges.