High Probability Bounds for Stochastic Continuous Submodular Maximization

Evan Becker Jingdong Gao Ted Zadouri Baharan Mirzasoleiman

Department of Computer Science, University of California Los Angeles (UCLA)

###### Abstract

We consider maximization of stochastic monotone continuous submodular
functions (CSF) with a diminishing return property. Existing algorithms only
guarantee the performance in expectation, and do not bound the probability of
getting a bad solution. This implies that for a particular run of the
algorithms, the solution may be much worse than the provided guarantee in
expectation. In this paper, we first empirically verify that this is indeed
the case. Then, we provide the first high-probability analysis of the existing
methods for stochastic CSF maximization, namely PGA, boosted PGA, SCG, and
SCG++. Finally, we provide an improved high-probability bound for SCG, under
slightly stronger assumptions, with a better convergence rate than that of the
expected solution. Through extensive experiments on non-concave quadratic
programming (NQP) and optimal budget allocation, we confirm the validity of
our bounds and show that even in the worst-case, PGA converges to $OPT/2$, and
boosted PGA, SCG, SCG++ converge to $(1-1/e)OPT$, but at a slower rate than
that of the expected solution.

##  1 INTRODUCTION

While in general set functions are hard to optimize over, the subclass of
submodular functions have useful properties that allow us to predictably
achieve a certain approximation of the true optimal value in polynomial time
[27]. Submodular functions exhibit a natural diminishing returns property and
appear in a wide variety of applications such as sensor placement [15], graph
cuts [12], data summarization [17], marketing [14] and clustering [23]. Thus,
theoretical bounds on what optimization methods can achieve have important
real-world implications. Continuous submodular functions (CSF) extend the
notion of submodularity to continuous domains and provide an interesting class
of non-convex functions that are still tractable to optimize over [3]. CSFs
have several applications, including non-convex/non-concave quadratic
programming [3], robust budget allocation [25, 24], sensor energy management
[3], online resource allocation [7], learning assignments [9], and e-commerce
and advertising [19]. In addition, they enable solving many discrete
submodular problems efficiently through their continuous relaxation such as
multi-linear [5] or Lovas extensions [18]. This has motivated a body of work
on optimizing CSFs [2, 3, 4].

More recently, constrained maximization of stochastic submodular functions has
gained a lot of attention [11, 13, 20, 30]. A stochastic CSF can be formulated
as the expected value of stochastic functions
$\tilde{F}:\mathcal{X}\times\mathcal{Z}\rightarrow\mathbb{R}_{+}$:

$\max_{\boldsymbol{x}\in\mathcal{C}}F(\boldsymbol{x})=\max_{\boldsymbol{x}\in\mathcal{C}}\mathbb{E}_{\boldsymbol{z}\sim
P}[\tilde{F}(\boldsymbol{x},\boldsymbol{z})],$ (1)

where $\mathcal{C}\subseteq\mathbb{R}^{d}_{+}$ is a bounded convex set,
$\boldsymbol{x}\\!\in\\!\mathcal{X}$ is the optimization variable, and
$\boldsymbol{z}\\!\in\\!\mathcal{Z}$ is a random variable drawn from a
(potentially unknown) distribution $P\\!$. Note that Problem (1) only assumes
that $F(\boldsymbol{x})$ is DR-submodular, and not necessarily the stochastic
functions $\tilde{F}(\boldsymbol{x},\boldsymbol{z})$. The continuous greedy
algorithm [3] can produce arbitrarily bad solutions for Problem (1), due to
the non-vanishing variance of gradient approximations [11]. To address this,
Projected Gradient Ascent (PGA) with diminishing step-sizes is first shown to
provide a $[OPT/2\\!-\\!\epsilon]$ guarantee [11]. Later, Stochastic
Continuous Greedy (SCG) suggested to reduce the noise of gradient
approximations via a momentum term and provided a tight
$[(1\\!-\\!1/e)OPT\\!-\epsilon]$ guarantee [20]. This work was followed by
Stochastic Continuous Greedy++ (SCG++), which improved the complexity of SCG
[13], by leveraging a variance reduction technique [8]. Most recently, boosted
PGA algorithm using a non-oblivious function is proposed [30], which also
achieves a $[(1\\!-\\!1/e)OPT\\!-\epsilon]$ approximation guarantee.

However, the above algorithms only guarantee the performance of the solution
in expectation. This implies that it is indeed possible that for a particular
run of the algorithms, the optimizer gets extremely unlucky with its gradient
estimates, and return a solution that is drastically worse than the provided
guarantee in expectation. Indeed, as we confirm by our experiments, all the
algorithms for stochastic CSF, namely PGA, boosted PGA, SCG, and SCG++, may
have a very high variance in their returned solution, as the noise gets
larger. Crucially, the provided expectation bounds do not provide much
insight, besides perhaps a basic Markov inequality, into the probability of
getting these bad solutions. This is because expected guarantees rely on
bounding the variance of the gradient estimation error, and cannot bound the
total accumulated error required for deriving high probability bounds.

In this paper, we address the above question by providing the first high
probability analysis of the existing methods for stochastic CSF maximization.
High-probability bounds have been explored very recently for the most popular
optimization methods, namely, SGD [10], and momentum SGD [16]. But, deriving
high-probability bounds for submodular optimization has remained unaddressed.
Different than the analysis of the expectation bounds for stochastic CSF
maximization algorithms [11, 13, 21], our analysis leverages two different
strategies to bound the distance between the algorithmic solution and the
optimal value. The first strategy is using a martingale process to model
functions of the gradient noise, allowing for the use of Azuma-Hoeffding
inequality to provide high-probability bounds on the algorithmic solution. The
second strategy is to use Chebyshev’s inequality to bound sum of squared
errors in gradient estimators, with a high probability. Table 1 summarizes our
results.

Our contributions are as follows. We derive the first high-probability
analysis for stochastic CSF methods (under the same assumptions used for their
expectation bounds), and show that after $K$ queries to the stochastic
gradient oracle:

  * •

For Projected Gradient Ascent (PGA) [11] and Boosted PGA [30], the lower-bound
on the average function value during a run of the algorithm converges at rate
$O(\frac{1}{K^{1/2}})$.

  * •

For Stochastic Continuous Greedy (SCG) [20], the lower-bound on the final
solution converges at rate $\mathcal{O}(\\!\frac{\delta}{K^{1/3}})$, where
$\delta$ depends on the confidence threshold.

  * •

For Stochastic Continuous Greedy++ (SCG++) [13], the lower-bound on the final
solution converges at rate $\\!\mathcal{O}(\\!\frac{\delta}{K^{1/4}})$, where
$\delta$ depends on the confidence threshold.

  * •

Under the sub-Gaussian assumption on the stochastic gradient oracle, we derive
an improved high-probability bound on the final solution of SCG that converges
to $(1-\frac{1}{e})OPT$ at a faster $\mathcal{O}(\frac{1}{K^{1/2}})$ rate.
Interestingly, this rate even exceeds the rate of convergence to the
_expected_ solution provided by [20]. Our analysis involves providing the
first high probability bound for adaptive momentum optimization methods, which
can be applied to other smooth function classes to provide superior
convergence and generalization properties [26]. Hence, it is of independent
interest.

  * •

Our extensive experiments on a non-concave quadratic programming example (NQP)
and a realistic optimal budget allocation problem confirm the validity of our
bounds and show that even in the worst-case PGA still converges to the
$OPT/2$, and boosted PGA, SCG, SCG++ still converge to $(1\\!-\\!1/e)OPT$, but
at a slower rate.

Our results characterize the full distribution of the solutions for stochastic
CSF maximization methods. In doing so, they allow an algorithm designer to
answer questions about worst and best-case performance and even make
modifications to mitigate the risk of getting a bad solution.

Table 1: Comparison of existing expectation and our high-probability bounds for three stochastic monotone DR-submodular maximization algorithms, namely PGA, SCG, SCG++. Here $k$ is the number of queries to the stochastic gradient oracle $\nabla\tilde{F}$. Note that while our original bound is not tight for SCG, by using the slightly stronger condition of a sub-Gaussian gradient noise one can achieve an $\mathcal{O}(1/K^{1/2})$ bound (see Sec. 4.3.1). Algorithm | Expectation Bound | Original Noise Assumptions | Bound Converges w.h.p?
---|---|---|---
PGA [11] | $(\frac{1}{2})OPT-\mathcal{O}(\frac{1}{K^{1/2}})$ |  $\nabla\tilde{F}$ bounded | Yes, at $\mathcal{O}(1/K^{1/2})$ rate
Boosted PGA [30] | $(1-\frac{1}{e})OPT-\mathcal{O}(\frac{1}{K^{1/2}})$ |  $\nabla\tilde{F}$ bounded | Yes, at $\mathcal{O}(1/K^{1/2})$ rate
SCG [20] | $(1-\frac{1}{e})OPT-\mathcal{O}(\frac{1}{K^{1/3}})$ |  $Var(\nabla\tilde{F})$ bounded, sub-Gaussian* | Yes*, at $\mathcal{O}(1/K^{1/2})$ rate
SCG++ [13] | $(1-\frac{1}{e})OPT-\mathcal{O}(\frac{1}{K^{1/2}})$ |  $\tilde{F},\nabla\tilde{F},\nabla^{2}\tilde{F},\log(p(\boldsymbol{z}))$ bounded | Yes, at $\mathcal{O}(1/K^{1/4})$ rate

##  2 RELATED WORK

##### Deterministic continuous submodular maximization.

Maximizing deterministic continuous submodular functions have been first
studied by Wolsey [27]. More recently, [4] proposed a multiplicative weight
update algorithm that achieves $(1\\!-\\!1/e\\!-\\!\epsilon)$ approximation
guarantee after $\tilde{O}(n/\epsilon^{2})$ oracle calls to gradients of a
monotone smooth twice differentiable DR-submodular function, subject to a
polytope constraint ($n$ is the ground set size). Later, a conditional
gradient method similar to the continuous greedy algorithm is shown to obtain
a similar approximation factor after $O(n/\epsilon)$ oracle calls to gradients
of monotone DR-submodular functions subject to a down-closed convex body [3].
Such methods, however, require exact computation of the gradient of the
function, which is not provided in the stochastic setting.

##### Stochastic continuous submodular maximization.

For stochastic continuous submodular maximization, conditional gradient
methods may lead to arbitrarily poor solutions, due to the high noise variance
[11]. While the noise variance can be reduced by averaging the gradient over a
(large) mini-batch of samples at each iteration, averaging considerably
increases the computational complexity of each iteration and becomes
prohibitive in many applications. To address this, stochastic proximal
gradient method are first proposed. In particular, [11] showed that when the
expected function is monotone and DR-submodular, Projected Gradient Ascent
(PGA) provides a $OPT/2-\epsilon$ guarantee in $\mathcal{O}(1/\epsilon^{2})$
iterations. Later, [20] introduced Stochastic Continuous Greedy (SCG), which
reduces the noise of gradient approximations via exponential averaging and
achieves a $(1-1/e)OPT-\epsilon$ guarantee in expectation after
$\mathcal{O}(1/\epsilon^{3})$ iterations. More recently, Stochastic Continuous
Greedy++ (SCG++) improved the complexity of SCG to
$\mathcal{O}(1/\epsilon^{2})$, by using a stochastic path-integrated
differential estimator (SPIDER) [8] to reduce the variance of the stochastic
gradient. Most recently, boosted PGA algorithm using a non-oblivious function
is proposed [30], which also achieves a $[(1-1/e)OPT-\epsilon]$ approximation
guarantee in $\mathcal{O}(1/\epsilon^{2})$ iterations. Existing works,
however, only provide guarantees in expectation and cannot deliver any insight
on the distribution of the solutions or worst-case analysis.

##### High-probability bounds for stochastic submodular minimization.

 Very recently, [28] studied an extension of the stochastic submodular
_minimization_ problem, namely, the stochastic $L^{\natural}$-convex [22]
minimization problem. $L^{\natural}$-convex functions are reduced to
submodular functions when the ground set size is 2. Specifically, [28]
developed a polynomial time algorithm that returns a near-optimal solution
with a high probability. The proposed method relies on the Lovász extension of
an $L^{\natural}$-convex function to transform the original problem to an
equivalent continuous convex optimization problem, and applies the stochastic
subgradient method to solve the continuous convex problem. To the best of our
knowledge, high-probability bounds for continuous submodular _maximization_
have not been explored before.

##  3 BACKGROUND AND PROBLEM FORMULATION

##### Continuous submodular functions.

We start by reviewing definition of submodularity for set functions. A set
function $f:2^{V}\rightarrow\mathbb{R}_{+}$, defined on the ground set $V$ ,
is submodular if for all subsets $A,B\subseteq V$, we have that

$f(A)+f(B)\geq f(A\cup B)+f(A\cap B).$ (2)

The notion of submodularity can be extended to continuous domains. A
continuous function $F:\mathcal{X}\rightarrow\mathbb{R}_{+}$ defined on the
set $\mathcal{X}=\Pi_{i=1}^{n}\mathcal{X}_{i}$, where each $\mathcal{X}_{i}$
is a compact subset of $\mathbb{R}_{+}$, is continuous submodular if for all
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{X}$ we have

$F(\boldsymbol{x})+F(\boldsymbol{y})\geq
F(\boldsymbol{x}\vee\boldsymbol{y})+F(\boldsymbol{x}\wedge\boldsymbol{y}).$
(3)

Here, $\boldsymbol{x}\vee\boldsymbol{y}:=\max(\boldsymbol{x},\boldsymbol{y})$
is component-wise maximum and
$\boldsymbol{x}\wedge\boldsymbol{y}:=\min(\boldsymbol{x},\boldsymbol{y})$ is
component-wise minimum operations. A submodular function $F$ is monotone on
$\mathcal{X}$, if for every
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{X},\boldsymbol{x}\leq\boldsymbol{y}$
we have that $F(\boldsymbol{x})\leq F(\boldsymbol{y})$. A function $F$ defined
over $\mathcal{X}$ satisfies the diminishing returns (DR) property, if for
every
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{X},\boldsymbol{x}\leq\boldsymbol{y}$,
and any standard basis vector $e_{i}\in\mathbb{R}^{n}$ and any
$k\in\mathbb{R}_{+}$ s.t. $(ke_{i}+\boldsymbol{x})\in\mathcal{X}$ and
$(ke_{i}+\boldsymbol{x})\in\mathcal{X}$, it holds that

$f(ke_{i}+\boldsymbol{x})-f(\boldsymbol{x})\geq
f(ke_{i}+\boldsymbol{y})-f(\boldsymbol{y}).$ (4)

When $F$ is twice-differentiable, DR-submodularity implies that all diagonal
entries of the Hessian are non-positive [3]. I.e.,

$\forall
i=j,\quad\forall\boldsymbol{x}\in\mathcal{X}\quad\frac{\partial^{2}F(\boldsymbol{x})}{\partial
x_{i}\partial x_{j}}\leq 0.$ (5)

##### Stochastic continuous submodular maximization.

In this work, we focus on constrained maximization of stochastic continuous
DR-submodular functions. Formally, our goal is to find $\boldsymbol{x}^{*}$
that maximizes the expected value $F(\boldsymbol{x})$ of the stochastic
function $\tilde{F}(\boldsymbol{x},\boldsymbol{z})$ over $\boldsymbol{x}$,
where the expectation is with respect to the random variable $\boldsymbol{Z}$:

$\max_{\boldsymbol{x}\in\mathcal{C}}F(\boldsymbol{x}):=\max_{\boldsymbol{x}\in\mathcal{C}}\mathbb{E}_{\boldsymbol{z}\sim
P}[\tilde{F}(\boldsymbol{x},\boldsymbol{z})],$ (6)

where $\mathcal{C}\\!\subseteq\\!\mathbb{R}_{+}$ is a convex compact set, and
$\boldsymbol{z}$ is the realization of the random variable $\boldsymbol{Z}$
drawn from a distribution $P$. We assume that the expected objective function
$F(\boldsymbol{x})$ is monotone and DR-submodular and the stochastic functions
$\tilde{F}(\boldsymbol{x},\boldsymbol{z})$ may not be monotone nor submodular.
We denote by $OPT\\!\triangleq\max_{x\in\mathcal{C}}F(\boldsymbol{x})$ the
optimal value of $F(\boldsymbol{x})$ over $\mathcal{C}$.

##  4 HIGH-PROBABILITY BOUNDS FOR STOCHASTIC CONTINUOUS SUBMODULAR
MAXIMIZATION

Next, we discuss our high-probability bounds for stochastic CSF maximization
algorithms, namely Projected Gradient Ascent (PGA), boosted PGA, Stochastic
Continuous Greedy (SCG), and Continuous Greedy++ (SCG++).

###  4.1 Projected Gradient Ascent

We start by analyzing the worst-case performance of the PGA method which
achieves a $[OPT/2-\epsilon]$ approximation in expectation, in
$\mathcal{O}(1/\epsilon^{2})$ iteration [11]. PGA starts from an initial
estimate $\boldsymbol{x}_{0}\in\mathcal{C}$. Then at every iteration $t$, it
takes a step in the direction of the noisy gradient
$\boldsymbol{g}_{t}=\nabla\tilde{F}(\boldsymbol{x}_{t},\boldsymbol{z}_{t})$,
and projects the solution onto the convex set $\mathcal{C}$. The update rule
at step $t$ takes the following form:

$\boldsymbol{x}_{t+1}=\mathcal{P}_{\mathcal{C}}(\boldsymbol{x}_{t}+\mu_{t}\boldsymbol{g}_{t}),$
(7)

where, $\mu_{t}$ is the diminishing learning rate at step $t$, and
$\mathcal{P}_{\mathcal{C}}$ denotes the Euclidean projection onto the set
$\mathcal{C}$. The pseudocode is provided in Appendix B.

Hassani et al. [11] provided a lower bound on the expected function value,
$\mathbb{E}[F(\boldsymbol{x}_{\tau})]$, at a time-step $\tau$, sampled
uniformly at random from $\\{1,\dots,T\\}$. Important to note, however, is
that the derived expectation is not only over this random variable $\tau$, but
_also the noise_ coming from the gradient estimates. This implies that it is
possible that the optimizer gets extremely unlucky with its gradient
estimates, in which case no $\boldsymbol{x}_{t}$ satisfies the lower bound
(for example, consider the unlikely but still possible scenario where $\forall
t,\>\boldsymbol{g}_{t}=0$). In Theorem 1, we provide an exact answer for how
unlikely a failure event like this would be.

To do so, we make similar assumptions to [11]:

######  Assumption 1.

The diameter of the constraint set $\mathcal{C}$ is bounded by $D$. I.e.,
$\forall\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}$, we have

$\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert\leq D.$

######  Assumption 2.

The function $F$ is Lipschitz smooth with constant $L$, over $\mathcal{X}$.
I.e., $\forall\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}$, we have

$\left\lVert\nabla F(\boldsymbol{x})-\nabla F(\boldsymbol{y})\right\rVert\leq
L\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert.$

######  Assumption 3.

Stochastic gradients
$\boldsymbol{g}_{t}\\!=\\!\nabla\tilde{F}(\boldsymbol{x},\boldsymbol{z})$ are
bounded in distance from their mean
$\nabla{F}(\boldsymbol{x}_{t})=\mathbb{E}[\boldsymbol{g}_{t}]$:

$\left\lVert\nabla{F}(x_{t})-\boldsymbol{g}_{t}\right\rVert\leq M.$

The following theorem shows that for any fixed confidence interval $p$, the
lower bound on $\sum_{t\in[T]}F(\boldsymbol{x}_{t})/T$ will converge to
$OPT/2$ at a rate of $\mathcal{O}(\sqrt{\frac{\log(1/1-p)}{T}})$.

######  Theorem 1.

Consider running PGA for $T$ iterations with step size of
$\eta_{t}=\frac{2}{\sqrt{t}}$ with Assumptions 1,2,3 satisfied. Then with
probability $p\\!\geq\\!1\\!-\\!\delta$, where $\delta\\!\in\\![0,1]$, the
average function value returned by the algorithm is lower bounded by

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}F(\boldsymbol{x}_{t})$
$\displaystyle\geq\frac{1}{2}OPT-\frac{C}{\sqrt{T}}-DM\sqrt{\frac{\log(1/\delta)}{2T}}$
(8)
$\displaystyle\geq\frac{1}{2}OPT-\mathcal{O}\left(\sqrt{\frac{\log(1/\delta)}{T}}\right),$

where we denote the constant $C:=\left(\frac{8(L+M)^{2}+D^{2}}{8}\right)$.

Unlike the expectation bound provided in [11], Theorem 1 assures that with
high probability, _at least one iterate_ from a _single_ algorithm run will be
larger than the lower bound. Therefore, one could modify the default PGA
algorithm to return the best iterate, $\max_{t\in[T]}F(\boldsymbol{x}_{t})$,
which is guaranteed to also be lower bounded with high probability by $OPT/2$.
We note that even in the case where the true function evaluation is hard to
compute, one can still find the best iterate with high probability given
unbiased stochastic function evaluations
$\tilde{F}(\boldsymbol{x},\boldsymbol{z})$. Concretely, given the ordering of
iterates from highest to lowest function value
$\boldsymbol{x}_{[1]},\dots,\boldsymbol{x}_{[T]}$, consider the difference
between the best two solutions
$d:=F(\boldsymbol{x}_{[1]})-F(\boldsymbol{x}_{[2]})$. One can use a Hoeffding
bound to determine the relatively small number of samples, $m$, needed to
calculate $\bar{F}(\boldsymbol{x}):=\frac{1}{m}\sum\tilde{F}(\boldsymbol{x})$
for each iterate, such that
$\bar{F}(\boldsymbol{x}_{[1]})\\!>\\!F(\boldsymbol{x}_{[1]})-d/2$ and
$\bar{F}(\boldsymbol{x}_{[k]})\\!<\\!F(\boldsymbol{x}_{[2]})+d/2$ for all
$k>1$ occurs with very high probability. Alternatively, since
$F(\boldsymbol{x})\leq OPT\>\>\forall\boldsymbol{x}$, at least
$\frac{r}{r+(1/2)OPT}$ fraction of solutions are greater than
$\sum_{t\in[T]}F(\boldsymbol{x}_{t})/T-r$ for a slack variable $r$. That is,
with only $k$ true function evaluations, at least one good solution is found
with probabiliy $p>1-(1-r)^{k}$.

Theorem 1 relies on diminishing returns and smoothness of $F$, along with the
bound on $\mathcal{C}$ to first bound the difference between
$F(\boldsymbol{x}_{t})$ and $F(\boldsymbol{x}^{*})$ based on the inner product
between gradient noise and $\boldsymbol{x}_{t}-\boldsymbol{x}^{*}$. However,
instead of taking the expectation of this inequality, it directly shows that
with Assumption 3, these random products satisfy the conditions of a
c-lipschitz Martingale difference sequence. This allows using standard high
probability bounds (Azuma-Hoeffding). See Appendix A.2 for the full proof.

We note that Assumption 3 is stronger than simply bounded variance and is
necessary to apply the Azuma-Hoeffding inequality. However if
$\boldsymbol{g}_{t}=\nabla F(\boldsymbol{x}_{t})+\boldsymbol{z}_{t}$ with each
$\boldsymbol{z}_{t}$ being zero mean and Sub-Gaussian, a similar version of
Theorem 1 can be derived following [10].

######  Corollary 1.

Consider the case where we set $\delta=\exp(-\sqrt{T})$. Then the averaged
function value of PGA is lower bounded with probability $p\geq
1-2\exp(-\sqrt{T})$ by:

$\frac{1}{T}\sum_{t=1}^{T}F(\boldsymbol{x}_{t})\geq\frac{1}{2}OPT-\mathcal{O}\left(\frac{1}{T^{1/4}}\right).$
(9)

We see that as $T\rightarrow\infty$ we have both $p\rightarrow 1$ and
$\\!\mathcal{O}(1/T^{1/4})\\!\rightarrow 0$. Thus, our lower-bound is tight.

###  4.2 Boosted Projected Gradient Ascent

Very recently, boosted PGA [30] is proposed to provide
$[(1-\frac{1}{e}-\epsilon^{2})OPT]$ approximation in expectation, in
$\mathcal{O}(1/\epsilon^{2})$ iterations. The idea is to find an auxiliary
(non-oblivious) function that can provide a better approximation guarantee
than the original DR-submodular function. Then the stochastic gradients of the
non-oblivious function $F^{\prime}$ (instead of the stochastic gradient of the
original DR-submodular function $F$) are leveraged by PGA. Specifically, [30]
used the following non-oblivious function $F^{\prime}$ and its gradient
$\nabla F^{\prime}$:

$\displaystyle
F^{\prime}(\boldsymbol{x}):=\int_{0}^{1}\frac{e^{(s-1)}}{s}F(s*\boldsymbol{x})ds,$
(10) $\displaystyle\nabla
F^{\prime}(\boldsymbol{x}):=\int_{0}^{1}e^{(s-1)}\nabla
F(s*\boldsymbol{x})ds.$ (11)

This has the nice property that $\langle\boldsymbol{y}-\boldsymbol{x},\nabla
F^{\prime}(\boldsymbol{x})\rangle\geq(1-1/e)F(\boldsymbol{y})-F(\boldsymbol{x})$,
which guarantees $(1-1/e)OPT$ approximation. Additionally, when the original
function is Lipschitz smooth (Assumption 2), $F^{\prime}(\boldsymbol{x})$ is
Lipschitz smooth with constant $L^{\prime}=L(1+1/e)$. To efficiently
approximate $\nabla F^{\prime}$ given a noisy gradient estimate
$\nabla\tilde{F^{\prime}}$, [29] uses the following estimator:

$\displaystyle\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t}):=(1-\frac{1}{e})\nabla\tilde{F^{\prime}}(s_{t}*\boldsymbol{x}_{t}).$
(12)

Here, $s_{t}$ is independently sampled from a distribution
$\mathbb{P}(\boldsymbol{S}\\!\\!\leq\\!\\!s)\\!=\\!\\!\int_{0}^{s}\frac{1}{1-e^{-1}}\mathds{1}(u\\!\in\\![0,1])du$,
where $\mathds{1}$ is indicator function.

The following theorem provides a lower bound on
$\sum_{t\in[T]}F(\boldsymbol{x}_{t})/T$, with high probability.

######  Theorem 2.

Consider running boosted PGA for $T$ iterations with step size of
$\eta_{t}=\frac{2}{\sqrt{t}}$ with Assumptions 1,2,3 satisfied. Then with
probability $p\\!\geq\\!1\\!-\\!\delta$, where $\delta\\!\in\\![0,1]$, the
average function value returned by the algorithm is lower bounded by

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}F(\boldsymbol{x}_{t})$
$\displaystyle\geq(1-\frac{1}{e})OPT-\frac{C^{\prime}}{\sqrt{T}}-DM^{\prime}\sqrt{\frac{\log(1/\delta)}{2T}}$
$\displaystyle\geq(1-\frac{1}{e})OPT-\mathcal{O}\\!\left(\\!\sqrt{\frac{\log(1/\delta)}{T}}\right),$
(13)

where we denote the constant
$C^{\prime}:=\left(\frac{8(L^{\prime}D+M^{\prime})^{2}+D^{2}}{8}\right)$, and
constant $M^{\prime}:=(M+2LD)\left(1-\frac{1}{e}\right)$.

Note that this bound has the same rate of convergence as Theorem 1 up to a
constant factor. This similarity also means a result parallel to Corollary 1
can be derived, demonstrating that this algorithm will also converge with
$p\rightarrow 1$ as $T\rightarrow\infty$. The proof of Theorem 2 follows a
similar structure to Theorem 1. We bound the sum of differences
$F(\boldsymbol{x}_{t})-F(\boldsymbol{x}^{*})$ by a Martingale sequence with a
bounded difference property. The key distinction in the non-oblivious case is
that we must bound gradients from $\nabla F^{\prime}(\boldsymbol{x})$ as well
as $\nabla\tilde{F}^{\prime}(\boldsymbol{x})$. We defer the full proof to
Appendix A.3.

Guarantees for weakly submodular functions. We note that Theorems 1, 2 for PGA
and boosted PGA can be extended to $\gamma$-weakly DR-submodular functions,
where we have $\gamma=\inf_{\boldsymbol{x}\leq\boldsymbol{y}}\inf_{i}([\nabla
F(\boldsymbol{x})]_{i}/[\nabla F(\boldsymbol{y})]_{i})$). This setting
produces bounds with the same rate of convergence up to a constant, to
$(\frac{\gamma^{2}}{1+\gamma^{2}})OPT$ and $(1\\!-\\!e^{-\gamma})OPT$ for PGA
and Boosted PGA, respectively. Note that $\gamma\\!=\\!1$ indicates a
differentiable and monotone DR-submodular function.

###  4.3 Stochastic Continuous Greedy

Next, we analyze the worst-case performance of the Stochastic Continuous
Greedy (SCG) algorithm. SCG uses a momentum term to reduce the noise of
gradient approximations. It starts from $\boldsymbol{x}_{0}=\boldsymbol{0}$,
and at every iteration $t$, calculates:

$\bar{\boldsymbol{g}}_{t+1}=(1-\rho_{t})\bar{\boldsymbol{g}}_{t}+\rho_{t}\nabla\tilde{F}(\boldsymbol{x}_{t},\boldsymbol{z}_{t}),$
(14)

where $\rho_{t}$ is a stepsize which approaches zero as $t$ approaches
infinity, and $\bar{\boldsymbol{g}}_{0}=0$. The SCG is then ascent in the
direction:

$\boldsymbol{v}_{t}\leftarrow\arg\max_{\boldsymbol{v}\in\mathcal{C}}\\{\left<\bar{\boldsymbol{g}}_{t}^{T},\boldsymbol{v}\right>\\},$
(15)

using the following updates rule with step-size ${1}/{T}$:

$\boldsymbol{x}_{t+1}=\boldsymbol{x}_{t}+\frac{1}{T}\boldsymbol{v}_{t}.$ (16)

The stepsize $\frac{1}{T}$ and the initialization
$\boldsymbol{x}_{0}=\boldsymbol{0}$ ensure that after $T$ iterations the
variable $\boldsymbol{x}_{T}$ ends up in the convex set $\mathcal{C}$. The
pseudocode is provided in Appendix B.

SCG provides a tight $[(1-1/e)OPT-\epsilon]$ guarantee in expectation for the
last iterate $T$, with $\mathcal{O}(1/\epsilon^{3})$ stochastic gradient
computations [20]. But, similar to PGA [11], the expected guarantee of SCG
does not tell us how frequently bad solutions, with
$F(\boldsymbol{x}_{T})\\!<\\![(1-1/e)OPT-\epsilon]$ are returned.

Here, we answer the above question by providing a high-probability bound on
the value of the final solution, $F(\boldsymbol{x}_{T})$, returned by SCG. To
do so, instead of assuming bounded gradient error (Assumption 3), we use the
weaker assumption from [20] on the variance of the stochastic gradients:

######  Assumption 4.

Stochastic gradients have mean
$\mathbb{E}[\boldsymbol{g}_{t}]=\nabla{F}(\boldsymbol{x}_{t})$ and bounded
variance:

$\mathbb{E}_{z\sim p}\left[\left\lVert\boldsymbol{g}_{t}-\nabla
F(\boldsymbol{x})\right\rVert^{2}\right]\leq\sigma^{2}.$

Given Assumption 4, [20] showed that the variance of the momentum error, i.e.,
$\mathbb{E}[\left\lVert
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert^{2}]$, converges to
zero, as $t$ grows. However, this cannot be directly used to provide a high-
probability bound on the value of the final solution (as we require the
summation rather than the expectation of error terms). To address this,
instead of using the bound on the variance of the noisy gradient at step $t$,
we apply Chebyshev’s inequality to bound the probability of the noisy gradient
to be far away from its expectation. Then, we use a union bound on iterations
$t\\!\in\\![T\\!-\\!1]$ to get the next Lemma:

######  Lemma 1.

Consider the Stochastic Continuous Greedy algorithm, with
$\rho_{t}=\frac{4}{(t+8)^{2/3}}$. Under Assumptions 1, 2, 4, we have the
following high probability bound on the total variance of the noisy gradients
during $t\in\\{0,\cdots,T-1\\}$:

$\mathbb{P}\left(\sum_{t=0}^{T-1}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert^{2}\leq\delta^{2}\sum_{t=0}^{T-1}\frac{Q}{(t+9)^{2/3}}\right)\geq
1-\frac{T}{\delta^{2}},$ (17)

where
$\\!Q\\!\\!:=\\!\\!\max\\!\left\\{\\!\left\lVert\nabla\\!F(\boldsymbol{x}_{0})\\!-\\!\bar{\boldsymbol{g}}_{0}\right\rVert^{2}\\!9^{2/3}\\!,\\!16\sigma^{2}\\!\\!+\\!3L^{2}D^{2}\\!\right\\}$,
$\delta\\!\\!>\\!0$.

The proof can be found in Section A.4. Note that Lemma 1 does not rely on
taking the expectation of the function values or gradient approximations.
Equipped with Lemma 1, we derive the following lower-bound on
$F(\boldsymbol{x}_{T})$, by recursively bounding the distance of the iterates
to the optimum, $F(\boldsymbol{x}^{*})$.

######  Theorem 3.

Consider the Stochastic Continuous Greedy algorithm, with
$\rho_{t}=\frac{4}{(t+8)^{2/3}}$. Under Assumptions 1, 2, 4, we have that with
probability greater than $1-\frac{T}{\delta^{2}}$:

$\displaystyle F(\boldsymbol{x}_{T})$
$\displaystyle\geq(1-\frac{1}{e})F(\boldsymbol{x}^{*})-\delta\frac{2Q^{1/2}D}{T^{1/3}}-\frac{LD^{2}}{2T^{2}}$
$\displaystyle=(1-\frac{1}{e})OPT-\mathcal{O}(\frac{\delta}{T^{1/3}}),$ (18)

where
$\\!Q\\!\\!:=\\!\\!\max\\!\left\\{\\!\left\lVert\nabla\\!F(\boldsymbol{x}_{0})\\!-\\!\bar{\boldsymbol{g}}_{0}\right\rVert^{2}\\!9^{2/3}\\!,\\!16\sigma^{2}\\!\\!+\\!3L^{2}D^{2}\\!\right\\}$,
$\delta\\!\\!>\\!0$.

The proof can be found in Appendix A.4. Unlike our Theorem 1 for PGA, we see
that for any fixed confidence threshold $p$ implying
$\delta=\sqrt{\frac{T}{1-p}}$, our lower bound does not converge. This is a
direct result of the weakening of the noise assumption, since the gradient
noise may have bounded variance but not be bounded itself. Next, we provide an
improved bound when gradient noise is sub-Gaussian.

####  4.3.1 Improved Bound under Sub-Gaussian Noise

The weak assumptions on the noisy gradients (only bounded variance from
Assumption 4) make it difficult to apply typical Martingale or sub-Gaussian
inequalities. If instead, we assume that the noisy gradient approximations are
sub-Gaussian, we arrive at a surprisingly tight lower bound. First we describe
the sub-Gaussian noise assumption as follows:

######  Assumption 5.

Stochastic gradients have mean
$\mathbb{E}[\boldsymbol{g}_{t}]=\nabla{F}(\boldsymbol{x}_{t})$ and
$\hat{\boldsymbol{z}}_{t}:=\left\lVert\boldsymbol{g}_{t}\\!-\\!\nabla
F(\boldsymbol{x})\right\rVert$ is sub-Gaussian. I.e. for $\sigma>0$, we have:

$\mathbb{E}(e^{\lambda\hat{\boldsymbol{z}}_{t}^{2}})\leq
e^{\sigma^{2}\lambda^{2}/2}\quad\forall\lambda\in\mathbb{R}$ (19)

When using the SCG algorithm under this new assumption, we can derive the
following high probability bound:

######  Theorem 4.

Consider the Stochastic Continuous Greedy algorithm, with
$\rho_{t}=\frac{1}{t^{\alpha}}$ where $\alpha\in(0,1)$. Then under Assumptions
1, 2, 5, with probability greater than $1-\delta$:

$\displaystyle F(\boldsymbol{x}_{T})$
$\displaystyle\geq(1-\frac{1}{e})OPT-\frac{2DK\sigma\sqrt{\log(1/\delta)}}{T^{1/2}}$
(20)
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad-(\frac{4K+1}{2})\frac{LD^{2}}{T}$
$\displaystyle=(1-\frac{1}{e})OPT-\mathcal{O}\left(\frac{\sqrt{\log(1/\delta)}}{T^{1/2}}\right),$
(21)

where $K:=\frac{1}{1-\alpha}\Gamma\left(\frac{1}{1-\alpha}\right)$.

At a high level, the proof of Theorem 4 expands the momentum into a weighted
summation of gradient approximations, which after some careful manipulations
can be treated as a summation of sub-Gaussian variables. This is to our
knowledge the first such result for adaptive momentum optimization methods,
where the momentum can change over time. Notably, it is general enough to be
used even in the context of other smooth function classes. Adaptive momentum
enjoys some superior convergence and generalization properties [26]. See
section A.5 for the detailed proof.

Notably, the bound in Theorem 4 has a faster convergence rate than the
original expectation bound of [20], i.e.,
$(1-\frac{1}{e})OPT-\mathcal{O}(1/T^{1/3})$. The new bound suggests that for
certain well conditioned problems, SCG can achieve the same convergence rate
as SCG++. In our experiments in Sec. 5, we show that empirically the
distribution of solutions of SCG do converge when gradient noise is
(sub-)Gaussian.

###  4.4 Stochastic Continuous Greedy++

Finally, we analyze the worst-case performance of the Stochastic Continuous
Greedy++ (SCG++), which aims to speed up SCG, using a stochastic path-
integrated differential estimator (SPIDER) [8] for the gradient. SCG++ assumes
that the probability distribution of the random variable $\boldsymbol{z}$
depends on the variable $\boldsymbol{x}$ and may change during the
optimization. To obtain an unbiased gradient estimator
$\hat{\boldsymbol{g}}_{t}$ with a reduced variance, SCG++ uses a mini-batch of
samples to first get an unbiased estimate of the Hessian,
$\tilde{\nabla}^{2}_{t}$:

$\tilde{\nabla}^{2}_{t}=\frac{1}{|\mathcal{M}|}\sum_{(a,\boldsymbol{z}(a))\in\mathcal{M}}\tilde{\nabla}^{2}F(\boldsymbol{x}(a),\boldsymbol{z}(a)),$
(22)

where $a$ is selected uniformly at random from $[0,1]$, $\boldsymbol{z}(a)$ is
a random variable with probability distribution
$p(\boldsymbol{z}(a);\boldsymbol{x}(a))$,
$\boldsymbol{x}(a):=a\boldsymbol{x}_{t}+(1-a)\boldsymbol{x}_{t-1}$, and
$\mathcal{M}$ is a mini-batch containing $|\mathcal{M}|$ samples of random
tuple $(a,\boldsymbol{z}(a))$. Then, SCG++ uses the Hessian estimate to
recursively calculate unbiased estimates of the gradient, based on the
gradient differences $\tilde{\Delta}^{t}$:

$\tilde{\Delta}^{t}:=\tilde{\nabla}^{2}_{t}(\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}).$
(23)

A gradient estimate, $\hat{\boldsymbol{g}}_{t}$, with a reduced variance is
then calculated as the initial noisy gradient estimate plus the sum of all the
gradient differences up to time $t$:

$\displaystyle\hat{\boldsymbol{g}}_{t}$
$\displaystyle=\nabla\tilde{F}(\boldsymbol{x}_{0},\mathcal{M}_{0})+\sum_{i=1}^{i}\tilde{\Delta}^{t}.$
(24)

With the above gradient estimate $\hat{\boldsymbol{g}}_{t}$, SCG++ starts from
$\boldsymbol{x}_{0}=\boldsymbol{0}$, and at each iteration $t$, performs a
standard Frank-Wolfe step with step-size $\frac{1}{T}$. The full update
sequence is provided in Appendix B.

SCG++ converges in expectation to the same $[(1-1/e)OPT-\epsilon]$
approximation as SCG, but using only $\mathcal{O}(1/\epsilon^{2})$ stochastic
gradient evaluations and $\mathcal{O}(1/\epsilon)$ calls to the linear
optimization oracle [13]. However, similar to PGA and SCG, the expected
approximation guarantee of SCG++ does not show the probability of returning a
final solution that is much lower than the expected solution.

The analysis of SCG++ requires stronger assumptions than SCG. Besides the
monotone DR-submodularity of $F$ and the bounded diameter on $\mathcal{C}$
(Assumption 1), we use the same assumptions originally used to analyze SCG++
in [13]:

######  Assumption 6.

The function value at the origin is:

$F(\mathbf{0})\geq 0.$ (25)

######  Assumption 7.

The stochastic function $\tilde{F}(\boldsymbol{x},\boldsymbol{z})$, its
gradient, and its Hessian are bounded:

$\displaystyle\tilde{F}(\boldsymbol{x},\boldsymbol{z})$ $\displaystyle\leq B,$
(26)
$\displaystyle\left\lVert\nabla\tilde{F}(\boldsymbol{x},\boldsymbol{z})\right\rVert$
$\displaystyle\leq G_{\tilde{F}},$ (27)
$\displaystyle\left\lVert\nabla^{2}\tilde{F}(\boldsymbol{x},\boldsymbol{z})\right\rVert$
$\displaystyle\leq L_{\tilde{F}}.$ (28)

######  Assumption 8.

The function $\log p(\boldsymbol{z})$ has the following bounds on gradient and
Hessian:

$\displaystyle\mathbb{E}\left(\left\lVert\nabla\log
p(\boldsymbol{z})\right\rVert^{4}\right)\leq G_{p}^{4},$ (29)
$\displaystyle\mathbb{E}\left(\left\lVert\nabla^{2}\log
p(\boldsymbol{z})\right\rVert^{2}\right)\leq L_{p}^{2}.$ (30)

######  Assumption 9.

The Hessian of the stochastic function
$\tilde{F}(\boldsymbol{x},\boldsymbol{z})$ is $L_{2}$ Lipschitz continuous
with constant $L_{2,{\tilde{F}}}$. The Hessian of the function $\log
p(\boldsymbol{z})$ is $L_{2}$ Lipschitz continuous with constant $L_{2,p}$.

$\left\lVert\nabla^{2}\tilde{F}(\boldsymbol{x},\boldsymbol{z})-\nabla^{2}\tilde{F}(\boldsymbol{y},\boldsymbol{z})\right\rVert\leq
L_{2,{\tilde{F}}}\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert,$ (31)
$\left\lVert\nabla^{2}\log p(\boldsymbol{z})-\nabla^{2}\log
p(\boldsymbol{z})\right\rVert\leq
L_{2,p}\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert.$ (32)

Under the above assumptions and with $\mathcal{O}(\epsilon^{-1})$ calls to the
stochastic oracle per iteration, the variance of the gradient approximation
$\hat{\boldsymbol{g}}_{t}$ converges to zero [13]. Instead of directly upper
bounding variance as in [13], we use Chebyshev’s inequality to prevent any
expectations from appearing in our bound. Specifically we use the following
Lemma:

######  Lemma 2.

Given SCG++ under Assumptions 1,5-8, we have the following high probability
bound:

$\mathbb{P}\left(\sum_{t=0}^{T-1}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\hat{\boldsymbol{g}}_{t}\right\rVert^{2}\leq\delta^{2}\sum_{t=0}^{T-1}\frac{2L^{2}D^{2}}{t^{2}}\right)\leq
1-\frac{T}{\delta^{2}}.$ (33)

Lemma 2 allows us to directly bound the function value of last iterate of
SCG++, $F(\boldsymbol{x}_{T})$, with a high probability.

######  Theorem 5.

Consider applying SCG++ under Assumptions 1, 5-8. Then with probability
$1-\frac{T}{\delta^{2}}$ :

$\displaystyle F(\boldsymbol{x}_{T})$
$\displaystyle\geq(1-\frac{1}{e})F(\boldsymbol{x}^{*})-\delta\frac{LD^{2}}{T^{2}}-\frac{LD^{2}}{2T^{2}}$
$\displaystyle=(1-\frac{1}{e})OPT-\mathcal{O}(\frac{\delta}{T}).$ (34)

For a fixed probability threshold $p$ we get the next Corollary:

######  Corollary 2.

For $\delta\\!=\\!\sqrt{\frac{T}{1-p}}$, with probability greater than $p$, we
have:

$\displaystyle F(\boldsymbol{x}_{T})$
$\displaystyle\geq(1-\frac{1}{e})F(\boldsymbol{x}^{*})-\frac{LD^{2}}{\sqrt{1-p}}\frac{1}{\sqrt{T}}-\frac{LD^{2}}{2T^{2}}$
(35) $\displaystyle=(1-\frac{1}{e})OPT-\mathcal{O}(\frac{1}{\sqrt{T}})$ (36)

SCG++ makes $\mathcal{O}(T)$ queries to the stochastic gradient oracle per
iteration, and $K=T^{2}$ queries in total. Hence, with probability greater
than $p$ the bound in Corollary 2 becomes:

$F(\boldsymbol{x}_{T})\geq(1-\frac{1}{e})OPT-\mathcal{O}(\frac{1}{K^{1/4}}).$
(37)

For any fixed confidence interval $p$, the lower bound still converges to
$(1-\frac{1}{e})OPT$, albeit at a slower rate. However, we believe that a
tighter $1/\sqrt{K}$ high probability bound likely exists, as evident by our
experimental results in Sec. 5.

##  5 NUMERICAL RESULTS

In our experiments, we first show that bad solutions of PGA, boosted PGA SCG,
and SCG++ can be much worse than their expected values. Then, we validate our
proposed bounds on simulated and real-world datasets. In practice, due to
measurement errors or inexact function calculations, the function and thus the
gradient evaluations are often noisy. In such situations, our high probability
bounds can effectively quantify the worst-case performance and be utilized to
mitigate the risk of getting a bad solution.

###  5.1 Continuous Submodular Problems

First, we introduce three monotone continuous DR-submodular problems that we
use in our experiments.

##### Non-convex/non-concave quadratic programming (NQP).

NQP functions of the form
$f(\boldsymbol{x})=\frac{1}{2}\boldsymbol{x}^{T}\boldsymbol{H}\boldsymbol{x}+\boldsymbol{h}^{T}\boldsymbol{x}$
arise in many applications, including scheduling, inventory theory, and free
boundary problems [2]. When all off-diagonal entries of $\boldsymbol{H}$ are
non-positive, the NQP is submodular.

For our experiment, we randomly generate $n\\!=\\!100$ monotone DR-submodular
NQP functions, where each $\boldsymbol{H}\in\mathbb{R}^{n\times n}$ is a
symmetric matrix sampled uniformly from $[-100,0]$. We further generated a set
of $m\\!=\\!50$ linear constraints to construct the positive polytope
$\mathbb{P}=\\{\boldsymbol{x}\in\mathbb{R}^{n},\boldsymbol{Ax}\leq\boldsymbol{b},0\leq\boldsymbol{x}\leq\bar{\boldsymbol{u}}\\}$,
where entries in $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ are uniformly
sampled from $[0,1]$, $\bar{\boldsymbol{u}}=\boldsymbol{1}$, and
$\boldsymbol{b}=\boldsymbol{1}$. To make $f$ monotone, we ensure the gradient
of $f$ is non-negative by setting
$\boldsymbol{h}=-\boldsymbol{H}\bar{\boldsymbol{u}}$.

##### Optimal budget allocation with continuous assignments.

The budget allocation problem can be modeled as a bipartite graph $(S,T;W)$,
where $S$ is a set of advertising channels and $T$ is a set of customers. The
edge weight $p_{st}\in W$ represent the influence probability of channel $s$
on customer $t$. The objective is to maximize the total influence on the
customers by allocating the budget to the set of advertising channels. The
total influence on customer $t$ from all the channels can be model by a
monotone DR-submodular function $I_{t}(\boldsymbol{x})=1-\prod_{(s,t)\in
W}(1-p_{st})^{\boldsymbol{x}_{s}}$, where
$\boldsymbol{x}_{s}\in\mathbb{R}_{+}$ is the budget allocated to channel $s$.
Then for a set of $k$ advertisers, where
$\boldsymbol{x}^{i}\in\mathbb{R}_{+}^{S}$ is the budget allocation of the
$i^{th}$ advertiser and
$\boldsymbol{x}=[\boldsymbol{x}^{1},\cdots,\boldsymbol{x}^{k}]$, the overall
objective is

$\displaystyle
g(\boldsymbol{x})=\sum_{i=1}^{k}\alpha_{i}f(\boldsymbol{x}^{i}),\quad$
$\displaystyle\text{with}\quad f(\boldsymbol{x}^{i})=\sum_{t\in
T}I_{t}(\boldsymbol{x}^{i}),$ (38) $\displaystyle
0\leq\boldsymbol{x}^{i}\leq\bar{\boldsymbol{u}}^{i},\quad\forall 1\leq i\leq
k,$

where $\alpha_{i}$ is a constant weight coefficient and $\bar{u}^{i}$ is the
budget limit on each channel for the $i^{th}$ advertiser.

For a real-world instance of the budget allocation problem, we use the Yahoo!
Search Marketing Advertiser Bidding Data [1], which includes search keyword
phrases and the bids placed on them by online customers. The dataset consists
of 1,000 search keywords, 10,475 customers and 52,567 edges, where each edge
between a keyword and customer represents the customer has bid on the keyword.
A customer may bid on one phrase multiple times, and we use the frequency of a
(phrase, customer) pair to measure the influence probability of the phrase on
that customer. Additionally, we use the average bidding price across all the
bids in the dataset as the limit on the budget of all the advertisers.

###  5.2 Bad Solutions and High-probability Bounds

Figure 1:  The distribution of
$\min_{\tau\in[T]}F(\boldsymbol{x}_{\tau})-\mathbb{E}[F(\boldsymbol{x}_{\tau})]$
for PGA and boosted PGA, and
$F(\boldsymbol{x}_{T})-\mathbb{E}[F(\boldsymbol{x}_{T})]$ for SCG and SCG++ on
NQP, over 100 runs with $T=5$ (left), and $T=100$ (right). Bad solutions can
be much worse than the expected values.

(a) NQP, PGA

(b) NQP, Boosted PGA

(c) NQP, SCG

(d) NQP, SCG++

(e) Yahoo!, PGA

(f) Yahoo!, Boosted PGA

(g) Yahoo!, SCG

(h) Yahoo!, SCG++

(i) NQP, SCG

Figure 2: (a)-(h) Median, minimum, and 90% percentile of the normalized
solutions obtained by PGA, Boosted PGA, SCG, SCG++ compared to our bounds
provided in Theorems 1, 2, 4, 5. The results of PGA, Boosted PGA, SCG, SCG++
are averaged over 100 runs. (i) validating our bounds on a simple NQP example
where the constants are known.

Setup. We repeat every experiment 100 times, and use a step-size of $1e-4$,
$1e-2$ for PGA methods on NQP and Yahoo! respectively. We set the step-size to
$1/T$ for SCG and SCG++, and use batch size of $T$ for SCG++. For SCG, we use
$\frac{4}{(t+8)^{2/3}}$ as the momentum coefficient. For PGA methods, we
randomly initialize $\boldsymbol{x}_{0}\sim\mathcal{N}(0,1)$ from a Gaussian
distribution, and for SCG and SCG++ we initialize
$\boldsymbol{x}_{0}=\boldsymbol{0}$. Additionally, for PGA, boosted PGA, and
SCG experiments, we add a noise sampled from a Gaussian distribution with mean
0 and standard deviation proportional to the gradient norms normalized by its
dimensionality to the queried gradients. SCG++ uses noisy estimates of the
Hessian, hence we add a smaller Gaussian noise with mean 0 to the Hessian.

Bad solutions are far from expectation. First, we look at the solution of PGA,
SCG, and SCG++ on NQP, to see how far the solution may be from the expected
value. Note that when running each algorithm for $T$ iterates, PGA returns the
solution for a random iterate $\tau\in[T]$, and SCG, SCG++ return the solution
of the final iterate $T$. Fig. 1 shows the distribution of
$\min_{\tau\in[T]}F(\boldsymbol{x}_{\tau})$ for PGA, and
$F(\boldsymbol{x}_{T})$ for boosted PGA, SCG and SCG++ for $T=5$ (left), and
$T=100$ (right), over 100 runs. We see that bad solutions of the algorithms
can be much worse than their expected value. While more number of iterations
reduces the variance of SCG, we see that PGA and SCG++ have a very high
variance even after $T=100$ rounds (see Appendix C for more details). This
shows the insufficiency of the expected guarantees, and confirms the necessity
of high-probability analysis.

High-probability bounds. Next, we empirically confirm the validity of our
high-probability bounds. To do so, we first apply PGA, Boosted PGA, SCG, and
SCG++ to the continuous submodular problems discussed in Sec. 5.1. Then, we
compare the empirical results with our bounds in Theorems 1, 2, 4, 5.
Specifically, for each iteration $t$, we report the average utility up to $t$,
i.e. $\frac{1}{t}\sum_{i=1}^{t}F(\boldsymbol{x}_{i})$, for PGA; and the value
of $F(\boldsymbol{x}_{t})$ for Boosted PGA, SCG, and SCG++. To avoid the need
for calculating the exact scaling constants in Theorems (e.g. $L,D,K$, etc.)
and the true optimal value $OPT$ (which determines the asymptote), we fit a
line in the same form of the lower bound derived in Theorems 1, 2, 4, 5, to
the output of the algorithms. For each line, $c_{1}$ corresponds to fraction
of $OPT$ the bound is converging to, while $c_{2}$ scales the rate of
convergence depending on the problem-specific constants and desired confidence
threshold. Specifically, for each algorithm we fit a line of the form
$l(t)=c_{1}\\!-\\!\frac{c_{2}}{\sqrt{t}}$. Importantly, as SCG++ uses batch
size of $\mathcal{O}(T)$, an equivalent form of this fitted line is
$l(t)=c_{1}\\!-\\!\frac{c_{2}}{k^{1/4}}$, which is slower than the previous
two algorithms. For $c_{1}$, we use the same value for min, median, and
different percentiles, by taking the average of the $c_{1}$ values obtained
from the fitted lines for an algorithm on the same dataset. Using the above
$c_{1}$, we fit the curves again to get the corresponding $c_{2}$ for each
line.

Fig. 2(a)-(h) show the median, minimum, and 90% percentile of utility over the
course of training of each algorithm, compared to our predicted lower bounds.
We see that our bounds closely match these utility statistics for various
iterations of PGA, SCG, SCG++, and boosted PGA applied to different problems.
Since for each percentile level the bound is of the same order, the
_differences_ in percentiles decrease as well (e.g.
$\frac{a}{t^{1/2}}-\frac{b}{t^{1/2}}=\frac{c}{t^{1/2}}$). This effect can be
seen as the minimum returned value across runs approaches the median and 90%
returned values as the number of training iterations increase.

We further validate our bounds by adding a simple example where the constants
are known and running SCG on the problem. We construct a small NQP where
$\boldsymbol{H}\\!\in\\!\mathbb{R}^{5\times 5}$ is sampled uniformly from
$[-1,0]$. Hence, the Lipschitz constant
$L=\left\lVert\boldsymbol{H}\right\rVert_{2}\\!=\\!\sqrt{\lambda_{max}(\boldsymbol{H}^{T}\boldsymbol{H})}$.
We use linear constraints as Sec. 5.1 and set
$\boldsymbol{A}=[0.2,0.2,0.2,0.2,0.2]$. Thus, diameter
$D=\left\lVert\textbf{1}\right\rVert_{2}$. For a clipped Gaussian noise
$clip(\mathcal{N}(0,\sigma),-2\sigma,2\sigma)$ to queried gradients for SCG,
$M=2\sqrt{5}\sigma$. The optimal value for the problem is approximated by
taking the maximum value across 100 SCG runs with 5000 iterations. Using above
constants in Theorem 1, 2, 4, 5, Fig. 2(i) shows our predicted lower bound
with 99% confidence converges quickly to the minimum of the collected utility
trajectories.

##  6 CONCLUSION

We derived the first high probability analysis of the existing methods for
stochastic Continuous Submodular Function (CSF) maximization, namely PGA,
boosted PGA, SCG, and SCG++. When assumptions on the stochasticity of
gradients are strong enough, we showed that even in the worst case the
solutions of the algorithms are lower bounded by a function converging to
their expected guarantees. Specifically, with $K$ stochastic gradient
computations, we demonstrated that PGA converges with rate of
$O(\frac{1}{\sqrt{K}})$ to the expected $OPT/2$ and the boosted version at the
same rate to $(1-1/e)OPT$. For SCG and SCG++, we showed that both algorithms
converge at rates of at least $O(\frac{\delta}{K^{\frac{1}{3}}})$ and
$O(\frac{\delta}{K^{\frac{1}{2}}})$ to the expected $(1-1/e)OPT$, where
$\delta$ depends on the confidence threshold. Besides, under the sub-Gaussian
assumption on the gradient noise, we provided an improved lower bound of
$O(\frac{1}{\sqrt{K}})$ for the convergence of SCG, that is faster than the
existing convergence rate to the expected solution. Our results allows
characterizing worst and best-case performance of CSF maximization in
stochastic settings, and mitigating the risk of getting a bad solution.

## Acknowledgment

BM was supported the National Science Foundation CAREER Award 2146492.

## References

  * [1] Yahoo! advertisement data: https://webscope.sandbox.yahoo.com/catalog.php?datatype=a.
  * [2] An Bian, Kfir Levy, Andreas Krause, and Joachim M Buhmann.  Continuous dr-submodular maximization: Structure and algorithms.  Advances in Neural Information Processing Systems, 30, 2017.
  * [3] Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause.  Guaranteed non-convex optimization: Submodular maximization over continuous domains.  In Artificial Intelligence and Statistics, pages 111–120. PMLR, 2017.
  * [4] Chandra Chekuri, TS Jayram, and Jan Vondrák.  On multiplicative weight updates for concave and submodular function maximization.  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 201–210, 2015.
  * [5] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  SIAM Journal on Computing, 43(6):1831–1879, 2014.
  * [6] Fan Chung and Linyuan Lu.  Concentration inequalities and martingale inequalities: a survey.  Internet mathematics, 3(1):79–127, 2006.
  * [7] Reza Eghbali and Maryam Fazel.  Designing smoothing functions for improved worst-case competitive ratio in online optimization.  Advances in Neural Information Processing Systems, 29, 2016.
  * [8] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang.  Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator.  Advances in Neural Information Processing Systems, 31, 2018.
  * [9] Daniel Golovin, Andreas Krause, and Matthew Streeter.  Online submodular maximization under a matroid constraint with application to learning assignments.  arXiv preprint arXiv:1407.1082, 2014.
  * [10] Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa.  Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent.  arXiv preprint arXiv:1909.00843, 2019.
  * [11] S. Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi.  Gradient methods for submodular maximization.  CoRR, abs/1708.03949, 2017.
  * [12] Stefanie Jegelka and Jeff A. Bilmes.  Submodularity beyond submodular energies: Coupling edges in graph cuts.  CVPR 2011, pages 1897–1904, 2011.
  * [13] Amin Karbasi, Hamed Hassani, Aryan Mokhtari, and Zebang Shen.  Stochastic continuous greedy ++: When upper and lower bounds match.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [14] David Kempe, Jon M. Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In KDD ’03, 2003.
  * [15] Andreas Krause, Carlos Guestrin, Anupam Gupta, and Jon Kleinberg.  Near-optimal sensor placements: Maximizing information while minimizing communication cost.  In Proceedings of the 5th International Conference on Information Processing in Sensor Networks, page 2–10, 2006.
  * [16] Xiaoyu Li and Francesco Orabona.  A high probability analysis of adaptive sgd with momentum.  In Workshop on Beyond First Order Methods in ML Systems at ICML’20, 2020.
  * [17] Hui-Ching Lin and Jeff A. Bilmes.  A class of submodular functions for document summarization.  In ACL, 2011.
  * [18] László Lovász.  Submodular functions and convexity.  In Mathematical programming: The state of the art, Bonn, pages 235–257, 1982.
  * [19] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani.  Adwords and generalized online matching.  Journal of the ACM (JACM), 54(5):22–es, 2007.
  * [20] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi.  Conditional gradient method for stochastic submodular maximization: Closing the gap.  In International Conference on Artificial Intelligence and Statistics, pages 1886–1895. PMLR, 2018.
  * [21] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi.  Stochastic conditional gradient methods: From convex minimization to submodular maximization.  Journal of machine learning research, 2020.
  * [22] Kazuo Murota.  Discrete convex analysis.  Mathematical Programming, 83(1):313–371, 1998.
  * [23] Mukund Narasimhan, Nebojsa Jojic, and Jeff A Bilmes.  Q-clustering.  In Y. Weiss, B. Schölkopf, and J. Platt, editors, Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005.
  * [24] Tasuku Soma and Yuichi Yoshida.  Non-monotone dr-submodular function maximization.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
  * [25] Matthew Staib and Stefanie Jegelka.  Robust budget allocation via continuous submodular functions.  In International Conference on Machine Learning, pages 3230–3240. PMLR, 2017.
  * [26] Tao Sun, Huaming Ling, Zuoqiang Shi, Dongsheng Li, and Bao Wang.  Training deep neural networks with adaptive momentum inspired by the quadratic optimization.  arXiv preprint arXiv:2110.09057, 2021.
  * [27] Laurence A Wolsey.  An analysis of the greedy algorithm for the submodular set covering problem.  Combinatorica, 2(4):385–393, 1982.
  * [28] Haixiang Zhang, Zeyu Zheng, and Javad Lavaei.  Stochastic $L^{\natural}$-convex function minimization.  Advances in Neural Information Processing Systems, 34:13004–13018, 2021.
  * [29] Lijun Zhang, Tianbao Yang, and Rong Jin.  Empirical risk minimization for stochastic convex optimization: $\mathcal{O}(1/n)$ and $\mathcal{O}(1/n^{2})$-type of risk bounds.  In Conference on Learning Theory, pages 1954–1979. PMLR, 2017.
  * [30] Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang.  Stochastic continuous submodular maximization: Boosting via non-oblivious function.  In International Conference on Machine Learning, pages 26116–26134. PMLR, 2022.

##  Appendix A ADDITIONAL PROOFS

###  A.1 Background on Martingale Sequences

We first provide a brief review on Martingale sequences, which can be found in
any standard text on stochastic processes such as [6]. Given probability space
$\Omega$ and probability distribution p, we first denote $\mathcal{F}$ as a
$\sigma$-field on $\Omega$. We also denote the filtration $\mathbb{F}$ as a
nested sequence of $\sigma$-subfields:

$\mathbb{F}:=\\{\mathcal{F}_{t}\\}_{t\leq n}\quad
s.t.\quad\mathcal{F}_{0}\subset\mathcal{F}_{1}\subset\dots\subset\mathcal{F}_{n}=\mathcal{F}$
(39)

We say that a sequence of random variables
$\\{X_{t}\\}_{t=1}^{n}:=\\{X_{1},\dots,X_{n}\\}$ is Martingale with respect to
filtration $\mathbb{F}$ if the following properties hold:

$\displaystyle\mathbb{E}[|X_{t}|]\leq\infty$
$\displaystyle\mathbb{E}[X_{t+1}|\mathcal{F}_{t}]=X_{t}$ (40)

In other words, given past observations, the next random variable in the
sequence is expected to take on the value of the previous one.

A Martingale _difference_ sequence $\\{Y_{t}\\}_{t\leq n}$ with respect to
filtration $\mathbb{F}$ is defined as having a conditional expectation of zero

$\mathbb{E}[Y_{t+1}|\mathcal{F}_{t}]=0$ (41)

It is easy to see that given a Martingale sequence $\\{Y_{t}\\}_{t=1}^{n}$,
one can construct a difference sequence by setting $Y_{t}=X_{t}-X_{t-1}$.

Lastly, we say a Martingale is $c$-lipschitz if $\forall t$

$|X_{t}-X_{t-1}|\leq c_{t}$ (42)

This is equivalent to saying all random variables $Y_{t}$ in the corresponding
Martingale difference sequence are bounded.

###  A.2 Proof of Theorem 1

We first make use of an alternative form of the usual Azuma-Hoeffding
inequality from [6]:

######  Theorem 6.

(Chung and Lu 2006, theorem 5.2) If martingale X is c-lipschitz, then

$\mathbb{P}\left(|X-\mathbb{E}(X)|\leq\sqrt{2\sum_{i}c_{i}^{2}\log(1/\delta)}\right)\geq
1-\delta$ (43)

Next, we prove theorem 1.

###### Proof.

Submodularity guarantees that for any two points $x,y\in\mathcal{X}$:

$\nabla F(\boldsymbol{x})\geq\nabla F(\boldsymbol{y})\>\text{for
all}\>\boldsymbol{x}\leq\boldsymbol{y}$ (44)

Using eq 7.2 from Hassani et al. 2017 in [11] we know that for any two points
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{X}$ we have the relation

$\displaystyle F(\boldsymbol{y})-2F(\boldsymbol{x})\leq\left<\nabla
F(\boldsymbol{x}),\boldsymbol{y}-\boldsymbol{x}\right>$ (45)

This allows us to proceed with a derivation of convergence similar to [29] for
SGD: First replace our $\boldsymbol{y},\boldsymbol{x}$ in the previous
inequality with $\boldsymbol{x}^{*}$ (the maximizing input to our function)
and $\boldsymbol{x}_{t}$ (the $t$-th iteration of our algorithm) respectively.
Then letting $\hat{\boldsymbol{z}}_{t}:=\boldsymbol{g}_{t}-\nabla
F(\boldsymbol{x}_{t})$ denote the random difference between the true and noisy
gradient we have

$\displaystyle F(\boldsymbol{x}^{*})-2F(\boldsymbol{x}_{t})$
$\displaystyle\leq\left<\nabla
F(\boldsymbol{x}_{t}),\boldsymbol{x}^{*}-\boldsymbol{x}_{t}\right>$
$\displaystyle=\left<\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\boldsymbol{g}_{t}\right>-\left<\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\hat{\boldsymbol{z}}_{t}\right>$
$\displaystyle\leq\frac{1}{\eta_{t}}\left<\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\boldsymbol{x}^{\prime}_{t+1}-\boldsymbol{x}_{t}\right>-\left<\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\hat{\boldsymbol{z}}_{t}\right>$
(46)

In the second inequality we use the definition of our gradient step (before
projection)
$\boldsymbol{x}^{\prime}_{t+1}=\boldsymbol{x}_{t}+\eta_{t}\boldsymbol{g}_{t}$.
Next, through some algebra we get

$\displaystyle F(\boldsymbol{x}^{*})-2F(\boldsymbol{x}_{t})$
$\displaystyle\leq\frac{1}{2\eta_{t}}(\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{\prime}_{t+1}\right\rVert_{2}^{2}+\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert_{2}^{2}-\left\lVert\boldsymbol{x}^{\prime}_{t+1}-\boldsymbol{x}^{*}\right\rVert_{2}^{2})-\left<\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\hat{\boldsymbol{z}}_{t}\right>$
$\displaystyle\leq\frac{1}{2\eta_{t}}(\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{\prime}_{t+1}\right\rVert_{2}^{2}+\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert_{2}^{2}-\left\lVert\boldsymbol{x}_{t+1}-\boldsymbol{x}^{*}\right\rVert_{2}^{2})-\left<\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\hat{\boldsymbol{z}}_{t}\right>$
(47)

By the property of euclidean projections we know
$\left\lVert\boldsymbol{x}_{t+1}-\boldsymbol{x}^{*}\right\rVert\leq\left\lVert\boldsymbol{x}^{\prime}_{t+1}-\boldsymbol{x}^{*}\right\rVert$
which gives us the second line above. Next we use our gradient step equation
and lipschitz-smoothness assumption to get:

$\displaystyle F(\boldsymbol{x}^{*})-2F(\boldsymbol{x}_{t})$
$\displaystyle\leq\frac{\eta_{t}}{2}\left\lVert\boldsymbol{g}_{t}\right\rVert_{2}^{2}+\frac{1}{2\eta_{t}}(\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert_{2}^{2}-\left\lVert\boldsymbol{x}_{t+1}-\boldsymbol{x}^{*}\right\rVert_{2}^{2})-\left<\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\hat{\boldsymbol{z}}_{t}\right>$
$\displaystyle\leq\frac{\eta_{t}(L+M)^{2}}{2}+\frac{1}{2\eta_{t}}(\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert_{2}^{2}-\left\lVert\boldsymbol{x}_{t+1}-\boldsymbol{x}^{*}\right\rVert_{2}^{2})-\left<\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\hat{\boldsymbol{z}}_{t}\right>$
(48)

We let
$\Delta_{t}\triangleq\left<\boldsymbol{x}_{t}-\boldsymbol{x}^{*},\hat{\boldsymbol{z}}_{t}\right>$,
and $\eta_{t}=\frac{2}{\sqrt{t}}$ to get

$\displaystyle F(\boldsymbol{x}^{*})-2F(\boldsymbol{x}_{t})$
$\displaystyle\leq\frac{(L+M)^{2}}{\sqrt{t}}+\frac{\sqrt{t}}{4}(\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert_{2}^{2}-\left\lVert\boldsymbol{x}_{t+1}-\boldsymbol{x}^{*}\right\rVert_{2}^{2})+\Delta_{t}$
$\displaystyle\leq\frac{(L+M)^{2}}{\sqrt{t}}+\frac{\sqrt{T}}{4}(\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert_{2}^{2}-\left\lVert\boldsymbol{x}_{t+1}-\boldsymbol{x}^{*}\right\rVert_{2}^{2})+\Delta_{t}$
(49)

If combine the inequalities for each $\boldsymbol{x}_{t}$ and divide by T we
have:

$F(\boldsymbol{x}^{*})-(\frac{2}{T})\sum_{t=1}^{T}F(\boldsymbol{x}_{t})\leq\frac{1}{T}\left(\sum_{t=1}^{T}\frac{1}{\sqrt{t}}(L+M)^{2}+\frac{\sqrt{T}}{4}\left\lVert\boldsymbol{x}^{*}-\boldsymbol{x}_{1}\right\rVert_{2}^{2}+\sum_{t=1}^{T}\Delta_{t}\right)\\\
$

Using the fact that $\sum_{t=1}^{T}\frac{1}{\sqrt{t}}\leq 2\sqrt{T}$ we
simplify to

$\displaystyle
F(\boldsymbol{x}^{*})-(\frac{2}{T})\sum_{t=1}^{T}F(\boldsymbol{x}_{t})$
$\displaystyle\leq\frac{1}{T}\left(2\sqrt{T}(L+M)^{2}+\frac{\sqrt{T}}{4}\left\lVert\boldsymbol{x}^{*}-\boldsymbol{x}_{1}\right\rVert_{2}^{2}+\sum_{t=1}^{T}\Delta_{t}\right)$
$\displaystyle=\frac{2(L+M)^{2}}{\sqrt{T}}+\frac{\left\lVert\boldsymbol{x}^{*}-\boldsymbol{x}_{1}\right\rVert_{2}^{2}}{4\sqrt{T}}+\frac{1}{T}\sum_{t=1}^{T}\Delta_{t}$
(50)

Rearranging this inequality we see

$\displaystyle\frac{1}{2}OPT-\frac{1}{T}\sum_{t=1}^{T}F(\boldsymbol{x}_{t})\leq\frac{(L+M)^{2}}{\sqrt{T}}+\frac{\left\lVert\boldsymbol{x}^{*}-\boldsymbol{x}_{1}\right\rVert_{2}^{2}}{8\sqrt{T}}+\frac{1}{2T}\sum_{t=1}^{T}\Delta_{t}$
(51)

Let $\Delta^{\prime}_{t}\triangleq\frac{1}{2}\Delta_{t}$ so we can simplify to

$\displaystyle\frac{1}{2}OPT-\frac{1}{T}\sum_{t=1}^{T}F(\boldsymbol{x}_{t})\leq\frac{1}{\sqrt{T}}\left(\frac{8(L+M)^{2}+\left\lVert\boldsymbol{x}^{*}-\boldsymbol{x}_{1}\right\rVert_{2}^{2}}{8}\right)+\frac{1}{T}\sum_{t=1}^{T}\Delta^{\prime}_{t}$
(52)

Our next step is to use the Azuma-Hoeffding inequality to bound
$\frac{1}{T}\sum_{t=1}^{T}\Delta^{\prime}_{t}$. If we can show that
$\\{\Delta^{\prime}_{t}\\}_{T}$ is a bounded martingale difference sequence
with zero expectation, then we know by Theorem 6 with probability $1-\delta$:

$\displaystyle|\sum_{t=1}^{T}\Delta^{\prime}_{t}|\lesssim\sqrt{T\log(1/\delta)}$
(53)

Expanding $\mathbb{E}(\Delta^{\prime}_{t})$ we see that because
$\boldsymbol{x}_{t}-\boldsymbol{x}^{*}$ is independent of the gradient error
$\hat{\boldsymbol{z}}_{t}$ we have

$\displaystyle\mathbb{E}(\Delta^{\prime}_{t})$
$\displaystyle=\mathbb{E}\left(\frac{1}{2}\left<\boldsymbol{x}_{t}-\boldsymbol{x}^{*},\hat{\boldsymbol{z}}_{t}\right>\right)=\frac{1}{2}\left<\mathbb{E}(\boldsymbol{x}_{t}-\boldsymbol{x}^{*}),\mathbb{E}(\hat{\boldsymbol{z}}_{t})\right>=0$
(54)

Similarly, we can use triangle inequalities and our assumptions to bound
$\left\lVert\Delta^{\prime}_{t}\right\rVert$ by a constant

$\displaystyle\left\lVert\Delta^{\prime}_{t}\right\rVert\leq\frac{1}{2}\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert\left\lVert\hat{\boldsymbol{z}}_{t}\right\rVert\leq\frac{DM}{2}$
(55)

Recall D is the maximum distance between any two points in our set
$\mathcal{C}$. Therefore we have

$\mathbb{P}\left(|X-\mathbb{E}(X)|\leq DM\sqrt{T\log(1/\delta)/2}\right)\geq
1-\delta$ (56)

Therefore we have a martingale difference sequence which implies with
probability $1-\delta$

$\displaystyle\frac{1}{2}OPT-\frac{1}{T}\sum_{t=1}^{T}F(\boldsymbol{x}_{t})$
$\displaystyle\leq\frac{1}{\sqrt{T}}\left(\frac{8(L+M)^{2}+D^{2}}{8}\right)+\sqrt{\frac{\log(\frac{1}{\delta})}{2T}}DM$
$\displaystyle=O(\frac{1}{\sqrt{T}})$ (57)

∎

###  A.3 Proof of Theorem 2

In this section, we demonstrate how to adapt the PGA bound in theorem 1 to the
Boosted PGA setting. For the proof we use the slightly more general form of
the non-oblivious function in [30] which also works for weakly submodular
functions with parameter $\gamma$:

$\displaystyle
F^{\prime}(\boldsymbol{x}):=\int_{0}^{1}\frac{e^{\gamma(s-1)}}{s}F(s*\boldsymbol{x})ds$
(58) $\displaystyle\nabla
F^{\prime}(\boldsymbol{x}):=\int_{0}^{1}e^{\gamma(s-1)}F(s*\boldsymbol{x})ds$
(59)

The noisy gradient estimate of this auxiliary function is now:

$\displaystyle\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t}):=\frac{1-e^{-\gamma}}{\gamma}\nabla\tilde{F}(s_{t}*\boldsymbol{x}_{t}).$
(60)

Here $s_{t}$ is independently sampled from a distribution with cdf:
$\mathbb{P}(\boldsymbol{S}\leq
s)=\int_{0}^{s}\frac{\gamma^{\gamma(u-1)}}{1-e^{-\gamma}}\mathds{1}(u\in[0,1])du$,
where $\mathds{1}$ is the indicator function.
We now begin with a slightly stricter version of proposition 1 from [30].

######  Lemma 3 (Proposition 1, Zhang et al. 2022).

If $z_{t}$ is sampled according to the distribution in Eq. (60), then given
Assumptions 1,2,3 are satisfied (i.e. Lipschitz-smooth function along with
bounded domain and gradient noise), we have

$\displaystyle\mathbb{E}\left(\frac{1-e^{-\gamma}}{\gamma}\nabla\tilde{F}(s_{t}*\boldsymbol{x}_{t})\right)=\nabla
F^{\prime}(\boldsymbol{x})$ (61) $\displaystyle\left\lVert\nabla
F^{\prime}(\boldsymbol{x})-\nabla\tilde{F}^{\prime}(\boldsymbol{x})\right\rVert^{2}\leq
M_{\gamma}^{2}$ (62)

where $M_{\gamma}:=(M+2LD)\left(\frac{1-e^{-\gamma}}{\gamma}\right)$.

The first equality statement is unchanged from the original proposition, while
the second inequality is modified to bound the squared norm error instead of
the variance. We provide a short proof of the second inequality below:

###### Proof.

$\displaystyle\left\lVert\nabla
F^{\prime}(\boldsymbol{x})-\nabla\tilde{F}^{\prime}(\boldsymbol{x})\right\rVert$
$\displaystyle\leq\left\lVert\frac{1-e^{-\gamma}}{\gamma}(\nabla\tilde{F}(z*\boldsymbol{x})-\nabla
F(z*\boldsymbol{x}))\right\rVert+\left\lVert\frac{1-e^{-\gamma}}{\gamma}\nabla
F(z*\boldsymbol{x})-\nabla F^{\prime}(x)\right\rVert$
$\displaystyle\leq\left(\frac{1-e^{-\gamma}}{\gamma}\right)M+\left\lVert\frac{1-e^{-\gamma}}{\gamma}\nabla
F(z*\boldsymbol{x})-\nabla F^{\prime}(x)\right\rVert$ (63)

We use the definition of $\nabla\tilde{F}^{\prime}(\boldsymbol{x})$, as well
as the triangle inequality in the first step. In the second step, we use the
assumption that the noise of our gradient oracle is bounded by $M$. Finally to
bound the second term:

$\displaystyle\left\lVert\frac{1-e^{-\gamma}}{\gamma}\nabla
F(z*\boldsymbol{x})-\nabla F^{\prime}(x))\right\rVert$
$\displaystyle=\left\lVert\int_{0}^{1}e^{\gamma(u-1)}(\nabla
F(z*\boldsymbol{x})-\nabla F(u*\boldsymbol{x})du\right\rVert$
$\displaystyle\leq\left(\int_{0}^{1}e^{\gamma(u-1)}|z-u|L\left\lVert\boldsymbol{x}\right\rVert|\right)$
$\displaystyle\leq
2LD\left(\int_{0}^{1}e^{\gamma(u-1)}du\right)=2LD\left(\frac{1-e^{-\gamma}}{\gamma}\right)$
(64)

We use the Lipschitz smoothness constraint and Cauchy-Schwarz in the first
inequality, and $|z-u|<2$ in the second. ∎

Now equipped with Lemma 3, we can proceed using the same proof structure as in
Theorem 1:

###### Proof.

Starting from $\langle\boldsymbol{y}-\boldsymbol{x},\nabla
F^{\prime}(\boldsymbol{x})\rangle\geq(1-e^{-\gamma})F(\boldsymbol{y})-F(\boldsymbol{x})$
evaluated at $\boldsymbol{y}=\boldsymbol{x}^{*}$, we can show using steps
analogous to sections A.2, A.2 and A.2 the following inequality:

$\displaystyle(1-e^{-\gamma})F(\boldsymbol{y})-F(\boldsymbol{x})$
$\displaystyle\leq\frac{\eta_{t}}{2}\left\lVert\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t})\right\rVert^{2}+\frac{1}{2\eta_{t}}\left(\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert^{2}-\left\lVert\boldsymbol{x}_{t+1}-\boldsymbol{x}^{*}\right\rVert^{2}\right)-\langle\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t})-\nabla
F^{\prime}(\boldsymbol{x}_{t})\rangle$
$\displaystyle\leq\frac{\eta_{t}}{2}(L_{\gamma}D+M_{\gamma})^{2}+\frac{1}{2\eta_{t}}\left(\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\right\rVert^{2}-\left\lVert\boldsymbol{x}_{t+1}-\boldsymbol{x}^{*}\right\rVert^{2}\right)-\langle\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t})-\nabla
F^{\prime}(\boldsymbol{x}_{t})\rangle$ (65)

From [30] we know that $F^{\prime}$ is $L_{\gamma}$-smooth with
$L_{\gamma}=L\frac{\gamma+e^{-\gamma}-1}{\gamma^{2}}$, giving us the second
inequality above. Using $\eta_{t}=1/\sqrt{t}$ and applying the bound
iteratively produces the parallel equation to eq. 51:

$\displaystyle(1-e^{-\gamma})OPT-\frac{1}{T}F(\boldsymbol{x}_{t})\leq\frac{1}{\sqrt{T}}(L_{\gamma}D+M_{\gamma})^{2}+\frac{\left\lVert\boldsymbol{x}^{*}-\boldsymbol{x}_{1}\right\rVert^{2}}{8\sqrt{T}}+\frac{1}{2T}\sum_{t=1}^{T}\langle\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t})-\nabla
F^{\prime}(\boldsymbol{x}_{t})\rangle$ (66)

From Lemma 3 we can treat the summation of
$\langle\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t})-\nabla
F^{\prime}(\boldsymbol{x}_{t})\rangle$ terms as a c-lipschitz Martingale with
constant:

$|\langle\boldsymbol{x}^{*}-\boldsymbol{x}_{t},\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t})-\nabla
F^{\prime}(\boldsymbol{x}_{t})\rangle|\leq\left\lVert\boldsymbol{x}^{*}-\boldsymbol{x}_{t}\right\rVert\left\lVert\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t})-\nabla
F^{\prime}(\boldsymbol{x}_{t})\right\rVert\leq DM_{\gamma}=:c$ (67)

Therefore, the analogous bound to theorem 1 for non-oblivious PGA is:

$(1-e^{-\gamma})OPT-\frac{1}{T}F(\boldsymbol{x}_{t})\leq\frac{1}{\sqrt{T}}\left(\frac{8(L_{\gamma}D+M_{\gamma})^{2}+D^{2}}{8}\right)+\sqrt{\frac{\log(\frac{1}{\delta})}{2T}}DM_{\gamma}$
(68)

With probability $p>1-\delta$. By substituting $\gamma=1$, we recover the
bound for the fully submodular setting.

∎

###  A.4 Proof of Theorem 3

We first make use the following lemma from Mokhtari et al. which bounds the
variance in momentum error:

######  Lemma 4.

(Mokhtari et al. 2018, Lemma 2) Given a momentum parameter
$p_{t}=\frac{4}{(t+8)^{2/3}}$, the gradient estimates
$\bar{\boldsymbol{g}}_{t}$ have the following property:

$\mathbb{E}\left[\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert^{2}\right]\leq\frac{Q}{(t+9)^{2/3}}$

We note that as a corollary to this lemma, the Chebyshev inequality gives us
the following high probability bound:

$\mathbb{P}\left(\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert\geq\delta\sqrt{\frac{Q}{(t+9)^{2/3}}}\right)\leq\frac{1}{\delta^{2}}$
(69)

Squaring both terms inside the condition:

$\mathbb{P}\left(\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert^{2}\geq\delta^{2}\frac{Q}{(t+9)^{2/3}}\right)\leq\frac{1}{\delta^{2}}$
(70)

Now we are ready to begin the proof of theorem 3.

###### Proof.

Starting with the following inequality derived in [20] (Mokhtari et al. 2018,
eq. 20) we have:

$F(\boldsymbol{x}_{t+1})-F(\boldsymbol{x}_{t})\geq\frac{1}{T}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{t}))-\frac{LD^{2}}{2T^{2}}-\frac{1}{2T}(4\beta_{t}D^{2}+\frac{\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert^{2}}{\beta_{t}})$

Instead of taking the expectations of both sides as in [20], we immediately
apply the inequality recursively from $t=0,1,\dots,T-1$ to get

$F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{T})\leq(1-\frac{1}{T})^{T}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{0}))+\sum_{t=0}^{T-1}\frac{1}{2T}\left[4\beta_{t}D^{2}+\frac{\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert^{2}}{\beta_{t}}\right]+\frac{LD^{2}}{2T^{2}}$

Looking at the term $\sum_{t=0}^{T-1}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert^{2}$, we can use
the union bound as follows:

$\mathbb{P}(\sum_{t=0}^{T-1}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert^{2}\geq\delta^{2}\sum_{t=0}^{T-1}\frac{Q}{(t+9)^{2/3}})\leq\sum_{t}\frac{1}{\delta^{2}}=\frac{T}{\delta^{2}}$

Therefore we know that with probability at least $1-\frac{T}{\delta^{2}}$ that
the inequality in the opposite direction is true.

Then choosing $\beta_{t}=\frac{\delta\sqrt{Q}}{2D(t+9)^{1/3}}$, we get the
upper bound:

$F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{T})\leq\frac{1}{e}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{0}))+\sum_{t=0}^{T-1}\delta\frac{2Q^{1/2}D}{(t+9)^{1/3}T}+\frac{LD^{2}}{2T^{2}}$
(71)

Therefore with probability greater than $1-\frac{T}{\delta^{2}}$ we have the
following bound:

$F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{T})\leq\frac{1}{e}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{0}))+\delta\frac{2Q^{1/2}D}{T^{1/3}}+\frac{LD^{2}}{2T^{2}}$
(72)

Some more manipulation, and we have with probability greater than
$1-\frac{T}{\delta^{2}}$

$F(\boldsymbol{x}_{T})\geq(1-\frac{1}{e})F(\boldsymbol{x}^{*})-\delta\frac{2Q^{1/2}D}{T^{1/3}}-\frac{LD^{2}}{2T^{2}}$
(73)

∎

###  A.5 Proof of Theorem 4 (Stronger SCG Bound)

Before verifying theorem 4, we first provide the following lemma, which gives
a high probability bound for the sum of momentum errors:

######  Lemma 5.

Given i.i.d. errors $\left\lVert\nabla
F(\boldsymbol{x}_{t})-\boldsymbol{g}_{t}\right\rVert$ that are each sub-
Guassian with parameter $\sigma$, and momentum
$\bar{\boldsymbol{g}}_{t}=(1-\rho_{t})\bar{\boldsymbol{g}}_{t-1}+\rho_{t}\nabla\tilde{F}(\boldsymbol{x}_{t},\boldsymbol{z}_{t})$
with parameter of the form $\rho_{t}=\frac{1}{t^{\alpha}}$ and
$\alpha\in(0,1)$, then with probability greater than $1-\delta$

$\sum_{t=1}^{T}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert\leq\sqrt{2K^{2}\sigma^{2}T\log(1/\delta)}+LDK$
(74)

Where $K:=\frac{1}{1-\alpha}\Gamma(\frac{1}{1-\alpha})$

The cumulative error bound in lemma 5 is to our knowledge the first such
result for adaptive momentum optimization methods (i.e. the momentum can
change over time). Notably, it is general enough to be used even in the
context of other smooth function classes. Recently, [26] showed adaptive
momentum enjoys some superior convergence and generalization properties, and
hence our lemma is of independent interest. See section A.6 for the proof of
this lemma.

Next, we show a tighter high probability bound on the final iterate of the SCG
algorithm in theorem 4.

###### Proof.

Using the smoothness of F and boundedness of $x\in\mathcal{C}$, Hassani et al.
2017 showed that

$F(\boldsymbol{x}_{t+1})-F(\boldsymbol{x}_{t})\geq\frac{1}{T}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{t}))-\frac{LD^{2}}{2T^{2}}+\frac{1}{T}\left<\boldsymbol{v}_{t}-\boldsymbol{x}^{*},\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right>$ (75)

The Cauchy-Schwarz inequality allows us to bound the last term by

$\displaystyle\frac{1}{T}\left<\boldsymbol{v}_{t}-\boldsymbol{x}^{*},\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right>\geq-\frac{1}{T}\left\lVert\boldsymbol{v}_{t}-\boldsymbol{x}^{*}\right\rVert\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert\geq-\frac{2D}{T}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert$ (76)

Substituting this bound and rearranging terms we have

$F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{t+1})\leq(1-\frac{1}{T})(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{t}))+\frac{2D}{T}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert+\frac{LD^{2}}{2T^{2}}$
(77)

Applying this inequality recursively for $t=0,\dots,T-1$ we have

$\displaystyle
F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{T})\leq(1-\frac{1}{T})^{T}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{0}))+\frac{2D}{T}\sum_{t=0}^{T-1}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert+\frac{LD^{2}}{2T}$
(78)

Using a momentum term of $\rho_{t}=\frac{1}{t^{1/2}}$ for lemma 5 means that
$\alpha=0.5$ and hence $K=2$. Directly substituting this inequality into eq.
78 gives us

$\displaystyle F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{T})$
$\displaystyle\leq(1-\frac{1}{T})^{T}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{0}))+\frac{2D}{T}\left[\sqrt{2K^{2}\sigma^{2}T\log(1/\delta)}+LDK\right]+\frac{LD^{2}}{2T}$
$\displaystyle\leq\frac{1}{e}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{0}))+\frac{2D\sqrt{2K^{2}\sigma^{2}\log(1/\delta)}}{\sqrt{T}}+(\frac{4K+1}{2})\frac{LD^{2}}{T}$
(79)

Dropping $F(x_{0})$ and rearranging we have

$F(\boldsymbol{x}_{T})\geq(1-\frac{1}{e})F(\boldsymbol{x}^{*})-\frac{2DK\sigma\sqrt{\log(1/\delta)}}{T^{1/2}}-(\frac{4K+1}{2})\frac{LD^{2}}{T}$
(80)

∎

###  A.6 Proof of Lemma 5

Our first goal is to bound the term $\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert$. Substituting
$\bar{\boldsymbol{g}}_{t}=(1-\rho_{t})\bar{\boldsymbol{g}}_{t-1}+\rho_{t}\nabla\tilde{F}(\boldsymbol{x}_{t},\boldsymbol{z}_{t})$
we have

$\displaystyle\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert=\left\lVert\nabla
F(\boldsymbol{x}_{t})-(1-\rho_{t})\bar{\boldsymbol{g}}_{t-1}-\rho_{t}\nabla\tilde{F}(\boldsymbol{x}_{t},\boldsymbol{z}_{t})\right\rVert$
(81)

Adding and subtracting $(1-\rho_{t})\nabla F(\boldsymbol{x}_{t-1})$ on the
right hand side and applying the triangle inequality gives us

$\displaystyle\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert=\left\lVert\rho_{t}(\nabla
F(\boldsymbol{x}_{t})-\nabla\tilde{F}(\boldsymbol{x}_{t},\boldsymbol{z}_{t}))-(1-\rho_{t})(\nabla
F(\boldsymbol{x}_{t})-\nabla F(\boldsymbol{x}_{t-1}))+(1-\rho_{t})(\nabla
F(\boldsymbol{x}_{t-1})-\bar{\boldsymbol{g}}_{t-1})\right\rVert$
$\displaystyle\leq\rho_{t}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\nabla\tilde{F}(\boldsymbol{x}_{t},\boldsymbol{z}_{t})\right\rVert+(1-\rho_{t})\left\lVert\nabla
F(\boldsymbol{x}_{t})-\nabla
F(\boldsymbol{x}_{t-1})\right\rVert+(1-\rho_{t})\left\lVert\nabla
F(\boldsymbol{x}_{t-1})-\bar{\boldsymbol{g}}_{t-1}\right\rVert$ (82)

Now using our assumptions on the smoothness of F and boundedness of our
domain, we know that $\left\lVert\nabla F(\boldsymbol{x}_{t})-\nabla
F(\boldsymbol{x}_{t-1})\right\rVert\leq
L\left\lVert\boldsymbol{x}_{t}-\boldsymbol{x}_{t-1}\right\rVert=L\left\lVert\frac{\boldsymbol{v}_{t}}{T}\right\rVert\leq\frac{LD}{T}$
and hence

$\displaystyle\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert$
$\displaystyle\leq\rho_{t}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\nabla\tilde{F}(\boldsymbol{x}_{t},\boldsymbol{z}_{t})\right\rVert+(1-\rho_{t})\frac{LD}{T}+(1-\rho_{t})\left\lVert\nabla
F(\boldsymbol{x}_{t-1})-\bar{\boldsymbol{g}}_{t-1}\right\rVert$ (83)

Define $a_{i}:=\left\lVert\nabla
F(\boldsymbol{x}_{i})-\nabla\tilde{F}(\boldsymbol{x}_{i},\boldsymbol{z}_{i})\right\rVert$
as a random variable and recursively apply the inequality in eq. 83 to get

$\displaystyle\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert\leq\sum_{i=1}^{t}\rho_{i}\left(\prod_{j=i+1}^{t}(1-\rho_{j})\right)a_{i}+\frac{LD}{T}\sum_{i=1}^{t}\prod_{j=i}^{t}(1-\rho_{j})$
(84)

Given any sequence of momentum terms $\rho_{j}$ that is monotonic non-
increasing we have the upper bound $\rho_{j}\leq\rho_{1}$ and
$(1-\rho_{j})\leq(1-\rho_{t})$ and therefore

$\displaystyle\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert\leq\rho_{1}\sum_{i=1}^{t}(1-\rho_{t})^{t-i}a_{i}+\sum_{i=1}^{t}(1-\rho_{t})^{t-i+1}\frac{LD}{T}$
(85)

We now bound $S_{T}:=\sum_{t=1}^{T}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\bar{\boldsymbol{g}}_{t}\right\rVert$ as

$\displaystyle
S_{T}\leq\sum_{t=1}^{T}\rho_{1}\sum_{i=1}^{t}(1-\rho_{t})^{t-i}a_{i}+\frac{LD}{T}\sum_{t=1}^{T}\sum_{i=1}^{t}(1-\rho_{t})^{t+1-i}$
(86)

Using the following lemma from [16], we can bound the first term on the right
hand side

######  Lemma 6.

(Li and Orabona 2020 [16], Lemma 4) $\forall T\geq 1$, it holds that

$\sum_{t=1}^{T}a_{t}\sum_{i=1}^{t}b_{i}=\sum_{t=1}^{T}b_{t}\sum_{i=t}^{T}a_{i}$
(87)

Applying lemma 6 (step a) to the first term on the r.h.s. we have

$\displaystyle\sum_{t=1}^{T}\rho_{1}\sum_{i=1}^{t}(1-\rho_{t})^{t-i}a_{i}$
$\displaystyle\leq\rho_{1}\sum_{t=1}^{T}(1-\rho_{t})^{t}\sum_{i=1}^{t}(1-\rho_{t})^{-i}a_{i}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\rho_{1}\sum_{t=1}^{T}(1-\rho_{t})^{-t}a_{t}\sum_{i=t}^{T}(1-\rho_{t})^{i}$
$\displaystyle=\rho_{1}\sum_{t=1}^{T}a_{t}\sum_{i=t}^{T}(1-\rho_{t})^{i-t}$
(88)

To get a simple upper bound on this quantity, one could again use the fact
that $\rho_{t}$ is monotonic non-increasing to bound $1-\rho_{t}\leq
1-\rho_{T}$. Using the properties of geometric series this would lead to an
upper bound of

$\displaystyle\rho_{1}\sum_{t=1}^{T}a_{t}\sum_{i=t}^{T}(1-\rho_{t})^{i-t}$
$\displaystyle\leq\rho_{1}\sum_{t=1}^{T}a_{t}\sum_{i=t}^{T}(1-\rho_{T})^{i-t}\leq\frac{\rho_{1}}{\rho_{T}}\sum_{t=1}^{T}a_{t}$
(89)

If $\rho_{1}=\rho_{T}=\rho$ is a constant, then $\frac{\rho_{1}}{\rho_{T}}=1$
and we are just left with a sum of error terms. However, if our momentum term
is of the form $\rho_{t}=\frac{1}{t^{\alpha}}$, then we have a coefficient
$\frac{\rho_{1}}{\rho_{T}}=\mathcal{O}(t^{\alpha})$ in this bound. In order to
achieve a tighter constant bound in the general case of $\rho_{t}$ we need the
following technical lemma:

######  Lemma 7.

For $\alpha\in(0,1)$ non-inclusive, we have

$\sum_{t=1}^{\infty}(1-\frac{1}{t^{\alpha}})^{t}\leq\frac{1}{1-\alpha}\Gamma\left(\frac{1}{1-\alpha}\right)$
(90)

Where $\Gamma(z):=\int_{0}^{\infty}t^{z-1}e^{-t}dt$ is the Gamma function

###### Proof.

(Lemma 7) Using the well known inequality $(1-\frac{1}{n})^{n}\leq\frac{1}{e}$
and substituting $n=t^{\alpha}$ we get

$(1-\frac{1}{t^{\alpha}})^{t^{\alpha}}\leq
e^{-1}\implies(1-\frac{1}{t^{\alpha}})^{t}\leq e^{-t^{1-\alpha}}$ (91)

Where the second inequality can be found by raising both sides to the
$t^{1-\alpha}$ power. Since each term in our sequence is positive and
decreasing we know that we can bound our series by

$\displaystyle\sum_{t=1}^{\infty}(1-\frac{1}{t^{\alpha}})^{t}\leq\sum_{t=1}^{\infty}e^{-t^{1-\alpha}}<\int_{0}^{\infty}e^{-t^{1-\alpha}}dt$
(92)

Lastly we use a change of variables $u=t^{1-\alpha}$,
$du=(1-\alpha)t^{-\alpha}dt$ to get the integral into the following form

$\displaystyle\sum_{t=1}^{\infty}(1-\frac{1}{t^{\alpha}})^{t}$
$\displaystyle<\frac{1}{1-\alpha}\int_{0}^{\infty}e^{-u}u^{\frac{\alpha}{1-\alpha}}du=\frac{1}{1-\alpha}\Gamma(\frac{1}{1-\alpha})$
(93)

∎

Using lemma 7 and denoting $K:=\frac{1}{1-\alpha}\Gamma(\frac{1}{1-\alpha})$
as a constant, we can bound the summation in section A.6 by

$\rho_{1}\sum_{t=1}^{T}a_{t}\sum_{i=t}^{T}(1-\rho_{t})^{i-t}\leq\rho_{1}K\sum_{t=1}^{T}a_{t}$
(94)

Again using lemma 6 and lemma 7 we also have an upper bound on the second term
in eq. 86:

$\displaystyle\frac{LD}{T}\sum_{t=1}^{T}\sum_{i=1}^{t}(1-\rho_{t})^{t+1-i}\leq
LDK$ (95)

Therefore our bound on $S_{T}$ simplifies to

$S_{T}\leq\rho_{1}K\sum_{t=1}^{T}a_{t}+LDK$ (96)

We know by our original assumption that $a_{i}$ is a zero-mean sub-gaussian
random variable, therefore the weighted sum will also be sub-gaussian with
variance proxy

$\bar{\sigma}^{2}=\rho_{1}^{2}K^{2}\sum_{i=1}^{T}\sigma_{i}^{2}\leq
K^{2}\sigma^{2}T$ (97)

This means by Hoeffding’s inequality

$\mathbb{P}\left(\rho_{1}K\sum_{t=1}^{T}a_{t}\geq\lambda\right)\leq\exp\left\\{\frac{-\lambda^{2}}{2K^{2}\sigma^{2}T}\right\\}$
(98)

Rearranging we also find the equivalent statement is true

$\mathbb{P}\left(\sum_{t=1}^{T}a_{t}\leq\sqrt{2K^{2}\sigma^{2}T\ln(1/\delta)}\right)\geq
1-\delta$ (99)

Therefore we know that with probability greater than $1-\delta$

$S_{T}\leq\sqrt{2K^{2}\sigma^{2}T\log(1/\delta)}+LDK$ (100)

∎

###  A.7 Proof of Theorem 5

Similarly to the proof of theorem 3, we first utilize a bound on the variance
of the gradient approximation:

######  Lemma 8.

(Hassani et al. 2020, Lemma 2) Given the gradient approximations $g_{t}$ as
calculated in algorithm 4, target error $\epsilon$, and batch size
$|\mathcal{M}|=1/\epsilon$, we have

$\mathbb{E}\left[\left\lVert\nabla
F(\boldsymbol{x}_{t})-\hat{\boldsymbol{g}}_{t}\right\rVert^{2}\right]\leq(1+\epsilon
t)L^{2}D^{2}\epsilon^{2}$

Larger batch sizes mean more queries of our stochastic oracle, but have the
benefit of reducing the target error $\epsilon$. If we choose $\epsilon=1/t$
we get the bound:

$\mathbb{E}\left[\left\lVert\nabla
F(\boldsymbol{x}_{t})-\hat{\boldsymbol{g}}_{t}\right\rVert^{2}\right]\leq\frac{2L^{2}D^{2}}{t^{2}}$

Notice that the residuals between the true gradient and these new estimates
decay much more rapidly. Using the Chebyshev inequality we have

$\mathbb{P}\left(\left\lVert\nabla
F(\boldsymbol{x}_{t})-\hat{\boldsymbol{g}}_{t}\right\rVert^{2}\geq\delta^{2}\frac{2L^{2}D^{2}}{t^{2}}\right)\leq\frac{1}{\delta^{2}}$
(101)

The union bound is likewise

$\mathbb{P}\left(\sum_{t=0}^{T-1}\left\lVert\nabla
F(\boldsymbol{x}_{t})-\hat{\boldsymbol{g}}_{t}\right\rVert^{2}\geq\delta^{2}\sum_{t=0}^{T-1}\frac{2L^{2}D^{2}}{t^{2}}\right)\leq\frac{T}{\delta^{2}}$
(102)

Now we will begin the proof of theorem 5.

###### Proof.

We intervene at the following inequality found in the original SCG++
expectation bound proof (Hassani et al. 2020, eq. 33):

$F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{T})\leq(1-\frac{1}{T})^{T}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{0}))+\sum_{t=0}^{T-1}\frac{1}{2T}\left[\beta_{t}D^{2}+\frac{\left\lVert\nabla
F(\boldsymbol{x}_{t})-\hat{\boldsymbol{g}}_{t}\right\rVert^{2}}{\beta_{t}}\right]+\frac{LD^{2}}{2T^{2}}$

This time setting $\beta_{t}=\frac{\sqrt{2}\delta L}{t}$ we know with
probability at least $1-\frac{T}{\delta^{2}}$

$F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{T})\leq\frac{1}{e}(F(\boldsymbol{x}^{*})-F(\boldsymbol{x}_{0}))+\sum_{t=0}^{T-1}\delta\frac{\sqrt{2}LD^{2}}{tT}+\frac{LD^{2}}{2T^{2}}$
(103)

With some rearrangement and simplification

$F(\boldsymbol{x}_{T})\geq(1-\frac{1}{e})F(\boldsymbol{x}^{*})-\delta\frac{LD^{2}}{T}-\frac{LD^{2}}{2T^{2}}$
(104)

∎

##  Appendix B CONTINUOUS SUBMODULAR MAXIMIZATION ALGORITHMS

initialization: convex constraint set $\mathcal{C}$ with step lengths
$\eta_{t}$

initialization: $\boldsymbol{x}_{0}\in\mathcal{C}$

for  _t=1….T_ do

$\boldsymbol{g}_{t}\leftarrow\nabla F(\boldsymbol{x}_{t},\boldsymbol{z}_{t})$,
where $\boldsymbol{z}_{t}\sim P$

$\boldsymbol{y}_{t+1}\leftarrow\boldsymbol{x}_{t}+\eta\boldsymbol{g}_{t}$

$\boldsymbol{x}_{t+1}\leftarrow\arg\min_{\boldsymbol{x}\in
C}||\boldsymbol{y}_{t+1}-\boldsymbol{x}||_{2}$

end for

return $\boldsymbol{x}_{T}$

Algorithm 1 Projected Gradient Ascent

initialization: convex constraint set $\mathcal{C}$ with step lengths
$\eta_{t}$

initialization: $\boldsymbol{x}_{0}\in\mathcal{C}$

for  _t=1….T_ do

Sample $s_{t}$ from $\boldsymbol{S}$ where $\mathbb{P}(\boldsymbol{S}\leq
s)=\int_{0}^{s}\frac{\gamma^{\gamma(u-1)}}{1-e^{-\gamma}}\mathds{1}(u\in[0,1])du$

Compute
$\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t}):=\frac{1-e^{-\gamma}}{\gamma}\nabla\tilde{F}(s_{t}*\boldsymbol{x}_{t})$

$\boldsymbol{y}_{t+1}\leftarrow\boldsymbol{x}_{t}+\eta\nabla\tilde{F}^{\prime}(\boldsymbol{x}_{t})$

$\boldsymbol{x}_{t+1}\leftarrow\arg\min_{\boldsymbol{x}\in
C}||\boldsymbol{y}_{t+1}-\boldsymbol{x}||_{2}$

end for

return $\boldsymbol{x}_{T}$

Algorithm 2 Boosted Projected Gradient Ascent

initialization: Stepsizes $\rho_{t}>0$.

initialization: $\bar{\boldsymbol{g}}_{0}=\boldsymbol{x}_{0}=0$

for  _t=1….T_ do

$\bar{\boldsymbol{g}}_{t}\leftarrow(1-\rho_{t})\bar{\boldsymbol{g}}_{t-1}+\rho_{t}\nabla\tilde{F}(x_{t},z_{t})$

$\boldsymbol{v}_{t}\leftarrow\arg\max_{\boldsymbol{v}\in
C}\\{\bar{\boldsymbol{g}}_{t}^{T}\boldsymbol{v}\\}$

$\boldsymbol{x}_{t+1}\leftarrow\boldsymbol{x}_{t+1}+\frac{1}{T}\boldsymbol{v}_{t}$

end for

return $\boldsymbol{x}_{T}$

Algorithm 3 Stochastic Continuous Greedy

input: minibatch sizes $|\mathcal{M}_{0}|$ and $|\mathcal{M}|$

initialization: $\boldsymbol{x}^{0}=0$

for  _t=1….T_ do

if  _t=1_ then

$M_{0}\sim p(\boldsymbol{z};\boldsymbol{x}^{0})$ and find
$\hat{\boldsymbol{g}}_{0}=\nabla\tilde{F}(x_{0},\mathcal{M}_{0})$

else

$a\sim Unif[0,1]$

$\boldsymbol{x}(a)=a\cdot\boldsymbol{x}_{t}+(1-a)\cdot\boldsymbol{x}_{t-1}$

$\mathcal{M}\sim p(\boldsymbol{z};\boldsymbol{x}(a))$

$\widetilde{\nabla_{t}^{2}}=\frac{1}{|\mathcal{M}|}\sum_{(a,\boldsymbol{z}(a))\in\mathcal{M}}\widetilde{\nabla^{2}}F(\boldsymbol{x}(a);\boldsymbol{z}(a))$

$\tilde{\Delta^{t}}=\widetilde{\nabla_{t}^{2}}(\boldsymbol{x}^{t}-\boldsymbol{x}^{t-1})$

$\hat{\boldsymbol{g}}_{t}\leftarrow\hat{\boldsymbol{g}}_{t-1}+\tilde{\Delta^{t}}$

$\boldsymbol{v}_{t}\leftarrow\arg\max_{\boldsymbol{v}\in
C}\\{\hat{\boldsymbol{g}}_{t}^{T}\boldsymbol{v}\\}$

$\boldsymbol{x}_{t+1}\leftarrow\boldsymbol{x}_{t+1}+\frac{1}{T}\boldsymbol{v}_{t}$

end for

return $\boldsymbol{x}_{T}$

Algorithm 4 Stochastic Continuous Greedy++

##  Appendix C ADDITIONAL EXPERIMENTAL RESULTS

###  C.1 Distance Between Expectation and Bad Solutions

In this section, we present more results on how far away the worst-case PGA
solutions can be from the expectation. In Figure 3 we show the distribution of
variance in returned solution utility for each run of the algorithm. Figure 4
shows the distribution of minimum and maximum _normalized_ utilities and the
expectations for PGA on each dataset. We observe that there is a large gap
between the minimum solutions and the expectation, and in the extreme case a
bad run can have 30% less value than the expectation. This observation
demonstrates the need for providing a lower bound on the performance of the
existing stochastic continuous submodular maximization methods.

Figure 3: Variance of PGA Utility Distribution. NQP (Left) Yahoo! (Right).

Figure 4: Normalized Utility Distribution of PGA. Histograms of normalized
minimum and maximum utility of each individual run, and the expected utility,
across 500 runs for NQP & Yahoo!.