Timezone: »

 
Oral
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
Sepideh Mahabadi · Piotr Indyk · Shayan Oveis Gharan · Alireza Rezaei

Tue Jun 11 04:00 PM -- 04:20 PM (PDT) @ Grand Ballroom
in Large Scale Learning and Systems »
``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.
[ Slides]  [ Video] 

Author Information

Sepideh Mahabadi (Toyota Technological Institute at Chicago)
Piotr Indyk (MIT)
Shayan Oveis Gharan (University of Washington)
Alireza Rezaei (University of Washington)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors