One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes

Determinantal point processes are the standard probabilistic model of diverse subsets, used for example in recommender systems. Existing MAP inference algorithms for nonsymmetric DPPs must hold the whole dataset in memory, which is infeasible at industry scale. We started the study of streaming and online MAP inference for these models and designed one-pass algorithms that match the offline greedy algorithm using far less memory. We proved that no such algorithm has a worst-case guarantee, and gave one in the random-order model.

This work led to a granted US patent with Adobe Research. I am the sole first and corresponding author.