Timezone: »
It is often desirable for recommender systems and other information retrieval applications to provide diverse results, and determinantal point processes (DPPs) have become a popular way to capture the trade-off between the quality of individual results and the diversity of the overall set. However, computational concerns limit the usefulness of DPPs in practice. Sampling from a DPP is inherently expensive: if the underlying collection contains N items, then generating each DPP sample requires O(N) time following a one-time preprocessing phase. Additionally, results often need to be personalized to a user, but standard approaches to personalization invalidate the preprocessing, making personalized samples especially expensive. In this work we address both of these shortcomings. First, we propose a new algorithm for generating DPP samples in O(log N) time following a slightly more expensive preprocessing phase. We then extend the algorithm to support arbitrary query-time feature weights, allowing us to generate samples customized to individual users while still retaining logarithmic runtime. Experiments show that our approach runs over 300 times faster than traditional DPP sampling on collections of 100,000 items for samples of size 10.
Author Information
Jennifer Gillenwater (Google Research NYC)
Alex Kulesza (Google)
Zelda Mariet (MIT)
Sergei Vassilvitskii (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes »
Thu. Jun 13th 01:30 -- 04:00 AM Room Pacific Ballroom #230
More from the Same Authors
-
2021 : Differentially Private Quantiles »
Jennifer Gillenwater · Matthew Joseph · Alex Kulesza -
2023 Tutorial: How to DP-fy ML: A Practical Tutorial to Machine Learning with Differential Privacy »
Sergei Vassilvitskii · Natalia Ponomareva · Zheng Xu -
2022 Poster: A Joint Exponential Mechanism For Differentially Private Top-$k$ »
Jennifer Gillenwater · Matthew Joseph · andres munoz · Monica Ribero Diaz -
2022 Spotlight: A Joint Exponential Mechanism For Differentially Private Top-$k$ »
Jennifer Gillenwater · Matthew Joseph · andres munoz · Monica Ribero Diaz -
2021 Poster: Differentially Private Quantiles »
Jennifer Gillenwater · Matthew Joseph · Alex Kulesza -
2021 Spotlight: Differentially Private Quantiles »
Jennifer Gillenwater · Matthew Joseph · Alex Kulesza -
2020 : Scaling DPP MAP Inference »
Jennifer Gillenwater -
2019 Workshop: Negative Dependence: Theory and Applications in Machine Learning »
Mike Gartrell · Jennifer Gillenwater · Alex Kulesza · Zelda Mariet -
2019 Poster: Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy »
Kareem Amin · Alex Kulesza · andres munoz · Sergei Vassilvitskii -
2019 Oral: Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy »
Kareem Amin · Alex Kulesza · andres munoz · Sergei Vassilvitskii -
2018 Poster: Competitive Caching with Machine Learned Advice »
Thodoris Lykouris · Sergei Vassilvitskii -
2018 Oral: Competitive Caching with Machine Learned Advice »
Thodoris Lykouris · Sergei Vassilvitskii -
2017 Poster: Consistent k-Clustering »
Silvio Lattanzi · Sergei Vassilvitskii -
2017 Talk: Consistent k-Clustering »
Silvio Lattanzi · Sergei Vassilvitskii