Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm

Sepideh Mahabadi, Piotr Indyk, Shayan Oveis Gharan, Alireza Rezaei
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:4254-4263, 2019.

Abstract

“Composable core-sets” are an efficient framework for solving optimization problems in massive data models. In this work, we consider efficient construction of composable core-sets for the determinant maximization problem. This can also be cast as the MAP inference task for “determinantal point processes", that have recently gained a lot of interest for modeling diversity and fairness. The problem was recently studied in \cite{indyk2018composable}, where they designed composable core-sets with the optimal approximation bound of $O(k)^k$. On the other hand, the more practical “Greedy" algorithm has been previously used in similar contexts. In this work, first we provide a theoretical approximation guarantee of $C^{k^2}$ for the Greedy algorithm in the context of composable core-sets; Further, we propose to use a “Local Search" based algorithm that while being still practical, achieves a nearly optimal approximation bound of $O(k)^{2k}$; Finally, we implement all three algorithms and show the effectiveness of our proposed algorithm on standard data sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-mahabadi19a, title = {Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm}, author = {Mahabadi, Sepideh and Indyk, Piotr and Gharan, Shayan Oveis and Rezaei, Alireza}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {4254--4263}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/mahabadi19a/mahabadi19a.pdf}, url = {https://proceedings.mlr.press/v97/mahabadi19a.html}, abstract = {“Composable core-sets” are an efficient framework for solving optimization problems in massive data models. In this work, we consider efficient construction of composable core-sets for the determinant maximization problem. This can also be cast as the MAP inference task for “determinantal point processes", that have recently gained a lot of interest for modeling diversity and fairness. The problem was recently studied in \cite{indyk2018composable}, where they designed composable core-sets with the optimal approximation bound of $O(k)^k$. On the other hand, the more practical “Greedy" algorithm has been previously used in similar contexts. In this work, first we provide a theoretical approximation guarantee of $C^{k^2}$ for the Greedy algorithm in the context of composable core-sets; Further, we propose to use a “Local Search" based algorithm that while being still practical, achieves a nearly optimal approximation bound of $O(k)^{2k}$; Finally, we implement all three algorithms and show the effectiveness of our proposed algorithm on standard data sets.} }
Endnote
%0 Conference Paper %T Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm %A Sepideh Mahabadi %A Piotr Indyk %A Shayan Oveis Gharan %A Alireza Rezaei %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-mahabadi19a %I PMLR %P 4254--4263 %U https://proceedings.mlr.press/v97/mahabadi19a.html %V 97 %X “Composable core-sets” are an efficient framework for solving optimization problems in massive data models. In this work, we consider efficient construction of composable core-sets for the determinant maximization problem. This can also be cast as the MAP inference task for “determinantal point processes", that have recently gained a lot of interest for modeling diversity and fairness. The problem was recently studied in \cite{indyk2018composable}, where they designed composable core-sets with the optimal approximation bound of $O(k)^k$. On the other hand, the more practical “Greedy" algorithm has been previously used in similar contexts. In this work, first we provide a theoretical approximation guarantee of $C^{k^2}$ for the Greedy algorithm in the context of composable core-sets; Further, we propose to use a “Local Search" based algorithm that while being still practical, achieves a nearly optimal approximation bound of $O(k)^{2k}$; Finally, we implement all three algorithms and show the effectiveness of our proposed algorithm on standard data sets.
APA
Mahabadi, S., Indyk, P., Gharan, S.O. & Rezaei, A.. (2019). Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:4254-4263 Available from https://proceedings.mlr.press/v97/mahabadi19a.html.

Related Material