Timezone: »
DPP MAP inference, the problem of finding the highest probability set under the distribution defined by a DPP, is of practical importance for a variety of areas such as recommender systems, active learning, and data compression. Unfortunately, finding the exact MAP solution is NP-hard. Often though, the standard greedy submodular maximization algorithm works well in practice for approximating the solution. In this talk, we discuss ways to speed up this simple greedy algorithm, as well as slower, but more accurate alternatives to it. We also discuss how to scale greedy for customized DPPs, where we want to solve the MAP problem multiple times with different weightings of item features. We conclude with a brief note on the complexity of MAP for nonsymmetric DPPs, where we show that greedy scales fairly well if we assume a particular kernel decomposition.
Author Information
Jennifer Gillenwater (Google Research NYC)
More from the Same Authors
-
2021 : Differentially Private Quantiles »
Jennifer Gillenwater · Matthew Joseph · Alex Kulesza -
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 -
2019 Workshop: Negative Dependence: Theory and Applications in Machine Learning »
Mike Gartrell · Jennifer Gillenwater · Alex Kulesza · Zelda Mariet -
2019 Poster: A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes »
Jennifer Gillenwater · Alex Kulesza · Zelda Mariet · Sergei Vassilvitskii -
2019 Oral: A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes »
Jennifer Gillenwater · Alex Kulesza · Zelda Mariet · Sergei Vassilvitskii