# Fast Submodular Function Maximization

Lianke Qin<EMAIL_ADDRESS>UCSB. Zhao Song<EMAIL_ADDRESS>Adobe Research.
Yitan Wang<EMAIL_ADDRESS>Yale University.

Submodular functions have many real-world applications, such as document
summarization, sensor placement, and image segmentation. For all these
applications, the key building block is how to compute the maximum value of a
submodular function efficiently. We consider both the online and offline
versions of the problem: in each iteration, the data set changes incrementally
or is not changed, and a user can issue a query to maximize the function on a
given subset of the data. The user can be malicious, issuing queries based on
previous query results to break the competitive ratio for the online
algorithm. Today, the best-known algorithm for online submodular function
maximization has a running time of $O(nkd^{2})$ where $n$ is a total number of
elements, $d$ is the feature dimension and $k$ is the number of elements to be
selected. We propose a new method based on a novel search tree data structure.
Our algorithm only takes $\widetilde{O}(nk+kd^{2}+nd)$ time.

##  1 Introduction

Submodular functions are one important set of functions in machine learning
tasks. A submodular function is a set function defined on a set of data
points, and the function has the property that the incremental value for any
individual data point to the function value decreases as the size of the data
set increases. Submodular functions have many real-world applications,
including sparse estimation [70], mean field inference [7], variational
inference [21, 12], active learning [70], stochastic optimization [30],
document summeriazation [46]), sensor placement [51], and image segmentation
[58].

In these applications, we typically face an optimization problem to find the
maximum point of the submodular function subject to some constraints. Even for
the simplest constraints, e.g. cardinality constraints, maximize general
submodular functions can be NP-hard [28, 43]. Fortunately, it is well-known
that submodular function maximization with cardinality constraints can be well
approximated by greedily adding elements [53]. Submodular function
maximization with various other constraints and structure of objective
functions, including matroid constraints [14, 45, 15], knapsack constraints
[47, 64], min-cost coverage function [71], and mutual information function
[43, 52] are also studied. In practice, it sometimes happens that instead of
having access to the complete input data, we do not know the information about
the future and have to make online decisions [60, 50]. Recently, online
submodular function maximization has received much attention [59, 17].

For the general online convex optimization problem, $O(\sqrt{T})$ regret could
be achieved [75]. Then for a strongly convex function, the regret bound could
be improved to $O(\log T)$ [36]. It has been observed that convexity is
closely related to continuous submodularity [6]. In the partially transparent
feedback and deterministic setting, $(1-1/e)$-regret could be achieved [59].
The bandit setting was developed in [29] and has been broadly studied in a
series of works [22, 2, 8]. With stronger assumptions, sharper bounds could be
achieved [44, 1, 63, 37, 20, 9]. In [17], continuous submodular function
maximization in online setting was studied. Projection-free algorithm was
studied in [16]. Submodular bandit with extra structures, e.g. linear
submodular bandit and adaptive submodular bandit problem, were studied [73,
72, 31].

In this paper, we consider both the offline and the online versions of the
problem: in each iteration, the data set changes incrementally or is
unchanged, and a user can issue a query to maximize the function on a given
subset of the data. For the online setting, the user can be adversarial,
issuing queries based on previous query results to break the competitive ratio
for the the online algorithm. Today, the best-known algorithm for online
submodular function maximization has to pay $\Omega(n)$ to linear scan all the
$n$ items. To accelerate submodular function maximization algorithms and save
computation resources, we build an embedding representation of the submodular
maximization problem and propose a new method based on a novel search tree
data structure which only spends linear in $n$ time at the initialization. In
each iteration of the algorithm, we only need to pay sublinear in $n$ time to
pick an item to add into the set.

###  1.1 Our Results

The main result of this paper can be informally stated as Theorem 1.1.

######  Theorem 1.1 (Main result, informal version of Theorem F.1).

There exists an algorithm (Algorithm 1) that solves submodular function
maximization problem with the cardinality constraint in

$\displaystyle\widetilde{O}(nd+kn+kd^{2})$

time and returns a set $S$ with

$\displaystyle f(S)\geq(1-1/e)\max_{|T|=k}\\{f(T)\\}-k$

where $n$ is the size of the ground set, $d$ is the dimension of the problem
embedding, and $k$ is the cardinality constraint.

We remark that the best previous algorithm takes $O(nd^{2}k)$ time and returns
a set $S$ such that $f(S)\geq(1-1/e)\max_{|T|=k}\\{f(T)\\}$. See details in
Theorem 4.1 and Theorem 4.3.

Algorithm 1 Fast Submodular Function Maximization Algorithm

1:procedure
FastSubmodularAlgorithm($n,k,\\{u_{1},\cdots,u_{n}\\}\subseteq\mathbb{R}^{d}$)
$\triangleright$ Theorem 1.1

2: $S_{0}\leftarrow\emptyset$

3: DS ds.Init ($u_{1},u_{2},\cdots,u_{n},\epsilon,\delta/k$) $\triangleright$
Algorithm 5

4: for $t=0\to k-1$ do

5: $A_{t}\leftarrow h(S_{t})$

6: $j\leftarrow$ ds.Query($A_{t}$)

7: $S_{t+1}\leftarrow S_{t}\cup\\{j\\}$

8: ds.Delete($j$)

9: end for

10: return $S_{k}$

11:end procedure

#### Roadmap.

The rest of our paper is organized as follows. Section 2 formally defines
basic notations and our research problem. Section 3 provides an overview of
our techniques. Section 4 provides a benchmark of submodular algorithms, where
all of our algorithms are based on this benchmark. Section 5 gives an
auxiliary data structure to construct our main search data structure. Section
6 formally introduces and explains a fast quadratic form search data
structure, which is the critical part of this paper. At last, Section 7 makes
a summary of this paper.

##  2 Preliminary

###  2.1 Notations

For a square matrix $A$, we use $\operatorname{tr}[A]$ to denote the trace of
$A$. For a set $S\subseteq[n]$ , we use $\overline{S}$ to denote the
complementary set of $S$, which is equivalent to $[n]\backslash S$. If there
is no ambiguity, we will omit $[n]$. We use $n$ to denote the number of
elements in the ground set $[n]$. We use $d$ to denote the dimension of each
vector. For $t\geq 1$, we use $S_{t}$ to denote the set of selected elements
at time $1,2,\cdots,t$.

For two $d$-dimensional vectors $u,v$, we use $\langle u,v\rangle$ to denote
their inner product. For two $n\times m$-dimensional matrices $A,B$, we will
also use $\langle A,B\rangle$ to denote their inner product, that is, their
elementary-wise product. For any function $f$, we use $\widetilde{O}(f)$ to
denote $\operatorname{poly}(\log f)$.

###  2.2 Problem Formulation

We formalize the submodular function maximization problem with cardinality
constraint in this section. Informally, a set function is submodular if it has
decreasing marginal increment.

######  Definition 2.1 (Submodular function).

Let $f:2^{[n]}\rightarrow\mathbb{R}$ denote a set function. Define the
discrete derivative $\Delta_{f}$ as $\Delta_{f}(i|S):=f(S\cup\\{i\\})-f(S)$.
Function $f$ is submodular if for every $S\subseteq T$ and $i\in[n]-T$, it
holds that $\Delta_{f}(i|T)\leq\Delta_{f}(i|S).$

For the purpose of simplicity, we present the submodular maximization problem
with cardinality constraint in this paper. For other typical constraints like
knapsack constraint and matroid constraint, our method could naturally be
extended and we discuss the extension in section G.

#### Goal

In this paper, we are going to propose algorithms solving optimization problem
(1) efficiently.

$\displaystyle\max_{S\subseteq[n]}$ $\displaystyle f(S)$ (1) s.t.
$\displaystyle|S|\leq k$

#### Representation of $f(S)$

One problem arises in designing algorithm is how we select the representation
of input instances. As the constraint part in optimization problem (1) is
simple, it remains to decide the representation of $f(S)$. Suppose
$S=\\{i_{1},i_{2},\cdots,i_{m}\\}\subseteq[n]$, we could always decompose
$f(S)$ into sum of increment as

$\displaystyle f(S)=f(S_{0})+\sum_{j=1}^{m}f(S_{j})-f(S_{j-1}),$ (2)

where $S_{0}=\emptyset$ and $S_{j}=S_{j-1}+\\{i_{j}\\}$. Without loss of
generality, we could assume $f(\emptyset)=0$. Note that by the definition of
$\Delta_{f}(i|S)$, we have $f(S_{j})-f(S_{j-1})=\Delta_{f}(i_{j}|S_{j-1})$. So
the decomposition (2) can be simplified as

$\displaystyle f(S)=\sum_{j=1}^{m}\Delta_{f}(i_{j}|S_{j-1})$ (3)

To introduce our advanced data structure later, we further represent
$\Delta_{f}(i|S)$ in the form of

$\displaystyle\Delta_{f}(i|S)=u_{i}^{\top}h(S)u_{i}$ (4)

where $u_{i}\in\mathbb{R}^{d}$ is a $d$-dimensional vector and
$h(S)\in\mathbb{R}^{d\times d}$ is a $d$-by-$d$ matrix. Thus our input
instance $(n,k,f)$ of optimization problem (1) can be represented by
$(n,k,U,h)$ where $U=[u_{1},\cdots,u_{n}]$. We emphasize that we are not
assuming $f(S)$ must have some specific form here. Note that for $U$ we have
$n\cdot d$ free variables and for $h(S)$ we have $2^{n}\cdot d^{2}$ free
variables. Therefore, in total, we have $nd+2^{n}d^{2}$ free variables and
there are $n\cdot 2^{n}$ different values of $\Delta_{f}(i|S)$. Hence we have
enough degrees of freedom to represent any submodular function $f$ in the form
of (3) and (4) when $d\geq\sqrt{n}$.

In practice, an important subclass of submodular functions is monotone
submodular functions, i.e. functions $f$ satisfying $f(A)\leq f(B)$ for all
$A\subseteq B\subseteq[n]$. When $f$ is monotone, we could restrict all $h(S)$
to be a positive semidefinite (PSD) matrix. In the case of PSD $h(S)$, we can
achieve faster acceleration.

##  3 Technique Overview

Our data structure design starts with the greedy search approach [53]. The
proposed algorithm here already has a small error. Specifically, under the
representation of $f(S)$ in Eq. (4), [53] uses an algorithm which starts from
empty set $S_{0}=\emptyset$, and in each time step $t$, it constructs $S_{t}$
by adding increase $S_{t-1}$ with a singleton set that maximizes the marginal
gain of $f$. Formally, [53] chooses
$i=\arg\max_{i\in\overline{S}_{t-1}}\\{u_{i}^{\top}h(S_{t-1})u_{i}\\}$ and
makes $S_{t}=S_{t-1}+\\{i\\}$. It is proved that this algorithm can achieve at
least a constant times ($\approx 0.63$) approximation of the optimal
algorithm. Many following works solving submodular function maximization with
other types of constraints and solving online submodular function maximization
use similar greedy updating rules. Hence our acceleration method could be
applied to many algorithms developed later too.

#### Transforming quadratic form into inner product form

Our first important technique of this paper is the following two observations:
(1) for $d$-dimensional vector $u$ and $d\times d$ matrix $A$,
$u^{\top}Au=\langle uu^{\top},A\rangle$; (2) after flattening two $d\times d$
matrices $A,B$ into $d^{2}$-dimensional vectors $v_{A},v_{B}$, their inner
product remain unchanged, that is, $\langle A,B\rangle=\langle
v_{A},v_{B}\rangle$. From this perspective, the process of maximizing
$u_{j}^{\top}h(Q)u_{j}$ can be implemented by computing the inner product of
two vectors, where one vector is the flattened $u_{j}u_{j}^{\top}$, hence only
related to $u_{j}$, and the other vector is only related to $h(Q)$.

#### Inner product search data structure

Before introducing the rest part of our result, we first introduce a dynamic
inner product estimation data structure proposed by us (see Theorem 5.2 for
details). It has three operations: Init, Update, Query (See Algorithm 4 and
for more details).

  * •

Init. It accepts a set of arbitrarily large-scale vectors $x_{1},\cdots,x_{n}$
and two precision parameters $\epsilon$ and $\delta$ as input, and
initializes. It guarantees that, if the length of all of the input vectors is
bounded a constant (i.e., not ill-conditioned), and if the precision
parameters $\epsilon$, $\delta$ are constants, this procedure runs in $O(nd)$
time.

  * •

Update. It supports the update of an entry. Taken an index $i$ and a specific
vector $\beta$ as input, it replaces $x_{i}$ by $\beta$, as like we
initialized it with vectors
$x_{1},x_{2},\cdots,x_{i-1},\beta,x_{i+1},\cdots,x_{n}$. With the same
assumption of input in Init, it runs in $O(d)$ time.

  * •

Query. Taking a vector $q$ as input, it rapidly computes the inner product of
$q$ and all of the input vectors $x_{1},x_{2},\cdots,x_{n}$ such that success
probability at least $1-\delta$ and the error of each inner product is at most
$\epsilon$. With the same assumption of input, this procedure runs in $o(nd)$
time.

#### Fast quadratic form search data structure

After introducing the inner product search data structure, we explain how our
greedy search algorithm works. Specifically, we propose a fast quadratic form
search data structure to efficiently find an element $u_{i}$ from a large set
of vectors $\\{u_{1},u_{2},\cdots,u_{n}\\}$ with large target value
$u_{i}^{\top}Au_{i}$ for an arbitrary matrix $A$.

This is achieved with the help of the above inner product search data
structure. We notice that we can convert the computation of
$\arg\max_{j}\\{u_{j}^{\top}h(Q)u_{j}\\}$ to a single query
$\textsc{Query}(h(Q))$, which runs in $O(n+d^{2})$ time when the norm of input
vectors $u_{1},\cdots,u_{n}$ are bounded by a constant.

Specifically, at the beginning we initial an inner product estimation data
structure with flattened
$u_{1}u_{1}^{\top},u_{2}u_{2}^{\top},\cdots,u_{n}u_{n}^{\top}$, and precision
parameters $\epsilon$, $\delta$ which depend on practical demand, then in each
iteration, we query $h(Q)$ to obtain a list approximated inner products. To
find the satisfied $j$, we only need to find the largest one in the list. As
described above, as long as the error tolerance is constant and the input is
not ill-conditioned (that is, the norm of $u_{1},u_{2},\cdots,u_{n}$ are all
bounded by a constant), the running time of each iteration is $O(n+d^{2})$,
far faster than $O(nd^{2})$ in the naive implementation and $O(nd^{\omega-1})$
in the batch implementation.

##  4 Benchmark: Greedy Selection

In this section, we present two implementations of the greedy selection
algorithm as our benchmarks.

###  4.1 Analysis on greedy algorithms

The greedy selection algorithm starts with an empty set $S_{0}=\emptyset$. In
each iteration, the algorithm chooses the element maximizing the marginal
increment to add into the set, until the set eventually contains $k$ elements.
To be more specific, in iteration $t\in\\{1,2,\cdots,k\\}$, we let

$S_{t}\leftarrow S_{t-1}+\\{j_{t}\\}.$

where the element in the singleton is
$j_{t}=\arg\max_{j\in\overline{S}_{t-1}}f(S_{t-1}+\\{j\\})$. Although the
greedy selection algorithm is very simple, it is effective in the sense that
the approximation error of it is $1-1/e$.

######  Theorem 4.1 ([53]).

For a monotone submodular function $f$, the greedy algorithm (see Algorithm 2)
guarantees to output a set $S$ satisfying
$f(S)\geq(1-1/e)\max_{|T|=k}\\{f(T)\\}$.

Algorithm 2 Greedy algorithm benchmark

1:procedure GreedyAlgorithm(submodular function $f$)

2: $S_{0}\leftarrow\emptyset$

3: for $t=0\to k-1$ do

4: $j\leftarrow\arg\max_{i}\\{f(S_{t}\cup\\{i\\})\\}$

5: $S_{t+1}\leftarrow S_{t}\cup\\{j\\}$

6: end for

7: return $S_{k}$

8:end procedure

######  Corollary 4.2.

Given $\epsilon>0$. Consider an approximate greedy algorithm $A$ that has an
oracle $O$: taken an arbitrary set $S\subseteq[n]$ and $i\in[n]\backslash S$,
returns a value $O(S,i)$ with a guarantee that $\Delta(i|S)-\epsilon\leq
O(S,i)\leq\Delta(i|S)+\epsilon$. And in each time step $t=1,2,\cdots,k$, it
selects $j_{t}=\arg\max_{j}\\{O(S_{t-1},j)\\}$ and lets $S_{t}\leftarrow
S_{t-1}\cup\\{j_{t}\\}$, then this algorithm makes sure that it returns a set
$S_{k}$ with $f(S_{k})\geq(1-1/e)\max_{|T|=k}\\{f(T)\\}-k(2-1/e)\epsilon.$

###### Proof.

Consider the real greedy algorithm $A^{*}$ which really selects
$j_{t}=\arg\max_{j}\\{\Delta(j|S_{t-1})\\}$ and adds $j_{t}$ to $S_{t-1}$
every time. Define another set function $f^{\prime}:2^{[n]}\to\mathbb{R}$ by
$\Delta^{\prime}f(i|S)=O(S,i)$. Suppose $f^{\prime}$ is well-defined and
submodular. Then $A$ is a greedy algorithm acts on the submodular function
$f$. For the two submodular function maximization problem with submodular
function $f$ and $f^{\prime}$, suppose algorithm $A$ outputs sets $S_{A}$ with
$f(S_{A})=\mathsf{alg}$ and $f^{\prime}(S_{A})=\mathsf{alg}^{\prime}$
respectively, and suppose algorithm $A^{*}$ outputs sets $S_{A^{*}}$ with
$f(S_{A^{*}})=\mathsf{opt}$ and $f^{\prime}(S_{A^{*}})=\mathsf{opt}^{\prime}$
respectively.

By Theorem 4.1, since $A$ is the greedy algorithm of the submodular
maximization problem with $f^{\prime}$, $\mathsf{alg}^{\prime}$ is at least
$1-1/e$ times the optimal algorithm of the submodular maximization problem
with $f^{\prime}$, hence is at least $1-1/e$ times the output value of
$A^{*}$, which is, $\mathsf{alg}^{\prime}\geq(1-1/e)\mathsf{opt}^{\prime}$.

Since $O(S,i)\geq\Delta(i|S)-\epsilon$, then we have

$\displaystyle\mathsf{opt}^{\prime}=$ $\displaystyle~{}f^{\prime}(S_{A^{*}})$
$\displaystyle\geq$ $\displaystyle~{}f(S_{A^{*}})-k\epsilon$ $\displaystyle=$
$\displaystyle~{}\mathsf{opt}-k\epsilon.$

Since $O(S,i)\leq\Delta(i|S)+\epsilon$, then we have

$\displaystyle\mathsf{alg}^{\prime}=$ $\displaystyle~{}f^{\prime}(S_{A})$
$\displaystyle\leq$ $\displaystyle~{}f(S_{A})+k\epsilon$ $\displaystyle=$
$\displaystyle~{}\mathsf{alg}+k\epsilon.$

Combining the 3 equations, we have

$\displaystyle\mathsf{alg}\geq\mathsf{alg}^{\prime}-k\epsilon\geq~{}(1-1/e)\mathsf{opt}^{\prime}-k\epsilon\geq~{}(1-1/e)\mathsf{opt}-k(2-1/e)\epsilon.$

∎

###  4.2 Greedy selection with naive implementation

The greedy selection algorithm can be implemented naively by computing $j_{t}$
via enumerating elements in $\overline{S}_{t-1}$ in each iteration.

######  Theorem 4.3.

The naive implementation of the greedy selection algorithm (Algorithm 3) uses
$O(d^{2})$ space, takes $O(1)$ time to initialize, and uses $O(nd^{2})$ time
in each iteration (to add a new element to the set).

###### Proof.

Algorithm 3 correctly implements the greedy selection. In each iteration of
the for-loop beginning at line 5 in Algorithm 3, since $A_{t}$ is a $d\times
d$ matrix, computing $w_{j}$ takes $O(d^{2})$ time. As $|\overline{S}_{t}|\leq
n$, adding each element takes $O(nd^{2})$ time. ∎

Algorithm 3 Naive implementation of the greedy selection algorithm

1:procedure Naive-Alg($n,k,\\{u_{1},\cdots,u_{n}\\}\subseteq\mathbb{R}^{d}$)

2: $S_{0}\leftarrow\emptyset$

3: for $t=0\to k-1$ do

4: $A_{t}\leftarrow h(S_{t})$, $w_{\max}\leftarrow-1$, $j_{\max}\leftarrow-1$

5: for $j\in\overline{S}_{t}$ do

6: $w_{j}\leftarrow u_{j}^{\top}A_{t}u_{j}$

7: if $w_{j}>w_{\max}$ then

8: $w_{\max}\leftarrow w_{j}$, $j_{\max}\leftarrow j$

9: end if

10: end for

11: $S_{t+1}\leftarrow S_{t}\cup\\{j_{\max}\\}$

12: end for

13: return $S_{k}$

14:end procedure

###  4.3 Greedy algorithm with batch

We could implement the greedy selection algorithm in a more efficient way by
considering the candidates of the new element added in a batch-by-batch way.

######  Theorem 4.4.

There is an implementation of the greedy selection algorithm (Algorithm 8)
that uses $O(d^{2})$ space, takes $O(1)$ time during the initialization,
spends $O(n\cdot d^{\omega-1})$ time in each iteration (to add an element to
the set), where $\omega$ is the constant for fast matrix multiplication in
theorem B.1.

###### Proof.

First, we prove Algorithm 8 is correct. Since
$U=[~{}u_{i_{1}}~{}u_{i_{2}}~{}\cdots~{}u_{i_{d}}~{}]$, we have
$(U^{\top}A_{t}U)_{jj}=u_{i_{j}}^{\top}A_{t}u_{i_{j}}$. Thus for each index
$j\in\overline{S}_{t}$, $u_{j}^{\top}A_{t}u_{j}$ will be compared with the
current maximal value $w_{\max}$, hence
$j_{\max}=\arg\max_{j\in\overline{S}_{t}}\\{u_{j}^{\top}A_{t}u_{j}\\}$.

Then we prove the running time of Algorithm 8. The outer for-loop beginning at
line 7 runs for $m=\lceil|\overline{S}_{t}|/d\rceil$ iterations. In each
iteration, computing $M$ takes $O(d^{\omega})$ time, and updating $w_{\max}$
and $j_{\max}$ takes $O(d)$ time. Hence adding an element takes
$O(md^{\omega})=O(nd^{\omega-1})$ time. ∎

##  5 Dynamic Inner Product Estimation

Now we describe our data structure design for inner product estimation.

######  Definition 5.1 (Online Approximate Adaptive Inner Product Estimation).

Given a set $\\{x_{1},x_{2},\cdots,x_{n}\\}$ of $d$-dimensional vectors, the
goal of online approximate adaptive inner product estimation is to design a
data structure with at least the following two procedures Update and Query:

  * •

Update$(i\in[n],z\in\mathbb{R}^{d})$. It supports to replace $x_{i}$ by $z$.

  * •

Query$(q\in\mathbb{R}^{d})$. Given a query vector $q$, it returns a set
$\\{\widetilde{w}_{i}\\}_{i=1}^{n}$ with guarantee that for any $i\in[n]$,
$\widetilde{w}_{i}$ is close to $\langle q,x_{i}\rangle$ with a high joint
probability. How precise this needs to be can be determined by practical
demands.

######  Theorem 5.2.

There is a data structure uses
$\widetilde{O}(\epsilon^{-2}D^{2}nd\log(1/\delta))$ space for the Online
Approximate Adaptive Inner Product Estimation Problem with the following
procedures:

  * •

Init$(\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$:
Given a list of data points
$\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$ ($\|x_{i}\|\leq D$, for
all $i\in[n]$), an accuracy parameter $\epsilon$ and a failure probability
$\delta$ as input, the data structure preprocesses in time

$\displaystyle\widetilde{O}(\epsilon^{-2}D^{2}nd\log(1/\delta)).$

  * •

Update$(i\in[n],z\in\mathbb{R}^{d})$: Given index $i$ and coordinate $z$, the
data structure replace $x_{i}$ by $z$ in time
$\widetilde{O}(\epsilon^{-2}D^{2}d\log(1/\delta))$.

  * •

Query$(q\in\mathbb{R}^{d})$: Given a query point $q\in\mathbb{R}^{d}$ (where
$\|q\|\leq 1$), the Query operation takes $q$ as input and approximately
estimates the inner product of $q$ and all the data points
$\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$ in time
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d)\log(1/\delta))$ i.e. it provides a list
of estimates $\\{\widetilde{w}_{i}\\}_{i=1}^{n}$ such that:

$\displaystyle\forall i\in[n],\langle
q,x_{i}\rangle-\epsilon\leq\widetilde{w}_{i}\leq\langle
q,x_{i}\rangle+\epsilon$

with probability at least $1-\delta$, even for a sequence of adaptively chosen
queries.

We refer the detailed proof to Section C. Lemma 5.3 gives the running time of
procedure Init. Lemma 5.4 analyzes the running time of Update. Lemma 5.5
analyzes the running time of Query.

######  Lemma 5.3 (Running time of initialization).

The procedure Init in Algorithm 4 runs in time
$\widetilde{O}(\epsilon^{-2}D^{2}nd\log(1/\delta))$.

######  Lemma 5.4 (Running time of Update).

The procedure Update in Algorithm 4 runs in time
$\widetilde{O}(\epsilon^{-2}D^{2}d\log(1/\delta))$.

######  Lemma 5.5 (Correctness and running time of Query).

The procedure Query in Algorithm 4 outputs $\\{\widetilde{w}_{i}\\}_{i=1}^{n}$
correctly and runs in time

$\displaystyle\widetilde{O}(\epsilon^{-2}D^{2}(n+d)\log(1/\delta)).$

###### Proof.

For the correctness proof part of procedure Query, we denote
$\|Q(x_{i})-P(y)\|_{2}$ by $d_{i}$, by leveraging asymmetric transformation we
have $\langle x_{i},y\rangle=D-\frac{1}{2}Dd_{i}^{2},$ and according to
Theorem B.5, Ade.Query($P(y)$) can give a series of
$\\{\widetilde{d_{i}}\\}_{i=1}^{n}$ with

$\displaystyle(1-\epsilon^{\prime})d_{i}\leq\widetilde{d_{i}}\leq(1+\epsilon^{\prime})d_{i},$

thus

$\displaystyle\widetilde{w_{i}}=$
$\displaystyle~{}D-\frac{D}{2}\widetilde{d_{i}}^{2}$ $\displaystyle\leq$
$\displaystyle~{}~{}D-\frac{D}{2}(1-\epsilon^{\prime})^{2}d_{i}^{2}$
$\displaystyle\leq$ $\displaystyle~{}\langle
x_{i},y\rangle+\frac{D}{2}(2\epsilon^{\prime}-\epsilon^{\prime 2})d_{i}^{2}$
$\displaystyle\leq$ $\displaystyle~{}~{}\langle x_{i},y\rangle+\epsilon,$

and

$\displaystyle\widetilde{w_{i}}=$
$\displaystyle~{}D-\frac{D}{2}\widetilde{d_{i}}^{2}$ $\displaystyle\geq$
$\displaystyle~{}D-\frac{D}{2}(1+\epsilon^{\prime})^{2}d_{i}^{2}$
$\displaystyle\geq$ $\displaystyle~{}\langle
x_{i},y\rangle-\frac{D}{2}(2\epsilon^{\prime}+\epsilon^{\prime 2})d_{i}^{2}$
$\displaystyle\geq$ $\displaystyle~{}\langle x_{i},y\rangle-\epsilon,$

where we use $\frac{D}{2}(2\epsilon^{\prime}-\epsilon^{\prime 2})\leq
D\epsilon^{\prime}\leq\epsilon$ and
$\frac{D}{2}(2\epsilon^{\prime}+\epsilon^{\prime
2})\leq\frac{3}{2}D\epsilon^{\prime}\leq\epsilon$. And for the running time
proof part, it holds because the member Ade has a Query time

$\displaystyle\widetilde{O}(\epsilon^{\prime-2}(n+d)\log(1/\delta))=\widetilde{O}(\epsilon^{-2}D^{2}(n+d)\log(1/\delta))$

by Theorem B.5. ∎

Algorithm 4 Dynamic inner product estimation

1:data structure DynamicInnerProductEstimation $\triangleright$ Theorem 5.2

2:members

3: ADE Ade

4:end members

5:procedure Init($x_{1},x_{2},\cdots,x_{n},\epsilon,\delta$) $\triangleright$
Lemma 5.3

6: $\epsilon^{\prime}=\frac{2\epsilon}{3D}$

7: Ade.Init$(Q(x_{1}),Q(x_{2}),\cdots,Q(x_{n}),\epsilon^{\prime},\delta)$

8:end procedure

9:procedure Update($i,z$) $\triangleright$ Lemma 5.4

10: Ade.Update$(i,Q(z))$

11:end procedure

12:procedure Query($q$) $\triangleright$ Lemma 5.5

13: $\widetilde{d}_{1},\widetilde{d}_{2},\cdots,\widetilde{d}_{n}$ =
Ade.Query$(P(q))$

14: for $i=1,2,\cdots,n$ do

15: $\widetilde{w}_{i}=1-\frac{1}{2}\widetilde{d}_{i}^{2}$

16: end for

17: return $\\{\widetilde{w}_{i}\\}_{i=1}^{n}$

18:end procedure

19:data structure

##  6 Fast Quadratic Form Search Data structure

In this section, we propose an improved quadratic form search data structure.
We first show our main conclusion theorem, and then a list of auxiliary
lemmas.

######  Theorem 6.1 (Data structure part of Theorem 1.1).

There exists a data structure uses
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{2}\log(1/\delta))$ space with the
following procedures:

  * •

Init$(\\{u_{1},u_{2},\cdots,u_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$.
Given vectors $u_{1},u_{2},\cdots,u_{n}$ satisfying $\|u_{i}\|_{2}\leq D$ for
any $i\in[n]$, accuracy parameter $\epsilon$ and failure probability $\delta$,
the data structure initializes with time
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{2}\log(1/\delta))$.

  * •

Query$(M\in\mathbb{R}^{d\times d})$. Given a $d\times d$ matrix $M$, the data
structure outputs a $j_{0}\in\overline{S}_{t}$ such that
$u_{j_{0}}^{\top}Mu_{j_{0}}\geq\max_{j}\\{u_{j}^{\top}Mu_{j}\\}-2\epsilon$
with probability at least $1-\delta$ in time
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d^{2})\log(1/\delta))$.

  * •

Delete$(i\in[n])$. Given an index $i$, the data structure deletes $u_{i}$ from
the candidate index set in time $O(\log n)$.

We propose Algorithm 5 as a construction proof of Theorem 6.1. Lemma 6.2
states the correctness of Query. Lemma 6.3, Lemma 6.4, and Lemma 6.5 show the
running time for Init, Query, and Delete, accordingly. We defer the detailed
proof to Section C.

######  Lemma 6.2 (Correctness).

Procedure Update in Algorithm 5 outputs a $j_{0}\in S$ such that
$u_{j_{0}}^{\top}Mu_{j_{0}}\geq\max_{j\in\overline{S}_{t}}\\{u_{j}^{\top}A_{t}u_{j}\\}-2\epsilon$
with probability at least $1-\delta$.

###### Proof.

By Theorem 5.2, line 16 in Algorithm 5, returns a list
$\\{\widetilde{w}_{1},\widetilde{w}_{2},\cdots,\widetilde{w}_{n}\\}$ such that
$\langle m,v_{i}\rangle-\epsilon\leq\widetilde{w}_{i}\leq\langle
m,v_{i}\rangle+\epsilon$ with probability at least $1-\delta$. Note that

$\displaystyle~{}\langle m,v_{i}\rangle=\sum_{j=1}^{d}\langle
m_{j},(u_{i})_{j}\cdot u_{i}\rangle=~{}\langle
M,u_{i}u_{i}^{\top}\rangle=\operatorname{tr}[Mu_{i}u_{i}^{\top}]=u_{i}^{\top}Mu_{i},$

where the first step follows from the definitions of $m$ and $v_{i}$, the
second step follows from $(u_{i})_{j}\cdot u_{i}$ equals the $j$-th column of
$u_{i}u_{i}\top$, the third step follows from $\langle
A,B\rangle=\operatorname{tr}[AB^{\top}]$, and the last step follows from
$\operatorname{tr}[AB]=\operatorname{tr}[BA]$. Thus

$\displaystyle u_{i}^{\top}Mu_{i}-\epsilon\leq\widetilde{w}_{i}\leq
u_{i}^{\top}Mu_{i}+\epsilon$ (5)

with probability at least $1-\delta$. Hence procedure Update outputs a $j_{0}$
such that

$\displaystyle u_{j_{0}}^{\top}Mu_{j_{0}}\leq$
$\displaystyle~{}\widetilde{w}_{j_{0}}+\epsilon$ $\displaystyle=$
$\displaystyle~{}\max_{j\in S}\\{\widetilde{w}_{j}\\}+\epsilon$
$\displaystyle\leq$ $\displaystyle~{}u_{j}^{\top}Mu_{j}+2\epsilon$

with probability $1-\delta$, where the first step follows from Equation (5),
the second step follows from line 17 in Algorithm 5, and the last step follows
from Equation (5). ∎

######  Lemma 6.3 (Init time).

Procedure Init in Algorithm 5 takes
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{2}\log(1/\delta))$ time.

######  Lemma 6.4 (Query time).

Procedure Query in Algorithm 5 takes

$\displaystyle\widetilde{O}(\epsilon^{-2}D^{2}(n+d^{2})\log(1/\delta))$

time.

######  Lemma 6.5 (Delete time).

Procedure Delete in Algorithm 5 takes $O(\log n)$ time to delete an index from
candidate index set.

Algorithm 5 Data Structure ds

1:data structure ds

2:members

3: $S$ (Candidate index set)

4: DynamicInnerProductEstimation Ipe $\triangleright$ Algorithm 4

5:end members

6:procedure
Init($\\{u_{1},u_{2},\cdots,u_{n}\\}\subset\mathbb{R}^{d},\epsilon>0,\delta>0$)

7: $S=[n]$

8: for $i=1$ to $n$ do

9: $v_{i}\leftarrow[~{}(u_{i})_{1}\cdot u_{i}^{\top}~{}~{}(u_{i})_{2}\cdot
u_{i}^{\top}~{}~{}\cdots~{}~{}(u_{i})_{d}\cdot u_{i}^{\top}~{}]^{\top}$

10: end for

11: Ipe.Init$(\\{v_{1},v_{2},\cdots v_{n}\\},\epsilon,\delta)$

12:end procedure

13:procedure Query($M\in\mathbb{R}^{d\times d}$)

14: Write $M$ as $[~{}m_{1}~{}m_{2}~{}\cdots~{}m_{d}~{}]$

15:
$m\leftarrow[~{}m_{1}^{\top}~{}m_{2}^{\top}~{}\cdots~{}m_{d}^{\top}~{}]^{\top}$

16:
$\\{\widetilde{w}_{1},\widetilde{w}_{2},\cdots,\widetilde{w}_{n}\\}\leftarrow\text{Ipe}$.Query$(m)$

17: return $\arg\max_{j\in S}\\{\widetilde{w}_{j}\\}$

18:end procedure

19:procedure Delete($i\in[n]$)

20: $S\leftarrow S\backslash\\{i\\}$

21:end procedure

22:end data structure

##  7 Conclusion

In this paper, we study the submodular function maximization problem. As
proved in many previous works, greedy selection algorithm and its variants
achieve satisfying approximation error in many settings, e.g., cardinality
constraints, matroid constraints, knapsack constraints, offline and online
setting. Therefore, we are motivated to find method accelerating the greedy
selection algorithm. We first develop an embedding representation of the input
instance of submodular maximization problems. Based on the embedding
representation, we design our tree-based dynamic data structure so that each
greedy selection step can be viewed as a query to our data structure. By
designing the data structure carefully, after each selection, our data
structure can be correspondingly updated efficiently. With operations
implemented efficiently, our method achieves acceleration for greedy algorithm
and its variants for submodular maximization problems. As far as we know, we
are not aware of any negative social impact of algorithm presented in this
work. However, we point out that proper usage of maximizing submodular
function for some particular purposes, which goes beyond the scope of this
paper, needs extra attention.

## References

  * ADX [10] Alekh Agarwal, Ofer Dekel, and Lin Xiao.  Optimal algorithms for online convex optimization with multi-point bandit feedback.  In Colt, pages 28–40. Citeseer, 2010.
  * AFH+ [11] Alekh Agarwal, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Alexander Rakhlin.  Stochastic convex optimization with bandit feedback.  Advances in Neural Information Processing Systems, 24, 2011.
  * ALS+ [22] Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, and Danyang Zhuo.  Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing.  arXiv preprint arXiv:2211.14227, 2022.
  * AR [15] Alexandr Andoni and Ilya Razenshteyn.  Optimal data-dependent hashing for approximate near neighbors.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 793–801, 2015.
  * AW [21] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539. SIAM, 2021.
  * Bac [19] Francis Bach.  Submodular functions: from discrete to continuous domains.  Mathematical Programming, 175(1):419–459, 2019.
  * BBK [19] Yatao Bian, Joachim Buhmann, and Andreas Krause.  Optimal continuous dr-submodular maximization and applications to provable mean field inference.  In International Conference on Machine Learning, pages 644–653. PMLR, 2019.
  * BE [16] Sébastien Bubeck and Ronen Eldan.  Multi-scale exploration of convex functions and bandit convex optimization.  In Conference on Learning Theory, pages 583–589. PMLR, 2016.
  * BLE [17] Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan.  Kernel-based methods for bandit convex optimization.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 72–85, 2017.
  * BPSW [21] Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein.  Training (overparametrized) neural networks in near-linear time.  In ITCS, 2021.
  * Bra [20] Jan van den Brand.  A deterministic linear program solver in current matrix multiplication time.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 259–278. SIAM, 2020.
  * CCK [16] Lin Chen, Forrest W Crawford, and Amin Karbasi.  Submodular variational inference for network reconstruction.  arXiv preprint arXiv:1603.08616, 2016.
  * CCLY [19] Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang.  A near-optimal algorithm for approximating the john ellipsoid.  In Conference on Learning Theory, pages 849–873. PMLR, 2019.
  * CCPV [07] Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák.  Maximizing a submodular set function subject to a matroid constraint.  In International Conference on Integer Programming and Combinatorial Optimization, pages 182–196. Springer, 2007.
  * CCPV [11] 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.
  * CHHK [18] Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi.  Projection-free online optimization with stochastic gradient: From convexity to submodularity.  In International Conference on Machine Learning, pages 814–823. PMLR, 2018.
  * CHK [18] Lin Chen, Hamed Hassani, and Amin Karbasi.  Online continuous submodular maximization.  In International Conference on Artificial Intelligence and Statistics, pages 1896–1905. PMLR, 2018.
  * CLS [19] Michael B Cohen, Yin Tat Lee, and Zhao Song.  Solving linear programs in the current matrix multiplication time.  In STOC, 2019.
  * CN [22] Yeshwanth Cherapanamjeri and Jelani Nelson.  Uniform approximations for randomized hadamard transforms with applications.  arXiv preprint arXiv:2203.01599, 2022.
  * DEK [15] Ofer Dekel, Ronen Eldan, and Tomer Koren.  Bandit smooth convex optimization: Improving the bias-variance tradeoff.  Advances in Neural Information Processing Systems, 28, 2015.
  * DK [14] Josip Djolonga and Andreas Krause.  From map to marginals: Variational inference in bayesian submodular models.  Advances in Neural Information Processing Systems, 27, 2014.
  * DKH [07] Varsha Dani, Sham M Kakade, and Thomas Hayes.  The price of bandit information for online optimization.  Advances in Neural Information Processing Systems, 20, 2007.
  * [23] Yichuan Deng, Zhihang Li, and Zhao Song.  Attention scheme inspired softmax regression.  arXiv preprint arXiv:2304.10411, 2023.
  * [24] Yichuan Deng, Zhihang Li, and Zhao Song.  An improved sample complexity for rank-1 matrix sensing.  arXiv preprint arXiv:2303.06895, 2023.
  * DLY [21] Sally Dong, Yin Tat Lee, and Guanghao Ye.  A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1784–1797, 2021.
  * DMS [23] Yichuan Deng, Sridhar Mahadevan, and Zhao Song.  Randomized and deterministic attention sparsification algorithms for over-parameterized feature dimension.  arxiv preprint: arxiv 2304.03426, 2023.
  * DSW [22] Yichuan Deng, Zhao Song, and Omri Weinstein.  Discrepancy minimization in input-sparsity time.  arXiv preprint arXiv:2210.12468, 2022.
  * Fei [98] Uriel Feige.  A threshold of ln n for approximating set cover.  Journal of the ACM (JACM), 45(4):634–652, 1998.
  * FKM [04] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan.  Online convex optimization in the bandit setting: gradient descent without a gradient.  arXiv preprint cs/0408007, 2004.
  * GK [11] 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.
  * GKW+ [13] Victor Gabillon, Branislav Kveton, Zheng Wen, Brian Eriksson, and Shanmugavelayutham Muthukrishnan.  Adaptive submodular maximization in bandit setting.  Advances in Neural Information Processing Systems, 26, 2013.
  * GQSW [22] Yeqi Gao, Lianke Qin, Zhao Song, and Yitan Wang.  A sublinear adversarial training algorithm.  arXiv preprint arXiv:2208.05395, 2022.
  * GS [22] Yuzhou Gu and Zhao Song.  A faster small treewidth sdp solver.  arXiv preprint arXiv:2211.06033, 2022.
  * GSY [23] Yeqi Gao, Zhao Song, and Junze Yin.  An iterative algorithm for rescaled hyperbolic functions regression.  arXiv preprint arXiv:2305.00660, 2023.
  * GSYZ [23] Yuzhou Gu, Zhao Song, Junze Yin, and Lichen Zhang.  Low rank matrix completion via robust alternating minimization in nearly linear time.  arXiv preprint arXiv:2302.11068, 2023.
  * HAK [07] Elad Hazan, Amit Agarwal, and Satyen Kale.  Logarithmic regret algorithms for online convex optimization.  Machine Learning, 69(2):169–192, 2007.
  * HL [14] Elad Hazan and Kfir Levy.  Bandit convex optimization: Towards tight bounds.  Advances in Neural Information Processing Systems, 27, 2014.
  * HSWZ [22] Hang Hu, Zhao Song, Omri Weinstein, and Danyang Zhuo.  Training overparametrized neural networks in sublinear time.  arXiv preprint arXiv:2208.04508, 2022.
  * IM [98] Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: towards removing the curse of dimensionality.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604–613, 1998.
  * JLSW [20] Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong.  An improved cutting plane method for convex optimization, convex-concave games and its applications.  In STOC, 2020.
  * JLSZ [23] Haotian Jiang, Yin Tat Lee, Zhao Song, and Lichen Zhang.  Convex minimization with integer minima in $\widetilde{O}(n^{4})$ time.  arXiv preprint arXiv:2304.03426, 2023.
  * JSWZ [21] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang.  Faster dynamic matrix inverse for faster lps.  In STOC, 2021.
  * KG [12] Andreas Krause and Carlos E Guestrin.  Near-optimal nonmyopic value of information in graphical models.  arXiv preprint arXiv:1207.1394, 2012.
  * Kle [04] Robert Kleinberg.  Nearly tight bounds for the continuum-armed bandit problem.  Advances in Neural Information Processing Systems, 17, 2004.
  * KRGG [09] Andreas Krause, Ram Rajagopal, Anupam Gupta, and Carlos Guestrin.  Simultaneous placement and scheduling of sensors.  In 2009 International Conference on Information Processing in Sensor Networks, pages 181–192. IEEE, 2009.
  * LB [11] 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\.
  * LKG+ [07] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance.  Cost-effective outbreak detection in networks.  In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 420–429, 2007.
  * LSZ [19] Yin Tat Lee, Zhao Song, and Qiuyi Zhang.  Solving empirical risk minimization in the current matrix multiplication time.  In Conference on Learning Theory (COLT), pages 2140–2157. PMLR, 2019.
  * LSZ [23] Zhihang Li, Zhao Song, and Tianyi Zhou.  Solving regularized exp, cosh and sinh regression problems.  arXiv preprint, 2303.15725, 2023.
  * MBMW [05] Kamesh Munagala, Shivnath Babu, Rajeev Motwani, and Jennifer Widom.  The pipelined set cover problem.  In International Conference on Database Theory, pages 83–98. Springer, 2005.
  * MH [18] Negar Mehr and Roberto Horowitz.  A submodular approach for optimal sensor placement in traffic networks.  In 2018 Annual American Control Conference (ACC), pages 6353–6358. IEEE, 2018.
  * NJB [05] Mukund Narasimhan, Nebojsa Jojic, and Jeff A Bilmes.  Q-clustering.  Advances in Neural Information Processing Systems, 18, 2005.
  * NWF [78] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.  An analysis of approximations for maximizing submodular set functions—i.  Mathematical programming, 14(1):265–294, 1978.
  * QJS+ [22] Lianke Qin, Rajesh Jayaram, Elaine Shi, Zhao Song, Danyang Zhuo, and Shumo Chu.  Adore: Differentially oblivious relational database operators.  In VLDB, 2022.
  * QRS+ [22] Lianke Qin, Aravind Reddy, Zhao Song, Zhaozhuo Xu, and Danyang Zhuo.  Adaptive and dynamic multi-resolution hashing for pairwise summations.  In BigData, 2022.
  * QSZ [23] Lianke Qin, Zhao Song, and Ruizhe Zhang.  A general algorithm for solving rank-one matrix sensing.  arXiv preprint arXiv:2303.12298, 2023.
  * QSZZ [23] Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo.  An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization.  In AISTATS, 2023.
  * SDP+ [19] Jianbing Shen, Xingping Dong, Jianteng Peng, Xiaogang Jin, Ling Shao, and Fatih Porikli.  Submodular function optimization for motion clustering and image segmentation.  IEEE transactions on neural networks and learning systems, 30(9):2637–2649, 2019.
  * SG [08] Matthew Streeter and Daniel Golovin.  An online algorithm for maximizing submodular functions.  Advances in Neural Information Processing Systems, 21, 2008.
  * SGS [08] Matthew Streeter, Daniel Golovin, and Stephen F Smith.  Combining multiple constraint solvers: Results on the cpai’06 competition data.  of: Proceedings of the Second International CSP Solver Competition, pages 11–18, 2008.
  * Son [19] Zhao Song.  Matrix theory: optimization, concentration, and algorithms.  The University of Texas at Austin, 2019.
  * SSX [21] Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu.  Sublinear least-squares value iteration via locality sensitive hashing.  arXiv preprint arXiv:2105.08285, 2021.
  * ST [11] Ankan Saha and Ambuj Tewari.  Improved regret guarantees for online smooth convex optimization with bandit feedback.  In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 636–642. JMLR Workshop and Conference Proceedings, 2011.
  * Svi [04] Maxim Sviridenko.  A note on maximizing a submodular set function subject to a knapsack constraint.  Operations Research Letters, 32(1):41–43, 2004.
  * SWYZ [23] Zhao Song, Yitan Wang, Zheng Yu, and Lichen Zhang.  Sketching for first order method: Efficient algorithm for low-bandwidth channel and vulnerability.  In ICML, 2023.
  * SXZ [22] Zhao Song, Zhaozhuo Xu, and Lichen Zhang.  Speeding up sparsification using inner product search data structures.  arXiv preprint arXiv:2204.03209, 2022.
  * SY [21] Zhao Song and Zheng Yu.  Oblivious sketching-based central path method for linear programming.  In International Conference on Machine Learning, pages 9835–9847. PMLR, 2021.
  * SYYZ [22] Zhao Song, Xin Yang, Yuanyuan Yang, and Tianyi Zhou.  Faster algorithm for structured john ellipsoid computation.  arXiv preprint arXiv:2211.14407, 2022.
  * SZZ [21] Zhao Song, Lichen Zhang, and Ruizhe Zhang.  Training multi-layer over-parametrized neural network in subquadratic time.  arXiv preprint arXiv:2112.07628, 2021.
  * WIB [15] 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.
  * Wol [82] Laurence A Wolsey.  An analysis of the greedy algorithm for the submodular set covering problem.  Combinatorica, 2(4):385–393, 1982.
  * YFT [16] Baosheng Yu, Meng Fang, and Dacheng Tao.  Linear submodular bandits with a knapsack constraint.  In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
  * YG [11] Yisong Yue and Carlos Guestrin.  Linear submodular bandits and their application to diversified retrieval.  Advances in Neural Information Processing Systems, 24, 2011.
  * Zha [22] Lichen Zhang.  Speeding up optimizations via data structures: Faster search, sample and maintenance.  Master’s thesis, Carnegie Mellon University, 2022.
  * Zin [03] Martin Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003.

## Appendix

#### Roadmap.

The appendix of our paper is organized as follows. Section A gives the
preliminary tools. Section B shows some tools from previous works. Section C
complements the omitted proofs of our data structures. Section D shows the
implementation with locality sensitive hashing. Section E shows how our work
can be extended to typical constraints and online setting. Section F utilizes
our data structures to obtain a formal submodular maximization algorithm.
Section G extends our work and expands its application scope.

##  Appendix A Preliminary

#### Notation

For any positive $n$, we use $[n]$ to denote the set $\\{1,2,\cdots,n\\}$. For
a square matrix $A$, we use $\operatorname{tr}[A]$ to denote the trace of $A$.
For a set $S\subseteq[n]$ , we use $\overline{S}$ to denote the complementary
set of $S$, which is equivalent to $[n]\backslash S$. If there is no
ambiguity, we will omit $[n]$. We use $n$ to denote the number of elements in
the ground set $[n]$. We use $d$ to denote the dimension of each vector. For
$t\geq 1$, we use $S_{t}$ to denote the set of selected elements at time
$1,2,\cdots,t$.

For two $d$-dimensional vectors $u,v$, we use $\langle u,v\rangle$ to denote
their inner product. For two $n\times m$ matrices $A,B$, we use $\langle
A,B\rangle$ to denote their inner product, that is, their elementary-wise
product. For any function $f$, we will use $\widetilde{O}(f)$ to denote
$O(f\cdot\operatorname{poly}(\log f))$.

For notational simplicity, we use $\overline{S}_{t}$ to denote $[n]\backslash
S_{t}$. In submodular maximization, in each iteration, we are greedily
updating the an object $S_{t+1}\subset[n]$ in the following sense

$\displaystyle S_{t+1}\leftarrow
S_{t}\cup\\{\arg\max_{j\in\overline{S}_{t}}f(S_{t}\cup\\{j\\})\\}$

where $f$ is a submodular function.

Let us decompose $f$ as sum of increments, e.g.

$\displaystyle f(S)=f(S-\\{j\\})+\Delta_{f}(j|S-\\{j\\})$

Let $Q=S-\\{j\\}$. Let us represent $\Delta_{f}(j|S-\\{j\\})$ as

$\displaystyle\Delta_{f}(j|S-\\{j\\})=u_{j}^{\top}\cdot h(Q)\cdot u_{j}$

where $h:2^{[n]}\rightarrow\mathbb{R}^{d\times d}$ and the output of function
$h$ should be a PSD matrix when $f$ is monotone.

##  Appendix B Tools from previous work

In this work we use sketching technique to speedup an optimization problem
which is called submodular optimization. Here we briefly a number of previous
sketching work in different areas. Sketching has been applied to speedup many
continuous optmization problems such as linear programming [18, 61, 11, 42,
25, 67, 33], empirical risk minimization [48, 57], cutting plane method [40],
computing John Ellipsoid [13, 68]. Other than continuous optimization, several
discrete optimization problems also can be applied [27, 66, 74, 41]. Sketching
ideas also have applied to several theoretical large language models problems
such as exponential and softmax regression [49, 34, 23], sketching the feature
dimension of attention matrix [26]. In many tasks machine learning tasks,
sketching technique is also very useful, matrix completion [35], adversarial
training [32], training over-parameterized neural tangent kernel regression
[10, 69, 74, 3, 38], matrix sensing [24, 56], kernel density estimation [55],
federated learning [65]. In addition, sketching technique also can be applied
to theory of relational database [54].

###  B.1 Fast multiplication

In our algorithm, we need to operate dense matrix multiplication. Currently,
the fastest matrix multiplication achieves $O(n^{2.373})$ time complexity
([5]).

######  Theorem B.1 (Matrix Multiplication([5])).

Let ${\cal T}_{\mathrm{mat}}(n)$ denote the number of operations used to
compute matrix product $AB$ where $A,B\in\mathbb{R}^{n\times n}$. There exists
an algorithm computing $AB$ with ${\cal T}_{\mathrm{mat}}(n)=O(n^{\omega})$
for some $\omega<2.373$.

###  B.2 Locality sensitive hashing

We present more previous lemmas on locality sensitive hashing.

The approxiate maximum inner product search problem is to find a point $p$
that achieves the maximum inner product with respect to the given point up to
a certain approximation error ratio.

######  Definition B.2 (Approximate Max-IP, [62]).

Let $c\in(0,1)$ and $\tau\in(0,1)$. Given an $n$-point dataset
$P\subset\mathbb{S}^{d-1}$ on the sphere, the goal of the $(c,\tau)$-Maximum
Inner Product Search (Max-IP) is to build a data structure that, given a query
$q\in\mathbb{S}^{d-1}$ with the promise that there exists a datapoint $p\in P$
with $\langle p,q\rangle\geq\tau$, it reports a datapoint $p^{\prime}\in P$
with similarity $\langle p^{\prime},q\rangle\geq c\cdot\tau$.

The naive method for the approximate MAX-IP problem by enumeration could solve
this problem in $O(nd)$ time and $O(nd)$ space. With more elaborate design,
the recent work ([62]) gives better solution. There are two choices provided
in [62].

######  Theorem B.3 (Theorem 8.2, page 19, [62]).

Let $c\in(0,1)$ and $\tau\in(0,1)$. Given a set of $n$-points
$Y\subset\mathbb{S}^{d-1}$ on the sphere, one can construct a data structure
with ${\cal T}_{\mathrm{init}}$ preprocessing time and ${\cal
S}_{\mathrm{space}}$ space so that for any query $x\in{\cal S}^{d-1}$, we take
query time complexity $O(d\cdot n^{\rho}\log(1/\delta))$:

  * •

if $\mathsf{Max-IP}(x,Y)\geq\tau$, then we output a vector in $Y$ which is a
$(c,\tau)-\mathsf{Max-IP}$ with respect to $(x,Y)$ with probability at least
$1-\delta$, where $\rho:=f(c,\tau)+o(1)$.

  * •

otherwise, we output $\mathsf{fail}$.

Further,

  * •

If ${\cal T}_{\mathsf{init}}=O(dn^{1+\rho})\log(1/\delta)$ and ${\cal
S}_{\mathsf{space}}=O(n^{1+\rho}+dn)\log(1/\delta)$, then
$f(c,\tau)=\frac{1-\tau}{1-2c\tau+\tau}$.

  * •

If ${\cal T}_{\mathsf{init}}=O(dn^{1+o(1)})\log(1/\delta)$ and ${\cal
S}_{\mathsf{space}}=O(n^{1+o(1)}+dn)\log(1/\delta)$, then
$f(c,\tau)=\frac{2(1-\tau)^{2}}{(1-c\tau)^{2}}-\frac{(1-\tau)^{4}}{(1-c\tau)^{4}}$.

The two results in above Theorem have trade-off. One algorithm depends on
$n^{\rho}$ and the dependence between $\rho$ and $c$ is better. The other the
algorithm depends on $n^{o(1)}$ which is faster than $n^{\rho}$, but the
dependence between $\rho$ and $c$ is worse.

###  B.3 Dynamic distance estimation

######  Definition B.4 (Online Approximate Adaptive Distance Estimation).

Given $n$ vectors $x_{1},\cdots,x_{n}$ from $d$-dimensional space, the goal is
to desgin a data structure that supports query $z$, and it outputs a vector
$u\in\mathbb{R}^{n}$ such that $u_{i}\approx\|x_{i}-z\|$ for all $i\in[n]$.

Brute force: $O(nd)$ time, $O(nd)$ space.

######  Theorem B.5 (Theorem 1.4 in [19]).

There is a data structure for the Online Approximate Adaptive Distance
Estimation Problem uses $\widetilde{O}(\epsilon^{-2}nd\log(1/\delta))$ space
with the following procedures:

  * •

Init$(\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$:
Given data points $\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$, an
accuracy parameter $\epsilon$ and a failure probability $\delta$ as input, the
data structure preprocesses in time
$\widetilde{O}(\epsilon^{-2}nd\log(1/\delta))$.

  * •

Query$(q\in\mathbb{R}^{d})$: Given a query point $q\in\mathbb{R}^{d}$, the
Query operation takes $q$ as input and approximately estimates the Euclidean
distances from $q$ to all the data points
$\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$ in time
$\widetilde{O}(\epsilon^{-2}(n+d)\log(1/\delta))$ i.e. it provides a set of
estimates $\\{\widetilde{d}_{i}\\}_{i=1}^{n}$ such that:

$\displaystyle\forall
i\in[n],(1-\epsilon)\|q-x_{i}\|_{2}\leq\widetilde{d}_{i}\leq(1+\epsilon)\|q-x_{i}\|_{2}$

with probability at least $1-\delta$, even for a sequence of adaptively chosen
queries.

Algorithm 6 Our conceptual algorithm – Offline

1:procedure
FastSubmodularMaximization($n,k,h,\\{u_{1},\cdots,u_{n}\\}\subset\mathbb{R}^{d}$)

2: ds.Init($u_{1},\cdots u_{n}$)

3: $S_{0}\leftarrow\emptyset$

4: for $t=0\to k-1$ do

5: $A_{t}\leftarrow h(S_{t})$

6: $j\leftarrow\text{ds}.\textsc{Query}(A_{t})$

7: $S_{t+1}\leftarrow S_{t}\cup\\{j\\}$

8: $\text{ds}.\textsc{Del}(j)$

9: end for

10: return $S_{k}$

11:end procedure

Algorithm 7 Our conceptual algorithm – semi-online

1:procedure
FastSubmodularMaximization($n,k,\\{u_{1},\cdots,u_{n}\\}\subset\mathbb{R}^{d}$)

2: ds.Init($u_{1},\cdots u_{n}$)

3: $S_{0}\leftarrow\emptyset$

4: for $t=0\to k-1$ do

5: $A_{t}\leftarrow h(S_{t})$

6: Adversary gives a pair $(i,z)$ where $i\in[n]\backslash S_{t}$ and
$z\in\mathbb{R}^{d}$

7: $\text{ds}.\textsc{Update}(i,z)$

8: $j\leftarrow\text{ds}.\textsc{Query}(A_{t})$

9: $S_{t+1}\leftarrow S_{t}\cup\\{j\\}$

10: $\text{ds}.\textsc{Del}(j)$

11: end for

12: return $S_{k}$

13:end procedure

###  B.4 Proof of Corollary 4.2: Robustness of greedy algorithm

######  Corollary B.6.

Given $\epsilon>0$. Consider an approximate greedy algorithm $A$ that has an
oracle $O$: taken an arbitrary set $S\subseteq[n]$ and $i\in[n]\backslash S$,
returns a value $O(S,i)$ with guarantee that $\Delta(i|S)-\epsilon\leq
O(S,i)\leq\Delta(i|S)+\epsilon$. And in each time step $t=1,2,\cdots,k$, it
selects $j_{t}=\arg\max_{j}\\{O(S_{t-1},j)\\}$ and lets $S_{t}\leftarrow
S_{t-1}\cup\\{j_{t}\\}$, then this algorithm makes sure that it returns a set
$S_{k}$ with

$\displaystyle f(S_{k})\geq(1-1/e)\max_{|T|=k}\\{f(T)\\}-k(2-1/e)\epsilon.$

###### Proof.

Define $f^{\prime}:2^{[n]}\to\mathbb{R}$ as
$f^{\prime}(S):=f(S-\\{i\\})+O(S-\\{i\\},i)$. Consider the real greedy
algorithm $A^{*}$ which really selects
$j_{t}=\arg\max_{j}\\{\Delta(j|S_{t-1})\\}$ and adds $j_{t}$ to $S_{t-1}$
every time. Define another set function $f^{\prime}:2^{[n]}\to\mathbb{R}$ by
$\Delta f^{\prime}(i|S)=O(S,i)$. Then $A$ is a greedy algorithm acts on
submodular function $f$. For the two submodular function maximization problem
with submodular function $f$ and $f^{\prime}$, suppose algorithm $A$ outputs
sets $S_{A}$ with $f(S_{A})=\mathsf{alg}$ and
$f^{\prime}(S_{A})=\mathsf{alg}^{\prime}$ respectively, and suppose algorithm
$A^{*}$ outputs sets $S_{A^{*}}$ with $f(S_{A^{*}})=\mathsf{opt}$ and
$f^{\prime}(S_{A^{*}})=\mathsf{opt}^{\prime}$ respectively.

By Theorem 4.1, since $A$ is the greedy algorithm of the submodular
maximization problem with $f^{\prime}$, $\mathsf{alg}^{\prime}$ is at least
$1-1/e$ times the optimal algorithm of the submodular maximization problem
with $f^{\prime}$, hence is at least $1-1/e$ times the output value of
$A^{*}$, which is, $\mathsf{alg}^{\prime}\geq(1-1/e)\mathsf{opt}^{\prime}$.

Since $O(S,i)\geq\Delta(i|S)-\epsilon$,
$\mathsf{opt}^{\prime}=f^{\prime}(S_{A^{*}})\geq
f(S_{A^{*}})-k\epsilon=\mathsf{opt}-k\epsilon$.

Since $O(S,i)\leq\Delta(i|S)+\epsilon$,
$\mathsf{alg}^{\prime}=f^{\prime}(S_{A})\leq
f(S_{A})+k\epsilon=\mathsf{alg}+k\epsilon$.

Combining the 3 equations, we have

$\displaystyle\mathsf{alg}\geq\mathsf{alg}^{\prime}-k\epsilon\geq(1-1/e)\mathsf{opt}^{\prime}-k\epsilon\geq(1-1/e)\mathsf{opt}-k(2-1/e)\epsilon.$

∎

Algorithm 8 Greedy Algorithm with Batch

1:procedure BatchAlg($n,k,\\{u_{1},\cdots,u_{n}\\}\subset\mathbb{R}^{d}$)

2: $S_{0}\leftarrow\emptyset$

3: for $t=0\to k-1$ do

4: $A_{t}\leftarrow h(S_{t})$

5: $w_{\max}\leftarrow-1$

6: $j_{\max}\leftarrow-1$

7: for $b=1$ to $m$ do

8: $U\leftarrow[~{}u_{(b-1)d+1}~{}u_{(b-1)d+2}~{}\cdots~{}u_{(b-1)d+d}~{}]$

9: $M\leftarrow U^{\top}A_{t}U$

10: for $j=1$ to $d$ do

11: $j_{\mathrm{tmp}}\leftarrow(b-1)\cdot d+j$

12: if $M_{j,j}>w_{\max}$ and $j_{\mathrm{tmp}}\in\overline{S}_{t}$ then

13: $w_{\max}\leftarrow M_{j,j}$

14: $j_{\max}\leftarrow j_{\mathrm{tmp}}$

15: end if

16: end for

17: end for

18: $S_{t+1}\leftarrow S_{t}\cup\\{j_{\max}\\}$

19: end for

20: return $S_{k}$

21:end procedure

##  Appendix C Omitted proofs of our data structures

This section is organized as follows: Section C.1 provides a complete
quadratic form search data structure which can approximately return the
quadratic form $u_{j}^{\top}Au_{j}$ for a query matrix $M$ and given vectors
$u_{1},u_{2},\cdots,u_{n}$; Section C.2 complements the omitted proofs of our
inner product estimation data structure (see Section 5), which can return the
approximate inner products between a query vector $v$ and a list of given
vectors $u_{1},u_{2},\cdots,u_{n}$; Section C.3 complements the omitted proofs
of our faster quadratic form data structure (see Section 6), which can
approximately return the quadratic form $u_{j}^{\top}Au_{j}$ for a query
matrix $M$ and given vectors $u_{1},u_{2},\cdots,u_{n}$.

###  C.1 Warmup: A quadratic form search data structure using IPE

We start with presentting a less optimal implementation of our data structure.
In section C.2, we will show a better and optimzed data structure.

######  Theorem C.1.

There is a data structure which uses
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{4}\log(1/\delta))$ space with the
following procedures:

  * •

Init$(\\{u_{1},u_{2},\cdots,u_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$.
Given vectors $u_{1},u_{2},\cdots,u_{n}$, accuracy parameter $\epsilon$ and
failure probability $\delta$, the data structure initializes with time
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{4}\log(1/\delta))$.

  * •

Query$(M\in\mathbb{R}^{d\times d})$. Given a $d\times d$ matrix $M$, the data
structure outputs a $j_{0}\in\overline{S}_{t}$ such that
$u_{j_{0}}^{\top}Mu_{j_{0}}\geq\max_{j}\\{u_{j}^{\top}A_{t}u_{j}\\}-2\epsilon$
with probability at least $1-\delta$ in time
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d)d^{3}\log(1/\delta))$.

  * •

Delete$(i\in[n])$. Given index $i$, the data structure deletes $u_{i}$ from
the candidate index set in time $O(\log n)$.

###### Proof.

This theorem follows from Lemma C.2, Lemma C.3, Lemma C.4 and Lemma C.5, where
Lemma C.2 focuses on the correctness of this data structure, Lemma C.3 focuses
on proving the running time of procedure Init, Lemma C.4 focuses on the
running time of procedure Query, and C.5 aims to prove the running time of
procedure Delete. ∎

The following lemma proves the correctness of this data structure.

######  Lemma C.2 (Correctness).

Procedure Update outputs a $j_{0}\in\overline{S}_{t}$ such that
$u_{j_{0}}^{\top}Mu_{j_{0}}\geq\max_{j\in\overline{S}_{t}}\\{u_{j}^{\top}A_{t}u_{j}\\}-2\epsilon$
with probability at least $1-\delta$.

###### Proof.

By Theorem 5.2, for each $i\in[d]$, line 20 returns a list
$\\{\widetilde{w}_{i1},\widetilde{w}_{i2},\cdots,\widetilde{w}_{id}\\}$ such
that $\langle m_{i},(u_{j})_{i}\cdot
u_{j}\rangle-\epsilon/d\leq\widetilde{w}_{ij}\leq\langle
m_{i},(u_{j})_{i}\cdot u_{j}\rangle+\epsilon/d$ with probability at least
$1-\delta/d$, since $s_{j}=\sum_{i=1}^{d}\widetilde{w}_{ij}$, by union bound,
we have

$\displaystyle\sum_{i=1}^{d}\langle m_{i},(u_{j})_{i}\cdot
u_{j}\rangle-\epsilon\leq s_{j}\leq\sum_{i=1}^{d}\langle
m_{i},(u_{j})_{i}\cdot u_{j}\rangle+\epsilon$

with probability at least $1-\delta$. Note that $(u_{j})_{i}\cdot u_{j}$ is
the $i$-th column of $u_{j}u_{j}\top$, we have

$\displaystyle\sum_{i=1}^{d}\langle m_{i},(u_{j})_{i}\cdot
u_{j}\rangle=\langle
M,u_{j}u_{j}^{\top}\rangle=\operatorname{tr}[Mu_{j}u_{j}^{\top}]=u_{j}^{\top}Mu_{j},$

that is,

$\displaystyle u_{j}^{\top}Mu_{j}-\epsilon\leq s_{j}\leq
u_{j}^{\top}Mu_{j}+\epsilon$ (6)

with probability at least $1-\delta$. Thus the algorithm returns $j_{0}$ such
that

$\displaystyle u_{j_{0}}^{\top}Mu_{j_{0}}\leq$
$\displaystyle~{}s_{j_{0}}+\epsilon$ $\displaystyle=$
$\displaystyle~{}\max_{j\in\overline{S}_{t}}\\{s_{j}\\}+\epsilon$
$\displaystyle\leq$
$\displaystyle~{}\max_{j\in\overline{S}_{t}}\\{u_{j}^{\top}Mu_{j}+\epsilon\\}+\epsilon$
$\displaystyle=$
$\displaystyle~{}\max_{j\in\overline{S}_{t}}\\{u_{j}^{\top}Mu_{j}+\epsilon\\}+2\epsilon,$

where the first step comes from Eq. (6), the second step comes from line 25 in
Alg. 9, the third step comes from Eq. (6), the last step comes from identical
transformation. ∎

The following lemma analyzes the time complexity of Init.

######  Lemma C.3 (Init time).

Procedure Init takes $\widetilde{O}(\epsilon^{-2}D^{2}nd^{4}\log(1/\delta))$
time.

###### Proof.

By Theorem 5.2, for each $i\in[n]$, $\text{Ipe}_{i}$.Init takes

$\displaystyle\widetilde{O}((\epsilon/d)^{-2}D^{2}nd\log(d/\delta))=\widetilde{O}(\epsilon^{-2}D^{2}nd^{3}\log(1/\delta)$

time. Since there are $d$ Ipe, the total initialization time is
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{4}\log(1/\delta)$. ∎

The following lemma analyzes the time complexity of Query.

######  Lemma C.4 (Query time).

Procedure Query takes
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d)d^{3}\log(1/\delta))$ time.

###### Proof.

By Theorem 5.2, line 20 takes
$\widetilde{O}((\epsilon/d)^{-2}D^{2}(n+d)\log(d/\delta))=\widetilde{O}(\epsilon^{-2}D^{2}(n+d)d^{2}\log(d/\delta))$
time. Since this procedure is called for $d$ times, the total time is
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d)d^{3}\log(d/\delta))$ time. ∎

The following lemma analyzes the running time of procedure Delete.

######  Lemma C.5 (Delete time).

Procedure Delete takes $O(\log n)$ time to delete an index from candidate
index set.

###### Proof.

This holds trivially since it takes $O(\log n)$ time to find an index in the
candidate index set $S$. ∎

Algorithm 9 Data Structure ds

1:data structure ds

2:members

3: $S$ (Candidate index set)

4: IPE $\text{Ipe}_{1},\text{Ipe}_{2},\cdots,\text{Ipe}_{d}$

5:end members

6:

7:procedure
Init($\\{u_{1},u_{2},\cdots,u_{n}\\}\subset\mathbb{R}^{d},\epsilon>0,\delta>0$)

8: $S=[n]$

9: for $i=1$ to $d$ do

10: $\text{Ipe}_{i}$.Init$(\\{(u_{1})_{i}\cdot u_{1},(u_{2})_{i}\cdot
u_{2},\cdots,(u_{n})_{i}\cdot u_{n}\\},\epsilon/d,\delta/d)$

11: end for

12:end procedure

13:

14:procedure Query($M\in\mathbb{R}^{d\times d}$)

15: for $i\in S$ do

16: $s_{i}\leftarrow 0$

17: end for

18: for $i=1$ to $d$ do

19: $m_{i}\leftarrow$ the $i$-th column of $M$

20:
$\\{\widetilde{w}_{i1},\widetilde{w}_{i2},\cdots,\widetilde{w}_{id}\\}\leftarrow\text{Ipe}_{i}$.Query$(m_{i})$

21: for $j\in S$ do

22: $s_{j}\leftarrow s_{j}+\widetilde{w}_{j}$

23: end for

24: end for

25: return $\arg\max_{j}\\{s_{j}\\}$

26:end procedure

27:

28:procedure Delete($i\in[n]$)

29: $S\leftarrow S\backslash\\{i\\}$

30:end procedure

31:end data structure

###  C.2 Proof of Theorem 5.2: Inner product estimation

The goal of this section is to prove the following theorem.

######  Theorem C.6 (Formal version of Theorem 5.2).

There is a data structure uses
$\widetilde{O}(\epsilon^{-2}D^{2}nd\log(1/\delta))$ space for the Online
Approximate Adaptive Inner Product Estimation Problem with the following
procedures:

  * •

Init$(\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$:
Given data points $\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$
($\|x_{i}\|\leq D$, for all $i\in[n]$), an accuracy parameter $\epsilon$ and a
failure probability $\delta$ as input, the data structure preprocesses in time
$\widetilde{O}(\epsilon^{-2}D^{2}nd\log(1/\delta))$.

  * •

Update$(i\in[n],z\in\mathbb{R}^{d})$: Given index $i$ and coordinate $z$, the
data structure replace $x_{i}$ by $z$ in time
$\widetilde{O}(\epsilon^{-2}D^{2}d\log(1/\delta))$.

  * •

Query$(q\in\mathbb{R}^{d})$: Given a query point $q\in\mathbb{R}^{d}$ (where
$\|q\|\leq 1$), the Query operation takes $q$ as input and approximately
estimates the inner product of $q$ and all the data points
$\\{x_{1},x_{2},\dots,x_{n}\\}\subset\mathbb{R}^{d}$ in time
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d)\log(1/\delta))$ i.e. it provides a set
of estimates $\\{\widetilde{w}_{i}\\}_{i=1}^{n}$ such that:

$\displaystyle\forall i\in[n],\langle
q,x_{i}\rangle-\epsilon\leq\widetilde{w}_{i}\leq\langle
q,x_{i}\rangle+\epsilon$

with probability at least $1-\delta$, even for a sequence of adaptively chosen
queries.

###### Proof.

We prove Theorem 5.2 by proving the following three lemmas Lemma 5.3, Lemma
5.4 and Lemma 5.5, where Lemma 5.3 focuses on procedure Init, Lemma 5.4
focuses on procedure Update and Lemma 5.5 focuses on procedure Query. ∎

######  Lemma C.7 (Running time of initialization).

The procedure Init in Algorithm 4 runs in time
$\widetilde{O}(\epsilon^{-2}D^{2}nd\log(1/\delta))$.

###### Proof.

This reason is that the member Ade has Init time

$\displaystyle\widetilde{O}(\epsilon^{\prime-2}nd\log(1/\delta))=\widetilde{O}(\epsilon^{-2}D^{2}nd\log(1/\delta))$

according to Theorem B.5. ∎

######  Lemma C.8 (Running time of Update).

The procedure Update in Algorithm 4 runs in time
$\widetilde{O}(\epsilon^{-2}D^{2}d\log(1/\delta))$.

###### Proof.

The reason is that the member Ade has Update time
$\widetilde{O}(\epsilon^{\prime-2}d\log(1/\delta))=\widetilde{O}(\epsilon^{-2}D^{2}d\log(1/\delta))$
by Theorem B.5 ∎

######  Lemma C.9 (Correctness and running time of Query).

The procedure Query in Algorithm 4 outputs $\\{\widetilde{w}_{i}\\}_{i=1}^{n}$
correctly and runs in time

$\displaystyle\widetilde{O}(\epsilon^{-2}D^{2}(n+d)\log(1/\delta)).$

###### Proof.

For the correctness part of procedure Query, let us denote
$\|Q(x_{i})-P(y)\|_{2}$ by $d_{i}$, using asymmetric transformation we have

$\displaystyle\langle x_{i},y\rangle$ $\displaystyle=D-\frac{1}{2}Dd_{i}^{2},$

and by Theorem B.5, Ade.Query($P(y)$) gives a series of
$\\{\widetilde{d_{i}}\\}_{i=1}^{n}$ with

$\displaystyle(1-\epsilon^{\prime})d_{i}\leq\widetilde{d_{i}}\leq(1+\epsilon^{\prime})d_{i},$

thus

$\displaystyle\widetilde{w_{i}}=D-\frac{D}{2}\widetilde{d_{i}}^{2}\leq
D-\frac{D}{2}(1-\epsilon^{\prime})^{2}d_{i}^{2}\leq\langle
x_{i},y\rangle+\frac{D}{2}(2\epsilon^{\prime}-\epsilon^{\prime
2})d_{i}^{2}\leq\langle x_{i},y\rangle+\epsilon,$
$\displaystyle\widetilde{w_{i}}=D-\frac{D}{2}\widetilde{d_{i}}^{2}\geq
D-\frac{D}{2}(1+\epsilon^{\prime})^{2}d_{i}^{2}\geq\langle
x_{i},y\rangle-\frac{D}{2}(2\epsilon^{\prime}+\epsilon^{\prime
2})d_{i}^{2}\geq\langle x_{i},y\rangle-\epsilon,$

where we use $\frac{D}{2}(2\epsilon^{\prime}-\epsilon^{\prime 2})\leq
D\epsilon^{\prime}\leq\epsilon$ and
$\frac{D}{2}(2\epsilon^{\prime}+\epsilon^{\prime
2})\leq\frac{3}{2}D\epsilon^{\prime}\leq\epsilon$. And for the running time,
it holds because the member Ade has Query time

$\displaystyle\widetilde{O}(\epsilon^{\prime-2}(n+d)\log(1/\delta))=\widetilde{O}(\epsilon^{-2}D^{2}(n+d)\log(1/\delta))$

according to Theorem B.5. ∎

###  C.3 Proof of Theorem 6.1: Faster quadratic form search data structure

######  Theorem C.10.

There exists a data structure uses
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{2}\log(1/\delta))$ space with the
following procedures:

  * •

Init$(\\{u_{1},u_{2},\cdots,u_{n}\\}\subset\mathbb{R}^{d},\epsilon\in(0,1),\delta\in(0,1))$.
Given vectors $u_{1},u_{2},\cdots,u_{n}$ satisfying $\|u_{i}\|_{2}\leq D$ for
any $i\in[n]$, accuracy parameter $\epsilon$ and failure probability $\delta$,
the data structure initializes with time
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{2}\log(1/\delta))$.

  * •

Query$(M\in\mathbb{R}^{d\times d})$. Given a $d\times d$ matrix $M$, the data
structure outputs a $j_{0}\in\overline{S}_{t}$ such that
$u_{j_{0}}^{\top}Mu_{j_{0}}\geq\max_{j}\\{u_{j}^{\top}Mu_{j}\\}-2\epsilon$
with probability at least $1-\delta$ in time
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d^{2})\log(1/\delta))$.

  * •

Delete$(i\in[n])$. Given index $i$, the data structure deletes $u_{i}$ from
the candidate index set in time $O(\log n)$.

###### Proof.

This theorem follows from Lemma 6.2, Lemma 6.3, Lemma 6.4 and Lemma 6.5. ∎

######  Lemma C.11 (Correctness).

Procedure Update outputs a $j_{0}\in S$ such that
$u_{j_{0}}^{\top}Mu_{j_{0}}\geq\max_{j\in\overline{S}_{t}}\\{u_{j}^{\top}A_{t}u_{j}\\}-2\epsilon$
with probability at least $1-\delta$.

###### Proof.

By Theorem 5.2, line 16 returns a list
$\\{\widetilde{w}_{1},\widetilde{w}_{2},\cdots,\widetilde{w}_{n}\\}$ such that
$\langle m,v_{i}\rangle-\epsilon\leq\widetilde{w}_{i}\leq\langle
m,v_{i}\rangle+\epsilon$ with probability at least $1-\delta$. Note that

$\displaystyle\langle m,v_{i}\rangle=\sum_{j=1}^{d}\langle
m_{j},(u_{i})_{j}\cdot u_{i}\rangle=\langle
M,u_{i}u_{i}^{\top}\rangle=\operatorname{tr}[Mu_{i}u_{i}^{\top}]=u_{i}^{\top}Mu_{i},$

where the first step follows from the definitions of $m$ and $v_{i}$, the
second step follows from $(u_{i})_{j}\cdot u_{i}$ equals the $j$-th column of
$u_{i}u_{i}^{\top}$, the third step follows from $\langle
A,B\rangle=\operatorname{tr}[AB^{\top}]$, and the last step follows from
$\operatorname{tr}[AB]=\operatorname{tr}[BA]$. Thus

$\displaystyle u_{i}^{\top}Mu_{i}-\epsilon\leq\widetilde{w}_{i}\leq
u_{i}^{\top}Mu_{i}+\epsilon$ (7)

with probability at least $1-\delta$. Hence procedure Update outputs a $j_{0}$
such that

$\displaystyle
u_{j_{0}}^{\top}Mu_{j_{0}}\leq\widetilde{w}_{j_{0}}+\epsilon=\max_{j\in
S}\\{\widetilde{w}_{j}\\}+\epsilon\leq u_{j}^{\top}Mu_{j}+2\epsilon$

with probability $1-\delta$, where the first step follows from Equation (7),
the second step follows from line 17 in Algorithm 5, and the last step follows
from Equation (7). ∎

######  Lemma C.12 (Init time).

Procedure Init takes $\widetilde{O}(\epsilon^{-2}D^{2}nd^{2}\log(1/\delta))$
time.

###### Proof.

By Theorem 5.2, Ipe.Init in line 11 takes
$\widetilde{O}(\epsilon^{-2}D^{2}nd^{2}\log(1/\delta))$ time, since
$\dim(v_{i})=d^{2}$ for each $i\in[n]$. ∎

######  Lemma C.13 (Query time).

Procedure Query takes
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d^{2})\log(1/\delta))$ time.

###### Proof.

By Theorem 5.2, line 16 takes
$\widetilde{O}(\epsilon^{-2}D^{2}(n+d^{2})\log(1/\delta))$ time. ∎

######  Lemma C.14 (Delete time).

Procedure Delete takes $O(\log n)$ time to delete an index from candidate
index set.

###### Proof.

This holds trivially since it takes $O(\log n)$ time to find an index in the
candidate index set $S$. ∎

##  Appendix D Alternative: Fast submodular maximization algorithm with LSH

###  D.1 Preliminary

Recent progress in locality sensitive hashing would also help us design faster
algorithms. Informally, we call a family of hash functions sensitive when it
tends to project points closed to each other to the same value and tends to
project points far away from each other to different value. The formal
definition of sensitive hashing is given in definition D.1.

######  Definition D.1 (Locality sensitive hashing, [39]).

Given parameter $R>0,c>1,0<p_{2}<p_{1}<1$, we say a family of hash functions
${\cal H}$ is $(R,cR,p_{1},p_{2})$-sensitive if it satisfies the following
conditions:

  * •

for any $x,y\in\mathbb{R}^{d}$, as long as $\|x-y\|_{2}\leq R$, then
$\Pr_{h\in{\cal H}}[h(x)=h(y)]\geq p_{1}$;

  * •

for any $x,y\in\mathbb{R}^{d}$, as long as $\|x-y\|_{2}\geq cR$, then
$\Pr_{h\in{\cal H}}[h(x)=h(y)]\leq p_{2}$.

The approximate near neighbor problem is to find a point $p$ closed to the
given point $q$ with some approximation error tolerance.

######  Definition D.2 (Approximate Near Neighbor, [62]).

Let $c>1$ and $r\in(0,2)$. Given an $n$-point dataset
$P\subset\mathbb{S}^{d-1}$ on the sphere, the goal of the $(c,r)$-Approximate
Near Neighbor (ANN) problem is to build a data structure that, given a query
$q\in\mathbb{S}^{d-1}$ with the promise that there exists a datapoint $p\in P$
with $\|p-q\|_{2}\leq r$ returns a datapoint $p^{\prime}\in P$ within distance
$c\cdot r$ from q.

Implementing a naive algorithm in a brute force way, we can solve the
approximate near neighbor problem in $O(nd)$ time and $O(nd)$ memory space. A
faster solution can be given in time $O(d\cdot n^{\rho})$ in $O(d\cdot
n^{\rho})$ time and $O(n^{1+\rho}+dn)$ space ([4]).

######  Theorem D.3 (Andoni and Razenshteyn [4] ).

Let $c>1$ and $r\in(0,2)$. Let $\rho=\frac{1}{2c^{2}-1}+o(1)$. The $(c,r)$-ANN
on a unit sphere $\mathbb{S}^{d-1}$ can be solved in space $O(n^{1+\rho}+dn)$
and query time $O(d\cdot n^{\rho})$.

###  D.2 Our Results

In this section, we give a greedy selection algorithm with data strctures
related to locality sensitive hashing (LSH).

We first give a definition of asymmetric transformation, e.g. see [62].

######  Definition D.4 (Asymmetric transformation).

Let $Y\subseteq\mathbb{R}^{d}$ and $\|b\|_{2}\leq 1$ for all $b\in B$. Let
$a\in\mathbb{R}^{d}$ with $\|a\|_{2}=1$. We define the following asymmetric
transformation:

$\displaystyle
P(b)=\left[\begin{array}[]{ccc}b^{\top}&\sqrt{1-\|b\|_{2}^{2}}&0\end{array}\right]^{\top},~{}~{}~{}~{}Q(a)=\left[\begin{array}[]{ccc}a^{\top}&0&\sqrt{1-\|a\|_{2}^{2}}\\\
\end{array}\right]^{\top}.$

Therefore, we have

$\displaystyle\|Q(a)\|_{2}=1,\|P(b)\|_{2}=1,\langle Q(a),P(b)\rangle=\langle
a,b\rangle.$

######  Theorem D.5 (Submodular function maximization problem with LSH).

There exists a data structure (see Algorithm 10) with the following
procedures:

  * •

Init$(\\{u_{1},u_{2},\cdots,u_{n}\\}\subset\mathbb{R}^{d},c\in(0,1),\delta\in(0,1))$.
Given vectors $u_{1},u_{2},\cdots,u_{n}$ satisfying $\|u_{i}\|_{2}\leq 1$ for
any $i\in[n]$, accuracy parameter $c\in(0,1)$, threshold parameter
$\tau\in(0,1)$ and failure probability $\delta\in(0,1)$, the data structure
initializes with time $O(d^{2}n^{1+\rho}\log(1/\delta))$.

  * •

Query$(M\in\mathbb{R}^{d\times d})$. Given a $d\times d$ matrix $M$ with
$\|M\|_{F}\leq 1$, as long as there exists a $j\in[n]$ with
$u_{j}^{\top}Mu_{j}\geq\tau$, then the data structure outputs an undeleted
index $j_{0}\in[n]$ such that $u_{j_{0}}^{\top}Mu_{j_{0}}\geq
c\max_{j}\\{u_{j}^{\top}Mu_{j}\\}$ with probability at least $1-\delta$ in
time $O(d^{2}n^{\rho}\log(1/\delta))$.

  * •

Delete$(i\in[n])$. Given index $i$, the data structure deletes $u_{i}$ from
the candidate index set in time $O(n^{\rho}\log(1/\delta))$.

Here $\rho=\frac{1-\tau}{1-2c\tau+\tau}+o(1)$.

###### Proof.

For procedure Init, computing $v_{1},\cdots,v_{n}$ needs $O(nd^{2})$ time, and
by Lemma B.3, since the dimension of every $Q(v_{i})$ is $d^{2}+2=O(d^{2})$,
maxip.Init$(Q(v_{1}),Q(v_{2}),\cdots,Q(v_{n}),\epsilon,\delta)$ runs in
$O(d^{2}n^{1+\rho}\log(1/\delta))$ time. Thus procedure Init runs in
$O(d^{2}n^{1+\rho}\log(1/\delta))$ time.

For procedure Query, computing $m$ needs $O(d^{2})$ time, and by Lemma B.3,
since $P(m)$ also has dimension $d^{2}+2=O(d^{2})$, maxip.Query$(P(m))$ needs
in $O(d^{2}n^{\rho}\log(1/\delta))$ time. Thus procedure Query runs in
$O(d^{2}n^{\rho}\log(1/\delta))$ time.

For procedure Delete, deleting $i$ from $S$ needs $O(1)$ time, and by Lemma
B.3, deleting $i$ from maxip needs $O(n^{\rho}\log(1/\delta))$ time. Thus
procedure Delete runs in $O(n^{\rho}\log(1/\delta))$ time.

For the correctness, first note that for any $i\in[n]$, $\langle
P(m),Q(v_{i})\rangle=\langle m,v_{i}\rangle=\langle
M,u_{i}u_{i}^{\top}\rangle=u_{i}^{\top}Mu_{i}$. And since the norm of $P(m)$
and $Q(v_{i})$ are both 1, by Lemma B.3, as long as there exists $j$ such that
$u_{j}^{\top}Mu_{j}\geq\tau$, maxip.Query$(P(m))$ outputs an index $i$ with
$u_{i}^{\top}Mu_{i}\geq c\max_{j\in[n]}\\{u_{j}^{\top}Mu_{j}\\}$ with
probability at least $1-\delta$.

Hence we complete the proof. ∎

Algorithm 10 Fast Quadratic Form Search Data Structure with LSH

1:data structure FQFSwithLSH

2:members

3: $S$ (Candidate index set)

4: Max-IP maxip

5:end members

6:

7:procedure
Init($\\{u_{1},u_{2},\cdots,u_{n}\\}\subset\mathbb{R}^{d},\epsilon>0,\delta>0$)

8: $S=[n]$

9: for $i=1$ to $n$ do

10: $v_{i}\leftarrow[~{}(u_{i})_{1}\cdot u_{i}^{\top}~{}~{}(u_{i})_{2}\cdot
u_{i}^{\top}~{}~{}\cdots~{}~{}(u_{i})_{d}\cdot u_{i}^{\top}~{}]^{\top}$

11: end for

12: maxip.Init$(\\{Q(v_{1}),Q(v_{2}),\cdots,Q(v_{n})\\},\epsilon,\delta)$

13:end procedure

14:

15:procedure Query($M\in\mathbb{R}^{d\times d}$)

16: Write $M$ as $[~{}m_{1}~{}m_{2}~{}\cdots~{}m_{d}~{}]$

17:
$m\leftarrow[~{}m_{1}^{\top}~{}m_{2}^{\top}~{}\cdots~{}m_{d}^{\top}~{}]^{\top}$

18: $i\leftarrow\text{maxip}$.Query$(P(m))$

19: return $v_{i}$

20:end procedure

21:

22:procedure Delete($i\in[n]$)

23: $S\leftarrow S\backslash\\{i\\}$

24: maxip.Delete$(i)$

25:end procedure

26:end data structure

######  Corollary D.6 (Combination of this data structure with the submodular
function maximization problem).

Suppose a nondecreasing submodular function $f$ satisfies that for any set
$S\subseteq[n]$ and an element $i\in[n]\backslash S$, $f(S\cup\\{i\\})-f(S)$
(defined as $\Delta(i|S)$) can be expressed as $u_{i}^{\top}h(S)u_{i}$, where
$u_{i}$ is a vector only related to $i$ with $\|u_{i}\|\leq 1$, and $h$ is a
function only related to $S$ with $\|h(S)\|_{F}\leq 1$.

Then there is a submodular algorithm (see Algorithm 11) such that, given a
submodular function maximization problem with cardinality constraint and
precision parameter $\epsilon$, threshold parameter $\tau$ and failure
tolerance $\delta$ as input, it runs in $O(d^{2}n^{\rho}(n+k)\log(k/\delta))$
time (where $\rho=\frac{1-\tau}{1-2c\tau+\tau}+o(1)$) and returns a solution
$S$ with $f(S)\geq c(1-1/e)\max_{|S|=k}\\{f(S)\\}$ with probability at least
$1-\delta$.

###### Proof.

Similarly, it follows from Theorem D.5 and a variant of Corollary B.6. ∎

Algorithm 11 Fast submodular maximization algorithm using LSH

1:procedure
FastSubmodularMaximizationLSH($n,k,h,\\{u_{1},\cdots,u_{n}\\}\subset\mathbb{R}^{d}$)

2: FQFSL ds.Init($u_{1},\cdots u_{n},\epsilon,\delta/k$) $\triangleright$
Algorithm 10

3: $S_{0}\leftarrow\emptyset$

4: for $t=0\to k-1$ do

5: $A_{t}\leftarrow h(S_{t})$

6: $j\leftarrow\text{ds}.\textsc{Query}(A_{t})$

7: $S_{t+1}\leftarrow S_{t}\cup\\{j\\}$

8: $\text{ds}.\textsc{Del}(j)$

9: end for

10: return $S_{k}$

11:end procedure

##  Appendix E  Extension to Typical Constraints and Online Setting

In this section, we demonstrate how to extend our method to accelerate
variants of submodular maximization problems, e.g., submodular maximization
subject to different constraints and online submodular function maximization.

###  E.1 Constraints: matroid constraints

We introduce the definition of matroid in Definition E.1 and then define the
submodular function maximization subject to matroid constraints.

######  Definition E.1 (Matroid).

The pair $M=(E,\mathcal{I})$ is called a matroid where $\mathcal{I}$ is a
family of subsets of $E$, if

  * •

$\mathcal{I}$ contains empty set, i.e., $\emptyset\in\mathcal{I}$.

  * •

$\mathcal{I}$ is downward-closed, i.e., for each $A\subseteq B\subseteq E$, if
$B\in\mathcal{I}$, then $A\in E$.

  * •

$\mathcal{I}$ satisfies augmentation property, i.e., if $A,B\in\mathcal{I}$,
$|A|<|B|$, then there exsits $x\in B-A$ such that $A+\\{x\\}\in\mathcal{I}$.

Suppose $M=([n],\mathcal{I})$ is a matroid, then we call the optimization
problem (8) the submodular maximization with matroid constraints.

$\displaystyle\max_{S\in\subseteq[n]}$ $\displaystyle f(S)$ (8) s.t.
$\displaystyle S\in\mathcal{I}$

Fortunately, the greedy selection algorithm can be adjusted to be still
effective for the matroid constraint. Now we greedily update $S_{t}$ as
$S_{t+1}\leftarrow S_{t}+\\{j_{t}\\}$, where $j_{t}$ is selected as

$\displaystyle
j_{t}=\operatornamewithlimits{argmax}_{\\{j\\}+S_{t}\in\mathcal{I}\atop
j\in\overline{S}_{t}}\Delta_{f}(j|S_{t}).$ (9)

This greedy selection guarantees a $1/2$ approximation error constant [53].
Note that $j_{t}$ in (9) shares similar form as greedy selection for
cardinality constraint, except that we further restrict $j$ to satisfy
$\\{j\\}+S_{t}$. Algorithm 12 formally states how to apply our method.

Algorithm 12 Fast Submodular Function Maximization with Matroid Constraint

1:procedure
FastMatroidSubmodular($n,M=([n],\mathcal{I}),\\{u_{1},\cdots,u_{n}\\}\subseteq\mathbb{R}^{d}$)

2: $S_{0}\leftarrow\emptyset$

3: FQFS ds.Init($u_{1},u_{2},\cdots,u_{n},\epsilon,\delta/n$)

4: for $t=1\to\operatorname{rank}(M)$ do

5: ds.Delete($j$) for $S_{t-1}+\\{j\\}\notin\mathcal{I}$

6: $A_{t-1}\leftarrow h(S_{t-1})$

7: $j\leftarrow$ ds.Query($A_{t-1}$)

8: $S_{t}\leftarrow S_{t-1}\cup\\{j\\}$

9: ds.Delete($j$)

10: end for

11: return $S_{\operatorname{rank}(M)}$

12:end procedure

######  Lemma E.2 (Correctness).

Given $\epsilon>0$. Suppose $M=([n],{\cal I})$ is a matroid. Consider an
approximate greedy algorithm $A$ (see Algorithm 12) for the submodular
function maximization with matroid constraint $M$ that has an oracle $O$:
taken an arbitrary set $S\subseteq[n]$ and $i\in[n]\backslash S$, returns a
value $O(S,i)$ with guarantee that $\Delta(i|S)-\epsilon\leq
O(S,i)\leq\Delta(i|S)+\epsilon$. And in each time step
$t=1,2,\cdots,\operatorname{rank}(M)$, it selects

$\displaystyle
j_{t}=\operatornamewithlimits{argmax}_{\\{j\\}+S_{t}\in\mathcal{I}\atop
j\in\overline{S}_{t}}\\{O(S_{t-1},j)\\},$

and lets $S_{t}\leftarrow S_{t-1}\cup\\{j_{t}\\}$, then this algorithm makes
sure that it returns a set $S_{\operatorname{rank}(M)}$ with

$\displaystyle
f(S_{\operatorname{rank}(M)})\geq\frac{1}{2}\max_{T\in\mathcal{I}}\\{f(T)\\}-\operatorname{rank}(M)\epsilon.$

###### Proof.

For convenience, let $k=\operatorname{rank}(M)$. For $t=1,2,\cdots,k$, define
$\Delta_{t-1}$ be the increment of the greedy algorithm to the objective
function $f$ at time step $t$. Let $T$ and $S$ be optimal and greedy solutions
respectively, with $|T|=|S|=k$.

For $t=0,1,\cdots,k$, let $U_{t-1}$ be the set of all elements considered
during the first $t$ iterations before the addition of a $t$-th element to
$S_{t-1}$, that is, the set of the deleted indices (line 5 and line 9 in
Algorithm 12) at time step $t=0,1,\cdots,t$. For $t=1,\cdots,k$, let
$s_{t-1}=|T\cap(U_{t}-U_{t-1})|$, which describes whether the element added to
$S$ by the greedy algorithm at time step $t$ belongs to $T$.

For a set $S\subseteq[n]$ (not necessary in $M$), define $\text{rank}(S)$ be
the cardinality of the largest subset of $S$ in $M$, and define
$span(S)=\\{j\in N|\text{rank}(S\cup\\{j\\})=\text{rank}(S)\\}$.

First we show

$\displaystyle\sum_{j\in
T-S}\Delta(j|S)\leq\sum_{i=1}^{k}(\Delta_{i-1}+2\epsilon)s_{i-1}.$ (10)

This is because

$\displaystyle\sum_{j\in T-S}\Delta(j|S)\leq$ $\displaystyle~{}\sum_{j\in
T}\Delta(j|S)$ $\displaystyle=$ $\displaystyle~{}\sum_{t=1}^{K}\sum_{j\in
T\cap(U^{t}-U^{t-1})}\Delta(j|S)$ $\displaystyle\leq$
$\displaystyle~{}\sum_{t=1}^{K}(\Delta_{t-1}+2\epsilon)s_{t-1},$

where the first step follows from $f$ is nondecreasing, the second step
follows from the partition $T=T\cap\sum_{t=1}^{k}(U^{t}-U^{t-1})$ and the last
step follows from the greedy rule and the oracle guarantee.

Second we show that $U^{t}\subseteq\text{span}(S^{t})$. This is because for an
element $x$ of $U^{t}$, if $x\notin\text{span}(S^{t})$, then $x\notin S^{t}$,
implying $x$ is excluded in line 5 of Algorithm 12 at a time step no larger
than $t$, which means $S^{t}\cup\\{x\\}\notin M$, then
$x\in\text{span}(S^{t})$, a contradiction.

Third we show $\sum_{i=1}^{t}s_{i-1}\leq t$ for $t=1,\cdots,k$. This is
because $\sum_{i=1}^{t}s_{i-1}=|T\cap U^{t}|$. Since
$U^{t}\subseteq\text{span}(S^{t})$ we have $|T\cap
U^{t}|\leq|T\cap\text{span}(S^{t})|$. But since $T\in M$ and
$\operatorname{rank}(\text{span}(S^{t}))=|S^{t}|=t$, we obtain
$|T\cap\text{span}(S^{t})|\leq t$. Therefore $\sum_{i=1}^{t}s_{i-1}\leq t$.

Combining them, we have

$\displaystyle\sum_{i=1}^{k}\Delta_{i-1}s_{i-1}=$
$\displaystyle~{}\sum_{i=1}^{k-1}(\Delta_{i-1}-\Delta_{i})\sum_{j=1}^{i}s_{j-1}+\Delta_{k-1}\sum_{j=1}^{k}s_{j-1}$
$\displaystyle\leq$
$\displaystyle~{}\sum_{i=1}^{k-1}(\Delta_{i-1}-\Delta_{i})i+\Delta_{k-1}(k-1)$
$\displaystyle=$ $\displaystyle~{}\sum_{i=1}^{k}\Delta_{i-1}$ $\displaystyle=$
$\displaystyle~{}f(S),$ (11)

where the first step in the proof utilizes the method of summation by parts,
the second step is derived from the inequality $\sum_{i=1}^{t}s_{i-1}\leq t$,
the third step is obtained by consolidating these terms. Lastly, the final
step is justified by the equality $\sum_{i=1}^{k}\Delta_{i-1}=f(S)$.

Then we have

$\displaystyle f(T)\leq$ $\displaystyle~{}f(S)+\sum_{j\in T-S}\Delta(j|S)$
$\displaystyle\leq$ $\displaystyle~{}f(S)+f(S)+2\epsilon\sum_{i=1}^{k}s_{i-1}$
$\displaystyle=$ $\displaystyle~{}2f(S)+2\epsilon\operatorname{rank}(M),$

where the first step follows from properties of submodular functions, the
second step follows from Eq. (10) and (11), and the last step follows from
$\sum_{i=1}^{k}s_{i-1}=k=\operatorname{rank}(M)$.

Hence $f(S)\geq\frac{1}{2}f(T)-\operatorname{rank}(M)\epsilon$, which finishes
the proof. ∎

######  Theorem E.3.

There is a submodular function maximization algorithm such that, given a
submodular function maximization problem with matroid constraint and two
precision parameters $\epsilon,\delta$ as input, it runs in
$O(\epsilon^{-2}(nd+n^{2}+\operatorname{rank}(M)d^{2})\log(n/\delta))$ time
and returns a solution $S$ with $f(S)\geq
1/2\max_{S\in\mathcal{I}}\\{f(S)\\}-\operatorname{rank}(M)\epsilon$ with
probability at least $1-\delta$.

###### Proof.

Combining Lemma E.2 (the correctness of Algorithm 12) and time complexity
analysis of operations in Section C, we prove the conclusion. ∎

###  E.2 Constraints: knapsack constraints

Another natural constraint that often appears in the submodular function
maximization problem is the knapsack constraint. It views the ground set as
indices of items and each item $j\in[n]$ has a weight $w(j)$. We have a
knapsack to put some items into it, subject to the constraint that the total
weight of selected items can not exceed the maximum load of the knapsack.

######  Definition E.4 (Maximization with knapsack constraints).

We call the maximization problem (12) as the submodular function maximization
problem with knapsack constraints.

$\displaystyle\max_{S\subseteq[n]}$ $\displaystyle f(S)$ (12) s.t.
$\displaystyle\sum_{j\in S}w(j)\leq W$

where $f$ is the objective submodular function, $w(j)\geq 0$ is the weight for
item $j$, and $W\geq 0$ is the maximum load of the knapsack.

Similarly, a natural way to adjust the greedy selection algorithm is to update
$S_{t}$ as

$\displaystyle S_{t+1}\leftarrow S_{t}+\\{j_{t}\\},$

where $j_{t}$ is selected as

$\displaystyle j_{t}=\operatornamewithlimits{argmax}_{w(j)+w(S_{t})\leq W\atop
j\in\overline{S}_{t}}\frac{\Delta_{f}(j|S_{t})}{w(j)}.$ (13)

Compare the updating rule (13) for the knapsack case to the rule in Algorithm
2, we note that there are two differences: in (13) we further restrict $j$ to
satisfy $w(j)+w(S_{t})\leq W$ and we substitute $\Delta_{f}(j|S_{t})$ by
$\frac{\Delta_{f}(j|S_{t})}{w(j)}$.

For the additional restriction

$\displaystyle w(j)+w(S_{t})\leq W,$

we can add this restriction to our data structure too. For the
$\Delta_{f}(j|S_{t})$, we can modify our embedding representation. Let
$v_{j}=\frac{u_{j}}{\sqrt{w(j)}}$, then we have

$\displaystyle\frac{\Delta_{f}(j|S)}{w(j)}=$
$\displaystyle~{}\frac{u_{j}^{\top}h(S)u_{j}}{w(j)}$ $\displaystyle=$
$\displaystyle~{}v_{j}^{\top}h(S)v_{j}.$

The search for $j$ that maximizes $v_{j}^{\top}h(S)v_{j}$ is again in the form
of queries can be solved by our dynamic data structure.

However, simply using the greedy strategy (13) is not guranteed to yield a
small error. Fortunately, it is proved that greedy selection by uniform cost
and greedy selection by benefit per cost can not be bad at the same time [47].
Combing the two greedy strategies, an error ratio of $1/2-1/(2e)$ is
guaranteed. Algorithm 13 formally describes how to extend our method to the
knapsack constraints.

Algorithm 13 Fast Submodular Function Maximization Algorithm with Knapsack
Constraint

1:procedure
FastKnapsackSelection($n,W,\\{w(1),\cdots,w(n)\\},\\{u_{1},\cdots,u_{n}\\}\subseteq\mathbb{R}^{d}$)

2: $t\leftarrow 0$

3: $S_{0}\leftarrow\emptyset$

4: FQFS ds.Init($u_{1},u_{2},\cdots,u_{n},\epsilon,\delta/n$)

5: while ds is not empty do

6: $A_{t}\leftarrow h(S_{t})$

7: $j\leftarrow$ ds.Query($A_{t}$)

8: if $w(S_{t})+w(j)\leq W$ then

9: $S_{t+1}\leftarrow S_{t}\cup\\{j\\}$

10: $t\leftarrow t+1$

11: end if

12: ds.Delete($j$)

13: end while

14: return $S_{t}$

15:end procedure

16:

17:procedure
FastKnapsackSubmodular($n,W,\\{w(1),\cdots,w(n)\\},\\{u_{1},\cdots,u_{n}\\}\subseteq\mathbb{R}^{d}$)

18: for $i=1\to n$ do

19: $v_{i}\leftarrow u_{i}/\sqrt{w(i)}$

20: end for

21:
$S_{\text{uc}}\leftarrow\text{FastKnapsackSelection}(n,W,\\{w(i)\\}_{i=1}^{n},\\{u_{i}\\}_{i=1}^{n})$

22:
$S_{\text{cb}}\leftarrow\text{FastKnapsackSelection}(n,W,\\{w(i)\\}_{i=1}^{n},\\{v_{i}\\}_{i=1}^{n})$

23: if $f(S_{\text{uc}})>f(S_{\text{cb}})$ then

24: $S\leftarrow S_{\text{uc}}$

25: else

26: $S\leftarrow S_{\text{cb}}$

27: end if

28: return $S$

29:end procedure

######  Lemma E.5 (correctness).

Given $\epsilon>0$. Consider an approximate greedy algorithm $A$ (see
Algorithm 13) for the submodular function maximization with knapsack
constraints that has an oracle $O$: taken an arbitrary set $S\subseteq[n]$ and
$i\in[n]\backslash S$, returns a value $O(S,i)$ with guarantee that
$\Delta(i|S)-\epsilon\leq O(S,i)\leq\Delta(i|S)+\epsilon$ and
$O^{\prime}(S,i)$ with guarantee that $\frac{\Delta(i|S)}{w(i)}-\epsilon\leq
O^{\prime}(S,i)\leq\frac{\Delta(i|S)}{w(i)}+\epsilon$. In the first pass, in
each time step $t$, it selects

$\displaystyle j_{t}=\operatornamewithlimits{argmax}_{w(\\{j\\}+S_{t})\leq
W\atop j\in\overline{S}_{t}}\\{O(S_{t-1},j)\\},$

and lets $S_{t}\leftarrow S_{t-1}\cup\\{j_{t}\\}$. Suppose the first pass ends
with a set $S_{k}$. In the second pass, in each time step $t$, it selects

$\displaystyle
j^{\prime}_{t}=\operatornamewithlimits{argmax}_{w(\\{j\\}+S_{t})\leq W\atop
j\in\overline{S}_{t}}\\{O^{\prime}(S_{t-1},j)\\},$

and lets $S^{\prime}_{t}\leftarrow S^{\prime}_{t-1}\cup\\{j^{\prime}_{t}\\}$.
Suppose the second pass ends with a set $S^{\prime}_{k^{\prime}}$. Then it
holds that

$\displaystyle\max\\{f(S_{k}),f(S^{\prime}_{k^{\prime}})\\}\geq(1/2-1/(2e))\max_{T:w(T)\leq
W}\\{f(T)\\}-L\epsilon.$

###### Proof.

Consider the second pass following Eq. (13) (corresponding to $S_{uc}$ in
Algorithm 13). Renumber the ground set $S=\\{x_{1},\cdots,x_{n}\\}$ such that
for each $i=0,1,\cdots,n$, the set of the selected elements at time step $i$
is $G_{i}:=\\{x_{1},\cdots,x_{i}\\}$ ($G_{0}:=\emptyset$). Let

$\displaystyle l=\arg\max_{i:c(G_{i})\leq B}\\{c(G_{i})\\}$

be the index corresponding to the iterations. Hence $G_{l}$ is the selected
set by the weighted greedy process.

Let $\operatorname{OPT}$ be the optimal set, and let
$L=c(\operatorname{OPT})$, $w=|\operatorname{OPT}|$.

By greedy rule,

$\displaystyle\frac{\Delta(x_{i}|G_{i-1})}{c(x_{i})}+\epsilon\geq$
$\displaystyle~{}O^{\prime}(G_{i-1},x_{i})$ $\displaystyle\geq$
$\displaystyle~{}\max_{y\in\overline{G_{i}}}\\{O^{\prime}(G_{i-1},y)\\}$
$\displaystyle\geq$
$\displaystyle~{}\max_{y\in\overline{G_{i}}}\\{\frac{\Delta(y|G_{i-1})}{c(y)}\\}-\epsilon.$

Since $f$ is nondecreasing, for $i=1,2,\cdots,l+1$, we have

$\displaystyle f(\operatorname{OPT})-f(G_{i-1})$ $\displaystyle~{}\leq
f(\operatorname{OPT}\cup G_{i-1})-f(G_{i-1})$
$\displaystyle=f(\operatorname{OPT}\backslash G_{i-1}\cup
G_{i-1})-f(G_{i-1}).$

Assume $\operatorname{OPT}\backslash G_{i-1}=\\{y_{1},\cdots,y_{m}\\}$, and
for $j=0,1,\cdots,m$, let
$Z_{j}=f(G_{i-1}\cup\\{y_{1},y_{2},\cdots,y_{j}\\})$, then

$\displaystyle
f(\operatorname{OPT})-f(G_{i-1})\leq\sum_{j=1}^{m}\Delta(y_{j}|Z_{j-1}).$

Now notice that

$\displaystyle\frac{\Delta(y_{j}|Z_{j-1})}{c(y_{j})}-\epsilon\leq\frac{\Delta(y_{j}|G_{i-1})}{c(y_{j})}-\epsilon\leq\frac{f(G_{i})-f(G_{i-1})}{c(x_{i})}+\epsilon,$

where the first step follows from $f$ is nondecreasing and the second step
follows from the greedy rule, we have

$\displaystyle\Delta(y_{j}|Z_{j-1})\leq\frac{c(y_{j})}{c(x_{i})}(f(G_{i})-f(G_{i-1}))+2c(y_{j})\epsilon.$

Since $\sum_{j=1}^{m}c(y_{j})\leq L$, it holds that

$\displaystyle f(\operatorname{OPT})-f(G_{i-1})=$
$\displaystyle~{}\sum_{j=1}^{m}\Delta(y_{j}|Z_{j-1})$ $\displaystyle\leq$
$\displaystyle~{}L\frac{f(G_{i})-f(G_{i-1})}{c(x_{i})}+2L\epsilon,$

that is,

$\displaystyle
f(G_{i})-f(G_{i-1})\geq\frac{c(x_{i})}{L}(f(\operatorname{OPT})-f(G_{i-1}))-2\epsilon.$

Then by induction, we have

$\displaystyle
f(G_{i})\geq(1-\prod_{k=1}^{i}(1-\frac{c(x_{k})}{L}))f(\operatorname{OPT})-2L\epsilon.$

This is because first it holds for $i=1$; then suppose it holds for $i-1$, we
have

$\displaystyle f(G_{i})$
$\displaystyle\geq\frac{c(x_{i})}{L}f(\operatorname{OPT})+(1-\frac{c(x_{i})}{L})f(G_{i-1})-2\epsilon$
$\displaystyle\geq(1-\prod_{k=1}^{i}(1-\frac{c(x_{k})}{L}))f(\operatorname{OPT})-2L(1-\frac{c(x_{i})}{L})\epsilon-2\epsilon$
$\displaystyle\geq(1-\prod_{k=1}^{i}(1-\frac{c(x_{k})}{L}))f(\operatorname{OPT})-2L(1-\frac{1}{L})\epsilon-2\epsilon$
$\displaystyle=(1-\prod_{k=1}^{i}(1-\frac{c(x_{k})}{L}))f(\operatorname{OPT})-2L\epsilon.$
(14)

After that, we have

$\displaystyle f(G_{l+1})$
$\displaystyle\geq(1-\prod_{k=1}^{l+1}(1-\frac{c(x_{k})}{L}))f(\operatorname{OPT})-2L\epsilon$
$\displaystyle\geq(1-\prod_{k=1}^{l+1}(1-\frac{c(x_{k})}{G_{l+1}}))f(\operatorname{OPT})-2L\epsilon$
$\displaystyle\geq(1-\prod_{k=1}^{l+1}(1-\frac{1}{l+1}))f(\operatorname{OPT})-2L\epsilon$
$\displaystyle\geq(1-\frac{1}{e})f(\operatorname{OPT})-2L\epsilon,$

where the first step follows from Eq. (14), the second step follows from
Jensen’s inequality,

Furthermore, note that the violating increase $F(G_{l+1})-F(G_{l})$ is bounded
by $F(x^{*})$ for $x^{*}=\arg\max_{x\in W}F(x)$, i.e. the second candidate
solution considered by the modified greedy algorithm. Hence

$\displaystyle f(G_{l})+f(x^{*})\geq$ $\displaystyle~{}f(G_{l+1})$
$\displaystyle\geq$
$\displaystyle~{}(1-\frac{1}{e})f(\operatorname{OPT})-2L\epsilon,$

so at least one of the values $F(x^{*})$ or $F(G_{l})$ must be greater than or
equal to

$\displaystyle((1/2-1/(2e))f(\operatorname{OPT})-L\epsilon).$

∎

######  Theorem E.6.

There is a submodular function maximization algorithm such that, given a
submodular function maximization problem with knapsack constraint and two
precision parameters $\epsilon,\delta$ as input, it runs in
$O(\epsilon^{-2}(nd+n^{2}+kd^{2})\log(k/\delta))$ time, where $k$ is the size
of the optimal solution, and returns a solution $S$ with

$\displaystyle f(S)\geq(1/2-1/(2e))\max_{S:w(S)\leq W}\\{f(S)\\}-L\epsilon$

with probability at least $1-\delta$.

###### Proof.

Combining Lemma E.5 (the correctness of Algorithm 13) and time complexity
analysis of operations in Section C, we prove the conclusion.

∎

###  E.3 Online decision

In the online decision setting, we receive one new element of the ground set
in each iteration $t$, and must decide $S_{t}$ immediately.

######  Definition E.7 (Online Setting in [59]).

Let $A$ denote a finite set of activities and $(a,\tau)\in
A\times\mathbb{R}_{+}$ denote an action, which means spending time $\tau$ on
activity $a$. We define a schedule $s$ as a sequence of actions
$s:=\langle(a_{1},\tau_{1}),\cdots(a_{m},\tau_{m})\rangle$. Let $\mathcal{S}$
denote the set of all schedules. Let $f^{(1)}\cdots f^{(n)}$ denote $n$ jobs,
where job $f^{(i)}:\mathcal{S}\rightarrow[0,1]$ is a monotone submodular
function. In each iteration, one job $f^{(i)}$ arrives. At time $t$, we have
the information about $\\{f^{(i)}\\}_{i=1}^{t-1}$. The schedule $S^{(i)}$ for
$f^{(i)}$ must be at time $t$. We define the time cost by a schedule $S$ as
$\ell(S):=\sum_{(a,\tau)\in S}\tau$. The goal of online submodular function
maximization is to minimize the regret $R$, which is defined as

$\displaystyle
R(S^{(1)},\cdots,S^{(n)}):=(1-1/e)\frac{\sum_{i=1}^{n}f^{(i)}(S^{*})}{n}-\frac{\sum_{i=1}^{n}f^{(i)}(S^{(i)})}{n}.$

where $S^{*}:=\arg\max_{S\in\mathcal{S}}\frac{\sum_{i=1}^{n}f^{(i)}(S*)}{n}$
is the optimal schedule, subject to the constraint
$\operatorname*{{\mathbb{E}}}[\ell(S^{(i)})]=T$.

An algorithm named online greedy (OG) achieving small regret bound is proposed
in [59] for the online submodular function maximization. For the OG algorithm,
from the perspective of operations, the main bottleneck is still greedily
searching $\frac{\Delta_{f}(j|S_{t-1})}{\tau_{j}}$. Hence our method could be
adjusted for the online setting too.

##  Appendix F Fast Submodular Function Maximization

In this section, we utilize our data structure to design a greedy submodular
algorithm.

######  Theorem F.1 (Combination of our data structure with the submodular
function maximization problem).

There is a submodular algorithm such that, given a submodular function
maximization problem with cardinality constraint and two precision parameters
$\epsilon,\delta$ as input, it runs in
$O(\epsilon^{-2}(nd+kn+kd^{2})\log(k/\delta))$ time and returns a solution $S$
with $f(S)\geq(1-1/e)\max_{|S|=k}\\{f(S)\\}-k(2-1/e)\epsilon$ with probability
at least $1-\delta$.

###### Proof.

Combining Corollary B.6 (the correctness of Algorithm 1) and time complexity
analysis of operations in Section C, we prove the conclusion. ∎

##  Appendix G Extension to Typical Constraints and Online Setting

In practice, there are many variants of the setting we showed in Section 2.2.
For a general optimization problem, it is usually taxonomized based on three
perspectives: (i) objective function, (ii) constraint, and (iii) decision
time. For the objective function, as we have discussed in Section 2.2, our
embedding representation is fairly general, as the embedding representation
has enough degree of freedom. For the constraint, in addition to cardinality
constraint in the form of $|S|\leq k$, there are constraints of other
structures in applications, e.g., knapsack constraints and matroid
constraints. For the decision time, if the decision must be made before
knowing the complete information of the objective function and the
constraints, it is called online optimization.

For simplicity, we demonstrated our accelerating method on the specific case
of cardinality constraint and offline decision making. However, our method
could be naturally extended to other constraints and online setting. So we
will discuss the extension in this section. More detailed proofs related to
this section is refered to Section E.

###  G.1 Constraints: matroid constraints

In some applications, some elements in the ground set might not be added into
$S$ at the same time. For example, we might let the ground set $[n]$ be the
indices of vectors and we can only select linearly independent vectors as our
solution. To characterize such constraints, we introduce matroid here.

######  Definition G.1 (Matroid).

The pair $M=(E,\mathcal{I})$ is called a matroid where $\mathcal{I}$ is a
family of subsets of $E$, if

  * •

$\mathcal{I}$ contains empty set, i.e., $\emptyset\in\mathcal{I}$.

  * •

$\mathcal{I}$ is downward-closed, i.e., for each $A\subseteq B\subseteq E$, if
$B\in\mathcal{I}$, then $A\in E$.

  * •

$\mathcal{I}$ satisfies augmentation property, i.e., if $A,B\in\mathcal{I}$,
$|A|<|B|$, then there exsits $x\in B-A$ such that $A+\\{x\\}\in\mathcal{I}$.

Suppose $M=([n],\mathcal{I})$ is a matroid, then we call the optimization
problem (15) the submodular maximization with matroid constraints.

$\displaystyle\max_{S\in\subseteq[n]}$ $\displaystyle f(S)$ (15) s.t.
$\displaystyle S\in\mathcal{I}$

Fortunately, the greedy selection algorithm can be adjusted to be still
effective for the matroid constraint. Now we greedily update $S_{t}$ as
$S_{t+1}\leftarrow S_{t}+\\{j_{t}\\}$, where $j_{t}$ is selected as

$\displaystyle
j_{t}=\operatornamewithlimits{argmax}_{\\{j\\}+S_{t}\in\mathcal{I}\atop
j\in\overline{S}_{t}}\Delta_{f}(j|S_{t}).$ (16)

This greedy selection guarantees a $1/2$ approximation error constant. Note
that $j_{t}$ in (16) shares similar form as greedy selection for cardinality
constraint, except that we further restrict $j$ to satisfy $\\{j\\}+S_{t}$.
Hence by adding the same restriction to our dynamic data structure, our method
could solve the matroid constraint case. For more details, we refer to Section
E.

###  G.2 Constraints: knapsack constraints

Another natural constraint that often appears in the submodular function
maximization problem is the knapsack constraint. It views the ground set as
indices of items and each item $j\in[n]$ has a weight $w(j)$. We have a
knapsack to put some items into it, subject to the constraint that the total
weight of selected items can not exceed the maximum load of the knapsack. We
call the maximization problem (17) as the submodular function maximization
problem with knapsack constraint.

$\displaystyle\max_{S\in\subseteq[n]}$ $\displaystyle f(S)$ (17) s.t.
$\displaystyle\sum_{j\in S}w(j)\leq W$

where $f$ is the objective submodular function, $w(j)$ is the weight for item
$j$, and $W$ is the maximum load of the knapsack. Similarly, a natural way to
adjust the greedy selection algorithm is to update $S_{t}$ as
$S_{t+1}\leftarrow S_{t}+\\{j_{t}\\}$, where $j_{t}$ is selected as

$\displaystyle j_{t}=\operatornamewithlimits{argmax}_{w(j)+w(S_{t})\leq W\atop
j\in\overline{S}_{t}}\frac{\Delta_{f}(j|S_{t})}{w(j)}.$ (18)

Compare the updating rule (18) for the knapsack case to the rule in Algorithm
2, we note that there are two differences: in (18) we further restrict $j$ to
satisfy $w(j)+w(S_{t})\leq W$ and we substitute $\Delta_{f}(j|S_{t})$ by
$\frac{\Delta_{f}(j|S_{t})}{w(j)}$.

For the additional restriction

$\displaystyle w(j)+w(S_{t})\leq W,$

we can adding this restriction too our data structure too. For the
$\Delta_{f}(j|S_{t})$, we can modify our embedding representation. Let
$v_{j}=\frac{u_{j}}{\sqrt{w(j)}}$, then we have

$\displaystyle\frac{\Delta_{f}(j|S)}{w(j)}=\frac{u_{j}^{\top}h(S)u_{j}}{w(j)}=v_{j}^{\top}h(S)v_{j}.$

The search for $j$ that maximizes $v_{j}^{\top}h(S)v_{j}$ is again in the form
of queries can be solved by our dynamic data structure. For more details, we
refer to Section E.

###  G.3 Online decision

In the online decision setting, we receive one new element of the ground set
in each iteration $t$, and must decide $S_{t}$ immediately. An algorithm named
online greedy (OG) achieving small regret bound is proposed in [59] for the
online submodular function maximization. For the OG algorithm, from the
perspective of operations, the main bottleneck is still searching quantities
related to $\Delta_{f}(j|S_{t-1})$. Hence our method could be adjusted for the
online setting too. More details are refered to Section E.