We study the complexity of sampling from a distribution over all index subsets of the set {1, ..., n} with the probability of a subset S proportional to the determinant of the submatrix LS of some n x n positive semidefinite matrix L, where LS corresponds to the entries of L indexed by S. Known as a determinantal point process (DPP), this distribution is used in machine learning to induce diversity in subset selection. When sampling from DDPs, we often wish to sample multiple subsets S with small expected size k = E[S] << n from a very large matrix L, so it is important to minimize the preprocessing cost of the procedure (performed once) as well as the sampling cost (performed repeatedly). For this purpose we provide DPPVFX, a new algorithm which, given access only to L, samples exactly from a determinantal point process while satisfying the following two properties: (1) its preprocessing cost is n poly(k), i.e., sublinear in the size of L, and (2) its sampling cost is poly(k), i.e., independent of the size of L. Prior to our results, stateoftheart exact samplers required O(n^3) preprocessing time and sampling time linear in n or dependent on the spectral properties of L. We furthermore give a reduction which allows using our algorithm for exact sampling from cardinality constrained determinantal point processes with n poly(k) time preprocessing. Our implementation of DPPVFX is provided at https://github.com/guilgautier/DPPy/.
Author Information
Michal Derezinski (UC Berkeley)
Daniele Calandriello (LCSL IIT/MIT)
Michal Valko (DeepMind Paris and Inria Lille  Nord Europe)
Michal is a research scientist in DeepMind Paris and SequeL team at Inria Lille  Nord Europe, France, lead by Philippe Preux and Rémi Munos. He also teaches the course Graphs in Machine Learning at l'ENS Cachan. Michal is primarily interested in designing algorithms that would require as little human supervision as possible. This means 1) reducing the “intelligence” that humans need to input into the system and 2) minimising the data that humans need spend inspecting, classifying, or “tuning” the algorithms. Another important feature of machine learning algorithms should be the ability to adapt to changing environments. That is why he is working in domains that are able to deal with minimal feedback, such as semisupervised learning, bandit algorithms, and anomaly detection. The common thread of Michal's work has been adaptive graphbased learning and its application to the real world applications such as recommender systems, medical error detection, and face recognition. His industrial collaborators include Intel, Technicolor, and Microsoft Research. He received his PhD in 2011 from University of Pittsburgh under the supervision of Miloš Hauskrecht and after was a postdoc of Rémi Munos.
More from the Same Authors

2019 Poster: Distributed estimation of the inverse Hessian by determinantal averaging »
Michal Derezinski · Michael W Mahoney 
2019 Poster: Planning in entropyregularized Markov decision processes and games »
JeanBastien Grill · Omar Darwiche Domingues · Pierre Menard · Remi Munos · Michal Valko 
2019 Poster: On two ways to use determinantal point processes for Monte Carlo integration »
Guillaume Gautier · Rémi Bardenet · Michal Valko 
2019 Poster: Multiagent Evaluation under Incomplete Information »
Mark Rowland · Shayegan Omidshafiei · Karl Tuyls · Julien Perolat · Michal Valko · Georgios Piliouras · Remi Munos 
2019 Spotlight: Multiagent Evaluation under Incomplete Information »
Mark Rowland · Shayegan Omidshafiei · Karl Tuyls · Julien Perolat · Michal Valko · Georgios Piliouras · Remi Munos 
2018 Poster: Optimistic optimization of a Brownian »
JeanBastien Grill · Michal Valko · Remi Munos 
2018 Poster: On Fast Leverage Score Sampling and Optimal Learning »
Alessandro Rudi · Daniele Calandriello · Luigi Carratino · Lorenzo Rosasco 
2018 Poster: Statistical and Computational TradeOffs in Kernel KMeans »
Daniele Calandriello · Lorenzo Rosasco 
2018 Spotlight: Statistical and Computational TradeOffs in Kernel KMeans »
Daniele Calandriello · Lorenzo Rosasco 
2018 Poster: Leveraged volume sampling for linear regression »
Michal Derezinski · Manfred K. Warmuth · Daniel Hsu 
2018 Spotlight: Leveraged volume sampling for linear regression »
Michal Derezinski · Manfred K. Warmuth · Daniel Hsu 
2017 Poster: Online Influence Maximization under Independent Cascade Model with SemiBandit Feedback »
Zheng Wen · Branislav Kveton · Michal Valko · Sharan Vaswani 
2017 Poster: Efficient SecondOrder Online Kernel Learning with Adaptive Embedding »
Daniele Calandriello · Alessandro Lazaric · Michal Valko 
2017 Poster: Unbiased estimates for linear regression via volume sampling »
Michal Derezinski · Manfred K. Warmuth 
2017 Spotlight: Unbiased estimates for linear regression via volume sampling »
Michal Derezinski · Manfred K. Warmuth 
2016 Poster: Blazing the trails before beating the path: Sampleefficient MonteCarlo planning »
JeanBastien Grill · Michal Valko · Remi Munos 
2016 Oral: Blazing the trails before beating the path: Sampleefficient MonteCarlo planning »
JeanBastien Grill · Michal Valko · Remi Munos 
2015 Poster: Blackbox optimization of noisy functions with unknown smoothness »
JeanBastien Grill · Michal Valko · Remi Munos · Remi Munos 
2014 Workshop: Second Workshop on Transfer and MultiTask Learning: Theory meets Practice »
Urun Dogan · Tatiana Tommasi · Yoshua Bengio · Francesco Orabona · Marius Kloft · Andres Munoz · Gunnar Rätsch · Hal Daumé III · Mehryar Mohri · Xuezhi Wang · Daniel Hernándezlobato · Song Liu · Thomas Unterthiner · Pascal Germain · Vinay P Namboodiri · Michael Goetz · Christopher Berlind · Sigurd Spieckermann · Marta Soare · Yujia Li · Vitaly Kuznetsov · Wenzhao Lian · Daniele Calandriello · Emilie Morvant 
2014 Poster: The limits of squared Euclidean distance regularization »
Michal Derezinski · Manfred K. Warmuth 
2014 Poster: Efficient learning by implicit exploration in bandit problems with side observations »
Tomáš Kocák · Gergely Neu · Michal Valko · Remi Munos 
2014 Spotlight: The limits of squared Euclidean distance regularization »
Michal Derezinski · Manfred K. Warmuth 
2014 Poster: Extreme bandits »
Alexandra Carpentier · Michal Valko 
2014 Poster: Online combinatorial optimization with stochastic decision sets and adversarial losses »
Gergely Neu · Michal Valko 
2014 Poster: Sparse MultiTask Reinforcement Learning »
Daniele Calandriello · Alessandro Lazaric · Marcello Restelli