Gradient Methods for Submodular Maximization

Introduction

Submodular set functions exhibit a natural diminishing returns property, resembling concave functions in continuous domains. At the same time, they can be minimized exactly in polynomial time (while can only be maximized approximately), which makes them similar to convex functions. They have found numerous applications in machine learning, including viral marketing , dictionary learning network monitoring , sensor placement , product recommendation , document and corpus summarization data summarization , crowd teaching , and probabilistic models . However, submodularity is in general a property that goes beyond set functions and can be defined for continuous functions. In this paper, we consider the following stochastic continuous submodular optimization problem:

where $\mathcal{K}$ is a bounded convex body, $\mathcal{D}$ is generally an unknown distribution, and $F_{\theta}$’s are are continuous submodular functions for every $\bm{\theta}\in\mathcal{D}$. Such a setting has recently been introduced in . We also denote the optimum value as $\text{OPT}\triangleq\max_{\bm{x}\in\mathcal{K}}F(\bm{x})$. We note that the function $F(x)$ is itself also continuous submodular as a non-negative combination of submodular functions are still submodular . The formulation covers popular instances of submodular optimization. For instance, when $\mathcal{D}$ puts all the probability mass on a single function, (1.1) reduces to deterministic continuous submodular optimization. Another common objective is the finite-sum continuous submodular optimization where $\mathcal{D}$ is uniformly distributed over $m$ instances, i.e., $F(x)\doteq\frac{1}{m}\sum_{\theta=1}^{m}F_{\theta}(x)$.

A natural approach to solving problems of the form (1.1) is to use projected stochastic methods. As we shall see in Section 5, these local search heuristics are surprisingly effective. However, the reasons for this empirical success is completely unclear. The main challenge is that maximizing $F$ corresponds to a nonconvex optimization problem (as the function $F$ is not concave), and a priori it is not clear why gradient methods should yield a reliable solution. This leads us to the main challenge of this paper

Do projected gradient methods lead to provably good solutions for continuous submodular maximization with general convex constraints?

We answer the above question in the affirmative, proving that projected gradient methods produce a competitive solution with respect to the optimum. More specifically, given a general bounded convex body $\mathcal{K}$ and a continuous function $F$ that is monotone, smooth, and (weakly) DR-submodular we show that

All stationary points of a DR-submodular function $F$ over $\mathcal{K}$ provide a $1/2$ approximation to the global maximum. Thus, projected gradient methods with sufficiently small step sizes (a.k.a. gradient flows) always lead to a solutions with $1/2$ approximation guarantees.

More generally, for weakly continuous DR-submodular functions with parameter $\gamma$ (define in (2.6)) we prove the above results with $\gamma^{2}/(1+\gamma^{2})$ approximation guarantee.

Our result have some important implications. First, they show that projected gradient methods are an efficient way of maximizing the multilinear extension of (weakly) submodular set functions for any submodularity ratio $\gamma$ (note that $\gamma=1$ corresponds to submodular functions) . Second, in contrast to conditional gradient methods for submodular maximization that should always start from the origin , projected gradient methods can start from any initial point in the constraint set $\mathcal{K}$ and still produce a competitive solution. Third, such conditional gradient methods, when applied to the stochastic setting (with a fixed batch size), perform poorly and can produce arbitrarily bad solutions when applied to continuous submodular functions (see Appendix B for an example and further discussion on why conditional gradient methods do not easily admit stochastic variants). In contrast, stochastic projected gradient methods are stable by design and provide a solution with $1/2$ guarantee in expectation. Finally, our work provides a unifying approach for solving the stochastic submodular maximization problem

Continuous submodular maximization

One can easily verify that for a differentiable DR-submodular functions the gradient is an antitone mapping, i.e., for all $\bm{x},\bm{y}\in\mathcal{X}$ such that $\bm{x}\leq\bm{y}$ we have $\nabla F(\bm{x})\geq\nabla F(\bm{y})$ . When twice differentiable, DR-submodularity is equivalent to

The above twice differentiable functions are sometimes called smooth submodular functions in the literature . However, in this paper, we say a differentiable submodular function $F$ is $L$-smooth w.r.t a norm $\|\cdot\|$ (and its dual norm $\|\cdot\|_{*}$) if for all $\bm{x},\bm{y}\in\mathcal{X}$ we have

We note that for set functions, DR-submodularity (i.e., Eq. 2.4) and submodularity (i.e., Eq. 2.1) are equivalent. However, this is not true for the general submodular functions defined on integer lattices or product of sub-intervals .

The focus of this paper is on continuous submodular maximization defined in Problem (1.1). More specifically, we assume that $\mathcal{K}\subset\mathcal{X}$ is a a general bounded convex set (not necessarily down-closed as considered in ) with diameter $R$. Moreover, we consider $F_{\theta}$’s to be monotone (weakly) DR-submodular functions with parameter $\gamma$.

Background and related work

Generalization of submodular set functions has lately received a lot of attention. For instance, a line of recent work considered DR-submodular function maximization over an integer lattice . Interestingly, Ene and Nguyen provided an efficient reduction from an integer-lattice DR-submodular to a submodular set function, thus suggesting a simple way to solve integer-lattice DR-submodular maximization. Note that such reductions cannot be applied to the optimization problem (1.1) as expressing general convex body constraints may require solving a continuous optimization problem.

Algorithms and main results

In this section we discuss our algorithms together with the corresponding theoretical guarantees. In what follows, we assume that $F$ is a weakly DR-submodular function with parameter $\gamma$.

We begin with the definition of a stationary point.

Stationary points are of interest because they characterize the fixed points of the Gradient Ascent (GA) method. Furthermore, (projected) gradient ascent with a sufficiently small step size is known to converge to a stationary point for smooth functions . To gain some intuition regarding this connection, let us consider the GA procedure. Roughly speaking, at any iteration $t$ of the GA procedure, the value of $F$ increases (to the first order) by $\langle\nabla F(\bm{x}_{t}),\bm{x}_{t+1}-\bm{x}_{t}\rangle$. Hence, the progress at time $t$ is at most $\max_{\bm{y}\in\mathcal{K}}\langle\nabla F(\bm{x}_{t}),\bm{y}-\bm{x}_{t}\rangle$. If at any time $t$ we have $\max_{\bm{y}\in\mathcal{K}}\langle\nabla F(\bm{x}_{t}),\bm{y}-\bm{x}_{t}\rangle\leq 0$, then the GA procedure will not make any progress and it will be stuck once it falls into a stationary point.

The next natural question is how small can the value of $F$ be at a stationary point compared to the global maximum? The following lemma relates the value of $F$ at a stationary point to OPT.

If $\bm{x}$ is a stationary point of $F$ in $\mathcal{K}$, then $F(\bm{x})\geq\frac{\gamma^{2}}{1+\gamma^{2}}\rm{OPT}$.

Furthermore, if $F$ is $L$-smooth, gradient ascent with a step size smaller than $1/L$ will converge to a stationary point.

The theorem above guarantees that all fixed points of the GA method yield a solution whose function value is at least $\frac{\gamma^{2}}{1+\gamma^{2}}$OPT. Thus, all fixed point of GA provide a factor $\frac{\gamma^{2}}{1+\gamma^{2}}$ approximation ratio. The particular case of $\gamma=1$, i.e., when $F$ is DR-submodular, asserts that at any stationary point $F$ is at least $\text{OPT}/2$. This lower bound is in fact tight. In Appendix A we provide a simple instance of a differentiable DR-Submodular function that attains $\text{OPT}/2$ at a stationary point that is also a local maximum.

2 (Stochastic) gradient methods

We now discuss our first algorithmic approach. For simplicity we focus our exposition on the DR submodular case, i.e., $\gamma=1$, and discuss how this extends to the more general case in the proofs (Section 7.4). A simple approach to maximizing DR submodular functions is to use the (projected) Gradient Ascent (GA) method. Starting from an initial estimate $\bm{x}_{1}\in\mathcal{K}$ obeying the constraints, GA iteratively applies the following update

Here, $\mu_{t}$ is the learning rate and $\mathcal{P}_{\mathcal{K}}(\bm{v})$ denotes the Euclidean projection of $\bm{v}$ onto the set $\mathcal{K}$. However, in many problems of practical interest we do not have direct access to the gradient of $F$. In these cases it is natural to use a stochastic estimate of the gradient in lieu of the actual gradient. This leads to the Stochastic Gradient Method (SGM). Starting from an initial estimate $\bm{x}_{0}\in\mathcal{K}$ obeying the constraints, SGM iteratively applies the following updates

Specifically, at every iteration $t$, the current iterate $\bm{x}_{t}$ is updated by adding $\mu_{t}\bm{g}_{t}$, where $\bm{g}_{t}$ is an unbiased estimate of the gradient $\nabla F(\bm{x}_{t})$ and $\mu_{t}$ is the learning rate. The result is then projected onto the set $\mathcal{K}$. We note that when $\bm{g}_{t}=\nabla F(\bm{x}_{t})$, i.e., when there is no randomness in the updates, then the SGM updates (4.2) reduce to the GA updates (4.1). We detail the SGM method in Algorithm 1.

As we shall see in our experiments detained in Section 5, the SGM method is surprisingly effective for maximizing monotone DR-submodular functions. However, the reasons for this empirical success was previously unclear. The main challenge is that maximizing $F$ corresponds to a nonconvex optimization problem (as the function $F$ is not concave), and a priori it is not clear why gradient methods should yield a competitive ratio. Thus, studying gradient methods for such nonconvex problems poses new challenges:

Do (stochastic) gradient methods converge to a stationary point?

We run stochastic gradient updates of the form (4.2) with $\mu_{t}=\frac{1}{L+\frac{\sigma}{R}\sqrt{t}}$. Let $\tau$ be a random variable taking values in $\{1,2,\ldots,T\}$ with equal probability. Then,

We would like to note that if we pick $\tau$ to be a random variable taking values in $\{2,\ldots,T-1\}$ with probability $\frac{1}{(T-1)}$ and $1$ and $T$ each with probability $\frac{1}{2(T-1)}$ then

The above results roughly state that $T=\mathcal{O}\left(\frac{R^{2}L}{\epsilon}+\frac{R^{2}\sigma^{2}}{\epsilon^{2}}\right)$ iterations of the stochastic gradient method from any initial point, yields a solution whose objective value is at least $\frac{\text{OPT}}{2}-\epsilon$. Stated differently, $T=\mathcal{O}\left(\frac{R^{2}L}{\epsilon}+\frac{R^{2}\sigma^{2}}{\epsilon^{2}}\right)$ iterations of the stochastic gradient method provides in expectation a value that exceeds $\frac{\text{OPT}}{2}-\epsilon$ approximation ratio for DR-submodular maximization. As explained in Section 4.1, it is not possible to go beyond the factor $1/2$ approximation ratio using gradient ascent from an arbitrary initialization.

An important aspect of the above result is that it only requires an unbiased estimate of the gradient. This flexibility is crucial for many DR-submodular maximization problems (see, (1.1)) as in many cases calculating the function $F$ and its derivative is not feasible. However, it is possible to provide a good un-biased estimator for these quantities.

We would like to point out that our results are similar in nature to known results about stochastic methods for convex optimization. Indeed, this result interpolates between the $\frac{1}{\sqrt{T}}$ for stochastic smooth optimization, and the $1/T$ for deterministic smooth optimization. The special case of $\sigma=0$ which corresponds to Gradient Ascent deserves particular attention. In this case, and under the assumptions of Theorem 4.3, it is possible to show that $F(\bm{x}_{T})\geq\frac{\rm{OPT}}{2}-\frac{R^{2}L}{T}$, without the need for a randomized choice of $\tau\in[T]$.

Finally, we would like to note that while the first term in (4.4) decreases as $1/T$, the pre-factor $L$ could be rather large in many applications. For instance, this quantity may depend on the dimension of the input $n$ (see Section C in the Appendix). Thus, the number of iterations for reaching a desirable accuracy may be very large. Such a large computational load causes (stochastic) gradient methods infeasible in some application domains. We will overcome this deficiency in the next section by using stochastic mirror methods.

3 Stochastic mirror method

$\Phi$ is strictly convex and differentiable.

We define the Bregman divergence associated to a mirror map $\phi$ as

We also define the projection onto a set $\mathcal{K}$ with respect to a mapping $\Phi$ via

Finally, we define the diameter as follows

Let $\Phi$ be a mirror map that is $1$-strongly convex on $\mathcal{K}$ with respect to the norm $\|\|$. Assume that $F$ is $L$-smooth with respect to the norm $\|\|$ and is a monotone, continuous submodular function. Furthermore, assume that we have access to a stochastic oracle $\bm{g}_{t}$ obeying

We start from $\bm{x}_{1}\in\arg\min_{\bm{x}\in\mathcal{K}}\Phi(\bm{x})$ and run the mirror ascent updates of the form

with $\mu_{t}=\frac{1}{L+\frac{\sigma}{R}\sqrt{t}}$. Let $\tau$ be a random variable taking values in $\{1,2,\ldots,T\}$ with equal probability. Then,

We would like to note that if we pick $\tau$ to be a random variable taking values in $\{2,\ldots,T-1\}$ with probability $\frac{1}{(T-1)}$ and $1$ and $T$ each with probability $\frac{1}{2(T-1)}$ then

Experiments

Therefore, by running the stochastic versions of projected gradient methods, we can find a solution in the continuous domain that is at least $1/2$ approximation to the optimal value. By rounding that fractional solution (for instance via randomized Pipage rounding ) we obtain a set whose utility is at least $1/2$ of the optimum solution set of size $k$. We note that randomized Pipage rounding does not need access to the value of $f$. We also remark that projection onto $\mathcal{P}_{k}$ can be done very efficiently in $O(n)$ time (see ). Therefore, such approach easily scales to big data scenarios where the size of the data set (e.g. number of users) or the number of items $n$ (e.g. number of movies) are very large.

In our experiments, we consider the following baselines:

Stochastic Gradient Ascent (SG): with the step size $\mu_{t}=c/\sqrt{t}$ and batch size $B$. The details for computing an unbiased estimation for the gradient of $F$ are given in Appendix D.

Stochastic Mirror Ascent (SM): with the step size $\mu_{t}=c/\sqrt{t}$ and batch size $B$.

Frank-Wolfe (FW) variant of : with parameter $T$ for the total number of iterations and batch size $B$ (we further let $\alpha=1,\delta=0$, see Algorithm 1 in for more details).

Batch-mode Greedy (Greedy): by running greedy algorithm over the empirical objective function with $B$ samples.

To run the experiments we use the MovieLens data set. It consists of 1 million ratings (from 1 to 5) by $n=6041$ users for $m=4000$ movies. Let $r_{i,j}$ denote the rating of user $i$ for movie $j$ (if such a rating does not exist we assign $r_{i,j}$ to 0). In our experiments, we consider two well motivated objective functions. The first one is the facility location where the valuation function by user $i$ is defined as $f_{i}(S)=\max_{j\in S}r_{i,j}$. In words, the way user $i$ evaluates a set $S$ is by picking the highest rated movie in $S$. For simplicity, we also assume that the distribution $\mathcal{D}$ is uniform. Thus, the objective function is $f_{1}(S)=\frac{1}{n}\sum_{i=1}^{n}\max_{j\in S}r_{i,j}$.

In our second experiment, we consider a different user-specific valuation function which is a concave function composed with a modular function, i.e., $f_{i}(S)=(\sum_{j\in S}r_{i,j})^{1/2}.$ Again, by considering the uniform distribution over the set of users, we obtain $f_{2}(S)=\frac{1}{n}\sum_{i=1}^{n}(\sum_{j\in S}r_{i,j})^{1/2}.$ Note that the multilinear extensions of $f_{1}$ and $f_{2}$ are neither concave nor convex.

Figure 1 depicts the performance of different algorithms for the two proposed objective functions. As Figures 1(a) and 1(c) show, the FW algorithm needs a much higher batch size to be comparable in performance w.r.t. to our stochastic gradient methods. With the same batch size and number of iterations SG, SM, and FW have similar computational complexity. Therefore, a smaller batch size leads to less computational effort. Figure 1(b) shows that after a few hundred iterations both SG and SM with $B=20$ obtain almost the same utility as Greedy with a large batch size ($B=1000$). Finally, Figure 1(d) shows the performance of the algorithms with respect to the number of times the single functions ($f_{i}$’s) are evaluated. This further shows that gradient based methods have comparable complexity w.r.t. the Greedy algorithm in the discrete domain.

Conclusion

In this paper we studied gradient methods for submodular maximization. Despite the lack of convexity of the objective function we demonstrated that local search heuristics are effective at finding approximately optimal solutions. In particular, we showed that all fixed point of projected gradient ascent provide a factor $1/2$ approximation to the global maxima. We also demonstrated that stochastic gradient and mirror methods achieve an objective value of ${\rm OPT}/2-\epsilon$ in $\mathcal{O}(\frac{1}{\epsilon^{2}})$ iterations. We further demonstrated the effectiveness of our methods with experiments on real data.

While in this paper we have focused on convex constraints, our framework may allow non-convex constraints as well. For instance it may be possible to combine our framework with recent results in to deal with general nonconvex constraints. Furthermore, in some cases projection onto the constraint set may be computationally intensive or even intractable but calculating an approximate projection may be possible with significantly less effort. One of the advantages of gradient descent-based proofs is that they continue to work even when some perturbations are introduced in the updates. Therefore, we believe that our framework can deal with approximate projections and we hope to pursue this in future work.

Proofs

To prove part (i) we first prove that for any two vectors $\bm{x},\bm{y}\in\mathcal{X},$ we have

To this aim note that for all $\bm{x},\bm{z}\in\mathcal{X}$ s.t. $\bm{x}\preceq\bm{z}$, by using (7.1), we have

Now, from (7.1) we deduce that for any $\bm{x},\bm{y}\in\mathcal{X}$:

From these two inequalities we immediately obtain

and we obtain (7.2) by noting that $F(\bm{x}\wedge\bm{y})\geq 0$ and $\bm{x}\wedge\bm{y}+\bm{x}\vee\bm{y}=\bm{x}+\bm{y}$.

Part (i) of the theorem follows from (7.2) by letting $\bm{x}$ to be a stationary point and $\bm{y}=\bm{x}^{*}:=\underset{\mathcal{K}}{\arg\max}F(\bm{y})$.

To prove part (ii) note that by the smoothness of the function (more specifically the quadratic upper bound) we have

Now note that $\bm{x}_{t+1}=\mathcal{P}_{\mathcal{K}}\left(\bm{x}_{t}+\mu_{t}\nabla F(\bm{x}_{t})\right)$ and thus using the properties of convex projections we have

Plugging this into the latter inequality we conclude that for $\mu_{t}\leq\frac{1}{L}$

By definition of projection the latter implies that $\mathcal{P}_{\mathcal{K}-\{\bm{x}\}}(\mu_{t}\nabla F(\bm{x}))=0$. A well known result in convex analysis (e.g., see [33, Lemma 6.4] or [34, Lemma 7.11]) implies $\max_{\bm{y}\in\mathcal{K}}\langle\nabla F(x),\bm{y}-\bm{x}\rangle\leq 0$, concluding the proof.

2 Proof of (stochastic) mirror method (Proof of Theorem 4.7)

We begin by stating some lemmas about mirror descent together with some useful preliminary lemmas in the next section.

We begin with two lemmas about mirror descent adapted from .

Let $\bm{x}\in\mathcal{K}$ and $\bm{y}\in\mathcal{K}$, then

Also we need the following well-known identity about Bregman divergences which will be useful several times in our proofs.

We next state a lemma due to Chekuri, Vondrak, and Zenkluser.

[36, Lemma 3.2] Assume $F$ is a monotone and submodular function. Then, for any two points $\bm{x},\bm{y}\in\mathcal{K}$

Consider one iteration of the mirror descent update

Using $\nabla\Phi(\bm{y})=\nabla\Phi(\bm{x})+\mu G(\bm{x})$, we conclude that

where the last equality follows from Lemma 7.2.

Consider the setting of Theorem 4.7 and let $D_{\Phi}$ be the Bregman divergence corresponding to the mirror map $\Phi$. Let $\eta$ be a nonnegative scalar with $\mu_{t}$ obeying

Proof Using smoothness of the function $F$ we have the following chain of inequalities

where (a) follows from the fact that $\langle\bm{a},\bm{b}\rangle\leq\frac{1}{2\eta}\|\bm{a}\|^{2}+\frac{\eta}{2}\|\bm{b}\|_{*}^{2}$ by Young’s inequality and (b) follows from strong convexity of the mirror map $\Phi$. Rearranging the above inequality we arrive at the following chain of inequalities

where (a) follows from Lemma 7.4 and (b) from the choice $\mu_{t}\leq 1/\left(L+1/\eta\right)$.

Using Lemma 7.5 with ${\bm{z}}=\bm{x}^{*}$ (Global optimum) and $\eta=\eta_{t}$ we have

Using \big{\langle}\bm{g}_{t},\bm{x}_{t}-\bm{x}^{*}\big{\rangle}=\big{\langle}\nabla F(\bm{x}_{t}),\bm{x}_{t}-\bm{x}^{*}\big{\rangle}+\big{\langle}\bm{g}_{t}-\nabla F(\bm{x}_{t}),\bm{x}_{t}-\bm{x}^{*}\big{\rangle} we conclude that

Using Lemma 7.3 with $\bm{y}=\bm{x}^{*}$ and $\bm{x}=\bm{x}_{t}$ in the above inequality we conclude that

Taking expectation of both sides we arrive at

Summing both sides from $t=1$ to $T$ we conclude that

Here, (a) follows from the fact that $D_{\Phi}(\bm{x}^{*},\bm{x}_{t})\leq R^{2}$. Now using $\eta_{t}=\frac{R}{\sigma\sqrt{t}}$ and $\mu_{t}=\frac{1}{L+\frac{1}{\eta_{t}}}$ we arrive at

Here, (a) follows from the fact that $\sum_{t=1}^{T}\frac{1}{\sqrt{t}}\leq 2\sqrt{T}$. Thus

The proof now follows from the fact that $E[F(\bm{x}_{T+1})]\leq{\rm OPT}$. Note also that from (7.6) we have

3 Proof of (stochastic) gradient method (Proof of Theorem 4.3)

4 Extensions to weakly submodular functions

In this section we shall show that Theorem 4.7 extends to weakly submodular functions with the new guarantee given by

To this aim using Lemma 7.5 with ${\bm{z}}=\bm{x}^{*}$ (Global optimum) and $\eta=\eta_{t}$ we have

Using \big{\langle}\bm{g}_{t},\bm{x}_{t}-\bm{x}^{*}\big{\rangle}=\big{\langle}\nabla F(\bm{x}_{t}),\bm{x}_{t}-\bm{x}^{*}\big{\rangle}+\big{\langle}\bm{g}_{t}-\nabla F(\bm{x}_{t}),\bm{x}_{t}-\bm{x}^{*}\big{\rangle} we conclude that

Using condition (7.2) with $\bm{y}=\bm{x}^{*}$ and $\bm{x}=\bm{x}_{t}$ in the above inequality we conclude that

Taking expectation of both sides we arrive at

Summing both sides from $t=1$ to $T$ we conclude that

Here, (a) follows from the fact that $D_{\Phi}(\bm{x}^{*},\bm{x}_{t})\leq R^{2}$. Now using $\eta_{t}=\frac{R}{\sigma\sqrt{t}}$ and $\mu_{t}=\frac{1}{L+\frac{1}{\eta_{t}}}$ we arrive at

Here, (a) follows from the fact that $\sum_{t=1}^{T}\frac{1}{\sqrt{t}}\leq 2\sqrt{T}$. Thus

Dividing both sides by $\left(\gamma+\frac{1}{\gamma}\right)T$ concludes the proof.

Acknowledgements

This work was done while the authors were visiting the Simon’s Institute for the Theory of Computing. The authors would like to thank Jeff Bilmes, Volkan Cevher, Maryam Fazel, Mohammad-Reza Karimi, Andreas Krause, Mario Lucic, and Andrea Montanari for helpful discussions.

References

Appendix A A DR-Submodular Function that Attains OPT/2+ϵOPT2italic-ϵ\rm{OPT}/2+\epsilon on a local maximum

Now, define $\mathcal{K}=\{\bm{x}\in^{2k+1}:\sum_{i=1}^{2k+1}x_{i}=k\}$. We claim that $\bm{x}_{\rm loc}=(\overbrace{1,1,\ldots,1}^{k},0,0,\ldots,0)$ is a local maximum. To see this, we have $\nabla F(\bm{x}_{\rm loc})=(\overbrace{1,1\cdots,1}^{2k},0)$. As a result, for any $y\in\mathcal{K}$:

As a result, $\bm{x}_{\rm loc}$ is a stationary point. It remains to show that in a sufficiently small neighborhood of $\bm{x}_{\rm loc}$ inside $\mathcal{K}$, $\bm{x}_{\rm loc}$ becomes the maximizer of $F$. Note that $F(\bm{x}_{\rm loc})=k+1$. Consider a point

It is easy to see that $y\in\mathcal{K}$. We have

Thus, by choosing $\epsilon\leq k$, we conclude that any $y$ with form as in (A.1) has a lower function value than $\bm{x}_{\rm loc}$. This proves that $\bm{x}_{\rm loc}$ is a local maximum. Now, consider the vector $\bm{x}^{*}=(0,0,\cdots,0,\overbrace{1,1,\cdots,1}^{k+1})$. We have $F(\bm{x}_{\rm loc})/F(\bm{x}^{*})=1/2+1/(2k)$. As a result, by considering a large enough $k$, the value of $F$ at the local maximum $\bm{x}_{\rm loc}$ becomes $\rm{OPT}/2+\epsilon$.

Appendix B An Example for Deficiency of the Frank-Wolfe Type Algorithm of [16] in the Stochastic Setting

Assume we want to maximize a DR-Submodular function $F$ over a convex set $\mathcal{K}$. Assume further that $0\in\mathcal{K}$. The Frank-Wolfe Type algorithm discussed in can be briefly stated as follows (note that for simplicity we let $\alpha=1$ and $\delta=0$, see Algorithm 1 in ): Fix a (large) number $T$ as the total number of iterations, let $\bm{x}_{0}=0$ and for $t<T$ do:

Assume now that instead of $\nabla F(x)$ we have access to an unbiased estimator $\nabla F_{i}(x)$ where $i\sim U$. Note that $\nabla F_{i}(x)=(m_{i,1},m_{i,2},\cdots,m_{i,n})$. As a result, for $i\in\{1,\cdots,n-1\}$we obtain $\arg\max_{v\in\mathcal{K}}\langle\nabla F_{i}(x),v\rangle=e_{i}$, where $e_{i}$ is the vector that has $1$ at position $i$ and elsewhere. Interestingly for this example, the stochastic Frank-Wolf algorithm never makes any progress on the $n-th$ coordinate and $\bm{x}_{t}$ will always take on the $n$-th coordinate. As a result, it is easy to see that for large $T$ the algorithm will end up at $\bm{x}_{\infty}=(1/(n-1),1/(n-1),\cdots,1/(n-1),0)$. However, we have $\bm{x}^{*}=(0,0,\cdots,0,1)$ and $F(\bm{x}_{\infty})/F(\bm{x}^{*})=2/(n-1)$ which can become arbitrarily small with $n$.

Let us briefly explain why conditional gradient methods do not easily admit stochastic variants. The main bottleneck is in the update step of the continuous greedy algorithm (FW). As stated above, in each iteration, FW finds a point in the constraint set $\mathcal{K}$ which has the highest inner product with the gradient and then uses this vector in order to update the current position. However, this step is not very robust to the noise. More precisely, if instead of the gradient of $F$ we plug into the $\arg\max$ a noisy (and unbiased) version of the gradient, the outcome may be far from $\bm{v}_{t}$. In other words, expectation and $\arg\max$ are not interchangeable. It is easy to see that the above example extends to FW with any fixed natch size (i.e. when gradient is approximated by averaging a fixed number of i.i.d. samples).

Before proving the lemma, let us remark that in many practical applications, the value of $m_{f}$ is not so large (see for example the movie recommendation setting of Section 5 where $m_{f}$ is less than the maximum possible rating).

Proof At any point $\bm{x}\in^{n}$, the Hessian of $F$, denoted by $\nabla^{2}F(x)$, has the following property (see ):

Appendix D How to Construct an Unbiased Estimator of the Gradient in Multilinear Extensions

where for example by $(\bm{x};x_{i}\leftarrow 1)$ we mean a vector which has value $1$ on its $i$-th coordinate and is equal to $\bm{x}$ elsewhere. To create an unbiased estimator for $\frac{\partial G}{\partial x_{i}}$ at a point $\bm{x}$ we can simply sample a set $S$ by including each element in it independently with probability $x_{i}$ and use $g(S\cup\{i\})-g(S\setminus\{i\})$ as an unbiased estimator for the $i$-th partial derivative. We can sample one single $S$ set and use the above trick for all the coordinates. This involves $n$ function computations for $g$. Having a batch size $B$ we can repeat this procedure $B$ times and then average.