Robust Budget Allocation via Continuous Submodular Functions
Matthew Staib and Stefanie Jegelka

arXiv:1702.08791v2 [cs.LG] 13 Jun 2017

Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology
{mstaib, stefje}@mit.edu

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 .

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 [Domingos
& Richardson, 2001; Kempe et al., 2003; Chen et al., 2009; Gomez Rodriguez & Schölkopf, 2012;
Borgs et al., 2014].
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
Y
It (y) = 1 −
[1 − pst ]y(s) ,
(1)
(s,t)∈E

P
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 totalPbudget 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 [Bian et al., 2017].
1

Since its introduction by Alon et al. [2012], several works have extended the formulation of
Budget Allocation and provided algorithms Bian et al. [2017]; Hatano et al. [2015]; Maehara et al.
[2015]; Soma et al. [2014]; Soma & Yoshida [2015]. Budget Allocation may also be viewed as
influence maximization on a bipartite graph, where information spreads as in the Independent
Cascade model. For integer y, Budget Allocation and Influence Maximization are NP-hard. Yet,
constant-factor approximations are possible, and build on the fact that the influence function is
submodular in the binary case, and DR-submodular in the integer case [Soma et al., 2014; Hatano
et al., 2015]. If y is continuous, the problem is a concave maximization problem.
The formulation of Budget Allocation assumes that the transmission probabilities are known
exactly. But this is rarely true in practice. Typically, the probabilities pst , and possibly the
graph itself, must be inferred from observations [Gomez Rodriguez et al., 2010; Du et al., 2013;
Narasimhan et al., 2015; Du et al., 2014; Netrapalli & Sanghavi, 2012]. In Section 4 we will see that
a misspecification or point estimate of parameters pst can lead to much reduced outcomes. A more
realistic assumption is to know confidence intervals for the pst . Realizing this severe deficiency,
recent work studied robust versions of Influence Maximization, where a budget y must be chosen
that maximizes the worst-case approximation ratio over a set of possible influence functions [He &
Kempe, 2016; Chen et al., 2016; Lowalekar et al., 2016]. The resulting optimization problem is
hard but admits bicriteria approximations.
In this work, we revisit Budget Allocation under uncertainty from the perspective of robust
optimization [Bertsimas et al., 2011; Ben-Tal et al., 2009]. We maximize the worst-case influence –
not approximation ratio – for p in a confidence set centered around the “best guess” (e.g., posterior
mean). This avoids pitfalls of the approximation ratio formulation (which can be misled to return
poor worst-case budgets, as demonstrated in Appendix A), while also allowing us to formulate the
problem as a max-min game:
max min I(y; p),
(2)
y∈Y

p∈P

where an “adversary” can arbitrarily manipulate p within the confidence set P. With p fixed, I(y; p)
is concave in y. However, the influence function I(y; p) is not convex, and not even quasiconvex,
in the adversary’s variables pst .
The new, key insight we exploit in this work is that I(y; p) has the property of continuous
submodularity in p – in contrast to previously exploited submodular maximization in y – and can
hence be minimized by generalizing techniques from discrete submodular optimization Bach [2015].
The techniques in [Bach, 2015], however, are restricted to box constraints, and do not directly apply
to our confidence sets. In fact, general constrained submodular minimization is hard [Svitkina &
Fleischer, 2011; Goel et al., 2009; Iwata & Nagano, 2009]. We make the following contributions:
1. We present an algorithm with optimality bounds for Robust Budget Allocation in the nonconvex adversarial scenario (2).
2. We provide the first results for continuous submodular minimization with box constraints
and one more “nice” constraint, and conditions under which the algorithm is guaranteed to
return a global optimum.

1.1

Background and Related Work

We begin with some background material and, along the way, discuss related work.

2

1.1.1

Submodularity over the integer lattice and continuous domains

Submodularity is perhaps best known as a property of set functions. A function F : 2V → R
defined on subsets S ⊆ V of a ground set V is submodular if for all sets S, T ⊆ V , it holds that
F (S) + F (T ) ≥ F (S ∩ T ) + F (S ∪ T ). A similar definition extends to functions defined over a
distributive lattice L, e.g. the integer lattice. Such a function f is submodular if for all x, y ∈ L,
it holds that
f (x) + f (y) ≥ f (x ∨ y) + f (x ∧ y).
(3)
For the integer lattice and vectors x, y, x ∨ y denotes the coordinate-wise maximum and x ∧ y the
coordinate-wise minimum. Submodularity has also been considered on continuous domains X ⊂ Rd ,
where, if f is also twice-differentiable, the property of submodularity means that all off-diagonal
∂f (x)
entries of the the Hessian are nonpositive, i.e., ∂x
≤ 0 for all i 6= j [Topkis, 1978, Theorem 3.2].
i ∂xj
These functions may be convex, concave, or neither.
Submodular functions on lattices can be minimized by a reduction to set functions, more precisely, ring families Birkhoff [1937]. Combinatorial algorithms for submodular optimization on lattices are discussed in [Khachaturov et al., 2012]. More recently, Bach [2015] extended results based
on the convex Lovász extension, by building on connections to optimal transport. The subclass of
L\ -convex functions admits strongly polynomial time minimization [Murota, 2003; Kolmogorov &
Shioura, 2009; Murota & Shioura, 2014], but does not apply in our setting.
Similarly, results for submodular maximization extend to integer lattices, e.g. [Gottschalk &
Peis, 2015]. Stronger results are possible if the submodular function also satisfies diminishing
returns: for all x ≤ y (coordinate-wise) and i such that y + ei ∈ X , it holds that f (x + ei ) − f (x) ≥
f (y + ei ) − f (y). For such DR-submodular functions, many approximation results for the set
function case extend [Bian et al., 2017; Soma & Yoshida, 2015; Soma et al., 2014]. In particular,
Ene & Nguyen [2016] show a generic reduction to set function optimization that they apply to
maximization. In fact, it also applies to minimization:
Q
Proposition 1.1. A DR-submodular function f defined on ni=1 [ki ] can be minimized in strongly
polynomial time O(n4 log4 k · log2 (n log k) · EO + n4 log4 k · logO(1) (n log k)), where k = maxi ki and
EO is the time complexity of evaluating f . Here, [ki ] = {0, 1, . . . , ki − 1}.
Proof. The function f can be reduced to a submodular set function g : 2V → R via [Ene & Nguyen,
2016], where |V | = O(n log k). The function g can be evaluated via mapping from 2V to the domain
of f , and then evaluating f , in time O(n log k · EO). We can directly substitute these complexities
into the runtime bound from [Lee et al., 2015].
In particular, the time complexity is logarithmic in k. For general lattice submodular functions,
this is not possible without further assumptions.
1.1.2

Related Problems

A sister problem of Budget Allocation is Influence Maximization on general graphs, where a set
of seed nodes is selected to start a propagation process. The influence function is still monotone
submodular and amenable to the greedy algorithm Kempe et al. [2003], but it cannot be evaluated
explicitly and requires approximation Chen et al. [2010]. Stochastic Coverage [Goemans & Vondrák,
2006] is a version of Set Cover where the covering sets Si ⊂ V are random. A variant of Budget
Allocation can be written as stochastic coverage with multiplicity. Stochastic Coverage has mainly
3

been studied in the online or adaptive setting, where logarithmic approximation factors can be
achieved [Golovin & Krause, 2011; Deshpande et al., 2016; Adamczyk et al., 2016].
Our
Q objective function (2) is a signomial in p, i.e., a linear combination of monomials of the
form i xci i . General signomial optimization is NP-hard [Chiang, 2005], but certain subclasses are
tractable: posynomials with all nonnegative coefficients can be minimized via Geometric Programming [Boyd et al., 2007], and signomials with a single negative coefficient admit sum of squares-like
relaxations [Chandrasekaran & Shah, 2016]. Our problem, a constrained posynomial maximization,
is not in general a geometric program. Some work addresses this setting via monomial approximation [Pascual & Ben-Israel, 1970; Ecker, 1980], but, to our knowledge, our algorithm is the first
that solves this problem to arbitrary accuracy.
1.1.3

Robust Optimization

Two prominent strategies of addressing uncertainty in parameters of optimization problems are
stochastic and robust optimization. If the distribution of the parameters is known (stochastic optimization), formulations such as value-at-risk (VaR) and conditional value-at-risk (CVaR) Rockafellar & Uryasev [2000, 2002] apply. In contrast, robust optimization [Ben-Tal et al., 2009; Bertsimas
et al., 2011] assumes that the parameters (of the cost function and constraints) can vary arbitrarily
within a known confidence set U , and the aim is to optimize the worst-case setting, i.e.,
min sup {g(y; u) s.t. Ay ≤ b}.
y

(4)

u,A,b∈U

Here, we will only have uncertainty in the cost function.
In this paper we are principally concerned with robust maximization of the continuous influence
function I(y), but mention some results for the discrete case. While there exist results for robust
and CVaR optimization of modular (linear) functions [Nikolova, 2010; Bertsimas & Sim, 2003],
submodular objectives do not in general admit such optimization Maehara [2015], but variants
admit approximations [Zhang et al., 2014]. The brittleness of submodular optimization under noise
has been studied in [Balkanski et al., 2016, 2017; Hassidim & Singer, 2016].
Approximations for robust submodular and influence optimization have been studied in [Krause
et al., 2008; He & Kempe, 2016; Chen et al., 2016; Lowalekar et al., 2016], where an adversary can
pick among a finite set of objective functions or remove selected elements Orlin et al. [2016].

2

Robust and Stochastic Budget Allocation

The unknown parameters in Budget Allocation are the transmission probabilities pst or edge weights
in a graph. If these are estimated from data, we may have posterior distributions or, a weaker
assumption, confidence sets for the parameters. For ease of notation, we will work with the failure
probabilities xst = 1 − pst instead of the pst directly, and write I(y; x) instead of I(y; p).

2.1

Stochastic Optimization

If a (posterior) distribution of the parameters is known, a simple strategy is to use expectations.
We place a uniform prior on xst , and observe nst independent observations drawn from Ber(xst ).
If we observe αst failures and and βst successes, the resulting posterior distribution on the variable

4

Xst is Beta(1 + αst , 1 + βst ). Given such a posterior, we may optimize
max I(y; E[X]), or

(5)

max E[I(y; X)].

(6)

y∈Y

y∈Y

Proposition 2.1. Problems (5) and (6) are concave maximization problems over the (convex) set
Y and can be solved exactly.
Concavity of (6) follows since it is an expectation over concave functions, and the problem can
be solved by stochastic gradient ascent or by explicitly computing gradients.
Merely maximizing expectation does not explicitly account for volatility and hence risk. One
option is to include variance Ben-Tal & Nemirovski [2000]; Bertsimas et al. [2011]; Atamtürk &
Narayanan [2008]:
p
min −E[I(y; X)] + ε Var(I(y; X)),
(7)
y∈Y

but in our case this CVaR formulation seems difficult:
p
Fact 2.1. For y in the nonnegative orthant, the term Var(I(y; X)) need not be convex or concave,
and need not be submodular or supermodular.
This observation does not rule out a solution, but the apparent difficulties further motivate a
robust formulation that, as we will see, is amenable to optimization.

2.2

Robust Optimization

The focus of this work is the robust version of Budget Allocation, where we allow an adversary to
arbitrarily set the parameters x within an uncertainty set X . This uncertainty set may result, for
instance, from a known distribution, or simply assumed bounds. Formally, we solve
max min I(y; x),
y∈Y x∈X

(8)

where Y ⊂ RS+ is a convex set with an efficient projection oracle, and X is an uncertainty set
containing an estimate x̂. In the sequel, we use uncertainty sets X = {x ∈ Box(l,Q
u) : R(x) ≤ B},
where R is a distance (or divergence) from the estimate x̂, and Box(l, u) is the box (s,t)∈E [lst , ust ].
The intervals [lst , ust ] can be thought of as either confidence intervals around x̂, or, if [lst , ust ] = [0, 1],
enforce that each xst is a valid probability.
Common examples of uncertainty sets used in Robust Optimization are Ellipsoidal and D-norm
uncertainty sets Bertsimas et al. [2011]. Our algorithm in Section 3.1 applies to both.
Ellipsoidal uncertainty. The ellipsoidal or quadratic uncertainty set is defined by
X Q (γ) = {x ∈ Box(0, 1) : (x − x̂)T Σ−1 (x − x̂) ≤ γ},
where Σ is the covariance of the random vector X of probabilities distributed according to our
Beta posteriors. In our case, since the distributions on each xst are independent, Σ−1 is actually
diagonal. Writing Σ = diag(σ 2 ), we have
n
o
X
X Q (γ) = x ∈ Box(0, 1) :
Rst (xst ) ≤ γ ,
(s,t)∈E

5

−2
where Rst (x) = (xst − x̂st )2 σst
.
D-norm uncertainty. The D-norm uncertainty set is similar to an `1 -ball around x̂, and is
defined as
n
X D (γ) = x : ∃c ∈ Box(0, 1) s.t.

xst = x̂st + (ust − x̂st )cst ,

X

o
cst ≤ γ .

(s,t)∈E

Essentially, we allow an adversary to increase x̂st up to some upper bound ust , subject to some
total budget γ across all terms xst . The set X D (γ) can be rewritten as
o
n
X
Rst (xst ) ≤ γ ,
X D (γ) = x ∈ Box(x̂, u) :
(s,t)∈E

where Rst (xst ) = (xst − x̂st )/(ust − x̂st ) is the fraction of the interval [x̂st , ust ] we have used up in
increasing xst .
The min-max formulation maxy∈Y minx∈X I(y; x) has several merits: the model is not tied to
a specific learning algorithm for the probabilities x as long as we can choose a suitable confidence
set. Moreover, this formulation allows to fully hedge against a worst-case scenario.

3

Optimization Algorithm

As noted above, the function I(y; x) is concave as a function of y for fixed x. As a pointwise
minimum of concave functions, F (y) := minx∈X I(y; x) is concave. Hence, if we can compute
subgradients of F (y), we can solve our max-min-problem via the subgradient method, as outlined
in Algorithm 1.
A subgradient gy ∈ ∂F (y) at y is given by the gradient of I(y; x∗ ) for the minimizing x∗ ∈
arg minx∈X I(y; x), i.e., gy = ∇y I(y; x∗ ). Hence, we must be able to compute x∗ for any y. We
also obtain a duality gap: for any x0 , y 0 we have
min I(y 0 ; x) ≤ max min I(y; x) ≤ max I(y; x0 ).
x∈X

y∈Y x∈X

y∈Y

(9)

This means we can estimate the optimal value I ∗ and use it in Polyak’s stepsize rule for the
subgradient method Polyak [1987].
But I(y; x) is not convex in x, and not even quasiconvex. For example, standard methods
√
[Wainwright & Chiang, 2004, Chapter 12] imply that f (x1 , x2 , x3 ) = 1 − x1 x2 − x3 is not quasiconvex on R3+ . Moreover, the above-mentioned signomial optimization techniques do not apply for
an exact solution either. So, it is not immediately clear that we can solve the inner optimization
problem.
The key insight we will be using is that I(y; x) has a different beneficial property: while not
convex, I(y; x) as a function of x is continuous submodular.
Lemma 3.1. Suppose we have n ≥ 1 differentiable functions
fi : R → R+ , for i = 1, . . . , n, either
Q
all nonincreasing or all nondecreasing. Then, f (x) = ni=1 fi (xi ) is a continuous supermodular
function from Rn to R+ .
6

Algorithm 1 Subgradient Ascent
Input: suboptimality tolerance ε > 0, initial feasible budget y (0) ∈ Y
Output: ε-optimal budget y for Problem (8)
repeat
x(k) ← arg minx∈X I(y (k) ; x)
g (k) ← ∇y I(y (k) ; x(k) )
L(k) ← I(y (k) ; x(k) )
U (k) ← maxy∈Y I(y; x(k) )
γ (k) ← (U (k) − L(k) )/kg (k) k22
y (k+1) ← projY (y (k) + γ (k) g (k) )
k ←k+1
until U (k) − L(k) ≤ ε
Proof. For n = 1, the resulting function is modular and therefore supermodular. In the case n ≥ 2,
we simply need to compute derivatives. The mixed derivatives are
Y
∂f
= fi0 (xi )fj0 (xj ) ·
fk (xk ).
∂xi ∂xj

(10)

k6=i,j

By monotonicity, fi0 and fj0 have the same sign, so their product is nonnegative, and since each fk
is nonnegative, the entire expression is nonnegative. Hence, f (x) is continuous supermodular by
Theorem 3.2 of [Topkis, 1978].
Corollary 3.1. The influence function I(y; x) defined in Section 2 is continuous submodular in x
over the nonnegative orthant, for each y ≥ 0.
Proof. Since submodularity is preserved under summation, it suffices to show that each function
It (y) is continuous submodular. By Lemma 3.1, since fs (z) = z y(s) is nonnegative and monotone
Q
y(s)
nondecreasing for y(s) ≥ 0, the product (s,t)∈E xst is continuous supermodular in x. Flipping
the sign and adding a constant term yields It (y), which is hence continuous submodular.
Conjecture 3.1. Strong duality holds, i.e.
max min I(y; x) = min max I(y; x).
y∈Y x∈X

x∈X y∈Y

(11)

If strong duality holds, then the duality gap maxy∈Y I(y; x∗ ) − minx∈X I(y ∗ ; x) in Equation (9)
is zero at optimality. If I(y; x) were quasiconvex in x, strong duality would hold by Sion’s min-max
theorem, but this is not the case. In practice, we observe that the duality gap always converges to
zero.
Bach [2015] demonstrates how to minimize a continuous submodular function H(x) subject to
box constraints x ∈ Box(l, u), up to an arbitrary suboptimality gap ε > 0. The constraint set X in
our Robust Budget Allocation problem, however, has box constraints with an additional constraint
R(x) ≤ B. This case is not addressed in any previous work. Fortunately, for a large class of
functions R, there is still an efficient algorithm for continuous submodular minimization, which we
present in the next section.

7

3.1

Constrained Continuous Submodular Function Minimization

We next address an algorithm for minimizing a monotone continuous submodular function H(x)
subject to box constraints x ∈ Box(l, u) and a constraint R(x) ≤ B:
minimize H(x)
s.t.
R(x) ≤ B
x ∈ Box(l, u).

(12)

If H and R were convex, the constrained problem would be equivalent to solving, with the right
Lagrange multipler λ∗ ≥ 0:
minimize H(x) + λ∗ R(x)
(13)
s.t.
x ∈ Box(l, u).
Although H and R are not necessarily convex here, it turns out that a similar approach indeed
applies. The main idea of our approach bears similarity with [Nagano et al., 2011] for the set
function case, but our setting with continuous functions and various uncertainty sets is more general, and requires more argumentation. We outline our theoretical results here, and defer further
implementation details and proofs to the appendix.
Following Bach [2015], we discretize the problem; for a sufficiently fine discretization,Qwe will
achieve arbitraryQ
accuracy. Let A be an interpolation mapping that maps the discrete set ni=1 [ki ]
into Box(l, u) = ni=1 [li , ui ] via the componentwise interpolation functions Ai : [ki ] → [li , ui ]. We
say Ai is δ-fine if Ai (xi + 1) − Ai (xi ) ≤ δ for all xi ∈ {0, 1, . . . , ki − 2}, and we say the full
interpolation function A is δ-fine if eachQAi is δ-fine.
Q
This mapping yields functions H δ : ni=1 [ki ] → R and Rδ : ni=1 [ki ] → R via H δ (x) = H(A(x))
and Rδ (x) = R(A(x)). H δ is lattice submodular (on the integer lattice). This construction leads
to a reduction of Problem (12) to a submodular minimization problem over the integer lattice:
δ
minimize H δ (x)
Qn+ λR (x)
s.t.
x ∈ i=1 [ki ].

(14)

Ideally, there should then exist a λ such that the associated minimizer x(λ) yields a close to optimal
solution for the constrained problem. Theorem 3.1 below states that this is indeed the case.
Moreover, a second benefit of submodularity is that we can find the entire solution path for
Problem (14) by solving a single optimization problem.
Lemma 3.2. Suppose H is continuous
submodular, and suppose the regularizer R is strictly inP
creasing and separable: R(x) = ni=1 Ri (xi ). Then we can recover a minimizer x(λ) for the induced
discrete Problem (14) for any λ ∈ R by solving a single convex optimization problem.
The problem in question arises from a relaxation h↓ that extends H δ in each coordinate i to
a function on distributions over the domain [ki ]. These distributions are represented via their
inverse cumulative distribution functions ρi , which take the coordinate xi as input, and output the
probability of exceeding xi . The function h↓ is an analogue of the Lovász extension of set functions
to continuous submodular functions [Bach, 2015], it is convex and coincides with H δ on lattice
points.
Formally, this resulting single optimization problem is:
P P −1
minimize h↓ (ρ) + ni=1 kjii=1
aixi (ρi (xi ))
Qn
(15)
ki −1
s.t.
ρ ∈ i=1 R↓
8

where Rk↓ refers to the set of ordered vectors z ∈ Rk that satisfy z1 ≥ z2 ≥ · · · ≥ zk , the notation
ρi (xi ) denotes the xi -th coordinate of the vector ρi , and the aixi are strictly convex functions given
by
1
aixi (t) = t2 · [Riδ (xi ) − Riδ (xi − 1)].
(16)
2
Problem (15) can be solved by Frank-Wolfe methods [Frank & Wolfe, 1956; Dunn & Harshbarger,
1978; Lacoste-Julien, 2016; Jaggi, 2013]. This is because the greedy algorithm for computing
subgradients of the Lovász extension can be generalized, and yields a linear optimization oracle for
the dual of Problem (15). We detail the relationship between Problems (14) and (15), as well as
how to implement the Frank-Wolfe methods, in Appendix C.
Let ρ∗ be the optimal solution for Problem (15). For any λ, we obtain a rounded solution x(λ)
for Problem (14) by thresholding: we set x(λ)i = max{j | 1 ≤ j ≤ ki − 1, ρ∗i (j) ≥ λ}, or zero if
ρ∗i (j) < λ for all j. Each x(λ0 ) is the optimal solution for Problem (14) with λ = λ0 . We use the
largest parameterized solution x(λ) that is still feasible, i.e. the solution x(λ∗ ) where λ∗ solves
min H δ (x(λ))
s.t. λ ≥ 0
Rδ (x(λ)) ≤ B.

(17)

This λ∗ can be found efficiently via binary search or a linear scan.
Theorem 3.1. Let H be continuous submodular and monotone decreasing, with `∞ -Lipschitz constant G, and let R be strictly increasing and separable. Assume all entries ρ∗i (j) of the optimal
solution ρ∗ of Problem (15) are distinct. Let x0 = A(x(λ∗ )) be the thresholding corresponding to the
optimal solution λ∗ of Problem (17), mapped back into the original continuous domain X . Then x0
is feasible for the continuous Problem (12), and is a 2Gδ-approximate solution:
H(x0 ) ≤ 2Gδ +

min

H(x).

x∈Box(l,u), R(x)≤B

Theorem 3.1 implies an algorithm for solving Problem (12) to ε-optimality: (1) set δ = ε/G,
(2) compute ρ∗ which solves Problem (15), (3) find the optimal thresholding of ρ∗ by determining
the smallest λ∗ for which Rδ (x(λ∗ )) ≤ B, and (4) map x(λ∗ ) back into continuous space via the
interpolation mapping A.
Optimality Bounds.
the discretized mesh

Theorem 3.1 is proved by comparing x0 and x∗ to the optimal solution on
x∗d ∈

argmin
x∈

Qn

i=1 [ki ]:R

H δ (x).

δ (x)≤B

Beyond the theoretical guarantee of Theorem 3.1, for any problem instance and candidate solution
x0 , we can compute a bound on the gap between H(x0 ) and H δ (x∗d ). The following two bounds are
proved in the appendix:
1. We can generate a discrete point x(λ+ ) satisfying
H(x0 ) ≤ [H(x0 ) − H δ (x(λ+ ))] + H δ (x∗d ).
2. The Lagrangian yields the bound
H(x0 ) ≤ λ∗ (B − R(x0 )) + H δ (x∗d ).
9

Improvements. The requirement in Theorem 3.1 that the elements of ρ∗ be distinct may seem
somewhat restrictive, but as long as ρ∗ has distinct elements in the neighborhood of our particular
λ∗ , this bound still holds. We see in Section 4.1.1 that in practice, ρ∗ almost always has distinct
elements in the regime we care about, and the bounds of Remark 3.1 are very good.
If H is DR-submodular and R is affine in each coordinate, then Problem (14) can be represented
more compactly via the reduction of Ene & Nguyen [2016], and hence problem (12) can be solved
more efficiently. In particular, the influence function I(y; x) is DR-submodular in x when for each
s, y(s) = 0 or y(s) ≥ 1.

3.2

Application to Robust Budget Allocation

The above algorithm directly applies to Robust Allocation with the uncertainty
sets in Section 2.2.
P
Q
The ellipsoidal uncertainty set X corresponds to the constraint that (s,t)∈E Rst (xst ) ≤ γ with
−2
Rst (x) = (xst − x̂st )2 σst
, and x ∈ Box(0, 1). By the monotonicity of I(x, y), there is never incentive
to reduce any xst below x̂st , so we can replace Box(0, 1) with Box(x̂, 1). On this interval, each Rst
is strictly increasing, and Theorem 3.1 applies.
For D-norm sets, we have Rst (xst ) = (xst − x̂st )/(ust − x̂st ). Since each Rst is monotone,
Theorem 3.1 applies.
Runtime and Alternatives. Since the core algorithm is Frank-Wolfe, it is straightforward to
show that Problem (15) can be solved to ε-suboptimality in time O(ε−1 n2 δ −3 α−1 |T |2 log nδ −1 ),
where α is the minimum derivative of the functions Ri . If ρ∗ has distinct elements separated by η,
then choosing ε = η 2 αδ/8 results in an exact solution to (14) in time O(η −2 n2 δ −4 α−2 |T |2 log nδ −1 ).
Noting that H δ + λRδ is submodular for all λ, one could instead perform binary search over
λ, each time converting the objective into a submodular set function via Birkhoff’s theorem and
solving submodular minimization e.g. via one of the recent fast methods [Chakrabarty et al., 2017;
Lee et al., 2015]. However, we are not aware of a practical implementation of the algorithm in [Lee
et al., 2015]. The algorithm in [Chakrabarty et al., 2017] yields a solution in expectation. This
approach also requires care in the precision of the search over λ, whereas our approach searches
directly over the O(nδ −1 ) elements of ρ∗ .

4

Experiments

We evaluate our Robust Budget Allocation algorithm on both synthetic test data and a real-world
bidding dataset from Yahoo! Webscope yah to demonstrate that our method yields real improvements. For all experiments, we used Algorithm 1 as the outer loop. For the inner submodular
minimization step, we implemented the pairwise Frank-Wolfe algorithm
of Lacoste-Julien & Jaggi
P
S
[2015]. In all cases, the feasible set of budgets Y is {y ∈ R+ : s∈S y(s) ≤ C} where the specific
budget C depends on the experiment. Our code is available at git.io/vHXkO.

4.1

Synthetic

On the synthetic data, we probe two questions: (1) how often does the distinctness condition of
Theorem 3.1 hold, so that we are guaranteed an optimal solution; and (2) what is the gain of using
a robust versus non-robust solution in an adversarial setting? For both settings, we set |S| = 6 and

10

D-norm, C = 0.4

0.028

Ellipsoidal, C = 0.4

0.01

0.005

0.014

0

0
0

0.026

50
D-norm, C = 4

100

0

50
Ellipsoidal, C = 4

100

0

50

100

0.01

0.013

0.005

0

0
0

50

100

Figure 1: Visualization of the sorted values of ρ∗i (j) (blue dots) with comparison to the particular Lagrange multiplier λ∗ (orange line). In most regimes there are no duplicate values, so that
Theorem 3.1 applies. The theorem only needs distinctness at λ∗ .
|T | = 2 and discretize with δ = 0.001. We generated true probabilties pst , created Beta posteriors,
and built both Ellipsoidal uncertainty sets X Q (γ) and D-norm sets X D (γ).
4.1.1

Optimality

Theorem 3.1 and Remark 3.1 demand that the values ρ∗i (j) be distinct at our chosen Lagrange
multiplier λ∗ and, under this condition, guarantee optimality. We illustrate this in four examples:
for Ellipsoidal or a D-norm uncertainty set, and a total influence budget C ∈ {0.4, 4}. Figure 3
shows all elements of ρ∗ in sorted order, as well as a horizontal line indicating our Lagrange
multiplier λ∗ which serves as a threshold. Despite some plateaus, the entries ρ∗i (j) are distinct
in most regimes, in particular around λ∗ , the regime that is needed for our results. Moreover, in
practice (on the Yahoo data) we observe later in Figure 3 that both solution-dependent bounds
from Remark 3.1 are very good, and all solutions are optimal within a very small gap.
4.1.2

Robustness and Quality

Next, we probe the effect of a robust versus non-robust solution for different uncertainty sets and
budgets γ of the adversary. We compare our robust solution with using a point estimate for x,
11

D-norm, C = 0.400

0.3

Ellipsoidal, C = 0.400

0.3

0.2

0.2

0.1

0.1

0

0
0

5
10
D-norm, C = 3.740

15

1.5

1.5

1

1

0.5

0.5

0

0

400
Ellipsoidal, C = 3.740

800

0

400

800

0
0

5

10

15

Figure 2: Comparison of worst-case expected influences for D-norm uncertainty sets X D (γ) (left)
and ellipsoidal uncertainty sets X Q (γ) (right), for different total budget bounds C. For any particular adversary budget γ, we compare minx∈X (γ) I(y; x) for each candidate allocation y.
i.e., ynom ∈ argmaxy∈Y I(y; x̂), treating estimates as ground truth, and the stochastic solution
yexpect ∈ argmaxy∈Y E[I(y; X)] as per Section 2.1. These two optimization problems were solved
via standard first-order methods using TFOCS Becker et al. [2011].
Figure 2 demonstrates that indeed, the alternative budgets are sensitive to the adversary and
the robustly-chosen budget yrobust performs better, even in cases where the other budgets achieve
zero influence. When the total budget C is large, yexpect performs nearly as well as yrobust , but
when resources are scarce (C is small) and the actual choice seems to matter more, yrobust performs
far better.

4.2

Yahoo! data

To evaluate our method on real-world data, we formulate a Budget Allocation instance on advertiser
bidding data from Yahoo! Webscope [yah]. This dataset logs bids on 1000 different phrases by
advertising accounts. We map the phrases to channels S and the accounts to customers T , with an
edge between s and t if a corresponding bid was made. For each pair (s, t), we draw the associated
transmission probability pst uniformly from [0, 0.4]. We bias these towards zero because we expect
people not to be easily influenced by advertising in the real world. We then generate an estimate
12

Figure 3: Convergence properties of our algorithm on real data. In the first plot, ‘p’ and ‘d’ refer to
primal and dual values, with dual gap shown on the second plot. The third plot demonstrates that
the problem-dependent suboptimality bounds of Remark 3.1 (x for x(λ+ ) and L for Lagrangian)
are very small (good) for all inner iterations of this run.
p̂st and build up a posterior by generating nst samples from Ber(pst ), where nst is the number of
bids between s and t in the dataset.
This transformation yields a bipartite graph with |S| = 1000, |T | = 10475, and more than
50,000 edges that we use for Budget Allocation. In our experiments, the typical gap between the
naive ynom and robust yrobust was 100-500 expected influenced people. We plot convergence of the
outer loop in Figure 3, where we observe fast convergence of both primal influence value and the
dual bound.

4.3

Comparison to first-order methods

Given the success of first-order methods on nonconvex problems in practice, it is natural to compare
these to our method for finding the worst-case vector x. On one of our Yahoo problem instances with
D-norm uncertainty set, we compared our submodular minimization scheme to Frank-Wolfe with
fixed stepsize as in [Lacoste-Julien, 2016], implementing the linear oracle using MOSEK [MOSEK
ApS, 2015]. Interestingly, from various initializations, Frank-Wolfe finds an optimal solution, as
verified by comparing to the guaranteed solution of our algorithm. Note that, due to non-convexity,
there are no formal guarantees for Frank-Wolfe to be optimal here, motivating the question of global
convergence properties of Frank-Wolfe in the presence of submodularity.
It is important to note that there are many cases where first-order methods are inefficient or
do not apply to our setup. These methods require either a projection oracle (PO) onto or linear
optimization oracle (LO) over the feasible set X defined by `, u and R(x). The D-norm set admits
a LO via linear programming, but we are not aware of any efficient LO for Ellipsoidal uncertainty,
nor PO for either set, that does not require quadratic programming. Even more, our algorithm
applies for nonconvex functions R(x) which induce nonconvex feasible sets X . Such nonconvex sets
may not even admit a unique projection, while our algorithm achieves provable solutions.

13

10500

9500

8500

7500
0

40

80

Figure 4: Convergence properties of Frank-Wolfe (FW), versus the optimal value attained with our
scheme (SFM).

5

Conclusion

We address the issue of uncertain parameters (or, model mis-specification) in Budget Allocation or
Bipartite Influence Maximization [Alon et al., 2012] from a robust optimization perspective. The
resulting Robust Budget Allocation is a nonconvex-concave saddle point problem. Although the
inner optimization problem is nonconvex, we show how continuous submodularity can be leveraged
to solve the problem to arbitrary accuracy ε, as can be verified with the proposed bounds on the
duality gap. In particular, our approach extends continuous submodular minimization methods
[Bach, 2015] to more general constraint sets, introducing a mechanism to solve a new class of constrained nonconvex optimization problems. We confirm on synthetic and real data that our method
finds high-quality solutions that are robust to parameters varying arbitrarily in an uncertainty set,
and scales up to graphs with over 50,000 edges.
There are many compelling directions for further study. The uncertainty sets we use are standard in the robust optimization literature, but have not been applied to e.g. Robust Influence
Maximization; it would be interesting to generalize our ideas to general graphs. Finally, despite
the inherent nonconvexity of our problem, first-order methods are often able to find a globally optimal solution. Explaining this phenomenon requires further study of the geometry of constrained
monotone submodular minimization.

Acknowledgements
We thank the anonymous reviewers for their helpful suggestions. We also thank MIT Supercloud
and the Lincoln Laboratory Supercomputing Center for providing computational resources. This
research was conducted with Government support under and awarded by DoD, Air Force Office of
Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32
CFR 168a, and also supported by NSF CAREER award 1553284.

14

References
Yahoo! Webscope dataset ydata-ysm-advertiser-bids-v1 0. URL http://research.yahoo.com/
Academic_Relations.
Adamczyk, Marek, Sviridenko, Maxim, and Ward, Justin. Submodular Stochastic Probing on
Matroids. Mathematics of Operations Research, 41(3):1022–1038, 2016.
Alon, Noga, Gamzu, Iftah, and Tennenholtz, Moshe. Optimizing Budget Allocation Among Channels and Influencers. In WWW. 2012.
Atamtürk, Alper and Narayanan, Vishnu. Polymatroids and mean-risk minimization in discrete
optimization. Operations Research Letters, 36(5):618–622, 2008.
Bach, Francis. Submodular Functions: From Discrete to Continous Domains. arXiv:1511.00394,
2015.
Balkanski, Eric, Rubinstein, Aviad, and Singer, Yaron. The power of optimization from samples.
In NIPS, 2016.
Balkanski, Eric, Rubinstein, Aviad, and Singer, Yaron. The limitations of optimization from samples. In STOC, 2017.
Becker, Stephen R., Candès, Emmanuel J., and Grant, Michael C. Templates for convex cone
problems with applications to sparse signal recovery. Mathematical programming computation, 3
(3):165–218, 2011.
Ben-Tal, Aharon and Nemirovski, Arkadi. Robust solutions of Linear Programming problems
contaminated with uncertain data. Mathematical Programming, 88(3):411–424, 2000.
Ben-Tal, Aharon, El Ghaoui, Laurent, and Nemirovski, Arkadi. Robust Optimization. Princeton
University Press, 2009.
Bertsimas, Dimitris and Sim, Melvyn. Robust discrete optimization and network flows. Mathematical programming, 98(1):49–71, 2003.
Bertsimas, Dimitris, Brown, David B., and Caramanis, Constantine. Theory and Applications of
Robust Optimization. SIAM Review, 53(3):464–501, 2011.
Best, Michael J. and Chakravarti, Nilotpal. Active set algorithms for isotonic regression; A unifying
framework. Mathematical Programming, 47(1-3):425–439, 1990.
Bian, Andrew An, Mirzasoleiman, Baharan, Buhmann, Joachim M., and Krause, Andreas. Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains. In AISTATS, 2017.
Birkhoff, Garrett. Rings of sets. Duke Mathematical Journal, 3(3):443–454, 1937.
Borgs, Christian, Brautbar, Michael, Chayes, Jennifer, and Lucier, Brendan. Maximizing Social
Influence in Nearly Optimal Time. In SODA, 2014.

15

Boyd, Stephen, Kim, Seung-Jean, Vandenberghe, Lieven, and Hassibi, Arash. A tutorial on geometric programming. Optimization and engineering, 8(1):67–127, 2007.
Chakrabarty, Deeparnab, Lee, Yin Tat, Sidford, Aaron, and Wong, Sam Chiu-wai. Subquadratic
submodular function minimization. In STOC, 2017.
Chandrasekaran, Venkat and Shah, Parikshit. Relative Entropy Relaxations for Signomial Optimization. SIAM Journal on Optimization, 26(2):1147–1173, 2016.
Chen, Wei, Wang, Yajun, and Yang, Siyu. Efficient influence maximization in social networks. In
KDD, 2009.
Chen, Wei, Wang, Chi, and Wang, Yajun. Scalable Influence Maximization for Prevalent Viral
Marketing in Large-scale Social Networks. In KDD, 2010.
Chen, Wei, Lin, Tian, Tan, Zihan, Zhao, Mingfei, and Zhou, Xuren. Robust influence maximization.
In KDD. 2016.
Chiang, Mung. Geometric Programming for Communication Systems. Commun. Inf. Theory, 2
(1/2):1–154, 2005.
Deshpande, Amol, Hellerstein, Lisa, and Kletenik, Devorah. Approximation Algorithms for
Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and MinKnapsack. ACM Trans. Algorithms, 12(3):42:1–42:28, 2016.
Domingos, Pedro and Richardson, Matt. Mining the network value of customers. In KDD, 2001.
Du, Nan, Song, Le, Gomez Rodriguez, Manuel, and Zha, Hongyuan. Scalable influence estimation
in continuous-time diffusion networks. In NIPS. 2013.
Du, Nan, Liang, Yingyu, Balcan, Maria-Florina, and Song, Le. Influence function learning in
information diffusion networks. In ICML, 2014.
Dunn, Joseph C. and Harshbarger, S. Conditional gradient algorithms with open loop step size
rules. Journal of Mathematical Analysis and Applications, 62(2):432–444, 1978.
Ecker, Joseph. Geometric Programming: Methods, Computations and Applications. SIAM Review,
22(3):338–362, 1980.
Ene, Alina and Nguyen, Huy L. A Reduction for Optimizing Lattice Submodular Functions with
Diminishing Returns. arXiv:1606.08362, 2016.
Frank, Marguerite and Wolfe, Philip. An algorithm for quadratic programming. Naval Research
Logistics Quarterly, 3(1-2):95–110, 1956.
Goel, Gagan, Karande, Chinmay, Tripathi, Pushkar, and Wang, Lei. Approximability of combinatorial problems with multi-agent submodular cost functions. In FOCS, 2009.
Goemans, Michel and Vondrák, Jan. Stochastic Covering and Adaptivity. In LATIN 2006: Theoretical Informatics. Springer Berlin Heidelberg, 2006.

16

Golovin, Daniel and Krause, Andreas. Adaptive Submodularity: Theory and Applications in Active
Learning and Stochastic Optimization. Journal of Artificial Intelligence, 42:427–486, 2011.
Gomez Rodriguez, Manuel and Schölkopf, Bernhard. Influence maximization in continuous time
diffusion networks. In ICML, 2012.
Gomez Rodriguez, Manuel, Leskovec, Jure, and Krause, Andreas. Inferring networks of diffusion
and influence. In KDD, 2010.
Gottschalk, Corinna and Peis, Britta. Submodular function maximization on the bounded integer
lattice. In Approximation and Online Algorithms: 13th International Workshop (WAOA), 2015.
Hassidim, Avinatan and Singer, Yaron. Submodular optimization under noise. arXiv preprint
arXiv:1601.03095, 2016.
Hatano, Daisuke, Fukunaga, Takuro, Maehara, Takanori, and Kawarabayashi, Ken-ichi. Lagrangian
Decomposition Algorithm for Allocating Marketing Channels. In AAAI, 2015.
He, Xinran and Kempe, David. Robust influence maximization. In KDD. 2016.
Iwata, Satoru and Nagano, Kiyohito. Submodular function minimization under covering constraints. In FOCS, 2009.
Jaggi, Martin. Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. In ICML,
2013.
Kempe, David, Kleinberg, Jon, and Tardos, Éva. Maximizing the Spread of Influence Through a
Social Network. In KDD, 2003.
Khachaturov, Vladimir R., Khachaturov, Roman V., and Khachaturov, Ruben V. Supermodular
programming on finite lattices. Computational Mathematics and Mathematical Physics, 52(6):
855–878, 2012.
Kolmogorov, Vladimir and Shioura, Akiyoshi. New algorithms for convex cost tension problem
with application to computer vision. Discrete Optimization, 6:378–393, 2009.
Krause, Andreas, McMahan, H Brendan, Guestrin, Carlos, and Gupta, Anupam. Robust submodular observation selection. Journal of Machine Learning Research, 9(Dec):2761–2801, 2008.
Lacoste-Julien, Simon.
arXiv:1607.00345, 2016.

Convergence Rate of Frank-Wolfe for Non-Convex Objectives.

Lacoste-Julien, Simon and Jaggi, Martin. On the global linear convergence of Frank-Wolfe optimization variants. In NIPS, 2015.
Lee, Yin Tat, Sidford, Aaron, and Wong, Sam Chiu-wai. A faster cutting plane method and its
implications for combinatorial and convex optimization. In FOCS, 2015.
Lowalekar, Meghna, Varakantham, Pradeep, and Kumar, Akshat. Robust Influence Maximization:
(Extended Abstract). In AAMAS, 2016.

17

Maehara, Takanori. Risk averse submodular utility maximization. Operations Research Letters, 43
(5):526–529, 2015.
Maehara, Takanori, Yabe, Akihiro, and Kawarabayashi, Ken-ichi. Budget Allocation Problem with
Multiple Advertisers: A Game Theoretic View. In ICML, 2015.
MOSEK ApS. MOSEK MATLAB Toolbox 8.0.0.57, 2015. URL http://docs.mosek.com/8.0/
toolbox/index.html.
Murota, Kazuo. Discrete convex analysis. SIAM, 2003.
Murota, Kazuo and Shioura, Akiyoshi. Exact bounds for steepest descent algorithms of l-convex
function minimization. Operations Research Letters, 42:361–366, 2014.
Nagano, Kiyohito, Kawahara, Yoshinobu, and Aihara, Kazuyuki. Size-constrained submodular
minimization through minimum norm base. In ICML, 2011.
Narasimhan, Harikrishna, Parkes, David C, and Singer, Yaron. Learnability of influence in networks. In NIPS. 2015.
Netrapalli, Praneeth and Sanghavi, Sujay. Learning the graph of epidemic cascades. In SIGMETRICS. 2012.
Nikolova, Evdokia. Approximation algorithms for reliable stochastic combinatorial optimization.
In APPROX. 2010.
Orlin, James B., Schulz, Andreas, and Udwani, Rajan. Robust monotone submodular function
maximization. In IPCO, 2016.
Pascual, Luis D. and Ben-Israel, Adi. Constrained maximization of posynomials by geometric
programming. Journal of Optimization Theory and Applications, 5(2):73–80, 1970.
Polyak, Boris T. Introduction to Optimization. Number 04; QA402. 5, P6. 1987.
Rockafellar, R Tyrrell and Uryasev, Stanislav. Optimization of conditional value-at-risk. Journal
of risk, 2:21–42, 2000.
Rockafellar, R Tyrrell and Uryasev, Stanislav. Conditional value-at-risk for general loss distributions. Journal of banking & finance, 26(7):1443–1471, 2002.
Soma, Tasuku and Yoshida, Yuichi. A Generalization of Submodular Cover via the Diminishing
Return Property on the Integer Lattice. In NIPS, 2015.
Soma, Tasuku, Kakimura, Naonori, Inaba, Kazuhiro, and Kawarabayashi, Ken-ichi. Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm. In ICML, 2014.
Svitkina, Zoya and Fleischer, Lisa. Submodular approximation: Sampling-based algorithms and
lower bounds. SIAM Journal on Computing, 40(6):1715–1737, 2011.
Topkis, Donald M. Minimizing a submodular function on a lattice. Operations research, 26(2):
305–321, 1978.

18

Wainwright, Kevin and Chiang, Alpha.
McGraw-Hill Education, 2004.

Fundamental Methods of Mathematical Economics.

Zhang, Peng, Chen, Wei, Sun, Xiaoming, Wang, Yajun, and Zhang, Jialin. Minimizing seed set
selection with probabilistic coverage guarantee in a social network. In KDD, 2014.

A

Worst-Case Approximation Ratio versus True Worst-Case

Consider the function f (x; θ) defined on {0, 1} × {0, 1}, with values given by:
(
(
1
x=0
1 x=0
f (x; 0) =
f (x; 1) =
0.6 x = 1,
2 x = 1.

(18)

We wish to choose x to maximize f (x; θ) robustly with respect to adversarial choices of θ. If θ were
fixed, we could directly choose x∗θ to maximize f (x; θ). In particular, x∗0 = 0 and x∗1 = 1. Of course,
we want to deal with worst-case θ. One option is to maximize the worst-case approximation ratio:
max min
x

θ

f (x; θ)
.
f (x∗θ ; θ)

(19)

One can verify that the best x according to this criterion is x = 1, with worst-case approximation
ratio 0.6 and worst-case function value 0.6. In this paper, we optimize the worst-case of the actual
function value:
max min f (x; θ).
(20)
x

θ

This criterion will select x = 0, which has a worse worst-case approximation ratio of 0.5, but
actually guarantees a function value of 1, significantly better than the 0.6 achieved by the other
formulation of robustness.

B

DR-submodularity and L\ -convexity

A function is L\ -convex if it satisfies a discrete version of midpoint convexity, i.e. for all x, y it
holds that




x+y
x+y
f (x) + f (y) ≥ f
+f
.
(21)
2
2
Remark B.1. An L\ -convex function need not be DR-submodular, and vice-versa. Hence algorithms for optimizing one type may not apply for the other.
Proof. Consider f1 (x1 , x2 ) = −x21 − 2x1 x2 and f2 (x1 , x2 ) = x21 + x22 , both defined on {0, 1, 2} ×
{0, 1, 2}. The function f1 is DR-submodular but violates discrete midpoint convexity for the pair
of points (0, 0) and (2, 2), while f2 is L\ -convex but does not have diminishing returns in either
dimension.
Intuitively-speaking, L\ -convex functions look like discretizations of convex functions. The
continuous objective function I(x, y) we consider need not be convex, hence its discretization need
not be L\ -convex, and we cannot use those tools. However, in some regimes (namely if each
y(s) ∈ {0} ∪ [1, ∞)), it happens that I(x, y) is DR-submodular in x.
19

C

Constrained Continuous Submodular Function Minimization

Define Rn↓ to be the set of vectors ρ in Rn which are monotone nonincreasing, i.e. ρ(1) ≥ ρ(2) ≥
· · · ≥ ρ(n). As in the main text, define [k] = {0, 1, . . . , k − 1}. One
Qof the key results from Bach
[2015] is that an arbitrary submodular function H(x) defined on ni=1 [ki ] can be extended to a
particular convex function h↓ (ρ) so that
minimize h↓ (ρ)
minimize H(x)Q
Q
⇔
n
s.t.
x ∈ i=1 [ki ]
s.t.
ρ ∈ ni=1 R↓ki −1 .

(22)

Moreover, Theorem 4 from Bach [2015] states that, if aiyi are strictly convex functions for all
i = 1, . . . , n and each yi ∈ [ki ], then the two problems
P P
minimize H(x) + ni=1 xyii=1 a0iyi (λ)
Q
(23)
s.t.
x ∈ ni=1 [ki ].
and

P P
minimize h↓ (ρ) + ni=1 kxii−1
=1 aixi [ρi (xi )]
Qn
ki −1
s.t.
ρ ∈ i=1 R↓

(24)

are equivalent. In particular, one recovers a solution to Problem (23) for any λ just as alluded to
in Lemma 3.2: find ρ∗ which solves Problem (24) and, for each component i, choose xi to be the
maximal value for which ρ∗i (xi ) ≥ λ.

C.1

Proof of Lemma 3.2

Proof.
The discretized form of the regularizer Rδ is also separable and can be written Rδ (x) =
Pn
1 2
δ
δ
i=1 Ri (x). For each i = 1, . . . , n and each yi ∈ [ki ] with yi ≥ 1, define aiyi (t) = 2 t · [Ri (yi ) −
Riδ (yi − 1)], so that a0iyi (t) = t · [Riδ (yi ) − Riδ (yi − 1)]. Since we assumed R(x) is strictly increasing,
the coefficient of t2 in each aiyi (t) is strictly positive, so that each aiyi (t) is strictly convex. Then,


xi 

X
Riδ (yi ) − Riδ (yi − 1) 
λRiδ (xi ) = λ · Riδ (0) +
(25)
yi =1

= λRiδ (0) +

xi
X

a0iyi (λ),

(26)

yi =1

so that the discretized version of the minimization problem can be written as
P P
minimize H δ (x) + λRδ (0) + ni=1 xyii=1 a0iyi (λ)
Q
s.t.
x ∈ ni=1 [ki ].
Since the term Rδ (0) does not depend on the variable x, this minimization is equivalent to
P P
minimize H δ (x) + ni=1 xyii=1 a0iyi (λ)
Q
s.t.
x ∈ ni=1 [ki ].

(27)

(28)

This problem is in the precise form where we can apply the preceding equivalence result between
Problems (23) and (24), so we are done.
20

C.2

Proof of Theorem 3.1

Proof. The general idea of this proof is to first show that the integer-valued point x∗d which solves
x∗d ∈

H δ (x)

argmin
x∈

Qn

i=1 [ki ]:R

δ (x)≤B

is also nearly a minimizer of the continuous version of the problem, due to the fineness of the
discretization. Then, we show that the solutions traced out by x(λ) get very close to x∗d . These
two results are simply combined via the triangle inequality.
C.2.1

Continuous and Discrete Problems

We begin by proving that
H δ (x∗d ) ≤ Gδ +

min

H(x).

(29)

x∈X :R(x)≤B

Consider x∗ ∈ arg minx∈X :R(x)≤B H(x). If x∗ corresponds to an integral point in the discretized
coordinate.
domain, then H(x∗ ) = H δ (x∗d ) and we are done. Else, x∗ has at least one non-integral
Q
By rounding coordinatewise, we can construct a set X = {x1 , . . . , xm } ⊆ ni=1 [ki ] so that x∗ ∈
conv({A(x1 ), . . . , A(xm )}. By monotonicity, there must be some xi ∈ X with Rδ (xi ) ≤ B, i.e.
A(xi ) is feasible for the original continuous problem. By construction, since the discretization
given by A is δ-fine, we must have kx∗ − A(xi )k∞ ≤ δ. Applying the Lipschitz property of H and
the optimality of x∗ , we have
Gδ ≥ H(A(xi )) − H(x∗ ) = H δ (xi ) − H(x∗ ) ≥ H δ (x∗d ) − H(x∗ ),
from which (29) follows.
C.2.2

Discrete and Parameterized Discrete Problems

Define λ− and λ+ by
λ− ∈

H δ (x(λ))

argmin

and

λ≥0:Rδ (x(λ))≤B

λ+ ∈

H δ (x(λ)).

argmax
λ≥0:Rδ (x(λ))≥B

The next step in proving our suboptimality bound is to prove that
H δ (x(λ+ )) ≤ H δ (x∗d ) ≤ H δ (x(λ− )),
from which it will follow that
H δ (x(λ− )) ≤ Gδ + H δ (x∗d ).

21

(30)

We begin by stating the min-max inequality, i.e. weak duality:
n
o
δ
δ
δ
max
H
(x)
+
λ(R
(x)
−
B)
min
H
(x)
=
min
Q
Q
δ
λ≥0
x∈ n
x∈ n
i=1 [ki ]
i=1 [ki ]:R (x)≤B
n
o
δ
δ
≥ max Q
min
H
(x)
+
λ(R
(x)
−
B)
λ≥0 x∈ n
i=1 [ki ]
n
o
= max H δ (x(λ)) + λ(Rδ (x(λ)) − B)
λ≥0
n
o
≥
max
H δ (x(λ)) + λ(Rδ (x(λ)) − B)
λ≥0:Rδ (x(λ))≥B

≥

max

λ≥0:Rδ (x(λ))≥B

H δ (x(λ))

(31)
(32)
(33)
(34)
(35)

= H δ (x(λ+ )).

(36)

We can also bound the optimal value of H δ (x∗d ) from the other side:
H δ (x∗d ) =

x∈

Qn

min

δ
i=1 [ki ]:R (x)≤B

H δ (x) ≤

min

λ≥0:Rδ (x(λ))≤B

H δ (x) = H δ (x(λ− ))

(37)

Q
because the set of x(λ) parameterized by λ is a subset of the full set {x ∈ ni=1 [ki ] : Rδ (x) ≤ B}.
We have now bounded the optimal value of H δ (x∗d ) on either side by optimization problems
where we seek an optimal λ ≥ 0 for the parameterization x(λ):
H δ (x(λ+ )) ≤ H δ (x∗d ) ≤ H δ (x(λ− )).

(38)

Recall that x(λ) comes from thresholding the values of ρ∗ by λ, and that we assume that the
elements of ρ∗ are unique. Hence, as we increase λ, the components of x decrease by 1 each time.
Combining this with the strict monotonicity of R, we see that kx(λ+ ) − x(λ− )k∞ ≤ 1. By the
Lipschitz properties of H δ , it follows that H δ (x(λ+ )) − H δ (x(λ− )) ≤ Gδ. Since H δ (x∗d ) lies in
the interval between H δ (x(λ+ )) and H δ (x(λ− )), it follows that H δ (x∗d ) − H δ (x(λ− )) ≤ Gδ.

C.3

Proof of Remark 3.1

Define λ∗ = λ− as in the previous section, so that x0 = A(x(λ∗ ). The x(λ+ ) bound is a simple
consequence from the above result that
H δ (x(λ+ )) ≤ H δ (x∗d ) ≤ H δ (x(λ− )) = H(x0 ).
As for the Lagrangian bound, since x(λ∗ ) is a minimizer for the regularized function H δ (x) +
λ∗ (Rδ (x) − B), it follows that
H δ (x(λ∗ )) + λ∗ (Rδ (x(λ∗ )) − B) ≤ H δ (x∗d ) + λ∗ (Rδ (x∗d ) − B).

(39)

Rearranging, and observing that Rδ (x∗d ) ≤ B because x∗d is feasible, it holds that
H(x0 ) = H δ (x(λ∗ )) ≤ H δ (x∗d ) + λ∗ (Rδ (x∗d ) − Rδ (x(λ∗ ))) ≤ H δ (x∗d ) + λ∗ (B − R(x0 )).

(40)

One can also combine either of these bounds with the result from the proof of Theorem 3.1 that
H δ (x∗d ) ≤ Gδ + H(x∗ ) yielding e.g.
H(x0 ) ≤ Gδ + λ∗ (B − R(x0 )) + H δ (x∗d ).
22

C.4

Solving the Optimization Problem

Now that we have proven equivalence results between the constrained problem we want to solve
and the convex problem (24), we need to actually solve the convex problem. At the beginning of
Section 5.2 in Bach [2015], it is stated that this surrogate problem can optimized via the FrankWolfe method and its variants, but only the the version of Problem (24) without the extra functions
aixi is elaborated upon. Here we detail how Frank-Wolfe algorithms can be used to solve the more
general parametric regularized problem. Our aim is to spell out very clearly the applicability of
Frank-Wolfe to this problem, for the ease of future practitioners.
Bach [2015] notes that by duality, Problem (24) is equivalent to:
min

Q
ki −1
ρ∈ n
i=1 R↓

h↓ (ρ) − H(0) +

n kX
i −1
X

aixi [ρi (xi )] =

i=1 xi =1

max hρ, wi +

min

Q
ki −1 w∈B(H)
ρ∈ n
i=1 R↓




= max

min

w∈B(H) ρ∈Qn

k −1

i
i=1 R↓

n kX
i −1
X

aixi [ρi (xi )]

i=1 xi =1

hρ, wi +

n kX
i −1
X
i=1 xi =1



aixi [ρi (xi )]


:= max f (w).
w∈B(H)

Here, the base polytope B(H) happens to be the convex hull of all vectors w which could be output
by the greedy algorithm in Bach [2015].
It is the dual problem, where we maximize over w, which is amenable to Frank-Wolfe. For FrankWolfe methods, we need two oracles: an oracle which, given w, returns ∇f (w); and an oracle which,
given ∇f (w), produces a point s which solves the linear optimization problem maxs∈B(H) hs, ∇f (w)i.
Per Bach [2015], an optimizer of the linear problem can be computed directly from the greedy
algorithm. For the gradient oracle, recall that we can find a subgradient of g(x) = miny h(x, y)
at the point x0 by finding y(x0 ) which is optimal for the inner problem, and then computing
∇x h(x, y(x0 )). Moreover, if such y(x0 ) is the unique optimizer, then the resulting vector is indeed
the gradient of g(x) at x0 . Hence, in our case, it suffices to first find ρ(w) which solves the inner
problem, and then ∇f (w) is simply ρ(w) because the inner function is linear in w. Since each
function aixi is strictly convex, the minimizer ρ(w) is unique, confirming that we indeed get a
gradient of f , and that f is differentiable.
Of course, we still need to compute the minimizer ρ(w). For a given w, we want to solve
min
ρ∈

Qn

i=1

k −1

hρ, wi +

R↓i

n kX
i −1
X

aixi [ρi (xi )]

i=1 xi =1

There are no constraints coupling the vectors ρi , and the objective is similarly separable, so we can
independently solve n problems of the form
min hρ, wi +

ρ∈Rk−1
↓

k−1
X

aj (ρj ).

j=1

Recall that each function aiyi (t) takes the form

1 2
2 t riyi

23

for some riyi > 0. Let D = diag(r), the

(k − 1) × (k − 1) matrix with diagonal entries rj . Our problem can then be written as
k−1

min hρ, wi +

ρ∈Rk−1
↓

1X
1
rj ρ2j = min hρ, wi + hDρ, ρi
2
2
ρ∈Rk−1
↓
j=1

1
= min hD1/2 ρ, D−1/2 wi + hD1/2 ρ, D1/2 ρi.
k−1
2
ρ∈R↓
Completing the square, the above problem is equivalent to
min kD

ρ∈Rk−1
↓

1/2

ρ+D

−1/2

wk22

= min

ρ∈Rk−1
↓

= min

k−1
X

1/2

−1/2

(rj ρj + rj

wj )2

j=1
k−1
X

ρ∈Rk−1
↓
j=1

rj (ρj + rj−1 wj )2 .

This last expression is precisely the problem which is called weighted isotonic regression: we are
fitting ρ to diag(r−1 )w, with weights r, subject to a monotonicity constraint. Weighted isotonic
regression is solved efficiently via the Pool Adjacent Violators algorithm of Best & Chakravarti
[1990].

C.5

Runtime

Frank-Wolfe returns an ε-suboptimal solution in O(ε−1 D2 L) iterations, where D is the diameter of
the feasible region, and L is the Lipschitz constant for the gradient of the objective [Jaggi, 2013].
Our optimization problem is maxw∈B(H) f (w) as defined in the previous section. Each w ∈ B(H)
has O(nδ −1 ) coordinates of the form H δ (x + ei ) − H δ (x). Since H δ is an expected influence in
the range [0, T ], we can bound the magnitude of each coordinate of w by T and hence D2 by
O(nδ −1 T 2 ). If α is the minimum derivative of the functions Ri , then the smallest coefficient of the
functions aixi (t) is bounded below by αδ. Hence the objective is the conjugate of an αδ-strongly
convex function, and therefore has α−1 δ −1 -Lipschitz gradient. Combining these, we arrive at the
O(ε−1 nδ −2 α−1 T 2 ) iteration bound. The most expensive step in each iteration is computing the
subgradient, which requires sorting the O(nδ −1 ) elements of ρ in time O(nδ −1 log nδ −1 ). Hence the
total runtime of Frank-Wolfe is O(ε−1 n2 δ −3 α−1 T 2 log nδ −1 ).
As specified in the main text, relating an approximate solution of (15) to a solution of (14) is
nontrivial. Assume ρ∗ has distinct elements separated by η, and chose ε to be less than η 2 αδ/8. If
ρ is ε-suboptimal, then by αδ-strong convexity we must have kρ − ρ∗ k2 < η/2, and therefore kρ −
ρ∗ k∞ < η/2. Since the smallest consecutive gap between elements of ρ∗ is η, this implies that ρ and
ρ∗ have the same ordering, and therefore admit the same solution x after thresholding. Accounting
for this choice in ε, we have an exact solution to (14) in total runtime of O(η −2 n2 δ −4 α−2 T 2 log nδ −1 ).

24

D

Expectation and Variance of the Influence Function

We wish to study the influence I(X, y), its expectation and its variance as a function of y. By
definition, the influence function is given by


X
Y
y(s)
1 −
Xst  .
(41)
I(X, y) =
t∈T

(s,t)∈E

Before we prove the stated results, we will simplify the functions involved.
Maximizing I(X, y) is equivalent to minimizing the function
X Y
y(s)
Xst

(42)

t∈T (s,t)∈E

and vice-versa. The particular properties we are interested in, namely convexity and submodularity,
are preserved under sums. Moreover, expectation is linear and variances add, so for our purposes
we can focus on only one term of the above sum. After reindexing in terms of i = 1, . . . , n instead
of (s, t) ∈ E, we are left studying functions of the form
f (y) =

n
Y

Xiyi .

(43)

i=1

If f (y) is always convex (or supermodular), then I(X, y) is always concave (submodular) in y, and
similarly for their expectations and variances.
Expectation

By independence,
E[f (y)] =

n
Y

E[Xiyi ].

(44)

i=1

Suppose that each Xi ∼ Beta(αi , βi ), so that
Γ(αi + βi )Γ(αi + yi )
Γ(αi + βi + yi )
Γ(αi + βi )Γ(αi + yi )Γ(βi )
=
Γ(αi + βi + yi )Γ(βi )
B(αi + yi , βi )
=
.
B(αi , βi )

E[Xiyi ] =

Then,
E[f (y)] =

n
Y
B(αi + yi , βi )
i=1

B(αi , βi )

∝

n
Y

B(αi + yi , βi ),

(45)
(46)
(47)

(48)

i=1

where by ∝ we mean that the product of the denominators is a positive constant, dependent on
the problem data but independent of y.

25

Variance

The variance of f (y) can be written as
"
Var

n
Y

#
Xiyi

=E

" n
Y

i=1

#
Xi2yi

−E

i=1

=
=

#2
Xiyi

(49)

i=1

n
n
h
i Y
Y
2
E Xi2yi −
E [Xiyi ]
i=1

(50)

i=1

n
Y
B(αi + 2yi , βi )
i=1

D.1

" n
Y

B(αi , βi )

−


n 
Y
B(αi + yi , βi ) 2
i=1

B(αi , βi )

.

(51)

Gradient of Expected Influence

Recall the identity
∂
B(a, b) = B(a, b)(ψ(a) − ψ(a + b)),
(52)
∂a
where ψ is the digamma function. We can then compute each component of the gradient of E[f (y)]:
n
Y
Y
∂
∂
1
·
B(αj + yj , βj ) ·
(E[f (y)]) =
(B(αi + yi , βi ))
∂yi
B(αi , βi )
∂yi

=

i=1
n
Y
i=1

(53)

j6=i

Y
1
·
B(αj + yj , βj ) · B(αi + yi , βi ) · (ψ(αi + yi ) − ψ(αi + yi + βi ))
B(αi , βi )
j6=i

(54)
= E[f (y)] · (ψ(αi + yi ) − ψ(αi + yi + βi )).

D.2

(55)

Counterexample for Fact 2.1

p
We give a specific choice of parameters n, αi , βi and yi for which the resulting function Var(f (y))
is non-convex, non-concave, non-submodular and non-supermodular for various points y ∈ Rn+ . For
the p
case T = 1, the function 1−f (y) is a valid influence function, so we have a valid counterexample
for Var(I(X, y)).
Consider the case n = 2, with α1 = α2 = 1 and β1 = β2 = 1. This corresponds to the Budget
Allocation problem where we have two sources each with an edge to one customer, and we have
only our prior (i.e. no data)
p on either of the edge probabilities. Using equation (51), we can directly
compute the Hessian of Var(f (y)) at any point y, e.g. using Mathematica.
In particular, for
p
y1 = y2 = 1, the Hessian has a positive and a negative eigenvalue, so Var(f (y)) is neither
p convex
nor concave at this point. Also for y1 = y2 = 1, the off-diagonal element is negative, so Var(f (y))
is not supermodular over all of R2+ . However, for y1 = y2 = 3, the off-diagonal element is positive,
so our function is also not submodular.

26

