A Unified Approach for Maximizing Continuous DR-submodular Functions
Authors: Mohammad Pedramfar
Christopher John Quinn
Vaneet Aggarwal
Venue: NeurIPS 2023 poster (2023)
Keywords: Stochastic optimization
submodular maximization
Frank-Wolfe algorithm

Abstract: This paper presents a unified approach for maximizing continuous DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the general convex set. We consider settings where the oracle provides access to either the gradient of the function or only the function value, and where the oracle access is either deterministic or stochastic. We determine the number of required oracle accesses in all cases. Our approach gives new/improved results for nine out of the sixteen considered cases, avoids computationally expensive projections in three cases, with the proposed framework matching performance of state-of-the-art approaches in the remaining four cases. Notably, our approach for the stochastic function value-based oracle enables the first regret bounds with bandit feedback for stochastic DR-submodular functions.

A Unified Approach for Maximizing Continuous DR-submodular Functions
Mohammad Pedramfar
Christopher John Quinn Iowa State University cj cjquinn@asstate. edu
Vaneet Aggarwal Purdue University vaneet&purdue edu
Purdue University mpedramt amf @purdue. edu
Abstract
This paper presents a unified approach for maximizing continuous DR- submodular functions that encompasses range of settings and oracle access types. Our approach includes a Frank- type offline algorithm for both mono- tone and non-monotone functions, with different restrictions on the general convex set. We consider settings where the oracle provides access to either the gradient of the function only the function value, and where the oracle access either deter- ministic or stochastic. We determine the number of required oracle accesses in all cases. Our approach gives newimmpooed results for nine out of the sixteen con- sidered cases, avoids computationally expensive projections in three cases, with the proposed framework matching performance the remaining four cases. Notably, our approach for the stochastic function value- based oracle enables the first regret bounds with bandit feedback for stochastic DR- DR-submodular functions.
ffte-of-thhear approaches
1 Introduction
The problem of optimizing DR-submodular functions over convex set has attracted considerable interest in both the machine learning and theoretical computer science communities 2 5 16 26)..
This is due to its many practical applications in modeling real-world problems, such influ- ence/revenue maximization, facility location, and non-convex/non-ccocave quadratic programming well as more recently identified applications like serving heterogeneous learners under networking constraints (20) and joint optimization of routing and eaching in networks 21..
3. [8 15 20).
Numerous studies investigated developing approximation algorithms for constrained DR- submodular maximization, utilizing a variety of algorithms and proof analysis techniques. These studies have addressed both monotone and non-monotone functions and considered various types of constraints on the feasible region. The studies have also considered different types of oracles gradient oracles and value oracles, where the oracles could be exact (deterministic) or stochastic. Lastly, for some of the aforementioned offline problem settings, some studies have also considered analogous online optimization problem settings as well, where performance is measured in regret over a horizon. This paper aims to unify the disparate offline problems under a single framework by providing comprehensive algorithm and analysis approach that covers broad range of setups. By providing a unified framework, this paper presents novel results for several cases where previous research either limited or non-existent, both for offline optimization problems and extensions to related stochastic online optimization problems.
This paper presents Frank- based mega-algo for (offline) constrained DR-submodular maximization where we could only query within the constraint set. with sixteen variants for sixteen problem settings. The algorithm is designed to handle settings where (i) the function is monotone
This work was supported in part by the National Science Foundation under grants CCF-2149588 and CCF. 2149617, and Cisco, Inc.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Offline DR-submodular optimization results.
F
Set
Oracle
Setting
Reference
Appx.
Complexity
det.
4]. (*)
1/e
O(1/c)
0 DEX
stoch.
23 (*)
1/e
O(1/e")
32
1/e
O(1/e")
Monotone
det.
This paper
1/e
O(1/69)
stoch.
This paper
1/e
O(1/c²)
[16
1/2
O(1/c)
det.
generalf
VF
This paper
1/2
0(1/e)
[6]
1/2
0(1/c))
stoch.
This paper
1/2
Ó(1/E)
det.
This paper
1/2
O(1/E2)
stoch.
This paper
1/2
Õ(1/c))
det.
3]. (*)
1/e
O(1/c)
VF
stoch.
233 (*)
1/e
O(L/e")
Non-Monotone
d.c.
F
This paper
1/e
O(1/e4
stoch.
This paper
1/e.
O(1/e))
Oleval/g
3/3
general
VF
det.
Olevatie)
10
1
O(1/e)
stoch.
This paper
O(1/e)
det.
This paper
1
O(1/e9)
stoch.
This paper
1
0(1/e))
This table compares the different results for the number of oracle calls (complexity) within the feasible set for OR-submodulla maximization. Shaded rows indicate problem settings for which our work has the first guarantees or beats the SOTA. The rows marked with blue star (*) correspond cases where Algorithm performance. The different columns
generalizes the corresponding algorithm and therefore has the enumerate properties the function, convex feasible region (downward-closed, includes eral), and the oracle, as well as the approximation ratios and oracle complexity (the number of queries needed to achieve the stated approximation ratio with at most > additive error). We have h := minxer) || (See Appendix B regarding [23 and (32.. when the oracle can be queried for any points [o, 1]" (even outside the feasihle region K.), the problem of optimizing monotone DR-submodular functions over general convex set simplifies - 4 and (23 achieve the same ratios and complexity bounds as listed above for 0 K;; [ can achieve approximation ratio of 1/c with the O(L/e") and O(1/c²) complexity for exact and stochastic value oracles respectively. [16] and use gradient ascent, requiring potentially computationally expensive projections.
origin, or gen-
or non-monotone, (ii) the feasible region downward-closed (d.c.) set (extended to include for monotone functions) general convex set, (iii) gradient value oracle access is available, and (iv) the oracle is exact or stochastic. Table enumerates the cases and corresponding results on oracle complexity (further details are provided in Appendix A We derive the first oracle com- plexity guarantees for nine cases, derive the oracle complexity in three cases where previous result had a computationally expensive projection step [32] [6] (and we obtain matching complexity in one these), and obtain matching guarantees in the remaining four cases. In addition to proving approximation ratios and oracle complexities for several (challenging) settings that are the first or improvements over the state of the art, the technical novelties of our approach include:
(i) A new construction procedure of a shrunk constraint set that allows to work with lower dimensional feasible sets when given value oracle, resulting in the first results on general lower dimensional feasible sets given value oracle.
(ii) The first Frank Wolfe type algorithm for analyzing monotone functions over a general con- set for any type of oracle, where only feasible points can be queried.
(iii) Shedding light on previously unexplained gap in approximation guarantees for monotone DR- submouuuaaa maximization. Specifically, by considering the notion of query sets and assuming that the oracles can only be queries within the constraint set, we divide the class of

---

monotone submodular maximization into monotone submodular maximization over convex sets containing the origin and monotone submodular maximization over general convex sets. Moreover, we conjecture that the 1/2 approximation coefficient, which has been considered sub-optimal in the literature, is optimal when oracle queries can only be made within the constraint set. (See Appendix B for more details.)
Furthermore, we also consider online stochastic DR-submodular optimization with bandit feedback, where an agent sequentially picks actions (from convex feasible region), receives stochastic wards (in expectation a DR-submodular function) but no additional information, and seeks to max- imize the expected cumulative reward. Performance is measured against the best action in expec- tation (or near-optimal baseline when the offline problem is NP-hard but can be approximated within a in polynomial time), the difference denoted expected a-regret. For such problems, when only bandit feedback is available (it is typically strong assumption that semi-bandit or full- information feedback is available), the agent must be able to learn from stochastic value oracle queries over the feasible actions action. By designing offline algorithms that only query feasible points, we made possible to convert those offline algorithms into online algorithms. In fact, because of how we designed the offline algorithms, we are able to access them in black-box fashion for online problems when only bandit feedback is available. Note that previous works on DR-submodular maximization with bandit feedback in monotone settings (e.g. 31 25 explicitly assume that the convex set contains the origin.
and 300
For each of the offline setups, we extend the offline algorithm (the respective variants for stochastic value oracle) and oracle query guarantees to provide algorithms and a-regret bounds in the bandit feedback scenario. Table 2 enumerates the problem settings and expected regret bounds with bandit and semi-bandit feedback. The key contributions of this work can be summarized follows:
1. This paper proposes a unified approach for maximizing continuous DR-submodular functions in a range of settings with different oracle access types, feasible region properties, and function properties. A Frank-Wolfs based algorithm is introduced, which compared to SOTA methods for each of the sixteen settings, achieves the best-known approximation coefficients for each case while providing (i) the first guarantees in nine cases, (ii) reduced computational complexity by avoiding projections in three cases, and (iii) matching guarantees in remaining four cases.
2. In particular, this paper gives the first results on offline DR-submodular maximization (for both monotone and non-monotone functions) over general convex sets and for downward-closed convex sets, when only a value oracle is available over the feasible set. Most prior works on offline DR-submodular maximization require access gradient oracle.
The results, summa- rized in Table 2, are pre- sented with two feedback monels-bandi feedback where only the (stochastic)
Table 2: Online stochastic DR-submodular optimization.
F
Set
Feedback
Reference
Coef.
a- a-Regret
1/e
O
Monotone
0
F
This paper
1 1-1/e
O(T3/4)
reward value is available and semi-bandit feedback where single stochastic sample of the gradient at the location is provided.
This paper
1 - 1/e
O(T5/6)
[6]
1/2
O(T1/2)
VF
general
This paper
1/2
Õ(T3/4)
This paper
1/2
Ó(T5/6)
This paper presents the first
VF
This paper
1/e
O(T3/4)
regret analysis with bandit feedback for stochastic DR-
Non-mono
d.c.
This paper
1/e
O(T5/8)
VF
This paper
1-h
O(T3/4)
submodular maximization
general
This paper 1
O(T5/6)
for both monotone and non-
monotone functions. For semi- semi-bandit feedback case, we provide the first result in one case, improve the state of the art result in two cases, and gives the result without computationally intensive projections in one case.
This table compares the different results for the expected a-regret for on- line stochastic DR-submodular maximization for the under bandit and semi- bandit feedback. Shaded rows indicate problem settings for which our work has the first guarantees or beats the SOTA. We have / == minxek || oc. the analysis (6) has an error (see the supplementary material for details). [66] uses gradient ascent, requiring potentially computationally expensive projections.
3

---

Related Work: The key related works are summarized in Tables and 2. We briefly discuss some key works here; see the supplementary materials for more discussion. For online DR- submodular optimization with bandit feedback, there has been some prior works in the adversarial
setup [1 33 25 30 which are not included in Table 2 as we consider the stochastic setup. [1
considered monotone DR- DR-submodular functions over downward-closed convex sets and achieved
(1 1/e)-regret of (11)/9) in adversarial setting. This was later improved by [25] to O(T5/6).
30 further improved the regret bound to O(T*/#). However, it should noted that they use a con- vex optimization subroutine at each iteration which could be even more computationally expensive than projection. [33] considered non non-monoton monotone DR -usuuboou functions over downward-closed convex sets and achieved 1/ ee-regtet of (T78/9) in adversarial setting.
2 Background and Notation
We introduce some basic notions, concepts and assumptions which will be used throughout the paper. For any vector E Rd, [x]; is the i-th entry of x. We consider the partial order Rd where I y if and only if [x]; S [y]: for all 1 S i S d. For two vectors y R the join of x and y, denoted by x V y and the meet of x and y, denoted by x A y, are defined by
(1) respectively. Clearly, we have X A S X S. X V.. We use || I1 to denote the Euclidean norm, and || bloo to denote the supremum norm. In the paper, we consider a bounded convex domain K. and w.l.o.g. assume that K. [0, 1j We say that K. is down-closed (d.c.) if there is point K. such that for all z E K., we have (x u < x I 2} C K. The diameter D of the convex domain K. is defined as D == sxxxxyxxx|lx yll- We use (,)()) to denote the open ball of radius centered at x. More generally, for a subset X C R.4, we define BB, (X) = Unex B,, (x)). If A is an affine subspace of TRd, then we define TBA (X) == A n (X). For a function F D - R and a set L, we use F/c to denote the restriction of F to the set D o L. For a linear space Lo S IRd, we use Pro Rd - Co to denote the projection onto Co. We will use E4 to denote the set {x E R x 2 0}. For any set X C Rd, the affine hull of X, denoted by (X), is defined to be the intersection of all affine subsets of IRd that contain X. The relative interior of set X is defined by
x Vy = (max [x Ivl:)) and X X y == (min [x] 1)
(X) == (x E X 3s > O, Baf(() (x) X).
is well known that for any non- non-empty convex set IC, the set relint is always non-empty. We will always assume that the feasible set contains at least two points and therefore dim 2 1, otherwise the optimization problem is trivial and there is nothing to solve.
A set function f 1) - IR+ is called submodular if for all y E 10, with x 2 y, we have f(x Vx) - f(x) S fly v a) - f(y),
Va E (0, 13dd
(2)
Submodular functions can be generalized over continuous domains. A function F [0, 1] + R is called DR-submodular if for all vectors x,y E [0, 1j with x S y, any basis vector e; = (0, O, 1,0,.- ,0) and any constant e > such that x + ce, E [0, 1]d and y + ce, E [0, 1jd,
holds that
F(x + cc:) F(x) 2 Fly + ce.) - F(y).
Note that if function F is differentiable then the diminishing-returr (DR) property ( is equivalent
to F 2 Fy() for x I y with x,y [0, 1] A function F' D - E is G-Lipschitz continuous if for all x, E D. (x) < G x-lx-yll. yl|. A differentiable function F' D + +R+ L-smooth if for all x,y E D. [VF((x) VF(y) <
A (possibly randomized) offline algorithm is said to be an a-approximation algorithm (for constant (0, 1) with 2 0 additive error for a class of maximization problems over non-negative func- tions if, for any problem instance maxzex: F(z), the algorithm output x that satisfies the following relation with the optimal solution zz
(4) where the expectation is with respect to the (possible) randomness of the algorithm. Further, we assume an oracle that can query the value F(x) or the gradient Fx)). The number of calls to the oracle to achieve the error in 4 is called the evaluation complexity.
aF aF(z") - E(F()] Se

---

3 Offline Algorithms and Guarantees
In this section, consider the problem of maximizing -usumuodula function general convex set in sixteen different cases, enumerated in Table | After setting up the problem in Sec- tion 3.1 we then explain two key elements of our proposed al algorithm when we only have access to a value oracle, (i) the Black Box Gradient Estimate (BBGE) procedure (Algorithm [T] to balance bias and variance in estimating gradients (Section (.2) and (ii) the construction of a shrunken fea- sible region to avoid infeasible value oracle queries during the BBGE procedure (Section 3.3). Our
main algorithm is proposed in Section 3.4 and analyzed in Section 3.5
3.1 Problem Setup
We consider a general non-oblivious constrained stochastic optimization problem
max F(z) := max [xxxp(xxx) [F x)]. zEK
(5)
zeR
where F is a DR-submodular function, and F x + R is determined by z and the random vari- able which is independently sampled according to x z). We say the oracle has variance o² 0, then we say we have access to an exact (deterministic) value oracle. We will use F(z) to denote the random variables F(z, x) where x a random variable with distribution p(iz). Similarly, we say we have access a stochastic gradient oracle if we can sample from function G K. x 2) - such that VF(z) = Ey>a(y=) y) and G' is determined by z and the random variable y which is sampled according to y <(y; z). Note that oracles are only defined on the feasible set. We will use G(z) denote the random variables G(z.y y) where y is random variable with distribution q(iz).
if suPzeK vaTx=p(xxx) [ [z, x)] = o². In particular, when
Assumption 1. We assume that F : [0, 1] - R is DR- oR-submodulaa, first-order differentiable, non- negative, G-Lipschitz for some G < sc, and L-smooth for some L Co. We also assume the feasible region K. is a closed convex domain in [0. 1] with at least two points. Moreover, we also assume that we either have access to a value oracle with variance of 2 0 or a gradient oracle with variance of 2 0.
Remark 1. The proposed algorithm does not need know the values of I., G, on 01- However, these constants appear in the final expressions of the number of oracle calls and the regret bounds.
3.2 Black Box Gradient Estimate
Without access to a gradient oracle (i.e., first-order information), we estimate gradient information using samples from value oracle. We will variation of the "smoothing trick" technique
[7] 31 & 33), which involves averaging through spherical sampling around a given point.
Definition 1 (Smoothing Trick). For function F' D - IR defined on D C _Rd, its d-smoothed
version Fs is given as
Fx(x) = E x- (z)) = E VLB - (0) F((x + &v)],
(6)
where v is chosen uniformly at random from the dim (iinaaff()))dimmmiioonn -dimensional ball Le [B( (()). Thus, the function value F2 (x) is obtained by "averaging" F over sliced ball of radius 8 around x.
(0).
When the value of 8 is clear from the context, we may drop the subseript and simply use F to denote the smoothed version of F. It can be easily seen that if F is DR-submodular, G-Lipschitz continuous, and L-smooth, then is F and [F()) F(x)ll of both functions. Moreover, if F is monotone, then so is F (Lemma 3). Therefore F is an approximation of the function F. A maximizer of F' also maximizes F approxxmmatel..
8G, for any point in the domain
Our definition of smoothing trick differs from the standard usage by accounting for the affine hull containing D. This will be of particular importance when the feasible region is of (affine) dimension less than d. such as when there are equality constraints. When af) = I.d our definition reduces to the standard definition of the smoothing trick. In this case, it well-known that the gradient of the
smoothed function Fs admits an unbiased one-point estimator 14] 17 Using two-point estimator instead of the one-point estimator results smaller variance two-point estimator to the general setting.
27 In Algorithm 1, we adapt the
5

---

3.3 Construction of K55
We want to run Algorithm as a subroutine within the main algorithm to estimate the gradient. However, in order to run Algo- rithm 1, we need to be able to query the or- acle within the set (B)f((((x))) acle can only be queried at points within the feasible set, we need restrict our attention to set Kgs such that B ( (KCs) S K. On the other hand, we want the optimal point of F within K5s to be close to the optimal point of F within K. One way to ensure
Algorithm 1 Black Box Gradient Estimate (BBGE)
I: Input: Point u, sampling radius 6, constraint lin-
ear space Lo, k = dlim(Lo) batch size B
2: Sample i1, ...
i.i.d from S n Lo
(x). Since the or-
3: For = 1 to B, y. <- 2 -u;, Di < 2 ou;
and evaluate Fly:) (, F
4: g g g
k 24
F(y!") - F(y;)) u
5: -.uuuuut g
that is have K3 not be too small. More formally, we want that (B (Kcs) 2 K. for some value of 8' 2 5 that is not too large. The constraint boundary could have complex geometry, and simply maintaining ô sized margin away from the boundary can result in big gaps between the boundary of K. and Ks. For example, in two dimensions, if K. is polyhedral and has acute angle, maintain- ing a margin away from both edges adjacent to the acute angle means the closest point the Ks to the corner may be much more than 5. For this construction, we choose c E relinl(AC) and a real
number r > O such that (Bff(()) (c) C I.. For any d < r, we define
8 -c.
K. =
Clearly if K. is downward-closed, then so is K.g".. Lemma shows that for any such choice of с and r > we have &f < P. See Appendix for more details about the choice of and We will drop 5 the superscripts in the rest of the paper when there is no ambiguity.
Remark 2. This construction is similar to the one carried out in [31 which was for d-dimensional downward-closed sets. Here we impose no restrictions on K. beyond Assumption ! A simpler
construction of shrunken constraint set was proposed in [8] However, as we discuss in Appendix D they require to able to query outside of the constraint set.
3.4 Generalized DR-Submodular Frank-Wolfe
The pseudocode of our proposed offline algorithm, Generalized DR-Submodular Frank-Wolfe, is shown in Algorithm 2. At high-level, it follows the basic template of Trank-Wolfs type methods, where over the course of a pre-specified number of itera- tions. the gradient (or a surrogate thereof)
Algorithm 2 Generalized DR-Submodular Frank- Wolfe
1: Input: Constraint set K,, iteration limit N 2 4, sampling radius 6, gradient step-size (pm \N
2: Construct K.s
3: Pick any 2 E argminzexs, |z]|0o
calculated, an optimization sub-routine
4: go 0
with a linear objective is solved to find a feasible point whose difference (with re- spect to the current solution) has the largest inner product with respect to the gradient, and then the current solution is updated to move the direction of that feasible point.
5: for n = 1 to N do
6: ga t estimate-gratd coaiee-grrazz,,, Zn. 8, aff(K) -1)
7:
8n + (1- Pn 1 + Png.
8:
v, t optimal-directionnl. (g.. kn)
9:
Zn+1 + update (Z,, Vn, E)
However, there are a number of important modifications to handle properties of the objective function, constraint set, and ora-
10: end for
11: Output 2N+1
cle type. For the oracle type, for instance, standard Frank-Wolff methods assume access deter- ministic gradient oracle. Frank-Woo Wolfe methods are known to be sensitive to errors in estimates of the gradient (e.g., see [66.. Thus, when only a stochastic gradient oracle or even more challeng- ing, only stochastic value oracle is available, the gradient estimators must be carefully designed to balance query complexity on the one hand and output error on the other. The Black Box Gradient Estimate (BBGE) sub-routine, presented in Algorithm 1, utilizes spherical sampling to produce an unbiased gradient estimate. This estimate is then combined with past estimates using momentum, as seen in (23), to control and reduce variance.

---

Our algorithm design is influenced by settings. One of the most closely related works is (8) which also dealt with using value oracle access for optimizing monotone functions. They used momentum and spherical sampling techniques that are similar to the ones we used in our Algorithm and the solution update step. In their work, [8] also considered shrunken feasible region to avoid sampling close to the boundary. However, they assumed that the value oracle could be queried outside the feasible set (see Appendix details).
methods that have been developed for specific
However, we modified the sampling procedure
In Algorithm 3, we consider the following cases for the function and the feasible set.
(A) If F is monotone DR-submodular and 0 E K, we choose
optimal-direettinn(::. z,,) argmaa gy), update(Zn, Vn, E) Zn EVn.
and 1/N. We start at point near the origin and always move to points that are bigger with respect the partial order on Rd. this case, since the function monotone, the optimal direction is maximal point with respect to the partial order. The choice of = 1/N guarantees that after N steps, we arrive at convex combination of points the feasible set and therefore the final point is also in the feasible set. The fact that the origin is also in the feasible set shows that the intermediate points also belong to the feasible set.
(B) If F is non monooonne DR OR-submodular and IC is downward closed set containing 0, we choose
optimal-directionlg.. gn. z..) = argmaxvek, -2) (V. gn), update(Zn. Vn, E) = Zn + Vvn
vSI-z.
and = 1/N. This case is similar to (A) However, since F is not monotone, we need to choose the optimal direction more conservatively,
(C) If F is monotone DR-submodular and K. is general convex set, choose
optimal-diroction(g:. 2,.) argmaxvek, gn), update(Za, Vn: = (1- + EVns
and e = ( In this case, if we update like cases (A) and (B), we do not have any guarantees of ending up in the feasible set, so we choose the update function be convex combination. Unlike (B) we do not need to limit ourselves in choosing the optimal direction and simply choose E to obtain the best approximation coefficient.
(D) If F is non-monotone DR-submodular and K. is general convex set, choose
optimal-dircction((.. z,.) argmaxvek, (v. g..., updato(z.. Vn, E) (1 E)z, EVn.
and e = 1og(2)/N. This case is similar to (C) we choose e to obtain the best approximation coefficient.
The choice of subroutine estimate-grad and Pa depend on the oracle. we have access to gra- dient oracle G, we set estimate-grad(2, 6, Lo) to be the average of B evaluations of Pco (Gíz)). Otherwise, Algorithm 1 with input z. 5, Lo- If we have access deterministic gradient oracle, then there is no need to use any momentum and we set = 1. In other cases, we choose Pn. (n+3)375
3.5 Approximation Guarantees for the Proposed Offline Algorithm
Theorem Suppose Assumption 7 holds. Let N 2 4, B and choose e. and > according to Section
3.3 If we have access to a gradient oracle, we choose d = 0, otherwise we
choose 8 E (0,r/2). Then the following results hold for the output 41 of Algorithm
(A) If F is monotone DR-submodular and O E K. then
3DQ1/2 LD N1/3
Vd+
(1 (1-=-)))((²) - - [[
+
+GG(2
(8)
2N
(B) If F is non-monotone DR-submodular and K. is downward closed set containing 0, then
3DQ
LD
Vd+22
/d+2D
e e'FF"z) E[F((N+1))
8GG
(9)
N1/3
2N
r

---

(C) If is monotone DR-submodular and K. is general convex set, then
F(z") - -E]F(ZN+1) 3DQ 3DQ)))og(NN
4DG + LD2 log(
+ 6G -D (10)
2
2N1/3
8N
(D) If F is non-monotone DR-submodular and K. is general corvex set, then
1 (1 (1- - (zll=))))))( -E(F((N+1)] S
3DQV/2
DG + 2LD2
5G P) (11)
1
N1/3
4N
In all these cases, we have
0
det. grad. oracle, stoch. grad. oracle with variance of > 0,
Q = max (12/3 6T2D2 (T22 +
4o
BJ
max(42/3322612 G2 + 4C3G 4243
value oracle with variance oă 2 0,
B
C' is constant, dim D diam(K),, and z is the global maximizer of F on K.
Theorem characterizes the worst-case approximation ratio and additive error bounds for different properties of the function and feasible region, where the additive error bounds depend on selected parameters N for the number of iterations, batch size B, and sampling radius 8.
The proof Parts (A) (D) provided in Appendix
respectively.
when we have access to an exact gradient oracle is similar 24 respectively. Part Part[(C) is the first analysis of Pronk-Wolfe type algorithm over general convex sets when the oracle can only be queried within the feasible set. When we have access to a stochastic gradient oracle, directly using gradient sample can result in arbitrary bad performance as shown in Appendix B of [16]. The momentum technique, first used in continuous submodular maximization in [23], used when we have access to stochastic gradient oracle. The control on the estimate of the gradient is deferred to Lemma 9 Since the momentum technique is robust to noise in the gradient, when only have access value oracle, we can use Algorithm similar to 8] obtain an unbiased estimate of the gradient and complete the proof.
The proof of parts (A) and (D)
to the proofs presented
Theorem converts those bounds to characterize the oracle complexity for user-specified additive error tolerance based on oracle properties (determiniistic/stocaastee gradient/value). The 16 combi- nations of the problem settings listed Table are enumerated by four cases (A)(D) in Theorem of function and feasible region properties (resulting in different approximation ratios) and the four cases 1-4 enumerated in Theorem 2 below of oracle properties. For the oracle properties, we con- sider the four cases as (Case 1): deterministic gradient oracle, (Case 2): stochastic gradient oracle, (Case 3): deterministic value oracle, and (Case 4): stochastic value oracle.
Theorem 2. The number of oracle calls for different orucles to uchieve an a-upproximation error of smaller than using Algorithm is
Case 1: Ô(1/e), Cases 2, Ō(L/e), Case 4: Ô(L/e)).
Moreover, in all of the cases above, if F is non-monotone or E KC, we may replace with O.
See Appendix M for proof.
Online DR-submodular optimization under bandit or semi-bandit feedback
In this section, we first describe the Black-box Explore- Explore-Then-CCe Commii algorithm that uses the offline algorithm for exploration, and uses the solution of the offline algorithm for exploitation. This followed by the regret analysis of the proposed algorithm. This is the first algorithm for stochastic continuous DR -ussuuoddular maximization under bandit feedback and obtains sfate-of-ther for semi-bandit feedback.

---

4.1 Problem Setup
There are typically two settings considered in online optimization with bandit feedback. The first is the adversarial setting, where the environment chooses a sequence of functions Fi, FNv and in each iteration n, the agent chooses a point z, in the feasible set K. observes (2n) and receives the reward Fn, (Zn). The goal is to choose the sequence of actions that minimize the following notion of expected r-regret.
N Σ Fz
Radv == max ZEK
E
Σ (z
(12)
In other words, the agent's cumulative reward is being compared to a times the reward of the best constant action in hindsight. Note that, in this case, the randomness is over the actions of the policy.
The second is the stochastic setting, where the environment chooses a function F : R and stochastic value oracle F. In each iteration n, the agent chooses a point Z, in the feasible set K,, receives the reward ( (F(z)) by querying the oracle in and observes this reward. Here the outer subscript n indicates that the result of querying the oracle at time n. since the oracle is stochastic. The goal is choose the sequence of actions that minimize the following notion of expected a- regret.
N
N Σ
Ratoch == aN max F(z) - E Σ
(((2)))
-NN max F(z) - E zER
F(zn)
(13)
Further, two feedback models are considered bandit and semi-bandit feedback. In the bandit feedback setting, the agent only observes the value of the function Fa at the point 2n In the semi- bandit setting, the agent has access to gradient oracle instead of a value oracle and observes G(z,) the point 2n, where G is unbiased estimator of F.
In unstructured multi-armed bandit problems, any regret bound for the adversarial setup could be translated into bounds for the stochastic setup. However, having non-trivial correlation between the actions of different arms complicates the relation between the stochastic and adversarial settings. Even in linear bandits, the relation between adversarial linear bandits and stochastic linear bandits is not trivial. (e.g. see Section 29 in [9]) While it is intuitively reasonable to assume that the optimal regret bounds for the stochastic case are better than that of the adversarial case, such a result is not yet proven for DR-submodular functions. Thus, while the cases of bandit feedback has been studied in the adversarial setup, the results do not reduce to stochastic setup. We also note that in the cases where there are adversarial setup results, this paper finds that the results in the stochastic setup achieve improved regret bounds (See Table 3 in Supplementary for the comparison).
4.2 Algorithm for DR-submodular maximization with Bandit Feedback
The proposed algorithm is described in Algorithm 3
In Algorithm 3, if there is semi-bandit feedback in
Algorithm 3 DR-Submodular Explore-
the form of stochastic gradient sample for each ac-
Then-Commit
tion 2,, we run the offline algorithm (Algorithm 2 with parameters from the proof of case of The- orem 2 for To 3//4 total queries. If only the stochastic reward for each action z,, is available (bandit feedback), we run the offline algorithm (Al- gorithm 2) with parameters from the proof of case 4 of Theorem for To = [ total queries. Then, for the remaining time (exploitation phase), we run the last action in the exploration phase.
1: Input: Horizon T, inner time horizon
To
2: Run Algorithm 2 for To. with according
to parameters described in Theorem 2
3: for remaining time do Repeat the last action of Algorithm end for
4.3 Regret Analysis for DR-submodular maximization with Bandit Feedback
In this section, we provide the regret analysis for the proposed algorithm. We note that by The- orem 2 Algorithm 2 requires a sample complexity of Ō(1/e²) with a stochastic value oracle for

---

offline problems (any of (A)-(D) in Theorem T.. Thus. the parameters and the results with bandit feedback are the same for all the four setups (A) (D). Likewise, when stochastic gradient oracle is available, Algorithm 2 requires a sample complexity of ((1/c²). Based on these sample complexi- ties, the overall regret of online DR DR-submodular maximization problem is given as follows.
Theorem 3. For an online constrained DR-submodular maximization problem over horizon T, where the expected reward function F. feasible region rype K., and approximation ratio a correspond to any of the four cases (A)-D) in Theorem ? bounded as:
Algorithu 3 achieves o-rrgrett 13
that is upper-
Semi-bandi Feedback (Case 2): O(T)/1),
Bandit Feedback (Case 4): Ö(T5/6).
Moreover, either type of feedback, if F' is non-monotone or 0 E K, we may replace Ô with O.
See Appendix Nfr the proof.
Conclusion
This work provides a novel and unified approach for maximizing continuous DR-submodular func- tions across various assumptions on function, constraint set, and oracle access types. The pro- posed Frank-Wole Wolfe based algorithm improves upon existing results for nine of the sixteen cases considered, and presents new results for offline DR-submodular maximization with only value oracle. Moreover, this work presents the first regret analysis with bandit feedback for stochastic DR-submodulas maximization, covering both monotone and non-monotone functions. These contri- butions significantly advance the field of -usubouuula optimization (with multiple applications) and open up new avenues for future research in this area.
Limitations:
While the number of function evaluations in the different setups considered in the paper are state of the art, lower bounds have not been investigated.
References
[1] Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimiza- tion with multi-point bandit feedback. Adam Tauman Kalai and Mehryar Mohri, editors, Proceedings of the 23rd Annual Conference on Learning Theory (COLT 2010), pages 28-40, 2010.
[2] Francis Bach. Submodular functions: from discrete to continuous domains. Mathematical Programming, 175:419 459, 2019.
[3] An Bian, Kfir Levy, Andreas Krause, and Joachim M Buhmann. Continuous DRssubmodular maximization: Structure and algorithms. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wal- lach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[4] Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guar- anteed Non-convex Optimization: Submodular Maximization over Continuous Domains. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Ar- tificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 111-120. PMLR, 20-22 Apr 2017.
[5] Yatao Bian, Joachim Buhmann, and Andreas Krause. Optimal continuous DR-submodular maximization and applications to provable mean field inference. In International Conference on Machine Learning, pages 644 653.. PMLR, 2019.
[6] Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free online optimization with stochastic gradient: From convexity to submodularity. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learn- ing, volume 80 of Proceedings of Machine Learning Research, pages 814-823, PMLR, 10-15 Jul 2018
10

---

[7] Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximiza- tion. In Amos Storkey and Fernando Perez-Cruz, editors, Proceedings of the Twenty-Fitt First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1896-1905. PMIR, 09-11 Apr 2018.
[8] Lin Chen, Mingrui Zhang, Hamed Hassani, and Amin Karbasi. Black box submodular maxi- mization: Discrete and continuous settings. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statis- tics, volume 108 of Proceedings of Machine Learning Research, pages 1058-1070. PMLR, 26-28 Aug 2020.
[9] Josip Djolonga and Andreas Krause. From map to marginals: Variational inference in Bayesian submodular models. Advances in Neural Information Processing Systems, 27, 2014.
[10] Donglei Du Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization. arXiv preprint arXiv:2205. 12442, 2022.
[11] Donglei Du, Zhicheng Liu, Chenchen Wu, Dachuan Xu, and Yang Zhou. An improved ap- proximation algorithm for maximizing a DR-submodular function over a convex set. arXiv preprint arXiv: 14740, 2022.
[12] Christoph Dürr, Nguyen Kim Thang, Abhinav Srivastav, and Léo Tible. Non-monotone DR-submodular maximization: Approximation and regret guarantees. arXiv preprint 1905. 2019.
[13] Maryam Fazel and Omid Sadeghi. Fast First-Order Methods for Monotone Strongly DR- Submodular Maximization, pages 169-179. ACDA23, 2023.
[14] Abraham D Flaxman, Adam Tauman Kalai, and Brendan McMahan. Online convex op- timization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385-394, 2005.
[15] Shuyang Gu, Chuangen Gao, Jun Huang, and Weili Wu. Profit maximization in social networks and non-monotone DR-submodular maximization. Theoretical Computer Science, 957:113847, 2023.
[16] Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. In Guyon, U. Von Luxburg, Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, vol- ume 30. Curran Associates, Inc., 2017.
[17] Elad Hazan et Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325220) 2016.
[18] Shinji Ito and Ryohei Fujimaki. Large-scale price optimization via network flow. Advances in Neural Information Processing Systems, 29, 2016.
[19] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[20] Yuanyuan Li, Yuezhou Liu, Lili Su, Edmund Yeh, and Stratis loannidis. Experimental de- sign networks: A paradigm for serving heterogeneous learners under networking constraints. IEEE/ACM Transactions on Networking, 3165):2236-2250, 2023.
[21] Yuanyuan Li, Yuchao Zhang, Stratis Ioannidis, and Jon Crowcroft. Jointly optimal routing and caching with bounded link capacities. In ICC 2023 IEEE International Conference on Communications, pages 1130-1136, 2023.
[22] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Conditional gradient method for stochas- tic submodular maximization: Closing the gap. In International Conference on Artificial In- telligence and Statistics, pages 1886-1895. PMLR, 2018.
[23] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. The Journal of Machine Learning Research, (11))4222-42800 2020.

---

[24] Loay Mualem and Moran Feldman. Resolving the approximability of offline and online non- monotone Dussubuouular maximization over general convex sets. In Francisco Ruiz, Jennifer Dy, and aan-Willem van de Meent, editors, Proceedings of The 26th International Confer- ence on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 2542-2564 PMLR, 25-27 Apr 2023.
[25] Rad Niazadeh. Negin Golrezaei, Joshua R. Wang, Fransisca Susan, and Ashwinkumar Badani- diyuru. Online learning via offline greedy algorithms: Applications in market design and optimization. In Proceedings of the 22nd ACM Conference on Economics and Computation, EC 21,, page 737-738, New York, NY, USA, 2021. Association for Computing Machinery.
[26] Rad Niazadeh, Tim Roughgarden, and Joshua R Wang. Optimal algorithms for continuous non- monotone submodular and DR-submodular maximization. The Journal of Machine Learning Research, 21(1):4937-4961 2020.
[27] Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two- point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
[28] Nguyen Kim Thang and Abhinav Srivastav. Online non-monotone DR-submodular maximiza- tion. Proceedings of the AAAI Conference on Artificial Intelligence, 35(11):9888-987, May 2021.
[29] Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265--33 304, 2013.
[30] Zongqi Wan, Jialin Zhang. Wei Chen, Xiaoming Sun, and Zhijie Zhang. Bandit multi-linear DR-submodular maximization and its applications on adversarial submodular bandits. In Pro- ceedings of the 40th International Conference on Machine Learning, pages 35491-35524.
PMLR, 2023.
[31] Mingrui Zhang, Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submod- ular maximization: From full-information to bandit feedback. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Informa- tion Processing Systems, volume 32. Curran Associates, Inc., 2019.
[32] Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodular maximization: Boosting via non-oblivious function. In Proceedings of the 39th International Conference on Machine Learning, pages 261 16-26134, PMLR, 2022.
[33] Qixin Zhang, Zengde Deng, Zaiyi Chen, Kuangqi Zhou, Haoyuan Hu, and Yu Yang. Online learning for non-monotone Subbouuuu maximization: From full information to bandit feedback. In Francisco Ruiz, Jennifer Dy, and Jan Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 3515 15377, PMLR, 25-27 Apr 2023.
12


Reviews:
[{"review_id": "yVAAOzQHje", "reviewer": "Reviewer_GwvC", "summary": "This paper considers the problem of maximizing a continuous DR-submodular function over a convex set, under various settings for the objective (monotone/non-monotone), constraint set (downward-closed/includes the origin/general set), and oracle access types (deterministic/stochastic gradient/value oracle) -- 16 settings in total. For any type of oracle, the oracle is only allowed to query within the feasible set. The authors propose a Frank-Wolfe meta-algorithm and its different variants for each of the considered settings which achieve the best known approximation guarantee in each case. These approximation guarantees are the first ones in nine of the considered settings, reduce the computational complexity in two cases, and match existing guarantees in the remaining five cases. The authors also extend these results to the online stochastic setting with bandit and semi-bandit feedback. They provide the first regret bounds for the bandit setting, and in the semi-bandit setting, they provide the first regret bound in one case, improve over exiting bounds in two cases, and improve the computational complexity in one case.", "questions": "- In Lemma 5, shouldn't d be replaced by k=dim(A) inside the expectation? Applying Lemma 4 with restriction to the first k coordinates is equivalent to applying it with sampling from a sphere of dimension k no? \n\n- Why is the claim on lines 671-672 in Lemma 5 true? Please explain or provide a reference.\n\n- The notations $\\hat{G}(z)|\\_\\mathcal{L}$ and $\\tilde{F}|\\_\\mathcal{L}$ are not defined, which makes it hard to understand some of the proofs. Are these the projection of $\\hat{G}$ on $\\mathcal{L}$ and the restriction of the domain of $\\tilde{F}$ to $\\mathcal{L}$?\n\n- $\\mathcal{L}$ is defined as $\\mathrm{aff}(K)$ in Lemma 9 and the proof of Theorem 1, but in Algorithm 2 it is defined as $\\mathrm{aff}(K) - z_1$.\n\n- I recommend motivating why it is important to restrict the oracle to query only feasible points.\n\n- It would be good to also include known lower bounds for settings where they are available.\n\n- h is not defined in Table 1. \n\n- In the appendix, it is helpful to remind the reader of what different terms refer to or to have a table listing them.", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "\n- The paper provide the first approximation guarantees for various settings of DR-submodular maximization, where the oracle is only allowed to query within the feasible set, and improve over existing results in few other settings.\n- The paper cover a wide range of settings under a unified algorithm and analysis.\n- The presentation of the main paper is very good, especially taking into consideration the amount of material covered.\n- Relation to related work is clear: the authors discuss how their results compare to existing ones, and which ideas/proofs are based on existing work. \n", "weaknesses": "\n- Potential error in Lemma 5 (see questions), which affects all results with the function value oracle. If incorrect, this is easily fixable but the algorithm would require knowing the dimension of the affine hull of the constraint set.\n \n- The presentation in the appendix can be improved to make it easier to read the proofs (see suggestions in questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and helpful suggestions.  Below we reply to your questions in order.\n\n1. You are correct.  In Lemma 5, the ratio $d/2\\delta$ in the expectation should be replaced by $k/2\\delta$ where $k = dim(A)$.\nSimilarly, in Algorithm 1, the ratio $d/2\\delta$ used in line 4 should be replaced with $k/2\\delta$.\nWith these modifications, the algorithms and proofs would be correct as is.\n\n2. For reference, that line is *Note that the function $F$ is defined only on $\\mathcal{D}$ and therefore the gradient $\\nabla F$ lives within the linear space $A$.*  Preceding that we defined $A$ as the affine hull of $\\mathcal{D}$, i.e. $A:= \\text{aff}(D).$  \nWe will include the following explanation in a footnote to clarify the statement.  \nLet $f : M \\to \\mathbb{R}$ be a differentiable function where $M$ is a manifold in $\\mathbb{R}^n$ for some choice of $n \\geq 1$.\nFor each $z \\in M$, the total derivative of $f$, is a linear function $D f(z) : T_z(M) \\to \\mathbb{R}$ from tangent space of $M$ at the point $z$ to $\\mathbb{R}$.\nThen gradient of $f$, i.e. $\\nabla f$ is the vector field on $M$ for which we have $\\langle \\nabla f(z), v \\rangle = (D f(z))(v)$, for all $z \\in M$ and $v \\in T_z(M)$.\nIn particular, since it is a vector field, at each point $z \\in M$, the value of $\\nabla f(z)$ is a vector in the tangent space $T_z(M) \\subseteq \\mathbb{R}^n$.\nAs a special case, if $M \\subseteq A$ where $A$ is an affine space, then the tangent space $T_z(M) \\subseteq A$ for all $z \\in M$ and therefore $\\nabla F(z) \\subseteq A$ for all $z \\in M$.\n\n3. For reference, that notation appears in Lemma 9 (starting on line 716).  \nWe apologize for the confusion.  You are correct.\n$\\tilde{F}|\\_{\\mathcal{L}}$ is the restriction of the domain of the $\\tilde{F}$ to $\\mathcal{L}$ and $\\hat{G}(z)|\\_{\\mathcal{L}}$ is the projection of $\\hat{G}$ onto $\\mathcal{L}$. Before Lemma 9, we will define the notion $\\tilde{F}|\\_{\\mathcal{L}}$ as the function restriction, define $P\\_{\\mathcal{L}}$ as the projection operator and replace $\\hat{G}(z)|\\_{\\mathcal{L}}$ with $P\\_{\\mathcal{L}}(\\hat{G}(z))$ to clarify.  \nWe will also include this notation in a notation table in the appendix.\n\n4. We apologize for the confusion that caused.  We re-used the notation \"$\\mathcal{L}$\" in those places for different affine spaces.  First, we remark that each definition is correct within its respective local scope (Algorithm 2, Lemma 9, Theorem 1). Second, we will revise the notation, fixing $\\mathcal{L} = \\operatorname{aff}(\\mathcal{K})$ and defining $\\mathcal{L}_0 = \\operatorname{aff}(\\mathcal{K}) - z$ (for some $z \\in \\mathcal{K}$) to distinguish between the two affine spaces. \nWe will also include this notation in a notation table in the appendix.      \n\n5. Thank you for the suggestion.  We agree this point should be more clearly motivated. \nPlease refer to the \"global rebuttal\" above for a detailed explanation.\n\n6. We agree.  Including lower bounds (when known) would provide important context for the sample complexity and regret bounds (for offline and online settings respectively) we and the SOTA have obtained.  \nWe will mention lower bounds in the introduction and include a discussion on those results in Appendix A: Details of Related Works.  (In Appendix A.1., we pointed out the optimality of the approximation ratios for two cases (mentioned in the following), but will make clear there and the introduction those are the only cases with tight bounds.)  \nFor reference, we will briefly summarize lower bounds and hardness results. The approximation coefficients are optimal for the case (i) where the function is monotone and the constraint set contains the origin and the case (ii) where the function is non-monotone and the constraint set is a general convex set. For monotone functions over general convex set, we conjecture that $1/2$ is the optimal coefficient (See the \"global rebuttal\" above for more details).\nFor non-monotone functions over downward closed convex sets, the $1/e$ coefficient is known to be sub-optimal. (See the recent paper \"Continuous Non-monotone DR-submodular Maximization with Down-closed Convex Constraint\" by Chen et al, arXiv.org:2307.09616, that obtains 0.385 coefficient) and the best known upper bound so far is 0.491 (See \"Submodular maximization by simulated annealing\" by Gharan et al. 22nd ACM-SIAM, 2011)  \nWith a stochastic gradient oracle, when maximizing a monotone function over a downward closed convex set, the lower bound on oracle complexity is $1/\\varepsilon^2$ (see \"Stochastic Continuous Greedy ++: When Upper and Lower Bounds Match\" by Karbasi et al. in NeurIPS 2019)  \nWe expect the algorithm to be efficient in the deterministic gradient oracle case for all where the approximation coefficient is optimal. This intuition is based on the fact that $O(1/\\varepsilon)$ is a fundamental barrier of linear programming based methods in general within the context of convex optimization. (See \"Conditional Gradient Methods\", Braun et al, arXiv:2211.14103v2, Section 2.1.2)\n\n7. We will revise the caption for Table 1 to include $h = \\min_{z \\in \\mathcal{K}} \\|z\\|_\\infty$.\n\n8. We will follow your suggestions, adding a notation table to the appendix and adding verbal reminders of what notation refers to throughout the paper (esp. in the appendices)."}, {"review_id": "RVywy3je2Z", "reviewer": "Reviewer_L9XA", "summary": "The paper studies maximizing stochastic DR-submodular functions under 16 different settings, which depend on 1) whether the function is monotone or not, 2) the feasible region is a downward-closed or a general convex set, 3) gradient or value oracle access is available, and 4) or the oracle is exact or stochastic. The authors present a unified approach based on the Frank-Wolfe meta-algorithm, which 1) provides the first oracle complexity guarantees in 9 settings, 2) reduces the computational complexity by avoiding projections in two settings, and 3) matches guarantees in the remaining 5 settings. The paper also considers online versions of the problem with bandit feedback and semi-bandit feedback and presents online algorithms with improved regret bounds.", "questions": "1. If possible, please provides more intuition in the main text about what difficulties the construction of a shrunk constraint set is used to solve and how it can solve these difficulties.\n\n2. Very recently, There is a paper titled \"Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits\" [arXiv: 2305.12402, ICML23], which presents a $\\tilde{O}(T^{3/4})$ regret for monotone submodular maximization with adversary bandit feedback. This partially beats your results for bandit submodular maximization. As the approaches are different and the arXiv paper was unavailable during the NeurIPS submission, I do not think it is a \"weakness\". But it is suggested to include the paper in the Related Work.", "limitations": "Yes, as stated in the paper, any non-trivial lower bound for the problem would be exciting.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper provides a unified approach for stochastic DR-submodular maximization, which encompasses a range of settings and beats or matches the SOTA results.\n\n2. The paper presents the first regret analysis for online stochastic DR-submodular maximization with bandit feedback.\n\n3. Technically, a novel construction procedure of a shrunk constraint set is invented that allows us to work with lower dimensional feasible sets when given a value oracle.\n\n4. The paper is organized very well, making it read clearly although there are so many settings. Besides, no typo was found after I read it.", "weaknesses": "1. I notice that only in the case where the value oracle is available, new guarantees that beat the SOTA are provided. So I consider it as the main part of the paper's contributions. In this case, the paper uses many standard techniques like the smoothing trick, the two-point estimator (for estimating gradients), and the momentum technique (for stochastic oracle). And to me what makes the paper different is the construction of a shrunk constraint set. But without reading the appendix, I can not figure out why such a construction is introduced and how it can achieve the claimed guarantees. So, I can not determine whether the paper enjoys excellent technical novelty or just consists of a refined combination of known techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for time and efforts in reviewing our submission.  Below we first provide a response to the points you raised in the \"Weaknesses\" section and then reply to your questions in order.\n\n**Weaknesses**\n\n1. In the \"global rebuttal\" above, we explain the novelty of our work in more detail and reply to your question about the shrunken set construction below.\n\n**Questions**\n\n1. The original version of one-point gradient estimator introduced in [14] is a technique that is used extensively [17, 1, 26, 29, 9, 30] in the literature to estimate the gradient of a function using a single sample. To use this technique for estimating $\\nabla F(z)$, one needs to sample points in a sphere centered at $z$. Therefore, it is only applicable when the function can be queried over an open set in $\\mathbb{R}^d$. In that case, the original constraint set $\\mathcal{K}$ should be shrunk to get $\\mathcal{K}'$ so that an open neighbourhood of $\\mathcal{K}'$ is contained in $\\mathcal{K}$. An example of such construction is done in Appendix D in [29], when $\\mathcal{K}$ is an open downward closed convex set.\nWhen the constraint set is a lower dimensional convex set in $\\mathbb{R}^d$, the technique needs to be modified since no open neighbourhood of $\\mathcal{K}'$ is contained in $\\mathcal{K}$.\nIn Lemma 5, we generalize the one-point gradient estimator from [14] so that it does not require sampling from a sphere. This allows us to propose a new construction that is much simpler than [29] and works for general convex sets.\n\n2. Thank you for bringing this new paper to our attention.  It is exciting to see how active this area is.\nWe will discuss this paper in the related work section. In Table 3 (line 553), we include results for stochastic and adversarial online DR-submodular maximization under bandit feedback. This new paper by Wan et al. belongs to the same category as the reference [29], i.e. in the second row for monotone objective functions with a constraint set that contains the origin ($0 \\in \\mathcal{K}$), which improves the adversarial setting regret bound from $O(T^{8/9})$ to $O(T^{3/4})$.  \nHowever, it should be noted that their algorithm relies on a ``self-concordant barrier'' $\\Phi(x)$ of the constraint set which increases the computational complexity of the algorithm.\nMore precisely, in Algorithm 1, line 13, of that paper we see that in each iteration a constrained optimization problem needs to be solved as a subroutine, for which the objective function is convex, but is not linear (like in our Frank-Wolfe type algorithm) or even quadratic (like in projected gradient ascent works like [16]). \nThus, for some problems, the computational complexity could be significantly higher than even gradient ascent. \nIt is also important to note that the guarantees depend on the existence of a self-concordant barrier. In Appendix D of their paper, they discuss the construction of self-concordant barriers when the constraint set is a product of simplices. It is unclear to us how  computationally expensive it is to  construct a self-concordant barrier for a general convex set containing the origin.  \nWe note that the ICML paper references Niazadeh et al. 2021 ([24] in our paper) as the previous SOTA for monotone online adversarial  with bandit feedback with $O(T^{5/6})$. However, in our submission in Appendix B (lines 618-627), we point out an error in their analysis (due to using stochastic gradient samples for a subroutine designed for exact gradients, without controlling for the subsequent variance such as with momentum).  \nHence, in the paper we will state that the SOTA using only a linear maximization oracle as a subroutine is $O(T^{8/9})$ and the SOTA without being restricted to using linear oracles is $O(T^{3/4})$."}, {"review_id": "MtaDkcvUZw", "reviewer": "Reviewer_f6HN", "summary": "This paper studies offline constrained DR-submodular maximization in 16 different settings (monotone/non-monotone, down-closed/general convex constraint, gradient/value oracle access, and exact/stochastic oracle) and provides a unified approach to solve all 16 cases with the same Frank-Wolfe algorithmic framework. Moreover, the authors extend their tools to study the online stochastic DR-submodular maximization problem under bandit and semi-bandit feedback models. The provided offline and online algorithms either match or improve the state-of-the-art results for each of the various settings.", "questions": "- I noticed that the following paper is missing from your references. In this work, the authors propose a boosting gradient ascent method that improves the $\\frac{1}{2}$ approximation ratio of gradient ascent to $1-\\frac{1}{e}$ for the monotone setting. How do their techniques and results compare to yours?\n\nZhang, Q., Deng, Z., Chen, Z., Hu, H. and Yang, Y., 2022, June. Stochastic continuous submodular maximization: Boosting via non-oblivious function. In International Conference on Machine Learning (pp. 26116-26134). PMLR.\n\n- Is it possible to use your unified approach and provide an analysis for the setting with bounded curvature (similar to what the following paper has done)?\n\nFazel, Maryam, and Omid Sadeghi. \"Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization.\" In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23), pp. 169-179. Society for Industrial and Applied Mathematics, 2023.\n\n-  In the online setting with bandit feedback, how many value oracle queries are necessary per iteration to run Algorithm 3?\n\n--------------------------------\nI've read the authors' rebuttal, thanks for addressing my questions and concerns.", "limitations": "This is a theoretical work and a discussion of potential negative societal impact is not necessary.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Constrained DR-submodular maximization has been studied in numerous works under different assumptions and settings and a number of algorithms have been proposed. In contrast, the algorithmic framework proposed in this paper is general and could be applied to any of the possible settings. \n- The paper is well-written and while the proofs are moved to the appendix, the main concepts and ideas are highlighted clearly in the paper.\n- Algorithm 1 (BBGE) for gradient estimation contains some novel ideas.", "weaknesses": "- While the unifying approach of the paper is interesting, most of the tools and techniques for gradient estimation and the Frank-Wolfe-type algorithm used here have been previously introduced and are not novel.\n- The main contributions of this work are the improved complexity (offline setting) and regret bounds (online setting) and these improvements could be highlighted via numerical examples, however, the paper lacks any experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our submission. We reply to your questions in order below. We also include a discussion on novelty and significance in a general rebuttal box above.\n\n1. Thank you for pointing this out. \nWe first discuss the technique. \nThe technique used in that paper is a combination of a novel line integral, referred to as boosting, and the projected gradient ascent.\nThe boosting method uses a line integral over the line segment connecting the origin to any point $z$ in the constraint set. (see Theorem 2 part ii)\nIn other words, it is working with the assumption that we are allowed to query the oracle on the convex hull of $\\mathcal{K} \\cup \\{0\\}$. (outside $\\mathcal{K}$)\nHence, technically speaking, they are not improving $1/2$ to $1-1/e$ within the same problem space, since $1/2$ solves monotone submodular maximization over a general convex set $\\mathcal{K}$ where we are only allowed to sample within $\\mathcal{K}$.  \nNext, we comment on the results. Briefly, they would beat our method and the SOTA included in Table 1 for one of the sixteen settings -- optimizing a monotone function $F$ over convex sets that contain the origin $(0\\in \\mathcal{K})$, using a stochastic gradient oracle $\\nabla F$.  For that problem,  Zhang et al. achieves an approximation of $1-1/e$ with $O(1/\\epsilon^2)$ sample complexity.  Our method and the prior SOTA [22] achieved an approximation of $1-1/e$ with $O(1/\\epsilon^3)$ sample complexity. We remark that our method, [4], and [22] are Frank-Wolfe type methods and use a linear maximization oracle as a subroutine while Zhang et al. use a quadratic maximization oracle as a subroutine, which for some problems could have high computational complexity. \nSimilarly, in Table 2, the results of Zhang et al. should be included in the same category as [7] and [29] and it will be the SOTA with ($1-1/e$)-regret of $O(T^{1/2})$. However, we again note that they use a projection based method, so our result would be SOTA among projection-free algorithms.\n\n2. Thank you for pointing this out. This is an interesting direction.  It is not immediately clear how the update rule, specifically the value of $v_k$ in Algorithm 3.1. SDRFW in Fazel et al., should change to adapt to other settings as we have studied in order to exploit curvature and strong DR-submodularity to obtain better guarantees. However, we would not be surprised if a unified approach similar in spirit to ours could be applied in the bounded curvature setting and believe it is worth future investigation.\n\n3. For the online setting with bandit feedback, for each time step in the online problem only a single value oracle query is performed (corresponding to a single action taken at each time step and only the stochastic reward being revealed to the agent). The exploration horizon $T_0$ in Algorithm 3 (for bandit feedback we have $T_0 \\gets \\lceil T^{5/6} \\rceil$) is input as the total number of iterations $N$ in Algorithm 2 when the latter is invoked as a black-box subroutine for exploration (so $N \\gets \\lceil T^{5/6} \\rceil$)."}, {"review_id": "rOT1xyS1w7", "reviewer": "Reviewer_Dxab", "summary": "In this work, the authors present a framework for maximizing continuous DR-submodular functions over a range of settings and Oracle access types. To achieve this, they employ a variant of the Frank-Wolfe algorithm which yields either the first guarantees in some cases or comparable results to the SOTA in other cases. The paper is generally well-written, and I have reviewed and found most of the proofs to be accurate. However, I do have a few significant concerns that I would like to highlight as weaknesses. ", "questions": "1. Can you please describe the main novelty of this framework?\n2. Besides the Online Stochastic DR-submodular maximization with Bandit Feedback result, the other results of this paper seem to be a straightforward extension of prior works. The authors need to highlight the challenges faced when proving these more general results and specify how they managed to overcome the challenges.", "limitations": "Yes. The authors adequately addressed the limitations.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "**Major:**\n1. This paper presents the first regret analysis with bandit feedback for stochastic DR-submodular functions maximization.\n\n**Minor:**\n1. Reducing computational complexity by avoiding projections in two cases.\n2. Obtaining the first results on offline DR-submodular maximization over general convex sets and down-closed convex sets.", "weaknesses": "**Major concerns:**\n\n1. This paper lacks empirical evaluation, and it is very crucial since the main contribution of this work is on avoiding computationally expensive projections. \n2. Motivation. In my opinion, this work lacks a very important paragraph/subsection on the importance of the setting where the oracle provides access to only the function value rather than the gradient of the function since the main results in this work are on this setting. For example, provide some applications in this setting.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time in reviewing our paper.\n\n**Weaknesses**\n\n1. For this concern, there are two points we would like to highlight.  \n(1) First, we would like to gently push back on the statement mentioned in the concern that \"the main contribution of this work is on avoiding computationally expensive projections.\"  \nAvoiding potentially computationally expensive projections did inspire our choice of using Frank-Wolfe type methods, similar to most SOTA works for offline and online constrained DR-submodular optimization. \nHowever, for only 3 of the 16 offline problems was a SOTA achieved by a gradient method. Specifically, for monotone functions over general convex set with stochastic/deterministic gradient oracle, in [16], and monotone functions over a convex set containing the origin with access to a stochastic gradient oracle, in \"Stochastic continuous submodular aximization: Boosting via non-oblivious function\" by Zhang et al. ICML 2022 mentioned by Reviewer 6fHN. Note that in one of these cases, namely the one with deterministic gradient oracle in [16], the complexity is the same as the Frank-Wolfe methods up to logartithmic factors. Likewise, for just 2 of the online stochastic problem settings (one row in Table 2 and the Zhang et al. paper mentioned above) were the SOTA a gradient based method.  \nFor those problem settings in offline and online case, the sample complexity (respectively regret bound) is worse for our Frank-Wolfe type algorithm compared to the gradient based method.  That was why we did not highlight our method in the corresponding rows.  \n(2) Second, we note that in all cases where our result matches SOTA, our unifying framework is a strict generalization of the prior works which focused on specific cases (namely, those with a (*) sign in Table 1). Hence, in all those cases, our algorithm reduces to the SOTA algorithm and therefore all of the experiments done in those papers apply to our algorithm as well.\n\n\n2. We agree that the introduction should be strengthened as you suggest.  \n**Motivation for (feasible) value oracle queries:**  We will revise the introduction to better motivate the importance of developing optimization methods for value oracle queries, including just over the feasible region.  We first highlight two points and then discuss application motivations.  \n(1) *Offline-to-online adaptations*  \nFor online optimization problems, when only bandit feedback is available (it is typically a strong assumption that semi-bandit or full-information feedback is available), then the agent must be able to learn from stochastic value oracle queries over the feasible actions action. By designing offline algorithms that only query feasible points, we made it possible to convert those offline algorithms into online algorithms.  In fact, because of how we designed the offline algorithms, we are able to access them in a black-box fashion for online problems when only bandit feedback is available.  \n(2) *More precise characterizations of inherent challenges underlying approximation guarantees*  \nAs noted above, in developing a unifying framework where we took care to characterize how powerful the oracles were, we identified the underlying causes for an approximation gap between gradient ascent and Frank-Wolfe methods.  \n**Applications:**  \nWe will revise the paper by discussing \"classic\" example applications that prior works (like [arXiv:2006.13474]) have shown to be instances of constrained DR-submodular maximization, such as influence/revenue maximization, facility location, and non-convex/non-concave quadratic programming, as well as more recently identified applications like serving heterogeneous learners under networking constraints [arXiv:2201.04830] and joint optimization of routing and caching in networks [arXiv:2302.02508]. We will comment on how strong/mild assuming availability of anything more powerful than a value oracle over the feasible region is. For many problems, the ability to evaluate gradients directly requires strong assumptions about problem-specific parameters. We will briefly mention the application examples in the introduction and elaborate in the appendices.  \nFor example:  \nInfluence maximization and profit maximization form a family of problems that model choosing advertising resource allocations to maximize the expected number of customers, where there is an underlying diffusion model for how advertising resources spent (stochastically) activate customers over a social network.  For common diffusion models, the objective function is known to be DR-submodular (see for instance [arXiv:2006.13474] or [arXiv:2212.06646]). The revenue (expected number of activated customers) is a monotone objective function; total profit (revenue from activated customers minus advertising costs) is a non-monotone objective. Budget limits are typically modeled as linear constraints.  \nOne significant challenge with these problems is that the objective function (and the gradients) cannot be analytically evaluated for general (non-bipartite) networks, *even if all the underlying diffusion model parameters are known exactly*.  \nThe mildest assumptions on knowledge/observability of the network diffusions for offline variants (respectively actions for online variants), especially fitting for user privacy and/or third-party access, leads to instantiations of queries as the agent selecting an advertising allocation within the budget (i.e. feasible point) and observing a (stochastic) count of activated customers. This corresponds to stochastic value oracle queries over the feasible region (respectively bandit feedback for online variants).\n\n**Questions**\n\nWe have included a discussion on novelty and significance in a general response box above. While the online stochastic setting is a novelty of our work, we have not listed it as one of the main technical novelties in here or in the submitted article since it is a relatively simple extension of the main results."}]

Author rebuttal:
We highlight our technical contributions (in addition to contributions in obtaining new guarantees for numerous offline and online settings as well as unifying algorithm design and analysis among several prior works).

1. **Our procedure is the first Frank-Wolfe type algorithm for analyzing monotone functions over general a convex set when the oracle is only allowed to query within the feasible set, for any type of oracle for the objective function (exact/stochastic value/gradient).**  
Note that the algorithm in this case is the same as the algorithm for non-monotone general convex case, only with a different step-size.
The main challenge here was recognizing that the analysis for the non-monotone general convex setting and the monotone setting where the convex set contains the origin could be combined to prove regret bounds for this algorithm.

2. **A new construction procedure of a shrunk constraint set that allows us to work with lower dimensional feasible sets when given a value oracle, resulting in the first results on general lower dimensional feasible sets given a value oracle.**  
*Please refer to Q.1 in the response to Reviewer L9XA for details about differences with prior works.*

3. **Our work sheds light on a previously unexplained gap in approximation guarantees for monotone DR-submodular maximization.**  
(We briefly mentioned some of the following in our paper, but will revise the main section and appendices to make the following clear.)  
Specifically, some prior works (enumerated below) studying monotone DR-submodular maximization over general convex sets obtained guarantees of $1/2$ while others obtained $1-1/e$.   
In [16], a $1/2$ guarantee was obtained by a projected gradient ascent method and this was shown by proving that the algorithm tends to a stationary point and proving that any stationary point is at least $1/2$ as good as the optimal point. Moreover, they construct examples with stationary points that are no better that $1/2$ of the optimal point.  
The $1-1/e$ guarantee was reported for Frank-Wolfe methods, which (superficially) suggests that the gap may be due to algorithm or analysis differences. However, in carrying out our work on developing a unified framework, we identified that the gap was not attributable to algorithm or analysis differences, but instead due to queries to infeasible points by the Frank-Wolfe methods (i.e. they were solving different problems). 
A key ingredient to obtain $1-1/e$ was the ability to query the (gradient) oracle within the convex hull of $\mathcal{K}\cup\{0\}$.
(Note that this is true for both Frank-Wolfe based methods and for projection based methods. Please refer to response to Question 1 of reviewer f6HN for more details about the projection based methods.)
For monotone submodular maximization over general convex sets (not necessarily containing the origin), we can only guarantee a coefficient of $1/2$, both for Frank-Wolfe type methods (our work) and projection based methods (i.e. [16]).  
Moreover, it is evident from our proofs that the case of maximizing a monotone function over a general convex region  with the origin infeasible ($0 \not \in \mathcal{K}$) is the only case where the starting point ($\mathbf{z}_1$ in our paper) of the algorithm does not matter.  
To the best of our knowledge, in every paper where the $1/2$ approximation coefficient and $1-1/e$ approximation coefficient in the monotone setting are compared, the comparison was unwittingly between problems that are inherently mathematically different: 
[16] and [8]  in experiments and main text; 
[7] and [9] in experiments; [30], [23], and [13] in related work section, [22] in the introduction  and Table 2, ”Stochastic continuous submodular Maximization: Boosting via non-oblivious function” by Zhang et al. ICML 2022 in the main claim; and ”Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization.” Fazel et al. (ACDA23), 2023  in the main claims.  
In other words, the $1/2$ approximation could very well be optimal in its own setting. We will add this explanation and the following conjecture to the final version.  
**Conjecture**: *The problem of maximizing a monotone DR-submodular continuous function subject to a general convex constraint, where the oracle access is limited to the feasible region, is NP-hard. For any $\epsilon > 0$, it cannot be approximated in polynomial time within a ratio of $1/2 + \epsilon$ (up to low-order terms), unless $RP = NP$.*  

**Minor correction to Tables**  
In Table 2, we cite 4 papers, but 2 of them ([29] and [30]) are referring to a method known as Mono-Frank-Wolfe, which is not for online stochastic setting since they choose one point but query feedback for another point.   The feedback model Mono-Frank-Wolfe relies on is more informative than the semi-bandit gradient $\nabla F$ feedback included in Table 2. Moreover, the paper [8] mentioned in Table 2 should be replaced with [16] since in the special case considered in Table 2, both algorithms will be the same and it was first proposed by [16].
As we have discussed in rebuttals below, the papers mentioned by reviewers L9XA and f6HN should also be added.

Meta-review: The paper addresses a significant problem by studying the maximization of stochastic DR-submodular functions across a diverse range of settings. These settings encompass factors such as monotonicity, feasible region characteristics, oracle access, and the nature of the oracle itself. The authors propose a unified approach grounded in the Frank-Wolfe meta-algorithm. Their contribution includes establishing oracle complexity guarantees, reducing computational complexity through innovative techniques, and matching guarantees in specific settings. Additionally, the paper extends its focus to online versions of the problem, showcasing algorithms with enhanced regret bounds under bandit and semi-bandit feedback scenarios.

I find the paper to be a commendable work, offering a strong and well-founded theoretical contribution that builds upon existing research in this domain. The authors' approach is notably comprehensive, addressing multiple dimensions of the problem and presenting novel insights.

Considering the above, I would recommend accepting the paper for inclusion in the conference proceedings.
Decision: Accept (poster)