Timezone: »

 
Poster
One-Pass algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes
Aravind Reddy · Ryan A. Rossi · Zhao Song · Anup Rao · Tung Mai · Nedim Lipka · Gang Wu · Eunyee Koh · Nesreen K Ahmed

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #1206
in Poster Session 1 »

In this paper, we initiate the study of streaming and online MAP inference problems for Non-symmetric Determinantal Point Processes (NDPPs) and provide one-pass algorithms for solving these problems. In the streaming setting, data points arrive in an arbitrary order and the algorithms are constrained to use a single-pass over the data as well as sub-linear memory, and only need to output a valid solution at the end of the stream. The online setting has an additional requirement of maintaining a valid solution at any point in time. We design new algorithms for these problems with provable guarantees and show that empirically, they perform comparably or even better than state-of-the-art offline algorithm while using substantially lower memory.

Keywords: OPT: Discrete and Combinatorial Optimization · T: Probabilistic Methods · MISC: Scalable Algorithms

Author Information

Aravind Reddy (Northwestern University)
Ryan A. Rossi (Adobe Research)
Zhao Song (Adobe Research)
Anup Rao (Adobe Research)
Tung Mai (Adobe Research)
Nedim Lipka (Adobe Research)
Gang Wu (Adobe Research)
Eunyee Koh (Adobe)
Nesreen K Ahmed (Intel AI Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors