![[2205.12377] Hardness of Maximum Likelihood Learning of DPPs](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2205.12377] Hardness of Maximum Likelihood Learning of DPPs
Summary
This article presents a proof of the NP-completeness of the maximum likelihood learning problem for Determinantal Point Processes (DPPs), enhancing the understanding of computational complexity in machine learning.
Why It Matters
Understanding the hardness of maximum likelihood learning for DPPs is crucial as it impacts algorithm design in machine learning applications that require diverse data selection. This work solidifies Kulesza's conjecture and provides a theoretical foundation for future research in computational complexity and probabilistic models.
Key Takeaways
- Proves the NP-completeness of maximum likelihood learning for DPPs.
- Enhances the theoretical framework for approximating log-likelihood in DPPs.
- Demonstrates a reduction from DPPs to the 3-Coloring problem, linking two areas of computational complexity.
Computer Science > Computational Complexity arXiv:2205.12377 (cs) [Submitted on 24 May 2022 (v1), last revised 25 Feb 2026 (this version, v3)] Title:Hardness of Maximum Likelihood Learning of DPPs Authors:Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie View a PDF of the paper titled Hardness of Maximum Likelihood Learning of DPPs, by Elena Grigorescu and 3 other authors View PDF HTML (experimental) Abstract: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. n seminal work on DPPs in Machine Learning, Kulesza conjectured in his PhD Thesis (2011) 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 approximat...
