Deletion-Robust Submodular Maximization at Scale
Ehsan Kazemi

ehsan.kazemi@yale.edu

Yale University, New Haven, CT 06511, USA

Morteza Zadimoghaddam

zadim@google.com

arXiv:1711.07112v2 [cs.LG] 21 Nov 2017

Google Research, New York, NY 10011, USA

Amin Karbasi

amin.karbasi@yale.edu

Yale University, New Haven, CT 06511, USA

Abstract
Can we efficiently extract useful information from a large user-generated dataset while
protecting the privacy of the users and/or ensuring fairness in representation. We cast
this problem as an instance of a deletion-robust submodular maximization where part
of the data may be deleted due to privacy concerns or fairness criteria. We propose the
first memory-efficient centralized, streaming, and distributed methods with constant-factor
approximation guarantees against any number of adversarial deletions. We extensively
evaluate the performance of our algorithms against prior state-of-the-art on real-world
applications, including (i) Uber-pick up locations with location privacy constraints; (ii)
feature selection with fairness constraints for income prediction and crime rate prediction;
and (iii) robust to deletion summarization of census data, consisting of 2,458,285 feature
vectors.

1. Introduction
It has long been known that solutions obtained from optimization methods can demonstrate
striking sensitivity to the parameters of the problem (Bertsimas et al., 2011). Robust
optimization, in contrast, is a paradigm in the mathematical programming community
with the aim of safeguarding the solutions from the (bounded) changes in the underlying
parameters.
In this paper, we consider submodular maximization, a very well studied discrete optimization problem defined over a finite set of items (e.g., images, videos, blog posts, sensors,
etc). Submodularity formalizes the notion of diminishing returns, stating (informally) that
selecting an item earlier results in a higher utility than selecting it later. This notion has
found far-reaching applications in machine learning (Bach et al., 2013), web search and
mining (Borodin et al., 2017), social network (Kempe et al., 2003), crowdsourcing (Singla
et al., 2016), and user modeling (Yue and Guestrin, 2011), to name a few. However, almost
all the existing methods for submodular maximization, ranging from centralized (Nemhauser
et al., 1978; Feldman et al., 2017) to streaming (Badanidiyuru et al., 2014), to distributed
(Mirzasoleiman et al., 2013; Mirrokni and Zadimoghaddam, 2015; Barbosa et al., 2015), rely
on greedy selection of elements. As a result, the returned solution of such methods are
remarkably sensitive to even a single deletion from the set of items.
1

The need for efficient deletion-robust optimization methods is wide-spread across many
data-driven applications. With access to big and massive data (usually generated by millions
of users), along with strong machine learning techniques, many service providers have been
able to exploit these new resources in order to improve the accuracy of their data analytics.
At the same time, it has been observed that many such inference tasks may leak very sensitive
information about the data providers (i.e., personally identifiable information, protected
health information, legal or financial data, etc). Similarly these algorithms can encode hidden
biases that disproportionately and adversely impact members with certain characteristics
(e.g., gender, race, religion, sexual orientation).
In order to reduce the effect of information extraction on privacy or fairness, one needs to
be able to remove sensitive data points (e.g., geolocations) or discard sensitive data features
(e.g., skin color) from the dataset without incurring too much loss in performance. For
instance, European Commission disclosed a draft “European Data Protection Regulation”
that contains concrete guidelines for providing individuals with the “right to be forgotten”.
By exercising this right, individuals may enforce the service provider to delete their personal
data or put restrictions from using part of it. Similarly, Title VII of the Civil Rights Act
of American anti-discrimination law prohibits employment discrimination against certain
characteristics (such as color and sex). Thus, to obtain fairer machine learning algorithms,
we need to reduce the bias inherent in the training examples due to the lack of certain
types of information, not being representative, or reflecting historical biases. This can be
done by either removing protected attributes from training data (Zemel et al., 2013) or
train them separately for different protected groups (Chayes, 2017), among other procedures.
Unfortunately, sensitive features or biased data usually are not known a priori and we might
get aware of their existence just after training our models (Beutel et al., 2017). Retraining a
machine learning model from scratch, after removing sensitive features and biased data, is
quite expensive for large datasets. Deletion-robust submodular maximization can save a lot
of time and computational resources in these scenarios.
Most existing submodular maximization methods, often used for data extraction (Mirzasoleiman et al., 2013) and informative subset selection (Wei et al., 2015), do not provide
such guarantees. In this paper, we develop the first scalable and memory-efficient algorithms
for maximizing a submodular function subject to a cardinality constraint that are robust
against any number of adversarial deletions. This is in sharp contrast to previous methods
that could only handle a fixed number of deletions (Orlin et al., 2016; Bogunovic et al., 2017)
or otherwise their memory requirement scales multiplicatively with the number of deletions
(Mirzasoleiman et al., 2017) (e.g., to handle 10 deletions, the robust solution becomes 10
folds larger).
Our contributions: To maximize a monotone submodular function with a cardinality
constraint k, we develop the following algorithms that are robust against any d adversarial
deletions:
• Centralized solution: We propose Robust-Centralized that achieves (1/2 − δ)- 
approximation guarantee (in expectation) with the memory requirement O k + (d log k)/δ 2 .
• Streaming solution: We propose Robust-Streaming that achieves
(1/2−δ)-approximation


k log k
log2 k
guarantee (in expectation) with the memory requirement O
+
d
.
3
δ
δ
2

Table 1: Comparison of algorithms for robust monotone submodular maximization with a
cardinality constraint.
Algorithm
OSU (Orlin et al., 2016)
Pro-Greedy (Bogunovic et al., 2017)
Robust (Mirzasoleiman et al., 2017)

Max. Robustness
√
o( k)
o(k)
arbitrary d

Robust-Centralized (ours)
Robust-Streaming (ours)
Robust-Distributed (ours)
Compact-Distributed (ours)

arbitrary
arbitrary
arbitrary
arbitrary

d
d
d
d

Approx.

Memory

Setup

0.387
0.387
1/2 - δ

k
k
O(kd log k/δ)

Centralized
Centralized
Streaming

1/2 − δ
1/2 − δ
0.218 − δ
0.109 − δ

O(k + d log k/δ 2 )
O(k log k/δ + d log2 k/δ 3 )
O(m(k + d log k/δ 2 ))
O(k + d log k/δ 2 )

Centralized
Streaming
Distributed
Distributed

• Distributed solution: We propose Robust-Distributed that achieves (0.218 − δ)- 
k
approximation guarantee (in expectation) with the memory requirement O m(k + d log
) ,
δ2
where m is the number of machines. We also introduce Compact-Distributed, a
variant of Robust-Distributed, where its memory requirement is independent of
number of machines.
Table 1 compares our proposed methods with previous algorithms. Our experimental results
demonstrate the effectiveness of our proposed methods on several real-life applications.

2. Related Work
Monotone submodular maximization under cardinality constraints is studied extensively in
centralized, streaming and distributed scenarios. The classical result of Nemhauser et al.
(1978) proves that the simple GREEDY algorithm that starts with an empty set and
iteratively adds elements with the highest marginal gain provides (1 − 1/e)-approximation
guarantee. To scale to large datasets, several multi-pass and streaming algorithms with
constant factor approximations have recently been proposed (Krause and Gomes, 2010;
Badanidiyuru et al., 2014; Kumar et al., 2015; Buchbinder et al., 2015). Also, different
distributed submodular maximization algorithms have been developed lately (Mirzasoleiman
et al., 2013; Mirrokni and Zadimoghaddam, 2015; Barbosa et al., 2015).
Krause et al. (2008) introduced the robust formulation of the classical cardinality constrained submodular maximization for the first time and gave a bi-criterion approximation to
the problem of max|A|≤k mini∈{1,··· ,`} fi (A), where fi is normalized monotone submodular for
every i. Note that submodular maximization of function f that is robust to the deletion of d
items can be modeled as a special case of this problem: max|A|≤k min|D|≤d f (A \ D). Krause
et al. (2008) guarantee a robust solution by returning a set whose size is k(1+Θ(log(dk log n)).
There are two main drawbacks with this approach when applied to deletions: first, the size
of final solution is logarithmically larger than k, and second, the running time is exponential
in d. Orlin et al. (2016) designed a centralized algorithm that outputs a set √
of cardinality
k in a polynomial time. Their algorithm is robust to the deletion of only o( k) elements.
Bogunovic et al. (2017) further improved the result of Orlin et al. (2016) to o(k) deletions.
The approximation guarantees for both of these algorithms are 0.387. The aforementioned
methods try to construct a solution without allowing to update the answer after deletion. In
contrast, Mirzasoleiman et al. (2017) developed a streaming algorithm which is robust to the
3

deletion of any number of d elements. They keep a set of size O(kd log k/δ), and after each
deletion they find a feasible solution of size at most k from this set. They also improved the
approximation guarantee to 1/2 − δ. The main drawback of this algorithm is the memory
√
requirement, which is quite impractical for large values of d and k; e.g., for k = O( n) and
√
d = O( n) the memory requirement is even larger than n.
Submodular maximization under a cardinality constraint has been widely used in classical
machine learning and data mining applications, including extracting representative elements
with exemplar based clustering (Krause and Gomes, 2010), data summarization through
active set selection (Herbrich et al., 2003; Seeger, 2004; Krause and Guestrin, 2005), feature
selection (Krause and Guestrin, 2005) and document summarization (Lin and Bilmes, 2011).
Furthermore, there are many other areas where robust submodular maximization could be
quite useful, including influence maximization (He and Kempe, 2016), personalized image
summarization (Lucic et al., 2016), sensor placement (Krause et al., 2008) and robust feature
selection (Globerson and Roweis, 2006).

3. Problem Definition
Assume we have a set function f : 2V → R≥0 . We define the marginal gain of an element
e ∈ V to the set A ⊆ V by ∆f (e|V ) = f (A ∪ {e}) − f (A). The function f is submodular if
for all A ⊆ B ⊆ V and e ∈ V \ B, we have ∆f (e|A) ≥ ∆f (e|B). A submodular function f is
monotone if for every A ⊆ B ⊆ V , we have f (A) ≤ f (B).
Through this paper our focus is on maximizing a monotone submodular function with a
cardinality constraint given a parameter k, i.e., our goal is to solve the following problem:
S ∗ = arg max f (S).

(1)

S⊆V,|S|≤k

In many applications, a subset of items of the ground set V may be removed and we
need to solve Eq. (1) again without the deleted items. For this reason, we require to make
our solution robust to the deletion. Indeed, the goal is to maximize a submodular function f
over a set V of items, where it is robust to the deletion of any subset D ⊂ V of size |D| ≤ d.
More precisely, we are interested in solving the following problem for each possible instance
of D:
S∗ =

arg max f (S).

(2)

S⊆V \D,|S|≤k

We also define OPT = f (S ∗ ). The most straightforward approach to this problem is to
solve Eq. (2) for each instance of D. Unfortunately, solving Eq. (2), for large datasets,
is computationally prohibitive. Also, deletion of elements from the set V can happen at
different stages in real time applications. This makes the problem even harder. Our solution
to this problem is to maintain a small subset A of V , called a core-set of V , where for each
set D we can efficiently find a subset B ⊆ A \ D that provides an acceptable approximation
for Eq. (2). For this reason, next we define the notion of (α, d)-robust randomized core-set.
Definition 1 A random subset of A ⊆ V is an (α, d)-robust randomized core-set for a set
V, if for any subset D ⊆ V of size |D| ≤ d, there exists a B ⊆ A \ D, |B| ≤ k such that
E[f (B)] ≥ α

max

S⊆V \D,|S|≤k

4

f (S).

4. Robustness and Cardinality Constraint
In this section, we present three fast and scalable randomized algorithms. These algorithms
solve the problem of robust submodular maximization in centralized, streaming and distributed scenarios. Our algorithms provide, in expectation, constant factor approximation
guarantees, where they are robust to the adversarial deletion of any d items from the set V.
In our setting, an adversary might try to find a set of inputs for which our algorithms fail to
provide good results. In order to make the optimization robust to the adversarial deletions,
we introduce randomness in the selection process. We also assume that the adversary dose
not have access to the random bits of the randomized algorithms.
The algorithms are designed based on a general idea that the elements are chosen randomly
from a large enough pool of similar items. This idea is useful because the adversary is not
aware of the random bits of the algorithms, which makes the deletion probability of elements
we have chosen negligible. Therefore, we can bound the expected value of the selected set.
Our solution consists of two steps. In the first step, we find a small core-set of elements
(in comparison to the whole dataset). We prove that after the deletion of at most d arbitrary
elements, we can still find a good approximation for the optimization problem in this small
set. In the second step, we choose at most k elements from the core-set we have found in the
first step. We prove a constant approximation factor for our algorithm in expectation. This
guarantees that the core-set is (α, d)-robust randomized for a constant α and arbitrary d.
In the optimization procedure, we use a thresholding idea to select elements. Similar
ideas have been used previously for designing streaming algorithms (Badanidiyuru et al.,
2014; Buchbinder et al., 2015). In those algorithms, when an element of the stream arrives, if
this element has sufficiently large marginal value it is kept. Otherwise it is discarded. In the
robust submodular maximization, we keep a large enough pool of elements with sufficient
marginal values before adding or discarding them. We randomly pick an element when the
size of pool is at least d/. Thus the element picked at each step is deleted with a probability
at most . This is true because the size of deleted items is at most d. To guarantee the
quality of the chosen elements after the deletion (i.e., we want the expected value of f over
the set of picked elements does not change a lot after deletion), not only they should have
been picked from a large pool of elements, the elements of pool should have almost the same
marginal gains. To explain why we need this property consider the following example.

Example 1 Suppose the ground set V consists of identical elements with equal value of
1. In other words, for any A ⊆ V , let f (A) be 1 if A is not empty, and let it be 0 for the
empty set. In this case, all elements are good candidates to be chosen at the beginning of
algorithm. However after choosing any of them, the marginal gain of the rest becomes 0, and
the algorithm has no incentive to continue selecting elements. If the first element is chosen
deterministically, the adversary can delete that element and we can not find any non-zero
value subset after deletion. Now if we pick d/ of these elements and then pick one of them
randomly, the probability that adversary can delete the chosen element reduces to  and we
achieve the robustness we aim for.
5

4.1 Centralized Algorithm
In this section we outline a centralized algorithm, called Robust-Coreset-Centralized,
to find an (α.d)-robust core-set for V. We also present the Robust-Centralized algorithm
which is able to find a good solution for Eq. (2) from the core-set. We use the threshold
based algorithmic ideas of Badanidiyuru et al. (2014) that yield the state of the art streaming
algorithms for submodular maximization. We then elaborate on the challenges the adversarial
deletion process causes for this approach and how we resolve them.
In their work, Badanidiyuru et al. (2014) prove that choosing elements with marginal
gain at least τ ∗ = OPT
2k from a stream until a maximum of k elements are chosen returns a
set S with an approximation factor of 1/2. The main problem with this primary idea is that
the value of OPT is not known by the algorithm. Badanidiyuru et al. (2014) pointed out
that, from the submodularity of f , we have ∆0 ≤ OPT ≤ k∆0 where ∆0 is the largest value
in set {f ({e})|e ∈ V }. By dividing the range [∆0 , k∆0 ] into intervals of [τi , τi+1 ) (where
τi+1 /τi is close to 1) it is possible to find a good enough approximation for OPT. Since the
ratio of upper and lower limits of the range [∆0 , k∆0 ] is k, it suffices to try log k different
estimates to get a close match on one of the guesses. In an streaming algorithm, we do not
know the maximum value of singletons a priori. Badanidiyuru et al. (2014) showed that
it is enough to look at the range mt ≤ OPT ≤ 2kmt , where mt is the maximum value of
elements observed at time t.
We first note that due to the deletion process, the relevant maximum singleton value
is not ∆0 , it is ∆00 = maxe∈V \D f ({e}). The algorithm is unaware of set D, therefore ∆00
could be anywhere in the range [∆d , ∆0 ] where ∆d is the d + 1-th largest value in the set
{f ({e})|e ∈ V }. The lower bound of ∆d is implied by the fact that at most d elements will be
deleted. So τ ∗ = OPT
2k could fall anywhere in the range [∆d /2k, ∆0 ]. Unlike (Badanidiyuru
et al., 2014), the upper and lower limits of this range do not differ only by a multiplicative
factor of k, thus a naive approach makes us try arbitrarily large number of different choices
to find a good estimate of τ ∗ . We resolve this issue by the following observation.
We reserve a set B of elements that might be valuable after the deletion process. Let
Vd be the (d + 1) largest singleton value elements, i.e., the top d + 1 elements e in the set
{f ({e})|e ∈ V }. We preserve all elements of Vd for the next round by inserting them to B.
This way we do not have to worry about thresholds above ∆d as all elements that might have
marginal value above ∆d to any set should be in set Vd and they are added to B. Therefore,
∆d
≤ (1 + )i ≤ ∆d }.
we consider all thresholds in the set T = {(1 + )i |
2k
Starting from the largest τ ∈ T to the smallest threshold in T, we iteratively construct
two sets Aτ and Bτ . At the end of the algorithm, the set B is defined as the union of Vd and
∪τ ∈T Bτ . We output the set B, along with all sets {Aτ }τ ∈T , as the core-set.
We initialize Aτ to ∅. We let Bτ to be the set of elements whose marginal values to
the set ∪τ 0 ≥τ Aτ 0 is in the range [τ, (1 + )τ ). We note that this is a dynamic definition
and whenever we add an element to any Aτ set, the related Bτ set might change as well.
Elements in the set Bτ are similar to each other in terms of their marginal values. Without
deletions, we can choose any element from Bτ and add it to our solution. However, if Bτ
has only a few elements, the adversary can delete all of them, and we will be left with an
arbitrary poor solution. To make the selection process robust, we select a random element
from Bτ and add it to Aτ only if there are at least d/ elements in Bτ . This way even if all
6

deleted elements are from the set Bτ , the probability of the selected elements being deleted
is at most . We also know that all elements added to Aτ have similar marginal values and
are interchangeable. We keep adding elements to Aτ until either ∪τ 0 ≥τ Aτ 0 has k elements or
the size of set Bτ becomes smaller than d/. At this stage, we keep both sets Aτ and Bτ as
a part of the output core-set. We also remove them from the ground set V and move on to
the next lower threshold. The pseudo code of Robust-Coreset-Centralized is given in
Algorithm 1.
Algorithm 1: Robust-Coreset-Centralized
1
2
3
4
5
6
7

8
9
10
11

∆d ← the (d + 1)-th largest value of set {f ({e})|e ∈ V };
Vd ← all the d + 1 elements with the largest values in set {f ({e})|e ∈ V };
∆d
T = {(1 + )i | 2(1+)k
≤ (1 + )i ≤ ∆d };
For each τ ∈ T : {Aτ } ← ∅ and {Bτ } ← ∅;
V ← V \ Vd ;
for τ ∈ T from the highest to the lowest do
while |Bτ | ≥ d for Bτ = {e ∈ V : τ ≤ ∆f (e| ∪τ 0 ≥τ Aτ 0 ) < (1 + )τ } and
| ∪τ 0 ≥τ Aτ 0 | < k do
Randomly pick an element e from Bτ and add it to Aτ , i.e., Aτ ← Aτ ∪ {e};
V ← V \ (Aτ ∪ Bτ );
B ← {∪Bτ } ∪ Vd ;
return {Aτ }, B

The sets {Aτ } and B are the outputs (core-set) of Robust-Coreset-Centralized.
Next we show how Robust-Centralized (with pseudo code given in Algorithm 2) returns a
solution for submodular maximization problem after the deletion of set D. The subsets of Aτ
and B after the deletion of set D are denoted by A0τ and B 0 , respectively, i.e., A0τ = Aτ \ D
and B 0 = B \ D. Robust-Centralized uses the sets {A0τ } and B 0 in order to find a
good solution to the optimization problem of Eq. (2). Robust-Centralized considers
all the possible thresholds in the range [∆00 /(2k), ∆00 ], where ∆00 is the largest value in set
{f ({e})|e ∈ V \ D}. We note that at this point, we can compute the value of ∆00 because the
set of deleted elements are revealed and we also kept all elements in Vd as part of the core-set.
For each threshold τ, we can ensure that the marginal gain of elements in Sτ = ∪τ 0 >τ Aτ 0 is
at least τ. Therefore, we keep them as part of the solution. Next for any element e ∈ B 0 the
Robust-Centralized algorithm checks if the marginal gain of e to Sτ is at least τ . If it
is, then e is added to Sτ . We do not need to introduce any extra randomness or selection
from a large pool of candidates for additional robustness at this point, since the deletions
are done already. The final solution is the set with the maximum value f (Sτ ) among all Sτ .
Theorem 1 For any δ > 0, by setting  = 2δ
3 , Robust-Coreset-Centralized and
Robust-Centralized satisfy the following properties:
• Robust-Centralized outputs a set S such that |S| ≤ k and E[f (S)] ≥ ( 12 − δ)OPT.
7

Algorithm 2: Robust-Centralized
Input: {A0τ } and B 0 // A0τ and B 0 contain elements of Aτ and B (outputs of
Robust-Coreset-Centralized) after deletion.
1
2
3
4
5
6
7
8

Output: Set S of cardinality at most k
∆00 ← the largest value of set {f ({e})|e ∈ {∪A0τ } ∪ B 0 };
∆0

0
T0 = {(1 + )i | 2(1+)k
≤ (1 + )i ≤ ∆00 };

0 from the highest to the lowest do
for τ ∈ TS
Sτ ← τ 0 ∈T0 ,τ 0 ≥τ A0τ 0 ;
for all e ∈ B 0 do
if ∆f (e|Sτ ) ≥ τ and |Sτ | < k then
Sτ ← Sτ ∪ e;
return arg maxSτ f (Sτ )



k
• Robust-Coreset-Centralized outputs at most O k + d log
elements as the core2
δ
set. Since this core-set is the input of Robust-Centralized, its space complexity is
upper bounded by the same number of elements.
• The query complexities
 of Robust-Coreset-Centralized


and Robust-Centralized
log k
log k log k
are, respectively, O (k + δ )|V | and O (k + d δ2 ) δ .
Proof We define V 0 = V \ D. Assume A0τ and B 0 , respectively, are subsets of Aτ and B
after deletion of set D from V . We define S ∗ = arg maxS⊆V \D,|S|≤k f (S) and f (S ∗ ) = OPT.
We start by showing that one of the thresholds the Robust-Centralized algorithm tries is
1
close to the standard threshold OPT
2k that guarantees the 2 approximation without deletion.
Lemma 1 There is a τ ∗ ∈ T0 such that τ ∗ ≤
of Robust-Centralized.

OPT
2k

< τ ∗ (1 + ), where T0 is defined in line 2

Proof From the submodularity of f we have ∆00 ≤ OPT ≤ k∆00 . Therefore, the smallest
∗
0
threshold in T0 is at most OPT
2k . Setting τ to be the largest threshold in T that does not
OPT
exceed 2k will satisfy the claim of this lemma.
Since Robust-Centralized tries different thresholds and outputs the maximum value
solution among them, it suffices to lower bound the expected value of f (Sτ ∗ ) by ( 12 − δ)OPT.
We note that Sτ ∗ consists of two parts: the elements added in the first stage (RobustCoreset-Centralized) that are not deleted, i.e. ∪τ ≥τ ∗ A0τ , and the set of elements added
in the second stage (line 7 of Robust-Centralized). We start by showing that the effect
of deletion on the value of the first part is negligible due to the robustness of how we
insert elements in Robust-Coreset-Centralized. To simplify the analysis, we abuse the
notation, and define A = ∪τ ≥τ ∗ Aτ and A0 = ∪τ ≥τ ∗ A0τ .
Lemma 2 E[f (A0 )] ≥ (1−2)E[f (A)], and consequently we have E[f (Sτ ∗ )] ≥ (1−2)E[f (Sτ ∗ ∪
A)] where the expectations are taken over the random coin flips of Robust-CoresetCentralized.
8

Proof We represent elements of Aτ with Aτ = {eτ,1 , · · · , eτ,nτ }. Similarly, we define
A0τ = {e0τ,1 , · · · , e0τ,n0τ }. We also define nτ = |Aτ | and n0τ = |A0τ |. We have
∗

|Aτ |
τ
X
X

f (A) =

∆f (eτ,l | ∪τ 0 >τ Aτ 0 ∪ {eτ,1 , · · · , eτ,l−1 }),

τ =τmax l=1

where τmax is the highest threshold in T0 . The marginal gain for all elements of Aτ is
sandwiched in the narrow range [τ, (1 + )τ ]. Therefore, we can bound the value of A in
terms of the sizes of Aτ sets and their associated thresholds:
X
X
|Aτ |τ ≤ f (A) ≤ (1 + )
|Aτ |τ.
τ ≥τ ∗

τ ≥τ ∗

By taking the expected value of each side of these bounds, we get:
X
X
E[|Aτ |]τ ≤ E[f (A)] ≤ (1 + )
E[|Aτ |]τ.
τ ≥τ ∗

(3)

τ ≥τ ∗

Each element of Aτ is picked randomly from a set of size d . This means that each of
these elements are deleted with a probability at most . From the submodularity of f , we
know that the marginal gain of elements of A0τ will not decrease after deletion of any other
element. Note that we have A0τ ⊆ Aτ . Therefore, we can lower bound the expected value of
remaining elements, i.e., f (A0 ), similarly:
∗

0

E[f (A )] =

|Aτ |
τ
X
X

0
E[Ieτ,l ∈D
/ ∆f (eτ,l | ∪τ 0 >τ Aτ 0 ∪ {Ieτ,1 ∈D
/ eτ,1 , · · · , Ieτ,l−1 ∈D
/ eτ,l−1 })]

τ =τmax l=1
(a)

≥

τ∗
X

|Aτ |

X

E[Ieτ,l ∈D
/ ∆f (eτ,l | ∪τ 0 >τ Aτ 0 ∪ {eτ,1 , · · · , eτ,l−1 })]

τ =τmax l=1
∗

≥

|Aτ |
τ
X
X

Pr[eτ,l ∈
/ D]τ ≥ (1 − )

X

E[|Aτ |]τ,

(4)

τ ≥τ ∗

τ =τmax l=1

where Ie∈D
/ D. Inequality (a) is concluded from
/ is a binary indicator variable to check e ∈
the submodularity of f . By combining Eqs. (3) and (4), we conclude that:
E[f (A0 ] ≥

1−
E[f (A)] ≥ (1 − 2)E[f (A)].
1+

So far we have proved that the expected value of A0 is not much smaller than the value of
A. We note that by definition A0 is a subset of both Sτ ∗ and A. By submodularity, we have:
f (Sτ ∗ ∪ A) − f (Sτ ∗ ) ≤ f (A) − f (A0 ).
We have shown that the expected value of the right hand side is at most 2E[f (A)] which
completes the proof, since f (A) ≤ f (Sτ ∗ ∪ A) by monotonicity of f .
We have shown that values of Sτ ∗ and Sτ ∗ ∪ A do not differ by much. So we can focus
on lower bounding f (Sτ ∗ ∪ A) in the rest of the proof.
9

Lemma 3 f (Sτ ∗ ∪ A) ≥

(1−)OPT
.
2

Proof The while loop condition in line 7 of Robust-Coreset-Centralized ensures
that there will be at most k elements in A. If A has exactly k elements, its value is at
OPT
least kτ ∗ ≥ 2(1+)
≥ (1−)OPT
, since each element added to A increases its value by some
2
threshold τ ≥ τ ∗ . Monotonicity of f implies that f (Sτ ∗ ∪ A) ≥ f (A) which completes the
proof in this case. Similarly, the claim is proved if Sτ ∗ has k elements. So in the rest of the
proof, we focus on the case |A| < k and |Sτ ∗ | < k.
We define Sτ ∗ ,e to be the subset of Sτ ∗ which is selected by Robust-Centralized
exactly before processing e. We have
(a)

(b)

X

f (S ∗ ) ≤ f (S ∗ ∪ Sτ ∗ ∪ A) ≤ f (Sτ ∗ ∪ A) +

f (e|Sτ ∗ ∪ A)

e∈S ∗ \(Sτ ∗ ∪A)
(c)

≤ f (Sτ ∗ ∪ A) +

X
e∈(S ∗ \(Sτ ∗ ∪A))\B 0

(d)

≤ f (Sτ ∗ ∪ A) + kτ ∗ =⇒

X

f (e|A) +

f (e|Sτ ∗ ,e )

e∈(S ∗ \(Sτ ∗ ∪A))∩B 0

OPT (e)
≤ f (Sτ ∗ ∪ A).
2

Inequality (a) is true because f is monotone. From the submodularity of f we conclude (b).
We have A ⊆ Sτ ∗ ∪ A and Sτ ∗ ,e ⊆ Sτ ∗ ∪ A. Thus (c) results from the submodularity of f .
To prove inequality (d), we first note that the elements e ∈ (S ∗ \ (Sτ ∗ ∪ A)) \ B 0 are
discarded by Robust-Coreset-Centralized. Since A has strictly less than k elements,
they were not discarded because of the cardinality constraint. So, for all of them we have
∆f (e|A) < τ ∗ (low marginal value). Elements e ∈ (S ∗ \ (Sτ ∗ ∪ A)) are not selected by
Robust-Centralized, and cardinality constraint was not the reason for their rejection.
Therefore, for these elements we have f (e|Sτ ∗ ,e ) < τ ∗ .
From the results of Lemmas 2 and 3, we know E[f (Sτ ∗ )] is at least (1−3)OPT
which
2
proves the first claim of this theorem.
The number of thresholds in Robust-Coreset-Centralized is O(log k/). For each
threshold τ , we store at most d/ items in a Bτ set. Also, the maximum number of elements
in {∪Aτ } is k. In addition, we have d + 1 items in Vd . Therefore, the size of core-set returned
by Robust-Coreset-Centralized is at most O k + (d log k)/2 elements. For the query
complexity of Robust-Coreset-Centralized we have: (i) each element is considered for
at most O(log k/) different thresholds, resulting in O ((|V | log k)/) oracle evaluations, and
(ii) when an element is picked from Bτ to be added to Aτ , we should re-calculate marginal
gain of elements and update Bτ resulting in k|V | oracle evaluations since the size of the
union set ∪τ ∈T Aτ never exceeds k. Robust-Centralized
receives the core-set as the input

so it only processes O k + (d log k)/2 elements. Each
of
them
is considered
to be added to


k log k
one of the O(log k/) sets {Sτ }τ ∈T0 which results in O (k + d log
) 
oracle evaluations.
2

10

4.2 Streaming Algorithm
In many applications, the dataset does not fit in the main memory of a single machine or even
the data itself arrives as a stream. So it is not possible to use centralized algorithms which
need random access to the whole data. In this section, we present a streaming algorithm with
a limited available memory. We first use the thresholding idea of Section 4.1 in order to find a
core-set for V. Then we show that it is possible to find a good solution from this core-set when
deletion happens. Recall that for Robust-Coreset-Centralized, the maximum singleton
element and the thresholds are fixed while in the streaming setting, they may change as
new elements arrive. To apply ideas of the centralized algorithm, we should overcome the
following challenges: (i) it is not possible to make several passes over the data for different
thresholds (i.e., we cannot start from the largest possible marginal gain to the lowest), and
(ii) the value of ∆0 and ∆d are not known a priori.
We show (similar to (Badanidiyuru et al., 2014)) that it is possible to maintain a good
approximation of OPT even with a single pass over the data. From now on, let ∆0 and
∆d , respectively, denote the largest and d + 1-th largest singleton values in the stream of
data at time step t. First, note that ∆d ≤ OPT and the marginal gain of all the currently
received elements is at most ∆0 . Therefore, it is enough to consider thresholds in the range
d
[∆
2k , ∆0 ]. A new threshold is instantiated when the maximum singleton element is changed.
These increasing new thresholds are between the current maximum and the previous one.
Therefore, all the elements with marginal gains larger than the new threshold will appear
after its instantiation.
Robust-Coreset-Streaming, for each threshold τ , keeps two sets Aτ and Bτ =
∪τ 0 ≥τ Bτ,τ 0 . All the elements with marginal gains at least τ (marginal gain of an element
e is calculated dynamically by adding e to Aτ , i.e, it is ∆f (e|Aτ )) are good enough to be
picked by this instance of the algorithm. In order to make the selected elements robust to
deletions, we should put all good enough elements in different Bτ,τ 0 sets, with thresholds τ 0
in the range [τ, ∆0 ], based on their marginal values. Whenever a set Bτ,τ 0 becomes large,
we pick one element of it randomly to add to Aτ . This ensures that an element is picked
from a large pool of almost similar elements. Formally, all the elements with a marginal
gain in the range [τ 0 , τ 0 (1 + )) are added to the set Bτ,τ 0 . When the size of a Bτ,τ 0 is at
least d/, we randomly pick an element from Bτ,τ 0 and add it to Aτ . Adding an element
to Aτ may decrease the marginal gains of elements in Bτ,τ 0 sets. So we recompute their
marginal gains and put them in the right Bτ,τ 00 set (they are kept if their marginal gains
are at least τ , otherwise they are discarded). These changes may make another set large,
so we keep adding elements to Aτ while we find a large Bτ,τ 00 set. This process continues
until a maximum of k elements are added to Aτ or the stream of data ends. Note that there
are at most d elements with marginal gains in the range (∆d , ∆0 ]; we can simply keep these
elements (refer to it as set Vd ). For all ∆d < τ ≤ ∆0 , we have Aτ = ∅, because there is no
pool of size at least d/ elements to pick from it. Also, for Bτ,τ 0 sets, we do not need to
cover the range (∆d , ∆0 ] with too many thresholds. Indeed, when ∆d changes (it can only
increase), we can update the set Vd and locate the removed elements from Vd into a correct
d
Bτ,τ 0 . Therefore, it is sufficient to consider only thresholds in the range[ ∆
2k , ∆d ]. The pseudo
code of Robust-Coreset-Streaming is given in Algorithm 3.
11

Algorithm 3: Robust-Coreset-Streaming
1
2
3
4

T = {(1 + e)i |i ∈ Z};
For each τ, τ 0 ∈ T : {Aτ } ← ∅ and {Bτ,τ 0 } ← ∅;
for every arriving element et do
∆d ← the (d + 1)-th largest element of {f {e1 }, · · · , {f {et }}// If t ≤ d + 1, then ∆d
is the smallest singleton value.

5
6
7
8
9
10
11
12

13

14
15
16

∆0 ← the largest element of {f {e1 }, · · · , {f {et }};
∆d
Tt = {(1 + )i | 2(1+)k
≤ (1 + )i ≤ ∆d };
Delete all Aτ and Bτ,τ 0 such the τ or τ 0 ∈
/ Tt ;
for τ ∈ Tt do
if |Aτ | < k and τ ≤ ∆f (e|Aτ ) then
Add et to Bτ,τ 0 such that for τ 0 ≤ ∆f (et |Aτ ) < τ 0 (1 + );
while ∃τ 00 such that |Bτ,τ 00 | ≥ d/ do
Randomly pick an element e from Bτ,τ 00 and add it to Aτ , i.e.,
Aτ ← Aτ ∪
S{e};
For all e ∈ τ 00 ∈Ti ,τ 00 ≥τ Bτ,τ 00 recompute ∆f (e|Aτ ) and re-place them in
correct bins;
for τ ∈ TnSdo
Bτ ← τ 0 ∈Tn ,τ 0 ≥τ Bτ,τ 0 ;
return {Aτ }, {Bτ }

At the end of Robust-Coreset-Streaming, we know there is one running instance of
∗
∗
∗
the algorithm with a threshold τ ∗ such that τ ∗ ≤ OPT
2k < (1+)τ . For all e ∈ V \(Aτ ∪Bτ ),
∗
we have ∆f (e|Aτ ∗ ) < τ . This ensures that the marginal gain of elements that are not picked
0
0
by this running instance are smaller than OPT
2k . Let {Aτ } and {Bτ } be the subsets of {Aτ }
and {Bτ } after the deletion of the set D from V, respectively. The elements of Aτ ∗ are robust
to the deletion, i.e., E[f (A0τ ∗ )] ≥ (1 − 2)E[f (Aτ ∗ )]. Also, all the elements with marginal gain
of at least τ ∗ are kept in the set Bτ0 ∗ . Finally, Robust-Streaming, by adding elements of
Bτ0 ∗ with a marginal gain at least τ ∗ to A0τ ∗ , finds a solution with an expected approximation
guarantee of 1−3
to the optimum solution. The pseudo code of Robust-Streaming is
2
given in Algorithm 4.
Theorem 2 For any δ > 0, by setting  = 2δ
3 , Robust-Coreset-Streaming and RobustStreaming satisfy the following properties:
• Robust-Streaming outputs a set S such that |S| ≤ k and E[f (S)] ≥ ( 12 − δ)OPT.
• Robust-Coreset-Streaming makes one passes over the data.


k
d log2 k
+
elements as the
• Robust-Coreset-Streaming outputs at most O k log
3
δ
δ
core-set. Since this core-set is the input of Robust-Streaming, its space complexity
is upper bounded by the same number of elements.
• The query complexities
and Robust-Streaming
 of Robust-Coreset-Streaming



log k
dk log2 k
d log3 k
are, respectively, O δ |V | + δ3
and O
.
δ4
12

Algorithm 4: Robust-Streaming
Input: {A0τ } and {Bτ0 }// A0τ and Bτ0 contain elements of Aτ and Bτ (outputs of
Robust-Coreset-Streaming) after deletion.
1
2
3
4
5
6
7
8

Output: Set S of cardinality at most k
∆00 ← the largest value of set {f ({e})|e ∈ {∪A0τ } ∪ {∪Bτ0 }};
∆0

0
T0 = {(1 + )i | 2(1+)k
≤ (1 + )i ≤ ∆00 };

for τ ∈ T0 do
Sτ ← A0τ ;
for all e ∈ Bτ0 do
if |Sτ | < k and ∆f (e|Sτ ) ≥ τ then
Sτ ← Sτ ∪ e;
return arg maxτ f (Sτ )

Proof The proof is similar to the proof of Theorem 1. We define V 0 = V \ D. Assume A0τ
and Bτ0 , respectively, are subsets of Aτ and Bτ after deletion of set D from V . We define
S∗ =

arg max f (S) and f (S ∗ ) = OPT.
S⊆V \D,|S|≤k

In our proof, we should consider three points. First, there is a τ ∗ ∈ T0 such that τ ∗ ≤ OPT
2k <
τ ∗ (1 + ). Second, we can show that E[f (A0τ ∗ )] ≥ (1 − 2)E[f (Aτ ∗ )]. Third, all the elements
with enough marginal gain are in the set Bτ0 ∗ and Robust-Centralized will add them to
the final solution.
∆0

0
First Note that ∆00 ≤ OPT ≤ k∆00 and T0 contains all the thresholds in [ 2(1+)k
, ∆00 ]. Also,

∆d ≤ ∆00 ≤ ∆0 . Therefore, there is a threshold τ ∗ such that τ ∗ ≤
in both T0 and Tn .

OPT
2k

< τ ∗ (1 + ) and it is

Second For the threshold τ ∗ , Robust-Coreset-Streaming returns two sets Aτ ∗ and
Bτ ∗ , where Bτ ∗ is the union of sets Bτ ∗ ,τ . Assume Aτ ∗ has nτ ∗ elements and out of these
nτ ∗ elements, nτ ∗ ,τ elements are picked from Bτ ∗ ,τ . This means their marginal gain is in the
range of [τ, τ (1 + )]. We can bound f (Aτ ∗ ) from above by
X
X
nτ ∗ τ τ ≤ f (Aτ ∗ ) ≤ (1 + )
nτ ∗ τ τ
τ ≥τ ∗

τ ≥τ ∗

By taking the expected value of each side of these bounds, we get:
X
X
E[nτ ∗ τ ]τ ≤ E[f (Aτ ∗ )] ≤ (1 + )
E[nτ ∗ τ ]τ
τ ≥τ ∗

(5)

τ ≥τ ∗

We know that an element which is picked at a given step is deleted with a probability at
most . The expected number of elements picked from Bτ ∗ ,τ that remains in the set A0τ (set
Aτ after deletion) is E[n0τ ∗ ,τ ] ≥ (1 − )E[nτ ∗ ,τ ]. Due to the submodularity of f , the marginal
gain of these undeleted elements is at least τ . To sum up, we have
X
E[f (A0τ )] ≥ (1 − )
E[nτ ∗ ,τ ]τ.
τ ≥τ ∗

13

Therefore, we have
E[f (A0τ ∗ )] ≥

1−
E[f (Aτ ∗ )] ≥ (1 − 2)E[f (Aτ ∗ )]
1+

(6)

Let Sτ ∗ denote the set returned by Robust-Streaming for threshold τ ∗ . To prove
E[f (Sτ ∗ )] ≥ ( 12 − 3)OPT, we consider three cases. If |Aτ ∗ | = k, then E[f (Aτ ∗ )] ≥ kτ ∗ ≥
OPT
OPT
and from Eq. (6) we have E[f (Sτ ∗ )] ≥ E[f (A0τ ∗ )] ≥ (1 − 2)E[f (Aτ ∗ ) ≥
2(1+) ≥ (1 − ) 2
(1−3)OPT
.
2
|Sτ ∗ | < k.

The claim is proved similarly if Sτ ∗ has k elements. Let’s assume |Aτ ∗ | < k and

Lemma 4 E[f (Sτ ∗ )] ≥ (1 − 2)E[f (Sτ ∗ ∪ Aτ ∗ )]. Also if |Aτ ∗ | < k and |Sτ ∗ | < k, then
f (Sτ ∗ ∪ Aτ ∗ ) ≥ (1−)OPT
.
2
The proof of this lemma is similar to the proofs of Lemmas 2 and 3 and we skip the details.
To sum-up, for the case |Aτ ∗ | < k, from Lemma 4, we have (1−3)OPT
≤ E[f (Sτ ∗ )]. This
2
concludes the first claim of theorem.
∆d
Number of thresholds in Robust-Coreset-Streaming in the interval [ 2(1+)k
, ∆d ] is
O( log k ). For each τ in this interval, there are O( log k ) sets of Bτ,τ 0 . We store at most d
elements in each of Bτ,τ 0 set. Also, the maximum number of elements in Aτ is k. Also, there
at most d elements with the marginal gain in range (∆d , ∆0 ]. To sum up, Robust-Coreset2
k
k
k
Streaming stores O( log k (k + d log
) + d) = O( k log
+ d log
)) elements. For the time

2
3
complexity of Robust-Coreset-Streaming we have: (i) each element is considered in at
most O( log k ) different thresholds resulting in O( log k |V |) oracle evaluations, and (ii) for each
threshold, when an element is picked from Bτ,τ 0 to be added to Aτ , we should re-calculate
k
marginal gains of all elements in ∪τ 00 ≥τ Bτ,τ 00 resulting in O( dk log
) oracle evaluations. This is
2
k
true because, for each τ , the size of Aτ never exceeds k and we have at most O( d log
) elements
2
in ∪τ 00 ≥τ Bτ,τ 00 . Therefore, the total time complexity of Robust-Coreset-Centralized
2
k
is O( log k |V | + dk log
). Robust-Streaming receives the core-set as the input so it only
3
2

2

k
k
k
processes O( k log
+ d log
) elements. From the input, only O( d log
) elements are in Bτ0 .

3
3
Each of them is considered to be added to one of the O( log k ) sets {Sτ }τ ∈T0 which results in
3

O( d log
4

k

) oracle evaluations.

4.3 Distributed Algorithm
The exponential growth of data makes it difficult to process or even store the data on a
single machine. For this reason, there is an urgent need to develop distributed or parallel
computing methods to process massive datasets. Classical centralized submodular maximization algorithms are sequential in nature; they require access to the whole dataset and are
not amenable to the distributed settings.
Fortunately, there is a simple solution to the problem of distributed submodular maximization within a MapReduce framework (Barbosa et al., 2015). This distributed algorithm first
partitions the data randomly onto m machines. Each machine runs the classical GREEDY
algorithm over its chunk of data and finds a solution. In the second step, the outputs
14

of GREEDY on all machines are collected in a single machine and another instance of
GREEDY is applied to find a new solution. The final solution is the best one among all the
collected answers. Mirrokni and Zadimoghaddam (2015), and Barbosa et al. (2015) proved
that this algorithm provides a solution with a constant factor approximation guarantee. In
this section, we use similar ideas to present a robust distributed submodular maximization
algorithm, called Robust-Distributed. We prove that our distributed algorithm finds an
(α, d)-robust randomized core-set with a constant α and any arbitrary d.
Robust-Distributed is a two-round distributed algorithm. It first randomly partitions
dataset between m machines. Each machine i runs Robust-Coreset-Centralized on
its data and passes the result (i.e., sets {Aiτ } and B i ) to a central machine. After the
deletion of the set D, this single machine runs m instances of Robust-Centralized on
the outputs received from each machine i and finds solutions S i . In addition, it runs the
classical GREEDY1 on the union of sets received from all machines (i.e., union of all sets
0
0
{Aiτ } and B i ) to find another solution T . The final solution is the best answer among T
i
and sets S . Robust-Distributed is outlined in Algorithm 5.
Algorithm 5: Robust-Distributed
1
2
3
4

5

for e ∈ V do
Assign e to a machine i chosen uniformly at random;
Let Vi be the elements assigned to machine i;
Run Robust-Coreset-Centralized (Algorithm 1) on each machine to obtain
{Aiτ } and B i ;
0
0
Run Robust-Centralized (Algorithm 2) on each {Aiτ } and B i to get the set S i of
i0
i0
cardinality at most k from each machine// {Aτ } and B are elements of {Aiτ } and
B i after deletion of set D.

6
7

S ← arg maxS i {f (S i )};
S S
0 S S
0
T ← GREEDY({ i τ ∈Ti Aiτ } { i B i })// Run the GREEDY algorithm over the union
of elements returned by Robust-Coreset-Centralized from all machines.

Ti is the

set of thresholds in machine i.
8

return arg max{f (T ), f (S)}

Theorem 3 For any δ > 0, by setting  = δ/2, Robust-Distributed satisfies the following
properties:
αβ
• It outputs a set S such that |S| ≤ k and E[f (S)] ≥ α+β
OPT, where α = 13 − δ and
β = 1 − 1e . This results in an approximation factor of 0.218 − δ.


k
• Robust-Distributed outputs at most O m(k + d log
)
elements as the core-set,
2
δ
where m is the number of machines.

Corollary 1 Running Robust-Coreset-Centralized on the output core-set
of Robust
Distributed produces a compact core-set of size O k + (d log k/δ 2 ) . Also, Robust1. It could be any other algorithm with a constant factor approximation.

15

Centralized finds a solution with (0.109 − δ)-approximation guarantee from this compact
core-set.
The first part of Corollary 1 is a direct consequence of Theorem 1. The second part results
from the approximation guarantees of Theorems 1 and 3. We refer to this version of our
distributed algorithm as Compact-Distributed. Next, we prove Theorem 3.
Proof In the first round of our algorithm, we randomly distribute the elements of V on m
machines. i.e., independently assigning each element to one of the m machines uniformly at
random. The data assigned to machine i is represented by Vi . We also define V 0 = V \ D
and Vi0 = Vi \ D. Let V 0 (1/m) represent the distribution over random subsets of V 0 where
each element is sampled independently with a probability 1/m.
Lemma 5 The distribution of Vi0 = Vi \ D is identical to V 0 (1/m).
Proof Note that we assume the adversary does not have access to the randomness of our
algorithm. Therefore, all the elements of V \ D are distributed uniformly at random on m
machines.
For the sake of analysis, we assume, in each run of the algorithm, for picking elements from
the pool of Bτ and tie-breaking we have a fixed strict total ordering Π of the elements of V.
The choice of permutation Π is uniformly at random from the symmetric group Sn . Indeed,
we assume Robust-Coreset-Centralized in each round among all the elements with the
marginal gain of [τ, (1 + )τ ) chooses the one with the highest rank in Π. Also, we make a
slight change to the algorithm: when the size of all the elements with marginal gain in a
range [τ, (1 + )τ ) is exactly d , we choose the element with the highest priority in Π and
pass all these elements to the next round (as part of the core-set). In this case, at most
d/ − 1 elements can have a marginal gain in range [τ, (1 + )τ ). So, Robust-CoresetCentralized would consider the next smaller threshold, i.e., elements with marginal gain
τ
in [ 1+
, τ ).
Suppose S ∗ = arg maxS⊆V 0 ,|S|≤k f (S) and f (S ∗ ) = OPT. In addition, let OPTi =
maxS⊂Vi0 ,|S|≤k f (S), i.e., OPTi is the optimum value for the data on machine i. Let’s define
the set Oi , conditioned on the fixed set Vi and the permutation Π, as follows
Oi = {e ∈ S ∗ : e ∈
/ Robust-Coreset-Centralized(Vi ∪ {e})}.
Note that while the output of Robust-Coreset-Centralized is random in general; if
we assume the set Vi and total ordering Π are fixed a priori, then the set Oi is deterministic
also.
Lemma 6 Consider a fixed strict total ordering Π between elements of V. For all e ∈ Oi0 ⊆ Oi
we have
e∈
/ Robust-Coreset-Centralized(Vi ∪ Oi0 ),
and
Robust-Coreset-Centralized(Vi ∪ Oi0 ) = Robust-Coreset-Centralized(Vi ).
16

Proof In the first step, we show that the thresholds for Robust-Coreset-Centralized
on sets Vi ∪ {e} and Vi ∪ Oi0 are equal to thresholds of Robust-Coreset-Centralized
on set Vi . First note that for e ∈ Oi , we have f ({e}) ≤ ∆d . This is true because if
f ({e}) > ∆d , then e is picked by the algorithm as an element of the core-set (as one
of the top d + 1 singleton value elements) and it contradicts with the assumption that
e∈
/ Robust-Coreset-Centralized(Vi ∪ {e}). As ∆0 and ∆d are the same for all sets
Vi , Vi ∪ {e} and Vi ∪ Oi0 , their corresponding thresholds is the same also.
We prove the equality of the output core-sets of Robust-Coreset-Centralized on
these three different sets by induction. For this reason assume, for a threshold τ , the
sets of elements chosen by Robust-Coreset-Centralized on both Vi and Vi ∪ Oi0 are
equal so far. We show that the two instances of algorithm pick exactly the same element
in the next step. Let Bτ and Bτ0 denote the set of all elements with the marginal gain
in the current bucket we are processing from Robust-Coreset-Centralized(Vi ) and
Robust-Coreset-Centralized(Vi ∪ Oi0 ), respectively. We consider two main cases. If
Oi0 ∩ Bτ0 = ∅, then the two sets Bτ and Bτ0 we are processing in the runs of the algorithm are
the same. If their size is strictly less than d , both instances output the set Bτ = Bτ0 as part
of their core-set and consider the next smaller threshold. Therefore the core-sets output by
the two runs of the algorithm will remain the same in this step as well, and the induction
step is proved. Otherwise, there are at least d elements, and the two instances choose the
same element to add to Aτ because they take the element with the highest priority in Π.
Now consider the case Oi0 ∩ Bτ0 = Oi00 6= ∅. We consider two sub-cases in this part. Assume
|Bτ | < d , then for all e ∈ Oi00 there exists at most d − 1 elements in Vi \ Oi with the marginal
gain in the current bucket. This contradicts the fact that e ∈ Oi because for every such e,
the set Bτ ∪ {e} has at most d elements and therefore e will be part of the core-set.
So we can focus on the sub-case |Bτ | ≥ d . Since for every e ∈ Oi00 , element e is not part
of the core-set when added to Vi , there should be some higher priority element in Bτ than
any e ∈ Oi00 . This highest priority element will be picked by both runs of the algorithm.
Therefore the core-sets remain the same in this step of induction as well which completes the
proof.
Next, we bound the marginal gain of elements of Oi versus elements picked from pools of
{Bτi } by Robust-Coreset-Centralized, i.e., set Ai .
Lemma 7 Consider a fixed strict total ordering Π between elements of V. Let Ai denote
the set chosen by Robust-Coreset-Centralized on machine i. For all e ∈ Oi , we have
1. If |Ai | < k then ∆f (e|Ai ) ≤

OPTi
.
2k

2. If |Ai | = k then ∆f (e|Ai ) ≤

(1 + )f (Ai )
(1 + )OPTi
≤
.
k
k

Proof From Lemma 6, we know Robust-Coreset-Centralized on the sets Vi and
Vi ∪ Oi outputs the same sets.
1. From the fact that |Ai | < k, we conclude Robust-Coreset-Centralized has passed
∆d
i
over all the thresholds and has not picked e. So we conclude ∆f (e|Ai ) ≤ 2(1+)k
≤ OPT
2k .
17

2. Denote Ai by {e1 , · · · , e|Ai | }, where ej is the j-th element added to Ai . Also, define
Aj = {e1 , · · · , ej }, i.e., Aj is the first j picked elements of Ai . We have
i

i

f (A ) =

|A |
X

∆f (ej |Aj−1 ),

j=1

where A0 = ∅. We know
(a)

(b)

∆f (e|Ai ) ≤ ∆f (e|Aj−1 ) ≤ (1 + )∆f (ej |Aj−1 )
The inequality (a) is the direct consequence of submodularity of f . We prove (b) by
contradiction. Assume (b) is not true. Then e should have been taken as a part of the
core-set before picking ej , and this contradicts with e being in Oi .
To sum up, we have
|Ai |

1+X
(1 + )OPTi
(1 + )f (Ai )
∆f (e|A ) ≤
≤
.
∆
(e
|A
)
≤
j−1
f j
i
|A |
k
k
i

j=1

The next step is to bound f (Oi ) based on f (Ai ) and OPTi .
Lemma 8 f (Oi ) ≤ f (Ai ) + (1 + )OPTi .
Proof We have
(a)

(b)

f (Oi ) ≤ f (Oi ∪ Ai ) ≤ f (Ai ) +

X

(c)

∆f (e|Ai ) ≤ f (Ai ) + (1 + )OPTi .

e∈Oi

Inequality (a) drives from the monotonicity of f . Inequality (b) is true because Oi ∩ Ai = ∅
and f is submodular. Inequality (c) is true from the result of Lemma 7 and the fact that
|Oi | ≤ k.
Now, we can bound the expected value of f (Oi ) by the expect value of f (S i ), where S i is
0
the result of Robust-Centralized from the core-set of machine i. Assume set Ai consists
of elements of Ai after deletion. We have
(a)

EΠ [f (Oi )] ≤ EΠ [Ai ] + (1 + )OPTi
0

(1 + )EΠ [Ai ]
+ (1 + )OPTi
1−
(c) (1 + )E [f (S i )]
Π
≤
+ (1 + )OPTi →
1−
(b)

≤

(d)
1
( − 2)EΠ [f (Oi )] ≤ EΠ [f (S i ))]
3

18

Inequalities (a) and (b) are directly from the results of Lemma 8 and Lemma 2. We know
Ai ⊆ S i and inequality (c) concludes from the monotonicity of f . Theorem 1 guarantees
that Robust-Coreset-Centralized outputs a ( 1−3
2 , d)-robust randomized core-set. This
)OPT
≤
EΠ [f (S i )]. Inequality (d) results from
ensures that, for every ground set Vi , ( 1−3
i
2
this fact.
We note that the only randomness properties we need in Lemma 2 and Theorem 1 are
to ensure each added element to an A set has a probability of deletion of at most  with
linearity of expectation. With the Π based implementation of this randomness, we achieve
these properties.
In the last step, we prove the approximation guarantee of Robust-Distributed. Define
vector p such that for e ∈ V , we have

PA∼V(1/m) [e ∈ Robust-Centralized(A ∪ {e})] if e ∈ S ∗ ,
pe =
0
otherwise.
Lemma 9 For α =

1
3

− 2 and β = 1 − 1e , we have

E[f (S i )] ≥ αE[f (Oi )] ≥ αf − (1S ∗ − p)
0

0

E[f (T )] ≥ βE[f (S ∗ ∩ ({∪i ∪τ ∈Ti Aiτ } ∪ {∪i B i })] ≥ βf − ((p)),
where f − is the Lovász extension of function f .
Proof The proof of this lemma is similar to the proof of (Barbosa et al., 2015, Theorem 5).
Let Z denote the set returned by Robust-Distributed. From Lemma 9, we have
E[f (Z)] ≥ E[f (S i )] ≥ αf − (1S ∗ − p)
−

E[f (Z)] ≥ E[f (T )] ≥ βf (p)

(7)
(8)

From the result of Eqs. (7) and (8) we have
(a)

(β + α)E[f (Z)] ≥ αβ(f − (1S ∗ − p) + f − ((p))) ≥ αβf − (1S ∗ ) = αβf (S ∗ ).
In inequality (a), we use the convexity of Lovász extension and (Barbosa et al., 2015,
Lemma 1). This proves the first part of theorem.
From Theorem 1, we know that the size of core-set for an instance of Robust-Coresetk
Centralized is O(k + d log
). Therefore, the size of core-set for Robust-Distributed is
2
at most m times of this value.

5. Experimental Results
In this section, we extensively evaluate the performance of our algorithms on several publicly
available real-world datasets. We consider algorithms that can be robust to the deletion of
any number of items and return k elements after deletion. Unfortunately, both OSU (Orlin
et al., 2016) and Pro-Greedy (Bogunovic et al., 2017) are robust to the deletion of only
o(k) items. For this reason, we compare our proposed methods with two other baselines:
19

(i) the deletion-robust algorithm designed by Mirzasoleiman et al. (2017) (we refer to it by
Robust), and (ii) the stochastic greedy algorithm (Mirzasoleiman et al., 2015) (SG), where
we first obtain a solution S of size r = 6k (we set r > k to make the solution robust to
deletion), and then we report GREEDY(S \ D) as the final answer. In our evaluations, we
consider the effect of three different parameters: (i) an algorithm is designed to be robust to
deletion of d elements; (ii) cardinality constraint k of the final solution; and (iii) number of
deleted elements r. The final objective value of all algorithms are normalized to the utility
obtained from a classical greedy algorithm that knows the set of deleted items D beforehand.
Note that we are able to guarantee the performance of our algorithms (also this is true
for Robust (Mirzasoleiman et al., 2017)) only when the number of deletions r is less than
d. In these experiments, we are also interested in evaluating the effect of larger number of
deletions, i.e., for of r  d.
5.1 Location Privacy
In a wide range of applications, the data can be represented as a kernel matrix K, which
encodes the similarity between different items in the database. In order to find a representative
set S of cardinality k, a common object function is
f (S) = log det(I + αKS,S ),

(9)

where KS,S is the principal sub-matrix of K indexed by S and α > 0 is a regularization
parameter (Herbrich et al., 2003; Seeger, 2004; Krause and Guestrin, 2005). This function is
monotone submodular.
In this section, we analyze a dataset of 10,000 geolocations. Each data entry is longitude
and latitude coordinates of Uber pickups in Manhattan, New York in April 2014 (UberDataset,
2016). Our goal is to find k representative samples using objective function described in
Eq. (9). The similarity of two location samples i and j is defined by a Gaussian kernel
Ki,j = exp(−d2i,j /h2 ), where the distance di,j (in meters) is calculated from the coordinates
and h is set to 5000. We set d = 5, i.e., we make algorithms (theoretically) robust to deletion
of at most five elements. To compare the effect of deletion of r = |D| elements on the
performance of algorithms,2 we use two deletion strategies to select these items: (i) classical
greedy algorithm, and (ii) the stochastic greedy algorithm.
In the first experiment, we study the effect of deleting different number of items on the
normalized objective values. In order to refer to an algorithm with a specific deletion strategy,
we use the name of algorithm followed by the deletion strategy, e.g., Rob-Stream-G refers to
Robust-Streaming where the deleted items are picked by greedy strategy. From Fig. 1a, we
observe that Robust-Streaming and Robust-Centralized are more robust to deletion
than Robust and SG. The effect of deleting by greedy strategy on the performance of
algorithms is more pronounced than SG strategy. It can be seen that, even by deleting
more than d = 5 items, our algorithms maintain their performance. Also, SG (which is not
designed to be robust to deletions) shows the worst performance. Other than normalized
objective values, the memory requirement of each algorithm is quite important. Indeed, we
are interested in deletion-robust algorithms that do not keep many items. Fig. 1b compares
the memory complexity of algorithms. We observe that Robust-Centralized needs to
2. Note that in practice r could be any number larger than d.

20

Rob-Cent-G
Rob-Stream-G
Robust-G
Rob-Cent-SG
Rob-Stream-SG
Robust-SG

8000

0.975

Memory complexity

Normalized objective value

1.000

0.950
0.925
0.900
0.875

Rob-Cent-G
Rob-Stream-G
Robust-G
SG-G

0.850
0.825
0

25

50

Rob-Cent-SG
Rob-Stream-SG
Robust-SG
SG-SG

75

100

125

150

6000

4000

2000

0

175

200

5

10

Number of deletions

20

30

40

Cardinality constraint

(a) We set d = 5 and k = 20.

(b) We set d = 5 and r = 100.

Figure 1: Uber dataset: (a) effect of deletion on the performance of algorithms with respect
two different deletion strategies; (b) memory complexity of robust algorithms for different
cardinality constraints.
keep the least number of items. For Robust algorithm, the memory complexity increases
super linear in k (it is O(k log k)), which makes it quite impractical for large values of k
and d. To sum-up, we observe that our proposed algorithms provide the best of two worlds:
while their normalized objective values are clearly better than other baselines, they need to
keep much fewer number of items.
5.2 Submodular Feature Selection
One of the challenges in learning from high dimensional data is to select a subset of relevant
features in a computationally feasible way. For this reason, the quality of a subset of features
S can be captured by the mutual information between attributes in S and the class variable
Y (Krause and Guestrin, 2005). More specifically,
I(Y ; XS ) =

X X


p(x, y) log2

y∈Y x∈XS

p(x, y)
p(x)p(y)


,

where XS is a random variable that represents the set S of k features. The joint distribution
on (Y,
Q X1 , · · · , Xk ), under the Naive Bayes assumption, is defined by p(y, x1 , · · · , xk ) =
p(y) ki=1 p(xi |y). This assumption makes the computation of joint distribution tractable.
In our experiments, we estimate each p(xi |y) by counting frequencies in the dataset. In the
feature selection problem, the goal is to choose k features such that maximizing f (S) =
I(Y ; XS ). It is known that the function f (S) = I(Y ; XS ), under the Naive Bayes assumption,
is monotone submodular (Krause and Guestrin, 2005).
In this section, we use this feature selection method on two real datasets. We first show
that our robust algorithms, after the deletion of sensitive features,3 provide results with near
3. Features that might cause unfairness in the final classifier.

21

1.0

Normalized objective value

Normalized objective value

1.0

0.9

0.8

0.7

0.6

Rob-Cent, k = 10
Rob-Stream, k = 10
Robust, k = 10
SG, k = 10

0.5

Rob-Cent, k = 5
Rob-Stream, k = 5
Robust, k = 5
SG, k = 5

0.8

0.6

0.4
Rob-Cent, k = 5
Rob-Stream, k = 5
Robust, k = 5
SG, k = 5

0.2

Rob-Cent, k = 4
Rob-Stream, k = 4
Robust, k = 4
SG, k = 4

0.0
0

5

10

15

20

0

5

Number of deletions

10

15

20

Number of deletions

(a) Adult Income

(b) Crime and Communities

Figure 2: The effect of deletion on the performance of different algorithms for feature selection.
We set d = 3
optimal quality (based on mutual information). Second, we demonstrate that classifiers that
are trained on these selected features perform very well. In our experiments, we set d = 3.
5.2.1 Fairness in Income Prediction
In this set of experiments, we use the Adult Income dataset from UCI Repository of machine
learning databases (Blake and Merz, 1998). This dataset contains information about 32,561
individuals and whether income of those individuals is over 50K a year. We extract 113
binary features from this dataset. The goal of the classification task is to predict the income
status of 16,281 test cases. For the deletions, we remove sensitive features that might result
in the unfairness, e.g., features about sex, race, nationality, marital status and relationship
status.
Fig. 2a compares algorithms based on different number of deletions for k = 5 and k = 10.
We observe that for both values of k, Robust-Centralized considerably outperforms
Robust (Mirzasoleiman et al., 2017) and SG. Also, the performance of Robust is better
than SG.
To further investigate the effect of deletions, we compare accuracy of different classifiers,
where each is trained on the features found by our algorithms and other baselines. We train
two type of classifiers: (i) Naive Bayes (Zhang, 2004) and (ii) SVM (Smola and Schölkopf,
2004). From Table 2, we observe that a SVM classifier, which is trained over all features,
results in an accuracy of 83.0%. If we use a greedy algorithm to find the best 5 features and
train SVM classifier on those features, the accuracy will drop to 79.6%.4 After deleting 10
features that might result in unfairness in classification (e.g., race and sex), we again use the
greedy algorithm to find the best five features (referred to as GREEDYD ). The accuracy in
this case is 79.3%. Also, interestingly, we observe that the accuracies of classifiers which are
trained on the features found by Robust-Centralized and Robust-Streaming drop only
by 0.2%. Furthermore, for the Naive Bayes classifier, we do not observe any decrease on the
4. Clearly there is a trade off between the number of features and accuracy.

22

Table 2: The comparison of different classifiers (Naive Bayes and SVM for Adult Income
dataset and RIDGE for Crime and Communities dataset). Ten sensitive features are deleted.
The number of stored features is reported in parenthesis.
Algorithm
All features
GREEDY
GREEDYD
Rob-Cent
Rob-Stream
Robust

Naive Bayes (Acc.)

SVM (Acc.)

RIDGE (RMSE)

0.798
0.788
0.781
0.781 (22)
0.781 (29)
0.779 (39)

0.830
0.796
0.793
0.791
0.791
0.788

0.136
0.193
0.199
0.163 (25)
0.177 (52)
0.197 (58)

accuracy when we train on the features found by our algorithms. Finally, both Centralized
(22) and Streaming (29) algorithms need to keep fewer number of items than Robust (39).
5.2.2 Fairness in Crime Rate Prediction
In the second experiment for robust feature selection, we use the Communities and Crime
dataset from UCI Repository of machine learning databases (Blake and Merz, 1998). This
dataset consist of 122 features with plausible connection to crime in communities within
the United States. The crime rate is provided as the per capita violent crimes. In this
experiment, we delete sensitive features such as distribution of race and sex in population
and police forces. Fig. 2b compares normalized objective values for k ∈ {4, 5} and different
number of deletions. Again, we observe that our centralized and streaming algorithms have
the best performances. We should point out that the parameter d can also play an important
role in practice. Indeed, since all algorithms are made robust to deletion of d = 3 elements,
the performance of Robust (Mirzasoleiman et al., 2017) hugely decreases with only r = 4
deletions, while our algorithms maintain their near optimal performances.
To assess the quality of selected features, we use a RIDGE regression classifier (Hoerl
and Kennard, 1970). The RMSE for a classifier that is trained on all features is 0.136. For
classifiers trained on features selected by GREEDY and GREEDYD , the errors increase
to 0.193 and 0.199, respectively. The errors for centralized (0.163) and streaming (0.177)
algorithms are even less than the greedy algorithm which knows the deleted features in
advance. This might be due to the fact that only our proposed methods select features related
to the percentage of divorced males and females as important attributes. It is plausible that
these attributes can have high correlations with crime rate.
5.3 Distributed Algorithm and Massive Data Summarization
To evaluate the performance of Robust-Distributed on massive datasets, we consider the
Census1990 dataset from UCI Repository of machine learning databases (Blake and Merz,
1998). This dataset is consists of 2,458,285 data points with 68 features. We are going to
find k representative samples from this large dataset. We apply the set selection objective
function described in Eq. (9). The similarity between two entries x and x0 is defined by
0k
√
1 − kx−x
, where kx − x0 k is the Euclidean distance between feature vectors of x and x0 .
68
23

1.10
Robust-Distributed
SG-Distributed

1.08

Normalized objective value

Normalized objective value

1.04
1.02
1.00
0.98
0.96
0.94
0.92

Robust-Distributed
SG-Distributed

1.06
1.04
1.02
1.00
0.98
0.96
0.94

0.90
D1

D2

D3

D1

D4

D2

D3

D4

Deletion strategy

Deletion strategy

(a) k = 50

(b) k = 100

Figure 3: Census1990 dataset: Robust-Distributed versus SG-Distributed for four
different deleting strategies.
We randomly split the dataset into m = 12 partitions. For each instance of RobustCoreset-Centralized, we set d = 25 with an  = 0.1. As a baseline, we consider a
distributed version of stochastic greedy algorithm (refer to it as SG-Distributed). For this
algorithm, we first run stochastic greedy on each partitions to select Si = 6k items. After
deletion of D, we report f (GREEDY(∪Si \ D)) as the final result. Also, we normalize the
utility of functions to the objective value of an instance of SG-Distributed that knows the
set of deleted items D in advance. For deletions, we propose four different strategies: D1
randomly deletes 50% of items, D2 randomly deletes 80% of items, D3 deletes all men in the
dataset, and D4 deletes all women in the dataset.
We investigate the effect of different deletion strategies for two values of k ∈ {50, 100}.
In Figs. 3a and 3b, we observe that Robust-Distributed clearly outperforms SGDistributed in all cases. Furthermore, we observe that the objective value of RobustDistributed in all scenarios is even better than our reference function for normalization
(normalized objective values are larger than 1). Each machine on average stores 209.3 (for
k = 50) and 348.3 (for k = 100) items. The standard deviations of memory complexities
are 36.9 and 26.5, respectively. To conclude, Robust-Distributed enables us to robustly
summarize a dataset of size 2,458,285 with storing only ≈4500 items. Our experimental
results confirm that this core-set is robust to the deletion of even 80% of items.

6. Conclusion
In this paper, we considered the problem of deletion-robust submodular maximization. We
provided the first scalable and memory-efficient solutions in different optimization settings,
namely, centralized, streaming, and distributed models of computation. We rigorously
proved that our methods enjoy constant factor approximations with respect to the optimum
algorithm that is also aware of the deleted set of elements. We showcased the effectiveness of
our algorithms on real-word problems where part of data should be deleted due to privacy
and fairness constraints.
24

References
Francis Bach et al. Learning with submodular functions: A convex optimization perspective.
Foundations and Trends R in Machine Learning, 6(2-3):145–373, 2013.
Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause.
Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data
mining, pages 671–680. ACM, 2014.
Rafael Barbosa, Alina Ene, Huy Nguyen, and Justin Ward. The power of randomization:
Distributed submodular maximization on massive datasets. In International Conference
on Machine Learning, pages 1236–1244, 2015.
Dimitris Bertsimas, David B Brown, and Constantine Caramanis. Theory and applications
of robust optimization. SIAM review, 53(3):464–501, 2011.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications
when adversarially learning fair representations. arXiv preprint arXiv:1707.00075, 2017.
Catherine L Blake and Christopher J Merz. Uci repository of machine learning databases
[http://www. ics. uci. edu/˜ mlearn/mlrepository. html]. irvine, ca: University of california.
Department of Information and Computer Science, 55, 1998.
Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher. Robust submodular maximization: A non-uniform partitioning approach. pages 508–516, 2017.
Allan Borodin, Aadhar Jain, Hyun Chul Lee, and Yuli Ye. Max-sum diversification, monotone
submodular functions, and dynamic updates. ACM Transactions on Algorithms (TALG),
13(3):41, 2017.
Niv Buchbinder, Moran Feldman, and Roy Schwartz. Online submodular maximization
with preemption. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 1202–1216. Society for Industrial and Applied Mathematics,
2015.
Jennifer T. Chayes. How Machine Learning Advances Will Improve the Fairness of Algorithms. https://www.huffingtonpost.com/entry/how-machine-learning-advanceswill-improve-the-fairness_us_599d8de8e4b056057bddcfc3, 2017. Accessed: 2017-1031.
Moran Feldman, Christopher Harshaw, and Amin Karbasi. Greed is good: Near-optimal
submodular maximization via greedy optimization. In Satyen Kale and Ohad Shamir,
editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings
of Machine Learning Research, pages 758–784, Amsterdam, Netherlands, 07–10 Jul 2017.
PMLR.
Amir Globerson and Sam Roweis. Nightmare at test time: Robust learning by feature
deletion. In Proceedings of the 23rd International Conference on Machine Learning,
25

ICML ’06, pages 353–360, New York, NY, USA, 2006. ACM. ISBN 1-59593-383-2. doi:
10.1145/1143844.1143889. URL http://doi.acm.org/10.1145/1143844.1143889.
Xinran He and David Kempe. Robust influence maximization. In Proceedings of the 22Nd
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD
’16, pages 885–894, New York, NY, USA, 2016. ACM. ISBN 978-1-4503-4232-2.
Ralf Herbrich, Neil D Lawrence, and Matthias Seeger. Fast sparse gaussian process methods:
The informative vector machine. In Advances in neural information processing systems,
pages 625–632, 2003.
Arthur E Hoerl and Robert W Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55–67, 1970.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through
a social network. In Proceedings of the ninth ACM SIGKDD international conference on
Knowledge discovery and data mining, pages 137–146. ACM, 2003.
Andreas Krause and Ryan G Gomes. Budgeted nonparametric learning from data streams.
In Proceedings of the 27th International Conference on Machine Learning (ICML-10),
pages 391–398, 2010.
Andreas Krause and Carlos Guestrin. Near-optimal nonmyopic value of information in
graphical models. In UAI ’05, Proceedings of the 21st Conference in Uncertainty in
Artificial Intelligence, Edinburgh, Scotland, July 26-29, 2005, pages 324–331, 2005.
Andreas Krause, H Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Robust
submodular observation selection. Journal of Machine Learning Research, 9(Dec):2761–
2801, 2008.
Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani. Fast greedy
algorithms in mapreduce and streaming. ACM Transactions on Parallel Computing, 2(3):
14, 2015.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In
Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics:
Human Language Technologies - Volume 1, HLT ’11, pages 510–520, Stroudsburg, PA,
USA, 2011. Association for Computational Linguistics. ISBN 978-1-932432-87-9. URL
http://dl.acm.org/citation.cfm?id=2002472.2002537.
Mario Lucic, Olivier Bachem, Morteza Zadimoghaddam, and Andreas Krause. Horizontally
scalable submodular maximization. In ICML, pages 2981–2989, 2016.
Vahab Mirrokni and Morteza Zadimoghaddam. Randomized composable core-sets for
distributed submodular maximization. In Proceedings of the forty-seventh annual ACM
symposium on Theory of computing, pages 153–162. ACM, 2015.
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed
submodular maximization: Identifying representative elements in massive data. In Advances
in Neural Information Processing Systems, pages 2049–2057, 2013.
26

Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and
Andreas Krause. Lazier than lazy greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 1812–1818,
2015. URL http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9956.
Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Deletion-robust submodular
maximization: Data summarization with “the right to be forgotten”. In International
Conference on Machine Learning, pages 2449–2458, 2017.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical Programming, 14(1):
265–294, 1978.
James B Orlin, Andreas S Schulz, and Rajan Udwani. Robust monotone submodular function
maximization. In International Conference on Integer Programming and Combinatorial
Optimization, pages 312–324. Springer, 2016.
Matthias Seeger. Greedy forward selection in the informative vector machine. Technical
report, Technical report, University of California at Berkeley, 2004.
Adish Singla, Sebastian Tschiatschek, and Andreas Krause. Noisy submodular maximization
via adaptive sampling with applications to crowdsourced image collection summarization.
In AAAI, pages 2037–2043, 2016.
Alex J Smola and Bernhard Schölkopf. A tutorial on support vector regression. Statistics
and computing, 14(3):199–222, 2004.
UberDataset. https://www.kaggle.com/fivethirtyeight/uber-pickups-in-new-yorkcity, 2016. Accessed: 2017-10-31.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active
learning. In Proceedings of the 32nd International Conference on Machine Learning
(ICML-15), pages 1954–1963, 2015.
Yisong Yue and Carlos Guestrin. Linear submodular bandits and their application to
diversified retrieval. In Advances in Neural Information Processing Systems, pages 2483–
2491, 2011.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair
representations. In Proceedings of the 30th International Conference on Machine Learning
(ICML-13), pages 325–333, 2013.
Harry Zhang. The optimality of naive bayes. AA, 1(2):3, 2004.

27

