革新知能統合研究センター

Video archive available!

Title: Scalable Determinantal Point Processes for Machine Learning

Abstract:
Determinantal point processes (DPPs) are a useful probabilistic model for selecting a small diverse subset out of a large collection of items, with applications in summarization, stochastic optimization, active learning and more.
In this talk, we will give a self contained introduction to DPP sampling and applications, as well as recent results on scaling these methods to millions of point.
Given a kernel function and a subset size , our goal is to sample out of items with probability proportional to the determinant of the kernel matrix induced by the subset (aka DPP). Existing DPP sampling algorithms require an expensive preprocessing step which involves multiple passes over all items, making it infeasible for large datasets. A naïve heuristic addressing this problem is to uniformly subsample a fraction of the data and perform DPP sampling only on those items, however this method offers no guarantee that the produced sample will even approximately resemble the target distribution over the original dataset. In this paper, we develop an algorithm which adaptively builds a sufficiently large uniform sample of data that is then used to efficiently generate a smaller set of items, while ensuring that this set is drawn exactly from the target distribution defined on all items. We show empirically that our algorithm produces a DPP sample after observing only a small fraction of all elements, leading to several orders of magnitude faster performance compared to the state-of-the-art.

Bio:
Daniele Calandriello is a Research Scientist at DeepMind Paris, where he works on scalable machine learning for sequential decision making.
He received his PhD in 2017 from INRIA Lille under the supervision of Michal Valko and Alessandro Lazaric, and his dissertation on efficient sequential learning won the french AI association award for best doctoral thesis. Prior to joining DeepMind PostDoc he worked on scalable non-parametric learning and sequential decision making at the Italian Institute of Technology as a member of Lorenzo Rosasco’s LCSL Lab, and on safety and efficiency in reinforcement learning as an undegraduate in Marcello Restelli’s group at Politecnico di Milano.
His research focuses on adaptive dimensionality reduction techniques using randomized subsampling and sketching. These techniques have been successfully applied (2014-2018) to optimization of noisy function, learning on graphs, clustering and supervised regression. His recent interest (2018-present) is to transfer some of these adaptive randomization techniques to experimental design and reinforcement learning.