Robust Budget Allocation Via Continuous Submodular Functions
- PDF / 812,423 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 5 Downloads / 188 Views
Robust Budget Allocation Via Continuous Submodular Functions Matthew Staib1 · Stefanie Jegelka1
© Springer Science+Business Media, LLC, part of Springer Nature 2019
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. (in: WWW’12 - Proceedings of the 21st Annual Conference on World Wide, ACM, New York, 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 ε. Keywords Submodular optimization · Constrained submodular optimization · Robust optimization · Nonconvex optimization · Budget allocation
1 Introduction The optimal allocation of resources for maximizing influence, spread of information or coverage, has gained attention in the past few years, in particular in machine learning and data mining [15,19,24,36,43].
B
Matthew Staib [email protected] Stefanie Jegelka [email protected]
1
Department of EECS, Massachusetts Institute of Technology, Cambridge, MA, USA
123
Applied Mathematics & Optimization
Formally, in the Budget Allocation Problem, one is given a bipartite influence graph between channels S and people T , and the task is to assign a budget y(s) to each channel s in S with the goal of maximizing the expected number of influenced people I(y). Each edge (s, t) ∈ E between channel s and person t is weighted with a probability pst that, e.g., an advertisement on radio station s will influence person t to buy some product. The budget y(s) controls how many independent attempts are made via the channel s to influence the people in T . The probability that a customer t is influenced when the advertising budget is y is It (y) = 1 −
(s,t)∈E
[1 − pst ] y(s) ,
(1)
and hence the expected number of influenced people is I(y) = t∈T It (y). We write I(y; p) = I(y) to make the dependence on the probabilities pst explicit. The total budget y must remain within some feasible set Y which may encode e.g. a total budget limit s∈S y(s) ≤ C. We allow the budgets y to be continuous, as in [13]. Since its introduction in [2], several works have extended the formulation of Budget Allocation and provided algorithms [13,39,53,66,67]. Budget Allocation may also be viewed as influence maximization on a bipartite graph, where
Data Loading...
