Hardness of Maximum Likelihood Learning of DPPs
by Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie
Theory of Computing, Volume 22(2168), pp. 1-58, 2026
Bibliography with links to cited articles
[1] Raja Hafiz Affandi, Emily Fox, Ryan Adams, and Ben Taskar: Learning the parameters of determinantal point process kernels. In International Conference on Machine Learning, pp. 1224–1232, 2014.
[2] Raja Hafiz Affandi, Emily B. Fox, and Ben Taskar: Approximate inference in continuous determinantal point processes. In Advances in Neural Information Processing Systems 25, pp. 1430–1438, 2013.
[3] Raja Hafiz Affandi, Alex Kulesza, Emily Fox, and Ben Taskar: Nyström approximation for large-scale determinantal processes. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, volume 31 of PMLR, pp. 85–98, 2013.
[4] Noga Alon and Michael Capalbo: Finding disjoint paths in expanders deterministically and online. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pp. 518–524. IEEE, 2007.
[5] Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei: Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes. In Conference on Learning Theory, pp. 103–115. PMLR, 2016.
[6] Lucas Anquetil, Mike Gartrell, Alain Rakotomamonjy, Ugo Tanielian, and Clément Calauzènes: Wasserstein learning of determinantal point processes. arXiv preprint arXiv:2011.09712, 2020.
[7] Yannick Baraud: Estimation of the density of a determinantal process. Confluentes Mathematici, 5(1):3–21, 2013.
[8] Piotr Berman, Marek Karpinski, and Alex D. Scott: Approximation hardness and satisfiability of bounded occurrence instances of SAT. Electronic Colloquium in Computational Complexity, TR03-022, 2003.
[9] Andrej Bogdanov, Kenji Obata, and Luca Trevisan: A lower bound for testing 3-colorability in bounded-degree graphs. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 93–102. IEEE, 2002.
[10] Alexei Borodin and Eric M. Rains: Eynard-Mehta theorem, Schur process, and their Pfaffian analogs. Journal of statistical physics, 121(3-4):291–317, 2005.
[11] Stephen Boyd and Lieven Vandenberghe: Convex optimization. Cambridge university press, 2004.
[12] Joshua Brakensiek and Venkatesan Guruswami: New hardness results for graph and hypergraph colorings. In 31st Conference on Computational Complexity (CCC 2016), 2016.
[13] Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, and John Urschel: Maximum likelihood estimation of determinantal point processes. arXiv preprint arXiv:1701.06501, 2017.
[14] Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, and John Urschel: Rates of estimation for determinantal point processes. In Conference on Learning Theory, pp. 343–345, 2017.
[15] Robert Burton and Robin Pemantle: Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances. The Annals of Probability, pp. 1329–1371, 1993.
[16] Wei-Lun Chao, Boqing Gong, Kristen Grauman, and Fei Sha: Large-margin determinantal point processes. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pp. 191–200, 2015.
[17] Ali Civril and Malik Magdon-Ismail: On selecting a maximum volume sub-matrix of a matrix and related problems. Theoretical Computer Science, 410(47-49):4801–4811, 2009.
[18] Michał Dereziński, Daniele Calandriello, and Michal Valko: Exact sampling of determinantal point processes with sublinear time preprocessing. In Advances in Neural Information Processing Systems 32, 2019.
[19] Michal Derezinski, Feynman T. Liang, and Michael W. Mahoney: Exact expressions for double descent and implicit regularization via surrogate random design. Advances in Neural Information Processing Systems 33, 2020.
[20] Michał Dereziński and Manfred K. Warmuth: Reverse iterative volume sampling for linear regression. The Journal of Machine Learning Research, 19(1):853–891, 2018.
[21] Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approximate coloring. SIAM Journal on Computing, 39(3):843–873, 2009.
[22] Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan: Revenue submodularity. In Proceedings of the 10th ACM conference on Electronic commerce, pp. 243–252, 2009.
[23] Christophe Dupuy and Francis Bach: Learning determinantal point processes in sublinear time. In International Conference on Artificial Intelligence and Statistics, pp. 244–257, 2018.
[24] Freeman J. Dyson: Statistical theory of the energy levels of complex systems. III. Journal of Mathematical Physics, 3(1):166–175, 1962.
[25] Mike Gartrell, Victor-Emmanuel Brunel, Elvis Dohmatob, and Syrine Krichene: Learning nonsymmetric determinantal point processes. arXiv preprint arXiv:1905.12962, 2019.
[26] Mike Gartrell, Ulrich Paquet, and Noam Koenigstein: Bayesian low-rank determinantal point processes. In Proceedings of the 10th ACM Conference on Recommender Systems, pp. 349–356, 2016.
[27] Mike Gartrell, Ulrich Paquet, and Noam Koenigstein: Low-rank factorization of determinantal point processes. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
[28] Khashayar Gatmiry, Maryam Aliakbarpour, and Stefanie Jegelka: Testing determinantal point processes. arXiv preprint arXiv:2008.03650, 2020.
[29] Jennifer Gillenwater, Alex Kulesza, and Ben Taskar: Discovering diverse and salient threads in document collections. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 710–720, 2012.
[30] Jennifer Gillenwater, Alex Kulesza, and Ben Taskar: Near-optimal map inference for determinantal point processes. In Advances in Neural Information Processing Systems 24, pp. 2744–2752, 2012.
[31] Jennifer A Gillenwater, Alex Kulesza, Emily Fox, and Ben Taskar: Expectation-maximization for learning determinantal point processes. Advances in Neural Information Processing Systems, 27:3149–3157, 2014.
[32] Oded Goldreich, Shari Goldwasser, and Dana Ron: Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653–750, 1998.
[33] Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie: Hardness of maximum likelihood learning of dpps. In Conference on learning theory, pp. 3800–3819. PMLR, 2022.
[34] Martin Grötschel, László Lovász, and Alexander Schrijver: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197, 1981.
[35] Carlos Guestrin, Andreas Krause, and Ajit Paul Singh: Near-optimal sensor placements in Gaussian processes. In Proceedings of the 22nd international conference on Machine learning, pp. 265–272, 2005.
[36] Venkatesan Guruswami and Sanjeev Khanna: On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics, 18(1):30–40, 2004.
[37] Venkatesan Guruswami and Ali Kemal Sinop: Optimal column-based low-rank matrix reconstruction. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pp. 1207–1214. SIAM, 2012.
[38] Moritz Hardt, Raghu Meka, Prasad Raghavendra, and Benjamin Weitz: Computational limits for matrix completion. In Conference on Learning Theory, pp. 703–725. PMLR, 2014.
[39] Johan Håstad: On bounded occurrence constraint satisfaction. Information Processing Letters, 74(1-2):1–6, 2000.
[40] Johan Håstad: Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001.
[41] Gerald Haynes, Catherine Park, Amanda Schaeffer, Jordan Webster, and Lon H Mitchell: Orthogonal vector coloring. The Electronic Journal of Combinatorics, 17, 2010.
[42] Roger A Horn and Charles R Johnson: Matrix analysis. Cambridge university press, second edition, 2012.
[43] J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág: Determinantal processes and independence. Probability surveys, 3:206–229, 2006.
[44] Ilse C. F. Ipsen and Rizwana Rehman: Perturbation bounds for determinants and characteristic polynomials. SIAM Journal on Matrix Analysis and Applications, 30(2):762–776, 2008.
[45] Byungkon Kang: Fast determinantal point process sampling with application to clustering. In Advances in Neural Information Processing Systems 25, pp. 2319–2327, 2013.
[46] David R. Karger, Rajeev Motwani, and Madhu Sudan: Approximate graph coloring by semidefinite programming. J. ACM, 45(2):246–265, 1998.
[47] Sanjeev Khanna, Nathan Linial, and Shmuel Safra: On the hardness of approximating the chromatic number. Combinatorica, 20(3):393–415, 2000.
[48] Chun-Wa Ko, Jon Lee, and Maurice Queyranne: An exact algorithm for maximum entropy sampling. Operations Research, 43(4):684–691, 1995.
[49] Andreas Krause, Ajit Singh, and Carlos Guestrin: Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008.
[50] Alex Kulesza and Ben Taskar: Structured determinantal point processes. Advances in neural information processing systems 23, pp. 1171–1179, 2010.
[51] Alex Kulesza and Ben Taskar: k-DPPs: fixed-size determinantal point processes. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 1193–1200, 2011.
[52] Alex Kulesza and Ben Taskar: Learning determinantal point processes. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pp. 419–427, 2011.
[53] Alex Kulesza and Ben Taskar: Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 5(2-3):123–286, 2012.
[54] John A. Kulesza: Learning with Determinantal Point Processes. Ph. D. thesis, University of Pennsylvania, 2012.
[55] Claire Launay, Bruno Galerne, and Agnès Desolneux: Exact sampling of determinantal point processes without eigendecomposition. Journal of Applied Probability, 57(4):1198–1221, 2020.
[56] Monique Laurent: Matrix completion problems. Encyclopedia of Optimization, 3:221–229, 2009.
[57] Frédéric Lavancier, Jesper Møller, and Ege Rubak: Determinantal point process models and statistical inference. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 77(4):853–877, 2015.
[58] Donghoon Lee, Geonho Cha, Ming-Hsuan Yang, and Songhwai Oh: Individualness and determinantal point processes for pedestrian detection. In European Conference on Computer Vision, pp. 330–346. Springer, 2016.
[59] Chengtao Li, Stefanie Jegelka, and Suvrit Sra: Fast DPP sampling for Nyström with application to kernel methods. In International Conference on Machine Learning, pp. 2061–2070. PMLR, 2016.
[60] Chengtao Li, Stefanie Jegelka, and Suvrit Sra: Fast mixing Markov chains for strongly Rayleigh measures, DPPs, and constrained sampling. In Advances in Neural Information Processing Systems 29, pp. 4195–4203, 2016.
[61] Hui Lin and Jeff Bilmes: Learning mixtures of submodular shells with application to document summarization. In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pp. 479–490, 2012.
[62] László Lovász: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory, 25(1):1–7, 1979.
[63] László Lovász: Graphs and Geometry. Volume 65. American Mathematical Soc., 2019.
[64] László Lovász, Michael Saks, and Alexander Schrijver: Orthogonal representations and connectivity of graphs. Linear Algebra and its Applications, 114-115:439–454, 1989.
[65] László Lovász, Michael Saks, and Alexander Schrijver: A correction: orthogonal representations and connectivity of graphs. Linear Algebra and its Applications, 313(1):101–105, 2000.
[66] László Lovász and Katalin Vesztergombi: Geometric representations of graphs. Paul Erdős and his Mathematics, 2, 1999.
[67] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak: Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.
[68] Russell Lyons: Determinantal probability measures. Publications Mathématiques de l’IHÉS, 98:167–212, 2003.
[69] Odile Macchi: The coincidence approach to stochastic point processes. Advances in Applied Probability, 7(1):83–122, 1975.
[70] Grigorii Aleksandrovich Margulis: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy peredachi informatsii, 24(1):51–60, 1988.
[71] Zelda Mariet, Mike Gartrell, and Suvrit Sra: Learning determinantal point processes by corrective negative sampling. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2251–2260, 2019.
[72] Zelda Mariet and Suvrit Sra: Fixed-point algorithms for learning determinantal point processes. In International Conference on Machine Learning, pp. 2389–2397, 2015.
[73] Zelda E Mariet and Suvrit Sra: Kronecker determinantal point processes. Advances in Neural Information Processing Systems, 29:2694–2702, 2016.
[74] Naoto Ohsaka: Unconstrained map inference, exponentiated determinantal point processes, and exponential inapproximability. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pp. 154–162, 2021.
[75] Takayuki Osogami and Rudy Raymond: Determinantal reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33(1), pp. 4659–4666, 2019.
[76] Takayuki Osogami, Rudy Raymond, Akshay Goel, Tomoyuki Shirai, and Takanori Maehara: Dynamic determinantal point processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32(1), 2018.
[77] Tory D. Parsons and Tomaž Pisanski: Vector representations of graphs. Discrete Mathematics, 78(1):143–154, 1989.
[78] René Peeters: Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica, 16(3):417–431, 1996.
[79] Leonard Pitt and Leslie G. Valiant: Computational limitations on learning from examples. Journal of the ACM (JACM), 35(4):965–984, 1988.
[80] Patrick Rebeschini and Amin Karbasi: Fast mixing for discrete point processes. In Conference on Learning Theory, pp. 1480–1500. PMLR, 2015.
[81] Zeév Rudnick and Peter Sarnak: Zeros of principal L-functions and random matrix theory. Duke Mathematical Journal, 81(2):269–322, 1996.
[82] Amar Shah and Zoubin Ghahramani: Determinantal clustering process-a nonparametric bayesian approach to kernel based semi-supervised clustering. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, pp. 566–575, 2013.
[83] Jasper Snoek, Richard Zemel, and Ryan Prescott Adams: A determinantal point process latent variable model for inhibition in neural spiking data. Advances in Neural Information Processing Systems 25, 2013.
[84] Alexander Soshnikov: Determinantal random point fields. Russian Mathematical Surveys, 55(5):923, 2000.
[85] Luca Trevisan: Non-approximability results for optimization problems on bounded degree instances. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 453–461, 2001.
[86] John Urschel, Victor-Emmanuel Brunel, Ankur Moitra, and Philippe Rigollet: Learning determinantal point processes with moments and cycles. In International Conference on Machine Learning, pp. 3511–3520. PMLR, 2017.
[87] Haotian Xu and Zhijian Ou: Scalable discovery of audio fingerprint motifs in broadcast streams with determinantal point process based motif clustering. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 24(5):978–989, 2016.
[88] Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang: Multi-agent determinantal q-learning. In International Conference on Machine Learning, pp. 10757–10766. PMLR, 2020.
[89] Jin-ge Yao, Feifan Fan, Wayne Xin Zhao, Xiaojun Wan, Edward Chang, and Jianguo Xiao: Tweet timeline generation with determinantal point processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30(1), 2016.
[90] Tao Zhou, Zoltán Kuscsik, Jian-Guo Liu, Matúš Medo, Joseph Rushton Wakeling, and Yi-Cheng Zhang: Solving the apparent diversity-accuracy dilemma of recommender systems. Proceedings of the National Academy of Sciences, 107(10):4511–4515, 2010.
[91] James Y. Zou and Ryan P. Adams: Priors for diversity in generative latent variable models. In Advances in Neural Information Processing Systems 24, pp. 2996–3004, 2012.
