# On the Complexity of Dynamic Submodular Maximization

Xi Chen
Columbia University
<EMAIL_ADDRESS>Binghui Peng
Columbia University
<EMAIL_ADDRESS>
###### Abstract

We study dynamic algorithms for the problem of maximizing a monotone
submodular function over a stream of $n$ insertions and deletions. We show
that any algorithm that maintains a $(0.5+\epsilon)$-approximate solution
under a cardinality constraint, for any constant $\epsilon>0$, must have an
amortized query complexity that is polynomial in $n$. Moreover, a linear
amortized query complexity is needed in order to maintain a
$0.584$-approximate solution. This is in sharp contrast with recent dynamic
algorithms of [LMNF+20, Mon20] that achieve $(0.5-\epsilon)$-approximation
with a $\operatorname{polylog}(n)$ amortized query complexity.

On the positive side, when the stream is insertion-only, we present efficient
algorithms for the problem under a cardinality constraint and under a matroid
constraint with approximation guarantee $1-1/e-\epsilon$ and amortized query
complexities $\smash{O(\log(k/\epsilon)/\epsilon^{2})}$ and
$\smash{k^{\widetilde{O}(1/\epsilon^{2})}\log n}$, respectively, where $k$
denotes the cardinality parameter or the rank of the matroid.

##  1 Introduction

Initiated by the classical work of [NWF78, NW78] in the 1970s, submodular
maximization has developed into a central topic of discrete optimization
during past decades [CCPV11, FNS11, Von13, CVZ14, BFSS15] (see [BF18] for a
survey). Capturing the natural notion of diminishing returns, submodular
functions and their optimization problems have found numerous applications in
areas such as machine learning [GK11, WIB15], data mining [LB11], algorithmic
game theory [Rou10], social networks [KKT03], etc. The canonical form of the
problem is to maximize a monotone submodular function under a cardinality
constraint $k$, for which the greedy algorithm of [NWF78] achieves the optimal
approximation ratio of $1-1/e$ [NW78, Fei98]. However, despite the simplicity
and optimality of this celebrated algorithm, there has been a surge of recent
research effort to reexamine the problem under a variety of computational
models motivated by unique challenges of working with massive datasets. These
include streaming algorithms [BMKK14, FNFSZ20], parallel algorithms [BS18a,
BRS19a, EN19, FMZ19, BRS19b, CQ19, ENV19], learning algorithms [BH11, BRS17]
and distributed algorithms [BENW15, MZ15, BENW16].

Dynamic submodular maximization. We study the power and limitations of
_dynamic_ algorithms for submodular maximization. In this model, the set of
elements that one can choose from is subject to changes incurred by a stream
of $n$ insertions and deletions. Letting $V_{t}$ denote the current set of
elements after the first $t$ operations, an algorithm needs to maintain a
subset $S_{t}\subseteq V_{t}$ of size at most $k$ that achieves a certain
approximation guarantee for every round $t$, and its performance is measured
by its amortized query complexity (i.e., the average number of queries it
makes per operation on the underlying unknown monotone submodular function);
see the formal definition of the model in Section 2.

The dynamic model is motivated by real-world applications of submodular
maximization over massive datasets that evolve frequently. Many of these
applications arise in machine learning and data mining tasks, including the
data subset selection problem [WIB15, GK11], movie recommendation system
[BS18b], influence maximization in social networks [KKT03], etc. As an
example, in influence maximization, one is given a social network as well as a
stochastic diffusion model, and the goal is to select a seed set of size at
most $k$ to maximize the influence spread over the network. The spread
function is submodular for many well-studied models and therefore, the problem
becomes submodular maximization with a cardinality constraint. Given that
social networks, like Twitter or Facebook, are involving continuously over
time, an old seed set could become outdated quickly. A natural rescue is to
have an efficient dynamic algorithm that maintains a seed set over time.

The problem of dynamic submodular maximization under a cardinality constraint
was studied in two recent papers [Mon20, LMNF+20], giving algorithms that
achieve an $(1/2-\epsilon)$-approximation guarantee with amortized query
complexities that are $O(k^{2}\log^{2}n\cdot\epsilon^{-3})$ and
$O(\log^{8}n\cdot\epsilon^{-6})$ in a stream of length $n$. Compared with the
$1-1/e$ approximation guarantee of the offline greedy algorithm, however, a
natural open question posted by [LMNF+20] is whether the $1/2$ can be further
improved under the dynamic setting, or even under the setting when the stream
is insertion-only.

###  1.1 Our results

We resolve the open question of [LMNF+20] by showing that any algorithm with
an approximation ratio of $1/2+\epsilon$ must have amortized query complexity
polynomial in the stream length $n$:

######  Theorem 1.1.

For any constant $\epsilon>0$, there is a constant $C_{\epsilon}>0$ with the
following property. When $k\geq C_{\epsilon}$, any randomized algorithm that
achieves an approximation ratio of $1/2+\epsilon$ for dynamic submodular
maximization under cardinality constraint $k$ requires amortized query
complexity $\smash{n^{\widetilde{\Omega}(\epsilon)}/k^{3}}$.

Moreover, we show that any algorithm with approximation ratio $0.584$ must
have an amortized query complexity that is linear in $n$:

######  Theorem 1.2.

There is a constant $C>0$ with the following property. When $k\geq C\log n$,
any randomized algorithm for dynamic submodular maximization under cardinality
constraint $k$ that obtains an approximation guarantee of $0.584$ must have
amortized query complexity at least $\Omega(n/k^{3})$.

In the proof of both theorems we construct a family of hard functions to hide
a secret matching. The main challenge is to achieve the following two
properties at the same time: The first one, which we will refer to as the
_large-gap_ property, states that any dynamic algorithm with a certain
approximation guarantee can only succeed by recovering the secret matching
hidden in the function. On the other hand, the second so-called
_indistinguishability_ property shows that each query made by an algorithm can
only reveal very little information about the secret matching. The
construction for Theorem 1.2 uses a simple bipartite structure but requires a
more detailed analysis to optimize for the constant $0.584$. The construction
for Theorem 1.1, on the other hand, is based on a more sophisticated
$(1/\epsilon)$-level tree structure which, at a high level, can be viewed as a
novel tree extension of the path-alike construction from [FNFSZ20]. We discuss
in more details about our lower bound proofs in Section 1.3.

On the positive side, when the stream is insertion only, we obtain an
algorithm that achieves an approximation guarantee of $1-1/e-\epsilon$ with
amortized query complexity $O(\log(k/\epsilon)/\epsilon^{2})$:

######  Theorem 1.3.

Given any $\epsilon>0$, there is a deterministic algorithm that achieves an
approximation guarantee of $1-1/e-\epsilon$ for dynamic submodular
maximization under cardinality constraint $k$ over insertion-only streams. The
amortized query complexity of the algorithm is
$O(\log(k/\epsilon)/\epsilon^{2})$.

We also obtain a randomized algorithm that achieves an approximation guarantee
of $1-1/e-\epsilon$ for the problem under a matroid constraint, with amortized
query complexity $\smash{k^{\widetilde{O}(1/\epsilon^{2})}\log n}$.

######  Theorem 1.4.

Given any $\epsilon>0$, there is a randomized algorithm that achieves an
approximation guarantee of $1-1/e-\epsilon$ for dynamic submodular
maximization under matroid constraints over insertion-only streams. The
amortized query complexity of the algorithm is
$\smash{k^{\widetilde{O}(1/\epsilon^{2})}\log n}$, where $k$ is the rank of
the matroid.

Our algorithms are inspired by the classic greedy solution and we turn it into
a dynamic algorithm via techniques involving lazy update, multilinear
extension and accelerated continuous greedy, together with the introduction of
a $O(1/\epsilon)$-pass prune-greedy algorithm that could be of independent
interests. We elaborate more details about the intuition behind our algorithms
in Section 1.3.

######  Remark 1.5.

The best offline algorithm for maximizing monotone submodular function with
cardinality constraints requires $O(n\log(1/\epsilon))$ queries [BFS17]. Our
dynamic algorithm incurs only poly-logarithmic overheads. While for matroid
constraints, even the state-of-art offline algorithm requires $O(nk)$ queries,
with additional $O(k^{2})$ queris to round the fractional solution [BV14].
Hence, for matroid constraints, our focus is to design dynamic algorithms with
$\operatorname{poly}(k)$ amortized query complexity.

We review related work and then give a technical overview of our results in
Section 1.3.

###  1.2 Related work

Dynamic submodular maximization has only been studied recently, and the work
of [Mon20, LMNF+20] are most relavant to us. The concurrent work of [Mon20]
and [LMNF+20] give $(1/2-\epsilon)$-approximation algorithm to the dynamic
submodular maximization problem under cardinality constraints, with amortized
query complexity $O(k^{2}\log^{2}n\cdot\epsilon^{-3})$ and
$O(\log^{8}n\cdot\epsilon^{-6})$ respectively.

Our work is also closely related to the streaming setting. For cardinality
constraints, [BMKK14] give an $(1/2-\epsilon)$-approximation algorithm in the
streaming model, The approximiation is tight, Feldman et al. [FNFSZ20] prove
$\Omega(\epsilon n/k^{3})$ space is necessary for achieving $(1/2+\epsilon)$
approximation. For matroid contraints, [CGQ15] give an $1/4$-approximation
algorithm. We remark the algorithm of [BMKK14] and [CGQ15] can be adapted to
the insertion-only dynamic setting with the same approximation guarantee, and
the amortized runing query complexity are $O(\epsilon^{-1}\log(k/\epsilon))$
and $O(k)$ respectively.

On lower bound side, our work make use of the symmetric gap techniques of
[MSV08, Von13] and the weight scheduling of [FNFSZ20].

###  1.3 Technical overview

We provide a streamlined technique overview of our approach.

A linear lower bound for $0.584$-approximation. Our lower bound is based on
the construction of a family of monotone submodular functions with the
following properties. They share the same ground set $V$ which is partitioned
into $2m$ sets $V=A_{1}\cup\cdots\cup A_{m}\cup B_{1}\cup\cdots\cup B_{m}$ and
the algorithm knows both $V$ and the partition. Each $A_{i}$ or $B_{j}$
contains $O(k)$ elements to be specified later. What is hidden inside the
function is a secret bijection $\pi:[m]\rightarrow[m]$, which is unknown to
the algorithm, and we write the function as
$\mathcal{F}_{\pi}:2^{V}\rightarrow[0,1]$. The three main properties we need
about $\mathcal{F}$ are:

  1. i)

For any $j\in[m]$, there is an $S\subseteq A_{\pi(j)}\cup B_{j}$ of size $k$
that achieves the optimal $\mathcal{F}_{\pi}(S)=1$;

  2. ii)

Large gap: For any $j\in[m]$, every $S\subseteq A_{1}\cup\cdots\cup A_{m}\cup
B_{j}$ of size at most $k$ has $\mathcal{F}_{\pi}(S)\leq\kappa$ for some (as
small as possible) parameter $\kappa>0$, unless $S\cap
A_{\pi(j)}\neq\emptyset;$ and

  3. iii)

Indistinguishability: Every query made by the algorithm reveals very little
information about $\pi$. (Looking ahead, we show that each query on
$\mathcal{F}_{\pi}$ is roughly equivalent to no more than $O(k)$ queries on
$\pi$, each of the limited form as “whether $\pi(a)$ is equal $b$ or not.”)

With these properties in hand, we use the following simple dynamic stream of
length $\Theta(mk)$ in our lower bound proof: $A_{1},\ldots,A_{m}$ are
inserted first and then we insert $B_{1}$, delete $B_{1}$, insert $B_{2}$,
delete $B_{2},\ldots$, until $B_{m}$ is inserted and deleted. The large-gap
property (ii) ensures that any algorithm with an approximation guarantee of
$\kappa$ must recover each entry $\pi(j)$ of the hidden $\pi$ after each set
$B_{j}$ is inserted.111Note that we are a bit sloppy here given that the
dynamic algorithm only needs to output a set $S_{j}$ after $B_{j}$ is inserted
to overlap with $A_{\pi(j)}$. But given that $|S_{j}|\leq k$, this can be
considered almost as good as knowing $\pi(j)$. The indistinguishability
property (iii), on the other hand, shows that $\Omega(m^{2}/k)$ queries are
needed to recover the hidden bijection $\pi$ (by a standard calculation) and
thus, the amortized query complexity is at least
$\Omega(m/k^{2})=\Omega(n/k^{3})$ by plugging in the stream length
$n=\Theta(mk)$. The main challenge is to find a construction that satisfies
(i) and (iii) and at the same time satisfies (ii) with a parameter $\kappa$
that is as small as possible (optimized to be $0.584$ at the end).

We focus on minimizing $\kappa$ in the large-gap property (ii) in this part,
given that achieving the indistinguishability (iii) will become more
challenging in the polynomial lower bound for $(0.5+\epsilon)$-approximation
later and will be what we focus on there. Our first attempt is the following
simple coverage function $\mathcal{F}$ (though our final construction will not
be a coverage function). Let $U$ be a large universe set (for intuition
consider $U$ to be arbitrarily large so that every expectation about random
sets we draw holds exactly). For each $j\in[m]$ we randomly partition $U$ into
two parts $U_{j,1}$ and $U_{j,2}$ of the same size: the union of elements of
$A_{\pi(j)}$ (which correspond to subsets of $U$) will be $U_{j,1}$ and the
union of elements of $B_{j}$ will be $U_{j,2}$. Each $B_{j}$ is further
partitioned into $w$ groups $B_{j,1},\ldots,B_{j,w}$, where $w$ is a large
enough constant, such that each $B_{j,\ell}$ has size $k/2$ and corresponds to
an even $(k/2)$-way random partition of $U_{i,2}$. The same happens with
$A_{\pi(j)}$. Now imagine that the algorithm does not know $\pi(j)$ and
returns $S\subset A_{i}\cup B_{j}$ with $i\neq\pi(j)$ by picking $k/2$
elements randomly from $A_{i}$ and $k/2$ elements randomly from $B_{j}$.
Simple calculation shows that elements in $S$ would together cover
$0.5(1-1/e)+0.25(1-1/e^{2})\approx 0.53$, which is very close to our goal of
$0.5$, and splitting elements not evenly between $A_{i}$ and $B_{j}$ can only
cover less.

However, the algorithm can deviate by (1) not picking elements randomly from
$A_{i}$ and $B_{j}$ and furthermore, (2) picking from not just $A_{i}\cup
B_{j}$ but also the much bigger set of $A_{1}\cup\cdots\cup A_{m}$. For (1),
if the algorithm manages to find out all $k/2$ elements of group $A_{i,\ell}$
and all $k/2$ elements of group $B_{j,\ell^{\prime}}$ for some
$\ell,\ell^{\prime}$, then together they would cover $3/4$. For (2), the
algorithm can pick one random element each from $k$ different $A_{i}$’s to
cover $1-1/e$. In our final construction, we overcame (1) by applying a
symmetric function constructed from [MSV08] on top of the coverage function
above. It guarantees that no algorithm (with a small number of queries) can
ever pick a set of elements from any of $A_{i}$ or $B_{j}$ that is non-
negligibly “ _unbalanced_ ,” by having noticeably more elements from any group
$A_{i,\ell}$ or $B_{j,\ell}$ than the average among $A_{i}$ or $B_{j}$.
Accordingly, the large-gap property (ii) needed can be updated to be the
following weaker version:

  1. ii)

Large gap, updated: For any $j\in[m]$, every “balanced” $S\subseteq
A_{1}\cup\cdots\cup A_{m}\cup B_{j}$ of size at most $k$ has
$\mathcal{F}_{\pi}(S)\leq\kappa$ for some parameter $\kappa>0$, unless $S\cap
A_{\pi(j)}\neq\emptyset;$

To address the challenge of (2), we use two parameters to introduce a
different type of _unbalancedness_ : First, $U$ is no longer partitioned
$50$-$50$; instead $U_{j,1}$ is $\beta$-fraction and $U_{j,2}$ is
$(1-\beta)$-fraction of $U$. Second, it is no longer the case that all groups
$A_{i,\ell}$ and $B_{j,\ell}$ have size $k/2$; instead every $A_{i,\ell}$ has
size $\alpha k$ and every $B_{j,\ell}$ has size $(1-\alpha)k$. With a detailed
analysis we show that $\kappa$ can be set to $0.584$ in the updated version of
the large-gap property (ii), when $\alpha=0.56$ and $\beta=0.42$.

A polynomial lower bound for $(1/2+\epsilon)$-approximation. Hard instances
for our linear lower bound sketched earlier reduce at the end to a simple
problem of recovering a hidden matching. To obtain a polynomial lower bound
for $(1/2+\epsilon)$-approximation, we need to further extend the idea to
amplify the (hardness of) approximation ratio by creating a depth-$L$ tree
structure with $L=1/\epsilon$ to hide multiple bijections at every level. Let
$m_{1},\ldots,m_{L}$ be a sequence of positive integers: $m_{L}=1$ but the
other integers will be specified at the end. The ground set $V$ is then
defined using a depth-$L$ tree $T$, in which each internal node at depth
$\ell$ ($\ell\in[0:L-1]$) has $m_{\ell+1}$ children. Let $U_{\ell}$ denote the
set of nodes $u=(u_{1},\ldots,u_{\ell})\in[m_{1}]\times\cdots\times[m_{\ell}]$
at depth $\ell$; its children are given by $(u,1),\ldots,$ $(u,m_{\ell+1})$.
The ground set is defined as $V=\cup_{u\in U_{1}\cup\cdots\cup U_{L}}A_{u}$,
where each $A_{u}$ contains $\epsilon k$ elements.

In the dynamic update stream, we perform a limited DFS walk on the tree,
meaning that after reaching a node $u$, one only explores the first
$d:=n^{\epsilon}$ children $(u,1),\ldots,(u,d)$ of $u$ (except when $u$ is at
depth $L-1$ in which case we just explore the only child of $u$). Let
$U_{L}^{*}:=[d]^{L-1}\times\\{1\\}$ be the set of leaves visited by the DFS
walk. We design the stream in a way such that whenever a leaf $u$ is reached,
the current set of elements is given by

$W_{u}:=\bigcup_{\ell\in[1:L]}\bigcup_{i\in[m_{\ell}]}A_{u_{1},\ldots,u_{\ell-1},i},$

i.e., the union of sets of nodes that are children of any node along the path
from the root to $u$. Let $\mathcal{A}_{u}=A_{u_{1}}\cup\cdots\cup
A_{u_{1},\ldots,u_{L-1}}$. The first two properties of our
$\mathcal{F}:2^{V}\rightarrow[0,1]$ can now be stated:

  1. i)

Let $S=\mathcal{A}_{u}\cup A_{u}$. We have $|S|=k$ and $\mathcal{F}(S)$
achieves the optimal $\mathcal{F}(S)=1$;

  2. ii)

Large gap: For any $S\subseteq W_{u}$ of size at most $k$,
$\mathcal{F}(S)<1/2+\epsilon$ unless $S\cap\mathcal{A}_{u}\neq\emptyset.$

At a high level, the construction of our monotone submodular function
$\mathcal{F}$ can be viewed as a novel tree extension of a path-alike
construction from [FNFSZ20] (for one-way communication complexity of
submodular maximization). In particular, we adopted a weight sequence
$\\{w_{\ell}\\}$ from [FNFSZ20] to play the role of parameter $\beta$ in our
linear lower bound discussed earlier, in order to achieve the large-gap
property (ii) above no matter how the $S$ is spread among different levels of
the tree.

Now $\mathcal{F}$ is only the base function that we use to construct the
family of hard functions. To this end, we introduce the notion of a
_shuffling_ $\pi$ of tree $T$, which consists of one bijection $\pi_{u}$ at
every internal node $u$ of $T$ to shuffle its children. Let
$\mathcal{F}_{\pi}$ be the function obtained after applying a hidden shuffling
$\pi$ on $\mathcal{F}$. Under the same stream, at the time when a leaf $u\in
U_{L}^{*}$ is arrived, the current set of elements remains to be $W_{u}$ but
the $\mathcal{A}_{u}$ we care about becomes

$\mathcal{A}_{u}^{\pi}:=A_{\pi_{\gamma}(u_{1})}\cup
A_{u_{1},\pi_{u_{1}}(u_{2})}\cup\cdots\cup
A_{u_{1},\ldots,u_{L-2},\pi_{u_{1},\ldots,u_{L-2}}}(u_{L-1}),$

where $\pi_{\gamma}$ denotes the hidden bijection at the root, $\pi_{u_{1}}$
denotes the hidden bijection at the depth-$1$ node $u_{1}$, so on and so
forth. The two properties (i) and (ii) hold after replacing $\mathcal{A}_{u}$
using $\mathcal{A}_{u}^{\pi}$. So finding $S\subseteq W_{u}$ of size at most
$k$ with $\mathcal{F}(S)\geq 1/2+\epsilon$ requires the algorithm to
(essentially) identify one of the edges along the path after shuffling, i.e.,
one of the entries
$\pi_{\epsilon}(u_{1}),\pi_{u_{1}}(u_{2}),\ldots,\pi_{u_{1},\ldots,u_{L-2}}$
$(u_{L-1})$ in the hidden bijections. The challenge left is to establish the
indistinguishability property:

  1. iii)

Indistinguishability: Every query made by the algorithm reveals very little
information about $\pi$. (More formally, we show that each query on
$\mathcal{F}_{\pi}$ is roughly equivalent to no more than $O(k^{2})$ queries
on $\pi$, each of the limited form as “whether $\pi_{u}(a)$ for some $u$ is
equal $b$.”

With (iii) if an algorithm tries to win by finding out
$\pi_{u_{1},\ldots,u_{L-2}}(u_{L-1})$ every time a leaf $u$ is reached then
each hidden entry requires $\Omega(m_{L-1}/k^{2})$ queries and thus,
$\Omega(m_{L-1}d^{L-1}/k^{2})$ queries in total. In general if an algorithm
keeps working on $\pi_{u_{1},\ldots,u_{\ell}}(u_{\ell+1})$, the total number
of queries needed is $\Omega(m_{\ell+1}d^{\ell+1}/k^{2})$. Setting
$m_{\ell}=n^{(L-\ell+1)\epsilon}/(2k)$ for each $\ell$ leads to a lower bound
of $\Omega(n^{1+\epsilon}/k^{3})$ for the total query complexity in all cases,
while maintaining the stream length to be $n$. (It is also not difficult to
show that mixing effort among different levels does not help.)

Finally let’s discuss how the indistinguishability property (iii) is
implemented. The first trick is to cap the function and have the final
function take the form as

$\mathcal{F}_{\pi}^{*}(S)=\min\big{\\{}\mathcal{F}_{\pi}(S)+\epsilon|S|/k,1\big{\\}}.$

This simple modification changes the value of solutions $S$ we care about
slightly, no more than $\epsilon$, given that $|S|\leq k$, and at the same
time guarantees no algorithm makes any query of size more than $k/\epsilon$;
otherwise the value returned is trivially $1$ and reveals no information. This
implies that each query $S$ made by an algorithm can only involve no more than
$k/\epsilon$ nodes in the tree; let $U_{S}$ denote the set of such nodes. A
final key observation is that the function $\mathcal{F}_{\pi}$ on $S$ is
uniquely determined by the structure of the tree formed by paths of nodes in
$U_{S}$ to the root after applying the shuffling $\pi$. The latter is uniquely
determined by the depth of the lowest common ancestor of every pair of nodes
in $U_{S}$ after shuffling $\pi$, which in turn can be obtained by making at
most one query to $\pi$ of the form described in (iii) for each pair in
$U_{S}$. The bound $O(k^{2})$ follows given that $|U_{S}|\leq k/\epsilon$.

Insertion-only streams: Submodular maximization with a cardinality constraint.
Our starting point is the classic (offline) greedy approach, where in each
round an element with the maximum marginal contribution is added to the
solution set. We adapt the greedy algorithm to the dynamic setting. For
simplicity, let’s assume in the overview that a value $\operatorname{OPT}$ is
given to the algorithm at the beginning and its goal is to maintain a set that
achieves a $(1-1/e-\epsilon)$-approximation when the actual optimal value
reaches $\operatorname{OPT}$. While it is impossible to find the element with
the maximum margin before having all of them in hands, we can instead choose
one whose margin gives a moderate improvement, i.e., add any element that
satisfies $f_{S}(e)\geq({\operatorname{OPT}-f(S)})/{k}$, where $S$ is the
current solution set. This suffices to achieve the optimal
$(1-1/e)$-approximation. A naive implementation, however, requires $O(k)$
amortized query complexity since the threshold
$({\operatorname{OPT}-f(S)})/{k}$ is updated every time a new element is added
to solution set, and the algorithm needs to scan over all elements in the
worst case. We circumvent this with the idea of lazy update. We divide the
mariginal contribution into $O(1/\epsilon)$ buckets, with the $i$-th buckets
containing marignal smaller than $i\cdot({\epsilon\operatorname{OPT}}/{k})$.
We don’t update the margin value every time the solution set is augmented.
Instead, each time a new element is inserted, the algorithm only checks the
bucket whose marginal is larger than the current threshold. One can show
either a new element is added to $S$, or it is pushed down to the next level.
The latter can happen at most $O(1/\epsilon)$, and after that, the element has
negligible marginal contribution that can be ignored safely.

Insertion-only streams: Submodular maximization with a matroid constraint. We
first provide a deterministic combinatorial algorithm that achieves a
$(1/2-\epsilon)$-approximation. We build upon the previous idea, but with
significant adaptations. Again, our goal is to simulate an offline greedy
algorithm but this time, one cannot relax the condition and hope to augment
the solution set whenever the margin has a moderate improvement. The analysis
of the offline greedy algorithm relies crucially on picking the maximum margin
element in each step. Our first idea is to find the element with approximate
maximum margin and branching over all possibilities. In particular, we divide
the marginal gain into $L=O(\epsilon^{-1}\log(k/\epsilon))$ many levels, where
the $\ell$-th level corresponds to
$[(1+\epsilon)^{-\ell+1}\operatorname{OPT},(1+\epsilon)^{-\ell}\operatorname{OPT}]$.
When working on an insertion-only stream, we proceed to the $(\ell+1)$-th
level only when there is no element in the $\ell$-th level anymore. Of course,
we still don’t know when the $\ell$-th level becomes empty so that we can move
to $\ell+1$, but we can enumerate over all possibilities and guarantee that
there exists one branch that fits the sequence of the offline approximate
greedy algorithm. The caveat is that the total number of branch is
$\binom{k}{L}$, which is quasi-polynomial in $k$. We further reduce this
number by considering a pruned version of the offline approximate greedy
algorithm, where the algorithm prunes extra element in each level and only
keeps the majority. We prove the algorithm still guarantees a
$(1/2-\epsilon)$-approximation and the total number of branch reduces to
$\smash{k^{\widetilde{O}(1/\epsilon)}}$. It requires careful analysis to make
the idea work, but the very high level intuition is that one needs to be more
careful in the first few buckets (since the marginal is large) and less
careful at the end. To amplify the approximation ratio to $(1-1/e-\epsilon)$,
we make use of the multi-linear extension and use the accelerated continuous
greedy framework [BV14]. In each iteration, we use the above combinatorial
algorithm to find the direction of improvement of the multi-linear extension.
We remark a similar amplifying procedure has been used in the previous work on
adaptive submodular maximization [CQ19, BRS19b].

Organization. We begin by presenting the linear lower bound for
0.584-approximation under fully dynamic stream in Section 3. Section 4 is
devoted to prove the polynomial lower bound on $(1/2+\epsilon)$-approximation.
We then turn to the insertion-only stream and provide our algorithms and
analysis. The algorithm for a cardinality constraint is presented in Section
5, and we provide an efficient $(1-1/e)$-approximation algorithm for a matroid
constraint in Section 6. We discuss future reserach directions in Section 7.

##  2 Preliminary

Submodular functions. Let $V$ be a finite ground set. A function
$f:2^{V}\rightarrow\mathbb{R}$ is _submodular_ if

$f(S\cup T)+f(S\cap T)\leq f(S)+f(T)$

for all pairs of sets $S,T\subseteq V$. We say $f$ is _nonnegative_ if
$f(S)\geq 0$ for all $S\subseteq V$ and $f$ is _monotone_ if $f(S)\leq f(T)$
whenever $S\subseteq T\subseteq V$. We study submodular functions that are
both nonnegative and monotone, and assume without loss of generality that
$f(\emptyset)=0$ (see Remark 2.2). We say an algorithm has query access to $f$
if it can adaptively pick subsets $S\subseteq V$ to reveal the value of
$f(S)$.

Given $f:2^{V}\rightarrow\mathbb{R}$ and $S,T\subseteq V$, the marginal gain
of adding $e$ to $S$ is defined as

$f_{S}(T):=f(S\cup T)-f(S).$

When $T=\\{e\\}$ is a singleton, we write $f_{S}(e)$ to denote
$f_{S}(\\{e\\})$ for convenience. Monotonicity and submodularity can be
defined equivalently using marginal gains: $f$ is monotone iff $f_{S}(e)\geq
0$ for all $e\in V$ and $S\subseteq V$; $f$ is submodular iff $f_{S}(e)\geq
f_{T}(e)$ for any $e\notin T$ and $S\subseteq T\subseteq V$.

Dynamic submodular maximization under a cardinality constraint.  Given $V$, a
positive integer $k$ and query access to a nonnegative, monotone submodular
function $f:V\rightarrow\mathbb{R}$, the goal is to find a
$\gamma$-approximate solution $S_{i}$ of size at most $k$ at the end of each
round $i$ when making a pass on a dynamic stream of insertions and deletions
(the stream is _insertion-only_ if no deletions are allowed). More formally,
starting with $V_{0}=\emptyset$, an element $e_{i}\in V$ is either inserted or
deleted at the beginning of round $i=1,\ldots,$ so that the current ground set
$V_{i}$ is set to be either $V_{i-1}\cup\\{e_{i}\\}$ if $e_{i}$ is inserted or
$V_{i}=V_{i-1}\setminus\\{e_{i}\\}$ if $e_{i}$ is deleted. After this, the
algorithm makes queries to $f$ to find a _$\gamma$ -approximate solution
$S_{i}$ of $f$ with respect to $V_{i}$_. This means that $|S_{i}|\leq k$ and

$f(S_{i})\geq\gamma\operatorname{OPT}_{i},\quad\text{where}\quad\operatorname{OPT}_{i}:=\max_{T\subseteq
V_{i},|T|\leq k}f(T)$

We emphasize that an algorithm remembers every query it has made so far. Thus
results of queries made in previous rounds may help finding $S_{i}$ in the
current round.

We will consider algorithms that are both deterministic and randomized. We say
a deterministic dynamic algorithm achieves an approximation guarantee of
$\gamma$ if given $n$ and any stream of length $n$, it returns a
$\gamma$-approximate solution $S_{i}$ of the $i$-th round for every $i\in[n]$.
We say a randomized dynamic algorithm achieves an approximation guarantee of
$\gamma$ if given $n$ and any stream of length $n$, with probability at least
$2/3$ it returns a $\gamma$-approximate solution $S_{i}$ for every round
$i\in[n]$. We say an (deterministic or randomized) algorithm has _amortized_
query complexity $Q(n)$ if the total number of queries it makes is always no
more than $n\cdot Q(n)$.

######  Remark 2.1.

We discuss some details of the model behind our upper and lower bounds:

  1. 1.

Our lower bounds hold even if the algorithm is given $V$ and it is allowed to
query during the $i$-th round any set $S$ of elements that have appeared in
$V_{j}$ for some $j\leq i$; our algorithms only query sets in $V_{i}$ and does
not need to know $V$ initially.

  2. 2.

Our lower bounds hold even if the algorithm is given $n$, the stream length;
our algorithms do not need to know $n$ and meet the stated amortized bounds at
the end of every round.

Dynamic submodular maximization under a matroid constraint  A set system
$\mathcal{M}\subseteq 2^{V}$ is a _matroid_ if it satisfies (i)
$\emptyset\in\mathcal{M}$, (ii) the downward closed and (iii) augmentation
properties. A set system $\mathcal{M}$ is downward closed if $T\in\mathcal{M}$
implies $S\in\mathcal{M}$ for all $S\subseteq T$. The augmentation property is
that if $S,T\in\mathcal{M}$ and $|S|<|T|$, then there must be an element $e\in
T\backslash S$ such that $S\cup\\{a\\}\in\mathcal{M}$. When $S\in\mathcal{M}$,
we say $S$ is feasible or independent. The rank of the matroid $\mathcal{M}$,
denoted as $\operatorname{rank}(\mathcal{M})$, is the maximum size of an
independent set in $\mathcal{M}$.

The setting of dynamic submodular maximization under a matroid constraint is
similar. In addition to $V$ and query access to $f$, the algorithm is given
query access to a matroid $\mathcal{M}$ over $V$: it can pick any $S\subseteq
V$ to query if $S\in\mathcal{M}$ or not. To goal is to find a
$\gamma$-approximate solution $S_{i}$ of $f$ with respect to $V_{i}$ at the
end of every round. This mdeans that $S_{i}\subseteq V_{i}$,
$S_{i}\in\mathcal{M}$ and

$f(S_{i})\geq\gamma\cdot\operatorname{OPT}_{i},\quad\text{where}\quad\operatorname{OPT}_{i}:=\max_{T\in\mathcal{M},T\subseteq
V_{i}}f(T).$

When measuring the amortized query complexity, we count queries to both $f$
and $\mathcal{M}$.

######  Remark 2.2.

In both problems, one can assume without loss of generality that
$f(\emptyset)=0$ (since any $\gamma$-approximate solution to $g$ with respect
to $V_{i}$, where $g(S):=f(S)-f(\emptyset)$, must be a $\gamma$-approximate
solution to $f$ with respect to $V_{i}$ as well). We will make this assumption
in the rest of the paper.

The multilinear extention The multilinear extension
$F:[0,1]^{|V|}\rightarrow\mathbb{R}^{+}$ of a function $f$ maps a point
$\mathbf{x}\in[0,1]^{|V|}$ to the expected value of a random set
$S\sim\mathbf{x}$, i.e.

$F(\mathbf{x})=\sum_{S\subseteq V}\prod_{e\in S}x_{e}\prod_{e^{\prime}\in
V\backslash S}(1-x_{e^{\prime}})f(S)$

We write
$F(\mathbf{x})=\operatorname*{{\mathbb{E}}}_{S\sim\mathbf{x}}[f(\mathbf{x})]$
for simplicity. For any $\mathbf{x}\in[0,1]^{|V|}$, $\lambda\in[0,1]$,
$S\subseteq V$, we write $F(\mathbf{x}+\lambda S)$ to denote
$F(\mathbf{x}^{\prime})$, where $x^{\prime}_{i}=x_{i}$ if $i\notin S$ and
$x^{\prime}_{i}=\min\\{x_{i}+\lambda,1\\}$ if $i\in S$.

For a continuous function $F:[0,1]^{|V|}\rightarrow\mathbb{R}$, we say it is
monotone if $\frac{\partial F}{\partial x_{i}}\geq 0$ and it is submodular if
$\frac{\partial^{2}F}{\partial x_{i}\partial x_{j}}\leq 0$ for every $i,j$.
When $f$ is monotone and submodular, the multilinear extension $F$ is also
monotone and submodular.

##  3 A linear lower bound for $0.584$-approximation

We restate the main theorem of this section:

See 1.2

###  3.1 Construction of the symmetric function

Let $w$ be a positive integer and let $\epsilon>0$ be a small constant to be
fixed later. Given $x\in[0,1]^{w}$, we let
$\overline{x}=\sum_{i=1}^{w}x_{i}/w$. Consider the following function $f$ over
$[0,1]^{w}$ and its symmetric version $g$:

$\displaystyle f(x):=1-\prod_{i\in[w]}(1-x_{i})\quad\text{and}\quad
g(x):=1-(1-\overline{x})^{w}.$

The following theorem is from [MSV08]. We need to make some minor changes on
the choice of parameters and include a proof in Appendix A for completeness.

######  Theorem 3.1 ([MSV08]).

Given any positive integer $w$ and $\epsilon>0$, let
$\gamma=\gamma(w,\epsilon):=w^{-1}\exp(-4w^{6}/\epsilon)$. There is a monotone
submodular function $\widehat{f}:[0,1]^{w}\rightarrow[0,1]$ with the following
two properties:

  1. 1.

Whenever $\max_{i,j\in[w]}|x_{i}-x_{j}|\leq\gamma$, we have
$\widehat{f}(x)=g(x)$;

  2. 2.

For any $x\in[0,1]^{w}$, we have $f(x)-\epsilon\leq\widehat{f}(x)\leq f(x)$.

Let $m$ be a positive integer. We use $\widehat{f}$ from Theorem 3.1 to
construct a function $\widehat{F}:[0,1]^{mw}\rightarrow\mathbb{R}$ as follows:
Writing $x\in[0,1]^{mw}$ as $x=(x_{1},\ldots,x_{s})$ and
$x_{i}=(x_{i,1},\ldots,x_{i,w})\in[0,1]^{w}$, we have

$\displaystyle\widehat{F}(x):=1-\prod_{i\in[m]}(1-\widehat{f}(x_{i})).$ (1)

We also define its symmetric version $G:[0,1]^{mw}\rightarrow\mathbb{R}^{+}$
as

$\displaystyle
G(x):=1-\prod_{i\in[m]}(1-g(x_{i}))=1-\prod_{i\in[m]}(1-\overline{x_{i}})^{w}.$

Here are some basic properties we need about $\widehat{F}$, we defer detailed
proof to Appendix A.

######  Lemma 3.2.

$\widehat{F}$ satisfies the following properties:

  * •

$\widehat{F}$ is monotone, submodular and satisfies $\widehat{F}(x)\in[0,1]$
for all $x\in[0,1]^{mw}$.

  * •

$\widehat{F}(x)=G(x)$ when $x\in[0,1]^{mw}$ satisfies

$\max_{i\in[m],j,j^{\prime}\in[w]}|x_{i,j}-x_{i,j^{\prime}}|\leq\gamma$

and in this case, $\widehat{F}(x)$ depends on
$\overline{x_{1}},\ldots,\overline{x_{m}}$ only.

  * •

$\widehat{F}(x)\geq 1-\epsilon$ when $x$ satisfies $x_{i,j}=1$ for some
$i\in[m]$ and $j\in[w]$,

###  3.2 Construction of the hard functions $\mathcal{F}_{c,\pi}$

We now present the construction of the family of hard functions that will be
used in the proof.

Choice of parameters. Let $n$ be the length of the dynamic stream. Let
$\epsilon>0$ be a constant. Let $\alpha$ and $\beta$ be two constants in
$(0,1)$ that we fix at the end of the proof.222Looking ahead, we will choose
$\alpha$ and $\beta$ to minimize the quantity $Q(\alpha,\beta)$ discussed in
Lemma 3.7; we will set them to be $\alpha=0.56$ and $\beta=0.42$,
respectively. Let

$w=10\left(\frac{1}{\alpha\epsilon}+\frac{1}{(1-\alpha)\epsilon}\right)\quad\text{and}\quad\gamma=w^{-1}\exp\left(-\frac{4w^{6}}{\epsilon}\right)$

be two constants. Let $k$ be the cardinality constraint parameter that is at
most $n^{1/4}$ (otherwise the lower bound $\Omega(n/k^{3})$ in the main
theorem becomes trivial) and satisfies

$k\geq\frac{10}{\epsilon\gamma\alpha^{2}(1-\alpha)^{2}}\cdot\log n.$

Finally, let $m$ be such that $n=(2-\alpha)mkw$ so we have
$m=\Omega(n^{2/3})$.

The ground set $V$. We start with the definition of the ground set $V$, where

$V=A\cup B,\quad A=\bigcup_{i=1}^{m}A_{i}\quad\text{and}\quad
B=\bigcup_{i=1}^{m}B_{i},$

where each $A_{i}$ has $\alpha kw$ elements and each $B_{j}$ has
$(1-\alpha)kw$ elements and they are pairwise disjoint.

The function $\mathcal{F}_{c,\pi}$. Let $c:V\rightarrow[w]$. We say $c$ is a
_proper_ $w$-coloring of $V$ if each $A_{i,j}$, the set of elements in $A_{i}$
with color $j\in[w]$, has size $\alpha k$ and each $B_{i,j}$, the set of
elements in $B_{i}$ with color $j$, has size $(1-\alpha)k$. (So
$A_{i,1},\ldots,A_{i,w}$ form an even partition of $A_{i}$ and
$B_{i,1},\ldots,B_{i,w}$ form an even partition of $B_{i}$.) Let
$\pi:[m]\rightarrow[m]$ be a bijection which we will view as matching
$A_{\pi(i)}$ with $B_{i}$ for each $i\in[m]$. Given any proper $w$-coloring
$c$ of $V$ and any bijection $\pi:[m]\rightarrow[m]$, we define a function
$\smash{\mathcal{F}_{c,\pi}:2^{V}\rightarrow\mathbb{R}}$ as follows.

For any $S\subseteq V$, let $\smash{y^{S}\in[0,1]^{mw}}$ and
$z^{S}\in[0,1]^{mw}$ be defined from $S$ as

$y^{S}_{i,j}=\frac{|S\cap A_{i,j}|}{\alpha k}\quad\text{and}\quad
z^{S}_{i,j}=\frac{|S\cap B_{i,j}|}{(1-\alpha)k}.$

For any any $I\subseteq[m]$, let $x^{S,I,\pi}\in[0,1]^{mw}$ be

$x^{S,I,\pi}_{i,j}=\begin{cases}y^{S}_{\pi(i),j}&\text{if $i\in
I$}\\\\[3.44444pt] z^{S}_{i,j}&\text{if $i\notin I$}\end{cases}.$

Finally we define $\mathcal{F}_{c,\pi}:2^{V}\rightarrow\mathbb{R}$: For any
$S\subseteq V$,

$\displaystyle\mathcal{F}_{c,\pi}(S)=\min\left\\{\sum_{I\subseteq[m]}\beta^{|I|}(1-\beta)^{m-|I|}\cdot\widehat{F}(x^{S,I,\pi})+\frac{\epsilon}{k}|S|,\hskip
1.42271pt1\right\\}.$ (2)

We state some basic properties of the function $\mathcal{F}_{c,\pi}$.

######  Lemma 3.3.

For any $c$ and $\pi$, $\mathcal{F}_{c,\pi}$ satisfies the following two
properties:

  1. 1.

$\mathcal{F}_{c,\pi}$ is monotone, submodular and
$\mathcal{F}_{c,\pi}(S)\in[0,1]$ for any $S\subseteq V$.

  2. 2.

When $|S|\geq k/\epsilon$, $\mathcal{F}_{c,\pi}(S)=1$.

  3. 3.

For any $i\in[m]$ and $j\in[w]$, we have $|A_{\pi(i),j}\cup B_{i,j}|=k$ and
$\mathcal{F}_{c,\pi}(A_{\pi(i),j}\cup B_{i,j})\geq 1-\epsilon$.

###### Proof.

We start with the first claim. By Lemma 3.2, $\widehat{F}$ is monotone and
submodular. Hence, it is easy to see that for each $I\subseteq[m]$,
$\widehat{F}(x^{S,I,\pi})$ is monotone and submodular in $S$. As addition and
the min operation keep both submodularity and monotonity,
$\mathcal{F}_{c,\pi}$ is both monotone and submodular.

For the second claim, since $\smash{\widehat{F}}$ is nonnegative,
$\mathcal{F}_{c,\pi}(S)\geq\min\\{\epsilon|S|/k,1\\}=1$ when $|S|\geq
k/\epsilon$.

For the last claim, note that $|A_{\pi(i),j}|=\alpha k$,
$|B_{i,j}|=(1-\alpha)k$ and $A_{\pi(i),j}\cap B_{i,j}=\emptyset$. Therefore,
$|A_{\pi(i),j}\cup B_{i,j}|=k$. Let $S=A_{\pi(i),j}\cup B_{i,j}$. We have
$\smash{x^{S,I,\pi}_{i,j}=1}$ for all $I\subseteq[m]$ since
$\smash{y^{S}_{\pi(i),j}=z^{S}_{i,j}=1}$. By Lemma 3.2,
$\smash{\widehat{F}(x^{S,I,\pi})\geq 1-\epsilon}$ for all $I$ and thus,

$\displaystyle\mathcal{F}(S)=$ $\displaystyle\leavevmode\nobreak\
\min\left\\{\sum_{I\subseteq[m]}\beta^{|I|}(1-\beta)^{m-|I|}\cdot\widehat{F}(x^{S,I,\pi})+\frac{\epsilon}{k}|S|,1\right\\}\geq\min\left\\{(1-\epsilon)+\frac{\epsilon}{k}|S|,1\right\\}\geq
1-\epsilon.$

This finishes the proof of the lemma.∎

For any subset $S\subseteq V$, we say $S$ is balanced with respect to $c$ if

$\max_{\begin{subarray}{c}i\in[m]\\\
j,j^{\prime}\in[w]\end{subarray}}\left|y^{S}_{i,j}-y^{S}_{i,j^{\prime}}\right|\leq\gamma\quad\text{and}\quad\max_{\begin{subarray}{c}i\in[m]\\\
j,j^{\prime}\in[w]\end{subarray}}\left|z^{S}_{i,j}-z^{S}_{i,j^{\prime}}\right|\leq\gamma.$

Define $\mathcal{G}_{\pi}:2^{V}\rightarrow\mathbb{R}$ as

$\displaystyle\mathcal{G}_{\pi}(S)=\min\left\\{\sum_{I\subseteq[m]}\beta^{|I|}(1-\beta)^{m-|I|}\cdot
G(x^{S,I,\pi})+\frac{\epsilon}{k}|S|,1\right\\}.$ (3)

Recall the function $G(x)$ only depends on $\overline{x_{i}}$, $i\in[m]$. As a
result, $\mathcal{G}_{\pi}(S)$ only depends on $|S\cap A_{i}|$ and $|S\cap
B_{i}|$, $i\in[m]$. The following Lemma is a direct consequence of Lemma 3.2:

######  Lemma 3.4.

When $S\subseteq V$ is balanced with respect to $c$, we have
$\mathcal{F}_{c,\pi}(S)=\mathcal{G}_{\pi}(S)$.

Given any $S\subseteq V$, the next lemma captures the minimal information
needed to evaluate $\mathcal{G}_{\pi}(S)$ without full knowledge of $c$ and
$\pi$. The proof can be found at Appendix A.

######  Lemma 3.5.

Let $S\subseteq V$ and let $\pi,\pi^{\prime}:[m]\rightarrow[m]$ be two
bijections. Then we have $\mathcal{G}_{\pi}(S)=\mathcal{G}_{\pi^{\prime}}(S)$
when the following condition holds: For each $i\in[m]$, we have
$\pi(i)=\pi^{\prime}(i)$ if 1) $S\cap B_{i}\neq\emptyset$ and 2) either $S\cap
A_{\pi(i)}\neq\emptyset$ or $S\cap A_{\pi^{\prime}(i)}\neq\emptyset$.

######  Remark 3.6.

Let $S\subseteq V$. If (1) $S$ is known to be balanced with respect to $c$ and
(2) we are given

$\big{\\{}(i,\pi(i)):\text{$i\in[m]$, $S\cap B_{i}\neq\emptyset$ and $S\cap
A_{\pi(i)}\neq\emptyset$}\big{\\}},$ (4)

then one can evaluate $\mathcal{F}_{c,\pi}(S)$ without more information about
$c$ and $\pi$. To see this, (1) implies that it suffices to evaluate
$\mathcal{G}_{\pi}(S)$. Lemma 3.5 implies that $\mathcal{G}_{\pi}(S)$ is
uniquely determined given (4).

We delay the proof of the following lemma to Appendix A. This is where we need
to choose the two parameters $\alpha$ and $\beta$ carefully to minimize the
constant $0.584$ in the lemma.

######  Lemma 3.7.

Fix any $i^{*}\in[m]$. Let $S\subseteq A\cup B_{i^{*}}$ be a set such that $S$
is balanced with respect to $c$ and $S\cap A_{\pi(i^{*})}=\emptyset$. Then we
have $\mathcal{F}_{c,\pi}(S)\leq 0.5839+3\epsilon$.

###  3.3 Lower bound for dynamic submodular maximization

Hard streams. The ground set is $V$, which is known to the algorithm; the
monotone submodular function $\mathcal{F}^{*}:2^{V}\rightarrow\mathbb{R}$ is
$\mathcal{F}_{c,\pi}$, where $c$ is a proper $w$-coloring of $V$ and
$\pi:[m]\rightarrow[m]$ is a bijection, both of which are unknown to the
algorithm. In the stream we first insert all elements of $A$, which takes
$\alpha mkw$ insertions. We then divide the rest of the stream into $m$
batches: For the $t$-th batch, we first insert all elements of $B_{t}$ and
then delete them. So the total length is $n=(2-\alpha)mkw$. This is the only
stream we will use in the proof but the function is determined by the unknown
$c$ and $\pi$.

We will focus on the $0.1m$ rounds when elements of $B_{t}$, for each
$t=1,\ldots,0.1m$, has just been inserted. To ease the presentation we
consider the following dynamic problem that consists of $0.1m$ stages. During
the $t$-th stage, an algorithm can query
$\mathcal{F}^{*}:2^{V}\rightarrow\mathbb{R}$ about any $S\subseteq A\cup
B_{1}\cup\cdots\cup B_{t}$ and can choose to start the next stage at any time
by outputting a set $S_{t}\subseteq A\cup B_{t}$ of size at most $k$. The
algorithm succeeds after $0.1m$ stages if
$\mathcal{F}^{*}(S_{t})>0.5839+3\epsilon$ for every $t\in[0.1m]$. We prove
that any randomized algorithm that succeeds with probability at least $2/3$
must have total query complexity of at least $\Omega(n^{2}/k^{3})$. It then
follows from Lemma 3.3 (part 3) that any randomized algorithm for dynamic
submodular maximization with an approximation guarantee of $0.5839+4\epsilon$
must have amortized query complexity $\Omega(n/k^{3})$.

###### Proof of Theorem 1.2.

Let $\mathsf{ALG}$ be a randomized algorithm for the $0.1m$-stage problem
described above that succeeds with probability at least $2/3$. By Lemma 3.3,
we may assume that $\mathsf{ALG}$ never queries a set of size more than
$k/\epsilon$. To lower bound the query complexity of $\mathsf{ALG}$ we
consider the following simple $0.1m$-stage game.

In the game there is a hidden proper $w$-coloring $c$ of $V$ and a hidden
bijection $\pi:[m]\rightarrow[m]$. The game similarly consists of $0.1m$
stages. During each round of stage $t$, the algorithm can make a query by
either (1) picking a subset $S$ of $V$ of size at most $k/\epsilon$ or (2)
picking a number $i\in[m]$. In case (1) the $c$-oracle returns “balanced” or
“unbalanced,” as whether $S$ is balanced with respect to $c$ or not; when
receiving “unbalanced” the algorithm wins the whole game. In case (2) the
$\pi$-oracle returns “matched” or “not matched,” as whether $\pi(t)=i$ or not;
after receiving “matched,” the algorithm can choose to proceed to the next
stage, and it wins the game if it passes all $0.1m$ stages.

We show that any randomized algorithm that wins the game with probability at
least $2/3$ must use at least $\Omega(m^{2})$ queries. To this end, we
consider the distribution of $(\mathbf{c},\bm{\pi})$ where $\mathbf{c}$ and
$\bm{\pi}$ are drawn uniformly and independently, and show that any
deterministic algorithm that wins the game with probability at least $2/3$
must use $\Omega(m^{2})$ queries.

Showing this distributional $\Omega(m^{2})$ lower bound for each subgame is
easy. For the subgame of finding an unbalanced set with respect to
$\mathbf{c}$, we have for any set $S$ of size at most $k/\epsilon$ that

$\displaystyle\Pr\left[y^{S}_{i,j}-y^{S}_{i,j^{\prime}}>\gamma\right]$
$\displaystyle=\Pr\Big{[}|S\cap A_{i,j}|-|S\cap A_{i,j^{\prime}}|>\gamma\alpha
k\Big{]}$
$\displaystyle\leq\exp\left(-\frac{\epsilon\gamma^{2}\alpha^{2}k^{2}}{2k}\right)\leq\frac{1}{n^{5}},\quad\text{and}$
$\displaystyle\Pr\left[z^{S}_{i,j}-z^{S}_{i,j^{\prime}}>\gamma\right]$
$\displaystyle=\Pr\Big{[}|S\cap B_{i,j}|-|S\cap
B_{i,j^{\prime}}|>\gamma(1-\alpha)k\Big{]}$
$\displaystyle\leq\exp\left(-\frac{\epsilon\gamma^{2}(1-\alpha)^{2}k^{2}}{2k}\right)\leq\frac{1}{n^{5}}$

for any fixed $i$ and $j\neq j^{\prime}$, given our choice of $k$. Therefore,
any deterministic algorithm that finds an unbalanced set with probability at
least $1/3$ requires $\Omega(n^{5})$ queries. For the subgame about
$\bm{\pi}$, at the beginning of each stage $t$, any of the remaining $m-(t-1)$
indices (other than $\pi(1),\ldots,\pi(t-1)$) is equally likely to be
$\pi(t)$. Given that $m-(t-1)\geq 0.9m$, it takes $\Omega(m)$ queries to pass
each of the $0.1m$ stages and thus, any deterministic algorithm that wins the
subgame about $\bm{\pi}$ with probability at least $1/3$ requires
$\Omega(m^{2})$ queries.

Back to the original game, if a deterministic algorithm $\mathcal{A}$ can win
with probability at least $2/3$, then it can either win the first or the
second subgame with probability at least $1/3$. Assuming for example it is the
latter case, we get a randomized algorithm for winning the second subgame over
$\bm{\pi}$ with probability at least $1/3$ by first drawing $\mathbf{c}$ and
then simulating $\mathcal{A}$ on the original game. Given that the number of
queries is at most that of $\mathcal{A}$, we have that query complexity of
$\mathcal{A}$ is $\Omega(m^{2})$.

To finish the proof we show how to use $\mathsf{ALG}$ to play the game. Let
$c$ be the hidden coloring and $\pi$ be the hidden bijection. We simulate the
execution of $\mathsf{ALG}$ on $\mathcal{F}^{*}=\mathcal{F}_{c,\pi}$ as
follows:

  1. 1.

During the first stage (of both the dynamic problem of maximizing
$\mathcal{F}^{*}$ over $A\cup B_{1}$ and the game), letting $S\subseteq A\cup
B_{1}$ of size at most $k/\epsilon$ be any query made by $\mathsf{ALG}$, we
make one query $S$ on the $c$-oracle (to see if $S$ is balanced or not) and
make one query $i$ on the $\pi$-oracle for each $i\in[m]$ with $S\cap
A_{i}\neq\emptyset$ (to see if $\pi(1)=i$). If $S$ is not balanced, we already
won the game; otherwise, we know $\mathcal{F}^{*}(S)=\mathcal{G}_{\pi}(S)$ and
the latter can be computed (see Remark 3.6) using information returned by the
$\pi$-oracle, so that we can continue the simulation of $\mathsf{ALG}$. When
$\mathsf{ALG}$ decides to output $S_{1}\subseteq A\cup B_{1}$ of size at most
$k$, we query $S_{1}$ on the $c$-oracle and query each $i$ on the $\pi$-oracle
with $S_{1}\cap A_{i}\neq\emptyset$. If $S_{1}$ is unbalanced, we won the
game; if $\pi(1)=i$ for some $i$ queried, we move to stage $2$ (in both the
dynamic problem and the game); if $S_{1}$ is balanced and $\pi(1)\neq i$ for
any $i:S_{1}\cap A_{i}\neq\emptyset$, it follows from Lemma 3.7 that
$\mathsf{ALG}$ has failed so we terminate the simulation and fail the game.

  2. 2.

During the $t$-th stage (of both the dynamic problem and the game), we
similarly simulate each query $S\subseteq A\cup B_{1}\cup\cdots\cup B_{t}$ of
$\mathsf{ALG}$. The only difference is that, given that we have passed the
first $(t-1)$ stages of the game, we already know $\pi(1),\ldots,\pi(t-1)$ and
thus, information returned by the $\pi$-oracle would be enough for us to
evaluate $\mathcal{F}^{*}(S)$. When $\mathsf{ALG}$ returns $S_{t}$, we query
$S_{t}$ and each $i$ with $S_{t}\cap A_{i}\neq\emptyset$, and act according to
results similarly.

To summarize, the simulation has three possible outcomes: (1) we won the game
because an unbalanced set has been found; (2) we won the game because we have
passed all $0.1m$ stages; or (3) $\mathsf{ALG}$ fails to find $S_{t}$ with
$\mathcal{F}_{c,\pi}(S_{t})\geq 0.5839+3\epsilon$ for some $t$. Given that (3)
only happens with probability at most $1/3$, we obtain an algorithm for the
game that succeeds with probability at least $2/3$ and thus, must use
$\Omega(m^{2})$ queries. To finish the proof, we note that if $\mathsf{ALG}$
has total query complexity $q$ then the algorithm we obtain for the game has
total query complexity at most

$q\cdot\left(1+\frac{k}{\epsilon}\right)+0.1m\cdot(1+k),$

which implies $q=\Omega(m^{2}/k)$ and thus, the amortized complexity of
$\mathsf{ALG}$ is $\Omega(m/k^{2})=\Omega(n/k^{3})$. Taking $\epsilon=3\times
10^{-5}$, we get the lower bound on approximation ratio. ∎

##  4 A Polynomial Lower Bound for $1/2+\epsilon$ Approximation

We restate the main theorem of this section:

See 1.1

###  4.1 The construction

Let $\epsilon>0$ be a positive constant. We assume that both $1/\epsilon$ and
$\epsilon k$ are positive integers. Our goal is to show that any randomized
algorithm for dynamic submodular maximization under a cardinality constraint
of $k$ with approximation $\smash{1/2+\widetilde{O}(\epsilon)}$ must have
amortized query complexity $\Omega(n^{\epsilon}/k^{3})$.

We start with the construction of a monotone submodular function
$\mathcal{F}:V\rightarrow\mathbb{R}$. The family of functions used in our
lower bound proof will be obtained from $\mathcal{F}$ by carefully shuffling
elements of $V$. Let $L=1/\epsilon\in\mathbb{N}$ and let
$m=(m_{1},\ldots,m_{L})$ be a tuple of positive integers to be fixed later,
with $m_{L}$ set to be $1$. Let $T$ be a tree of depth $L$, where the root is
at depth $0$ and its leaves are at depth $L$. Each internal node of $T$ at
depth $\ell\in[0:L-1]$ has $m_{\ell+1}$ children; the number of nodes at depth
$\ell\in[L]$ is $m_{1}\cdots m_{\ell}$. We use $\gamma$ to refer to the root
of $T$ and write $U_{0}=\\{\gamma\\}$; for each $\ell\in[L]$, we use
$V_{\ell}=[m_{1}]\times\cdots\times[m_{\ell}]$ to refer to nodes of $T$ at
depth $\ell$. So the set of nodes is $U_{0}\cup U_{1}\cup\cdots\cup U_{L}$ and
whenever we refer to a node $u$ of $T$ at depth $\ell$, it should be
considered as a tuple $(u_{1},\ldots,u_{\ell})\in U_{\ell}$. Children of $u\in
U_{\ell}$, $\ell\leq L-1$, are given by
$(u_{1},\ldots,u_{\ell},1),\ldots,(u_{1},\ldots,u_{\ell},m_{\ell+1})$.

The ground set $V$ of $\mathcal{F}$ is defined as follows. For each node $u\in
U:=U_{1}\cup\cdots\cup U_{L}$, we introduce a set
$A_{u}=\\{a_{u,1},\ldots,a_{u,w}\\}$ of $w:=\epsilon k$ new elements. We
define $V$ as the union of $A_{u}$ for all $u\in U$. To construct
$\mathcal{F}:2^{V}\rightarrow\mathbb{R}$, we will utilize a weight sequence
$\\{w_{\ell}\\}_{\ell\in[0:L]}$ from [FNFSZ20] to define a probability
distribution $\mathcal{D}$ over subsets of nodes of $T$. We specify the
sequence later in Lemma 4.5; for now it suffices to know that $w_{0}=0$,
$w_{\ell}$’s are nonnegative, and they sum to $1$.

Algorithm 1 Sample

1:Input: A node $v$ of $T$ at depth $\ell\in[0:L]$

2:Let $p_{\ell}$ be given as below:
$p_{\ell}=\frac{w_{\ell}}{1-\sum_{i=0}^{\ell-1}w_{i}}\in[0,1].$

3:With probability $p_{\ell}$, return $v$. $\triangleright$ Since $p_{L}=1$,
this always happen when $\ell=L$

4:Otherwise, run $\textsf{Sample}(v_{i})$ independently on each child $v_{i}$
of $v$ in the tree and return the union

We define the distribution of $\mathcal{D}$ over $2^{U}$ as follows. Drawing a
sample from $\mathbf{R}\sim\mathcal{D}$ can be done by calling the recursive
procedure Sample in Algorithm 1 on the root of $T$. Informally, starting with
$\mathbf{R}=\emptyset$, Sample performs a DFS walk on $T$. Whenever reaching a
node $v$ at depth $\ell$, it adds $v$ to $\mathbf{R}$ and does not explore any
of its children with probability $p_{\ell}$ (see Algorithm 1; note that
$p_{0}=0$ and $p_{L}=1$); otherwise, it continues the DFS walk to visit each
of its children. Because $p_{0}=0$, the root is never included in the set and
thus, $\mathbf{R}$ is always a subset of $U$.

We need the following properties about $\mathbf{R}$, the proof can be found at
Appendix B.

######  Lemma 4.1.

Let $\mathbf{R}\sim\mathcal{D}$, we need have the following properties

  * •

For any node $u$ of $T$ at depth $\ell$, the probability of $u\in\mathbf{R}$
with $\mathbf{R}\sim\mathcal{D}$ is $w_{\ell}$.

  * •

For any root-to-leaf path of $T$, every $R$ in the support of $\mathcal{D}$
has exactly one node in the path.

Let $P_{1}\subseteq U$ and $P_{2}\subseteq U$ be two subsets of nodes of $T$
and let $\tau$ be a bijection from $P_{1}$ to $P_{2}$ such that (1) $u$ and
$\tau(u)$ are at the same depth for every $u\in P_{1}$; and (2) for any
$u,v\in P_{1}$, the depth of the lowest common ancestor (LCA) of $u$ and $v$
is the same as that of $\tau(u)$ and $\tau(v)$. The following lemma follows
from how the procedure Sample works:

######  Lemma 4.2.

The distribution of $P_{2}\cap\mathbf{R}$, $\mathbf{R}\sim\mathcal{D}$, is
distributed the same as first drawing $\mathbf{R}\sim\mathcal{D}$, taking
$P_{1}\cap\mathbf{R}$ and applying $\tau$ on $P_{1}\cap\mathbf{R}$.

###### Proof.

Let $T_{1}$ (or $T_{2}$) be the subtree that consists of paths from nodes in
$P_{1}$ (or $P_{2}$) to the root. Using conditions (1) and (2), one can show
(by induction) that $\tau$ can be extended to obtain an isomorphism from
$P_{1}$ to $P_{2}$. Then $P_{1}\cap\mathbf{R}$ and $P_{2}\cap\mathbf{R}$ can
be obtained by running Sample on the same tree and the two distributions are
the same under $\tau$. ∎

We use $\mathcal{D}$ to define $\mathcal{F}$. Given $S\subseteq V$, we define
$x^{S}\in[0,1]^{U}$ as the vector indexed by $u\in U$ with

$x^{S}_{u}=\frac{|S\cap A_{u}|}{\epsilon k}\in[0,1].$

For any $R$ in the support of $\mathcal{D}$ we define
$g_{R}:[0,1]^{U}\rightarrow[0,1]$ and $\mathcal{G}:[0,1]^{U}\rightarrow[0,1]$
as

$\displaystyle g_{R}(x):=1-\prod_{u\in
R}\left(1-x_{u}\right)\quad\text{and}\quad\mathcal{G}(x)=\operatorname*{{\mathbb{E}}}_{\mathbf{R}\sim\mathcal{D}}\big{[}g_{\mathbf{R}}(x)\big{]}.$
(5)

We are now ready to define $\mathcal{F}$ over $2^{V}$ as

$\displaystyle\mathcal{F}(S)=\min\left\\{\mathcal{G}(x^{S})+\frac{\epsilon}{k}|S|,\hskip
1.13791pt1\right\\},\quad\text{for any set $S\subseteq V$.}$ (6)

We state some basic properties of $\mathcal{F}$. The detailed proof can be
found at Appendix B.

######  Lemma 4.3.

$\mathcal{F}$ is monotone submodular and $\mathcal{F}(S)\in[0,1]$ for any
$S\subseteq V$. Moreover, $\mathcal{F}(S)=1$ whenever $|S|\geq k/\epsilon$.

For each leaf $u\in U_{L}$, we define two important subsets of $V$. The first
set, $\mathcal{A}_{u}$, is the union of $A$’s along the path from $u$’s parent
to the root (not including the root):

$\mathcal{A}_{u}:=A_{u_{1}}\cup A_{u_{1},u_{2}}\cup\cdots\cup
A_{u_{1},\ldots,u_{L-1}}.$

The other set $W_{u}$ is the union of $A$’s of nodes that are children of
nodes along the root-to-$u$ path:

$W_{u}:=\bigcup_{\ell\in[L]}\bigcup_{j\in[m_{\ell}]}A_{u_{1},\ldots,u_{\ell-1},j}.$

The following lemma shows that $\mathcal{F}(\mathcal{A}_{u}\cup A_{u})$ is
large:

######  Lemma 4.4.

For any leaf $u\in U_{L}$, we have $|\mathcal{A}_{u}\cup A_{u}|=k$ and
$\mathcal{F}(\mathcal{A}_{u}\cup A_{u})=1$.

###### Proof.

Since these $L=1/\epsilon$ sets are pairwise disjoint and each has size
$\epsilon k$, $S$ has size $k$. The second part follows from the second part
of Lemma 4.1 and the definition of $g_{R}$. ∎

We would like to show in the next lemma that any set $S\subseteq W_{u}$ that
has size at most $k$ and does not overlap with $\mathcal{A}_{u}$ must have a
small $\mathcal{F}(S)$. For this we need to specify the weight sequence
$\\{w_{\ell}\\}$ that we will use from [FNFSZ20] (recall that $w_{0}=0$).

######  Definition 4.5 (Weight sequence).

Define $\\{\delta_{\ell}\\}_{\ell\in[L]}$, $\\{a_{\ell}\\}_{\ell\in[L]}$ and
the weight sequence $\\{w_{\ell}\\}_{\ell\in[L]}$ inductively as follow. We
set $\delta_{L}=1$ and for $\ell=L-1,L-2,\ldots,1$, let

$\delta_{\ell}=1+\left(\frac{1+\sqrt{1+4/\delta_{\ell+1}}}{2}\right)\cdot\delta_{\ell+1}$

and

$a_{\ell}=\prod_{i=1}^{\ell-1}\left(\frac{\delta_{i}-1}{\delta_{i+1}}\right)=\prod_{i=1}^{\ell-1}\frac{1}{1-1/\delta_{i}},$

the weight sequence $\\{w_{\ell}\\}_{\ell\in[L]}$ is defined as
$w_{\ell}={a_{\ell}}/{\sum_{\ell\in[L]}{a_{\ell}}}$.

The proof of the following lemma is adapted from Lemma 5.3 in [FNFSZ20] with
some generalizations, and the proof can be found in Appendix B.

######  Lemma 4.6.

For any leaf $u\in U_{L}$ and $S\subseteq W_{u}$ with $|S|\leq k$ and
$S\cap\mathcal{A}_{u}=\emptyset$, we have

$\mathcal{F}(S)\leq 0.5+O\left({\epsilon}\hskip
1.13791pt{\log^{2}(1/\epsilon)}\right).$

As it will become clear soon at the beginning of the next subsection, our goal
behind the family of hard streams is to have the dynamic algorithm solve
repeatedly the question of finding an $S\subseteq W_{u}$ with $|S|\leq k$ and
$S\cap\mathcal{A}_{u}\neq\emptyset$, for a large number of leafs $u$ of $T$.
These questions are, however, only interesting after we shuffle nodes of $T$
in the fashion to be described next.

A _shuffling_ $\pi$ of $T$ consists of a bijection
$\pi_{u}:[m_{\ell+1}]\rightarrow[m_{\ell+1}]$ for every $u\in U_{\ell}$,
$\ell\in[0:L-1]$. We use $\pi$ to shuffle each node $u\in U$ to $\pi(u)$ as
follows: $\pi(\gamma)=\gamma$; for each $u$ of depth $\ell\in[L]$, set

$\pi(u)=\big{(}u_{1},\ldots,u_{\ell-1},\pi_{u_{1},\ldots,u_{\ell-1}}(u_{\ell})\big{)}.$

A shuffling $\pi$ induces a bijection $\rho_{\pi}:V\rightarrow V$: For each
element $a_{u,i}$ for some $u\in U$ and $i\in[w]$, we set
$\rho_{\pi}(a_{u,i})=a_{\pi^{-1}(u),i}$. Finally we define for each shuffling
$\pi$ of $T$,

$\mathcal{F}_{\pi}(S):=\mathcal{F}\big{(}\rho_{\pi}(S)\big{)}.$

It is clear that Lemma 4.3 holds for $\mathcal{F}_{\pi}$ for any shuffling
$\pi$.

Given a leaf $u\in U_{L}$ of $T$ and a shuffling $\pi$, let

$\mathcal{A}_{u}^{\pi}:=A_{u_{1},\ldots,u_{L-2},\pi_{u_{1},\ldots,u_{L-2}}(u_{L-1})}\cup\cdots
A_{u_{1},\pi_{u_{1}}(u_{2})}\cup A_{\pi_{\epsilon}(u_{1})}.$

We get the following corollary of Lemma 4.4 and Lemma 4.6:

######  Corollary 4.7.

For any shuffling $\pi$ of $T$, we have

  * •

For any leaf $u\in U_{L}$, we have $|\mathcal{A}^{\pi}_{u}\cup A_{u}|=k$ and
$\mathcal{F}_{\pi}(\mathcal{A}^{\pi}_{u}\cup A_{u})=1$.

  * •

For any leaf $u$ and $S\subseteq W_{u}$ with $|S|\leq k$ and
$S\cap\mathcal{A}_{u}^{\pi}=\emptyset$, we have

$\mathcal{F}_{\pi}(S)\leq 0.5+O\left(\epsilon\hskip
1.13791pt{\log^{2}(1/\epsilon)}\right).$ (7)

###### Proof.

The first part follows from Lemma 4.4 and the observation that
$\rho_{\pi}(\mathcal{A}_{u}^{\pi}\cup A_{u})=\mathcal{A}_{u}\cup A_{u}$. The
second part follows from $\rho_{\pi}(S)\subseteq W_{u}$,
$\rho_{\pi}(S)\cap\mathcal{A}_{u}=\emptyset$ and Lemma 4.6. ∎

We need a corollary of Lemma 4.2. Similar to Lemma 3.5, it captures the
minimal information needed about $\pi$ to evaluate $\mathcal{F}_{\pi}$ at a
given set $S\subseteq V$:

######  Corollary 4.8.

Let $S\subseteq V$ and let $\pi,\pi^{\prime}$ be two shufflings of $T$. We
have $\mathcal{F}_{\pi}(S)=\mathcal{F}_{\pi^{\prime}}(S)$ when the following
condition holds: For every two nodes $u,v$ of $T$ such that $S\cap A_{u}$ and
$S\cap A_{v}$ are nonempty, the LCA of $\pi^{-1}(u)$ and $\pi^{-1}(v)$ is at
the same depth as the LCA of $\pi^{\prime-1}(u)$ and $\pi^{\prime-1}(v)$, both
in $T$.

###### Proof.

Let $P_{1}=\\{\pi^{-1}(u):\text{$u\in U$ and $S\cap A_{u}\neq\emptyset$}\\}$
and $P_{2}$ be be the set of nodes defined similarly using $\pi^{\prime}$. It
follows from Lemma 4.2 that $\mathbf{R}\cap P_{1}$ is the same as
$\mathbf{R}\cap P_{2}$, $\mathbf{R}\sim\mathcal{D}$, under the natural
bijection between $P_{1}$ and $P_{2}$. The statement follows from the
definition of $\mathcal{F}$. ∎

######  Remark 4.9.

To evaluate $\mathcal{F}_{\pi}(S)$, it suffices to know the LCA of
$\pi^{-1}(u)$ and $\pi^{-1}(v)$ for every $u,v$ with $S\cap
A_{u}\neq\emptyset$ and $S\cap A_{v}\neq\emptyset$. The LCA of $\pi^{-1}(u)$
and $\pi^{-1}(v)$ can be determined as follows.

  1. 1.

First consider the case when $u$ is a prefix of $v$ or $v$ is a prefix of $u$.
Let $u=(u_{1},\ldots,u_{\ell})$ and
$v=(u_{1},\ldots,u_{\ell},v_{\ell+1},\ldots)$. (The case when $v$ is a prefix
is similar.) Then the depth of LCA of $\pi(u)$ and $\pi^{-1}(v)$ is either
$\ell$ if $\pi_{u_{1},\ldots,u_{\ell-1}}(u_{\ell})=u_{\ell}$, or $\ell-1$
otherwise.

  2. 2.

Assume that $u=(u_{1},\ldots,u_{\ell},u_{\ell+1},\ldots)$ and
$v=(v_{1},\ldots,v_{\ell},v_{\ell+1},\ldots)$ with
$u_{1}=v_{1},\ldots,u_{\ell}=v_{\ell}$ but $u_{\ell+1}\neq v_{\ell+1}$. We
have three subcases. If both $u$ and $v$ have length strictly longer than
$\ell+1$, then the depth of LCA of of $\pi^{-1}(u)$ and $\pi^{-1}(v)$ is
$\ell$. If both $u$ and $v$ have length $\ell+1$, then the depth of LCA of
$\pi^{-1}(u)$ and $\pi^{-1}(v)$ is also $\ell$. (So in these two subcases we
we do not need to know anything about $\pi$.) Finally, if $u$ has length
$\ell+1$ and $v$ has length longer than $\ell+1$, then the depth of LCA of
$\pi^{-1}(u)$ and $\pi^{-1}(v)$ is $\ell+1$ if
$\pi_{v_{1},\ldots,v_{\ell}}(v_{\ell+1})=u_{\ell+1}$, and is $\ell$ otherwise.
The case when $u$ has length longer than $\ell+1$ and $v$ has length $\ell+1$
is similar.

To summarize, to determine the depth we only need to know whether a particular
entry of $\pi$ is equal to a certain value or not. Moreover, the entry is
either $\pi_{u_{1},\ldots,u_{\ell-1}}(u_{\ell})$ or
$\pi_{v_{1},\ldots,v_{\ell-1}}(v_{\ell})$ for some $\ell$.

###  4.2 Lower bound for dynamic submodular maximization

Choices of parameters. Let $L=1/\epsilon$ be a positive integer. Let $k$ be a
positive integer such that $k^{2}\leq n^{\epsilon}$ (as otherwise the lower
bound we aim for becomes trivial) and $w=\epsilon k$ is a positive integer.
Let $n$ be the length of dynamic streams and $d=n^{\epsilon}$. Set $m_{L}=1$
and

$m_{\ell}=\frac{n^{(L-\ell+1)\epsilon}}{2k},\quad\text{for each
$\ell\in[L-1]$}.$

Hard streams. The ground set is $V$, which is known to the algorithm; the
monotone submodular function $\mathcal{F}^{*}:2^{V}\rightarrow\mathbb{R}$ is
$\mathcal{F}_{\pi}$, where $\pi$ is a shuffling of $T$, which is unknown to
the algorithm. The stream is constructed by running Tranverse in Algorithm 2,
and is independent of $\pi$. It can be viewed as a DFS over the tree $T$,
starting at the root, except that every time it reaches a node $v$, it inserts
all children of $v$ but only explores the first $d$ children, and deletes all
children of $v$ at the end of the exploration.

We first bound the total number of operations by $n$. For each
$\ell\in[0:L-2]$, Tranverse visits $d^{\ell}$ nodes and creates
$2m_{\ell+1}\cdot w$ operations for each of them. Tranverse visits $d^{L-1}$
nodes at depth $L-1$ and creates $2w$ operations for each of them. Hence, the
total number of operations is

$\sum_{\ell=0}^{L-2}d^{\ell}\cdot m_{\ell+1}\cdot 2w+d^{L-1}\cdot
2w\leq\sum_{\ell=0}^{L-2}\epsilon n+\epsilon n\leq n.$

To gain some intuition behind the stream, we note that leafs of $T$ that
appear in the stream are exactly those in $U_{L}^{*}:=[d]^{L-1}\times\\{1\\}$,
and they appear in the stream under the lexicographical order (which we will
denote by $\prec$). For each such leaf $u\in U_{L}^{*}$, at the time when the
set $A_{u}$ was inserted, the current set of elements is $W_{u}$. Inspired by
Corollary 4.7 we will consider the following simplified $d^{L-1}$-stage
dynamic problem, where stages are indexed using leaves in $U^{*}_{L}$ under
the lexicographical order. During the $u$-th stage, an algorithm can query
$\mathcal{F}^{*}$ about any subset $S\subseteq\cup_{u^{\prime}\in
U_{L}^{*}:u^{\prime}\preceq u}W_{u^{\prime}}$ and can choose to start the next
stage at any time by returning an $S_{u}\subseteq W_{u}$ of size at most $k$.
We say an algorithm succeeds if $\smash{\mathcal{F}^{*}(S_{u})\geq
0.5+\widetilde{O}(\epsilon)}$ as on the RHS of (7) for every stage. We show
below that any randomized algorithm that succeeds with probability at least
$2/3$ must have total query complexity $\Omega(n^{1+\epsilon}/k^{3})$. It
follows from Corollary 4.7 that any randomized algorithm for dynamic
submodular maximization with an approximation guarantee of
$0.5+\widetilde{\Omega}(\epsilon)$ must have amortized query complexity
$\Omega(n^{\epsilon}/k^{3})$.

Algorithm 2 Tranverse

1:Input: A node $u$ of $T$ at depth $\ell\in[0:L-1]$

2:if $\ell=L-1$ then

3: Insert all elements of $A_{u_{1},\ldots,u_{L-1},1}$ and then delete them

4:else

5: Insert all elements in $A_{u_{1},\cdots,u_{\ell},i}$ for each
$i\in[m_{\ell+1}]$

6: for $i$ from $1$ to $d$ do

7: Call Tranverse on $(u_{1},\ldots,u_{\ell},i)$

8: end for

9: Delete all elements in $A_{u_{1},\cdots,u_{\ell},i}$ for each
$i\in[m_{\ell+1}]$

10:end if

###### Proof of Theorem 1.1.

Let $\bm{\pi}$ be a shuffling of $T$ drawn uniformly at random (i.e., every
bijection in $\bm{\pi}$ is drawn independently and uniformly). Consider any
deterministic algorithm $\mathsf{ALG}$ that succeeds with probability $2/3$ on
the $d^{L-1}$-stage dynamic problem described above with
$\mathcal{F}^{*}=\mathcal{F}_{\bm{\pi}}$. By Lemma 4.3 we assume without loss
of generality that $\mathsf{ALG}$ only queries sets of size at most
$k/\epsilon$. When $\mathsf{ALG}$ succeeds on
$\mathcal{F}^{*}=\mathcal{F}_{\pi}$ for some shuffling $\pi$, we have from
Corollary 4.7 that the $S_{u}$ it outputs during the $u$-th stage must satisfy
$\smash{S_{u}\cap\mathcal{A}_{u}^{\pi}\neq\emptyset}$, which implies (using
the definition of $\mathcal{A}_{u}^{\pi}$) that

$S_{u}\cap
A_{u_{1},\ldots,u_{\ell},\pi_{u_{1},\ldots,u_{\ell}}(u_{\ell+1})}\neq\emptyset$
(8)

for some $\ell\in[0:L-2]$. By an averaging argument, we have that there exists
an $\ell\in[0:L-2]$ such that with probability at least $2/(3L)$ over
$\bm{\pi}$, at least $(1/L)$-fraction of $S_{u}$ returned by $\mathsf{ALG}$
satisfy (8) for this $\ell$. Fix such an $\ell$ and this inspires us to
introduce the following simple game.

In the game there are $d^{\ell}$ hidden bijections
$\pi_{v_{1},\ldots,v_{\ell}}:[m_{\ell+1}]\rightarrow[m_{\ell+1}]$, for each
$v_{1},\ldots,v_{\ell}\in[d]$. The game consists of $d^{\ell+1}$ stages; each
stage is indexed by a $v=(v_{1},\ldots,v_{\ell+1})\in[d]^{\ell+1}$ and ordered
by the lexicographical order. During the $v$-th stage of the game, an
algorithm can send a number $i\in[m_{\ell+1}]$ to the oracle and the latter
reveals if $\pi_{v_{1},\ldots,v_{\ell}}(v_{\ell+1})=i$. We say the algorithm
wins the $v$-th stage if it queries an $i$ that matches
$\pi_{v_{1},\ldots,v_{\ell}}(v_{\ell+1})$ during the $v$-th stage. At any time
it can choose to give up and move forward to the next stage, in which case
$\pi_{v_{1},\ldots,v_{\ell}}(v_{\ell+1})$ is revealed to the algorithm. We say
an algorithm succeeds if it wins at least $(1/L)$-fraction of the $d^{\ell+1}$
stages.

We prove the following lower bound for this game in Appendix B:

######  Claim 4.10.

When the hidden bijections are drawn independently and uniformly, any
deterministic algorithm that succeeds with probability at least $2/(3L)$ has
total query complexity $\Omega(m_{\ell+1}d^{\ell+1})$.

To finish the proof, we show that $\mathsf{ALG}$ can be used to play the game
as follows:

  1. 1.

We start by drawing a random bijection for every node in the tree $T$ except
for those at $(v_{1},\ldots,v_{\ell})\in[d]^{\ell}$. Let $\pi$ be the
shuffling when they are combined with hidden bijections
$\pi_{v_{1},\ldots,v_{\ell}}$ in the game. We simulate $\mathsf{ALG}$ on
$\mathcal{F}_{\pi}$ over the stream Tranverse and maintain
the following invariant. During the $v$-th stage of the game, with
$v=(v_{1},\ldots,v_{\ell+1})\in[d]^{\ell+1}$, we simulate $\mathsf{ALG}$
through its stages for leaves $u\in U_{L}^{*}$ that have $v$ as a prefix and
assume
that we already know $\smash{\pi_{w_{1},\ldots,w_{\ell}}(w_{\ell+1})}$ for all
$\smash{w=(w_{1},\ldots,w_{\ell+1})\prec v}$ and $w\in[d]^{\ell+1}$.

  2. 2.

During the $u$-th stage of the simulation of $\mathsf{ALG}$ for some leaf
$u\in U_{L}^{*}$, we are in the $v$-th stage of the game with
$v=(u_{1},\ldots,u_{\ell+1})\in[d]^{\ell+1}$. For each query
$S\subseteq\cup_{u^{\prime}\in U_{L}^{*}:u^{\prime}\preceq u}{W_{u^{\prime}}}$
(of size at most $k/\epsilon$) made by $\mathsf{ALG}$, it follows from Remark
4.9 that, to evaluate $S$ at $\mathcal{F}_{\pi}$, we only need to know the
depth of LCA of $\pi^{-1}(u^{\prime\prime})$ and $\pi^{-1}(v^{\prime\prime})$
in $T$ for no more than $(k/\epsilon)^{2}$ many pairs of
$u^{\prime\prime},v^{\prime\prime}$ with $S\cap
A_{u^{\prime\prime}}\neq\emptyset$ and $S\cap
A_{v^{\prime\prime}}\neq\emptyset$. For each such pair, it follows from Remark
4.9 again that either we know the answer already or we need to compare
$\smash{\pi_{u_{1}^{\prime\prime},\ldots,u_{\ell}^{\prime\prime}}(u_{\ell+1}^{\prime\prime})}$
or
$\smash{\pi_{v_{1}^{\prime\prime},\ldots,v_{\ell}^{\prime\prime}}(v_{\ell+1}^{\prime\prime})}$
with a certain value. Given that $u^{\prime\prime}\preceq v$ and
$v^{\prime\prime}\preceq v$, either the answer is already known or we just
need to make a query to the game oracle. So we only need to make at most
$(k/\epsilon)^{2}$ queries to continue the simulation of $\mathsf{ALG}$. At
the end of the $u$-th stage of $\mathsf{ALG}$, let $S_{u}$ be the set that
$\mathsf{ALG}$ returns. For every $i$ such that $S_{u}\cap
A_{u_{1},\ldots,u_{\ell},i}\neq\emptyset$ (note that there are at most $k$
such $i$ given that $|S|\leq k$), we query $i$ on the game oracle. Note that
we would have won the $v$-th stage of the game by now if (8) holds for
$S_{u}$. We then continue to simulate $\mathsf{ALG}$ on the next stage of the
dynamic problem. If the next stage of $\mathsf{ALG}$ is about a new leaf $u$
with $v\prec(u_{1},\ldots,u_{\ell+1})$, then we also move to the next stage in
the game.

It is clear from the simulation that for any $\pi$, if $\mathsf{ALG}$ running
on $\mathcal{F}_{\pi}$ satisfies (8) for at least $(1/L)$-fraction of leaves
in $U_{L}^{*}$, then we win the game when $\pi$ is the shuffling we get by
combining our own random samples at the beginning with hidden bijections in
the game. Using the promise about $\mathsf{ALG}$ at the beginning, we get a
randomized algorithm that succeeds in the game with probability at least
$2/(3L)$ when the hidden bijections are drawn independently and uniformly at
random. On the other hand, if the query complexity of $\mathsf{ALG}$ is $q$,
then our simulation uses

$q\cdot\left(\frac{k}{\epsilon}\right)^{2}+d^{L-1}\cdot k$

Combining with Claim 4.10 we have $q=\Omega(n^{1+\epsilon}/k^{3})$. ∎

##  5 Insertion-only streams under a cardinality constraint

We consider insertion-only streams and give a deterministic
$(1-1/e-\epsilon)$-approximation algorithm with
$O(\log(k/\epsilon)/\epsilon^{2})$ amortized query complexity. As discussed in
Remark 2.1, our algorithm does not need to know the ground set $V$ or the
number of rounds $n$ at the beginning.

See 1.3

To prove Theorem 1.3, we give a deterministic algorithm with the following
performance guarantees. We follow standard arguments to finish the proof of
Theorem 1.3 in Appendix C.

######  Lemma 5.1.

There is a deterministic algorithm that satisfies the following performance
guarantees. Given a positive integer $k$, $\epsilon>0$ and
$\operatorname{OPT}>0$, the algorithm runs on an insertion-only stream and
outputs a set $S_{t}\subseteq V_{t}$ of size at most $k$ at the end of each
round $t$ such that (1) $S_{1}\subseteq S_{2}\subseteq\cdots$ and (2) when
$\operatorname{OPT}_{t}\geq\operatorname{OPT}$ for the first time, $S_{t}$
must satisfy $f(S_{t})\geq(1-1/e-\epsilon)\operatorname{OPT}$. The amortized
query complexity of the algorithm is $O(1/\epsilon)$.

Algorithm 3 Dynamic submodular maximization with a cardinality constraint.

1:procedure Initialize($k,\epsilon,\operatorname{OPT}$)

2: Initialize $S=\emptyset$, $\Delta=\epsilon\operatorname{OPT}/k$ and
$B_{\ell}=\emptyset$ for each $\ell=0,1,\ldots,\lfloor 1/\epsilon\rfloor$

3:end procedure

4:

5:procedure Insert($e$)

6: if $f_{S}(e)\geq(\operatorname{OPT}-f(S))/k-\Delta$ and $|S|<k$ then

7: Update $S\leftarrow S\cup\\{e\\}$ and call Revoke

8: else

9: Update $B_{\ell}\leftarrow B_{\ell}\cup\\{e\\}$ with $\ell=\lfloor
f_{S}(e)/\Delta\rfloor$$\triangleright$ $\ell\leq\lfloor 1/\epsilon\rfloor$
given $f_{S}(e)<\operatorname{OPT}/k$

10: end if

11:end procedure

12:

13:procedure Revoke

14: Let $r=\lfloor(\operatorname{OPT}-f(S))/(k\Delta)\rfloor$.

15: if $|S|<k$ and there exists an index $\ell\geq r$ with
$B_{\ell}\neq\emptyset$ then

16: Let $\ell$ be any such index and let $e^{\prime}$ be any element in
$B_{\ell}$.

17: if $f_{S}(e^{\prime})\geq(\operatorname{OPT}-f(S))/k-\Delta$ then

18: Update $S\leftarrow S\cup\\{e^{\prime}\\}$ and $B_{\ell}\leftarrow
B_{\ell}\backslash\\{e^{\prime}\\}$

19: else

20: Update $B_{\ell}\leftarrow B_{\ell}\backslash\\{e^{\prime}\\}$,
$B_{\ell^{\prime}}\leftarrow B_{\ell^{\prime}}\cup\\{e^{\prime}\\}$ with
$\ell^{\prime}=\lfloor f_{S}(e^{\prime})/\Delta\rfloor$ $\triangleright$
$0\leq\ell^{\prime}<r\leq\ell$

21: end if

22: Go to Line 14.

23: end if

24:end procedure

###### Proof.

The algorithm is described in Algorithm 3 with
$\Delta:=\epsilon\operatorname{OPT}/(k)$. We first run Initialize and then run
Insert$(e_{t})$ when the $t$-th element $e_{t}$ is inserted in the stream. It
outputs $S$ at the end of Insert$(e_{t})$ as $S_{t}$. It is clear that
$S_{1}\subseteq S_{2}\subseteq\cdots$ given that the algorithm only grows $S$
by adding elements to it.

We prove the approximation guarantee of the algorithm. Let $t$ be the first
time $\operatorname{OPT}_{t}\geq$ $\operatorname{OPT}$. We first consider the
case when $|S_{t}|=k$. Let $S_{t}=\\{s_{1},\ldots,s_{k}\\}$ where $s_{i}$ is
the $i$-th element inserted to $S$. Let $T_{i}=\\{s_{1},\ldots,s_{i}\\}$ for
each $i\in[0:k]$ (so $T_{k}=S_{t}$ and $T_{0}=\emptyset$ with $f(T_{0})=0$).
Given that

$f_{S}(e)\geq\frac{\operatorname{OPT}-f(S)}{k}-\Delta,$

whenever the algorithm adds an element $e$ to $S$ (line 7 and line 18), we
have

$f_{T_{i}}(s_{i+1})\geq\frac{\operatorname{OPT}-f(T_{i})}{k}-\Delta$

for each $i\in[k]$. By standard calculation, one has

$\displaystyle\operatorname{OPT}-f(S_{t})=\operatorname{OPT}-f(T_{k})$
$\displaystyle=\operatorname{OPT}-f(T_{k-1})-f_{T_{k-1}}(s_{k})$
$\displaystyle\leq\operatorname{OPT}-f(T_{k-1})-\frac{\operatorname{OPT}-f(T_{k-1})}{k}+\Delta$
$\displaystyle=\left(1-\frac{1}{k}\right)\big{(}\operatorname{OPT}-f(T_{k-1})\big{)}+\Delta$
$\displaystyle\hskip 28.45274pt\vdots$
$\displaystyle\leq\left(1-\frac{1}{k}\right)^{k}\big{(}\operatorname{OPT}-f(T_{0})\big{)}+k\Delta$
$\displaystyle\leq\frac{1}{e}\cdot\operatorname{OPT}+\frac{\epsilon}{4}\cdot\operatorname{OPT}.$

which implies that $f(S_{t})\geq(1-1/e-\epsilon)\operatorname{OPT}$.

Next consider the case when $|S_{t}|<k$. In this case we have that every
element inserted is either in $S_{t}$ or in one of the buckets $B_{\ell}$. Let
the optimal solution be $O_{t}=\\{o_{1},\ldots,o_{k}\\}$ and let

$r=\left\lfloor\frac{\operatorname{OPT}-f(S_{t})}{k\Delta}\right\rfloor.$

Then at the end of round $t$ (after Insert), we must have that every $o_{i}$
with $o_{i}\notin S_{t}$ lies in a bucket $B_{\ell}$ with $\ell<r$ and thus,

$\displaystyle f_{S_{t}}(o_{i})<(\ell+1)\Delta\leq
r\Delta\leq\frac{\operatorname{OPT}-f(S_{t})}{k}.$ (9)

This is because the algorithm makes sure that at any time, any element
$e^{\prime}\in B_{\ell}$ satisfies $f_{S}(e^{\prime})<(\ell+1)\Delta$. To see
this is the case, we note that the inequality holds when $e^{\prime}$ is added
to $B_{\ell}$ and that $S$ only grows over time. We conclude that
$f(S_{t})\geq(1-\epsilon)\operatorname{OPT}$; otherwise, one has

$\operatorname{OPT}\leq f(O_{t})\leq
f(S_{t})+\sum_{i\in[k]}f_{S_{t}}(o_{i})<f(S_{t})+\sum_{i=1}^{k}\frac{\operatorname{OPT}-f(S_{t})}{k}=\operatorname{OPT},$

a contradiction. The second step above follows from the submodularity and
monotonicity, the third step follows from Eq. (9) and
$f(S_{t})<(1-\epsilon)\operatorname{OPT}$.

Finally we bound the amortized query complexity of the algorithm. We charge
the two queries made in the evaluation of $f_{S}(e)$ (line 6 or 17) to $e$ and
show that the number of queries charged to $e$ is at most $O(1/\epsilon)$. To
see this, we note that $e$ is charged twice when it is just inserted. Every
time $e$ is charged during Revoke, either it is added to $S$ so that it is
never charged again, or it gets moved to a bucket with a strictly smaller
$\ell$, which can only happen $O(1/\epsilon)$ many times. ∎

##  6 Insertion-only stream: efficient algorithm for matroid constaints

We present an efficient $(1-1/e-\epsilon)$-approximation algorithm under the
general matroid constraint. We first give a $(1/2-\epsilon)$-approximate
deterministic combinatorial algorithm (Section 6.1), we then embed it into the
accelerated continuous greedy framework of [BV14] to achieve
$(1-1/e-\epsilon)$ approximation (Section 6.2).

###  6.1 The combinatorial algorithm

Given $k$ as the rank of the matroid $\mathcal{M}$, we define $L,R$ and
$\mathcal{A}$ as

$L=\left\lceil\frac{\log(k/\epsilon)}{\epsilon}\right\rceil,\quad
R=\left\lceil\frac{2\log(k/\epsilon)}{\epsilon^{2}}\right\rceil\quad\text{and}\quad\mathcal{A}=\left\\{(a_{1},\cdots,a_{L})\in\mathbb{Z}_{\geq
0}^{L}:\sum_{\ell\in[L]}a_{\ell}\leq R\right\\}.$

We note the size of $\mathcal{A}$ can be upper bounded by

$\displaystyle|\mathcal{A}|=\sum_{d=0}^{R}\binom{d+L-1}{L-1}\leq(R+1)\cdot\binom{R+L-1}{L-1}\leq(R+1)\left(\frac{2eR}{L}\right)^{L}=k^{\widetilde{O}(1/\epsilon)}.$
(10)

Both of our deterministic algorithm and randomized algorithm use a
deterministic subroutine called Prune-greedy described in Algorithm 4. The
inputs of Prune-greedy include $k$ as the rank of the underlying matroid
$\mathcal{M}$, a positive number $\operatorname{OPT}$, a tuple
$a\in\mathcal{A}$, as well as query access to both $f$ and $\mathcal{M}$. When
running on an insertion-only stream, Prune-greedy may decide to terminate at
the end of a round and output a set $S$. A complication due to the application
of this subroutine in the randomized algorithm is that we will give it query
access to a perturbed version of $f$: We say $h:V\rightarrow\mathbb{R}$ is a
_$\kappa$ -close_ of $f$ if $h(S)=f(S)\pm\kappa$ for every $S\subseteq V$.

We state its performance guarantees in the following lemma:

Algorithm 4 Prune-greedy

1:procedure Initialize($k,\operatorname{OPT},a,h,\mathcal{M}$)
$\triangleright$ $a\in\mathcal{A}$

2: Initialize $S\leftarrow\emptyset$ and $c_{\ell}\leftarrow a_{\ell}\Delta$
for each $\ell\in[L]$

3: Let $\ell^{*}$ be the smallest $\ell\in[L]$ with $c_{\ell}>0$

4:end procedure

5:

6:procedure Insert($e$)

7: if $S\cup e\in\mathcal{M}$ and
$h_{S}(e)\geq(1+\epsilon)^{-\ell^{*}}\operatorname{OPT}$ then

8: Update $c_{\ell^{*}}\leftarrow c_{\ell^{*}}-h_{S}(e)$ and $S\leftarrow
S\cup\\{e\\}$

9: if $c_{\ell^{*}}\leq 0$ then

10: Call Revoke

11: end if

12: end if

13:end procedure

14:

15:procedure Revoke

16: Update $\ell^{*}$ to be the smallest $\ell$ with $c_{\ell}>0$; Terminate
and return $S$ if no such $\ell$ exists

17: for each element $e_{i}$ inserted so far (in the order of insertions) do

18: if $S\cup e_{i}\in\mathcal{M}$ and
$h_{S}(e_{i})\geq(1+\epsilon)^{-\ell^{*}}\operatorname{OPT}$ then

19: Update $c_{\ell^{*}}\leftarrow c_{\ell^{*}}-h_{S}(e_{i})$ and $S\leftarrow
S\cup\\{e_{i}\\}$,

20: end if

21: end for

22: Go to line 16 if $c_{\ell}^{*}\leq 0$

23:end procedure

######  Lemma 6.1.

There is a deterministic algorithm that, given a positive integer $k$,
$\operatorname{OPT}>0$, $a\in\mathcal{A}$ and query access to a matroid
$\mathcal{M}$ over $V$ of rank $k$ and a function $h:V\rightarrow\mathbb{R}$
that is $\kappa$-close to a nonnegative and monotone submodular function
$f:V\rightarrow\mathbb{R}$, where $\kappa=\epsilon^{3}\operatorname{OPT}/k$.
The algorithm runs on insertion-only streams with amortized query complexity
$O(L)$ and has the following performance guarantee. Given any insertion-only
stream $e_{1},\ldots,e_{t}$ such that
$\operatorname{OPT}\leq\operatorname{OPT}_{t}\leq$
$(1+\epsilon)\operatorname{OPT}$, there exists an $a^{*}\in\mathcal{A}$ such
that when given $\operatorname{OPT}$ and $a^{*}$ as input, the algorithm
terminates before the end of round $t$ and outputs a feasible set $S\subseteq
V_{t}$ that satisfies

$f(S)\geq(1-O(\epsilon))f_{S}(O),\quad\text{for any set $O$ such that
$O\in\mathcal{M}$ and $O\subseteq V_{t}$.}$

###### Proof.

The algorithm is described in Algorithm 4, with

$\Delta:=\frac{\epsilon^{2}\operatorname{OPT}}{\log(k/\epsilon)}.$

Let $e_{1},\ldots,e_{t}$ be the stream with
$\operatorname{OPT}\leq\operatorname{OPT}_{t}\leq(1+\epsilon)\operatorname{OPT}$.
To specify the $a^{*}\in\mathcal{A}$ in the statement of the lemma, we
consider the following $L$-pass greedy algorithm. The algorithm maintains a
set $T\in\mathcal{M}$. It starts with $T=\emptyset$ and updates $T\rightarrow
T\cup T_{\ell}$ at the end of the $\ell$-th pass (so we have
$T=T_{1}\cup\cdots\cup T_{\ell}$ at the end of the $\ell$-th pass). During the
$\ell$-th pass, we set $S_{\ell}=\emptyset$ and go through
$e_{1},\ldots,e_{t}$. For each $e_{i}$, the algorithm checks if $T\cup
S_{\ell}\cup\\{e_{i}\\}\in\mathcal{M}$ and $h_{T\cup
S_{\ell}}(e_{i})\geq(1+\epsilon)^{-(\ell-1)}\operatorname{OPT}$. If so,
$e_{i}$ is added to $S_{\ell}$. At the end of the $\ell$-th pass, we do _not_
add all elements $S_{\ell}$ to $T$. Instead, we further prune $S_{\ell}$ to
get $T_{\ell}$: Let $e_{i_{1}},e_{i_{2}},\ldots$ be elements added to
$S_{\ell}$ during the $\ell$-th pass. $T_{\ell}$ is set to be
$\\{e_{i_{1}},\ldots,e_{i_{j}}\\}$ such that $j$ is the smallest integer such
that

$h_{T_{1}\cup\cdots\cup
T_{\ell-1}}(T_{\ell})\geq\Delta\left\lfloor\frac{h_{T_{1}\cup\cdots\cup
T_{\ell-1}}(S_{\ell})}{\Delta}\right\rfloor,$

where $T_{\ell}=\emptyset$ when the RHS above is $0$. This finishes the
$\ell$-th pass and the algorithm updates $T$ with $T\cup T_{\ell}$. Let
$(S_{1},\ldots,S_{L})$ and $(T_{1},\ldots,T_{L})$ be the two sequences of sets
obtained from this $L$-pass algorithm. Let $a^{*}\in\mathbb{Z}_{\geq 0}^{L}$
be defined as $a^{*}_{\ell}=\lfloor h_{T_{1}\cup\cdots\cup
T_{\ell-1}}(S_{\ell})/\Delta\rfloor$ for each $\ell\in[L]$. It is easy to see
that

$\displaystyle\Delta\sum_{\ell\in[L]}a^{*}_{\ell}$
$\displaystyle=\Delta\sum_{\ell\in[L]}\left\lfloor\frac{h_{T_{1}\cup\cdots\cup
T_{\ell-1}}(S_{\ell})}{\Delta}\right\rfloor$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \sum_{\ell=1}^{L}h_{T_{1}\cup\cdots\cup
T_{\ell-1}}(T_{\ell})\leq f(T)+2\kappa<2\operatorname{OPT}.$

Hence $\sum_{\ell\in[L]}a_{\ell}^{*}\leq R$ and thus, $a^{*}\in\mathcal{A}$.
The following lemma connects Prune-Greedy with this $L$-pass greedy algorithm:

######  Lemma 6.2.

Suppose that Prune-Greedy is given $a^{*}$ at the beginning, then it
terminates before the end of the $t$-th round and outputs exactly
$T=T_{1}\cup\cdots\cup T_{L}$.

Given Lemma 6.2, it suffices to prove that

$f(T)\geq(1-O(\epsilon))f_{T}(O),\quad\text{for every feasible set $O\subseteq
V_{t}$.}$

Fix an $O\in\mathcal{M}$ and $O\subseteq V_{t}$. The following Lemma is a
folklore.

######  Lemma 6.3.

Let $\mathcal{M}$ be a matroid and $T\in\mathcal{M}$ with
$T=T_{1}\cup\cdots\cup T_{L}$ such that $T_{1},\ldots,T_{L}$ are pairwise
disjoint. Then any $O\in\mathcal{M}$ can be partitioned into pairwise disjoint
$O_{1},\ldots,O_{L}$ such that

  1. 1.

If $|O|\geq|T|$ then $|O_{i}|=|T_{i}|$ for all $i<L$; If $|O|<|T|$, letting
$\ell$ be the smallest integer such that $|O|\leq\sum_{i\leq\ell}|T_{\ell}|$,
then $|O_{i}|=|T_{i}|$ for all $i<\ell$ and
$|O_{\ell}|=|O|-\sum_{i<\ell}|O_{i}|$. (Note that we always have
$|O_{i}|\leq|T_{i}|$ except for $i=L$.)

  2. 2.

For all $i<j$, $T_{i}\cap O_{j}=\emptyset$ and for every $i<L$,

$T_{1}\cup\cdots\cup T_{i}\cup O_{i+1}\cup\cdots\cup O_{L}\in\mathcal{M}.$

Recall $S_{1},\ldots,S_{L}$ from the $L$-pass greedy algorithm. We have for
every $\ell\in[L]$,

$T_{1}\cup\cdots\cup T_{\ell-1}\cup S_{\ell}\in\mathcal{M}.$

For the analysis we partition $O$ into pairwise disjoint sets
$E_{0},E_{1}\ldots,E_{L-2},P_{1},\ldots,P_{L}$ as follows.

  1. 1.

$P_{1}=O_{1}$;

  2. 2.

For each $\ell\geq 2$ and each $o\in O_{\ell}$, we consider two cases. If
$T_{1}\cup\cdots\cup T_{\ell-2}\cup S_{\ell-1}\cup\\{o\\}\in\mathcal{M}$ then
we have $o\in P_{\ell}$; otherwise, we have $o\in E_{r}$ where $r\geq 0$ is
the largest integer such that $T_{1}\cup\cdots\cup T_{r-1}\cup
S_{r}\cup\\{o\\}\in\mathcal{M}$ and $T_{1}\cup\cdots\cup T_{r}\cup
S_{r+1}\cup\\{o\\}\notin\mathcal{M}$. Note that $r\leq\ell-2$ and such an
$r\geq 0$ always exists given that the condition when $r=0$ is just that
$\\{o\\}\in\mathcal{M}$.

The following claim about the size of $E_{\ell}$ follows from the definition,
the detailed proof can be found at Appendix D.

######  Claim 6.4.

$|E_{\ell}|\leq|S_{\ell+1}\backslash T_{\ell+1}|$.

Now we have

$\displaystyle f_{T}(O)$
$\displaystyle\leq\sum_{\ell\in[L]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(O_{\ell})$ $\displaystyle\leq
f(O_{1})+\sum_{\ell\in[2:L]}\sum_{r\in[0:\ell-2]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(O_{\ell}\cap E_{r})+\sum_{\ell\in[2:L]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(P_{\ell}),$ (11)

where both steps follow from the submodularity of $f$.

We first bound the first and last term.

######  Lemma 6.5.

We have

$f(O_{1})+\sum_{\ell\in[2:L]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(P_{\ell})\leq(1+\epsilon)f(T)+6\epsilon\operatorname{OPT}.$

We will need the following fact, the proof can be found at Appendix D:

######  Fact 6.6.

Suppose $f$ is a monotone submodular funciton. For any three sets $A,B$ and
$C$ we have

$f_{A}(C)\leq f_{A\cup B}(C)+f_{A}(B).$

###### Proof of Lemma 6.5.

Recall that for every $o\in P_{\ell}$ with $\ell\geq 2$, we have
$T_{1}\cup\cdots\cup T_{\ell-2}\cup S_{\ell-1}\cup\\{o\\}\in\mathcal{M}.$ We
have

$\displaystyle\sum_{\ell\in[2:L]}f_{T_{1}\cup\cdots\cup T_{\ell-1}}(P_{\ell})$
$\displaystyle\leq\sum_{\ell\in[2:L]}f_{T_{1}\cup\cdots\cup T_{\ell-2}\cup
S_{\ell-1}}(P_{\ell})+f_{T_{1}\cup\cdots\cup T_{\ell-1}}(S_{\ell-1}\backslash
T_{\ell-1})$ $\displaystyle\leq\sum_{\ell\in[2:L]}f_{T_{1}\cup\cdots\cup
T_{\ell-2}\cup S_{\ell-1}}(P_{\ell})+2\epsilon\operatorname{OPT}$
$\displaystyle\leq\sum_{\ell\in[2:L]}\sum_{o\in
P_{\ell}}f_{T_{1}\cup\cdots\cup T_{\ell-2}\cup
S_{\ell-1}}(o)+2\epsilon\operatorname{OPT}$
$\displaystyle\leq\sum_{\ell\in[2:L]}|O_{\ell}|(1+\epsilon)^{-\ell+2}\operatorname{OPT}+3\epsilon\operatorname{OPT}$

The first step comes from Fact 6.6. The second step follows from

$\displaystyle f_{T_{1}\cup\cdots\cup T_{\ell-1}}(S_{\ell-1}\backslash
T_{\ell-1})$ $\displaystyle=f_{T_{1}\cup\cdots\cup
T_{\ell-2}}(S_{\ell-1})-f_{T_{1}\cup\cdots\cup T_{\ell-2}}(T_{\ell-1})$
$\displaystyle\leq h_{T_{1}\cup\cdots\cup
T_{\ell-2}}(S_{\ell-1})-h_{T_{1}\cup\cdots\cup
T_{\ell-2}}(T_{\ell-1})+4\kappa$ $\displaystyle\leq h_{T_{1}\cup\cdots\cup
T_{\ell-2}}(S_{\ell-1})-\Delta\left\lfloor\frac{h_{T_{1}\cup\cdots\cup
T_{\ell-2}}(S_{\ell-1})}{\Delta}\right\rfloor+4\kappa$
$\displaystyle\leq\Delta+4\kappa$ (12)

and that $(\Delta+4\kappa)L\leq 2\epsilon\operatorname{OPT}$. The third step
comes from the submodularity. The fourth step holds since $T_{1}\cup\cdots\cup
T_{\ell-2}\cup S_{\ell-1}\cup\\{o\\}$ is feasible for each $o\in P_{\ell}$, by
the $L$-pass greedy algorithm,

$f_{T_{1}\cup\cdots\cup T_{\ell-2}\cup S_{\ell-1}}(o)\leq
h_{T_{1}\cup\cdots\cup T_{\ell-2}\cup
S_{\ell-1}}(o)+\kappa\leq(1+\epsilon)^{-\ell+2}\operatorname{OPT}+\kappa$

and that $k\kappa\leq\epsilon\operatorname{OPT}$. On the other hand, we have
$f(O_{1})$ is $0$ if $|O_{1}|=0$ or when $|O_{1}|>0$ (and thus, $|T_{1}|>0$),

$f(O_{1})\leq\operatorname{OPT}_{t}\leq(1+\epsilon)\operatorname{OPT}\leq|O_{1}|(1+\epsilon)\operatorname{OPT}.$

In summary, we have

$\displaystyle f(O_{1})+\sum_{\ell\in[2:L]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(P_{\ell})$
$\displaystyle\leq\sum_{\ell\in[L]}|O_{\ell}|(1+\epsilon)^{-\ell+2}\operatorname{OPT}+3\epsilon\operatorname{OPT}$
$\displaystyle\leq\sum_{\ell\in[L-1]}|T_{\ell}|(1+\epsilon)^{-\ell+2}\operatorname{OPT}+4\epsilon\operatorname{OPT}$

where we used
$k(1+\epsilon)^{-L+2}\operatorname{OPT}\leq\epsilon\operatorname{OPT}$. To
connect with $f(T)$, we have from the greedy algorithm that

$f(T)=\sum_{\ell\in[L]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(T_{\ell})\geq\sum_{\ell\in[L]}h_{T_{1}\cup\cdots\cup
T_{\ell-1}}(T_{\ell})-2L\kappa\geq\sum_{\ell\in[L]}|T_{\ell}|(1+\epsilon)^{-\ell+1}\operatorname{OPT}-\epsilon\operatorname{OPT}.$

As a result, we have

$f(O_{1})+\sum_{\ell\in[2:L]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(P_{\ell})\leq(1+\epsilon)(f(T)+\epsilon\operatorname{OPT})+4\epsilon\operatorname{OPT}\leq(1+\epsilon)f(T)+6\epsilon\operatorname{OPT}.$
(13)

∎

We bound the second term of Eq. (11) as follow.

######  Lemma 6.7.

We have

$\sum_{\ell\in[2:L]}\sum_{r\in[0:\ell-2]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(O_{\ell}\cap E_{r})\leq 8\epsilon\operatorname{OPT}.$

###### Proof.

The proof can be derived via the following chain of inequalities.

$\displaystyle\sum_{\ell\in[2:L]}\sum_{r\in[0:\ell-2]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(O_{\ell}\cap E_{r})$
$\displaystyle=\sum_{r\in[0:L-2]}\sum_{\ell\in[r+2:L]}f_{T_{1}\cup\cdots\cup
T_{\ell-1}}(O_{\ell}\cap E_{r})$
$\displaystyle\leq\sum_{r\in[0:L-2]}f_{T_{1}\cup\cdots\cup T_{r}}(E_{r})$
$\displaystyle\leq\sum_{r\in[0:L-2]}f_{T_{1}\cup\cdots\cup T_{r-1}\cup
S_{r}}(E_{r})+\sum_{r\in[0:L-2]}f_{T_{1}\cup\cdots\cup T_{r}}(S_{r}\backslash
T_{r})$ $\displaystyle\leq\sum_{r\in[0:L-2]}f_{T_{1}\cup\cdots\cup T_{r-1}\cup
S_{r}}(E_{r})+2\epsilon\operatorname{OPT}$
$\displaystyle\leq\sum_{r\in[0:L-2]}\sum_{o\in E_{r}}f_{T_{1}\cup\cdots\cup
T_{r-1}\cup S_{r}}(o)+2\epsilon\operatorname{OPT}$
$\displaystyle\leq\sum_{r\in[0:L-2]}\sum_{o\in E_{r}}h_{T_{1}\cup\cdots\cup
T_{r-1}\cup S_{r}}(o)+3\epsilon\operatorname{OPT}$
$\displaystyle\leq\sum_{r\in[0:L-2]}|E_{r}|(1+\epsilon)^{-r+1}\operatorname{OPT}+3\epsilon\operatorname{OPT}$
$\displaystyle\leq\sum_{r\in[0:L-2]}|S_{r+1}\backslash
T_{r+1}|(1+\epsilon)^{-r+1}\operatorname{OPT}+3\epsilon\operatorname{OPT}$
$\displaystyle\leq(1+\epsilon)\sum_{r=0}^{L-2}f_{T_{1}\cup\cdots\cup
T_{r+1}}(S_{r+1}\backslash T_{r+1})+4\epsilon\operatorname{OPT}$
$\displaystyle\leq 8\epsilon\operatorname{OPT}.$ (14)

The second step holds due to the submodularity and monotonicity. The third
step holds due to Fact 6.6, and the fourth step holds due to Eq. (12). The
fifth step follows from submodularity. The sixth step holds since $h$ is
$\kappa$-close to $f$ and using $2k\kappa\leq\epsilon\operatorname{OPT}$. The
seventh step holds since every $o\in E_{r}$ has $T_{1}\cup\cdots\cup
T_{r-1}\cup S_{r}\cup\\{o\\}\in\mathcal{M}$. Hence, it follows from the
$L$-pass greedy algorithm that

$h_{T_{1}\cup\cdots\cup T_{r-1}\cup
S_{r}}(o)\leq(1+\epsilon)^{-r+1}\operatorname{OPT}.$

The seventh step holds due to Claim 6.4 that $|E_{r}|\leq|S_{r+1}\backslash
T_{r+1}|$. The eighth step holds since

$f_{T_{1}\cup\cdots\cup T_{r+1}}(S_{r+1}\backslash T_{r+1})\geq
h_{T_{1}\cup\cdots\cup T_{r+1}}(S_{r+1}\backslash
T_{r+1})-\kappa\geq|S_{r+1}\backslash
T_{r+1}|(1+\epsilon)^{-r}\operatorname{OPT}-\kappa,$

and the last step holds due to (12). ∎

Combining Lemma 6.5, Lemma 6.7 and Eq. (11), we have
$f_{T}(O)\leq(1+\epsilon)f(T)+11\epsilon\operatorname{OPT}.$ Since this holds
for all feasible sets, and in particular, it holds for the set $O_{t}$. Taking
a linear combination, we have

$\displaystyle
f(T)\geq\frac{1}{1+\epsilon}\big{(}(1-11\epsilon)f_{T}(O)+11\epsilon
f_{T}(O_{t})-11\epsilon\operatorname{OPT}\big{)}\geq\frac{1}{1+\epsilon}\big{(}(1-11\epsilon)f_{T}(O)-11\epsilon
f(T)\big{)}.$

Rearranging the term, we get the desired.

Finally, we bound the amortized query complexity of the algorithm. We charge
the two queries made in the evaluation of $h_{S}(e)$ (line 7 or 18) to $e$ and
show that the number of queries charged to $e$ is at most $O(L)$. To see this,
we note that $e$ is charged twice when it is just inserted. Every time $e$ is
charged during Revoke, either it is added to $S$ so that it is never charged
again, or its marginal contribution is small and won’t be queried in the
$\ell$-th level later. Hence, $e$ has been queried for at most $O(L)$ times.
We conclude the proof here. ∎

By standard argument, we conclude

######  Lemma 6.8.

Given a matroid $\mathcal{M}$, let $t>0$,
$\operatorname{OPT}\leq\operatorname{OPT}_{t}\leq(1+\epsilon)\operatorname{OPT}$.
After inserting the $t$-th element, our algorithm outputs a feasible set $S$
that satisfies $f(S)\geq(1/2-O(\epsilon))\operatorname{OPT}.$ The expected
number of oracles per operation is $k^{\widetilde{O}(1/\epsilon)}$.

The proof can be found at Appendix D. Combine with Lemma C.1, we have

######  Theorem 6.9.

Given any matroid $\mathcal{M}$, for any $\epsilon>0$, there is a
combinatorial algorithm that maintains a feasible set $S$ with
$(1/2-\epsilon)$-approximation at each iteration. Moreover, the amortized
number of queries per update is $k^{\widetilde{O}(1/\epsilon)}$.

###  6.2 Amplification via accelerated continuous greedy

We amplify the approximation ratio of the combinatorial algorithm via the
accelerated continuous greedy framework [BV14]. Let $m=O(1/\epsilon)$ and

$D=\\{\operatorname{OPT},(1+\epsilon)^{-1}\operatorname{OPT},\cdots,(1+\epsilon)^{-\lceil
4\log(1/\epsilon)/\epsilon\rceil}\operatorname{OPT}\\}\cup\\{0\\}.$

We run a separate branch for each $\mathbf{d}\in D^{m}$ and
$\mathbf{a}\in\mathcal{A}^{m}$. Intuitively, $d_{\tau}\in D$ should be seen as
an estimate on the progress of optimal solution in the $\tau$-th iteration,
and $a_{\tau}\in\mathcal{A}$ is a guess on the greedy sequence. Our algorithm
segragates answer from all branches and outputs the one with the maximum
value. In order to return an integral solution, the algorithm rounds the
fractional solution via the swap rounding approach [CVZ10]. The algorithm
description is presented in Algorithm 5.

Algorithm 5 Amplification via accelerated continuous greedy

1:Input: $\mathbf{d}\in D^{m},\mathbf{a}\in\mathcal{A}^{m}$

2:Initialize $\mathbf{x}\leftarrow\mathbf{0}$

3:for $\tau=1,2,\cdots,m$ do

4: Define $g(S)=F(\mathbf{x}+\frac{1}{m}S)-F(\mathbf{x})$ for all $S\subseteq
V$

5: Invoke Prune-greedy($d_{\tau},a_{\tau}$, g), and wait until it returns a
solution $S_{\tau}$

6: $\mathbf{x}\leftarrow\mathbf{x}+\frac{1}{m}S_{\tau}$

7:end for

We need the following Lemma in our analysis. The proof idea follows from
[BV14] and it appears in [CQ19, BRS19b]. It has some minor difference with
previous work and we provide a proof for completeness.

######  Lemma 6.10.

Let
$\operatorname{OPT}\leq\operatorname{OPT}_{t}\leq(1+\epsilon)\operatorname{OPT}$.
Suppose in each iteration of Algorithm 5, Prune-greedy returns a set $S$
satisfies

$\displaystyle
g(S)\geq(1-O(\epsilon))g_{S}(O_{t})-\epsilon^{2}\operatorname{OPT}.$ (15)

Then, the final solution $\mathbf{x}$ satisfies

$F(\mathbf{x})\geq(1-1/e-O(\epsilon))\operatorname{OPT}.$

###### Proof.

For any $\tau\in[m]$, let $x_{\tau}$ denote the fractional solution at the end
of $\tau$-th iteration, i.e. after the update at Line 6 of Algorithm 5, one
has

$\displaystyle F(\mathbf{x}_{\tau})-F(\mathbf{x}_{\tau-1})=$
$\displaystyle\leavevmode\nobreak\ g(S_{\tau})$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\
(1-O(\epsilon))g_{S_{\tau}}(O_{t})-\epsilon^{2}\operatorname{OPT}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
(1-O(\epsilon))\left(F\left(\mathbf{x}_{\tau}+\frac{1}{m}O_{t}\right)-F(\mathbf{x}_{\tau})\right)-\epsilon^{2}\operatorname{OPT}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
(1-O(\epsilon))\left(\frac{1}{m}F(\mathbf{x}_{\tau}+O_{t})+\left(1-\frac{1}{m}\right)F(\mathbf{x}_{\tau})-F(\mathbf{x}_{\tau})\right)-\epsilon^{2}\operatorname{OPT}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{m}(1-O(\epsilon))(F(\mathbf{x}_{\tau}+O_{t})-F(\mathbf{x}_{\tau}))-\epsilon^{2}\operatorname{OPT}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\frac{1}{m}(1-O(\epsilon))(F(O_{t})-F(\mathbf{x}_{\tau}))-\epsilon^{2}\operatorname{OPT}.$

The first and third step holds due to the definition of $g$, the second step
holds due to Eq. (15). The fourth step holds due to the submodularity of the
multilinear extension $F$. The last step is due to monotonicity.

Recurring the above equation for all $\tau\in[m]$, via standard calculation,
one can show that

$F(T)\geq(1-1/e-O(\epsilon))F(O_{t})=(1-1/e-O(\epsilon))\operatorname{OPT}.\qed$

See 1.4

###### Proof.

With Lemma C.1, it suffices to prove for any $t$, when
$\operatorname{OPT}\leq\operatorname{OPT}_{t}\leq(1+\epsilon)\operatorname{OPT}$,
our algorithm returns a solution set $S$ with
$f(S)\geq(1-1/e-O(\epsilon))\operatorname{OPT}_{t}$. Let $O_{t}$ be the
optimal solution. For any $\tau\in[m]$, let
$g^{(\tau)}(S):=F(\mathbf{x}_{\tau-1}+\frac{1}{m}S)$ and let
$(1+\epsilon)^{-\ell}\operatorname{OPT}\leq
g^{(\tau)}(O_{t})\leq(1+\epsilon)^{-\ell+1}\operatorname{OPT}$. When
$\ell\leq\lceil 4\log(1/\epsilon)/\epsilon\rceil$, we take
$d_{\tau}=(1+\epsilon)^{-\ell}\operatorname{OPT}$ and we know $d_{\tau}\leq
g^{(\tau)}(O)\leq(1+\epsilon)d_{\tau}$; otherwise, we set $d_{\tau}=0$. By
Lemma 6.1, we know there exists a branch $a\in\mathcal{A}$ that returns a
solution $S_{a,\tau}$ such that

$g^{(\tau)}(S_{a,\tau})\geq(1-O(\epsilon))g^{(\tau)}_{S_{a,\tau}}(O_{t})-\epsilon^{2}\operatorname{OPT}.$

We will use this sequence and set $a_{\tau}=a$. By recursively applying it for
all $\tau\in[m]$, the resulting $\mathbf{d},\mathbf{a}$ satisfy the condition
of Lemma 6.10, and we conclude the algorithm returns a solution $\mathbf{x}$
with $F(\mathbf{x})\geq(1-1/e-O(\epsilon))\operatorname{OPT}$.

For the amortized query complexity, the total number of branch equals

$|\mathcal{A}^{m}|\cdot|D^{m}|=k^{\widetilde{O}(1/\epsilon^{2})}\cdot(1/\epsilon)^{\widetilde{O}(1/\epsilon)}=k^{\widetilde{O}(1/\epsilon^{2})}.$

For each branch, there are $O(1/\epsilon)$ iterations, and in each iteration,
we run our combinatorial algorithm with a scheduel sequence
$a_{\tau}\in\mathcal{A}$. By Lemma 6.1, the amortized number of query (to
function $g$) equals $O(L)=O(\log(k/\epsilon)/\epsilon)$. We note that in the
accelerated continuous greedy algorithm, a query to function $g$ is equivalent
to two queries of the multilinear extension. To satisfy the requirement of
Lemma 6.1, one evaluates the value of multilinear extension with error
$\pm\epsilon^{3}/k$ and confidence
$\delta=\frac{\epsilon}{\operatorname{poly}(n)|\mathcal{A}^{m}||\mathcal{D}^{m}|L}$
using $\widetilde{O}(\epsilon^{-8}k^{2}\log n)$ query to the original function
$f$. Thus in total, the amortized number of query is at most

$k^{\widetilde{O}(1/\epsilon^{2})}\cdot\epsilon^{-1}\cdot\epsilon^{-1}\log(k/\epsilon)\cdot\widetilde{O}(\epsilon^{-8}k^{2}\log
n)=k^{\widetilde{O}(1/\epsilon^{2})}\log n.$

We also need to round the fractional solution to an integral one. The solution
is the convex combination of at most $O(1/\epsilon)$ independent sets, it
takes only $O(k^{2}/\epsilon)$ query to perform the swap rounding [CVZ10].
Hence, the overall amortized query complexity is
$k^{\widetilde{O}(1/\epsilon^{2})}\log n$. ∎

##  7 Conclusions

We study the power and limitations of dynamic algorithms for submodular
maximization. On the lower bound side, we prove a polynomial lower bound on
the amortized query complexity for achieving a $(1/2+\epsilon)$-approximation,
together with a linear lower bound for $0.584$-approximation, under fully
dynamic streams with insertions and deletions. On the algorithmic side, we
develop efficient $(1-1/e)$-approximation algorithms for insertion-only
streams under both cardinality and matroid constraints. We believe that
dynamic submodular maximization is a problem of significant importance in
theory and practice, and there are many interesting directions for further
investigations:

  * •

There is still space for improvement on our lower bounds. Is it possible to
prove a linear lower bound for $({1}/{2}+\epsilon)$-approximation? Or is it
actually possible to develop a sublinear algorithm (in amortized complexity)
that achieves a $(1/2+\Omega(1))$-approximation?

  * •

Many submodular functions important in practice can be accessed in white box
models instead of query models, e.g., the MAX-$k$ coverage problem, influence
maxmization under independent cascade model or linear threshold model. Can
ideas in this paper be extended to obtain upper/lower bounds on amortized time
complexity for these problems?

  * •

Can we extend results (algorithm or hardness) to non-monotone submodular
maximization? As far as we know, there is no known constant-factor
approximation algorithm with $\operatorname{poly}(k)$ amortized query
complexity for the non-monotone setting under fully dynamic streams. How does
the dynamic model compare to streaming model [AEF+20] under this setting?

  * •

For matroid constraints, can one improve the query complexity to $O(k^{2})$ or
even $O(k)$ over insertion-only streams? Also, for fully dynamic streams,
there is no known constant-factor approximation algorithm with
$\operatorname{poly}(k)$ amortized queries for matroid constraints.

## References

  * [AEF+20] Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh.  Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:19, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [BENW15] 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. PMLR, 2015.
  * [BENW16] Rafael da Ponte Barbosa, Alina Ene, Huy L Nguyen, and Justin Ward.  A new framework for distributed submodular maximization.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 645–654. Ieee, 2016.
  * [BF18] Niv Buchbinder and Moran Feldman.  Submodular functions maximization problems., 2018.
  * [BFS17] Niv Buchbinder, Moran Feldman, and Roy Schwartz.  Comparing apples and oranges: Query trade-off in submodular maximization.  Mathematics of Operations Research, 42(2):308–329, 2017.
  * [BFSS15] Niv Buchbinder, Moran Feldman, Joseph Seffi, and Roy Schwartz.  A tight linear time (1/2)-approximation for unconstrained submodular maximization.  SIAM Journal on Computing, 44(5):1384–1402, 2015.
  * [BH11] Maria-Florina Balcan and Nicholas JA Harvey.  Learning submodular functions.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 793–802, 2011.
  * [BMKK14] 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, 2014.
  * [BRS17] Eric Balkanski, Aviad Rubinstein, and Yaron Singer.  The limitations of optimization from samples.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1016–1027, 2017.
  * [BRS19a] Eric Balkanski, Aviad Rubinstein, and Yaron Singer.  An exponential speedup in parallel running time for submodular maximization without loss in approximation.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 283–302. SIAM, 2019.
  * [BRS19b] Eric Balkanski, Aviad Rubinstein, and Yaron Singer.  An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 66–77, 2019.
  * [BS18a] Eric Balkanski and Yaron Singer.  The adaptive complexity of maximizing a submodular function.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1138–1151, 2018.
  * [BS18b] Eric Balkanski and Yaron Singer.  Approximation guarantees for adaptive sampling.  In International Conference on Machine Learning, pages 384–393. PMLR, 2018.
  * [BV14] Ashwinkumar Badanidiyuru and Jan Vondrák.  Fast algorithms for maximizing submodular functions.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1497–1514. SIAM, 2014.
  * [CCPV11] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák.  Maximizing a monotone submodular function subject to a matroid constraint.  SIAM Journal on Computing, 40(6):1740–1766, 2011.
  * [CGQ15] Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud.  Streaming algorithms for submodular function maximization.  In International Colloquium on Automata, Languages, and Programming, pages 318–330. Springer, 2015.
  * [CQ19] Chandra Chekuri and Kent Quanrud.  Parallelizing greedy for submodular set function maximization in matroids and beyond.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 78–89, 2019.
  * [CVZ10] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.  Dependent randomized rounding via exchange properties of combinatorial structures.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 575–584. IEEE, 2010.
  * [CVZ14] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  SIAM Journal on Computing, 43(6):1831–1879, 2014.
  * [EN19] Alina Ene and Huy L Nguyen.  Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 274–282. SIAM, 2019.
  * [ENV19] Alina Ene, Huy L Nguyen, and Adrian Vladu.  Submodular maximization with matroid and packing constraints in parallel.  In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pages 90–101, 2019.
  * [Fei98] Uriel Feige.  A threshold of $\ln n$ for approximating set cover.  Journal of the ACM, 45(4):634–652, 1998.
  * [FMZ19] Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam.  Submodular maximization with nearly optimal approximation, adaptivity and query complexity.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 255–273. SIAM, 2019.
  * [FNFSZ20] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen.  The one-way communication complexity of submodular maximization with applications to streaming and robustness.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1363–1374, 2020.
  * [FNS11] Moran Feldman, Joseph Naor, and Roy Schwartz.  A unified continuous greedy algorithm for submodular maximization.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 570–579. IEEE, 2011.
  * [GK11] Daniel Golovin and Andreas Krause.  Adaptive submodularity: Theory and applications in active learning and stochastic optimization.  Journal of Artificial Intelligence Research, 42:427–486, 2011.
  * [KKT03] 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, 2003.
  * [LB11] 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, pages 510–520, 2011\.
  * [LMNF+20] Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakub Tarnawski, and Morteza Zadimoghaddam.  Fully dynamic algorithm for constrained submodular optimization.  Advances in Neural Information Processing Systems, 2020.
  * [Mon20] Morteza Monemizadeh.  Dynamic submodular maximization.  Advances in Neural Information Processing Systems, 33, 2020.
  * [MSV08] Vahab Mirrokni, Michael Schapira, and Jan Vondrák.  Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions.  In Proceedings of the 9th ACM conference on Electronic commerce, pages 70–77, 2008.
  * [MZ15] 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, 2015.
  * [NW78] George L Nemhauser and Laurence A Wolsey.  Best algorithms for approximating the maximum of a submodular set function.  Mathematics of operations research, 3(3):177–188, 1978.
  * [NWF78] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.  An analysis of approximations for maximizing submodular set functions.  Mathematical programming, 14(1):265–294, 1978.
  * [Rou10] Tim Roughgarden.  Algorithmic game theory.  Communications of the ACM, 53(7):78–86, 2010.
  * [Von13] Jan Vondrák.  Symmetry and approximability of submodular maximization problems.  SIAM Journal on Computing, 42(1):265–304, 2013.
  * [WIB15] Kai Wei, Rishabh Iyer, and Jeff Bilmes.  Submodularity in data subset selection and active learning.  In International Conference on Machine Learning, pages 1954–1963. PMLR, 2015.

##  Appendix A Missing proof from Section 3

###  A.1 Missing proof from Section 3.1

Let $x\in[0,1]^{w}$ and $\overline{x}=\frac{1}{w}\sum_{i=1}^{w}x_{i}$.
Consider the function

$\displaystyle f(x)=1-\prod_{i=1}^{w}(1-x_{i})$

and its symmetric version

$\displaystyle g(x)=1-(1-\overline{x})^{w}.$

The follow Lemma comes from Lemma 2.4 of [MSV08], we make some minor
modifications and provide the proof here for completeness.

######  Theorem A.1 (Restatement of Theorem 3.1).

For any $w\in\mathbb{Z}$, $\epsilon>0$ let
$\gamma=w^{-1}\exp(-4w^{6}/\epsilon)$. There is a function
$\widehat{f}:[0,1]^{w}\rightarrow[0,1]$ satisfies

  * •

When $\max_{i,j}|x_{i}-x_{j}|\leq\gamma$, $\widehat{f}(x)=g(x)$.

  * •

For any $x\in[0,1]^{w}$, $f(x)\geq\widehat{f}(x)\geq f(x)-\epsilon$.

Let $h(x):[0,1]^{w}\rightarrow[0,1]$ be the difference of $f(x)$ and $g(x)$,
i.e., $h(x)=f(x)-g(x)$. Here are some basic properties of $h(x)$.

######  Lemma A.2 (Claim of [MSV08]).

Let $h(x)=f(x)-g(x)$, and $\max_{i,j\in[w]}|x_{i}-x_{j}|=\delta$, then one has

  * •

$h(x)\leq w\delta(1-\overline{x})^{w-1}$.

  * •

$h(x)\geq w^{-4}\delta^{2}(1-\overline{x})^{w-2}$

  * •

$|\frac{\partial h}{\partial x_{j}}|\leq w\delta(1-\overline{x})^{w-2}$, i.e.
$|\frac{\partial h}{\partial x_{j}}|\leq
w^{3}(1-\overline{x})^{w/2-1}\sqrt{h(x)}$.

Define $\widetilde{f}(x)=f(x)-\phi(h(x))$ where $\phi:[0,1]\rightarrow[0,1]$
controls the interpolation between $f(x)$ and $g(x)$.

######  Lemma A.3 ([MSV08]).

Let $\epsilon_{1}=w\gamma=\exp(-4w^{6}/\epsilon)$,
$\epsilon_{2}=\exp(-2w^{6}/\epsilon)$, $\alpha=\frac{1}{2}w^{-6}\epsilon$,
There is a function $\phi:[0,1]\rightarrow[0,1]$ that satisfies

  * •

For $t\in[0,\epsilon_{1}]$, $\phi(t)=t$.

  * •

For $t\in[\epsilon_{1},\epsilon_{2}]$, the second derivative is
$\phi^{\prime\prime}(t)=-\alpha/t$ and the first derivative of $\phi$ is
continuous at $t=\epsilon_{1}$, hence,

$\phi^{\prime}(t)=1-\int_{\epsilon_{1}}^{t}\frac{\alpha}{\tau}d\tau=1-\alpha\log\frac{t}{\epsilon_{1}}.$

  * •

For $t>\epsilon_{2}$, we set $\phi(t)=\phi(\epsilon_{2})<1$.

Next, we show that $\widetilde{f}$ is close to a monotone submodular function,
by bounding its first derivative and second derivative.

######  Lemma A.4.

For any $i,j\in[w]$, one has

$\frac{\partial\widetilde{f}}{\partial x_{j}}\geq
0\quad\text{and}\quad\frac{\partial^{2}\widetilde{f}}{\partial x_{i}\partial
x_{j}}\leq\frac{1}{2}\epsilon(1-\overline{x})^{w-2}.$

###### Proof.

For the first derivative, we have

$\frac{\partial\widetilde{f}}{\partial x_{j}}=\frac{\partial f}{\partial
x_{j}}-\phi^{\prime}(h)\frac{\partial h}{\partial
x_{j}}=(1-\phi^{\prime}(h))\frac{\partial f}{\partial
x_{j}}+\phi^{\prime}(h)\frac{\partial g}{\partial x_{j}}.$

Since $0\leq\phi^{\prime}(h)\leq 1$, and $\frac{\partial g}{\partial
x_{j}},\frac{\partial f}{\partial x_{j}}\geq 0$, the first partial derivative
is always non-negative. ∎

For the second partial derivatives, we have

$\displaystyle\frac{\partial^{2}\widetilde{f}}{\partial x_{i}\partial x_{j}}=$
$\displaystyle\leavevmode\nobreak\ \frac{\partial^{2}f}{\partial x_{i}\partial
x_{j}}-\phi^{\prime}(h)\frac{\partial^{2}h}{\partial x_{i}\partial
x_{j}}-\phi^{{}^{\prime\prime}}(h)\frac{\partial h}{\partial
x_{i}}\frac{\partial h}{\partial x_{j}}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
(1-\phi^{\prime}(h))\frac{\partial^{2}f}{\partial x_{i}\partial
x_{j}}+\phi^{\prime}(h)\frac{\partial^{2}g}{\partial x_{i}\partial
x_{j}}-\phi^{\prime\prime}(h)\frac{\partial h}{\partial x_{i}}\frac{\partial
h}{\partial x_{j}}$

The first two terms are non-negative. To control the third term, we note that
$\phi^{\prime\prime}(h)\leq\alpha/h$ (Lemma A.3) and by Lemma A.2

$\left|\frac{\partial h}{\partial x_{j}}\right|\leq
w^{3}(1-\overline{x})^{w/2-1}\sqrt{h(x)}$

Hence, we conclude that

$\frac{\partial^{2}\widetilde{f}}{\partial x_{i}\partial
x_{j}}\leq\left|\phi^{\prime\prime}(h)\frac{\partial h}{\partial
x_{i}}\frac{\partial h}{\partial x_{j}}\right|\leq\alpha
w^{6}(1-\overline{x})^{w-2}=\frac{1}{2}\epsilon(1-\overline{x})^{w-2}$

###### Proof of Theorem A.1.

In order to make $\widetilde{f}$ a submodular function, we need to make the
second partial derivatives non-positive. Note that
$\frac{\partial^{2}g}{\partial x_{i}\partial
x_{j}}=-\frac{w-1}{w}(1-\overline{x})^{w-2}$. Therefore, it suffices to take

$\widehat{f}(x)=\frac{1}{1+\epsilon}\left(\widetilde{f}(x)+\epsilon
g(x)\right).$

It is clear that $\widehat{f}$ is nonnegative and
$f(x)\leq\frac{1}{1+\epsilon}(\widetilde{f}(x)+\epsilon
g(x))\leq\frac{1}{1+\epsilon}(1+\epsilon)=1$. The function $\widehat{f}$ is
monotone since both $\widetilde{f}$ and $g$ are monotone. For second partial
derivatives, by Lemma A.4 one has

$\frac{\partial^{2}f}{\partial x_{i}\partial
x_{j}}\leq\frac{2}{2+\epsilon}\left(\frac{1}{2}\epsilon(1-\overline{x})^{w-2}-\epsilon\frac{w-1}{w}(1-\overline{x})^{w-2}\right)\leq
0.$

Hence, we proved $\widehat{f}$ is sbumodular. When
$\max_{i,j}|x_{i}-x_{j}|\leq\gamma$, one has $h(x)\leq
w\gamma(1-\overline{x})^{w-1}\leq w\gamma=\epsilon_{1}$. Therefore,
$\phi(h(x))=h(x)=f(x)-g(x)$ and

$\displaystyle\widehat{f}(x)=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{1+\epsilon}\left(\widetilde{f}(x)+\epsilon
g(x)\right)=\frac{1}{1+\epsilon}\left(f(x)-\phi(h(x))+\epsilon g(x)\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{1+\epsilon}\left(g(x)+\epsilon g(x)\right)=g(x).$

While for any $x\in[0,1]$, one has

$\widehat{f}(x)=\frac{1}{1+\epsilon}\left(\widetilde{f}(x)+\epsilon
g(x)\right)\leq\frac{1}{1+\epsilon}\left(f(x)+\epsilon f(x)\right)=f(x)$

and

$\widehat{f}(x)\geq\frac{1}{1+\epsilon}\widetilde{f}(x)\geq\frac{1}{1+\epsilon}(f(x)-\epsilon_{2})\geq
f(x)\geq f(x)-\epsilon.$

∎

We next provide the proof for Lemma 3.2, which provides basic properties of
$\widehat{F}$.

###### Proof of Lemma 3.2.

Since $\widehat{f}(x_{i})\in[0,1]$, we have $\widehat{F}(x)\in[0,1]$.
$\widehat{F}$ is monotone, because for any $i\in[m],j\in[w]$,

$\frac{\partial\widehat{F}}{\partial
x_{i,j}}=\frac{\partial\widehat{f}}{\partial x_{i,j}}\prod_{\ell\neq
i}\big{(}1-\widehat{f}(x_{\ell})\big{)}\geq 0.$

Next we show that $\widehat{F}$ is submodular. For any
$i,i^{\prime}\in[m],j,j^{\prime}\in[w]$, when $i\neq i^{\prime}$, one has

$\frac{\partial^{2}\widehat{F}}{\partial x_{i,j}\partial
x_{i^{\prime},j^{\prime}}}=-\frac{\partial\widehat{f}}{\partial
x_{i,j}}\frac{\partial\widehat{f}}{\partial
x_{i^{\prime},j^{\prime}}}\prod_{\ell\neq
i,i^{\prime}}\big{(}1-\widehat{f}(x_{\ell})\big{)}\leq 0$

given that $\widehat{f}$ is monotone. When $i=i^{\prime}$, since $\widehat{f}$
is submodular, one has

$\frac{\partial^{2}\widehat{F}}{\partial x_{i,j}\partial
x_{i^{\prime},j^{\prime}}}=\frac{\partial^{2}\widehat{f}}{\partial
x_{i,j}\partial x_{i,j^{\prime}}}\prod_{\ell\neq
i}\big{(}1-\widehat{f}(x_{\ell})\big{)}\leq 0.$

Hence, we conclude $\widehat{F}$ is submodular.

The second property directly follows from Theorem 3.1. For the last property,
suppose $x_{i,j}=1$. Then we have $\smash{\widehat{f}(x_{i})\geq
f(x_{i})-\epsilon=1-\epsilon}$. Hence,

$\widehat{F}(x)=1-\prod_{i\in[s]}(1-\widehat{f}(x_{i}))\geq 1-\epsilon.$

This finishes the proof of the lemma. ∎

###  A.2 Missing proof from Section 3.2

We provide the proof for Lemma 3.5.

###### Proof of Lemma 3.5.

Let $S_{B}$ be the index defined as

$S_{B}:=\\{i:S\cap B_{i}\neq\emptyset,i\in[m]\\}.$

We also define index set $S_{A,\pi}$ for the bijection $\pi,\pi^{\prime}$

$S_{A,\pi}:=\\{i:S\cap A_{\pi(i)}\neq\emptyset,i\in[m]\\}\quad\text{and}\quad
S_{A,\pi^{\prime}}:=\\{i:S\cap A_{\pi^{\prime}(i)}\neq\emptyset,i\in[m]\\}.$

Suppose $\pi,\pi^{\prime}$ satisfies the condition of the Lemma, we conclude
that

$\displaystyle S_{B}\cap S_{A,\pi}=S_{B}\cap S_{A,\pi^{\prime}}=\\{i:S\cap
B_{i}\neq\emptyset\text{ and }S\cap(A_{\pi(i)}\cup
A_{\pi^{\prime}(i)})\neq\emptyset,i\in[m]\\}.$

Consider the following mapping $\sigma:[m]\rightarrow[m]$, $\sigma$ is
identity on $[m]\backslash(S_{A,\pi}\cup S_{A,\pi^{\prime}}\backslash S_{B})$,
and it forms an one-to-one mapping on $S_{A,\pi}\cup
S_{A,\pi^{\prime}}\backslash S_{B}$, such that for any $i\in S_{A,\pi}$,
$\pi(i)=\pi^{\prime}(\sigma(i))$. One can prove such mapping always exists
when the condition of the Lemma holds. and it is an one-to-one mapping on
$[m]$.

We can extend $\sigma$ and define $\sigma(I):=\\{\sigma(i):i\in I\\}$ for any
$I\subseteq[m]$. Since $\sigma$ is an one-to-one mapping on $[m]$, we have
that $\sigma$ forms a bijection on $2^{[m]}$ and $|\sigma(I)|=|I|$. In order
to show $\mathcal{G}_{\pi}(S)=\mathcal{G}_{\pi^{\prime}}(S)$, it suffices to
prove

$\displaystyle\sum_{I\subseteq[m]}\beta^{|I|}(1-\beta)^{m-|I|}G(x^{S,I,\pi})=\sum_{I\subseteq[m]}\beta^{|I|}(1-\beta)^{m-|I|}G(x^{S,I,\pi^{\prime}}).$
(16)

Let
$\overline{x}^{S,I,\pi}_{i}:=\frac{1}{w}\sum_{j\in[w]}\overline{z}^{S}_{i,j}=\frac{1}{w}\sum_{j\in[w]}\frac{|S\cap
B_{i,j}|}{(1-\alpha)k}=\frac{1}{w}\frac{|S\cap B_{i}|}{(1-\alpha)k}$ for
$i\notin I$ and
$\overline{x}^{S,I,\pi}_{i}:=\frac{1}{w}\sum_{j\in[w]}\overline{y}^{S}_{\pi(i),j}=\frac{1}{w}\sum_{j\in[w]}\frac{|S\cap
A_{\pi(i),j}|}{\alpha k}=\frac{1}{w}\frac{|S\cap A_{\pi(i)}|}{\alpha k}$. We
define $\overline{x}^{S,I,\pi^{\prime}}_{i}$ accordingly. Then we have

$\displaystyle G(x^{S,I,\pi})=$ $\displaystyle\leavevmode\nobreak\
1-\prod_{i\in[m]}(1-g(x^{S,I,\pi}_{i}))=1-\prod_{i\in[m]}(1-\overline{x}^{S,I,\pi}_{i})^{w}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ 1-\prod_{i\in[m]\backslash
I}\left(1-\frac{1}{w}\frac{|S\cap B_{i}|}{(1-\alpha)k}\right)^{w}\prod_{i\in
I}\left(1-\frac{1}{w}\frac{|S\cap A_{\pi(i)}|}{\alpha k}\right)^{w}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ 1-\prod_{i\in[m]\backslash
I}\left(1-\frac{1}{w}\frac{|S\cap B_{i}|}{(1-\alpha)k}\right)^{w}\prod_{i\in
I}\left(1-\frac{1}{w}\frac{|S\cap A_{\pi^{\prime}(\sigma(i))}|}{\alpha
k}\right)^{w}$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
1-\prod_{i\in[m]\backslash\sigma(I)}\left(1-\frac{1}{w}\frac{|S\cap
B_{i}|}{(1-\alpha)k}\right)^{w}\prod_{i\in\sigma(I)}\left(1-\frac{1}{w}\frac{|S\cap
A_{\pi^{\prime}(i)}|}{\alpha k}\right)^{w}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
1-\prod_{i\in[m]}(1-\overline{x}^{S,\sigma(I),\pi^{\prime}}_{i})^{w}=1-\prod_{i\in[m]}(1-g(x^{S,\sigma(I),\pi^{\prime}}_{i}))G(x^{S,\sigma(I),\pi}).$
(17)

The first three steps holds due to the definition $G$. The fourth step follows
from for any $i\in S_{A,\pi}$, $\pi(i)=\pi^{\prime}(\sigma(i))$, and for
$i\notin S_{A,\pi}$, $|S\cap A_{\pi(i)}|=0=|S\cap
A_{\pi^{\prime}(\sigma(i))}|$, and therefore $|S\cap A_{\pi(i)}|=|S\cap
A_{\pi^{\prime}(\sigma(i))}|$ holds for all $i\in[m]$. The fifth step follows
from $\sigma$ is identity on $S_{B}$, and hence,

$\prod_{i\in[m]\backslash I}\left(1-\frac{1}{w}\frac{|S\cap B_{i}|}{\alpha
k}\right)^{w}=\prod_{i\in[m]\backslash\sigma(I)}\left(1-\frac{1}{w}\frac{|S\cap
B_{i}|}{(1-\alpha)k}\right)^{w}.$

The last three steps follow from the definition of $G$.

Note that Eq. (17) implies Eq. (16) as $\sigma$ creates an one-to-on mappting
from $2^{[m]}$ to $2^{[m]}$ and $|I|=|\sigma(I)|$ for any $I\subseteq[m]$. ∎

Next, we prove Lemma 3.7.

###### Proof of Lemma 3.7.

Let $S$ be a set that is balanced, and we assume it consists of $\lambda k$
element from $B_{i^{*}}$ and $(1-\lambda k)$ from the $A_{1},\cdots,A_{m}$.

For any $I\subseteq[m]$, suppose $i^{*}\in I$. For any $i\notin I$, we know
that $\overline{x}_{i}^{S,I,\pi}:=\frac{1}{w}\sum_{j\in[w]}\frac{|B_{i,j}\cap
S|}{(1-\alpha)k}=0$ and for any $i\in I$,
$\overline{x}_{i}^{S,I,\pi}=\overline{y}^{S}_{\pi(i)}:=\sum_{j\in[w]}\frac{|S\cap
A_{\pi(i),j}|}{\alpha k}$, hence, we have

$\displaystyle\widehat{F}(x^{S,I,\pi})=G(x^{S,I,\pi})=$
$\displaystyle\leavevmode\nobreak\ 1-\prod_{i\in
I}\left(1-\frac{\overline{x}_{i}^{S,I,\pi}}{\alpha wk}\right)^{w}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ 1-\prod_{i\in
I}\exp\left(-w(1+\epsilon)\frac{\overline{x}_{i}^{S,I,\pi}}{\alpha wk}\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
1-\exp\left(-(1+\epsilon)\frac{\sum_{i\in I}\overline{x}_{i}^{S,I,\pi}}{\alpha
k}\right)$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
1-\exp\left(-\frac{\sum_{i\in I}\overline{x}_{i}^{S,I,\pi}}{\alpha
k}\right)+\epsilon.$ (18)

The first step holds since $S$ is balanced, the second step follows from the
definition. The third step follows from $1-x\geq e^{-(1+\epsilon)x}$ when
$x\leq\epsilon/10$ and $\frac{x_{i}^{S,I,\pi}}{\alpha
wk}\leq\frac{(1-\lambda)k}{\alpha wk}\leq\frac{1}{\alpha w}\leq\epsilon/10$.
The last step follows from $\exp(-c(1+\epsilon))\geq\exp(-c)-\epsilon$ for any
$\epsilon>0$ and $c>0$.

For any $i\in[m]$, let $X^{S,I,\pi}_{i}$ be a random variable such that
$X^{S,I,\pi}_{i}=\overline{x}^{S,I,\pi}_{i}$ with probability $\beta$ and
$X^{S,I,\pi}_{i}=0$ with probability $1-\beta$. Let
$K(x):\mathbb{R}^{m}\rightarrow\mathbb{R}$, and for any $x\in\mathbb{R}^{m}$,
$K(x)=1-\exp(\sum_{i=1}^{m}x_{i}/\alpha k)$. It is easy to verify that $K$ is
concave and one has

$\displaystyle\sum_{I\subseteq[m],i^{*}\in
I}\beta^{|I|}(1-\beta)^{m-|I|}\widehat{F}(x^{S,I,\pi})\leq$
$\displaystyle\leavevmode\nobreak\ \sum_{I\subseteq[m],i^{*}\in
I}\beta^{|I|}(1-\beta)^{m-|I|}\left(1-\exp\left(-\frac{\sum_{i\in
I}\overline{x}_{i}^{S,I,\pi}}{\alpha k}\right)+\epsilon\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sum_{I\subseteq[m],i^{*}\in
I}\beta^{|I|}(1-\beta)^{m-|I|}\left(1-\exp\left(-\frac{\sum_{i\in
I}\overline{x}_{i}^{S,I,\pi}}{\alpha k}\right)\right)+\beta\epsilon$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\beta\operatorname*{{\mathbb{E}}}_{X^{S,I,\pi}_{1},\cdots,X^{S,I,\pi}_{m}}\left[K(X^{S,I,\pi}_{i},\cdots,X^{S,I,\pi}_{i})\right]+\beta\epsilon$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ \beta
K(\overline{x}^{S,I,\pi}_{1},\cdots,\overline{x}^{S,I,\pi}_{m})+\beta\epsilon$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\beta\left(1-\exp\left(\frac{-(1-\lambda)\beta}{\alpha}\right)\right)+\beta\epsilon.$
(19)

The first step follows from Eq. (18), the third step follows from
$\pi(i^{*})\notin S$, and therefore, $\overline{x}_{i^{*}}^{S,I,\pi}=0$ when
$i^{*}\in I$. The fourth step follows the Jenson’s inequality and the
concavity of $K$. The last step follows from
$\sum_{i\in[m]}\overline{x}^{S,I,\pi}_{i}=(1-\lambda)k$.

Similarly, when $i^{*}\notin I$, we have
$\overline{x}_{i}^{S,I,\pi}=\overline{y}^{S}_{\pi(i)}:=\sum_{j\in[w]}\frac{|S\cap
A_{\pi(i),j}|}{\alpha k}$ for $i\in I$,
$\overline{x}_{i^{*}}^{S,I,\pi}=\overline{z}_{i^{*}}^{S}=\frac{\lambda
k}{(1-\alpha)kw}=\frac{\lambda}{(1-\alpha)w}$ and
$\overline{x}_{i}^{S,I,\pi}=\frac{1}{w}\sum_{j\in w}\frac{|B_{i,j}\cap
S|}{(1-\alpha)k}=0$ for $i\in[m]\backslash(I\cup\\{i^{*}\\})$. Therefore,

$\displaystyle\widehat{F}(x^{S,I,\pi})=G(x^{S,I,\pi})=$
$\displaystyle\leavevmode\nobreak\ 1-\prod_{i\in
I}\left(1-\frac{\overline{x}^{S,I,\pi}_{i}}{\alpha
wk}\right)^{w}\left(1-\overline{x}^{S,I,\pi}_{i^{*}}\right)^{w}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ 1-\prod_{i\in
I}\left(1-\frac{\overline{x}^{S,I,\pi}_{i}}{\alpha
wk}\right)^{w}\left(1-\frac{\lambda}{(1-\alpha)w}\right)^{w}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ 1-\prod_{i\in
I}\exp\left(-w(1+\epsilon)\frac{\overline{x}^{S,I,\pi}_{i}}{\alpha
wk}\right)\exp\left(-w(1+\epsilon)\frac{\lambda}{(1-\alpha)w}\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
1-\exp\left(-(1+\epsilon)\frac{\sum_{i\in I}\overline{x}^{S,I,\pi}_{i}}{\alpha
k}\right)\exp\left(-(1+\epsilon)\frac{\lambda}{1-\alpha}\right)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
1-\exp\left(-\frac{\sum_{i\in I}\overline{x}^{S,I,\pi}_{i}}{\alpha
k}\right)\exp\left(-\frac{\lambda}{1-\alpha}\right)+2\epsilon.$ (20)

The fourth step follows from $1-x\geq e^{-(1+\epsilon)x}$ when
$x\leq\epsilon/10$, $\frac{\overline{x}_{S,A,i}}{\alpha