Online MAP Inference of Determinantal Point Processes

In this paper, we provide efficient approximation algorithms for finding the most likelihood configuration (MAP) of size $k$ for Determinantal Point Processes (DPP) in the online and streaming settings where the data points arrive in an arbitrary order. More specifically, in the online setting, where the algorithm cannot discard the selected elements from its local memory, our Online-DPP algorithm achieves an $O(k^{O(k)})$ multiplicative approximation with $\eta$ additive error, using memory independent of the number of points. In the streaming setting, where the algorithm is allowed to discard the previously selected elements, our Stream-DPP algorithm achieves an $O(k^{O(k)})$ multiplicative approximation (and no additive error), with similar memory bounds. We note that the exponential dependence on $k$ in the approximation factor is unavoidable even in the offline setting.

• Algorithms and Theory