Timezone: »
In this paper, we initiate the study of one-pass algorithms for solving the maximum-a-posteriori (MAP) inference problem for Non-symmetric Determinantal Point Processes (NDPPs). In particular, we formulate streaming and online versions of the problem and provide one-pass algorithms for solving these problems. In our 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. Our online setting has an additional requirement of maintaining a valid solution at any point in time. We design new one-pass algorithms for these problems and show that they perform comparably to (or even better than) the offline greedy algorithm while using substantially lower memory.
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)
-
2022 Poster: One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes »
Tue. Jul 19th through Wed the 20th Room Hall E #1124
More from the Same Authors
-
2021 : Coresets for Classification – Simplified and Strengthened »
Anup Rao · Tung Mai · Cameron Musco -
2022 : Single, Practical and Fast Dynamic Truncation Kernel Multiplication »
Lianke Qin · Somdeb Sarkhel · Zhao Song · Danyang Zhuo -
2022 Poster: Bounding the Width of Neural Networks via Coupled Initialization - A Worst Case Analysis »
Alexander Munteanu · Simon Omlor · Zhao Song · David Woodruff -
2022 Poster: Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning »
Mayee Chen · Daniel Y Fu · Avanika Narayan · Michael Zhang · Zhao Song · Kayvon Fatahalian · Christopher Re -
2022 Spotlight: Bounding the Width of Neural Networks via Coupled Initialization - A Worst Case Analysis »
Alexander Munteanu · Simon Omlor · Zhao Song · David Woodruff -
2022 Spotlight: Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning »
Mayee Chen · Daniel Y Fu · Avanika Narayan · Michael Zhang · Zhao Song · Kayvon Fatahalian · Christopher Re -
2022 Poster: Online Balanced Experimental Design »
David Arbour · Drew Dimmery · Tung Mai · Anup Rao -
2022 Spotlight: Online Balanced Experimental Design »
David Arbour · Drew Dimmery · Tung Mai · Anup Rao -
2021 : Coresets for Classification – Simplified and Strengthened »
Tung Mai · Anup Rao · Cameron Musco -
2021 Poster: Asymptotics of Ridge Regression in Convolutional Models »
Mojtaba Sahraee-Ardakan · Tung Mai · Anup Rao · Ryan A. Rossi · Sundeep Rangan · Alyson Fletcher -
2021 Spotlight: Asymptotics of Ridge Regression in Convolutional Models »
Mojtaba Sahraee-Ardakan · Tung Mai · Anup Rao · Ryan A. Rossi · Sundeep Rangan · Alyson Fletcher -
2021 Poster: Fundamental Tradeoffs in Distributionally Adversarial Training »
Mohammad Mehrabi · Adel Javanmard · Ryan A. Rossi · Anup Rao · Tung Mai -
2021 Spotlight: Fundamental Tradeoffs in Distributionally Adversarial Training »
Mohammad Mehrabi · Adel Javanmard · Ryan A. Rossi · Anup Rao · Tung Mai -
2020 Poster: Structured Policy Iteration for Linear Quadratic Regulator »
Youngsuk Park · Ryan A. Rossi · Zheng Wen · Gang Wu · Handong Zhao