Skip to yearly menu bar Skip to main content


Online MAP Inference of Determinantal Point Processes

Aditya Bhaskara · Amin Karbasi · Silvio Lattanzi · Morteza Zadimoghaddam

Poster Session 3 #1092

Abstract: 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.

Chat is not available.