Timezone: »

 
Poster
Online MAP Inference of Determinantal Point Processes
Aditya Bhaskara · Amin Karbasi · Silvio Lattanzi · Morteza Zadimoghaddam

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1092
in Poster Session 4 »
In this paper, we provide an efficient approximation algorithm for finding the most likelihood configuration (MAP) of size $k$ for Determinantal Point Processes (DPP) in the online setting where the data points arrive in an arbitrary order and the algorithm cannot discard the selected elements from its local memory. Given a tolerance additive error $\eta$, our \online algorithm achieves a $k^{O(k)}$ multiplicative approximation guarantee with an additive error $\eta$, using a memory footprint independent of the size of the data stream. We note that the exponential dependence on $k$ in the approximation factor is unavoidable even in the offline setting. Our result readily implies a streaming algorithm with an improved memory bound compared to existing results.

Author Information

Aditya Bhaskara (University of Utah)
Amin Karbasi (Yale)
Silvio Lattanzi (Google Research)
Morteza Zadimoghaddam (Google Research)

More from the Same Authors