Abstract:
In this paper, we provide an efficient approximation algorithm for finding the most likelihood configuration (MAP) of size kk 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 ηη, our \online algorithm achieves a kO(k)kO(k) multiplicative approximation guarantee with an additive error ηη, using a memory footprint independent of the size of the data stream. We note that the exponential dependence on kk 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.