Robust Budget Allocation via Continuous Submodular Functions

Matthew Staib, Stefanie Jegelka
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:3230-3240, 2017.

Abstract

The optimal allocation of resources for maximizing influence, spread of information or coverage, has gained attention in the past years, in particular in machine learning and data mining. But in applications, the parameters of the problem are rarely known exactly, and using wrong parameters can lead to undesirable outcomes. We hence revisit a continuous version of the Budget Allocation or Bipartite Influence Maximization problem introduced by Alon et al. (2012) from a robust optimization perspective, where an adversary may choose the least favorable parameters within a confidence set. The resulting problem is a nonconvex-concave saddle point problem (or game). We show that this nonconvex problem can be solved exactly by leveraging connections to continuous submodular functions, and by solving a constrained submodular minimization problem. Although constrained submodular minimization is hard in general, here, we establish conditions under which such a problem can be solved to arbitrary precision $\epsilon$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-staib17a, title = {Robust Budget Allocation via Continuous Submodular Functions}, author = {Matthew Staib and Stefanie Jegelka}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {3230--3240}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/staib17a/staib17a.pdf}, url = {https://proceedings.mlr.press/v70/staib17a.html}, abstract = {The optimal allocation of resources for maximizing influence, spread of information or coverage, has gained attention in the past years, in particular in machine learning and data mining. But in applications, the parameters of the problem are rarely known exactly, and using wrong parameters can lead to undesirable outcomes. We hence revisit a continuous version of the Budget Allocation or Bipartite Influence Maximization problem introduced by Alon et al. (2012) from a robust optimization perspective, where an adversary may choose the least favorable parameters within a confidence set. The resulting problem is a nonconvex-concave saddle point problem (or game). We show that this nonconvex problem can be solved exactly by leveraging connections to continuous submodular functions, and by solving a constrained submodular minimization problem. Although constrained submodular minimization is hard in general, here, we establish conditions under which such a problem can be solved to arbitrary precision $\epsilon$.} }
Endnote
%0 Conference Paper %T Robust Budget Allocation via Continuous Submodular Functions %A Matthew Staib %A Stefanie Jegelka %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-staib17a %I PMLR %P 3230--3240 %U https://proceedings.mlr.press/v70/staib17a.html %V 70 %X The optimal allocation of resources for maximizing influence, spread of information or coverage, has gained attention in the past years, in particular in machine learning and data mining. But in applications, the parameters of the problem are rarely known exactly, and using wrong parameters can lead to undesirable outcomes. We hence revisit a continuous version of the Budget Allocation or Bipartite Influence Maximization problem introduced by Alon et al. (2012) from a robust optimization perspective, where an adversary may choose the least favorable parameters within a confidence set. The resulting problem is a nonconvex-concave saddle point problem (or game). We show that this nonconvex problem can be solved exactly by leveraging connections to continuous submodular functions, and by solving a constrained submodular minimization problem. Although constrained submodular minimization is hard in general, here, we establish conditions under which such a problem can be solved to arbitrary precision $\epsilon$.
APA
Staib, M. & Jegelka, S.. (2017). Robust Budget Allocation via Continuous Submodular Functions. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:3230-3240 Available from https://proceedings.mlr.press/v70/staib17a.html.

Related Material