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 Ahmed
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:18463-18482, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-reddy22a, title = {One-Pass Algorithms for {MAP} Inference of Nonsymmetric Determinantal Point Processes}, author = {Reddy, Aravind and Rossi, Ryan A. and Song, Zhao and Rao, Anup and Mai, Tung and Lipka, Nedim and Wu, Gang and Koh, Eunyee and Ahmed, Nesreen}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {18463--18482}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/reddy22a/reddy22a.pdf}, url = {https://proceedings.mlr.press/v162/reddy22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes %A Aravind Reddy %A Ryan A. Rossi %A Zhao Song %A Anup Rao %A Tung Mai %A Nedim Lipka %A Gang Wu %A Eunyee Koh %A Nesreen Ahmed %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-reddy22a %I PMLR %P 18463--18482 %U https://proceedings.mlr.press/v162/reddy22a.html %V 162 %X 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.
APA
Reddy, A., Rossi, R.A., Song, Z., Rao, A., Mai, T., Lipka, N., Wu, G., Koh, E. & Ahmed, N.. (2022). One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:18463-18482 Available from https://proceedings.mlr.press/v162/reddy22a.html.

Related Material