Robust Maximization of Non-Submodular Objectives

arXiv:1802.07073v2 [stat.ML] 14 Mar 2018

Ilija Bogunovic†
LIONS, EPFL
ilija.bogunovic@epfl.ch

Junyao Zhao†
LIONS, EPFL
zhaoju@student.ethz.ch

Abstract

Volkan Cevher
LIONS, EPFL
volkan.cevher@epfl.ch

nality constraint k, i.e.
max

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number
of elements τ is deleted from the returned
set. The focus of this work is on the worstcase adversarial setting. While there exist
constant-factor guarantees when the function
is submodular [1, 2], there are no guarantees
for non-submodular objectives. In this work,
we present a new algorithm ObliviousGreedy and prove the first constant-factor
approximation guarantees for a wider class
of non-submodular objectives. The obtained
theoretical bounds are the first constantfactor bounds that also hold in the linear
regime, i.e. when the number of deletions τ
is linear in k. Our bounds depend on established parameters such as the submodularity
ratio and some novel ones such as the inverse
curvature. We bound these parameters for
two important objectives including support
selection and variance reduction. Finally, we
numerically demonstrate the robust performance of Oblivious-Greedy for these two
objectives on various datasets.

1

Introduction

A wide variety of important problems in machine
learning can be formulated as the maximization of a
monotone 1 set function f : 2V → R+ under the cardi†

Equal contribution.
Non-negative and normalized (i.e. f (∅) = 0) f (·) is
monotone if for any sets X ⊆ Y ⊆ V it holds f (X) ≤ f (Y ).
1

Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Lanzarote, Spain. PMLR: Volume 84. Copyright 2018 by the
author(s).

S⊆V,|S|≤k

f (S),

(1)

where V = {v1 , · · · vn } is the ground set of items. However, in many applications, we might require robustness of the solution set, meaning that the objective
value should deteriorate as little as possible after a
subset of elements is deleted.
For example, an important problem in machine learning is feature selection, where the goal is to extract a
subset of features that are informative w.r.t. a given
task (e.g. classification). For some tasks, it is of great
importance to select features that exhibit robustness
against deletions. This is particularly important in
domains with non-stationary feature distributions or
with input sensor failures [3]. Another important example is the optimization of an unknown function from
point evaluations that require performing costly experiments. When the experiments can fail, protecting
against worst-case failures becomes important.
In this work, we consider the following robust variant
of Problem (1):
max

min

S⊆V,|S|≤k E⊆S,|E|≤τ

f (S \ E),

(2)

where2 τ is the size of subset E that is removed from
the solution set S. When the objective function exhibits submodularity, a natural notion of diminishing
returns3 , a constant factor approximation guarantee
can be obtained for the robust Problem 2 [1, 2]. However, in many applications such as the above mentioned feature selection problem, the objective function f (·) is not submodular and the obtained guarantees are not applicable.
Background and related work. When the objective function is submodular, the simple Greedy algorithm [4] achieves a (1 − 1/e)-multiplicative approximation guarantee for Problem 1. The constant factor
2

When τ = 0, Problem (2) reduces to Problem (1).
f (·) is submodular if for any sets X ⊆ Y ⊆ V and
any element e ∈ V \ Y , it holds that f (X ∪ {e}) − f (X) ≥
f (Y ∪ {e}) − f (Y ).
3

Robust Maximization of Non-Submodular Objectives

can be further improved by exploiting the properties of
the objective function, such as the closeness to being
modular captured by the notion of curvature [5, 6, 7].
In many cases, the Greedy algorithm performs well
empirically even when the objective function deviates
from being submodular. An important class of such
objectives are γ-weakly submodular functions. Simply
put, submodularity ratio γ is a quantity that characterizes how close the function is to being submodular. It was first introduced in [8], where it was shown
that for such functions the approximation ratio of
Greedy for Problem (1) degrades slowly as the submodularity ratio decreases i.e. as (1 − e−γ ). In [9],
the authors obtain the approximation guarantee of the
form α−1 (1 − e−γα ), that further depends on the curvature α.
When the objective is submodular, the Greedy algorithm can perform arbitrarily badly when applied to
Problem (2) [1, 2]. A submodular version of Problem (2) was first introduced in Krause et al. [10],
while the first efficient algorithm and constant factor guarantees
were obtained in Orlin et al. [1] for
√
τ = o( k). In Bogunovic et al. [2], the authors introduce the PRo-GREEDY algorithm that attains
the same 0.387-guarantee but it allows for greater robustness, i.e. the allowed number of removed elements
is τ = o(k). It is not clear how the obtained guarantees generalize for non-submodular functions. In the
submodular setting, the curvature-dependent constant
factor approximation is obtained in [11] that holds for
any number of removals.

Deletion robust submodular maximization in the
streaming setting has been considered in [18, 19, 20].
Other versions of robust submodular optimization
problems have also been studied. In [10], the goal
is to select a set of elements that is robust against
the worst possible objective from a given finite set of
monotone submodular functions. The same problem
with different types of constraints is considered in [21].
It was further studied in the domain of influence maximization [22, 23]. The robust version of the budget
allocation problem was considered in [24].In [25], the
authors study the problem of maximizing a monotone
submodular function under adversarial noise. We conclude this section by noting that very recently a couple
of different works have further studied robust submodular problems [26, 27, 28, 29].
Main contributions:
• We initiate the study of the robust optimization Problem (2) for a wider class of monotone non-submodular functions. We present a
new algorithm Oblivious-Greedy and prove the
first constant factor approximation guarantees for
Problem (2). When the function is submodular
and under mild conditions, we recover the approximation guarantees obtained in the previous
works [1, 2].
• In the non-submodular setting, we obtain the first
constant factor approximation guarantees for the
linear regime, i.e. when τ = ck for some c ∈ (0, 1).
• Our theoretical bounds are expressed in terms of
parameters that further characterize a set function. Some of them have been used in previous works, e.g. submodularity ratio, and some of
them are novel, such as the inverse curvature. We
prove some interesting relations between these parameters and obtain theoretical bounds for them
in two important applications: (i) support selection and (ii) variance reduction objective used in
batch Bayesian optimization. This allows us to
obtain the first robust guarantees for these two
important objectives.

One important class of non-submodular functions that
we consider in this work are those used for support
selection:
f (S) :=

max

x∈X ,supp(x)⊆S

l(x),

(3)

where l(·) is a continuous function, X is a convex set
and supp(x) = {i : xi 6= 0}. A popular way to solve
the problem of finding a k-sparse vector that maximizes l, i.e. x ∈ arg maxx∈X ,kxk0 ≤k l(x) is to maximize
the auxiliary set function in (3) subject to the cardinality constraint k. This setting and its variants have
been used in various applications, for example, sparse
approximation [8, 12], feature selection [13], sparse
recovery [14], sparse M-estimation [15] and column
subset selection problems [16]. An important result
from [17] states that if l(·) is (m, L)-(strongly concave,
smooth) then f (S) is weakly submodular with submodularity ratio γ ≥ m
L . Consequently, this result enlarges the number of problems where Greedy comes
with guarantees. In this work, we consider the robust
version of this problem, where the goal is to protect
against the worst-case adversarial deletions of features.

• Finally, we experimentally validate the robustness
of Oblivious-Greedy in several scenarios, and
demonstrate that it outperforms other robust and
non-robust algorithms.

2

Preliminaries

Set function ratios. In this work, we consider a normalized monotone set function f : 2V → R+ ; we proceed by defining several quantities that characterize
it. Some of the quantities were introduced and used

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

in various different works, while the novel ones that
we consider are inverse curvature, bipartite supermodularity ratio and (super/sub)additivity ratio.
Definition 1 (Submodularity [8] and Supermodularity ratio). The submodularity ratio of f (·) is the largest
scalar γ ∈ [0, 1] s.t.
P
i∈Ω f ({i}|S)
≥ γ, ∀ disjoint S, Ω ⊆ V.
(4)
f (Ω|S)
while the supermodularity ratio is the largest scalar γ̌ ∈
[0, 1] s.t.
P

f (Ω|S)
≥ γ̌,
i∈Ω f ({i}|S)

∀ disjoint S, Ω ⊆ V.

∀S, Ω ⊆ V, i ∈ S \ Ω,

(6)
while the inverse generalized curvature is the smallest
scalar α̌ ∈ [0, 1] s.t.
∀S, Ω ⊆ V, i ∈ S \ Ω.
(7)

The function f (·) is submodular (supermodular) iff
α̌ = 0 (α = 0). The function is modular iff α = α̌ = 0.
In general, α can be different from α̌.
Definition 3 (sub/superadditivity ratio). The subadditivity ratio of f (·) is the largest scalar ν ∈ [0, 1] such
that
P
i∈S f ({i})
≥ ν, ∀S ⊆ V.
(8)
f (S)
The superadditivity ratio is the largest scalar ν̌ ∈ [0, 1]
such that
f (S)
≥ ν̌,
i∈S f ({i})

P

∀S ⊆ V.

and ν̌ ≥ γ̌ ≥ 1 − α.

We also provide a more general definition of the bipartite subadditivity ratio used in [13].
Definition 4 (Bipartite subadditivity ratio). The bipartite subadditivity ratio of f (·) is the largest scalar
θ ∈ [0, 1] s.t.
f (A) + f (B)
≥ θ,
f (S)

∀S ⊆ V, A ∪ B = S, A ∩ B = ∅.
(10)

Remark 1. For any f (·), it holds that θ ≥ ν̌ν.

Definition 2 (Generalized curvature [6, 9] and inverse
generalized curvature). The generalized curvature of
f (·) is the smallest scalar α ∈ [0, 1] s.t.

f ({i}|S \ {i})
≥ 1 − α̌,
f ({i}|S \ {i} ∪ Ω)

ν ≥ γ ≥ 1 − α̌

(5)

The function f (·) is submodular (supermodular)
iff γ = 1 (γ̌ = 1).
Hence, the submodularity/supermodularity ratio measures to what extent
the function has submodular/supermodular properties. While f (·) is modular iff γ = γ̌ = 1, in general,
γ can be different from γ̌.

f ({i}|S \ {i} ∪ Ω)
≥ 1 − α,
f ({i}|S \ {i})

Proposition 1. For any f (·), the following relations
hold:

(9)

If the function is submodular (supermodular) then ν =
1 (ν̌ = 1).
The following proposition captures the relation between the above quantities.

Greedy guarantee. Different works [8, 9] have studied the performance of the Greedy algorithm [4] for
Problem 1 when the objective is γ-weakly submodular. In our analysis, we are going to make use of the
following important result from [8].
Lemma 1. For a monotone normalized set function
f : 2V → R+ , with submodularity ratio γ ∈ [0, 1] the
Greedy algorithm when run for l steps returns a set
Sl of size l such that


l
f (Sl ) ≥ 1 − e−γ k f (OPT(k,V ) ),
where OPT(k,V ) is used to denote the optimal set of
size k, i.e., OPT(k,V ) ∈ arg maxS⊆V,|S|≤k f (S).

3

Algorithm and its Guarantees

We present our Oblivious-Greedy algorithm in Algorithm 1. The algorithm requires a non-negative
monotone set function f : 2V → R+ , and the ground
set of items V . It constructs two sets S0 and S1 .
The first set S0 is constructed via oblivious selection,
i.e. ⌈βτ ⌉ items with the individually highest objective
values are selected. Here, β ∈ R+ is an input parameter, that together with τ , determines the size of S0
(|S0 | = ⌈βτ ⌉ ≤ k). We provide more information on
this parameter in the next section. The second set S1 ,
of size k − |S0 |, is obtained by running the Greedy
algorithm on the remaining items V \ S0 . Finally, the
algorithm outputs the set S = S0 ∪ S1 of size k that is
robust against the worst-case removal of τ elements.
Intuitively, the role of S0 is to ensure robustness, as
its elements are selected independently of each other
and have high marginal values, while S1 is obtained
greedily and it is near-optimal on the set V \ S0 .
Oblivious-Greedy is simpler than the submodular
algorithms PRo-GREEDY [2] and OSU [1]. Both
of these algorithms construct multiple sets (buckets)

Robust Maximization of Non-Submodular Objectives

Algorithm 1 Oblivious-Greedy algorithm
Require: Set V , k, τ , β ∈ R+ and ⌈βτ ⌉ ≤ k
Ensure: Set S ⊆ V such that |S| ≤ k
1: S0 , S1 ← ∅
2: for i ← 0 to ⌈βτ ⌉ do
3:
v ← arg maxv∈V \S0 f ({v})
4:
S0 ← S0 ∪ {v}
5: S1 ← Greedy(k − |S0 |, (V \ S0 ))
6: S ← S0 ∪ S1
7: return S
whose number and size depend on the input parameters k and τ . In contrast, Oblivious-Greedy always
constructs two sets, where the first set is obtained by
the fast Oblivious selection.
For Problem (1) and the weakly submodular objective, the Greedy algorithm achieves a constant factor approximation (Lemma 1), while Oblivious selection achieves (γ/k)-approximation [13]. For the harder
Problem (2), Greedy can fail arbitrarily badly [2].
Interestingly enough, the combination of these two algorithms reflected in Oblivious-Greedy leads to a
constant factor approximation for Problem (2).
3.1

θf (OPT(k−τ,V \ES∗ ) ) − (1 − e−

Intermediate results. Before stating our main result, we provide three lower bounds on f (S \ ES∗ ). For
the returned set S = S0 ∪S1 , we let E0 denote elements
removed from S0 , i.e., E0 := ES∗ ∩ S0 and similarly
E1 := ES∗ ∩ S1 . The first lemma is borrowed from [2],
and states that f (S\ES∗ ) is at least some constant fraction of the utility of the elements obtained greedily in
the second stage.
Lemma 2. For any f (·) (not necessarily submodular),
let µ ∈ [0, 1] be a constant such that f (E1 | (S \ES∗ )) =
µf (S1 ) holds. Then, f (S \ ES∗ ) ≥ (1 − µ)f (S1 ).
The next lemma generalizes the result obtained in [1,
2], and applies to any non-negative monotone set function with bipartite subadditivity ratio θ.
∗
As shown in [1], f (OPT(k−τ,V \ES∗ ) ) ≥ f (OPT \ EOPT
),
where OPT is the optimal solution to Problem (2).

k−|S0 |
k−τ

)−1 f (S1 ).

In other words, if f (S1 ) is small compared to the utility of the optimal solution, then f (S \ ES∗ ) is at least
a constant factor away from the optimal solution.
Next, we present our key lemma that further relates
f (S \ ES∗ ) to the utility of the set S1 with no deletions.

Lemma 4. Let β be a constant such that |S0 | = ⌈βτ ⌉
and |S0 | ≤ k, and let ν̌, α̌ ∈ [0, 1] be a superadditivity
ratio and generalized inverse curvature (Eq. (9) and
Eq. (7), respectively). Finally, let µ be a constant defined as in Lemma 2. Then,
f (S \ ES∗ ) ≥ (β − 1)ν̌(1 − α̌)µf (S1 ).
Proof. We have:
f (S \ ES∗ ) ≥ f (S0 \ E0 )
X
f ({ei })
≥ ν̌

(11)

ei ∈S0 \E0

|S0 \ E0 | X
ν̌
f ({ei })
≥
|E1 |

(12)

(β − 1)τ X
ν̌
f ({ei })
τ

(13)

ei ∈E1

Approximation guarantee

The quantity of interest in this section is the remaining utility after the adversarial removal of elements
f (S \ ES∗ ), where S is the set of size k returned by
Oblivious-Greedy, and ES∗ is the set of size τ chosen
by the adversary, i.e., ES∗ ∈ arg minE⊂S,|E|≤τ f (S \ E).
Let OPT(k−τ,V \ES∗ ) denote the optimal solution, of size
k − τ , when the ground set is V \ ES∗ . The goal in this
section is to compare f (S \ES∗ ) to f (OPT(k−τ,V \ES∗ ) ).4
All the omitted proofs from this section can be found
in the supplementary material.

4

Lemma 3. Let θ ∈ [0, 1] be a bipartite subadditivity
ratio defined in Eq. (10). Then f (S \ ES∗ ) is at least

≥

ei ∈E1

≥ (β − 1)ν̌(1 − α̌)
|E1 |

×


X 
(i−1)
(14)
f {ei }|(S \ ES∗ ) ∪ E1
i=1

= (β − 1)ν̌(1 − α̌)f (E1 |(S \ ES∗ ))
= (β − 1)ν̌(1 − α̌)µf (S1 ).

(15)
(16)

Eq. (11) follows by the superadditivity. Eq. (12)
follows from the way S0 is constructed, i.e. via
Oblivious selection that ensures f ({i}) ≥ f ({j}) for
every i ∈ S0 \ E0 and j ∈ E1 . Eq. (13) follows from
|S0 \ E0 | = ⌈βτ ⌉ − |E0 | ≥ βτ − τ = (β − 1)τ , and
|E1 | ≤ τ .
To prove Eq. (14), let E1 = {e1 , · · · e|E1 | }, and let
(i−1)

E1
⊆ E1 denote the set {e1 , · · · , ei−1 }. Also, let
(0)
E1 = ∅. Eq. (14) then follows from


(i−1)
f ({ei }) ≥ (1 − α̌)f {ei }|(S \ ES∗ ) ∪ E1
,
which in turns follows from (7) by setting S = {ei }
(i−1)
.
and Ω = (S \ ES∗ ) ∪ E1

∗
Finally, Eq.
 (15) follows from f (E1 |(S \ ES )) =
P
(i−1)
∗
(telescoping sum)
ei ∈E1 f {ei }|(S \ ES ) ∪ E1

and Eq. (16) follows from the definition of µ.

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

approximation guarantee

0.40
0.36
0.31
0.27
0.22
0.18
0.13
0.09
0.04
0.00
1.0

0.0

0.2

0.4

γ

0.6

0.8

1.0 0.0

0.2

0.4

0.6

0.8

θ

Figure 1: Approximation guarantee obtained in Remark 2. The green cross represents the approximation
guarantee when f is submodular (γ = θ = 1).
Main result. We obtain the main result by examining
the maximum of the obtained lower bounds in Lemma
2, 3 and 4. Note, that all three obtained lower bounds
depend on f (S1 ). In Lemma 3, we benefit from f (S1 )
being small while the opposite is true for Lemma 2
and 4 (both bounds are increasing in f (S1 )). By examining the latter two, we observe that in Lemma 2
we benefit from µ being small (i.e. the utility that we
lose due to E1 is small compared to the utility of the
whole set S1 ) while the opposite is true for Lemma 4.
By carefully balancing between these cases (see Appendix C for details) we arrive at our main result.
Theorem 1. Let f : 2V → R+ be a normalized, monotone set function with submodularity ratio γ, bipartite
subadditivity ratio θ, inverse curvature α̌ and superadditivity ratio ν̌, every parameter in [0, 1]. For a
given budget k and τ = ⌈ck⌉, for some c ∈ (0, 1), the
Oblivious-Greedy algorithm with β s.t. ⌈βτ ⌉ ≤ k
and β > 1, , returns a set S of size k such that when
k → ∞ we have


1−βc
θP 1 − e−γ 1−c

 f (OPT(k−τ,V \ES∗ ) ).
f (S \ ES∗ ) ≥
1−βc
1 + P 1 − e−γ 1−c
where P is used to denote

(β−1)ν̌(1−α̌)
1+(β−1)ν̌(1−α̌) .

Remark 2. Consider f (·) from Theorem
1 with ν̌ ∈
 
k
(0, 1] and α̌ ∈ [0, 1). When τ = o β and β ≥ log k
we have:


1 − e−γ
∗
+ o(1) f (OPT(k−τ,V \ES∗ ) ).
f (S \ ES ) ≥ θ
2 − e−γ
Interpretation. An open question from [2] is whether
a constant factor approximation guarantee is possible
in the linear regime, i.e. when the number of removals
is τ = ⌈ck⌉ for some constant c ∈ (0, 1) [2]. In Theorem 1 we obtain the first asymptotic constant factor
approximation in this regime.

Additionally, when f is submodular, all the parameters in the obtained bound are fixed (α̌ = 0 and
γ = θ = 1 due to submodularity) except the superadditivity ratio ν̌ which can take any value in [0, 1]. The
approximation factor improves for greater ν̌, i.e. the
closer the function is to being superadditive. On the
other hand, if f is supermodular then ν̌ = 1 while
α̌, θ, γ are in [0, 1], and the approximation factor improves for larger θ and γ, and smaller α̌.
From Remark 2, when f is submodular, ObliviousGreedy achieves an asymptotic approximation factor of at least 0.387. This matches the approximation guarantee obtained in [2, 1], while
 it allows for

a greater number of deletions τ = o logk k in com

√
parison to τ = o logk3 k and τ = o( k) obtained in
[2] and [1], respectively. Most importantly, our result
holds for a wider range of non-submodular functions.
In Figure 1 we show how the asymptotic approximation factor changes as a function of γ and θ.
We also obtain an alternative formulation of our main
result, which we present in the following corollary.
Corollary 1. Consider the setting from Theorem 1
(β−1)ν̌ν
. Then we have
and let P := 1+(β−1)ν̌(1−ν)


1−βc
θ2 P 1 − e−γ 1−c
 f (OPT(k−τ,V \ES∗ ) ).

f (S \ES∗ ) ≥
1−βc
1 + θP 1 − e−γ 1−c
Additionally,
  consider f (·) with ν̌, ν ∈ (0, 1]. When
τ = o βk and β ≥ log k, as k → ∞, we have that
f (S \ ES∗ ) is at least
 2

θ (1 − e−γ )
+
o(1)
f (OPT(k−τ,V \ES∗ ) ).
1 + θ(1 − e−γ )
The key observation is that the approximation factor depends on ν instead of inverse curvature α̌. The
asymptotic approximation ratio is slightly worse here
compared to Theorem 1. However, depending on the
considered application, it might be significantly harder
to provide bounds for the inverse curvature than bipartite subadditivty ratio, and hence in such cases, this
formulation might be more suitable.

4

Applications

In this section, we consider two important real-world
applications where deletion robust optimization is of
interest. We show that the parameters used in the
statement of our main theoretical result can be explicitly characterized, which implies that the obtained
guarantees are applicable.

Robust Maximization of Non-Submodular Objectives

4.1

Robust Support Selection

We first consider the recent results that connect submodularity with concavity [17, 13]. In order to obtain
bounds for robust support selection for general concave functions, we make use of the theoretical bounds
obtained for Oblivious-Greedy in Corollary 1.
Given a differentiable concave function l : X → R,
where X ⊆ Rd is a convex set, and k ≤ d, the support
selection problem is: maxkxk0 ≤k l(x). As in [17], we let
supp(x) = {i : xi 6= 0}, and consider the associated
normalized monotone set function

Different acquisition (i.e. auxiliary) functions have
been proposed to evaluate the utility of candidate
points for the next evaluations of the unknown function [33]. Recently in [34], the variance reduction objective was used as the acquisition function – the unknown function is evaluated at the points that maximally reduce variance of the posterior distribution over
the given set of points that represent potential maximizers. We formalize this as follows.

and f ’s submodularity ratio γ is lower bounded by m
L.
Subsequently, in [13] it is shown that θ can also be
lower bounded by the same ratio m
L.

Setup. Let f (x) be an unknown function defined over
a finite domain X = {x1 , · · · , xn }, where xi ∈ Rd .
Once we evaluate the function at some point xi ∈
X , we receive a noisy observation yi = f (xi ) + z,
where z ∼ N (0, σ 2 ). In Bayesian optimization, f
is modeled as a sample from a Gaussian process.
We use a Gaussian process with zero mean and kernel function k(x, x′ ), i.e. f ∼ GP(0, k(x, x′ )). Let
S = {e1 , · · · , e|S| } ⊆ [n] denote the set of points,
and XS := [xe1 , · · · , xe|S| ] ∈ R|S|×d and yS :=
[y1 , · · · , y|S| ] denote the corresponding data matrix
and observations, respectively. The posterior distribution of f given the points XS and observations yS
is again a GP, with the posterior variance given by:
−1
2
= k(x, x) − k(x, XS ) k(XS , XS ) + σ 2 I|S|
σx|S

In this paper, we consider the robust support selection
problem, that is, finding a set of features S ⊆ [d] of size
k that is robust against the deletion of limited number
of features. More formally, the goal is to maximize the
following objective over all S ⊆ [d]:

For a given set of potential maximizers M ⊆ [n], the
variance reduction objective is defined as follows:
X
2
FM (S) :=
,
(17)
σx2 − σx|S

f (S) :=

max

supp(x)⊆S,x∈X

l(x) − l(0).

Let Tl (x, y) := l(y) − l(x) − h∇l(x), y − xi. An important result from [17] can be rephrased as follows:
if l(·) is L-smooth and m-strongly concave then for all
x, y ∈ dom(l), it holds
−

L
m
ky − xk22 ≥ Tl (x, y) ≥ − ky − xk22 ,
2
2

min

max

|ES |≤τ,ES ⊆S supp(x)⊆S\ES

l(x) − l(0).

By inspecting the bound obtained in Corollary 1, it
remains to bound the (super/sub)additive ratio ν and
ν̌. The first bound follows by combining the result
m
γ≥ m
L with Proposition 1: ν ≥ γ ≥ L . To prove the
second bound, we make use of the following result.
Proposition 2. The supermodularity ratio γ̌ of the
considered objective f (·) can be lower bounded by m
L.
The second bound follows by combining the result in
Proposition 2 and Proposition 1: ν̌ ≥ γ̌ ≥ m
L.
4.2

Variance Reduction in Robust Batch
Bayesian Optimization

In batch Bayesian optimization, the goal is to optimize
an unknown non-convex function from costly concurrent function evaluations [30, 31, 32]. Most often, the
concurrent evaluations correspond to running an expensive batch of experiments. In the case where experiments can fail, it is beneficial to select a set of
experiments in a robust way.

×k(XS , x).

x∈XM

σx2

where
= k(x, x). We show in Appendix D.2.1 that
this objective is not submodular in general.
Finally, our goal is to find a set of points S of size k
that maximizes
X
2
min
.
σx2 − σx|S\E
S
|ES |≤τ,ES ⊆S

x∈XM

Proposition 3. Assume the kernel function is such
that k(xi , xi ) ≤ kmax , for every i ∈ [n]. The objective
function in (17) is normalized and monotone, and both
its curvature α and inverse curvature α̌ can be upper
max
.
bounded by σ2k+k
max
We can combine this result with Proposition 1, to obσ2
σ2
tain ν ≥ γ ≥ σ2 +k
and ν̌ ≥ γ̌ ≥ σ2 +k
. Also,
max
max
4

σ
we have θ ≥ (σ2 +k
2 (Remark 1). Consequently, all
max )
the parameters from Theorem 1 are explicitly characterized.

5

Experimental Results

Optimization performance. For a returned set
S, we measure the performance in terms of

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

The minimum objective value f (S \ E) among all obtained sets E is reported. Most of the time, for all
the considered algorithms, Greedy Min finds E that
reduces utility the most.

1000
800
Obl.-Greedy
Obl.
Greedy
OSU
Pro
Sg
Rg
Omp

600
400
200
11

23

35

47

59

71

Obj. value

Obj. value

1200

600
400
200

83

31

40

49

58

67

76

85

Cardinality k
(a) Lin. reg. (τ = 10)

Cardinality k
(b) Lin. reg. (τ = 30)

0.6

0.4

0.4
0.3

Obl.-Greedy
Obl.
Greedy
OSU
Pro
Sg
Rg
Omp

0.2
0.1
11

23

35

47

59

71

83

Cardinality k
(c) Lin. reg. (τ = 10)

R2 test

0.5

R2 test

800

94

0.3
0.2
0.1

31

40

49

58

67

76

85

94

Cardinality k
(d) Lin. reg. (τ = 30)

Figure 2: Comparison of the algorithms on the linear
regression task.
5.1

Robust Support Selection

Linear Regression. Our setup is similar to the one
in [13]. Each row of the design matrix X ∈ Rn×d is
generated by an autoregressive process,
p
Xi,t+1 = 1 − α2 Xi,t + αǫi,t ,
(18)
5

The random adversaries are inspired by [36] and [37].

200
Obl.-Greedy
Obl.
Greedy

100

11

24

37

50

63

76

Obj. value

300

89

Cardinality k
(a) Log. synthetic (τ = 10)

150
100
50
31 40 49 58 67 76 85 94

Cardinality k
(b) Log. synthetic (τ = 30)

0.9
0.8
0.7

Obl.-Greedy
Obl.
Greedy

0.6
11

24

37

50

63

76

89

Cardinality k
(c) Log. synthetic (τ = 10)

Test accuracy

– Random Greedy adversaries:5 In order to introduce
randomness in the removal process we consider (iii)
Random Greedy Min – iteratively selects a random element from the top τ elements whose marginal gains
are the highest in terms of reducing the objective
value f (S \ E) and (iv) Stochastic Greedy Min – iteratively selects an element, from a random set R ⊆ V ,
with the highest marginal gain in terms of reducing
f (S \ E). At every step, R is obtained by subsampling
(|S|/τ ) log(1/ǫ) elements from S.

200

Obj. value

– Greedy adversaries: (i) Greedy Min – iteratively removes elements to reduce the objective value f (S \ E)
as much as possible, and (ii) Greedy Max – iteratively
adds elements from S to maximize the objective f (E).

400

Test accuracy

minE⊆S,|E|≤τ f (S \ E). Note that f (S \ E) is a submodular function in E. Finding the minimizer E s.t.
|E| ≤ τ is NP-hard even to approximate [35]. We rely
on the following methods in order to find E of size τ
that degrades the solution as much as possible:

0.8
0.75
0.7
0.65
0.6
0.55
31 40 49 58 67 76 85 94

Cardinality k
(d) Log. synthetic (τ = 30)

Figure 3: Logistic regression task with synth. dataset.
where ǫi,t is i.i.d. standard Gaussian with variance
α2 = 0.5. We use n = 800 training data points
and d = 1000. An additional 2400 points are used
for testing. We generate a 100-sparse regression vector by selecting random
entries of ω and set them
 q
ωs = (−1)Bern(1/2) × 5 logn d + δs , where δs is a

standard i.i.d. Gaussian noise. The target is given
by y = Xω + z, where ∀i ∈ [n], zi ∼ N (0, 5).
We compare the performance of Oblivious-Greedy
against: (i) robust algorithms (in blue) such as
Oblivious, PRo-GREEDY [2], OSU [1], (ii)
greedy-type algorithms (in red) such as Greedy,
Stochastic-Greedy [37], Random-Greedy [36],
Orthogonal-Matching-Pursuit. We require β >
1 for our asymptotic results to hold, but we found
out that in practice (small k regime) β ≤ 1 usually gives the best performance. We use ObliviousGreedy with β = 1 unless stated otherwise.
The results are shown in Fig. 6. Since PRo-GREEDY
and OSU only make sense in the regime where τ
is relatively small, the plots show their performance
only for feasible values of k. It can be observed that
Oblivious-Greedy achieves the best performance
among all the methods in terms of both training error and test score. Also, the greedy-type algorithms
become less robust for larger values of τ .
Logistic Regression. We compare the performance
of Oblivious-Greedy vs. Greedy and Oblivious
selection on both synthetic and real-world data.
– Synthetic data: We generate a 100-sparse ω by letting ωs = (−1)Bern(1/2) × δs , with δs ∼ Unif([−1, 1]).
The design matrix X is generated as in (18), with

Robust Maximization of Non-Submodular Objectives

15
10

Obl.-Greedy
Obl.
Greedy

5

Obj. value

Obj. value

12

20

10
8
6
4
2

0
51 56 61 66 71 76 81 86 91 96 101

51 56 61 66 71 76 81 86 91 96 101

Cardinality k
(b) α = 0.1, τ = 50

Cardinality k
(a) α = 0.05, τ = 50
25

3
2.5
2
1.5
1

Obj. value

– MNIST: We consider the 10-class logistic regression task on the MNIST [38] dataset. In this experiment, we set β = 0.5 in Oblivious-Greedy, and
we sample 200 images for each digit for the training
phase and 100 images of each for testing. The results are shown in Fig. 4. It can be observed that
Oblivious-Greedy has a distinctive advantage over
Greedy and Oblivious, while when τ increases the
performance of Greedy decays significantly and more
robust Oblivious starts to outperform it.

25

Obj. value

α2 = 0.09. We set d = 200,and use n = 600 points
for training and additional 1800 points for testing.
The label of the i-th data point X(i,·) is set to 1
if 1/(1 + exp(X(i,·) β)) > 0.5 and 0 otherwise. The
results are shown in Fig. 3. We can observe that
Oblivious-Greedy outperforms other methods both
in terms of the achieved objective value and generalization error. We also note that the performance of
Greedy decays significantly when τ increases.

20
15
10

0.5
51 56 61 66 71 76 81 86 91 96 101

Cardinality k
(c) α = 0.2, τ = 50

5

1 6 11 16 21 26 31 36 41 46 51 56 61 66

Num. of removals τ
(d) α = 0.1, k = 100

Figure 5: Comparison of the algorithms on the variance reduction task.

2000
1000

Obl.-Greedy
Obl.
Greedy

Obj. value

Obj. value

2000
3000

1500
1000
500
47 50 53 56 59 62 65 68

17 24 31 38 45 52 59 66

Cardinality k
(a) MNIST (τ = 15)

Cardinality k
(b) MNIST (τ = 45)

0.7
0.6
0.5
0.4
0.3

Obl.-Greedy
Obl.
Greedy

17 24 31 38 45 52 59 66

Cardinality k
(c) MNIST (τ = 15)

Test accuracy

Test accuracy

0.8

0.5
0.4
0.3

47 50 53 56 59 62 65 68

Cardinality k
(d) MNIST (τ = 45)

Results. In Figure 5 (a), (b), (c), the performance
of all three algorithms is shown when τ is fixed to
50. Different figures correspond to different α values. We observe that when α = 0.1, Greedy outperforms Oblivious for most values of k, while Oblivious clearly outperforms Greedy when α = 0.2. For
all presented values of α, Oblivious-Greedy outperforms both Greedy and Oblivious selection. For
larger values of α, the correlation between the points
becomes small and consequently so do the objective
values. In such cases, all three algorithms perform
similarly. In Figure 5 (d), we show how the performance of all three algorithms decreases as the number
of removals increases. When the number of removals
is small both Greedy and our algorithm perform similarly, while as the number of removals increases the
performance of Greedy drops more rapidly.

Figure 4: Logistic regression with MNIST dataset.
5.2

Robust Batch Bayesian Optimization via
Variance Reduction

Setup. We conducted the following synthetic experiment. A design matrix X of size 600 × 20 is obtained
via the autoregressive process from (18). The function
values at these points are generated from a GP with
3/2-Mátern kernel [39] with both lengthscale and output variance set to 1.0. The samples of this function
are corrupted by Gaussian noise, σ 2 = 1.0. Objective
function used is the variance reduction (Eq. (17)). Finally, half of the points randomly chosen are selected
in the set M , while the other half is used in the selection process. We use β = 0.5 in our algorithm.

6

Conclusion

We have presented a new algorithm ObliviousGreedy that achieves constant-factor approximation
guarantees for the robust maximization of monotone
non-submodular objectives. The theoretical guarantees hold for general τ = ck for some c ∈ (0, 1), which
resolves the important question posed in [1, 2]. We
have also obtained the first robust guarantees for support selection and variance reduction objectives. In
various experiments, we have demonstrated the robust performance of Oblivious-Greedy by showing that it outperforms both Oblivious selection and
Greedy, and hence achieves the best of both worlds.

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

Acknowledgement
The authors would like to thank Jonathan Scarlett and
Slobodan Mitrović for useful discussions. This work
was done during JZ’s summer internship at LIONS,
EPFL. IB and VC’s work was supported in part by
the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation
program (grant agreement number 725594), in part by
the Swiss National Science Foundation (SNF), project
407540 167319/1, in part by the NCCR MARVEL,
funded by the Swiss National Science Foundation.

References
[1] J. B. Orlin, A. S. Schulz, and R. Udwani, “Robust monotone submodular function maximization,” in Int. Conf. on Integer Programming and
Combinatorial Opt. (IPCO), Springer, 2016.
[2] I. Bogunovic, S. Mitrović, J. Scarlett, and
V. Cevher, “Robust submodular maximization: A
non-uniform partitioning approach,” in Int. Conf.
on Machine Learning (ICML), August 2017.
[3] A. Globerson and S. Roweis, “Nightmare at test
time: robust learning by feature deletion,” in Int.
Conf. Machine Learning (ICML), 2006.
[4] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher,
“An analysis of approximations for maximizing
submodular set functions—i,” Mathematical Programming, vol. 14, no. 1, pp. 265–294, 1978.
[5] M. Conforti and G. Cornuéjols, “Submodular set
functions, matroids and the greedy algorithm:
tight worst-case bounds and some generalizations
of the rado-edmonds theorem,” Discrete applied
mathematics, vol. 7, no. 3, pp. 251–274, 1984.
[6] J. Vondrák, “Submodularity and curvature: The
optimal algorithm (combinatorial optimization
and discrete algorithms),” Kokyuroku Bessatsu,
p. 23:253–266, 2010.
[7] R. K. Iyer, S. Jegelka, and J. A. Bilmes, “Curvature and optimal algorithms for learning and
minimizing submodular functions,” in Adv. Neur.
Inf. Proc. Sys. (NIPS), pp. 2742–2750, 2013.
[8] A. Das and D. Kempe, “Submodular meets spectral: Greedy algorithms for subset selection,
sparse approximation and dictionary selection,”
in Proc. of Int. Conf. on Machine Learning,
ICML, pp. 1057–1064, 2011.
[9] A. A. Bian, J. Buhmann, A. Krause, and S. Tschiatschek, “Guarantees for greedy maximization of

non-submodular functions with applications,” in
Proc. Int. Conf. on Machine Learning (ICML),
August 2017.
[10] A. Krause, H. B. McMahan, C. Guestrin, and
A. Gupta, “Robust submodular observation selection,” Journal of Machine Learning Research,
vol. 9, no. Dec, pp. 2761–2801, 2008.
[11] V. Tzoumas, K. Gatsis, A. Jadbabaie, and
G. J. Pappas, “Resilient monotone submodular function maximization,” arXiv preprint
arXiv:1703.07280, 2017.
[12] V. Cevher and A. Krause, “Greedy dictionary selection for sparse representation,” IEEE Journal
of Selected Topics in Signal Processing, vol. 5,
no. 5, pp. 979–988, 2011.
[13] R. Khanna, E. Elenberg, A. G. Dimakis, S. Negahban, and J. Ghosh, “Scalable greedy feature
selection via weak submodularity,” in Proc. of
Int. Conf. on Artificial Intelligence and Statistics,
AISTATS, pp. 1560–1568, 2017.
[14] E. J. Candes, J. K. Romberg, and T. Tao, “Stable
signal recovery from incomplete and inaccurate
measurements,” Communications on pure and applied mathematics, vol. 59, no. 8, pp. 1207–1223,
2006.
[15] P. Jain, A. Tewari, and P. Kar, “On iterative hard
thresholding methods for high-dimensional mestimation,” in Adv. Neur. Inf. Proc. Sys. (NIPS),
pp. 685–693, 2014.
[16] J. Altschuler, A. Bhaskara, G. Fu, V. Mirrokni, A. Rostamizadeh, and M. Zadimoghaddam, “Greedy column subset selection: New
bounds and distributed algorithms,” in Int. Conf.
on Machine Learning (ICML), pp. 2539–2548,
2016.
[17] E. R. Elenberg, R. Khanna, A. G. Dimakis, and S. Negahban, “Restricted strong
convexity implies weak submodularity,” CoRR,
vol. abs/1612.00804, 2016.
[18] S. Mitrovic, I. Bogunovic, A. Norouzi-Fard, J. M.
Tarnawski, and V. Cevher, “Streaming robust
submodular maximization: A partitioned thresholding approach,” in Adv. Neur. Inf. Proc. Sys.
(NIPS), pp. 4560–4569, 2017.
[19] B. Mirzasoleiman, A. Karbasi, and A. Krause,
“Deletion-robust submodular maximization:
Data summarization with “the right to be
forgotten”,” in Int. Conf. Mach. Learn. (ICML),
pp. 2449–2458, 2017.

Robust Maximization of Non-Submodular Objectives

[20] E. Kazemi, M. Zadimoghaddam, and A. Karbasi, “Deletion-robust submodular maximization
at scale,” arXiv preprint arXiv:1711.07112, 2017.
[21] T. Powers, J. Bilmes, S. Wisdom, D. W. Krout,
and L. Atlas, “Constrained robust submodular
optimization.” NIPS OPT2016 workshop, 2016.
[22] X. He and D. Kempe, “Robust influence maximization,” in Int. Conf. Knowledge Discovery and
Data Mining (KDD), pp. 885–894, 2016.
[23] W. Chen, T. Lin, Z. Tan, M. Zhao, and X. Zhou,
“Robust influence maximization,” arXiv preprint
arXiv:1601.06551, 2016.
[24] M. Staib and S. Jegelka, “Robust budget allocation via continuous submodular functions,” in
Proc. of Int. Conf. on Machine Learning (ICML),
pp. 3230–3240, 2017.
[25] A. Hassidim and Y. Singer, “Submodular optimization under noise,” in Proc. of Conf. on Learning Theory, COLT, pp. 1069–1122, 2017.
[26] R. Udwani, “Multi-objective maximization of
monotone submodular functions with cardinality constraint,” arXiv preprint arXiv:1711.06428,
2017.
[27] B. Wilder, “Equilibrium computation for zero
sum games with submodular structure,” arXiv
preprint arXiv:1710.00996, 2017.
[28] N. Anari, N. Haghtalab, S. Pokutta, M. Singh,
A. Torrico, et al., “Robust submodular maximization: Offline and online algorithms,” arXiv
preprint arXiv:1710.04740, 2017.
[29] R. S. Chen, B. Lucier, Y. Singer, and V. Syrgkanis, “Robust optimization for non-convex objectives,” in Adv. in Neur. Inf. Proc. Sys., pp. 4708–
4717, 2017.
[30] T. Desautels, A. Krause, and J. W. Burdick,
“Parallelizing exploration-exploitation tradeoffs
in gaussian process bandit optimization,” The
Journal of Machine Learning Research, vol. 15,
no. 1, pp. 3873–3923, 2014.
[31] J. González, Z. Dai, P. Hennig, and N. Lawrence,
“Batch bayesian optimization via local penalization,” in Artificial Intelligence and Statistics,
pp. 648–657, 2016.
[32] J. Azimi, A. Jalali, and X. Z. Fern, “Hybrid batch
bayesian optimization,” in Proc. of Int. Conf. on
Machine Learning, ICML, 2012.

[33] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams,
and N. de Freitas, “Taking the human out of the
loop: A review of bayesian optimization,” Proceedings of the IEEE, vol. 104, no. 1, pp. 148–175,
2016.
[34] I. Bogunovic, J. Scarlett, A. Krause, and
V. Cevher, “Truncated variance reduction: A unified approach to bayesian optimization and levelset estimation,” in Adv. in Neur. Inf. Proc. Sys.,
pp. 1507–1515, 2016.
[35] Z. Svitkina and L. Fleischer, “Submodular approximation: Sampling-based algorithms and
lower bounds,” SIAM Journal on Computing,
vol. 40, no. 6, pp. 1715–1737, 2011.
[36] N. Buchbinder, M. Feldman, J. S. Naor, and
R. Schwartz, “Submodular maximization with
cardinality constraints,” in Proc. of ACM-SIAM
symposium on Discrete algorithms, pp. 1433–
1452, Society for Industrial and Applied Mathematics, 2014.
[37] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi,
J. Vondrák, and A. Krause, “Lazier than lazy
greedy,” in Proc. Conf. Art. Intell. (AAAI), 2015.
[38] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner,
“Gradient-based learning applied to document
recognition,” Proc. of the IEEE, vol. 86, no. 11,
pp. 2278–2324, 1998.
[39] C. E. Rasmussen and C. K. Williams, Gaussian
processes for machine learning, vol. 1. MIT press
Cambridge, 2006.
[40] K. B. Petersen, M. S. Pedersen, et al., “The matrix cookbook,” Technical University of Denmark,
vol. 7, p. 15, 2008.

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

Appendix
Robust Maximization of Non-Submodular Objectives
(Ilija Bogunovic† , Junyao Zhao† and Volkan Cevher, AISTATS 2018)

A
–
–
–
–

Organization of the Appendix

Appendix
Appendix
Appendix
Appendix

B

B:
C:
D:
E:

Proofs from Section 2
Proofs of the Main Result (Section 3)
Proofs from Section 4
Additional experiments

Proofs from Section 2

B.1

Proof of Proposition 1

Proof. We prove the following relations:
• ν ≥ γ, ν̌ ≥ γ̌:
By setting S = ∅ in both Eq. (4) and Eq. (5), we obtain ∀S ⊆ V :
X
f ({i}) ≥ γf (S),

(19)

i∈S

and
f (S) ≥ γ̌

X

f ({i}).

(20)

i∈S

The result follows since, by definition of ν and ν̌, they are the largest scalars such that Eq. (19) and Eq. (20)
hold, respectively.
• γ ≥ 1 − α̌, γ̌ ≥ 1 − α:
Let S, Ω ⊆ V be two arbitrary disjoint sets. We arbitrarily order elements of Ω = {e1 , · · · , e|Ω| } and we let
Ωj−1 denote the first j − 1 elements of Ω. We also let Ω0 be an empty set.
By the definition of α̌ (see Eq. (7)) we have:
|Ω|
X
j=1

f ({ej }|S) =

|Ω|
X

f ({ej }|S ∪ {ej } \ {ej })

≥

|Ω|
X

(1 − α̌)f ({ej }|S ∪ {ej } \ {ej } ∪ Ωj−1 )

j=1

j=1

= (1 − α̌)f (Ω|S) ,

(21)

where the last equality is obtained via telescoping sums.
Similarly, by the definition of α (see Eq. (6)) we have:
(1 − α)

|Ω|
X
j=1

f ({ej }|S) =

|Ω|
X

(1 − α)f ({ej }|S ∪ {ej } \ {ej })

≤

|Ω|
X

f ({ej }|S ∪ {ej } \ {ej } ∪ Ωj−1 )

j=1

j=1

= f (Ω|S) .

(22)

Because S and Ω are arbitrary disjoint sets, and both γ and γ̌ are the largest scalars such that for all disjoint
P
P|Ω|
sets S, Ω ⊆ V the following holds |Ω|
j=1 f ({ej }|S) ≥ γf (Ω|S) and γ̌
j=1 f ({ej }|S) ≤ f (Ω|S), it follows
from Eq. (21) and Eq. (22), respectively, that γ ≥ 1 − α̌ and γ̌ ≥ 1 − α.

Robust Maximization of Non-Submodular Objectives

B.2

Proof of Remark 1

Proof. Consider any set S ⊆ V , and A and B such that A ∪ B = S, A ∩ B = ∅. We have
P
P
P
ν̌ i∈A f ({i}) + ν̌ i∈B f ({i})
ν̌ i∈S f ({i})
f (A) + f (B)
≥
=
≥ ν ν̌,
f (S)
f (S)
f (S)
where the first and second inequality follow by the definition of ν and ν̌ (Eq. (8) and Eq. (9)), respectively.
By the definition (see Eq. (10)), θ is the largest scalar such that f (A) + f (B) ≥ θf (S) holds, hence, it follows
θ ≥ ν ν̌.

C

Proofs of the Main Result (Section 3)

C.1

Proof of Lemma 2

We reproduce the proof from [2] for the sake of completeness.
Proof.
f (S \ ES∗ ) = f (S) − f (S) + f (S \ ES∗ )

= f (S0 ∪ S1 ) + f (S \ E0 ) − f (S \ E0 ) − f (S) + f (S \ ES∗ )
= f (S1 ) + f (S0 | S1 ) + f (S \ E0 ) − f (S) − f (S \ E0 ) + f (S \ ES∗ )

= f (S1 ) + f (S0 | (S \ S0 )) + f (S \ E0 ) − f (E0 ∪ (S \ E0 )) − f (S \ E0 ) + f (S \ ES∗ )
= f (S1 ) + f (S0 | (S \ S0 )) − f (E0 | (S \ E0 )) − f (S \ E0 ) + f (S \ ES∗ )
= f (S1 ) + f (S0 | (S \ S0 )) − f (E0 | (S \ E0 )) − f (E1 ∪ (S \ ES∗ )) + f (S \ ES∗ )
= f (S1 ) + f (S0 | (S \ S0 )) − f (E0 | (S \ E0 )) − f (E1 | S \ ES∗ )
= f (S1 ) − f (E1 | S \ ES∗ ) + f (S0 | (S \ S0 )) − f (E0 | (S \ E0 ))
≥ (1 − µ)f (S1 ),

(23)

where we used S = S0 ∪ S1 , ES∗ = E0 ∪ E1 . and (23) follows from monotonicity, i.e., f (S0 | (S \ S0 )) − f (E0 | (S \
E0 )) ≥ 0 (due to E0 ⊆ S0 and S \ S0 ⊆ S \ E0 ), along with the definition of µ.
C.2

Proof of Lemma 3

Proof. We start by defining S0′ := OPT(k−τ,V \E0 ) ∩ (S0 \ E0 ) and X := OPT(k−τ,V \E0 ) \ S0′ .
f (S0 \ E0 ) + f (OPT(k−τ,V \S0 ) ) ≥ f (S0′ ) + f (X)

≥ θf (OPT(k−τ,V \E0 ) )
≥ θf (OPT(k−τ,V \ES∗ ) ),

(24)
(25)
(26)

where (24) follows from monotonicity as S0′ ⊆ (S0 \ E0 ) and (V \ S0 ) ⊆ (V \ E0 ). Eq. (25) follows from the fact
that OPT(k−τ,V \E0 ) = S0′ ∪ X and the bipartite subadditive property (10). The final equation follows from the
definition of the optimal solution and the fact that ES∗ = E0 ∪ E1 .
By rearranging and noting that f (S \ ES∗ ) ≥ f (S0 \ E0 ) due to (S0 \ E0 ) ⊆ (S \ ES∗ ) and monotonicity, we obtain
f (S \ ES∗ ) ≥ θf (OPT(k−τ,V \ES∗ ) ) − f (OPT(k−τ,V \S0 ) ).

C.3

Proof of Theorem 1

Before proving the theorem we outline the following auxiliary lemma:

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

Lemma 5 (Lemma D.2 in [2]). For any set function f , sets A, B, and constant α > 0, we have


α
max{αf (A), βf (B) − f (A)} ≥
βf (B).
1+α

(27)

Next, we prove the main theorem.
Proof. First we note that β should be chosen such that the following condition holds |S0 | = ⌈βτ ⌉ ≤ k. When
τ = ⌈ck⌉ for c ∈ (0, 1) and k → ∞ the condition β < 1c suffices.
We consider two cases, when µ = 0 and µ 6= 0. When µ = 0, from Lemma 2 we have
f (S \ ES∗ ) ≥ f (S1 )

(28)

On the other hand, when µ 6= 0, by Lemma 2 and 4 we have
f (S \ ES∗ ) ≥ max{(1 − µ)f (S1 ), (β − 1)ν̌(1 − α̌)µf (S1 )}
≥

(β − 1)ν̌(1 − α̌)
f (S1 ).
1 + (β − 1)ν̌(1 − α̌)

(29)

(β−1)ν̌(1−α̌)
By denoting P := 1+(β−1)ν̌(1−
α̌) we observe that P ∈ [0, 1) once β ≥ 1. Hence, by setting β ≥ 1 and taking the
minimum between two bounds in Eq. (29) and Eq. (28) we conclude that Eq. (29) holds for any µ ∈ [0, 1].

By combining Eq. (29) with Lemma 1 we obtain


k−⌈βτ ⌉
f (S \ ES∗ ) ≥ P 1 − e−γ k−τ
f (OPT(k−τ,V \S0 ) ).

(30)

By further combining this with Lemma 3 we have


k−⌈βτ ⌉
f (OPT(k−τ,V \S0 ) )}
f (S \ ES∗ ) ≥ max{θf (OPT(k−τ,V \ES∗ ) ) − f (OPT(k−τ,V \S0 ) ), P 1 − e−γ k−τ


k−⌈βτ ⌉
P 1 − e−γ k−τ
 f (OPT(k−τ,V \ES∗ ) )

≥θ
k−⌈βτ ⌉
1 + P 1 − e−γ k−τ

(31)

where the second inequality follows from Lemma 5. By plugging in τ = ⌈ck⌉ we further obtain


k−β⌈ck⌉−1
P 1 − e−γ (1−c)k

 f (OPT(k−τ,V \ES∗ ) )
f (S \ ES∗ ) ≥ θ
k−β⌈ck⌉−1
1 + P 1 − e−γ (1−c)k

β 
1−βc− 1 −
k
k
1−c
P 1 − e−γ
∗
≥θ

β  f (OPT(k−τ,V \ES ) )
1−βc− 1 −
k
k
1−c
1 + P 1 − e−γ


−γ 1−βc
1−c
θP
1
−
e
k→∞
 f (OPT(k−τ,V \ES∗ ) ).

−−−−→
1−βc
1 + P 1 − e−γ 1−c
Finally, Remark 2 follows from Eq. (30) when τ ∈ o
is thus satisfied), as k → ∞, we have both
α̌ ∈ [0, 1).

 

k−⌈βτ ⌉
k−τ

k
β

and β ≥ log k (note that the condition |S0 | = ⌈βτ ⌉ ≤ k

→ 1 and P =

(β−1)ν̌(1−α̌)
1+(β−1)ν̌(1−α̌)

→ 1, when ν̌ ∈ (0, 1] and

Robust Maximization of Non-Submodular Objectives

C.4

Proof of Corollary 1

To prove this result we need the following two lemmas that can be thought of as the alternative to Lemma 2
and 4.
Lemma 6. Let µ′ ∈ [0, 1] be a constant such that f (E1 ) = µ′ f (S1 ) holds. Consider f (·) with bipartite subadditivity ratio θ ∈ [0, 1] defined in Eq. (4). Then
f (S \ ES∗ ) ≥ (θ − µ′ )f (S1 ).

(32)

Proof. By the definition of θ, f (S1 \ E1 ) + f (E1 ) ≥ θf (S1 ). Hence,
f (S \ ES∗ ) ≥ f (S1 \ E1 )

≥ θf (S1 ) − f (E1 )
= (θ − µ′ )f (S1 ).

Lemma 7. Let β be a constant such that |S0 | = ⌈βτ ⌉ and |S0 | ≤ k, and let ν̌, ν ∈ [0, 1] be superadditivity and
subadditivity ratio (Eq. (9) and Eq. (8), respectively). Finally, let µ′ be a constant defined as in Lemma 6. Then,
f (S \ ES∗ ) ≥ (β − 1)ν̌νµ′ f (S1 ).

(33)

Proof. The proof follows that of Lemma 4, with two modifications. In Eq. (34) we used the subadditive property
of f (·), and Eq. (35) follows by the definition of µ′ .
f (S \ ES∗ ) ≥ f (S0 \ E0 )
X
f ({ei })
≥ ν̌
ei ∈S0 \E0

≥

|S0 \ E0 | X
ν̌
f ({ei })
|E1 |
ei ∈E1

(β − 1)τ X
ν̌
f ({ei })
≥
τ
ei ∈E1

≥ (β − 1)ν̌νf (E1 )
′

= (β − 1)ν̌νµ f (S1 ).

(34)
(35)

Next we prove the main corollary. The proof follows the steps of the proof from Appendix C.3, except that here
we make use of Lemma 6 and 7.
Proof. We consider two cases, when µ′ = 0 and µ′ 6= 0. When µ′ = 0, from Lemma 6 we have
f (S \ ES∗ ) ≥ θf (S1 ).
On the other hand, when µ′ 6= 0, by Lemma 6 and 7 we have
f (S \ ES∗ ) ≥ max{(θ − µ′ )f (S1 ), (β − 1)ν̌νµ′ f (S1 )}
≥θ

(β − 1)ν̌ν
f (S1 ).
1 + (β − 1)ν̌ν

(36)

(β−1)ν̌ν
and observing that P ∈ [0, 1) once β ≥ 1, we conclude that Eq. (36) holds for any
By denoting P := 1+(β−1)ν̌ν
′
µ ∈ [0, 1] once β ≥ 1.

By combining Eq. (36) with Lemma 1 we obtain


k−⌈βτ ⌉
f (OPT(k−τ,V \S0 ) ).
f (S \ ES∗ ) ≥ θP 1 − e−γ k−τ

(37)

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

By further combining this with Lemma 3 we have


k−⌈βτ ⌉
f (S \ ES∗ ) ≥ max{θf (OPT(k−τ,V \ES∗ ) ) − f (OPT(k−τ,V \S0 ) ), θP 1 − e−γ k−τ
f (OPT(k−τ,V \S0 ) )}


k−⌈βτ ⌉
θ2 P 1 − e−γ k−τ

 f (OPT(k−τ,V \ES∗ ) ),
≥
(38)
k−⌈βτ ⌉
1 + θP 1 − e−γ k−τ
where the second inequality follows from Lemma 5. By plugging in τ = ⌈ck⌉ in the last equation and by letting
k → ∞ we arrive at:


1−βc
θ2 P 1 − e−γ 1−c
 f (OPT(k−τ,V \ES∗ ) ).

f (S \ ES∗ ) ≥
1−βc
1 + θP 1 − e−γ 1−c
 
(β−1)ν̌ν
⌉
Finally, from Eq. (38), when τ ∈ o βk and β ≥ log k, as k → ∞, we have both k−⌈βτ
→ 1 and P = 1+(β−1)ν̌ν
→
k−τ
1 (when ν, ν̌ ∈ (0, 1]). It follows
k→∞

f (S \ ES∗ ) −−−−→

D
D.1

θ2 (1 − e−γ )
f (OPT(k−τ,V \ES∗ ) ).
1 + θ(1 − e−γ )

Proofs from Section 4
Proof of Proposition 2

Proof. The goal is to prove: γ̌ ≥

m
L.

Let S ⊆ [d] and Ω ⊆ [d] be any two disjoint sets, and for any set A ⊆ [d] let x(A) = arg maxsupp(x)⊆A,x∈X l(x).
(A)

Moreover, for B ⊆ [d] let xB

denote those coordinates of vector x(A) that correspond to the indices in B.

We proceed by upper bounding the denominator and lower bounding the numerator in (5). By definition of x(S)
and strong concavity of l(·),

m (S∪{i})
x
− x(S)
2
2
m
≤
max
h∇l(x(S) ), v − x(S) i −
v − x(S)
v:v(S∪{i})c =0
2
2
1
=
∇l(x(S) )i
2m

l(x(S∪{i}) ) − l(x(S) ) ≤ h∇l(x(S) ), x(S∪{i}) − x(S) i −

where the last equality follows by plugging in the maximizer v = x(S) +
X
i∈Ω

 X 1
∇l(x(S) )i
l(x(S∪{i}) ) − l(x(S) ) ≤
2m
i∈Ω

2

=

1
(S)
)i .
m ∇l(x

2

Hence,

1
∇l(x(S) )Ω
2m

On the other hand, from the definition of x(S∪Ω) and due to smoothness of l(·) we have
1
∇l(x(S) )Ω ) − l(x(S) )
L
L 1
1
∇l(x(S) )Ω
≥ h∇l(x(S) ), ∇l(x(S) )Ω i −
L
2 L
2
1
l(x(S) )Ω .
=
2L

l(x(S∪Ω) ) − l(x(S) ) ≥ l(x(S) +

2

2

.

Robust Maximization of Non-Submodular Objectives

It follows that

l(x(S∪Ω) ) − l(x(S) )
m
≥ ,
(S∪{i}) ) − l(x(S) )
L
l(x
i∈Ω

P

∀ disjoint S, Ω ⊆ [d]

We finish the proof by noting that γ̌ is the largest constant for the above statement to hold.

D.2
D.2.1

Variance Reduction in GPs
Non-submodularity of Variance Reduction

The goal of this section is to show that the GP variance reduction objective is not submodular in general.
Consider the following PSD kernel matrix:
√


1 − z2 0
√ 1
K =  1 − z2
1
z2 .
2
0
z
1
We consider a single x = {3} (i.e. M is a singleton) that corresponds to the third data point. The objective is
as follows:
2
2
.
− σ{3}|S∪i
F (i|S) = σ{3}|S
The submodular property implies F ({1}) ≥ F ({1}|{2}). We have:
2
2
− σ{3}|{1}
F ({1}) = σ{3}

= 1 − K({3}, {3}) − K({3}, {1})(K({1}, {1}) + σ 2 )−1 K({1}, {3})

= 1 − 1 + 0 = 0,
and

2
2
− σ{3}|{2}
F ({2}) = σ{3}

= 1 − K({3}, {3}) − K({3}, {2})(K({2}, {2}) + σ 2 )−1 K({2}, {3})

= 1 − (1 − z 2 (1 + σ 2 )−1 z 2 ) =

z4
,
1 + σ2

and
2
2
F ({1, 2}) = σ{3}
− σ{3}|{1,2}

= 1 − K({3}, {3}) + [K({3}, {1}), K({3}, {2})]

√
−1  
2
1
+
σ
,
0
1 − z2
= 1 − 1 + [0, z ] √
z2
1 − z 2 , 1 + σ2
2

=


−1 

1 + σ 2 , K({2}, {1})
K({1}, {3})
K({1}, {2}), 1 + σ 2
K({2}, {3})



z 4 (1 + σ 2 )
.
(1 + σ 2 )2 − (1 − z 2 )

We obtain,
F ({1}|{2}) = F ({1, 2}) − F ({2})
=

z4
z4
−
.
(1 + σ 2 ) − (1 − z 2 )(1 + σ 2 )−1
1 + σ2

When z ∈ (0, 1), F ({1}|{2}) is strictly greater than 0, and hence greater than F ({1}). This is in contradiction
with the submodular property which implies F ({1}) ≥ F ({1}|{2}).

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

D.2.2

Proof of Proposition 3

Proof. We are interested in lower bounding the following ratios:

f ({i}|S\{i}∪Ω)
f ({i}|S\{i})

and

f ({i}|S\{i})
f ({i}|S\{i}∪Ω) .

Let kmax ∈ R+ be the largest variance, i.e. k(xi , xi ) ≤ kmax for every i. Consider the case when M is a singleton
set:
2
2
f (i|S) = σx|S
− σx|S∪i
.
By using Ω = {i} in Eq. (39), we can rewrite f (i|S) as
f (i|S) = a2i Bi−1 ,
where ai , Bi ∈ R+ , and are given by:
ai = k(x, xi ) − k(x, XS )(k(XS , XS ) + σ 2 I)−1 k(XS , xi )
and
Bi = σ 2 + k(xi , xi ) − k(xi , XS )(k(XS , XS ) + σ 2 I)−1 k(XS , xi ).
By using the fact that k(xi , xi ) ≤ kmax , for every i and S, we can upper bound Bi by σ 2 + kmax (note that
k(xi , xi ) − k(xi , XS )(k(XS , XS ) + σ 2 I)−1 k(XS , xi ) ≥ 0 as variance cannot be negative), and lower bound by σ 2 .
It follows that for every i and S we have:

σ2

a2i
a2
≤ f (i|S) ≤ i2 .
+ kmax
σ

Therefore,
σ2
a2 /(σ 2 + kmax )
f ({i}|S \ {i} ∪ Ω)
=
,
≥ i
f ({i}|S \ {i})
a2i /σ 2
σ 2 + kmax
σ2
a2 /(σ 2 + kmax )
f ({i}|S \ {i})
=
,
≥ i
f ({i}|S \ {i} ∪ Ω)
a2i /σ 2
σ 2 + kmax

∀S, Ω ⊆ V, i ∈ S \ Ω,
∀S, Ω ⊆ V, i ∈ S \ Ω.

It follows:
σ2
,
σ 2 + kmax
σ2
(1 − α̌) ≥ 2
.
σ + kmax
(1 − α) ≥

and

The obtained result also holds for any set M ⊆ [n].
D.2.3

Alternative GP variance reduction form

Here, the goal is to show that the variance reduction can be written as
2
2
F (Ω|S) = σx|S
− σx|S∪Ω
= aB−1 aT ,
1×|Ω\S|

where a ∈ R+

|Ω\S|×|Ω\S|

, B ∈ R+

and are given by:

a := k(x, XΩ\S ) − k(x, XS )(k(XS , XS ) + σ 2 I)−1 k(XS , XΩ\S ),
and
B := σ 2 I + k(XΩ\S , XΩ\S ) − k(XΩ\S , XS )(k(XS , XS ) + σ 2 I)−1 k(XS , XΩ\S ).
This form is used in the proof in Appendix D.2.2.

(39)

Robust Maximization of Non-Submodular Objectives

Proof. Recall the definition of the posterior variance:
2
σx|S
= k(x, x) − k(x, XS ) k(XS , XS ) + σ 2 I|S|

−1

k(XS , x).

We have
2
2
− σx|S∪Ω
F (Ω|S) = σx|S

−1
−1
= k(x, XS∪Ω ) k(XS∪Ω , XS∪Ω ) + σ 2 I|Ω∪S|
k(XS∪Ω , x) − k(x, XS ) k(XS , XS ) + σ 2 I|S|
k(XS , x)
−1  T 

m1
A11 , A12
−1 T
= [m1 , m2 ]
− m1 A11
m1 ,
mT2
A21 , A22

where we use the following notation:
m1 := k(x, XS ),
m2 := k(x, XΩ\S ),
A11 := k(XS , XS ) + σ 2 I|S| ,
A12 := k(XS , XΩ\S ),
A21 := k(XΩ\S , XS ),
A22 := k(XΩ\S , XΩ\S ) + σ 2 I|Ω\S| .
By using the inverse formula [40, Section 9.1.3] we obtain:
 −1
 T
−1
−1
−1
A11 + A−1
A21 A11
, −A−1
m1
T
11 A12 B
11 A12 B
F (Ω|S) = [m1 , m2 ]
− m1 A−1
−1
11 m1 ,
mT2
−B−1 A21 A11
,
B−1
where

B := A22 − A21 A−1
11 A12 .

Finally, we obtain:
−1
T
−1
T
−1
T
F (Ω|S) = m1 A−1
A21 A−1
A21 A−1
11 m1 + m1 A11 A12 B
11 m1 − m2 B
11 m1
−1 T
T
− m1 A−1
m2 + m2 B−1 mT2 − m1 A−1
11 A12 B
11 m1

−1 T
−1
T
T
= m1 A−1
(A21 A11
m1 − mT2 ) − m2 B−1 (A21 A−1
11 A12 B
11 m1 − m2 )

−1
T
T
= (m1 A11
A12 − m2 )B−1 (A21 A−1
11 m1 − m2 )

−1
T
= (m2 − m1 A−1
(mT2 − A21 A−1
11 A12 )B
11 m1 ).

By setting
a := m2 − m1 A−1
11 A12

= k(x, XΩ\S ) − k(x, XS )(k(XS , XS ) + σ 2 I)−1 k(XS , XΩ\S )

and
T
aT := mT2 − A21 A−1
11 m1

= k(XΩ\S , x) − k(XΩ\S , XS )(k(XS , XS ) + σ 2 I)−1 k(XS , x),

we have
F (Ω|S) = aB−1 aT ,
where
B = σ 2 I|Ω\S| + k(XΩ\S , XΩ\S ) − k(XΩ\S , XS )(k(XS , XS ) + σ 2 I|S| )−1 k(XS , XΩ\S ).

Ilija Bogunovic† , Junyao Zhao† , Volkan Cevher

E

Additional Experiments
0.5

200

21 31 41 51 61 71 81 91

Obj. value

100
50

Cardinality k
(e) Log. synthetic (τ = 20)

65

73

81

89

21

31

41

51

61

71

81

0.85

50

49

57

65

73

81

41

0.75
0.7
0.65

1500
1000

2000
1500
1000
500

500
33

39

45

51

57

Cardinality k
(i) MNIST (τ = 25)

63

37

42

47

52

57

62

Cardinality k
(j) MNIST (τ = 35)

67

Cardinality k
(g) Log. synthetic (τ = 20)

0.6
0.5
0.4
0.3
0.2
27

65

73

81

89

33

39

45

51

57

63

Cardinality k
(k) MNIST (τ = 25)

0.75
0.7
0.65
0.6
0.55
41

49

57

65

73

81

89

Cardinality k
(h) Log. synthetic (τ = 40)
Test accuracy

2000

57

0.8

0.8

0.7

2500

49

Cardinality k
(d) Lin. reg. (τ = 40)

0.6
21 31 41 51 61 71 81 91

89

0.1

91

150

100

0.2
0.15

0.05

Cardinality k
(c) Lin. reg. (τ = 20)

2500

Obj. value

Obj. value

57

Cardinality k
(f) Log. synthetic (τ = 40)

3000

27

0.2

Cardinality k
(b) Lin. reg. (τ = 40)

41

21 31 41 51 61 71 81 91

49

Test accuracy

Obj. value

150

0.3

0.1

41

Cardinality k
(a) Lin. reg. (τ = 20)
200

200

R2 test

400

400

Test accuracy

Obl.-Greedy
Obl.
Greedy
OSU
Pro
Sg
Rg
Omp

600

0.4

R2 test

800

0.25

600

Test accuracy

1000

Obj. value

Obj. value

1200

0.6
0.5
0.4
0.3
0.2
37

42

47

52

57

62

Cardinality k
(l) MNIST (τ = 35)

Figure 6: Additional experiments for comparison of the algorithms on support selection task.

67

