TY - GEN
T1 - Robust budget allocation via continuous submodular functions
AU - Staib, Matthew
AU - Jegelka, Stefanie
N1 - Publisher Copyright:
Copyright © 2017 by the authors.
PY - 2017
Y1 - 2017
N2 - 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 adver-sary 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 min-imization is hard in general, here, we establish conditions under which such a problem can be solved to arbitrary precision e.
AB - 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 adver-sary 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 min-imization is hard in general, here, we establish conditions under which such a problem can be solved to arbitrary precision e.
UR - http://www.scopus.com/inward/record.url?scp=85047011210&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85047011210
T3 - 34th International Conference on Machine Learning, ICML 2017
SP - 4963
EP - 4980
BT - 34th International Conference on Machine Learning, ICML 2017
PB - International Machine Learning Society (IMLS)
T2 - 34th International Conference on Machine Learning, ICML 2017
Y2 - 6 August 2017 through 11 August 2017
ER -