Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints
Authors: Guanyu Nie
Vaneet Aggarwal
Christopher John Quinn
Venue: NeurIPS 2024 poster (2024)
Keywords: DR-submodular
long term constraint
gradient ascent
Primary area: online_learning

Abstract: In this paper, we consider the problem of online monotone DR-submodular maximization subject to long-term stochastic constraints. Specifically, at each round $t\in [T]$, after committing an action $\mathbf{x}_t$, a random reward $f_t(\mathbf{x}_t)$ and an unbiased gradient estimate of the point $\widetilde{\nabla}f_t(\mathbf{x}_t)$ (semi-bandit feedback) are revealed. Meanwhile, a budget of $g_t(\mathbf{x}_t)$, which is linear and stochastic, is consumed of its total allotted budget $B_T$. We propose a gradient ascent based algorithm that achieves $\frac{1}{2}$-regret of $\mathcal{O}(\sqrt{T})$ with $\mathcal{O}(T^{3/4})$ constraint violation with high probability. Moreover, when first-order full-information feedback is available, we propose an algorithm that achieves $(1-1/e)$-regret of $\mathcal{O}(\sqrt{T})$ with $\mathcal{O}(T^{3/4})$ constraint violation. These algorithms significantly improve over the state-of-the-art in terms of query complexity.

Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints
Guanyu Nie Iowa State University Ames, IA 50010
Vaneet Aggarwal Purdue University West Lafayette, IN 47907 vaneetopurdue.eed edu
Christopher John Quinn lowa State University Ames, IA 50010 cjquinn@iastate. edu
nieg@iastate.ddi edu
Abstract
In this paper, we consider the problem of online monotone DR-submodular maxi- mization subject to long-term stochastic constraints. Specifically, at each round E [7]. after committing an action Xt, random reward fx(x+) and an unbi- ased gradient estimate of the point V fx())) (semi-bandit feedback) are revealed. Meanwhile, budget g: (xt), which is linear and stochastic, consumed its total allotted budget Br. We propose gradient ascent based algorithm that achieves 1 -regret of ((VT) with ((T3/4) constraint violation with high probabil- ity. Moreover, when first-order full-information feedback is available, we propose an algorithm that achieves (1 - 1/e) rregrett O(TT) with (T73/4) constraint violation. These algorithms significantly improve the state-of matteoofthh--ae in terms query complexity.
1 Introduction
Online optimization confronts diverse challenges as information gradually unfolds, compelling irreversible decisions at each step amidst uncertainty about future information. Typically, an online optimization problem can be framed as recurring game between a learner or algorithm and an adversary environment: during each iteration, the learner chooses action from a predefined domain set, and the environment subsequently reveals feedback in the form of utility or reward for the selected action. Over time, the learner aims learn from past experiences and improve decision- making strategies to maximize cumulative rewards.
In instances where the objective function is concave and the feasible set is convex, the problem has been extensively explored in the literature under the name online convex optimization (OCO) [33. OCO has found considerable success in various machine learning applications, leveraging the well-established theories of convex optimization. Within OCO, is established that any algorithm incurs a regret of ((VT) the worst case [13]. Notably, there exist algorithms that match this lower bound, such as Online Gradient Descent (OGD) 43
Even though optimizing convex/concave functions can be done efficiently. most problems in artificial intelligence are non-convex. Examples include training deep neural networks, Bayesian inference, and clustering, among many others. One important example of such functions called submodular set function. Submodular set functions exhibit natural property known as diminishing returns, akin to concave functions continuous domains. They have been applied in various machine learning contexts, including viral marketing [16], sensor placement []T], recommendation systems (23), data summarization [22]. and numerous others. However, submodularity extends beyond set functions and can also be defined for continuous functions. DR DR-submodularity represents special class of such continuous functions [
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In the realm of online DRssuboodular maximization, two primary types of algorithms have received extensive attention. Gradient ascent algorithms are often favored for their simplicity and lower gradient sample complexity, while Trank-Wolfe algorithms offer the ability to avoid potentially costly projection operations [9]. The type of feedback also plays a pivotal role in algorithm design. Frank- Wolfe algorithms typically assume more information is acquired each round, assuming that upon committing an action, the agent can observe the entire function, and gradients of multiple points can be observed. This feedback type is often referred to as full information feedback. On the other hand, gradient ascent-based algorithms usually assume only the function value of the chosen action and the gradient at that point can be observed. This feedback type is often referred to as semiibandir feedback. Recent efforts have aimed to enhance gradient queries for Frank- Wolfe algorithms, albeit at the cost of worse regret [4I.
In numerous applications, aside from the goal of maximizing the cumulative reward, there exist constraints on the sequence of decisions made by the learner that must he satisfied on average [ In such scenarios, long-term constraints pose challenges because the decision-maie makinng process cannot be simply expressed as restricting the set of actions for all time steps may be sub-optimal. Instead, the learner still (always) wants to maximize cumulative reward, but if putatively instantancously high reward arms are expensive, can only play them few times. To illustrate, let's consider the online ad allocation problem encountered by an advertiser. At each round t E [T], the advertiser faces the task of determining the allocation of funds across n different websites for placing ads. While the primary aim is to maximize the overall click-through rates of the ads, the advertiser is also constrained by predetermined budget allocated over specified time horizon 4. In this scenario, the cost of ad placement in each round may either be fixed and known in advance, or it may depend on the number of clicks the ads receive, which remains uncertain in advance. As result, the advertiser must navigate the trade-off between optimizing the total reward and adhering to budget constraints.
In this paper, we study the problem of online DR-submodular maximization with long-term (linear) budget constraints. While most prior works assume the objective function is chosen adversarially we study the stochastic DR-submodular maximization setting, where the objective functions are i.i.d. sampled from a distribution 7 12]. Note that this setting is still of interest because opposed to assuming each arriving function fo being DR-submodulaa,
100 29 31,
only assume the expectation of ft to possess oo-suooooularrty Moreover, we consider the aani-bandit feedback setting where only the noisy function value fx(x;) and unbiased gradient estimator of that point f (x₂) can be observed. To the best of our knowledge, these particular settings (stochastic utility and semi-bandit feedback) have not been explored in the literature on oRsuubmod maximization with long-term constraints.
Our Contributions: We summarize our contributions in three parts.
1. In the semi-bandit feedback setting, we propose the first stochastic gradient ascent based algorithm for stochastic online DR-submodular maximization with stochastic long-term constraints. Our proposed algorithm can achieve ((VT) 1 -regret and (T3/4) constraint violation with high probability. Compared to all previous works [10] 29 BT, they consider first-order full-inffe aall-information feedback and require unbiased gradient estimates at VT locations (not just action x,) in every round. For those works, their query complexity in each round is VT while ours is just 1.
2
2. In first order full-information setting, where the unbiased gradient estimates of any point can be observed, we propose the first stochastic gradient ascent based algorithm for stochastic online DR- submodular maximization with stochastic long-term constraints. We utilize the recently developed technique in [42] called the non-oblivious function. Our proposed algorithm can achieve ((VT) (1 - 1/e)-regret and (T3/4) constraint violation with high probability. Again, compared to our query complexity is significantly lower.
previous works 10 29
Regarding the approximation ratios: We note that in offline 1- 1/e is known to be the optimal approximation ratio for optimizing monotone DR submodular functions over general convex set, where the query can be anywhere in the convex hull of (0) (K the constraint set). However, when the oracle calls are restricted to K., an approximation ratio of 1/2 is the best that is known to be achievable (28). Thus, full information feedback can achieve 1 e/e-regret while the semi-bandit feedback achieves 1/2-regret.

---

Table 1:
We include related works from online DRssubmodular optimization with constant stochastic long term constraint functions. (Works handling adversarial long-term constraints require different definition of regret.) All methods require gradient oracle for feedback, and "Noise' lists whether the gradient is exact or there is stochastic noise. "# Grad.' is the number gradient evaluations required per-round. 'Con. Viol.' is the bound on the constraint violation. f [31] considered constraint set being convex while all other works consider linear constraint. In '# Grad.' column, 2vT means this work needs vT gradients on both f and g- While all actions will be feasible, some gradient queries will be in the convex hull of K. (0).
REFERENCE
REGION
NOISE
# GRAD.
APPROX.
REGRET
CON. VIOL.
29
0 E K 0 E K 0 E KC
VT
1-1/
O(VT)
Õ(VT)
BIT
X
2/T
1-
1/c
O(VT)
O(VT)
10
VT
1- 1/e
O(VT)
O(VT)
29
0 E KC
V
VT
1- 1/e
O(T3/4)
Õ(VT)
THEOREM
GENERAL
V
I
1 1 1/e
O(VT)
O(T9/4)
THEOREM
GENERAL
V
((SEM))
1/2
O(VT)
O(T9/4)
2
Related Works
The primary related works summarized in Table T We briefly discuss notable contributions and for additional related works, see Appendix F
Online DR-submodular Maximization with Long- Term Constraints We do not compare results with adversarial constraints due to additional assumptions needed in this setting. See Appendix F for detailed discussion. In the context of stochastic constraints, Raut al. 29 conducted the initial study of the problem. They successfully attained O(VT) regret and constraint violation with high probability, as well as (T3/1) regret and O (VT) constraint violation in expectation. Building upon this work, Sadeghi et al. [31] further improved the results to achieve ((VT) regret and constraint violation, both in expectation and with high probability. Additionally, Feng et al. [10] extended these findings to incorporate weakly DR OR-submodular utilityy, achieving analogous results.
Online Convex Optimization with Long-Term Term Constraints Several results for OCO with determin- 37
40 Existing literature has established that a regret of O (vTT) and a cumulative constraint violation of 1/44 can be achieved without the Slater condition. Conversely, assuming the Slater condition allows for achieving regret of O ((T)) and cumulative constraint violation of (1). In cases where the considered constraint assumed to be stochastic, Yu et al. [39 achieved a ((VT) bound on both regret and constraint violations under the Slater condition. Furthermore, Wei et al. (35] achieved the same regret and constraint violation bounds while assuming a strictly weaker assumption than the Slater condition.
istic long-term constraints can be found in [4] 20
38
Preliminaries
3.1 Notations
Vectors are shown by lowercase bold letters, such as x Rdd, We denote by || Il the E (Euclidean) norm. We [T] to denote the set (1.2.... ,T. The inner product of vectors x,y E Rd is denoted by either yx x y. For
R. define [u]+ == max(u, 0}. For two vectors y E Rd x 3 y implies that S yi, Vi E [d]. For convex set X', we denote the projection of y onto set X' as (y) = arg milxex x - y|
3.2 Function Properties
Here we list some function properties that will appear in our assumptions.
Monotonicity A function f is monotone if fxx I f(y) for all x 3 y.

---

Lipschitz continuous A function f is Lipschitz continuous with parameter 3 if for any x, y E X, we have f(x) f(y)= - 3||x x y//-
3.3 DR-Submodular Functions
function f : + R4,, defined on the ground set S2 is said to be submodular if
+ 2 f(AUB) f(A
for all A, B C Ω. The notion of submodularity has been extended to continuous domains 34 36 Consider function f : X -> R+ where the domain is of the form X' IT==1 X, and each X; is
a compact subset of IR.. We say that f is continuous submodular if f is continuous and for all
x, X, we have
f(x) + f(y) 2 f(x V + f(xAy)
where x V y and X y are component-win wise maximum and minimum, respectively. For efficient maximization, we also require that these functions satisfy diminishing returns condition S We say a differentiable function f is continuous DR -ussubmodular f it satisfies
fx(x) N ff(y)
for all x x y. When the function f is twice differentiable, Dusuubnodularity is equivalent
8 f(x) dr,Or,
I 0, Vi, Vx
The following lemma is an important property of monotone DR-submodular functions. Lemma 1. Let f. : + R+ be monotone, differentiable, DR-submodular function. For any two vectors x, y E X, we have
fly) - -f(x2 S (Vf(x). x).
The proof can be found in the proof of Theorem 4.2 in 11). Note that this property shares an analogy
with a pivotal characteristic that defines concavity: f(y) fxx S (Vf(x). x). Lemma [ also implies that if we use gradient descent directly on f. we can only achieve an approximation ratio of 1/2. Zhang al. [42] introduced the so-called non-oblivious function to obtain the optimal approximation ratio of 1 - l/e:
Lemma 2. Let f X + IR+, be a monotone, differentiable, DR-suboodular funtoda,, and let F be the non oblivious function of f defined by its gradient V (x fo e² Vf(z e=
x)dz. Then for any
vectors x, y E X, we have
(VF(x).y-x) x)
The proof of Lemma can be found in 42
4 Problem Statement
Consider the following offline optimization problem:
max f(x)
subject to g(x) s 0,
where gxx) (p.x) b for some non-negative constant b. We study an analogous online setup as follows: At each round E [7], the algorithm chooses an action x, K, where K. C R4 is fixed, known set. We consider both the utility and the constraints being stochastic, where we assume each time step, the utility function Se sampled i.i.d. from a distribution D, with mean f. i.e., = Ejo-D, J(-), while the cost vector P, is i.i.d. sampled from another distribution Dp. After
an action is selected by the learner, a random reward fe (x,) is obtained while using (p,, (p), of its fixed total allotted budget Br, and P, is observed. In the semi-bandit setting, an unbiased gradient estimator for that action, (xx)), is also revealed. the first order full-information setting, the unbiased gradient estimator of any point can be observed. In this paper, we consider both settings while all other works in the literature on Dussuuuod maximization with long-term constraints, such [10 29 31). consider dill-information feedback.

---

To make sure the long-tem term constraint is not vacuous, we consider By bT for a constant b such that minxex x) S maxxex (p. x). In this case, there will always be a solution x that satisfies constraint (having zero constraint violation) and it is not the case that any sequence of actions (especially the most expensive w.r.t. p) feasible.
We make the following assumptions to proceed our analysis:
Assumption 1. The constraint set IC is convex and compact, with diameter d = sup yEE |x yl and radius r = suPxex ||x||. Since X' is compact, we denote its diameter as d = suPx.yEX x- y and radius as f = SUPxxx' |x||, respectively.
Assumption 2. The expected utility function f(-) is monotone DR-submodular and B ~Lipschhi.
Assumption 3. The distribution D, for the cost vectors has bounded support 3, n R4 with mean p O. where B is the unit ball of Euclidean norm.
Assumption 4. The gradient oracle is unbiased [xV - = and has a bounded variance V (x) (x) s o². In the semi-bandit setting, we assume G max, supx [ fxx))l finite. In the first order full-information setting, denoting the unbiased estimator of the non-oblivious function obtained at round by (F((x), we assume Gp =
max; supx V Fr (x)l is finite.
we do not assume bounded smooth- ness on the gradients: fx() f(y) S x mox-ylln yll. Moreover, we do not assume f(0) = O.
Unlike Frank-Wolfe type algorithms in other papers [10 21
Our overall goal is to maximize the total obtained reward while satisfying the budget constraint asymptotically (i.e.. Ei (p. xx) Br being sub-linear T).
Note that our proposed algorithm can handle multiple linear constraints as well, and similar regret and constraint violation bounds can be derived. In the case of there constraints g:(-), i [m], we can define g(x) := max4e[m] (x) and it can be shown that preserves the same properties those of individual yı 's (sub-differentiabbiity bounded (sub-)gradients and bounded values; Proposition 6 in (00 for proofs).
For simplicity of presentation, we denote 3 max 3pp. Since K. is compact, from mono- tonicity of f we have Fi == maxxex [xx) is bounded. Since f is 8y-Lipschitz, we have F2 == maxx.yex lx() - f(y) S B,D is bounded. Since IC is compact and D, has bounded support, have C. == maxp'~D, maxxex (p', x) 4p is bounded.
To measure the effectiveness our proposed algorithm, we use the notions of regret and total constraint violation to quantify the overall utility and the total resource consumption, respectively.
Regret typically defined as the difference between the total reward accumulated by the algorithm and the best fixed action in hindsight. Note that even in the offline setting, maximizing a monotone susuuuuau function subject a convex constraint can only be done approximately in polynomial time unless RP NP [5] Thus, we instead use the notion of a-regret of an algorithm.
Definition 1. The a-regret an online algorithm with outputs {x, YT is defined as
T
RT OE max
E - S(x),,
1=1
[=1
where KC" is the restricted search space of solutions that satisfy long-term constraints for T steps, (i.e.,
can be played T times), K {x K. ET - g(x) < 0}. which is also equivalent satisfying per-round constraint: KC* = {x E K. g(x) 0).
Since are mainly interested in stochastic utility functions, i.e., Dj, we aim minimize the expected a-regret:
T
E[Rr] = aT max f(x) xek.
f(x).
Denote x" arg maxxex- f(x). Note that since P, is drawn i.i.d. from the distribution DD with mean p Vt [T', the best benchmark action is with respect the "truc" underlying p of the constraint
5

---

function as opposed to It is possible that the best-fixed action has constraint violation with some noisy P, 's.
We next define the total constraint violation. Definition The total constraint violation an online algorithm with outputs (x+]== is defined as
T Cr == Σ (x1) = (p. - Br.
T
t=1
Again, in the stochastic constraint setting, the total constraint violation is defined with respect to the mean p.
An Efficient Primal-Dual Algorithm under Semi-bandit Feedback
In this section, introduce first proposed algorithm for online DR-submodular maximization subject to stochastic long term constraints under semi-bandit feedback: Online Lagrangian Stochastic Gradient Ascent (OLSGA). The algorithm is presented in Algorithm The overall structure of the algorithm is inspired by the primal-dual update in Online Convex Optimization (OCO) (e.g., (20).
Associating a dual variable À [0, +oo) with the constraint, the saddle point formulation of (I can be written as
min xo)o,+oo)
f(x) (x))..
In this work, we consider the following regularized Lagrangian function L(x, X) given by
[(x, A) = f(x) - Ag(x) + 2 X2.
8n
It is important to observe that the expression in deviates from the conventional Lagrangian due the inclusion of the term bn X2, where both and rj are parameters that will be later chosen optimize theoretical guarantees. The main purpose of this modification is to control the value of achieve the goal restricting À to
and prevent it from growing large. Although bounded domain, using the quadratic regularizer makes convenient for our analysis.
One issue is that (shown in g(x)) is unknown to the online algorithm. Therefore, we alternatively empirical estimate P. - Ps instead of p the Lagrangian function. Moreover, in order to achieve the high probability bound, we adjust our Lagrangian function in (3) as follows:
87
Ax(x, f((x) (x)
+
2
where (x) (p. x)
By
% and 7
20 220
log( 2I
For the purpose of analysis, we further
T
define (x) : (P,,
Br
7
For the purpose of analysis, we do directly use Equation our primal update. Let E, be defined by its gradient, VxZ,(x,, fx(x))) - 2A, Vg. (xx). The primal updates are formulated as follows:
X (x V. A.))-
Note that compared Equation the Lagrangian function used for updating has coefficient of in front of the second term.
Our proposed algorithm is shown in Algorithm [ The algorithm proceed follows: it takes convex constraint set K. and a time horizon as inputs. Initially, the algorithm selects an initial point At each time step f [T), the algorithm takes action xt, acquires reward fx(xx), and observes the cost vector P; as well as an unbiased gradient estimate (.x( Subsequently. unbiased gradient estimates of the updating Lagrangian function with respect to x and to are computed using the empirical estimate p. Using these calculated gradients, updates and À made using and ( respectively.
X1 E K. and sets À

---

Algorithm OLSGA (Semi-bandit Feedback)
1: Input: Convex set X, time horizon T
2: Initialize X1 E K, A1 = 0.
3: for E [T] do
4: Play X obtain f((x;) and (xx,) and Pt
5: Compute p. = 2 Ps
6: Compute
V (x,, 2x) (x((x,)) 2Ax (x,,
(5)
Vx dx) -x((xx,) + 5mp4
(6)
7: Update Xz and Ae:
X++1 = Ix(x; + 17 Ci Ae))
(7)
A411 (1 (he 17 X Xt))
8: end for
Remark 1. A notable difference between our algorithm and all prior works addressing online DR- submodular maximization with long-term constraints (e.g., [1) is that algorithm can handle search spaces that do not necessarily include O. This distinction bears importance, particularly when considering scenarios where we can only query values within the constraint
In such cases, 1/2 has been conjectured to be the optimal approximation ratio ((28) section B in Appendix). We refer to Appendix H for motivation examples where searching over KU [O) is not applicable.
Now, we establish the regret and constraint violation achievable by our proposed Algorithm 1 Before delving into the main theorem, we first present three lemmas, which are adapted from [2] and essential for achieving high probability bounds. Given the slight difference in the definition of p. we provide the proofs in Appendices A C respectivel. First, Lemma demonstrates that with high probability, the empirical estimate is close to its mean p.
Lemma 3. The following holds with probability at least
T E -Ppp-Pl Q3,
2nT
Tlog
where Q > is some universal constant.
Next, Lemma 4 establishes that with high probability, the g(-) computed using p, and g(-) calculated using p are close.
Lemma Let x E be fixed. For a fixed E [T] and {+= 22 g(x)l S Tt. holds with probability at least - G.
(x.
1=1
Finally, Lemma 5 an upper bound for the total constraint violation.
Lemma 5. Let (Tr) be defined as in Lemma 4 then the following holds:
Cr
ge (xx) +
p..
pll
+
(9)
Armed with these results, we can now establish regret and constraint violation bounds for Algorithm [ Theorem Let Assumptions
be satisfied. Let mmax(G, C}. Choose 7) = UVF
and 8 832. Let X1...., XT be the sequence of solutions obtained by Algorithum | When T is sufficiently large, i.e., T 64d ga
U we have the following rergrtt and constraint violation bounds
with probability at least 1
E [r] O(VT) and CT O(T3/4).
7

---

The complete theorem statement and the complete proof are in Appendix D
Parfial Proof: From the update of Xt, have that for any K.
Xx++ x||²
||[ X + V Eg (Xe, Ae)) x|1
X + 2, x,, 2,) - =
X x|2 V (x1, X+) 21)(x xx)x-xx)VVxii(ee
(10)
Rearranging, and using Assumption 4 and Assumption we have
(x - x.) V Cxt, Ar)
(xt,
(1xx - - - xx1 + + 4n (11)
21)
Applying similar steps on the À updates, we establish
(A - From monotonicity and DR-submodularity of [x)], we have
(112
211 1eet1 All2) c²n 2nr 27 (12)
2n
ExC,(x, A - 20, (x::
= EE xx )1) 2Lr (x)[
δn X2
< B[(x xx) T V
Ae) xxI] (x)x(()
(Lemma 1
1
[[[[x x|| 2- x1+1 x $| G2n 4n X2 AxTi(x) 811 x
$ 2n
(13)
where 113) follows from Similarly, from convexity of function Li(x, X) w.r.t X, we have
Li(x,, 2) (x,, Ac)
(A x+) T VXCe(xe, Ae)
(1 alI 11x441 All C² - 2 28 (14)
21p
where 14
follows from
12 Subtracting two times
from 13). and sum t over through T, we
get
T
E L (x, No) - (x,
d
x²
T
T
8n
<
+ + G2T + n
Σ
x + 20"
TT T + 4n Σ
2 +
Σ tm1
X + \x0
X²
2m 1
2
t=l
(15)
Expanding the left hand side of (15 and rearranging, deduce
Stj + ( x2
Σ -f(x)=2(xx))) +
2A
ge
(xx)
1=1
1=1
d2
(x) + (432 4522
8) Σ
X
G 20 + 4n Σ πt. (16)
2n
To ensure that the equation 4,82 + 462,,² - 0 has real roots, we require T >
61d2
02- Setting
0
5 = 8,32 ensures that 43 + 2 - 0-6 0. Set = x"; From Lemma with probability at least
1- f. de (x*)
(xx) --- 7t I gxx)) holds. since x satisfies the long term constraint, have
g(x*) < O. Thus, we can drop the first two terms in the RHS of (16) and by union bound, we get
with probability at least
18T + 1)) x² 17 2n
& GG + 20 + 4n Σ
- -(xx))2((x))] 2f(x))+
2A Σ
(x.)
7
1=1
(17)

---

Maximizing the LHS of 17 with respect to À over the range [0, +00), we get a solution of À
E 5. (x(x))
8n7 1/n Plugging this into
gives us
Ei= Dr [xxx))]
S de GGnII +0 + +4n Σ
T
-i((x)) 2f(x)))
2
(18)
ōrÿī + 1/11
2n
Plugging in = max{G, and 1 UV we have with probability at least E,
7dU S 2
27
Σ - -f(xx)
VT + SdU log
(19)
InI + 1/1
where we used the fact that Σ V7
Tv This gives us our result on objective regret:
Σ
[(xx) -(x))) = O(VT). =
(20)
The detailed proof, including constraint violation steps, provided in Appendix D
6 First Order Full-information Case
In this section, we introduce our second proposed algorithm for online DR- submodularr maximization subject to stochastic long-term constraints under the first-order full-information feedback. In the interest of space, the algorithm is presented in Algorithm 2 in the Appendix. The overall structure of the algorithm is similar to Algorithm [ but the primal update uses the gradient of the non-oblivious function:
V, V,Li (x.(x)) d Vo (x;),,
Xt+1 = [xx( + v/ (x,, Ae)).
where the non-oblivious function F is defined by its gradient: VF(x) f' x)d2. As we discussed in Section 3. the non-oblivious function F plays an important role in obtaining the optimal approximation ratio 1 - 1/c. However, calculating the gradient of the non-oblivious function Fxx) can be challenging, especially when only unbiased estimates of the gradients are available. To overcome this, [42] presents computational approach for obtaining an unbiased estimate of the gradient of Fxx) through sampling (Lines and 7). The following lemma indicates that (1 - 1/e)/eeeeeeee fz(z x) is unbiased estimator of FF(x) with bounded variance.
Lemma If z is sampled from r.v. Z in line 6 of Algorithm
E fx) x]
v and
V fx()) 2x)]] x
o2, have
(1 1/c) x) x FF(x);
(i) E
(1-11/e)\/icl xx -V/=\//
x S soi where of = 21- 1/e)200 0²
21
(ii)
E
With the unbiased estimator the gradient of the non-oblivious function, we show the following regret and constraint violation guarantee for our Algorithm 2 in Appendix B
Theorem 2.
Let Assumptions
3 be satisfied. Let U max(Gr, C). Choosing 17 U.T and
6 432 Let Xt, & E [T] be the sequence solutions obtained by Algorithm
When T is sufficiently we have the following (1 1/e)-regret and constraint violation bounds with
2
large, i.e., T' > 16d 8² probability at least
212
E Rr] O(VT) and CT O(T3/4).

---

7 Conclusions
In this paper, we address the problem of stochastic Dussubmodular maximization with stochastic long-term constraints over a general convex set. We introduce the first algorithm for this setting, attaining ((VT) regret and (TT3/1) constraint violation bounds. Notably, our algorithm operates in both the semi-bandit feedback and first-order full-information setting, requiring only gradient query per round, while all previous works operate in the full-information setting with vT gradient queries per round. Extension of the results here to upper-linearizable functions in 27 is an open direction.
8 Acknowledgement
This work was supported in part by the National Science Foundation under grants CCF-2149588 and CCF-2149617. We acknowledge Yiyang (Roy) Lu for helpful feedback.
References
[1] S. Agrawal and N. R. Devanur. Bandits with concave rewards and convex knapsacks. Proceed- ings of the fifteenth ACM conference Economics and computation, 2014.
[2] R. Bach. Submodular functions: from discrete to continuous domains. Matherattiaal Programming, 175:419- - -459, 2015.
[3] A. Badanidiyuru, R. D. Kleinberg, and A. Slivkins. Bandits with knapsacks. 2013 IEEE 54th Annual Symposium Foundations of Computer Science, pages 207-216, 2013.
[4] S. Balseiro and Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65:3952-3966 09 2019. doi: 10. 10.11877mmsc2211833111
[5] A. A. Bian, B. Mirzasoleiman, J. Buhmann, and A. Krause. Guaranteed Non-convex Optimiza- tion: Submodular Maximization over Continuous Domains. In AISTATS, volume 54, pages 111-120. PMLR, 20-22 Apr 2017.
[6] Y. Bian, J. M. Buhmann, and A. Krause. Continuous submodular function maximization. ArXiv, abs/2006. 13474, 2020.
[7] L. Chen, C. Harshaw, H. Hassani, and A. Karbasi. Projection- free online optimization with stochastic gradient: From convexity to submodularity. In J. Dy and A. Krause, editors, Proceed- ings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 814 823. PMLR, 10-15 Jul 2018
[8] L. Chen, C. Harshaw, H. Hassani, and A. Karbasi. Projection free online optimization with stochastic gradient: From convexity to submodularity. In J. Dy and A. Krause, editors, Proceed- ings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages
PMLR, 10-15 Jul 2018.
[9] L. Chen, H. Hassani, and A. Karbasi. Online continuous submodular maximization. In A. Storkey and F. Perez-Cruz, editors, Proceedings of the Twenty-Fit First International Confer- ence on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1896-1999 1905. PMLR, 09-11 Apr 2018
[10] J. Feng. R. Yang, Y. Zhang, and Z. Zhang. Online weakly dr-submodular optimization with stochastic long-temn constraints. In D.-Z. Du, D. Du, C. Wu, and D. Xu, editors, Theory and Applications of Models of Computation, pages 32-42, Cham, 2022. Springer International Publishing. ISBN 778-3-031-20350-2
[11] C. Guestrin, A. Krause, and A. P. Singh. Near-optimal sensor placements in gaussian processes. Proceedings of the 22nd international conference Machine learning. 2005.
[12] H. Hassani, M. Soltanolkotabi, and A. Karbasi. Gradient methods for submodular maximization.
In Neural Information Processing Systems, 2017.
10

---

[13] E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization. Now, Boston, 2016. ISBN 978- 178-1-88083-17--2 doi: 10.1561/2400000013.
[14] R. Jenatton, J. Huang, and C. Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In M. F. Balcan and K. Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 402-411, New York, New York, USA, 20-22 Jun 2016. PMLR.
[15] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. A short note on concentration inequalities for random vectors with subgaussian norm, 2019.
[16] D. Kempe, J. M. Kleinberg, and É. Tardos. Maximizing the spread of influence through social network. In Knowledge Discovery and Data Mining, 2003.
[17] A. Krause and D. Golovin. Submodular function maximization. In Tractability, 2014.
[18] N. Liakopoulos, A. Destounis, G. Paschos, T. Spyropoulos, and P. Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3952. PMLR, 09-15 Jun 2019.
[19] T. Lin, J. Li, and W. Chen. Stochastic online greedy learning with semi-bandit feedbacks. In Proceedings of the 29th International Conference on Neural Information Processing Systems, pages 352-360, 2015.
[20] M. Mahdavi, R. Jin, and T. Yang. Trading regret for efficiency: Online convex optimization with long term constraints. Journal of Machine Learning Research, (3(81)22503-2528 2012.
[21] S. Mannor, J. N. Tsitsiklis, and J. Y. Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10:569-590. 550, 2009.
[22] B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause. Distributed submodular maximization: Identifying representative elements massive data. In C. Burges, L.. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[23] B. Mirzasoleiman, A. Badanidiyuru, and Karbasi. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning, 2016.
[24] R. Niazadeh, N. Golrezaei, J. R. Wang. F. Susan, and A. Badanidiyuru. Online learning via offline greedy algorithms: Applications in market design and optimization. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 737-738, 2021.
[25] G. Nie, M. Agarwal, A. K. Umrawal, V. Aggarwal, and C. Quinn. An explore-then the---omminnttt algorithm for submodular maximization under full-bandit feedback. In Uncertainty in Artificial Intelligence, pages 15511 PMLR, 2022.
[26] G. Nie, Y. Y. Nadew, Y. Zhu, V. Aggarwal, and C. J. Quinn. A framework for adapting offline algorithms to solve combinatorial multi-armed bandit problems with bandit feedback. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 26166-26198. PMLR, 23-29 Jul 2023.
[27] M. Pedramfar and V. Aggarwal. From linear to linearizable optimization: novel framework with applications to stationary and non-stationary dr-submodular optimization. In Thirty-eighth Conference on Neural Information Processing Systems, 2024.
[28] M. Pedramfar, C. J. Quinn, and V. Aggarwal. unified approach for maximizing continuous DR- ou-subood functions. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
[29] S. Raut, O. Sadeghi, and M. Fazel. Online dr-submodular maximization: Minimizing regret and constraint violation. In AAAI Conference on Artificial Intelligence, 2021.
11

---

[30] O. Sadeghi and M. Fazel. Online continuous dr-submodular maximization with long- long-term budget constraints. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1410-4419 PMLR, 26-28 Aug 2020.
[31] O. Sadeghi, P. Raut, and M. Fazel. A single recipe for online submodular maximization with adversarial or stochastic constraints. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 14712-14723. Curran Associates, Inc., 2020.
[32] T. Soma, N. Kakimura, K. Inaba, and K. ichi Kawarabayashi. Optimal budget allocation: Theoretical guarantee and efficient algorithm. In International Conference on Machine Learning, 2014.
[33] M. J. Streeter and D. Golovin, An online algorithm for maximizing submodular functions. In Neural Information Processing Systems, 2008
[34] J. Vondrák. Submodularity in Combinatorial Optimization. Phd thesis, Charles University, 2007.
[35] X. Wei, H. Yu, and M. J. Neely. Online primal-dual mirror descent under stochastic constraints. Proceedings of the ACM Measurement and Analysis of Computing Systems, 4:1 -36, 2019.
[36] L. A. Wolsey. An analysis of the greedy algorithm for the submodular covering problem. Combinatorica, 1-385-393, 1982.
[37] X. Yi, X. Li, T. Yang, L. Xie, T. Chai, and K. Johansson. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11998-12000 12008. PMIR, 18-24 Jul 2021.
[38] H. Yu and M. J. Neely. A low complexity algorithm with ol o(VT) regret and o(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24, 2020.
[39] H. Yu, M. Neely, and X. Wei. Online convex optimization with stochastic constraints. In Neural Information Processing Systems, 2017.
[40] J. Yuan and A. Lamperski. Online convex optimization for cumulative constraints. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biannhh, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[41] M. Zhang, L. Chen, H. Hassani, and A. Karbasi. Online continuous submodular maximization: From full-information to bandit feedback. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[42] Q. Zhang, Z. Deng, Z. Chen, H. Hu, and Y. Yang. Stochastic continuous submodular maximiza- tion: Boosting via non-oblivious function. In International Conference on Machine Learning, 2022.
[43] M. A. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning. 2003.
12

---

A Proof of Lemma 3
Before proceeding to the proof, we first show a lemma:
Lemma 7. For all t E [T), the following holds:
P(Ip. pll 2 2e 3p7
where p cB for some universal constant
Proof. From Assumption 1 we have lpp, |l S B. We can apply Lemma of [15] with sub Gaussian
parameter p = cß for some universal constant c > 0 and the result follows immediately.
Then we proceed to prove Lemma 3 We restate the lemma follows:
Lemma 8. The following holds with probability at least E:
T
2nT
Σ
lt. Pl P 201
Tlog
1=1
where Q > 0 is some universal constant.
Proof. From the definition of P.. have
1r
pll Σ (p. - -)
(21)
Combine W[p, p] 0 and Lemma we can apply Corollary of [15] the random vector (p. p) and obtain with probability at least
7
2dT
2dT
Σ 1=1
P..
p)l se
Σ
p² log(
d' d'pv t log(
(22)
where c' > is some universal constant. Combining 21 and 22 with probability at least
and apply union bound, we have
f.
T E
T
P
pll
(p.
p)ll
1=1
5=1
T
2dT
d dP log(
)/6
1=1
2dT
Σ d p
T Tlog(
(23)
t=1
where the last inequality follows from Σ v
< 2VT.
We get the desired result be taking
= 2cd..
B Proof of Lemmal
We restate the lemma as follows:
2T Lemma 9. Let E KC be fixed. For fixed [T] and {no c2celog
T
[x)
g(x) % holds with probability at least $.
13

---

Proof. Recall from the definition that (x(x) = (D..x) - Br Yí and (x) == (P. Br. Br T
T
Note that (x)] (P. x) Br] (p. x) T gxx). Recall that have defined
:= maxp'~D, maxxex: Kp', x) T
Be Thus, we have De (x) is bounded within interval [-C,c].
Apply Hoeffding's inequality on (x), we get
tyi
(( (3) g(0)و > w) S 2 2xxp
20
Substituting the value of 7o the right hand side, we get that IP ([īi(x) - g(x)] > 7h f..
C Proof of Lemma 5
We restate the lemma as follows:
Lemma 10. Let {1:)2=1 be defined as in Lemma
then the following holds:
T
Cr
9t (xx) +
pip pl
+
7t-
(24)
Proof. Bounding Σt= 1= 9t (x() from below, we obtain:
9t
(xx)
Σ 9 (xi)
+
( (xx) -g(xi))
Σ 7s
T
T
> Σ
9 (xx)
Σ
1e (x+) - -9 (x+)]
1=1
T
= CT
Σ
(p: -p,
t=1
2 CT
lIP: pll ||x|||
7
(=1
1=1
2 Cr
Σ
lp. pl
Σ 70
Rearranging the above inequality, we obtain the desired result.
D Proof of Theorem 1
We restate theorem follows:
Theorem 3. Let Assumptions
4 be satisfied. Let = max C}. Choose 1) UVT
and 8 8,3 Let Xt, 1 [T] be the sequence of solutions obtained by Algorithm 7
When T is
sufficiently large, i.e., T> t/a we have the following rregret and constraint violation bounds
64
with probability at least E:
2 5(x*) s(x))
7dU VT + SAU log
2T = 0T2
E E
< t=1
s
4
and
( 7dU VT + 4dU log
2T + (Fi + Fa)T)
(80) U
(882d
+ 4) VT
Cr CrS
2nI + 2 2TC2 log
2T
+ +rQ0 Tlog
(25)
=O(33/4)
14

---

Proof.
From the update of Xs, we have that for any x E K.
Xx+1 - x|2 2 ====1 =||TT< (x + VV (xe: 2z)) - x112
I ||x, + 1/ (X,,
Xx, de) - xx12
(def. of projection)
= ||x: x|2 + x VI Lx Ax) 21((x - (x,, Ac).
(26)
Rearranging,
(x- xxx)) xxx) (V
1
(1xx;- x|| - ||x+11 - xx "1 "I C. 2il1
2ny
(1x: x||
||++1-
- x|| + " [x,) 22. (x+))
27
(from
S 20
(1xx x|| - |x 1x++1- + n1 (x,))l + 4m V
(la + b11 v 2||a|1 + 2|1613)
1 (|xx x|| - ||x++1 x1 + G2 + 4n
(27)
2n
where 27 follows from Assumption 4 and Assumption 3 Taking expectation with respect to ft, we have
(x, Ao) - (x, Ae)
= -EEE[C 2o - (x):
[x)[f(x) - (x) + 5n1 x² - [((xx)) - (x)) + 5n x²
[x:]
2
2
811 x²
= -](E]f(x)) - (x)) -
- -x(00())) + Ax0e((x)
2
8n
< El(x - x:) (..I((( - (x) gx(x))) x:I] + Ax))(x)
x?
2
(Assumption
2 and Lemma
677
El(( xx) (x)(((()) 2Ax xx) V . |x]] + Xxīx(x)
X
2
(.) is linear so ge (y) [x(x) 2 (Vg. y x))
6n X²
< E[E[(x - xx) (x.( - 2Xx xx)
xx]] + (x)
(linearity of expectation)
= E[E[(x - x.) T V. xx][ + (x, - 811 X²
2
1 Blllx x||2 ||x+1 x| 9] + G2n + 3n X? + Xx.r(x)
8n (28)
x?
2n
2
where 28 follows from 27 From the update of A 8 we have
|A++1 - 21 = ||10 (Ar V/C - A/12
(from S
$ - / (x) - A112
(def. of projection)
= "
- AA) 2,7
(x,,(xx)))))
(29)
15

---

Rearranging,
VxL (A-A))V
1
(11 - 2122 11441 - -113) - 7 VX,,((x,, At)1
2n
1
(112 - -112- - -1Ac+1 -113) - "1 - (xx) + dn1ael?
21
2
(from 6
1
(11 -1 -113) "11 - -x(())) - - + dep
2m
(by def. 9e)
1
2 21
(112e- - 117--1441 A113) - (x,)) 12 2,7 - 20²
(apply ||a b1l S 2||a|12 + 2116|1 twice)
1 (112 - - -1 - -113) - C2n - 207/ - 22 Xp:
2 21
(30)
where the last inequality follows from the definition of C maxp' DD, maxxex |axxex1(p,xx) (x(x) == (). Br. From convexity of function Cx A) w.r.t X, we have
BF and
(x) - Lx(x,, A1) (A Ao) (x,, Ac)
2n (112 - AlI - | - A|(3) - C²n 2 - 2 (31)
where 31
follows from (30) Subtracting two times (1) from (8). we get
-x,,
A)] - El|x, x|| - ||x,+1 x| + 17
(112, 2112 - 11 2123)
2n
817 x2
+ G + 4n1 22 + 2C 1 + 4n7 + 182,,>>² + xx)r(())
2 (32)
Summing 32) for L E [T), we have
T
EXC dt) - (x., A)]
1 T
T
1
$
[[[|x - x||² - -||x++1 - xx]]]+ +
(11 - A112 - -14411 - -1133)
21
17 t=1
1=1
T
T
T
T
511 T
+
GTT + 4n
Σ
23 + 202 + 4n) Σ
7t + 45221''
2
3
Σ
X2 +
Xx
X?
2 1=1
t=1
1=1
1=1
t=1
1 E|||x| - x|| - ||XT+1 - x1| + - [(1 - 2
$ 2m
- -117++1 - 2l13)
T
T
T
T
81 Xxg)(x)
T Σ :=1
+
+G + +n
Σ
2₂ + 2C + 4n >
2t + 482y''
Σ
X₂
+
x?
2 (telescoping series)
1=1
1=1
1=1
t=1
1 EE|II- XT+1 11
1
+
-1111= 211 111+1~21133)
2n
17
T
T
T
T
5n 2
T
+
GTT + +
Σ
2 + 202
+ 4m Σ
2t + 452 3
2
Σ
X2
+ t=1
Xx
2
1=1
1=1
1=1
t=1 (triangle inequality)
d x2
811
+ + G + n1 Σ
x2 + 2C 2C
TT + 4m
2 +
4 3
X² +
(x)
x3
2m
n
2 t=1 (33)
t=1
16

---

where (33 uses Assumption with def. of diameter d, A1 0, and -Il hand side of (33 we deduce
112 < O. Expanding the left
T
T
T
Ön
Σ
[x) - 2xxx)
+ Σ
(x) (x]
+
8912
2
1=1
1=1
1=1
d
x²
8n
T
+
+ G² + 4n Σ
X 20 1/T + 4n Σ
2
+
Σ
X +
X
(x)
Σ
X?-
21
2 t=
1=1
t=1
t=1
t=
(34)
Rearranging, we have
T
T
50pT +1)+ -111 12
Σ ( - 2/(x)] + 22 E (xx)
11
T
X + d
T + G² + 20 + 4n
(x) + 17 (482 +482+ 402
Σ t=1 2n
Σ
(35)
t=1
S x". From Lemma with probability at least 1 - 5. 5t (x*) = 0x(xx) - - g(x*) holds.
Since x" satisfies the long term constraint, we have g(x") ) S 0. By the union bound, we get with probability least 1 that for the first term the RHS of (35)
T
T
{x)x(x 2g(x*)
A < O.
Now choose å such that 4,8² + 182 8 < 0 (so that the second term the RHS of (35) will be negative and can be dropped with an upper bound). This is a quadratic term w.r.t. 8. is casy verify that the quadratic formula has real roots when 17 S 83 As we choose rj .-. this will
6dd2 0
give us the condition that T needs to be sufficiently large, i.e., T > 5 8.32.
We can simply choose
Applying both of those inequalities to 35) and by union bound, get with probability at least 1
I
T
+ )
Σ -f(x))22(xx))) + 21
Σ
(xx) - (87/ +
t=1
d + 22 + +4
Σ
2
(36)
2n
1=1
Maximizing the LHS of (36) with respect to X, over the range [0, +00), we get a solution of ΣT, d((x))]
Plugging this into (36) gives
11/m
El Fe (x,))
T
d²
T
[f(x')) 2f(x,))
<
GG + 2 + +4n Σ
2
(37)
ōnTT + 1/1
2n
17

---

Let = max[G, Choosing 17 = UVT we have with probability at least 1
- + Et (x,)
T
8n1 1111
[=1
d dmax(G,C)
G
dCºd G
8 Mnax(GCCddll
27
VT+ max(G,
VT
VT
2
VT
d (max(GG
8Udlog
2T
T
VT + max C.dVT max (G, CG,C
Σ
7
(38)
2
VT
SUdlog T
7dU
1
VT+ +
(39)
2
VT
t=1
7dU
2T
$
VT + 16 log
(40)
2
E
where Equation
40
uses Et=1 V
1 S 2VT. This gives
[(x)) s(xi)
TdU
27 VT + SdU log
O(T
(41)
4
Next, we establish our constraint violation bound.
Since Fi = maxxex: [xx) and F2 =
maxx.yek lf(x) - -(yy), we have
1f(x*) 2xxx)) s [f(x*) f(x)) + [f(x)) S F1 + F2,
(42)
thus, Et=l(((0) - 2f(x))] 2 -(F + P2)T. Plugging back in 40 we have
1x 1
2T 7dU VT SdU log
E (Fi + P2)T.
(43)
Tnp + 1/1)
Rearranging and plug in the value of n,, we have
Σ
T
((x))
<v
S
TdU
VT +
SdU log
2T
+ (Fi + (Fi+ +BaTT
(
883'd
U
+ U
4
(44)
g
Combining 44) with Lemma
5 we get
Cr 1
7dU 4
VT + SdU log
2T
+ (Fi+ -A)))
(88Pd) U
+ d
VT +r
T
10 - pll +
Σ
T
U
TdU
2T
(88'd U
VT + 8dU log
+ (Fi (Fi+ (Fi+F5)))
+ d
VT
4
1nTT
T
+ rrQ
Tlog
+
7
(using Lemma 3
E
[=1
7dU
2T + (F1 + +F2TT
(80))
U
5
VT + SdU log
+ -
VT
1nTT
(T
+ +rQo
Tlog
+ 2
2T
= O(T3/4).
where in the last inequality we plug in the definition of nr This concludes the proof.
18

---

Algorithm 2 OLSGA with First Order Full Information
1: Input: Convex set X, time horizon T
2: Initialize X1 K. A 0.
3: for t E [T] do
4: Play Xx, obtain f((x;) and f-((-) and Pt
5: Compute P, = : E Ps
6: Sample be from Z where P(Z 2) = -1² - du.
7: Compute (x,) (1 V/( *x+)
8: Compute
vxC,(x,, Ao) (F((x,) do (x)()))
(45)
VxL((x(; = (x)( + ònide
(46)
9: Update X₁ and Ay:
X [xx + 17 N.CC(xx,) Ar))
(47)
Ac+1 = [1 (he V/V (x))
(48)
10: end for
E
Proof of Theorem 2
We restate theorem follows:
Theorem 4. Let Assumptions 3 be satisfied. Let = max[Gr, C}. Choosing vj == U-T and
5= = 482. Let Xt, t. (T) be the sequence of solutions obtained by Algorithm 2 When T is sufficiently large, i.e., T 2 328 ge we have the following (1 1/ee-regret and constraint violation bounds with probability least E:
U
T
5dU VT 8dU log
2T
E RT S
(1-11/07 1/e)(())((x*) -(x))
s 2
(
g
and
CT CTS s V
5dU
2
VT + 8dU log
2T
+-1 +
Fi
F2)))
4432d U
+
d
VT
2nT
2T
+ +rQo
T Tlog
+ 2
2TC log
O(T3/4)
Proof. From the update of Xx, we have that for any x E K.
|x++ x 2= =1[T<xxxx + vn Ax)) - x|12
S S|Ix + 17 V. V.Zo(xx Ae) - x|1
(def. of projection)
||x, x||2 + n²² 4 (x 22) 2n((x x.
(x, (x,,,(
(49)
19

---

Rearranging,
(x - x1) (xx,,,xxx,,))
1e) $
(1|x4 x||2 ||x x|() + " V (x,,((x,))))
2n
2
-
-x| (||x; x11 ||
マ [ - de (z)e)
211
(from (45)
(1|x; x|1 ||x+11 x|3 + 1 [x,((x)) )1 + V ||
211
(Ia + b112 ニ 2||a|| + 2|16133)
$ 2n
(1|x+ x|| -|xx+11 x|(²) + G + n
(50)
where (50) follows from Assumption and Assumption expectation over fi)
When is fixed, we have (taking
E(11
= (08((1-16))(((x///1 - (((x,))))) xx]
= =E[E[(1 - 1/e) - -xx(()) + 8n {2) - (Jr(xi) (x)x(())
8n
\/)xx.]] xx]]
2
81 x;)
E] - 1/0) - -x(x)) (x( - -x(x))))=11+++ + 'x(ā((x)
2e
8n X₂
S Bl(( xx) ((E((( (x) (x(x)))) x11]| + -x)
(Lemma 2
2e
81
E|E[(x
(x (x)))) xxTx(x)
X3
2e (linearity of expectation)
< <E (x.) Ac((x xx) (x.():) xx + 1 -x
811
2c X
(.(() is convex so T:(y)
[x(x) 2 (V), x))
61 X?
B[E[(x (F,( - (x, xx]]] + -x)x
2e
E|E[(x - x (F(((x) - (x,)) + 5n7 | + 1 -x1
81] X
2
2
[E[[((x - xx) V.C. (xi, [x,] + =x,
2e
1 [||| x|1 ||x 12] + G + n +
1 Ax)e(())
811 X2=
W 2m
(51)
2e
where 51) follows from 50
From the update (48) of X, we have
||++1 - 21 = ||110 (A: - 1/ (x Ae)) A112
(from (48)
$ 1 - V,,,, - 2112
(def. of projection)
< || ,
- 22(2- - (x,,(xx))))
(52)
20

---

where (2) multiplies through. Rearranging,
(A (x- VxLe(x), 2 (e -212- 11441 1141-~111 2113) -219)- " 1 (x1, Ao)11
1
2m
1
(11A2 - 2122- -1A44 - -(13)- - 711 - Tr (x+) + 5epAell
21
(from (46)
1
(112, - 212 - -1A++1 - -113) - -1 - 9r (x+) - ~ + 0
=
21
2
2 2m
1
(112- 2112- -
2 -1441 \113) - ( 12 - -2m
: - -2 X²
(apply ||a b11² 2 2||a|22 + 2|16| twice)
1 (11) - 212 1A - - - - 207 - -252 x2:
(53)
2m
where the last inequality follows from the definition of == maxp<~D, maxxex 1 x)) Br and (x(x)= = PP., x) Br. From convexity of function L( A) w.r.t X, we have
fx 2) - C. Ax) 2 (A- Ao) T VxLe(xe, (x)
1
Σ 2n
(112e - A1I - | - -113) - -C - 2mm? - 26 (54)
where (54 follows from (53)
Subtracting 544 from 51 we get
1
|x, - -x| x||2-1|x1+ x|| + 1 (1) A112 - 1 - 211²)
EI(1- - (/ee - A)
s (x,,
2n
21
+ G + n + C2n + 2m + 25"12² + 1
811 x²
2
(55)
Summing
(55) for t E [T]. we have
T
B[(1 - 1/e) Ae) - Cx(xx, A)]
T
1 T
[|[|x - x1|2 - -||x++1 - -x1
Σ
(IIA - Al2 - 11 - -113)
27 1=1
2n
t=1
T
T
T
1
87 Σ x²
+
GZ.n + n7
Σ 1=1
X + C2TIT + 2n
Σ
+ +2207
3
Σ
X2
+
X1 (x)
2e 1=1
1=1
t=1
1=1
(56)
1 E|||x| - -x112= - ||xT+1 - -x1 + -
$ 2n
(1121 - A/12 - -11A41 - 2113)
27
T
T
T
T
8n T
+
GGani + n7
Σ
X2 + 027I + 2n
Σ
1t
+ 28 3
>
X²
+
(x)
x
2e
1=1
1=1
1=1
1=1
1=1
(57)
1 -E|Ix- xT+111 11
1
+
-
(1 212 - ||T+1 - x
2m
21
+
GGOnT + n
Σ
T
x + 0 + 2n
2 Σ
1t + 202
Σ
T
x2
+
1
X
(x)
8n
2e
1=1
1=1
1=1
[=1
(=1
(triangle inequality)
d
x²
81
+ + GZanT + n2 Σ
X + 0 T/ + 2n
2 + 28
X2
(x)
x²
78
2m
2n
2e 1=1
t=1
(58)
21

---

where (58) uses Assumption with def. of diameter d,A1 0, and -11 112 < O. Expanding the left hand side of (58). we deduce
8m12
òn,2
(1 1/0)S(x) [xx,]
(xx) (1 1/e))r(((x)]
((1 1//e)
2
1=1
d²
X²
T
T
δ1
T
+
1 + n132
Σ
1 + 21j Σ
7t
28 11
1 +
Axge(()
x2
2n 2n
2e
(59)
Rearranging, we have
T
ónTT
1
[[11-/e]f(a) f(xx)] + {
[((x))
+
12
2
21
1=1
T Σ (x) + 8 + 20 1/
8
T
d2
I
2 X2
GpppT + C2T + +2
76
(60)
27
1=1
Set x x": From Lemma with probability at least 1 - f. (x(x)) -
< g(x))
holds. since x' satisfies the long term constraint, have g(x") S 0. Now choose 6 such that 3 + 25
s 0. This is quadratic term w.r.t. 5. is easy verify that the quadratic formula
has real roots when 1) S v2 be sufficiently large, i.e., T 32 Applying both of those inequalities to (60) and by union bound, we get with probability at least 1 - 6,
d this will give the condition that T needs to As we choose 17 UVT
8g
D.-. We can simply choose 4,3..
Σ - ((0-1/ef(x))- f(x,)]+
Σ [x()))
T
[nqT
+
1 22
S d2
+ +Gantt + +C + 2m
Σ 76
T
2
2m
2n
(61)
Maximizing the LHS of 661 with respect to X, over the range [0, -00), we get a solution of
[EZ (xx))]
Plugging this into 61 gives us
/nt/2+1/22
Σ Σ Te (x1)
d²
Σ (1 - (/e)/xx)x)x------- [xxx:] + 8T + 1/2n
GGgHT Crp 21
Σ
2
(62)
71
27
1=1
(=1
Let U = max Choosing 1 = UVT we have with probability at least 1 - E,
Do (x.)
Σ (1 1/e)s(x') - f(xx)) + 8n/ 1/27
d maxx/GF C}
G VT
C2d max max, C)
4 4max Cld T
27
1
VT
VT
2
max (Gr, C}
VT
d mmxx/Gr (GF, C}
4 4max(Gr, Cldlog
2T
T
1
VT (GF, CJ.V - max GGr C
2
vT
7
5dU
4dU log
T 1
VT +
(63)
2
VT
t=1 Vi
5dU
27
VT SdU log
(64)
2
E
12)
(65)
22

---

and dropping the second term on the LHS gives us the desired (1 - (a/)e-regnnr bound.
Next, we establish constraint violation bound. Since Fi maxxex: [(x) and F2
yaxx,yex [x() - f(y),, we have
1 fx (11 - (1-1//ef(xx) - f(xi) 1f(xx)) - f(xx) (f(x) 5 + F2.
(66)
e
thus, El (a-l(111)ff((x)) - f(xx)) 2 ( + F2).. Plugging back in 644 we have
E (x)) 1
5dU
27 + VT SdU log
Fi F2)T.
(67)
òFÿI + 1/7
2
e
Rearranging and plug in the value of 17. we have
T
5dU
2T
Fi
433d U
Σ
gpxi)
SdU log
+
+
F2)TT)
+ d
VT.
(68)
2
U
Combining (68) with Lemma
5
we get
5dU
2T
F
U (4/) + d
433dd U
T
CT ST S
VT SdU log
+
+
F2)r))
VT +r Σ
11:
pll +
Σ
7
2
E
1=1
5:UU
2T
Fi
433dd
VT + SdU log
+
(--
+ Fa)r)
+ d
VT
2
U
2nI
T
+ +QQ0/
Tlog
+
(using Lemma
3
1=1
$V(
5dU
2T
F1
433dd
U
s
VT
SdU log
+
F2)TT
+ d
VT
2
U
2nT
(TT
+ +rQoy
Tlog
2
2TC log
E
(69)
where in the last inequality we plug in the definition of no. This concludes the proof.
F More Related Works
We discuss more related works in this section.
Adversarial Constraints It worth noting a line of research that emphasizes adversarial constraints. This setting was initially explored in [21], where simple counterexample highlighted that achieving sub-linear regret against the best fixed benchmark action in hindsight while maintaining sub-lineat total constraint violation, is not always possible. Subsequent works addressed this challenge by introducing additional assumptions to the problem setting to derive meaningful results. Specifically, these works not only required the fixed benchmark action to satisfy the long-term constraint but also imposed the restriction that the benchmark satisfies the constraint proportionally over any window of size W E [T] [18 30 31]. Due to these added assumptions, direct comparisons with our work are not applicable.
Online Monotone Submodular Maximization In the discrete domain, online monotone submodular set maximization was first studied in (33) in the adversarial setting where they introduced the meta-action technique. More recently, [24] proposed novel algorithms utilizing the Blackwell Approachability framework, showcasing improved regrets (w.r.t. constant terms) in both semi-
bandit and bandit feedback settings. As for stochastic submodular maximization in the discrete
23

---

domain, [19] investigated the case of semi- bandit feedback, specifically in the form of marginal gains. Additionally. recent works such [25] 26 have delved into the full-bandit feedback setting. For continuous domains, 9 first investigate the online (stochastic) gradient ascent (OGA) with 2 --regret
of ((T Then, inspired by the meta actions 33
also proposed Frank- Wolfe type algorithm with (1 //e) of ((T1/2) when exact gradient is available. When only stochastic gradient available, 7 proposed variant of Trank-Wolfe algorithm achieving (1 1/c)- of (TT1/2), but requires (T3)2 stochastie gradient queries in each time step. In the effort of reducing gradient queries, [41] achieves (1 1/e)-regret of ((T1/5) with only stochastic gradient evaluation each round. Recently, 42 have proposed an auxiliary function to boost the approximation ratio of the
9
online gradient ascent algorithms from
2 to 1 - 1/c.
G Query Set and Constraint Set
Let KC C 12 denote a convex set, with K'' defined as the convex hull of KC U {0}. For problems involving monotone functions over a general set K., the optimal solution in K'' is the same as that in IC due to monotonicity. However, addressing this extended problem domain within K.' may necessitate evaluating the function across the larger set, which may not always be feasible. In the literature of stochastic DRssubmodular maximization without long-term constraints, various algorithms have been developed to accommodate different constraints (general convex set, convex set containing o, downward-closed set, etc.). Notably, in scenarios where queries are restricted solely to the constraint set, no algorithm
online nor offline-has demonstrated an ability to surpass a 1/2 approximation ratio. For exhaustive discussion on this matter, we defer to (28)
H Application Examples: Origin not Included in Constraint Set
We will discuss the following example motivating applications to highlight the importance of gen- eral convex regions I. for which the origin is not feasible. For such problems, the best-known approximation ratio is 1/2 [2]
1. Maximum Coverage 17] Imagine a city's emergency management agency aiming to optimize the deployment of emergency response teams (firefighters, medical personnel, rescue teams) in many rounds during crises like major fires or earthquakes. The objective is maximize coverage across different city zones. Allocating 0 teams to any zone isn't feasible, as it means no emergency response. The goal is to allocate resources in each round maximize overall response coverage while satísfying the long-term agency budget.
2. Budget Allocation [32] Let bipartite graph G (S, W') represent social network, where S and T are collections advertising channels and customers, respectively. The edge weight represents the influence probability of channel to customer t. The goal is to distribute the per-round budget among the source nodes, and to maximize the expected influence on the potential customers over multiple rounds, while satisfying long-term constraint (e.g., money spent). Corporate management may require a minimum level of customer engagement with each campaign overall from select target groups. There may also be per-round minimum contractual purchase requirements with the advertising partners. Thus, allocating O budget in any round may not be permitted.
3. Facility location 177 Consider scenario where company needs to decide on the locations (virtual) to set up new service centers to maximize service coverage over multiple rounds while satisfying total budget constraint over all rounds. At each round, each customer segment must receive at least a certain level of service or coverage, which means is not a feasible solution because facilities can provide service.
All the problems above were initially studied in the discrete domain and extended to the continuous domain in [6]. Furthermore, when faced with a discrete objective, one can always use the "relax and rounding" strategy transition from addressing discrete problem tackling continuous one. Such techniques are widely frequently utilized within the submodular maximization community, as exemplified by the work of [8)
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly state the paper's contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: Some limitations of the paper have been discussed in the conclusion section. Assumptions form another part of the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

We have clearly stated the required assumptions and an accompanying com- plete proof in the appendix for each theory result.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer:
[NA]
Justification:
Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
Policy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//guuii wwwiiccgguie///eeeeeee CoodeSubeiiieeee ssi wswinnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
27

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
Our research conforms, in every respect, to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our work is primarily of theoretical nature and has no immediate societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No high risk data or model have been used.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No existing asset has been used in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new asset is introduced in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No experiments with human subjects were conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We conducted no experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "pGBS7M3M1p", "reviewer": "Reviewer_QRJN", "summary": "This paper investigates the online learning of DR-submodular with a stochastic budget (linear) constraint. The constraints vary from different rounds. In each round, the constraint is sampled from an unknown distribution independently, and the constraint in round $t$ can only be observed after the learner have submitted her action $x_t$. The goal is to minimize the regret and total constraint violation. This paper achieves $O(\\sqrt{T})$ regret and $O(\\sqrt{T})$ total constraint violation in both semi-bandit setting and first-order feedback setting. Here, the semi-bandit setting means the learner can only obtain the gradient at the played action. The first-order feedback setting means the learner can query a gradient at any point each round. \n\nFor semi-bandit setting, the author achieves $O(\\sqrt{T})$ 0.5-regret and $O(\\sqrt{T})$ total constraint violation. For the first-order feedback setting, the author achieves $O(\\sqrt{T})$ (1-1/e)-regret and $O(\\sqrt{T})$ constraint violation. These results have the same bound with the existing works, but the algorithms in this paper only need to query 1 gradient each round and the existing algorithms need $\\sqrt{T}$ gradient queries each round. Reducing the number of gradient queries is the main contribution of this paper.", "questions": "1.\tThere is a new paper extends the non-oblivious PGA technique to non-monotone function setting: https://arxiv.org/abs/2401.08330. Can we use this result to generalize your results to non-monotone setting?\n2.\tWhy do the authors assume that the utility functions are sampled i.i.d. from a distribution? We know the online gradient ascent works for adversarial environment. Can we till derive the current results if the utility functions are adversarially selected? This question also applies on the constraint, what if the constraint is adversarially selected?\n3.\tSee weakness 1, what is the new challenge in your algorithm design and analysis?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe problem studied is well motivated and has many potential applications\n2.\tThe proposed algorithm is computational-efficient compared with the existing results, and the authors provide a rigorous theoretical guarantee.", "weaknesses": "1. The main weakness is the technical contribution. The method used in this paper is a simple combination between non-oblivious PGA [37] and regularized Lagrangian function techniques [26]. I do not find the new analysis or algorithmic challenge. \n2. The author's references to previous works do not seem to be appropriate. Especially the citation about the paper which proposed the non-oblivious PGA. For example, in line 135—137, Lemma 2 is just a simple corollary from [37] (just setting the curvature to 1 in that paper). However, the authors use vague statements, that is “The proof can be derived from [37] and is presented in Lemma 2 of [39]”. First, I think the author should directly cite [37] behind the Lemma 2 rather than use another statement to show the reference, since this lemma is proposed in [37]. Second, [39] seems do not contribute to this lemma (this paper just writes down the lemma where the submodular curvature is set to 1), so the author should not mention [39] here. Also, in line 286—289, Lemma 7 is also a direct corollary of Proposition 1 of [37] (by setting curvature γ=1). However, the author did not cite [37] directly behind Lemma 7. The authors just write “[37] present a computational approach for…” and did not mention that Lemma 7 is also from [37]. \n3. The 1/2 approximation ratio is not satisfactory, even in the semi-bandit setting. It's known that the 1-1/e approximation ratio can be achieved in the full-bandit setting, which is a harder setting than the semi-bandit setting. As the authors say, these bandit algorithms with 1-1/e approximation ratio require the assumption that 0∈K. But I don't think it is necessary to remove this assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and helpful suggestions. Next, we will address some of your concerns in \"Weakness\" and \"Questions\". \n\n### Weaknesses\n\n> 1. The main weakness is the technical contribution. The method used in this paper is a simple combination between non-oblivious PGA and regularized Lagrangian function techniques. I do not find the new analysis or algorithmic challenge.\n\nWe address technical contributions in Q1 of the general response  above.\n\n> 2. The author's references to previous works do not seem to be appropriate $\\dots$\n\nThank you for your detailed suggestions.  We agree with you and will cite [37] for Lemmas 2 and 7 to clarify [Zhang et al.]'s contributions.\n\n> 3. The 1/2 approximation ratio is not satisfactory, even in the semi-bandit setting. It's known that the 1-1/e approximation ratio can be achieved in the full-bandit setting, which is a harder setting than the semi-bandit setting. As the authors say, these bandit algorithms with 1-1/e approximation ratio require the assumption that $0\\in \\mathcal{K}$. But I don't think it is necessary to remove this assumption.\n\nFirst, in the final version of the paper we will include application examples that showcase the importance of general convex regions $\\mathcal{K}$ for which the origin is not feasible. Please refer to Q2 in the general response  above for examples.\n\nSecond, we note that when $0\\in \\mathcal{K}$, there is no clear path to get $O(\\sqrt{T})$ $(1-1/e)$-regret with semi-bandit feedback *even without considering long-term constraints*. When the origin is included, the best known $(1-1/e)$-regret bound for semi-bandit feedback  without long-term constraint is $O(T^{3/4})$ in Pedramfar et al., 2023 [24]. As indicated by the non-oblivious function in Lemma 2, the $1-1/e$ approximation needs  information at two locations (e.g. a function value at $x$ and a gradient value  at $z*x$). One possibility is that when $0\\in \\mathcal{K}$ and we have semi-bandit feedback, we believe we could utilize an explore-then-commit approach to bound $(1-1/e)$-regret, but the horizon $T$ dependence would be worse than $O(\\sqrt{T})$. For reference, Table 1 in [Pedramfar et al., 2024] is good summary of regret bounds for online DR-submodular optimization under different types of feedback (semi and full bandit), objective functions, and feasible regions. \n\n### Questions\n\n> 1. There is a new paper extending the non-oblivious PGA technique to non-monotone function setting: https://arxiv.org/abs/2401.08330. Can we use this result to generalize your results to non-monotone setting?\n\nThat is a great question. We think it might be possible but were not able to carefully verify this in the short rebuttal time. We will leave it as a future direction.\n\n> 2. Why do the authors assume that the utility functions are sampled i.i.d. from a distribution? We know the online gradient ascent works for adversarial environment. Can we still derive the current results if the utility functions are adversarially selected? This question also applies on the constraint, what if the constraint is adversarially selected?\n\nFirst, we note that the analysis we perform does not extend to adversarial objectives. Specifically, the operations in equation (38), which uses tower rule of expectations to establish upper bound on the difference of Lagrangian functions, rely on the stochastic nature of the objective. On the other hand, in adversarial objective scenarios, we anticipate that the methodologies applied in Lemma 7.5 from [Hassani et al., 2017] could be used to go through those steps, but we will leave it as future work. \n\nSecond, we emphasize that in DR-submodular maximization, the stochastic and adversarial settings are distinctly separate scenarios, as we've detailed in lines 61-63 of the paper: \"Note that this setting is still of interest because as opposed of assuming each arriving function $f_t$ being DR-submodular, we only assume the expectation of $f_t$ to possess DR-submodularity\". Working with the stochastic objectives holds equal significance to the adversarial ones, given that many real-world applications are commonly framed within a stochastic framework, such as maximum coverage and budget allocation problems (described in general response), among others.\n\nWhen the constraints are selected adversarially, for either stochastic or adversarial objectives, there is a known hardness result: [Mannor et al., 2009] provided a simple counterexample showing that achieving sub-linear regret against the best-fixed benchmark action in hindsight while maintaining sub-linear total constraint violation is not always possible. Subsequently, works addressing adversarial constraints alter the regret definition to consider only benchmark satisfying the constraint proportionally over some window of size $W\\in [T]$, e.g., [Sadeghi et al., 2020]. We have included a discussion with this point in Appendix G. It is not clear if our results in this paper could be extended to that setting.\n\n> 3. See weakness 1, what is the new challenge in your algorithm design and analysis?\n\nWe address technical contributions in Q1 of the general response  above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5IjLxRqkmN", "reviewer": "Reviewer_Tz1S", "summary": "The paper studied the problem of online monotone DR-submodular maximization subject to long term stochastic constraints. In detail, it explored the stochastic DR-submodular maximization setting, where the objective functions are i.i.d. sampled from a distribution. Previous works considered adversarial objective functions at each step. Additionally, it also considered the semi-bandit feedback setting, where only the noisy function value $f_t(\\mathbf x_t)$ and an unbiased gradient estimator of that point $\\tilde{\\nabla} f_t\\left(\\mathbf{x}_t\\right)$ can be observed. They proposed the first stochastic gradient ascent based algorithm in both semi-bandit feedback setting and first order full-information setting.", "questions": "- What is the significance of handling search spaces that do not necessarily include 0 between your algorithm and other algorithms? Could you provide more details?\n- Why do most prior works assume the adversarial choice of functions? Are there any example applications that would fall into the stochastic setting considered in this paper?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduced two interesting settings: stochastic utility and semi-bandit feedback, which are more general than those previously studied in the literature.\n\n- They proposed the first stochastic gradient ascent based algorithm under these novel settings. Their algorithms require only 1 gradient query per round, while all previous works require $\\sqrt{T}$. This makes their algorithms significantly more query-efficient compared to prior approaches. These algorithms were inspired by primal-dual updates in online convex optimization, and it was interesting to see this connection.\n\n- The paper is well-written, with clear and easy-to-follow presentation and writing", "weaknesses": "- The authors did not motivate the stochastic DR-submodular setting well. It is not explained why previous works used adversarial setting and what the motivation is for relaxing this scenario.\n- It isn't clear what the signfiicance is of not requiring that 0 be in the constraint region.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review. Here we address the questions in  \"Weakness\" and \"Questions\" as follows.\n\n### Weaknesses\n\n> - The authors did not motivate the stochastic DR-submodular setting well. It is not explained why previous works used adversarial setting and what the motivation is for relaxing this scenario to stochastic setting.\n\nFirst, for objectives, we emphasize that in DR-submodular maximization, the stochastic and adversarial settings are distinctly separate scenarios, as we've detailed in lines 61-63 of the paper: \"Note that this setting is still of interest because as opposed of assuming each arriving function $f_t$ being DR-submodular, we only assume the expectation of $f_t$ to possess DR-submodularity\". Working with the stochastic objectives holds equal significance to the adversarial ones, given that many real-world applications are commonly framed within a stochastic framework, such as influence maximization and facility location problems (described in general response), among others.\n\nSecond, when the constraints are selected adversarially, for either stochastic or adversarial objectives, there is a known hardness result: [Mannor et al., 2009] provided a simple counterexample showing that achieving sub-linear regret against the best-fixed benchmark action in hindsight while maintaining sub-linear total constraint violation is not always possible. Subsequently, works addressing adversarial constraints alter the regret definition to consider only benchmark satisfying the constraint proportionally over some window of size $W\\in [T]$, e.g., [Sadeghi et al., 2020]. We have included a discussion with this point in Appendix G. It is not clear if our results in this paper could be extended to that setting.\n\n> - It isn't clear what the significance is of not requiring that 0 be in the constraint region.\n\nSee response to the first question below.\n\n### Questions\n\n> - What is the significance of handling search spaces that do not necessarily include 0 between your algorithm and other algorithms? Could you provide more details?\n\nIn offline DR-submodular maximization literature (without long-term constraints), there appears to be a significant hardness gap between $0\\in \\mathcal{K}$ and otherwise when only feasible points can be queried (e.g. with semi-bandit and bandit feedback). With $\\mathcal{K}$ being a general convex set, the best-known approximation ratio is 1/2 [Hassani et al., 2017]. The tightness of the upper bound is not known, but is conjectured to be 1/2 [Pedramfar et al., 2023]. With the assumption $0\\in \\mathcal{K}$, the best-known result is $1-1/e$ [Mokhtari et al., 2020].\n\nIn online scenarios, we note that when $0\\in \\mathcal{K}$, there is no clear path to get $1-1/e$-regret in semi-bandit setting with only $\\sqrt{T}$ regret even not considering long-term constraint. When the origin is included, the best known $1-1/e$-regret in semi-bandit setting without long-term constraint is $O(T^{3/4})$ in [Pedramfar et al., 2023]. As indicated by Lemma 2, the $1-1/e$ approximation needs additional information (to query function value at $z\\*x$). One possibility is that when $0\\in \\mathcal{K}$, we could utilize an ETC style in the semi-bandit setting, where we alternately sample $z_t\\*x_t$ (giving estimates for $\\nabla F$), and $x_t$ (giving reward signal,) to achieve $1-1/e$ approximation ratio but a regret worse than $O(\\sqrt{T})$. Table 1 in [Pedramfar et al., 2023] gives a great summary of regret results for online DR-submodular optimization. \n\nIn the final version of the paper, we will also include application examples that showcase the importance of general convex regions $\\mathcal{K}$ for which the origin is not feasible. Please refer to Q2 in the general response above for those examples. \n\n>  - Why do most prior works assume the adversarial choice of functions? Are there any example applications that would fall into the stochastic setting considered in this paper?\n\nPlease see response to the first Weakness above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OXBN2RglzI", "reviewer": "Reviewer_w3Qq", "summary": "In this work, the authors address the problem of online DR-submodular maximization subject to long-term stochastic (linear) constraints. At each round $t\\in[T]$, after committing an action $\\x_t$, a random reward and an unbiased estimate of the point are revealed.\n\nThis paper focuses on the stochastic DR-submodular maximization setting, where the objective functions are i.i.d. sampled from a distribution. Moreover, this work also considers the semi-bandit feedback setting where only the noisy function value and an unbiased gradient estimator of that point can be observed.\n\nThe main contributions of this work can be summarized as follows:\n\n- A stochastic gradient ascent-based algorithm for stochastic online DR-submodular maximization with stochastic long-term constraints achieving $O(\\sqrt{T}) \\frac{1}{2}-$regret and $O(\\sqrt{T})$ constraint violation with high probability. in the semi-bandit feedback setting.\n- A stochastic gradient ascent-based algorithm for stochastic online DR-submodular maximization with stochastic long-term constraints achieving $O(\\sqrt{T}) (1-\\frac{1}{e})-$regret and $O(\\sqrt{T})$ constraint violation with high probability. in the semi-bandit feedback setting.\n\nIt is worth noting that the query complexity is significantly lower compared to previous works in both settings.", "questions": "I have no questions", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The presentation was clear, and I enjoyed reading this paper.\n\nThe results were clearly explained, and I especially liked the proof of Algorithm 1.", "weaknesses": "I have two concerns:\n\n- The paper lacks empirical evaluation, which would be valuable in highlighting a use case and demonstrating the effectiveness of your proposed approach.\n- The theoretical results, while commendable, are not particularly groundbreaking.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and your encouraging review. We address your concerns in the following:\n\n\n### Weaknesses\n\n> The paper lacks empirical evaluation, which would be valuable in highlighting a use case and demonstrating the effectiveness of your proposed approach.\n\nWe agree with you that empirical evaluation can be valuable to demonstrate the effectiveness of proposed approaches in real-world applications.   However, we highlight a few points:\n\n1. Our paper primarily emphasizes the theoretical contribution of our approach.\n\n2. *Our Algorithm 1 is the first algorithm*  for online stochastic DR-submodular optimization with long-term constraints under semi-bandit feedback.  There would not be any baselines to compare it to.  All of the algorithms from previous works listed in Table 1 are for simpler settings (full information feedback, $0 \\in \\mathcal{K}$, some requiring exact gradients).  We could potentially empirically evaluate Algorithm 1 against those in simpler settings (full information feedback, $0 \\in \\mathcal{K}$, exact gradients) but we do not think it would be fair to do so.\n\n2. Similarly, our Algorithm 2 is the first algorithm for online stochastic DR-submodular optimization with long-term constraints with full-information feedback (when $0 \\in \\mathcal{K}$ is queryable).  There would not be any baselines to compare to (aside from our Algorithm 1 designed for a harder setting of semi-bandit feedback).   We could potentially apply Algorithm 2 in a simpler setting ($0 \\in \\mathcal{K}$, exact gradients) to evaluate against other algorithms listed in Table 1, though we think it would not be entirely fair to do so.\n\n3. Existing methods for DR-submodular maximization with long-term constraints typically exhibit high query complexity, often exhibiting $\\sqrt{T}$ per round for query complexity. In contrast, our method achieves a query complexity of just 1 per round. \n\n> The theoretical results, while commendable, are not particularly groundbreaking.\n\nWe highlight some aspects  we believe are significant in Q1 of the general response above.\n\n### Questions\n\n> I have no questions", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for carefully reading the paper and their constructive suggestions. In the following we address some common questions.

> Regarding technical contribution.

Some reviewers have concerns about limited technical contribution. Here we emphasize two technical novelties: 

1. Lemma 6, which upper bounds the relaxed constraint violation ($\tilde{g}_t$) using dual variables ($\lambda_t$), is completely new and is a critical result to derive the $\mathcal{O}(\sqrt{T})$ constraint violation. Previous works did not have an analogous bound. Without this bound, we would only be able to obtain a worse $\mathcal{O}(T^{3/4})$ constraint violation.  We obtained Lemma 6 by carefully digging into the updates of the $\lambda_t$'s and discovering some relations that we could leverage. We note that this lemma could be of independent interest to the online (non-)convex optimization community. For other papers dealing with the simpler setting of OCO that achieve better than $\mathcal{O}(T^{3/4})$ constraint violation, some special conditions (e.g., strong duality [Akhtar et al., 2021] or a strong convexity surrogate function [Yu et al., 2020]) are needed. However, when the objective is non-convex and such conditions are difficult to establish, our approach could potentially be used to obtain $\mathcal{O}(\sqrt{T})$ constraint violation. DR-submodular objective is one  such setting. 

2. Our algorithm design is simple, yet it has remarkably outperformed existing benchmarks in both regret and constraint violations. We believe achieving superior guarantees with a simple algorithm is a *strength* of our work, not a weakness. Furthermore, this simplicity also translates into complexity efficiency, as evidenced by the substantial reduction in the number of gradient oracle calls required by our algorithm (1 oracle query per round for our methods versus $O(\sqrt{T})$ for previous methods).

We will emphasize these arguments in the final version of the paper.

> Application examples of $0 \notin \mathcal{K}$.

We will discuss the following example motivating applications in the final paper to highlight the importance of general convex regions $\mathcal{K}$ for which the origin is not feasible. For such problems, the best-known approximation ratio is 1/2 [Hassani et al., 2017].

1. **Maximum Coverage [Krause et al., 2014]** Imagine a city's emergency management agency aiming to optimize the deployment of emergency response teams (firefighters, medical personnel, rescue teams) in many rounds during crises like major fires or earthquakes. The objective is to maximize coverage across different city zones. Allocating 0 teams to any zone isn't feasible, as it means no emergency response. The goal is to allocate resources in each round to maximize overall response coverage, while satisfying the long term agency budget.

2. **Budget Allocation [Soma et al., 2014]** This is a apecial case of the influence maximization problem. Let a bipartite graph $G = (S, T; W)$ represent a social network, where $S$ and $T$ are collections of advertising channels and customers, respectively. The edge weight represents the influence probability of channel $s$ to customer $t$. The goal is to distribute the per-round budget among the source nodes, and to maximize the expected influence on the potential customers over multiple rounds, while satisfying a long-term constraint (e.g., money spent). Corporate management may require a minimum level of customer engagement with each campaign overall or from select target groups.  There may also be per-round minimum contractual purchase requirements with the advertising partners.  Thus, allocating 0 budget in any round may not be permitted.

3. **Facility location [Krause et al., 2014]** Consider a scenario where a company needs to decide on the locations (virtual) to set up new service centers to maximize service coverage over multiple rounds, while satisfying a total budget constraint over all rounds. At each round, each customer segment must receive at least a certain level of service or coverage, which means 0 is not a feasible solution because no facilities cannot provide any service.

All the problems above were initially studied in discrete domain and extended to continuous domain in [Bian et al., 2019]. Furthermore, when faced with a discrete objective, one can always use the "relax and rounding" strategy to transition from addressing a discrete problem to tackling a continuous one. Such techniques are frequently utilized within the submodular maximization community, as exemplified by the work of [Chen et al., 2018].

#### Additional References
Bian et al. Continuous Submodular Function Maximization. 2020.

Krause and Golovin. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems. Cambridge University Press, 2014

Soma et al. Optimal budget allocation: Theoretical guarantee and efficient algorithm. ICML 2014.

Chen et al. Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity. ICML 2018.

Meta-review: Overall, the reviewers appreciated this paper's results, but there were some concerns regarding the technical contribution of the results and the comparison with prior work that was cleared during the author-reviewer discussion phase of the paper. The authors are encouraged to include the modifications suggested by the reviewers in the final version.
Decision: Accept (poster)