A Greedy Approximation for k-Determinantal Point Processes

Julia Grosse, Rahel Fischer, Roman Garnett, Philipp Hennig
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:3052-3060, 2024.

Abstract

Determinantal point processes (DPPs) are an important concept in random matrix theory and combinatorics, and increasingly in machine learning. Samples from these processes exhibit a form of self-avoidance, so they are also helpful in guiding algorithms that explore to reduce uncertainty, such as in active learning, Bayesian optimization, reinforcement learning, and marginalization in graphical models. The best-known algorithms for sampling from DPPs exactly require significant computational expense, which can be unwelcome in machine learning applications when the cost of sampling is relatively low and capturing the precise repulsive nature of the DPP may not be critical. We suggest an inexpensive approximate strategy for sampling a fixed number of points (as would typically be desired in a machine learning setting) from a so-called $k$-DPP based on iterative inverse transform sampling. We prove that our algorithm satisfies a $(1 - 1/\epsilon)$ approximation guarantee relative to exact sampling from the $k$-DPP, and provide an efficient implementation for many common kernels used in machine learning, including the Gaussian and Matérn class. Finally, we compare the empirical runtime of our method to exact and Markov-Chain-Monte-Carlo (MCMC) samplers and investigate the approximation quality in a Bayesian Quadrature (BQ) setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-grosse24a, title = {A Greedy Approximation for k-Determinantal Point Processes}, author = {Grosse, Julia and Fischer, Rahel and Garnett, Roman and Hennig, Philipp}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {3052--3060}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/grosse24a/grosse24a.pdf}, url = {https://proceedings.mlr.press/v238/grosse24a.html}, abstract = {Determinantal point processes (DPPs) are an important concept in random matrix theory and combinatorics, and increasingly in machine learning. Samples from these processes exhibit a form of self-avoidance, so they are also helpful in guiding algorithms that explore to reduce uncertainty, such as in active learning, Bayesian optimization, reinforcement learning, and marginalization in graphical models. The best-known algorithms for sampling from DPPs exactly require significant computational expense, which can be unwelcome in machine learning applications when the cost of sampling is relatively low and capturing the precise repulsive nature of the DPP may not be critical. We suggest an inexpensive approximate strategy for sampling a fixed number of points (as would typically be desired in a machine learning setting) from a so-called $k$-DPP based on iterative inverse transform sampling. We prove that our algorithm satisfies a $(1 - 1/\epsilon)$ approximation guarantee relative to exact sampling from the $k$-DPP, and provide an efficient implementation for many common kernels used in machine learning, including the Gaussian and Matérn class. Finally, we compare the empirical runtime of our method to exact and Markov-Chain-Monte-Carlo (MCMC) samplers and investigate the approximation quality in a Bayesian Quadrature (BQ) setting.} }
Endnote
%0 Conference Paper %T A Greedy Approximation for k-Determinantal Point Processes %A Julia Grosse %A Rahel Fischer %A Roman Garnett %A Philipp Hennig %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-grosse24a %I PMLR %P 3052--3060 %U https://proceedings.mlr.press/v238/grosse24a.html %V 238 %X Determinantal point processes (DPPs) are an important concept in random matrix theory and combinatorics, and increasingly in machine learning. Samples from these processes exhibit a form of self-avoidance, so they are also helpful in guiding algorithms that explore to reduce uncertainty, such as in active learning, Bayesian optimization, reinforcement learning, and marginalization in graphical models. The best-known algorithms for sampling from DPPs exactly require significant computational expense, which can be unwelcome in machine learning applications when the cost of sampling is relatively low and capturing the precise repulsive nature of the DPP may not be critical. We suggest an inexpensive approximate strategy for sampling a fixed number of points (as would typically be desired in a machine learning setting) from a so-called $k$-DPP based on iterative inverse transform sampling. We prove that our algorithm satisfies a $(1 - 1/\epsilon)$ approximation guarantee relative to exact sampling from the $k$-DPP, and provide an efficient implementation for many common kernels used in machine learning, including the Gaussian and Matérn class. Finally, we compare the empirical runtime of our method to exact and Markov-Chain-Monte-Carlo (MCMC) samplers and investigate the approximation quality in a Bayesian Quadrature (BQ) setting.
APA
Grosse, J., Fischer, R., Garnett, R. & Hennig, P.. (2024). A Greedy Approximation for k-Determinantal Point Processes. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:3052-3060 Available from https://proceedings.mlr.press/v238/grosse24a.html.

Related Material