Adaptive Sampling for Fast Constrained Maximization of Submodular Functions

Francesco Quinzan, Vanja Doskoc, Andreas Göbel, Tobias Friedrich
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:964-972, 2021.

Abstract

Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a p-system side constraint, and it achieves a (p + O(sqrt(p)))-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a (p + O(1))-approximation when the given side constraint is a p-extendable system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-quinzan21a, title = { Adaptive Sampling for Fast Constrained Maximization of Submodular Functions }, author = {Quinzan, Francesco and Doskoc, Vanja and G{\"o}bel, Andreas and Friedrich, Tobias}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {964--972}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/quinzan21a/quinzan21a.pdf}, url = {https://proceedings.mlr.press/v130/quinzan21a.html}, abstract = { Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a p-system side constraint, and it achieves a (p + O(sqrt(p)))-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a (p + O(1))-approximation when the given side constraint is a p-extendable system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances. } }
Endnote
%0 Conference Paper %T Adaptive Sampling for Fast Constrained Maximization of Submodular Functions %A Francesco Quinzan %A Vanja Doskoc %A Andreas Göbel %A Tobias Friedrich %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-quinzan21a %I PMLR %P 964--972 %U https://proceedings.mlr.press/v130/quinzan21a.html %V 130 %X Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a p-system side constraint, and it achieves a (p + O(sqrt(p)))-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a (p + O(1))-approximation when the given side constraint is a p-extendable system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.
APA
Quinzan, F., Doskoc, V., Göbel, A. & Friedrich, T.. (2021). Adaptive Sampling for Fast Constrained Maximization of Submodular Functions . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:964-972 Available from https://proceedings.mlr.press/v130/quinzan21a.html.

Related Material