figures/environments figures/macros

# Deletion Robust Non-Monotone Submodular Maximization over Matroids

Paul Dütting Google Research. Email: {duetting, ashkannorouzi, silviol,
<EMAIL_ADDRESS>Federico Fusco Department of Computer, Control, and
Management Engineering “Antonio Ruberti”, Sapienza University of Rome, Italy.
Email<EMAIL_ADDRESS>Part of this work was done while Federico was
an intern at Google Research, hosted by Paul Dütting. Silvio Lattanzi∗ Ashkan
Norouzi-Fard∗ Morteza Zadimoghaddam∗

###### Abstract

Maximizing a submodular function is a fundamental task in machine learning and
in this paper we study the deletion robust version of the problem under the
classic matroids constraint. Here the goal is to extract a small size summary
of the dataset that contains a high value independent set even after an
adversary deleted some elements. We present constant-factor approximation
algorithms, whose space complexity depends on the rank $k$ of the matroid and
the number $d$ of deleted elements. In the centralized setting we present a
$(4.597+O(\eps))$-approximation algorithm with summary size
$O(\frac{k+d}{\eps^{2}}\log\frac{k}{\eps})$ that is improved to a
$(3.582+O(\eps))$-approximation with
$O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps})$ summary size when the objective is
monotone. In the streaming setting we provide a
$(9.435+O(\eps))$-approximation algorithm with summary size and memory
$O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps})$; the approximation factor is then
improved to $(5.582+O(\eps))$ in the monotone case.

##  1 Introduction

Submodular maximization is a fundamental problem in machine learning that
encompasses a broad range of applications, including active learning
(GolovinK11) sparse reconstruction (Bach10; DasK11; DasDK12), video analysis
(ZhengJCP14), and data summarization (lin-bilmes-2011-class; BairiIRB15).

Given a submodular function $f$, a universe of elements $V$, and a family
$\mathcal{F}\subseteq 2^{V}$ of feasible subsets of $V$, the optimization
problem consists in finding a set $S\in\mathcal{F}$ that maximizes $f(S)$. A
natural choice for $\mathcal{F}$ are capacity constraints (a.k.a. $k$-uniform
matroid constraints) where any subset $S$ of $V$ of size at most $k$ is
feasible. Another standard restriction, which generalizes capacity constraints
and naturally comes up in a variety of settings, are matroid constraints. As
an example where such more general constraints are needed, consider a movie
recommendation application, where, given a large corpus of movies from various
genres, we want to come up with a set of recommended videos that contains at
most one movie from each genre.

Exact submodular maximization is a NP-hard problem, but efficient algorithms
exist that obtain small constant-factor approximation guarantees in both the
centralized and in the streaming setting (e.g., fisher78-II; CalinescuCPV11;
BuchbinderF19; ChakrabartiK15; FeldmanK018).

In this work we design algorithms for submodular optimization over matroids
that are robust to deletions. A main motivation for considering deletions are
privacy and user preferences. For example, users may exert their “right to be
forgotten” or may update their preferences and thus exclude some of the data
points. For instance, in the earlier movie recommendation example, a user may
mark some of the recommended videos as “seen” or “inappropriate,” and we may
wish to quickly update the list of recommendations.

###  1.1 The Deletion Robust Approach

Following MitrovicBNTC17, we model robustness to deletion as a two phases game
against an adversary. In the first phase, the algorithm receives a robustness
parameter $d$ and chooses a subset $W\subseteq V$ as summary of the whole
dataset $V$. Concurrently, an adversary selects a subset $D\subseteq V$ with
$|D|\leq d$. The adversary may know the algorithm but has no access to its
random bits. In the second phase, the adversary reveals $D$ and the algorithm
determines a feasible solution from $W\setminus D$. The goal of the algorithm
is to be competitive with the optimal solution on $V\setminus D$. Natural
performance metrics in this model are the algorithm’s approximation guarantee
and its space complexity as measured by the size of the set $W$. We consider
this problem in both the centralized and in the streaming setting. The
adversary studied is called oblivious, as its choice of the deleted elements
$D$ does not depend on the realized $W$, but possibly on the structure of the
algorithm (not on its random bits). This is a natural assumption in the
applications. Consider the movie recommendation example: the fact that a movie
has already been watched by the user or that it is deemed inappropriate is
independent of the fact that the specific movie has been selected or not in
the summary.

In this model, to obtain a constant-factor approximation, the summary size has
to be $\Omega(k+d)$, even when $f$ is additive and the constraint is a
$k$-uniform matroid. To see this, consider the case where exactly $k+d$ of the
elements have unitary weight and the remaining elements have weight zero. The
adversary selects $d$ of the valuable elements to be deleted, but the
algorithm does not know which. To be protective against any possible choice of
the adversary, the best strategy of the algorithm is to choose $W$ uniformly
at random from the elements that carry weight. This leads to an expected
weight of the surviving elements of $|W|\cdot k/(k+d)$, while the optimum is
$k$.

Prior work gave deletion robust algorithms for the special case of $k$-uniform
matroids and monotone objective. The state-of-the-art is a $2+O(\eps)$
approximation with $O(k+\frac{d\log k}{\eps^{2}})$ space in the centralized
setting, while in the streaming setting the same approximation is achievable
at the cost of an extra multiplicative factor of $O(\frac{\log k}{\eps})$ in
space complexity (KazemiZK18).

For general matroids, MirzasoleimanK017 give a black-box reduction that adapts
(non-robust) submodular optimization algorithms to the deletion robust
setting. Their approach yields a $3.147$-approximation algorithm for monotone
objectives using Ashkan21 and a $5.205$ approximation for non-monotone
objectives via BuchbinderF19. The downside of MirzasoleimanK017 is that the
space complexity is $\tilde{O}(kd)$.111Where the $\tilde{O}$ notation hides
logarithmic factors. The multiplicative factor $d$ is inherent in the
construction, and the $k$ is needed in any subroutine, so this approach
necessarily leads to a space complexity of $\Omega(dk)$. The main open problem
from their work is to design _space-efficient_ algorithms for the respective
problems. This question is important in many practical scenarios where
datasets are large and space is an important resource.

Reference | Objective | Model | Approximation | Summary size
---|---|---|---|---
cor:centralized_nonmonotone (this work) | Non-Monotone | Centralized | $4.597+O(\eps)$ | $O\big{(}\frac{k+d}{\eps^{2}}\log k\big{)}$
cor:centralized_monotone (this work) | Monotone | Centralized | $3.582+O(\eps)$ | $O\big{(}k+\frac{d}{\eps^{2}}\log k\big{)}$
MirzasoleimanK017 | Non-Monotone | Streaming | $5.205$ | $\tilde{O}(kd)$
thm:robust-streaming (this work) | Non-Monotone | Streaming | $9.435+O(\eps)$ | $O\big{(}k+\frac{d}{\eps^{2}}\log k\big{)}$
MirzasoleimanK017 | Monotone | Streaming | $3.147$ | $\tilde{O}(kd)$
cor:streaming (this work) | Monotone | Streaming | $5.582+O(\eps)$ | $O\big{(}k+\frac{d}{\eps^{2}}\log k\big{)}$
Zhang22 | Monotone | Streaming | $4$ | $O(k+d)$
Table 1: The table summarizes the results for deletion robust submodular
maximization with matroid constraints. Note that the $\tilde{O}$ hides terms
poly-logarithmic in the rank $k$. The approximation guarantees of
MirzasoleimanK017 are obtained via the state-of-the-art streaming algorithms
for submodular maximization with matroid constraints (BuchbinderF19 and
Ashkan21).

###  1.2 Our Results

We present the first constant-factor approximation algorithms for deletion
robust submodular maximization subject to general matroid constraints with
almost optimal space usage, i.e., our algorithms only use $\tilde{O}(k+d)$
space. More formally, in the centralized setting we present a
$(4.597+O(\eps))$-approximation algorithm with summary size
$O(\frac{k+d}{\eps^{2}}\log\frac{k}{\eps})$, that can be improved to a
$(3.582+O(\eps))$-approximation with summary size
$O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps})$ if the objective is monotone. In
the streaming setting we provide a $(9.435+O(\eps))$-approximation algorithm
with summary size and memory $O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps})$, that
becomes a $(5.582+O(\eps))$-approximation if the objective is monotone. We
remark that, besides the black box results by MirzasoleimanK017 that have a
far-from-optimal space usage, we are the first to offer a positive result for
non-monotone submodular functions in the deletion robust setting, with any
type of constraint. All our results are summarized and compared to the
existing literature in table:our_results.

For monotone objectives the constants in the two cases are $2+\beta$ and
$4+\beta$, where $\beta$ is $e/(e-1)\approx 1.582$, i.e., the best-possible
approximation guarantee for the standard centralized problem (CalinescuCPV11;
Feige98). For the non-monotone case we still have a $2+\beta$, where
$\beta\approx 2.597$ is the state-of-the-art approximation guarantee for non-
robust centralized submodular maximization subject to matroid constraint
(BuchbinderF19); our approximation for the streaming setting also depends on
the routine used, but in a more intricate way. The result of BuchbinderF19 are
not known to be tight, thus better algorithms may exist and would
automatically improve our approximation guarantees.

We point out that the state-of-the-art approximation guarantees for (non-
robust) submodular maximization with matroid constraint in the streaming model
are $3.147$-approximation in the monotone case and a $5.205$-approximation in
the general non-negative, i.e. possibly non-monotone, case (Ashkan21). The
“price of robustness” is thus just an extra small additive term in the
approximation factor, depending on the setting. At the same time, up to
possibly a logarithmic factor, the memory requirements of all our results are
tight.

###  1.3 Our Techniques

Intuitively, the extra difficulty in obtaining space-efficient robust deletion
summaries with general matroid constraints is that the algorithm can only use
elements respecting the matroid constraint to replace a good deleted element
from a candidate solution. This issue gets amplified when multiple elements
need to be replaced. This is in sharp contrast to the specal case of
$k$-uniform matroids where all elements can replace any other element.

Our algorithms start by setting a logarithmic number of value thresholds that
span the average contribution of relevant optimum elements, and use these to
group together elements with similar marginal value. The candidate solution is
constructed using only elements from bundles that are large enough (at least a
factor of $1/\eps$ larger than the number of deletions). Random selection from
a large bundle protects/insures the value of the selected solution against
adversarial deletions. In the centralized algorithm, it is possible to sweep
through the thresholds in decreasing order. This monotonic iteration helps us
design a charging mechanism for high value optimum elements dismissed due to
the matroid constraint. We use the matroid structural properties to find an
injective mapping from optimum elements rejected by the matroid property to
the set of selected elements. Given the monotonic sweeping of thresholds, the
marginal value of missed opportunities cannot dominate the values of added
elements. Finally, since each fixed element of the base set has very low
probability to be added to the solution (due to the deletion robust sampling),
we can handle for free the non-monotonicity of the objective in the analysis
via a well known sampling argument for submodular functions (FeigeMV07).

In the streaming setting, elements arrive in an arbitrary order in terms of
their membership to various bundles. So we keep adding elements as long as a
large enough bundle exists. Addition of elements from lower value bundles
might technically prevent us from selecting some high value elements due to
the matroid constraint. So when considering a new element, we allow for a swap
operation with any of the elements in the solution to maintain feasibility of
the matroid constraint. We perform the swap if the marginal value of the new
element $e$ is substantially (a constant factor) higher than the marginal
value that the element $e^{\prime}$ we are kicking out of the solution had
when it was added to the solution. The constant factor gap between marginal
values helps us account for not only $e^{\prime}$ but also the whole potential
chain of elements that $e^{\prime}$ caused directly or indirectly to be
removed in the course of the algorithm. As we repeatedely swap elements in and
out the solution, it no longer holds that each fixed elements of the base set
has very low probability to be, at some point, added to the solution. To
tackle non-monotonicity, we embed a uniform sampling step in the procedure
outlined above (as in, e.g., FeldmanK018; AmanatidisFLLMR21;
AmanatidisFLLR22): any new element is discarded with some fixed probability
before even being considered for swapping.

Finally, a consideration on the deletion robust parameter $d$. Our algorithms
(just like the algorithms from earlier work) do not need exact knowledge of
$d$; an upper bound on it yields the same approximation, at the cost of a
larger summary. Also, with some extra work, it is possible to show that our
approximation guarantees degrade gracefully when the estimate of $d$ was too
conservative and there were actually more deletions. Note that some prior
knowledge on $d$ is a reasonable assumption in the applications and that
without any prior information about $d$ it is provably impossible to achieve
good approximation and memory efficiency.

###  1.4 Related Work

Robust submodular optimization has been studied for more than a decade. In
krause2008robust, the authors study robustness from the perspective of
multiple agents each with its own submodular valuation function; their
objective is to select a subset that maximizes the minimum among all the
agents’ valuation functions. In some sense, this maximum minimum objective
could be seen as a max-min fair subset selection goal. Another robustness
setting that deals with multiple valuation function is distributionally robust
submodular optimization (staib2019distributionally) in which we have access to
samples from a distribution of valuations functions. These settings are
fundamentally different from the robustness setting we study in our paper.

orlin2018robust and bogunovic2017robust looked at robustness of a selected set
in the presence of a few deletions. In their model, the algorithm needs to
finalize the solution before the adversarial deletions are revealed and the
adversary sees the choices of the algorithm. Therefore having at least $k$
deletions reduces the value of any solution to zero. Here, $k$ is the
cardinality constraint or the rank of the matroid depending on the setting.
This is the most prohibitive deletion robust setting we are aware of in the
literature and not surprisingly the positive results of orlin2018robust and
bogunovic2017robust are mostly useful when we are dealing with a few number of
deletions.

MirzasoleimanK017 study submodular maximization, and provide a general
framework to empower insertion-only algorithms to process deletions on the fly
as well as insertions. Their result works on general constraints including
matroids. As a result, they provide dynamic algorithms that process a stream
of deletions and insertions with an extra multiplicative overhead of $d$ (on
both the computation time and memory footprint) compared to insertion-only
algorithms. Here $d$ is the overall number of deletions over the course of the
algorithm. They propose the elegant idea of running $d+1$ concurrent streaming
submodular maximization algorithms where $d$ is the maximum number of
deletions. Every element is sent to the first algorithm. If it is not
selected, it is sent to the second algorithm; if it is not selected again, it
is sent to the third algorithm and so on. With this trick, they maintain the
invariant that the solution of one of these algorithms is untouched by the
adversarial deletions, and therefore this set of $\tilde{O}(dk)$ elements
suffice to achieve robust algorithms for matroid constraints. This approach
has the drawback of having per update computation time linearly dependent on
$d$ which can be prohibitive for large number of deletions. It also has a
total memory of $\tilde{O}(dk)$ which could be suboptimal compared to the
lower bound of $\Omega(d+k)$. For a closely related dynamic setting with
cardinality constraint, LattanziMNTZ20 provide a $2$-approximation algorithm
for $k$-uniform matroids with per update computation time of poly-logarithmic
in the total number of updates (length of the stream of updates). This much
faster computation time comes at the cost of a potentially much larger memory
footprint (up to the whole ground set). monemizadeh2020dynamic independently
designed an algorithm with similar approximation guarantee and an update time
quadratic in the cardinality constraint with a smaller dependence on
logarithmic terms.

As argued in the Introduction, a simple lower bound of $\Omega(d+k)$ exists on
the memory footprint needed by any robust constant-factor approximation
algorithm. The gap between this lower bound and the $O(dk)$ memory footprint
in MirzasoleimanK017 motivated the follow-up works that focused on designing
even more memory and computationally efficient algorithms.

MitrovicBNTC17 and KazemiZK18 are the first to study the deletion robust
setting we consider in our work. They independently designed submodular
maximization algorithms for $k$-uniform matroids. MitrovicBNTC17 proposed a
streaming algorithm that achieves constant competitive ratio with memory
$O((k+d)\polylog(k))$. Their results extends to the case that the adversary is
aware of the summary set $W$ before selecting the set $D$ of deleted elements.
On the other hand, KazemiZK18 design centralized and distributed algorithms
with constant factor approximation and $O(k+d\log(k))$ memory, as well as a
streaming algorithm with $2$-approximation factor and memory footprint of
$O(k\log(k)+d\log^{2}(k))$. We have borrowed some of their ideas including
bundling elements based on their marginal values and ensuring that prior to
deletions, elements are added to the solution only if they are selected
uniformly at random from a large enough bundle (pool of candidates).

Subsequently, AvdiukhinMYZ19 showed how to obtain algorithms for the case of
knapsack constraints with similar memory requirements and constant factor
approximation. While their approximation guarantees are far from optimal,
their notion of robustness is stronger than the one we consider: there the
adversary can select the set of deleted elements adaptively with respect to
the summary produced by the algorithm.

We aim to achieve the generality of the work of MirzasoleimanK017 work by
providing streaming algorithms that work for all types of matroid constraints
while maintaining the almost optimal computation time and space efficiency of
MitrovicBNTC17 and KazemiZK18.

Another well-studied robustness model is the sliding window model. In this
case, the deletions occur as the algorithm sweeps through the stream of
elements and in that sense they occur regularly rather than in an adversarial
manner. Every element is deleted exactly $W$ steps after its arrival. So at
every moment, the most recent $W$ elements are present and the objective is to
select a subset of these present elements. epasto2017submodular design a $3$
approximation algorithm for the case of cardinality constraints with a memory
independent of the window size $W$. zhao2019submodular provide algorithms that
extend the sliding window algorithm to settings where elements have non-
uniform lifespans and leave after arbitrary times.

Prior to deletion robust models and motivated by large scale applications,
MirzasoleimanKSK13 designed the distributed greedy algorithm and showed that
it achieves provable guarantees for the cardinality constraint problem under
some assumptions. In follow-up work, mirrokni2015randomized provided core-set
frameworks that always achieve constant factor approximation in the
distributed setting. barbosa2016new showed how to approach the optimal
$e/(e-1)$ approximation guarantee by increasing the round complexity of the
distributed algorithm. For the case of matroid constraints, ene2019submodular
provided distributed algorithms that achieve the $e/(e-1)$ approximation with
poly-logarithmic number of distributed rounds. For the streaming setting,
Ashkan21 provided a $3.147$ competitive ratio algorithm with $\tilde{O}(k)$
memory with a matroid constraint of rank $k$.

A preliminary version of this work considering only monotone objectives has
appeared as DuettingFLNZ22. We mention that, in follow-up work, Zhang22 design
a simple algorithm for the streaming version of the deletion-robust submodular
maximization problem with monotone objective subject to a $p$-matroid
constraint. Their algorithm has optimal space usage of $O(k+d)$ and achieves a
$4p$ approximation. They handle robustness via an elegant non-uniform sampling
technique that avoids the extra $O(\log k)$ due to keeping the different
buckets.

##  2 Problem formulation and preliminary results

We consider a set function $f:2^{V}\to\bbRp$ on a (potentially large) ground
set $V$. Given two sets $X,Y\subseteq V$, the _marginal gain_ of $X$ with
respect to $Y$ quantifies the change in value of adding $X$ to $Y$ and is
defined as

$\marginal{X}{Y}=f(X\cup Y)-f(Y)\,.$

When $X$ consists of a singleton $x$, we use the shorthand $f(x|Y)$ instead of
$f(\\{x\\}|Y)$. The function $f$ is called _monotone_ if $\marginal{e}{X}\geq
0$ for each set $X\subseteq V$ and element $e\in V$, and _submodular_ if for
any two sets $X$ and $Y$ such that $X\subseteq Y\subseteq V$ and any element
$e\in V\setminus Y$ we have $\marginal{e}{X}\geq\marginal{e}{Y}.$ Throughout
the paper, we assume that $f$ is given in terms of a value oracle that
computes $f(S)$ for given $S\subseteq V$ and that $f$ is _normalized_ , i.e.,
$f(\emptyset)=0$. When not specified otherwise, we do not assume monotonicity
of the function $f$. We slightly abuse the notation and for a set $X$ and an
element $e$, use $X+e$ to denote $X\cup\\{e\\}$ and $X-e$ for
$X\setminus\\{e\\}$.

A non-empty family of sets $\cM\subseteq 2^{V}$ is called a _matroid_ if it
satisfies the following properties. Downward-closedness: if $A\subseteq B$ and
$B\in\cM$, then $A\in\cM$; augmentation: if $A,B\in\cM$ with $|A|<|B|$, then
there exists $e\in B$ such that $A+e\in\cM$. We call a set $A\subseteq 2^{V}$
_independent_ , if $A\in\cM$, and _dependent_ otherwise. An independent set
that is maximal with respect to inclusion is called a base; all the bases of a
matroid share the same cardinality $k$, which is referred to as the rank of
the matroid. In general, it is possible to define the rank set function
$r:2^{V}\to\mathbb{N}$ that outputs the cardinality of the largest independent
set: $r(T)=\max\\{|I|\text{ s.t. }I\subseteq T\text{ and }T\in\cM\\}$. Dually
to basis, for any $A\notin\cM$, we can define a circuit $C(A)$ as a minimal
dependent subset of $A$, i.e. $C(A)\notin\cM$ such that all its proper subsets
are independent. Starting from any matroid $\cM$ it is possible to define two
auxiliary structures: the _contraction_ of $\cM$ by $S$, written $\cM/S$,
which is the matroid on $V\setminus S$ with rank function $r(T)=r_{\cM}(T\cup
S)-r_{\cM}(S)$, and the _restriction_ of $\cM$ by $S$, which is the matroid
$\cM^{\prime}$ on $E\setminus S$ whose independent sets $T$ are characterized
by the property that $T\cup S\in\cM$.

###  2.1 The Deletion Robust Model

The deletion robust model consists of two phases. The input of the first phase
is the ground set $V$ and a robustness parameter $d$, while the input of the
second phase is an adversarial set of $d$ deleted elements $D\subset V$, along
with the outputs of the first phase. The goal is to design an algorithm that
constructs a small size summary $W\subseteq V$ that is robust to deletions in
the first phase, and a solution $S\subseteq W\setminus D$ that is independent
with respect to matroid $\cM$ in the second phase. The difficulty of the
problem lies in the fact that the summary $W$ has to be robust against any
possible choice of set $D$ by an adversary oblivious to the randomness of the
algorithm.

For any set of deleted elements $D$, the optimum solution denoted by
$\OPT(V\setminus D)$ is defined as

$f(\OPT(V\setminus D))=\argmax_{R\subseteq V\setminus D,R\in\cM}f(R).$

We say that a two phase algorithm is an $\alpha$ approximation for this
problem if for all $D\subset V\text{ s.t. }|D|\leq d,$ it holds that

$f(\OPT(V\setminus D))\leq\alpha\cdot\E{f(S_{D})},$

where $S_{D}$ is the solution produced in Phase II when set $D$ is deleted and
the expectation is with respect to the eventual internal randomization of the
algorithm. Besides $\alpha$, an important feature of a two phase algorithm is
its summary size, i.e., the cardinality of the set $W$ returned by the first
phase.

In this paper we also consider the streaming version of the problem where the
elements in $V$ are presented in some arbitrary order (Phase I) and at the end
of such online phase the algorithm has to output a deletion robust summary
$W.$ Finally, the deleted set $D$ is revealed and Phase II on $W\setminus D$
takes place offline. The quality of an algorithm for the streaming problem is
not only assessed by its approximation guarantee and summary size, but is also
measured in terms of its memory, i.e., the cardinality of the buffer in the
online phase.

###  2.2 Preliminary Results

We conclude this section with three preliminary results: the folklore sampling
Lemma by BuchbinderFNS14, a combinatorial Lemma we derived from the well known
Hall’s Marriage Theorem and a graph theoretical result from FeldmanK018. While
the first Lemma is our main tool to address non-monotonicity, the other two
results are used for the charging arguments in the analysis of our algorithms.

We start with the sampling Lemma, that has been proved by FeigeMV11 and that
we report as in Lemma 2.2 of BuchbinderFNS14.

[Sampling Lemma] Let $f:2^{V}\to\mathbb{R}_{\geq 0}$ be a (possibly not
normalized) submodular set function, let $X\subseteq V$ and let $X(p)$ be a
sampled subset, where each element of $X$ appears with probability at most $p$
(not necessarily independent). Then
$\mathbb{E}\left[f(X(p))\right]\geq(1-p)f(\emptyset)\,$.

We move now to our combinatorial Lemma. At a high level, it is a general tool
that maps injectively elements in a dependent set to those of an independent
set under some conditions.

[Combinatorial Lemma] Consider a matroid $\cM\subseteq 2^{V}$ and two sets
$F\subseteq V$, and $G\in\mathcal{M}$. Suppose that for all $x\in G\setminus
F$ there exist a set $F_{x}\subseteq F,F_{x}\in\mathcal{M}$ such that
$F_{x}+x\not\in\mathcal{M}$. Then there exists a mapping $h:G\setminus
F\rightarrow F$ such that

  * •

for all $x\in G\setminus F$, $h(x)\in F_{x}$, and

  * •

for all $x,y\in G\setminus F$ with $x\neq y$, $h(x)\neq h(y)$.

Intuitively, $h$ as a _semi-matching_ that matches all elements in $G\setminus
F$ to an element in $\cup_{x\in G\setminus F}F_{x}$, while some of the
elements in $\cup_{x\in G\setminus F}F_{x}\subseteq F$ can remain unmatched.
To prove the Lemma, we use the combinatorial version of Hall’s Marriage
Theorem, that concerns set systems and the existence of a transversal (a.k.a.
system of distinct representatives). Formally, let $\cS$ be a family of finite
subsets of a base set $X$ ($\cS$ may contain the same set multiple times). A
_transversal_ is an injective function $f:\cS\rightarrow X$ such that $f(S)\in
S$ for every set $S\in\cS$. In other words, $f$ selects one representative
from each set in $S$ in such a way that no two of these representatives are
equal.

[Hall (1935)] A family of sets $\cS$ has a transversal if and only if $\cS$
satisfies the marriage condition: i.e., if for each subfamily
$\cW\subseteq\cS$, it holds that $|\cW|\leq\left|\bigcup_{F\in\cW}F\right|.$

We are ready to present the proof of our combinatorial lemma.

###### Proof.

Let $W$ be any subset of $G\setminus F$ and define $F_{W}=\bigcup_{x\in
W}F_{x}$. We want to show that

$|F_{W}|=|\bigcup_{x\in W}F_{x}|\geq|W|.$

In order to do that we first show that $\cl(W\cup F_{W})=\cl(F_{W})$, where
$\cl(.)$ denotes the _closure_ (or _span_) of a set. We have that
$W\subseteq\cl(F_{W})$, in fact, for each element $x\in W$ there exists a
subset $F_{x}\subseteq F_{W}$ such that $F_{x}+x\not\in\I$ and therefore
$x\in\cl(F_{x})$, which implies, by monotonicity of the closure with respect
to the inclusion, that $x\in\cl(F_{W})$. We also know that
$F_{W}\subseteq\cl(F_{W})$, hence $F_{W}\cup W\subseteq\cl(F_{W})$. If we
apply the closure to both sets, we get

$\cl(F_{W}\cup W)\subseteq\cl(\cl(F_{W}))=\cl(F_{W})\subseteq\cl(F_{W}\cup
W),$

where the equation follows by the well-known properties of closure. This shows
that $\cl(F_{W}\cup W)=\cl(F_{W})$ as claimed.

Now let’s look at the restriction of the matroid $\cM$ to $\cl(F_{W}\cup
W)=\cl(F_{W})$. Afterwards, contract this matroid by $(F\cap G)\cap\cl(F_{W})$
and call the resulting matroid with $\cM^{\prime}$. We claim that $W$ is
independent in this new matroid $\cM^{\prime}$. This is due to, $W\subseteq
G\setminus F$ and $W\cup(F\cap G)\subseteq G$ and $G\in\I$. If we call
$r^{\prime}$ the rank of the matroid $\cM^{\prime}$, we have
$r_{\cM}(\cl(F_{W}))\geq r_{\cM}(\cl(F_{W})\setminus(F\cap
B))=r^{\prime}\geq|W|.$ Finally, it holds that $|F_{W}|\geq
r_{\cM}(F_{W})=r_{\cM}(\cl(F_{W})).$ Putting these two chains of inequalities
together we obtain $|F_{W}|\geq|W|$ as claimed. The proof follows by applying
hall-thm.

The last preliminary result we present is Lemma $13$ of FeldmanK018. It
concerns directed acyclic graphs (DAGs) where the nodes are also elements of a
matroid. Under some assumption, it guarantees the existence of an injective
mapping between elements in an independent set and of the sinks of the DAG. As
a convention, we denote with $\delta^{+}(u)$ the out-neighborhood of any node
$u.$

Consider an arbitrary directed acyclic graph $G=(V,E)$ whose vertices are
elements of some matroid $\cM$. If every non-sink vertex $u$ of $G$ is spanned
by $\delta^{+}(u)$ in $\cM$, then for every set $S$ of vertices of $G$ which
is independent in $\cM$ there must exist an injective function $\psi$ such
that, for every vertex $u\in S$, $\psi(u)$ is a sink of $G$ which is reachable
from $u$.

##  3 Centralized Algorithm

In this section, we present a centralized algorithm for the Deletion Robust
Submodular Maximization problem subject to a matroid constraint. To that end,
we start by defining some notations. Let $\tilde{e}$ be the $(d+1)$-th element
with largest value according to $f$ and let $\Delta$ be its value. Given the
precision parameter $\eps$, we define the set of relevant thresholds $T$ as
follows

$T=\left\\{(1+\eps)^{i}\mid\eps\cdot\frac{\Delta}{(1+\eps)k}<(1+\eps)^{i}\leq\Delta\right\\}.$

The first phase of our algorithm constructs the summary in iterations using
two main sets: a candidate solution $A$ and a reservoir $B$ of good elements,
that are grouped into buckets of similar elements. The algorithm goes over the
thresholds in $T$ in decreasing order and updates sets $A,B$, and $V$. Let
$\tau$ be the threshold considered at some point, then $B_{\tau}$ contains any
element $e\in V$ such that $f(e|A)>\tau$ and $A+e\in\cM$. These are the high
contribution elements that can be added to $A$. As long as the size of
$B_{\tau}>(k+d)/\eps$, the algorithm chooses uniformly at random an element
from $B_{\tau}$, adds it to $A$ and recomputes $B_{\tau}$. We observe that $A$
is robust to deletions, i.e., when $d$ elements are deleted, the probability
of one specific element in $A$ being deleted is intuitively at most $\eps$.
Moreover, since each element added to $A$ is drawn from a pool of elements
with similar marginals, the value of this set after the deletions decreases at
most by a factor $(1-\eps)$ in expectation (this is a very slack bound).

As soon as the cardinality of $B_{\tau}$ drops below $(k+d)/\varepsilon$, no
more elements can be added directly from it to $A$ while keeping $A$ robust
and feasible. Therefore, we remove these elements from $V$ and save them for
Phase II. During the execution of the algorithm we need to take special care
of the top $d$ element with highest $f$ values. To avoid complications, we
remove them from the instance before starting the procedure and add them to
set $B$ at the end. This does not affect the general logic and only simplifies
the presentation and the proofs. The pseudocode of the centralized algorithm
for Phase I is given in alg:centralized-phase-I.

Algorithm 1 Centralized Algorithm Phase I

1: Input: Precision $\varepsilon$ and deletion parameter $d$

2: $\Delta\leftarrow$ $(d+1)^{th}$ largest value in $\\{f(e)\mid e\in V\\}$.

3: $V_{d}\leftarrow$ elements with the $d$ largest values.

4: $V\leftarrow V\setminus V_{d}$, $A\leftarrow\emptyset$.

5:
$T=\left\\{(1+\eps)^{i}\mid\eps\cdot\frac{\Delta}{(1+\eps)k}<(1+\eps)^{i}\leq\Delta\right\\}$

6: for $\tau\in T$ in decreasing order do

7: $B_{\tau}\leftarrow\\{e\in V\mid A+e\in\cM,f(e\mid A)\geq\tau\\}$

8: while $|B_{\tau}|\geq\frac{k+d}{\varepsilon}$ do

9: $e\leftarrow$ a random element sampled independently and uniformly from
$B_{\tau}$.

10: $V\leftarrow V-e$, $A\leftarrow A+e$.

11: $B_{\tau}\leftarrow\\{e\in V\mid A+e\in\cM,f(e\mid A)\geq\tau\\}$

12: Remove $B_{\tau}$ from $V$.

13: $B\leftarrow V_{d}\cup\bigcup_{\tau\in T}B_{\tau}$.

14: return $A,B$.

The summary $W$ computed at the end of Phase I is composed by the union of $A$
and $B$ and is then passed to the second phase of our algorithm, which uses as
routine an arbitrary algorithm for submodular maximization subject to matroid
constraint. takes as input a set of elements, function $f$ and matroid $\cM$
and returns a $\beta$-approximate solution. In this phase we simply use to
compute a solution among all the elements in $A$ and $B$ that survived the
deletion and return the best among the computed solution and the value of the
surviving elements in $A$.

Algorithm 2 Algorithm Phase II

1: Input: $A$ and $B$ outputs of phase I, set $D$ of deleted elements and
optimization routine $\BBAlg$

2: $A^{\prime}\leftarrow A\setminus D$, $B^{\prime}\leftarrow B\setminus D$

3: $\tilde{S}\leftarrow\BBAlg(A^{\prime}\cup B^{\prime})$

4: return $S\leftarrow\argmax\\{f(A^{\prime}),f(\tilde{S})\\}$

Consider the problem of deletion robust non-monotone submodular maximization
with matroid constraints. For $\eps\in(0,1/5)$, the Centralized Algorithm
(alg:centralized-phase-I and alg:phase-II) is in expectation a
$(2+\beta+O(\eps))$-approximation algorithm with summary size
$O(\frac{k+d}{\eps^{2}}\log{\frac{k}{\eps}})$, where $\beta$ is the
approximation ratio of the auxiliary algorithm .

###### Proof.

In this proof, sets $A$ and $B$ are the sets returned by Algorithm 1 at the
end of phase I. We start by analyzing the size of the summary, composed by $A$
and $B$. Set $A\in\cM$, thus its size is no more than the rank of $\cM$,
therefore: $|A|\leq k$. Set $B$ is the union of $V_{d}$ (containing exactly
$d$ elements) and $\bigcup_{\tau\in T}B_{\tau}$. Each set $B_{\tau}$ has at
most $\frac{k+d}{\eps}$ element and there are at most
$\frac{2}{\eps}\log\frac{k}{\eps}$ such sets. Therefore

$|A|+|B|\leq k+d+\frac{2(k+d)}{\eps^{2}}\log\frac{k}{\eps}\in
O\left(\frac{k+d}{\eps^{2}}\log{\frac{k}{\eps}}\right).$

We move our focus on bounding the approximation factor. To that end, we fix
any set $D$ with $|D|\leq d$ and bound the ratio between the expected value of
$f(S)$ and $f(\OPT)$ (we omit the dependence on $D$ since it is clear from the
context). As a first step, we bound the value of $\OPT$ with that of $\OPT\cup
A$. This passage is trivially true when $f$ is monotone, but needs some work
otherwise.

It holds that $(1-\eps)f(\OPT)\leq\E{f(\OPT\cup A)}.$

###### Proof.

Every time a new random element $x_{i}$ is added to the candidate solution
$A$, it is drawn uniformly at random from a large pool of elements of
cardinality at least $(k+d)/\eps$. Thus
${\mathbb{P}}\left(x=x_{i}\right)\leq\frac{\eps}{k+d}$ for all fixed $x$ and
all $i=1,\dots k.$ By union bound, we have the following:

${\mathbb{P}}\left(x\in
A\right)\leq\sum_{i=1}^{k}{\mathbb{P}}\left(x=x_{i}\right)\leq\eps\frac{k}{k+d}\leq\eps,\;\;\forall
x\in V.$

Consider the submodular function $g:2^{V}\to\mathbb{R}_{\geq 0}$, defined as
$g(T)=f(\OPT\cup T),$ for all $T\subseteq V$. We can apply the sampling Lemma
(lem:sampling) on $g$ and the bound on ${\mathbb{P}}\left(x\in A\right)$ to
obtain the desired claim:

$\E{f(\OPT\cup A)}=\E{g(A)}\geq(1-\eps)g(\emptyset)=(1-\eps)f(\OPT).$

This means we just need to bound the value of $\OPT\cup A$; to do that we
introduce three subsets and analyze the resulting terms separately. First,
recall that we denoted by $B^{\prime}$ the subset of $B$ surviving the
deletion: $B^{\prime}=B\setminus D$; clearly it holds that $B\cap\OPT\subseteq
B^{\prime}$. Then, define $L$ as the set of elements of low value:

$L=\left\\{e\in V\setminus D\mid f(e\mid
A)\leq\eps\cdot\frac{f(\OPT)}{k}\right\\}.$

Intuitively, $L$ contains all the low value elements: these elements do not
increase the value of the submodular function considerably if added to $A$ (we
do not lose much by ignoring them). Finally, let $F$ be the surviving elements
that have not been added to the summary because of feasibility issues;
formally, $F=V\setminus(A\cup B\cup L\cup D)$. We can now decompose the
contributions of elements in $\OPT\cup A$ using the sets we introduced: by
submodularity and lem:nonmonotone, we in fact have:

$\displaystyle(1-\eps)f(\OPT)\leq$ $\displaystyle\E{f(\OPT\cup A)}$
$\displaystyle\leq$ $\displaystyle\E{f(A)}+\E{f(\OPT\cap B^{\prime}\mid A)}$
$\displaystyle+$ $\displaystyle\E{f(\OPT\cap F\mid A)}+\E{f(\OPT\cap L\mid
A)}$ (1)

Recall that $A^{\prime}$ is the candidate solution once the deleted elements
are realized; we use its expected value to bound the first term of the
inequality. Intuitively, for any element that is part of $A$ the probability
of it being deleted is $O(\eps)$, since it is sampled from $(d+k)/\eps$
similar elements uniformly at random and only $d$ elements are deleted. We
formalize this idea in the following Lemma.

It holds that $\E{f(A)}\leq\frac{1+\eps}{1-\eps}\ \E{f(A^{\prime})}$.

###### Proof.

The proof is similar to that of Lemma 2 in kazemi17arxiv, but note that we do
assume the monotonicity of $f$. For the sake of the analysis, for each
threshold $\tau\in T$, let $A_{\tau}$ denote the set of elements in $A$ that
were added during an iteration of the for loop corresponding to threshold
$\tau$ in alg:centralized-phase-I. Moreover, let $n_{\tau}=|A_{\tau}|$ and
order the elements in $A_{\tau}=\langle
x_{1,\tau},x_{2,\tau},\dots,x_{n_{\tau},\tau}\rangle$ according to the order
in which they are added to $A_{\tau}.$ Finally, let $I(\ell,\tau)$ be the
indicator random variable corresponding to the element $x_{\ell,\tau}$ not
being in $D$. Note that the randomness here is with respect to the random draw
of the algorithm in Phase I: $D$ is fixed but unknown to the algorithm. The
crucial argument is that $x_{\ell,\tau}$ is drawn uniformly at random from a
set of cardinality at least $(d+k)/\varepsilon$ where at most $d$ elements lie
in $D$, hence

${\mathbb{P}}\left(I(\ell,\tau)\right)\geq 1-\varepsilon\frac{d}{k+d}\geq
1-\eps.$ (2)

We can decompose the value of $A$ as follows using the definition of marginal
value:

$\displaystyle f(A)$ $\displaystyle=\sum_{\tau\in
T}\sum_{\ell=1}^{n_{\tau}}f(x_{\ell,\tau}|\cup_{t>\tau}A_{t}\cup\\{x_{1,\tau},x_{2,\tau},\dots,x_{\ell-1,\tau}\\}).$

The elements added in a specific iteration of the for loop share the same
marginal up to an $(1+\varepsilon)$ factor, i.e.,

$\tau\leq
f(x_{\ell,\tau}|\cup_{t>\tau}A_{t}\cup\\{x_{1,\tau},x_{2,\tau},\dots,x_{\ell-1,\tau}\\})\leq\tau\cdot(1+\varepsilon),\quad\forall\tau\in
T,\quad\forall\ell=1,\dots,n_{\ell}.$ (3)

Thus, summing up those contributions, we have

$\sum_{\tau\in T}|A_{\tau}|\cdot\tau\leq f(A)\leq(1+\varepsilon)\sum_{\tau\in
T}|A_{\tau}|\cdot\tau.$ (4)

We now decompose in a similar way the value of $A^{\prime}=A\setminus D$. Let
$I(\ell,i)\cdot x$ be a shorthand to denote the element $x$ if the indicator
variable $I(\ell,i)$ is $1$ and the empty set otherwise. Similarly, we let
$I(\ell,i)\cdot X$ be a shorthand to denote the set $X$ if the indicator
variable $I(\ell,i)$ is $1$ and the empty set otherwise. We also define
$A^{\prime}_{\tau}=A_{\tau}\setminus D=A_{\tau}\cap A^{\prime}$, we have

$\displaystyle f(A^{\prime})$ $\displaystyle=\sum_{\tau\in
T}\sum_{\ell=1}^{n_{\tau}}I(\ell,\tau)\cdot
f(x_{\ell,\tau}|\cup_{t>\tau}A_{t}\cup\\{I(1,\tau)\cdot
x_{1,\tau},I(2,\tau)\cdot x_{2,\tau},\dots,I(\ell-1,\tau)\cdot
x_{\ell-1,\tau}\\})$ $\displaystyle\geq\sum_{\tau\in
T}\sum_{\ell=1}^{n_{\tau}}I(\ell,\tau)\cdot
f(x_{\ell,\tau}|\cup_{t>\tau}A_{t}\cup\\{x_{1,\tau},x_{2,\tau},\dots,x_{\ell-1,\tau}\\})$
$\displaystyle\geq\sum_{\tau\in
T}\sum_{\ell=1}^{n_{\tau}}I(\ell,\tau)\cdot\tau$ $\displaystyle=\sum_{\tau\in
T}|A^{\prime}_{\tau}|\cdot\tau,$

where the first inequality follows by submodularity and the second one follows
from eq:at_cont. We apply the expected value to the previous inequality, which
results in

$\E{f(A^{\prime})}\geq\sum_{\tau\in
T}\E{|A^{\prime}_{\tau}|}\cdot\tau\geq(1-\varepsilon)\sum_{\tau\in
T}\E{|A_{\tau}|}\cdot\tau\geq\frac{1-\varepsilon}{1+\varepsilon}\E{f(A)},$

where the second inequality follows by linearity of expectation and
eq:robust_proba, while the last one from the right hand side of
eq:robust_ineq.

For the second term of eq:partition_OPT, observe that $\OPT\cap
B^{\prime}\in\cM$ and is contained in the set of elements passed to , so its
value is dominated by $\beta$ times the value of the of $\BBAlg(A^{\prime}\cup
B^{\prime})$, all in all:

$\displaystyle\E{f(\OPT\cap B^{\prime}\mid A)}\leq\beta\cdot\E{f(S)}.$ (5)

Recall infact that $S$ is the final solution output by the algorithm. Bounding
the third term is more involved and is handled in the following Lemma via a
charging argument that uses our Combinatorial Lemma (lem:hall-lemma).

It holds that $\E{f(\OPT\cap F\mid A)}\leq(1+\eps)\E{f(A)}$.

###### Proof.

Let’s order the elements in $\Sopt\cap F=\\{x_{1},x_{2},\dots\\}$ according to
the order in which they were removed from some $B_{\tau}$ because of
feasibility constraint (since they are in $V\setminus(A\cup B\cup D\cup L)$ it
must be the case). Note that once an element fails the feasibility test and is
removed from some $B_{\tau}$, it never becomes feasible again because of
diminishing returns property of submodular functions. Furthermore, for each
such $x_{i}$ let $F_{i}$ be the set $A$ when $x_{i}$ fails the feasibility
test. We know that $F_{i}$ is independent since $A$ is independent during the
execution of Algorithm 1; moreover, by definition, $F_{i}+x_{i}\not\in\cM$. By
lem:hall-lemma there exists an injective function $h:\Sopt\cap F\to A$ such
that $h(x_{i})\in F_{i}$ for all $i$. Let $A_{i}$ denote the set $A$ when the
element $h(x_{i})$ gets added to it. Since $h(x_{i})$ has been added to $A$
before $x_{i}$, it holds that $A_{i}\subseteq F_{i}$. We have

$\displaystyle f(\Sopt\cap F\mid A)$ $\displaystyle\leq\sum_{x\in\Sopt\cap
F}f(x|A_{i})$ $\displaystyle\leq\sum_{x\in\Sopt\cap F}(1+\varepsilon)\cdot
f(h(x_{i})|A_{i})$ $\displaystyle\leq(1+\varepsilon)\cdot f(A),$

where the first inequality follows from submodularity and the fact that
$A_{i}\subseteq A$ for all $i$. The second inequality uses the fact that if
$x_{i}$ was still feasible to add when $h(x_{i})$ was added, then their
marginals are at most a $(1+\varepsilon)$ factor away. The last inequality
follows from a telescopic decomposition of $A$, the fact that an element is
added to the candidate solution $A$ only if its marginal is positive (actually
larger than a certain non-negative threshold), and the fact that $h$ is
injective. Applying the expectation to both extremes of the chain of
inequalities gives the Lemma.

The fourth term of eq:partition_OPT refers to at most $k$ elements and can be
bounded based on the definition of $L$: any element $e$ in $L$ is such that
$f(e|A)\leq\eps\cdot\frac{f(\OPT)}{k},$ by submodularity we have then that

$\displaystyle\E{f(\OPT\cap L\mid A)}\leq\E{\sum_{e\in\OPT\cap L}f(e\mid
A)}\leq\eps\cdot f(\OPT).$ (6)

Finally, we compose the four bounds in eq:partition_OPT, thus obtaining the
following:

$\displaystyle(1-\eps)f(\OPT)\leq$ $\displaystyle\E{f(A)}+\E{f(\OPT\cap
B^{\prime}\mid A)}$ $\displaystyle+\E{f(\OPT\cap F\mid A)}+\E{f(\OPT\cap L\mid
A)}$ $\displaystyle\leq$
$\displaystyle\left(2+\eps\right)\E{f(A)}+\beta\E{f(S)}+\eps f(\OPT)$ (Due to
(5), (6) and Lemma 3) $\displaystyle\leq$
$\displaystyle(2+\eps)\frac{1+\eps}{1-\eps}\E{f(A^{\prime})}+\beta\cdot\E{f(S)}+\eps
f(\OPT)$ (Lemma 3) $\displaystyle\leq$
$\displaystyle\left[(2+\eps)\frac{1+\eps}{1-\eps}+\beta\right]\cdot\E{f(S)}+\eps\cdot
f(\OPT)$ (Definition of $S$)

Rearranging terms we get

$\displaystyle f(\OPT)$ $\displaystyle\leq\frac{\E{f(\OPT\cup
A)}}{1-2\eps}\leq\left[\frac{\left(2+\eps\right)(1+\eps)}{(1-2\eps)(1-\eps)}+\frac{\beta}{1-2\eps}\right]\cdot\E{f(S)}$
$\displaystyle\leq\left[2+\beta+\left(4\beta+15\right)\cdot\eps\right]\cdot\E{f(S)},$

where in the last inequality we used that
$\frac{\left(2+\eps\right)(1+\eps)}{(1-2\eps)(1-\eps)}\leq 2+15\eps$ for all
$\eps\in(0,\frac{1}{5})$ and that $1/(1-2\eps)\leq(1+4\eps)$ in the same
interval. The theorem follows since as long as $\beta$ is a constant it holds
that $\left(4\beta+15\right)\cdot\eps\in O(\eps)$.

Plugging in the previous Theorem some routines for non-monotone submodular
maximization with matroid constraints we get, for examples, an approximation
of $\approx 4.597$ if we use the state of the art algorithm as in
BuchbinderF19 or $\approx 4.73$ if we use the less involved measured
continuous greedy (FeldmanNS11). Using the former routine and handling the
$\eps$ term accordingly, it is easy to see we have the following Corollary.

Consider the problem of deletion robust non-monotone submodular maximization
with matroid constraints and fix any constant $\delta\in(0,1)$, then there
exists a constant $C_{\delta}$ such that for any $\eps\in(0,\delta)$, in
expectation a ${(4.597+\eps\cdot C_{\delta})}$-approximation algorithm with
summary size $O(\frac{(k+d)}{\eps^{2}}\log\frac{k}{\eps})$ exists.

If we move our attention to monotone objective, we get an approximation factor
$4$ if we use as subroutine the greedy algorithm (fisher78-II) or
$2+\tfrac{e}{e-1}\leq 3.582$ if we use continuous greedy as in CalinescuCPV11.
Furthermore, it is possible to slightly improve the bound on the cardinalily
of the summary.

Consider the problem of deletion robust monotone submodular maximization with
matroid constraints and fix any constant $\delta\in(0,1)$, then there exists a
constant $\tilde{C}_{\delta}$ such that for any $\eps\in(0,\delta)$, in
expectation a ${(3.582+\eps\cdot\tilde{C}_{\delta})}$-approximation algorithm
with summary size $O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps})$ exists.

###### Proof.

First, we study the improved bound on the summary size. Since the function is
monotone, we do not need to argue as in lem:nonmonotone to bound $f(\OPT)$
with $f(\OPT\cup A)$; thus we can modify the condition on the while loop of
Algorithm 1 to simply consider $|B_{\tau}|\geq d/\eps$. With this tweak, there
are still at most $\frac{1}{\eps}\log(k/\eps)$ buckets, but each one has
cardinality at most $d/\eps$, thus the summary size is
$O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps}).$ From the approximation point of
view, lem:robustness still holds, as the crucial property that
${\mathbb{P}}\left(I(\ell,\tau)\right)\geq 1-\eps$ is verified (we are
sampling uniformly at random from a bucket of cardinality at least $d/\eps$
where there are at most $d$ deleted elements). The rest of the analysis of
thm:robust-centralized goes trough without any other difference and we get
that

$f(\OPT)\leq\E{f(\OPT\cup
A)}\leq\left[\left(2+\eps\right)\frac{1+\eps}{1-\eps}+\beta\right]\cdot\E{f(S)}+\eps\cdot
f(\OPT)$

We use as optimization routine continuous greedy, therefore we can plug in
$\beta=\frac{e}{e-1}$ and, rearranging the terms we obtain

$\displaystyle f(\Sopt)$
$\displaystyle\leq\left(\frac{e}{(e-1)(1-\eps)}+\frac{(2+\eps)(1+\eps)}{(1-\eps)^{2}}\right)\E{f(S)}$
$\displaystyle\leq\Big{[}\frac{e}{e-1}+2+\underbrace{\frac{8e-7-\delta(2e-1)}{(e-1)(\delta-1)^{2}}}_{\tilde{C}_{\delta}}\cdot\eps\Big{]}\E{f(S)},$

where the last inequality can be numerically verified and holds for any
$\eps\in(0,\delta).$

##  4 Streaming Setting

Algorithm 3 Streaming Algorithm Phase I

1: Input: Precision $\varepsilon$, deletion parameter $d,$ sampling
probability $p$ and parameter $\gamma$

2: $T\leftarrow\\{(1+\varepsilon)^{i}\mid i\in\mathbb{Z}\\}$

3: $A\leftarrow\emptyset$, $\Delta\leftarrow 0$, $\tau_{min}\leftarrow 0$,
$B_{\tau}\leftarrow\emptyset$ for all $\tau\in T$

4:
$L\leftarrow\emptyset,\Gamma\leftarrow\emptyset,K\leftarrow\emptyset,R\leftarrow\emptyset,F\leftarrow\emptyset$
$\rhd$ Auxiliary sets for the analysis

5: $V_{d}\leftarrow$ the first $d$ arriving elements

6: for every arriving element $e^{\prime}$ do

7: Add $e^{\prime}$ to $V_{d}$ and then pop element $e$ with smallest value
from $V_{d}$

8: $\Delta\leftarrow\max\\{f(e),\Delta\\}$,
$\tau_{min}\leftarrow\frac{\varepsilon}{1+\varepsilon}\cdot\frac{\Delta}{k},T\leftarrow\\{\tau\in
T\mid\tau\geq\tau_{min}\\}$

9: Remove all $B_{\tau}$ s.t. $\tau\not\in T$$\rhd$ Deleted elements are added
to $L$

10: if $\tau_{min}>f(e\mid A)$ then Discard $e$ and continue$\rhd$
$L\leftarrow L+e$

11: Find the largest threshold $\tau\in T$ s.t. $f(e\mid A)\geq\tau$ and add
$e$ to $B_{\tau}$

12: while $\exists\tau\in T$ such that $|B_{\tau}|\geq\frac{d}{\varepsilon}$
do

13: Remove one element $g$ from $B_{\tau}$ u.a.r. $\rhd$
$\Gamma\leftarrow\Gamma+g$

14: $w(g)\leftarrow f(g\mid A)$

15: Draw $X_{g}$ independently from a Bernoulli with parameter $p$

16: if $A+g\in\I$ then

17: if $X_{g}=1$, then $A\leftarrow A+g$

18: else Discard $g$ $\rhd$ $R\leftarrow R+g$

19: else

20: $k_{g}\leftarrow\argmin\\{w(k)\mid k\in C(A+g)\\}$

21: if $w(g)>(1+\gamma)\cdot w(k_{g})$ then

22: if $X_{g}=1$, then $A\leftarrow A+g-k_{g}$ $\rhd$ $K\leftarrow K+k_{g}$

23: else Discard $g$ $\rhd$ $R\leftarrow R+g$

24: else

25: Discard $g$ $\rhd$ $F\leftarrow F+g$

26: Update $\\{B_{\tau}\\}$ according to $A$ $\rhd$ Deleted elements are added
to $L$

27: $B\leftarrow V_{d}\cup_{\tau\in T}B_{\tau}$

28: return $A,B$

In this section we present our algorithm for Deletion Robust Submodular
Maximization in the streaming setting. Here, the elements of $V$ in the first
phase arrive on a stream and we want to compute a small summary $W$ using
limited (online) memory. Our approach consists of carefully mimicking the
swapping algorithm (ChakrabartiK15) with subsampling (FeldmanK018) in a
deletion robust fashion; to that end, the algorithm maintains an independent
candidate solution $A$ and buckets $B_{\tau}$ that contain small reservoirs of
elements from the stream with similar marginal contribution each element with
respect to the current solution $A.$ Beyond the $B_{\tau}$, an extra buffer
$V_{d}$ containing the best $d$ elements seen so far is kept.

We start explaining the algorithm by defining the thresholds $\tau$. In the
streaming setting we do not have an a priori estimate of $\OPT$, so that we do
not know upfront which are the thresholds corresponding to high quality
elements. This issue is overcome by initially considering all the powers of
$(1+\eps)$ and progressively removing the ones too small with respect to
$\Delta$, i.e., the $(d+1)$-st largest value seen so far. Every new element
$e^{\prime}$ that arrives is first used to update $V_{d}$: if its value is
larger then the minimum in $V_{d}$ then we add it to $V_{d}$ and remove the
smallest value element from $V_{d}$ and denote it by $e$. If the value of the
newly arrived element is smaller than smallest value element in $V_{d}$, we
keep the set $V_{d}$ intact. For simplicity, we set $e$ to be the newly
arrived element $e^{\prime}$ in this case. In other words, element $e$ is
either the new element or the element which lost its place in $V_{d}$ to the
new element.

In either case, we use element $e$ in the next steps of the algorithm. Then,
the value of $\Delta$ is updated if $f(e)>\Delta$ and all the buckets
corresponding to thresholds that are too small are deleted, this guarantees
that only a logarithmic number of active buckets is kept. At this point
element $e$ is put into the correct bucket $B_{\tau}$, if such bucket still
exists. Now, new elements are drawn uniformly at random from the buckets
$B_{\tau}$ with size at least $d/\eps$ as long as no bucket contains more than
$d/\eps$ elements. These drawn elements are added to $A$ if and only if the
subsampling is successful and it is either feasible to add them directly or
they can be swapped with a less important element in $A$. To make this notion
of importance more precise, each element in the solution is associated with a
weight, i.e., its marginal value to $A$ when it was first considered to be
added to the solution. To complete the notation, we let weight of a set of
elements be the sum of the weights of its elements. An element in $A$ is
swapped for a more promising one only if the new one has a weight that is
larger by at least a $(1+\gamma)$ factor and it is sampled independently with
some probability $p$, while maintaining $A$ independent.

Every time $A$ changes, the buckets $B_{\tau}$ are completely updated so to
maintain the invariant that $B_{\tau}$ contains only elements whose marginal
value with respect to the current solution $A$ is within $\tau$ and
$(1+\eps)\cdot\tau.$ This property is crucial to ensure the deletion
robustness: every bucket contains elements that are similar, i.e., whose
marginal density with respect to the current solution is at most a
multiplicative $(1+\eps)$ factor away. When the stream terminates, the
algorithm passes the deletion robust summary $W$ (composed by the candidate
solution $A$ and $B$, containing $V_{d}$ and the surviving buckets) to
Algorithm 2. The pseudocode of this algorithm is presented in alg:streaming-
phase-I. Before stating and proving our Theorem, we describe some of the
properties of the weight function $w$ that governs the swapping.

Let $w$ be the weight function, $A$ the candidate solution,
$A^{\prime}=A\setminus D$ and let $K$ be the set of all the elements that, at
some point, were in $A$ but were later swapped. Then, the following properties
hold:

  * $(i)$

$\gamma\cdot w(K)\leq w(A)\leq f(A)$

  * $(ii)$

$w(A^{\prime})\leq f(A^{\prime})$

  * $(iii)$

$f(A\cup K)\leq w(A\cup K)$

###### Proof.

The proof of the first inequality is similar to the one of Lemma 9 in
ChakrabartiK15. Crucially, the weight function $w$ is linear and once an
element enters $A$, its weight is fixed forever as the marginal value it
contributed when entering $A$, moreover the weight of all the elements added
to $A$ is strictly positive. During the run of the algorithm, every time an
element $k_{g}$ is removed from $A$, the weight of $A$ increases by
$w(g)-w(k_{g})$ by its replacement with some element $g$. Moreover,
$\gamma\cdot w(k_{g})\leq w(g)-w(k_{g})$ for every element $k_{g}\in K$ since
$(1+\gamma)w(k_{g})\leq w(g)$. Summing up over all elements in $K$, and
recalling that the weight function is positive for all the elements in $A\cup
K$, it holds that

$w(K)=\sum_{k_{g}\in K}w(k_{g})\leq\frac{1}{\gamma}\sum_{k_{g}\in
K}\left[w(g)-w(k_{g})\right]\leq\frac{1}{\gamma}w(A).$

We show now the second inequality. Let $<a_{1},a_{2},\dots a_{\ell}>$ be the
elements in $A$, sorted in the order in which they were added to $A$. We have
that

$f(A)=\sum_{i=1}^{\ell}f(a_{i}|\\{a_{1},\dots,a_{i-1}\\})\geq\sum_{i=1}^{\ell}f(a_{i}|A_{a_{i}})=\sum_{i=1}^{\ell}w(a_{i})=w(A),$

where $A_{a_{i}}$ is the solution set right before $a_{i}$ is added to $A$.
The inequality follows from submodularity, since
$\\{a_{1},\dots,a_{i-1}\\}\subseteq A_{a_{i}}$. Similarly, let $I(a)$ the
indicator random variable corresponding to $a\not\in D$, while $I(a)\cdot a$
is a shorthand for the element $a$ if $I(a)=1$ and the empty set otherwise.

$\displaystyle f(A^{\prime})$ $\displaystyle=\sum_{i=1}^{\ell}I(a_{i})\cdot
f(a_{i}|\\{I(a_{1})\cdot a_{1},\dots,I(a_{i-1})\cdot a_{i-1}\\})$
$\displaystyle\geq\sum_{i=1}^{\ell}I(a_{i})\cdot
f(a_{i}|\\{a_{1},\dots,a_{i-1}\\})$
$\displaystyle\geq\sum_{i=1}^{\ell}I(a_{i})\cdot
f(a_{i}|A_{a_{i}})=w(A^{\prime}).$

For the last inequality, let $x_{1},x_{2},\dots x_{t}$ be the elements in
$A\cup K$, sorted by the order in which they were added to $A$. We have that

$f(A\cup
K)=\sum_{i=1}^{t}f(x_{i}|\\{x_{1},\dots,x_{i-1}\\})\leq\sum_{i=1}^{t}f(x_{i}|A_{x_{i}})=\sum_{i=1}^{t}w(x_{i})=w(A\cup
K),$

where $A_{x_{i}}$ is the solution set right before $x_{i}$ is added to $A$.
The inequality follows from submodularity: $A_{x_{i}}$ contains all the
elements entered in $A$ before $x_{i}$ minus those elements that have already
been removed from it.

We are now ready for the main result of the Section. Instead of stating a
general black box result as in thm:robust-centralized, we consider directly
the algorithm from BuchbinderF19 as and analyze the relative algorithm for a
suitable choice of $p$ and $\gamma.$ This is just for clarity of exposition:
the dependence on $\beta$ of the generic approximation is more involved than
in the centralized case.

Consider the problem of deletion robust non-monotone submodular maximization
with matroid constraints in the streaming scenario. Fix any constant
$\delta\in(0,1)$, then there exists a constant $G_{\delta}$ such that for any
$\eps\in(0,\delta)$, in expectation a
$(9.435+G_{\delta}\cdot\eps)$-approximation algorithm with summary and memory
size $O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps})$ exists.

###### Proof.

We start by bounding the memory of the algorithm. Sets $A$ and $V_{d}$ always
contains at most $k$, respectively $d$, elements. Every time a new element of
the stream is considered, all the active $B_{\tau}$ contain at most $d/\eps$
elements; furthermore there are always at most
$O(\frac{1}{\eps}\log\frac{k}{\eps})$ of them. This is ensured by the
invariant that the active thresholds are smaller than $\Delta$ (by
submodularity) and larger than $\tau_{\min}.$ Overall, the memory of the
algorithm and the summary size is thus
$O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps})$.

As in the analysis of thm:robust-centralized, we now fix any set $D$ and study
the relative expected performance of our algorithm. In the pseudocode we have
introduced some auxiliary sets that are useful in the analysis: the base set
$V$ is partitioned into the elements that are considered at some point in line
13 (contained in $\Gamma$), those in the buckets or $V_{d}$ (contained in set
$B$) and the ones with low marginals (contained in set $L$). We have all the
ingredients to decompose $\OPT\cup A\cup K$ accordingly:

$\displaystyle(1-p)f(\Sopt)\leq$ $\displaystyle\E{f(\Sopt\cup A\cup K)}$
$\displaystyle=$ $\displaystyle\E{f(A\cup K)}+\E{f(\Sopt\cap L\mid A\cup K)}$
$\displaystyle+\E{f(\Sopt\cap B\mid A\cup K)}+\E{f(\Sopt\cap\Gamma\mid A\cup
K)}$ (7)

Note that the first inequality follows from the uniform sampling step and the
sampling Lemma: each fixed element belong to $A\cup K$ with a probability that
is at most $p$.

The second and third terms of the decomposition are fairly easy to bound. If
an element $e$ is added to $L$ at some point it means that its marginal
contribution with respect to the current solution $A$ is smaller than the
current estimate $\tau_{min}$ of $\eps f(\OPT)/k$ (of which it is consistently
a lower bound), by submodularity this implies that also its contribution with
respect to the final $A\cup K$ is such that $f(e|A\cup K)\leq\eps f(\OPT)/k$,
all in all:

$f(\OPT\cap L\mid A\cup K)\leq\sum_{x\in\OPT\cap L}f(x|A\cup K)\leq\eps\cdot
f(\OPT).$ (8)

We know that $\OPT\cap D=\emptyset$, this implies that $\OPT\cap B$ is
contained in $B^{\prime}$ and thus in the summary $W$ that is passed to the
second phase algorithm. Plus, note that $\OPT\cap B$ is independent because it
is contained in $\OPT$. So, if we use as $\BBAlg$ a routine for centralized
submodular maximization with matroid constraint that guarantees a $\beta$
approximation, we have:

$\displaystyle\E{f(\Sopt\cap B\mid A\cup K)}\leq\E{f(\Sopt\cap
B)}\leq\beta\cdot\E{f(S)}.$ (9)

At this point we get back to the decomposition in eq:str-decomposition and
bound the first term. We show that the value of all the elements that at some
point were in the candidate solutions, i.e.,$(A\cup K)$, is comparable to (a
constant factor of) $f(A^{\prime})$. This result handles two challenges: it
shows that the total value of the elements swapped is upper bounded by
$1/\gamma$ that of those that are not swapped, and that $A$ is indeed robust
to deletion.

It holds that $\E{f(A\cup
K)}\leq\frac{1+\eps}{1-\eps}(1+\frac{1}{\gamma})\E{f(A^{\prime})}$.

###### Proof.

As a first step, we show that $w(A)$ is close to $f(A^{\prime})$, at least in
expectation. Let $A_{\tau}$ be the subset of elements that were added into $A$
coming from $B_{\tau}$ and $A^{\prime}_{\tau}=A_{\tau}\setminus D$. Moreover,
let $a_{t}^{\tau}$ be the $t^{th}$ element added to $A_{\tau}$ (if any). We
have the following:

$\displaystyle\E{|A^{\prime}_{\tau}|}$
$\displaystyle=\E{\sum_{t=1}^{|A_{\tau}|}\mathbbm{1}(a_{t}^{\tau}\not\in
D)}=\sum_{t=1}^{+\infty}\E{\mathbbm{1}(a_{t}^{\tau}\not\in
D)\cdot\mathbbm{1}(|A_{\tau}|\geq t)}$
$\displaystyle=\sum_{t=1}^{+\infty}\E{\mathbbm{1}(a_{t}^{\tau}\not\in
D)\big{|}|A_{\tau}|\geq t}\cdot{\mathbb{P}}\left(|A_{\tau}|\geq t\right)$
$\displaystyle\geq(1-\varepsilon)\sum_{t=1}^{+\infty}{\mathbb{P}}\left(|A_{\tau}|\geq
t\right)$ $\displaystyle=(1-\varepsilon)\E{|A_{\tau}|}.$

The crucial observation is that when the algorithm decides to add an element
to $A$ from $B_{\tau}$, then the probability that the element belongs to $D$
is at most $\eps.$ Let $A_{a}$ be the elements in $A$ when $a$ is added, so
that $w(a)=f(a|A_{a})$. Moreover $I(a)$ is the indicator variable of the event
$a\in A^{\prime}$ given that $a\in A$. We have

$w(A)=\sum_{\tau\in T}\sum_{a\in A_{\tau}}w(a)\text{, while
}w(A^{\prime})=\sum_{\tau\in T}\sum_{a\in A_{\tau}}I(a)\cdot w(a)$

We know that the weight of an element $a$ coming from $B_{t}$ is such that
$\tau\leq w(a)\leq(1+\eps)\cdot\tau$. Therefore we can proceed similarly to
what we had in lem:robustness:

$\displaystyle\E{w(A^{\prime})}$ $\displaystyle=\E{\sum_{\tau\in T}\sum_{a\in
A_{\tau}}I(a)\cdot w(a)}=\sum_{\tau\in T}\E{\sum_{a\in A_{\tau}}I(a)\cdot
w(a)}\geq\sum_{\tau\in T}\tau\cdot\E{\sum_{a\in A_{\tau}}I(a)}$
$\displaystyle=\sum_{\tau\in
T}\tau\cdot\E{|A^{\prime}_{\tau}|}\geq(1-\varepsilon)\cdot\sum_{\tau\in
T}\tau\cdot\E{|A_{\tau}|}\geq\frac{(1-\varepsilon)}{(1+\varepsilon)}\E{w(A)}.$
(10)

Now, let’s move our attention to $w(A)+w(K)$. Using the properties as in
lem:killed_elements of the weight function we have that

$\displaystyle\E{f(A\cup K)}$ $\displaystyle\leq\E{w(A\cup K)}$ (Property
(iii)) $\displaystyle=\E{w(A)+w(K)}$ (Linearity of $w$)
$\displaystyle\leq\left(1+\frac{1}{\gamma}\right)\E{w(A)}$ (Property (i))
$\displaystyle\leq\left(1+\frac{1}{\gamma}\right)\frac{1+\eps}{1-\eps}\cdot\E{w(A^{\prime})}$
(Due to (10))
$\displaystyle\leq\left(1+\frac{1}{\gamma}\right)\frac{1+\eps}{1-\eps}\cdot\E{f(A^{\prime})}$
(Property (ii))
$\displaystyle\leq\left(1+\frac{1}{\gamma}\right)\frac{1+\eps}{1-\eps}\cdot\E{f(S)}$
(11)

We are left with bounding the marginal contribution of elements in
$\OPT\cap\Gamma$ with respect to $A\cup K$. $\Gamma\setminus(A\cup K)$ is
partitioned into two disjoint sets: $F$ that is the set of all the elements
that failed the swapping test (line 21) and $R$ that is the set of all the
elements that were removed because of sampling either in line 18 or 23.

Choosing $p=1/(\gamma+2)$, it holds that

$\E{f(\Sopt\cap\Gamma\mid A\cup
K)}\leq(1+\gamma)\frac{1+\eps}{1-\eps}\cdot\E{f(S)}.$

###### Proof.

Let $g$ be any element in $\OPT\cap\Gamma$, and fix any compatible story
$\cE_{g}$ of the algorithm up to the point when $g$ is considered in line 13
of alg:streaming-phase-I. The story $\cE_{g}$ deterministically induces the
candidate solution $A_{g}$ when $g$ is considered. If $g$ is not in $F$, i.e.
it is possible to either add it directly or swap it with some $k_{g}\in A_{g}$
such that $f(g\mid A_{g})=w(g)\geq(1+\gamma)w(k_{g})$, then we have two cases:
either $g$ is successfully sampled and swapped with some element in the
current candidate solution $A_{g}$, or $g$ is added to $R$ and discarded.
Conditioning on $\cE_{g}$, we have:

$p\cdot\E{\ind{g\in
R}w(g)\mid\cE_{g}}=p\cdot(1-p)\E{w(g)\mid\cE_{g}}=(1-p)\cdot\E{\ind{g\in A\cup
K}w(g)\mid\cE_{g}}.$

Summing over all such $g$ and taking the expectation over all the compatible
$\cE_{g}$, we get:

$p\cdot\E{w(\OPT\cap R)}=(1-p)\cdot\E{w(\OPT\cap(A\cup K))}.$ (12)

We now move our attention to the elements in $\OPT\cap F$, i.e., the good
elements in $\OPT$ that have been discarded because of the matroid constraint.
As a first step we show the existence of the injection
$h:(\OPT\cap\Gamma)\setminus R\to A$ with the following properties:

  * $(a)$

$h$ restricted to $A\cap\OPT$ is the identity

  * $(b)$

$w(g)\leq(1+\gamma)w(h(g))$ for all $g\in\OPT\cap F$

  * $(c)$

$w(g)\leq w(h(g))$ for all $g\in(\OPT\cap K)$

We prove the existence of such $h$ by constructing a suitable graph $G$ where
we then apply lem:graph. The nodes of $G$ are the elements of $\Gamma$, while
the edges are created iteratively as the algorithm considers elements in $A$.
Let $u$ be a generic element arriving in $\Gamma\setminus R$, and let $A_{u}$
be the candidate solution at that point. If $A_{u}+u\in\cM$, then no edge is
created at that iteration, otherwise, there exists a unique cycle $C(A_{u}+u)$
in $A_{u}+u$ containing $u$. Now, we have two cases, either $u$ is swapped
with some element $x$ in $C(A_{u}+u)\cap A_{u}$, in which case we create
directed edges from $x$ to each element in $C(A_{u}+u)-x$, or $u$ is rejected.
In the latter case, we create directed edges from $u$ to each element in
$C(A_{u}+u)-u$. Note that, in both cases, the out-neighborhood of the node
that gets discarded spans the element corresponding to the node itself. It is
also clear that the graph $G$ generated at the end of the procedure is
acyclic, as an out-edge is only created when an element is discarded towards
elements that have not been discarded yet. Thus, the graph respects the
assumption of lem:graph and there exists an injective function $h$ such that,
every vertex/element $u\in(\OPT\cap\Gamma)\setminus R$ is associated with a
sink $h(u)$ that is reachable from $u$. From a different perspective, this $h$
is a charging function that associates each element in
$(\OPT\cap\Gamma)\setminus R$ with an element in the final solution $A$ that
_accounts_ for it. It is easy to see that $h$ respects the three properties we
want to enforce. $h$ restricted to $A\cap\OPT$ is the identity as elements in
$A$ are sinks. Consider now any element $g\in\OPT\cap F$, this is an element
that has been discarded without being added to the solution, this means that
outgoing edges from $g$ are such that $w(g)\leq(1+\gamma)w(u)$, for all
$u\in\delta^{+}(g).$ If we focus on the unique path from $g$ to $h(g)$, we see
that after the first step, when the weight decreases by at most a $(1+\gamma)$
factor, all the following edges do not decrease the weight, this is because an
outgoing edge from an element of the solution either points to an element it
is swapped with (whose weight is larger by at least a $(1+\gamma)$ factor) or
to another element in the solution but with larger weight (as we swap the
element with smallest weight in the cycle). The same argument clearly implies
that, for all the elements already in the solution that are later swapped,
i.e. in $\OPT\cap K$, it holds that the weight does not decrease along the
path to the associated sink. We can use the properties of the injective
function $h$ to bound $w(\OPT\cap F)$.

$\displaystyle\mathbb{E}$ $\displaystyle[w(\OPT\cap
F)]\leq(1+\gamma)\E{w(h(\OPT\cap F))}$ Property $(b)$
$\displaystyle\leq(1+\gamma)\E{w(h(\OPT\cap F))+w(h(\OPT\cap K))-w(\OPT\cap
K))}$ Property $(c)$ $\displaystyle=(1+\gamma)\E{w(h(\OPT\cap(F\cup
K))-w(\OPT\cap K)+w(\OPT\cap A)-w(\OPT\cap A)}$
$\displaystyle=(1+\gamma)\E{w(h((\OPT\cap\Gamma)\setminus R))-w(\OPT\cap(A\cup
K)))}$ Property $(a)$
$\displaystyle\leq(1+\gamma)\E{w(A)}-(1+\gamma)(w(\OPT\cap(A\cup K)))$ (13)

Observe that in the last inequality we use that $w(a)\geq 0$ for all $a\in A$,
as $h((\OPT\cap\Gamma)\setminus R)$ may be a strict subset of $A.$ We can
finally proceed to prove the Lemma.

$\displaystyle\mathbb{E}[f(\Sopt\cap\Gamma$ $\displaystyle\mid A\cup
K)]\leq\E{\sum_{x\in\Sopt\cap F}f(x|A\cup K)}+\E{\sum_{x\in\Sopt\cap
R}f(x|A\cup K)}$ $\displaystyle\leq$ $\displaystyle\E{w(\Sopt\cap
F)}+\E{w(\Sopt\cap R)}$ $\displaystyle\leq$
$\displaystyle(1+\gamma)\E{w(A)}+\left(\frac{1-p}{p}-1-\gamma\right)\E{w(\OPT\cap(A\cup
K))}$ By (12) and (13) $\displaystyle=$ $\displaystyle(1+\gamma)\E{w(A)}$ By
the choice of $p$ $\displaystyle\leq$
$\displaystyle(1+\gamma)\frac{1+\eps}{1-\eps}\cdot\E{f(S)}.$ As in
lem:streaming_robust

Note that the first two inequalities follow from submodularity and the fact
that the candidate solution when an element is considered (and thus that is
used to compute its weight) is always contained in $A\cup K$.

Plugging eq:str-small-els,eq:str-AcupK,eq:str-OPTcapB,eq:str-swapping into
eq:str-decomposition we obtain the following:

$\displaystyle\left(1-\frac{1}{2+\gamma}\right)f(\Sopt)\leq$
$\displaystyle\E{f(A\cup K)}+\E{f(\Sopt\cap L|A\cup K)}$
$\displaystyle+\E{f(\Sopt\cap B|A\cup K)}+\E{f(\Sopt\cap\Gamma|A\cup K)}$
$\displaystyle\leq$
$\displaystyle\left[\left(2+\gamma+\frac{1}{\gamma}\right)\frac{1+\eps}{1-\eps}+\beta\right]\cdot\E{f(S)}+\eps\cdot
f(\OPT)$

Rearranging terms, one gets

$\displaystyle f(\OPT)$
$\displaystyle\leq\left(1-\eps-\frac{1}{2+\gamma}\right)^{-1}\left[\left(2+\gamma+\frac{1}{\gamma}\right)\frac{1+\eps}{1-\eps}+\beta\right]\cdot\E{f(S)}$
$\displaystyle=\frac{(2+\gamma)[\gamma^{2}+(\beta+2)\gamma+1+\eps(\gamma^{2}+(2-\beta)\gamma+1)]}{\gamma(1-\gamma)(1-\eps)[1+\gamma-\eps(\gamma+2)]}\cdot\E{f(S)}$
$\displaystyle=\frac{(2+\gamma)[\gamma^{2}+(\beta+2)\gamma+1]}{\gamma[1+\gamma-\eps(\gamma+2)]}\frac{1+\eps}{1-\eps}\cdot\E{f(S)}$

The Theorem follows by using as optimization routine the state of the art
algorithm for centralized (non-monotone) submodular maximization with matroid
constraint ($\beta\approx 2.597$ as in BuchbinderF19) and then choose $\gamma$
(and accordingly $p$) as to minimize the multiplicative factor. In particular,
if we set $\gamma\approx 1.746$, then for any fixed $\delta$ there exists a
constant $G_{\delta}$ such that we get an approximation of the form
$(9.435+G_{\delta}\cdot\eps)$ for all $\eps$ in $(0,\delta).$

As a corollary of the previous Theorem, we get an improved approximation
considering monotone objective. There is clearly no need for the sampling
procedure and we can use the greedy fisher78-II or continuous greedy
CalinescuCPV11 subroutine as $\BBAlg$. Consider the problem of deletion robust
monotone submodular maximization with matroid constraints in the streaming
setting and fix any constant $\delta\in(0,1)$, then there exists a constant
$\tilde{G}_{\delta}$ such that for any $\eps\in(0,\delta)$, in expectation a
${(5.582+\eps\cdot\tilde{G}_{\delta})}$-approximation algorithm with summary
size and memory $O(k+\frac{d}{\eps^{2}}\log\frac{k}{\eps})$ exists.

###### Proof.

The proof is similar to the one of thm:robust-streaming. The only difference
is that we do not do subsampling as $f(\OPT)$ is smaller than $f(\OPT\cup
A\cup K)$ by monotonicity. Thus, we set $p=1$ and $\gamma=1$ and then eq:str-
decomposition becomes:

$\displaystyle f(\Sopt)\leq$ $\displaystyle\E{f(\Sopt\cup A\cup K)}$
$\displaystyle=$ $\displaystyle\E{f(A\cup K)}+\E{f(\Sopt\cap L\mid A\cup K)}$
$\displaystyle+\E{f(\Sopt\cap B\mid A\cup K)}+\E{f(\Sopt\cap\Gamma\mid A\cup
K)}$ $\displaystyle\leq$ $\displaystyle 2\frac{1+\eps}{1-\eps}\E{f(S)}+\eps
f(\OPT)$ $\displaystyle+\beta\cdot\E{f(S)}+\E{f(\OPT\cap\Gamma|A\cup K)}$

For the last term, we use a more general statement. For all
$X\subseteq\Gamma,$ $X\in\cM$, then it holds that $w(X)\leq 2\cdot w(A).$ This
is a direct application of Theorem 1 of Varadaraja11 (using a single matroid
and setting $r=2$). More in specific, we can imagine to restrict the stream to
consider only the elements in $\Gamma$, with the order in which they are
considered in line 13. Choosing $X=\OPT\cap\Gamma$, we then get that

$\E{f(\OPT\cap\Gamma|A\cup K)}\leq\E{w(\OPT\cap\Gamma)}\leq 2\E{w(A)}.$

We use as optimization routine continuous greedy, therefore we can plug in
$\beta=\frac{e}{e-1}$ and, rearranging the terms we obtain

$\displaystyle f(\Sopt)$
$\displaystyle\leq\left(2\frac{1+\eps}{(1-\eps)^{2}}+\frac{3e-2}{(1-\eps)(e-1)}\right)\E{f(S)}$
$\displaystyle\leq\Big{[}\frac{e}{e-1}+4+\underbrace{\frac{9e-8-\delta(5e-4)}{(e-1)(1-\delta)^{2}}}_{\tilde{G}_{\delta}}\cdot\eps\Big{]}\E{f(S)}.$

The last inequality can be numerically verified and holds for any
$\eps\in(0,\delta).$

##  5 Conclusion and Future Work

We presented the first space-efficient constant-factor approximation
algorithms for deletion robust submodular maximization over matroids in both
the centralized and the streaming setting. In particular, we are also the
first to design space-efficient deletion robust algorithms for non-monotone
objective with any type of constraints. A natural direction for future work is
to extend these results and ideas to other constraints (e.g., multiple
matroids and knapsack), and to consider fully dynamic versions with insertions
and deletions.

## Acknowledgements

Federico Fusco’s work was partially supported by the ERC Advanced Grant 788893
AMDROMA “Algorithmic and Mechanism Design Research in Online Markets” and the
MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets.” Part of
this work was done while Federico was an intern at Google Research, hosted by
Paul Dütting.

figures/arXiv˙non˙monotone.bbl