Streaming k-Submodular Maximization under Noise subject to Size Constraint

Lan Nguyen, My T. Thai
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:7338-7347, 2020.

Abstract

Maximizing on k-submodular functions subject to size constraint has received extensive attention recently. In this paper, we investigate a more realistic scenario of this problem that (1) obtaining exact evaluation of an objective function is impractical, instead, its noisy version is acquired; and (2) algorithms are required to take only one single pass over dataset, producing solutions in a timely manner. We propose two novel streaming algorithms, namely DStream and RStream, with their theoretical performance guarantees. We further demonstrate the efficiency of our algorithms in two application, showing that our algorithms can return comparative results to state-of-the-art non-streaming methods while using a much fewer number of queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-nguyen20f, title = {Streaming k-Submodular Maximization under Noise subject to Size Constraint}, author = {Nguyen, Lan and Thai, My T.}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {7338--7347}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/nguyen20f/nguyen20f.pdf}, url = {https://proceedings.mlr.press/v119/nguyen20f.html}, abstract = {Maximizing on k-submodular functions subject to size constraint has received extensive attention recently. In this paper, we investigate a more realistic scenario of this problem that (1) obtaining exact evaluation of an objective function is impractical, instead, its noisy version is acquired; and (2) algorithms are required to take only one single pass over dataset, producing solutions in a timely manner. We propose two novel streaming algorithms, namely DStream and RStream, with their theoretical performance guarantees. We further demonstrate the efficiency of our algorithms in two application, showing that our algorithms can return comparative results to state-of-the-art non-streaming methods while using a much fewer number of queries.} }
Endnote
%0 Conference Paper %T Streaming k-Submodular Maximization under Noise subject to Size Constraint %A Lan Nguyen %A My T. Thai %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-nguyen20f %I PMLR %P 7338--7347 %U https://proceedings.mlr.press/v119/nguyen20f.html %V 119 %X Maximizing on k-submodular functions subject to size constraint has received extensive attention recently. In this paper, we investigate a more realistic scenario of this problem that (1) obtaining exact evaluation of an objective function is impractical, instead, its noisy version is acquired; and (2) algorithms are required to take only one single pass over dataset, producing solutions in a timely manner. We propose two novel streaming algorithms, namely DStream and RStream, with their theoretical performance guarantees. We further demonstrate the efficiency of our algorithms in two application, showing that our algorithms can return comparative results to state-of-the-art non-streaming methods while using a much fewer number of queries.
APA
Nguyen, L. & Thai, M.T.. (2020). Streaming k-Submodular Maximization under Noise subject to Size Constraint. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:7338-7347 Available from https://proceedings.mlr.press/v119/nguyen20f.html.

Related Material