Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
Authors: Mohammad Pedramfar
Yididiya Y. Nadew
Christopher John Quinn
Vaneet Aggarwal
Venue: ICLR 2024 poster (2024)
Keywords: Stochastic optimization
submodular maximization
Frank-Wolfe algorithm
Primary area: reinforcement learning

Abstract: This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial continuous DR-submodular optimization, spanning scenarios such as full information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear $\alpha$-regret bounds or have better $\alpha$-regret bounds than the state of the art, where $\alpha$ is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-art sub-linear $\alpha$-regret bounds among projection-free algorithms in 7 of the 8 considered cases while matching the result of the remaining case. Additionally, this paper addresses semi-bandit and bandit feedback for adversarial DR-submodular optimization, advancing the understanding of this optimization area.

Published as a conference paper at ICLR 2024
UNIFIED PROJECTION-FREB ALGORITHMS FOR AD- VERSARIAL DR-SUBMODULAR OPTIMIZATION
Mohammad Pedramfar
Yididiya Y. Nadew
School of Industrial Engineering Purdue University West Lafayette, IN 47907, USA
Department of Computer Science Iowa State University
Ames, IA 50010, USA
mpedranff@urruee. edu
yididiya@ wwweeaassttee.e.e...aa.aaaaaeeee edu
Christopher J. Quinn
Vaneet Aggarwal
Department of Computer Science lowa State University
School of Industrial Engineering Purdue University
Ames, IA 50010, USA
West Lafayette. IN 47907, USA vaneet@purrdue.er
ej ejquinn@iastate edu
ABSTRACT
This paper introduces unified projection-free Frank-Woll Wolfe type algorithms for ad- versarial continuous DR-submodular optimization, spanning scenarios such full information and (semi-) (bandi feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. For every problem consid- ered the non-monotone setting, the proposed algorithms are either the first with proven sub-linear a-regret bounds have better a-regret bounds than the state of the art, where a is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-arr sub-linear a-regret bounds among projection-free algorithms in of the considered cases while matching the result of the remaining case. Additionally, this paper addresses semi- semi-bandit and bandit feedback for adversarial DR uR-suboodular optimization, ad- vancing the understanding of this optimization area.
INTRODUCTION
The optimization of continuous adversarial DR-submodular functions has become increasingly prominent recent years. This form optimization represents an important subset of non-convex optimization problems at the forefront of machine learning and statistics. These challenges have numerous real-world applications like revenue maximization, mean-field inference, and recommen-
dation systems, among others (Bian et al. 2019; Hassani al. 2017; Mitra et al. 2021 Djolonga & Krause 2014 Ito & Fujimaki] 2016 [0116) Gu et al. 2023] Li et al. 2023). The problems at hand can recurring game played between an optimizer and adversary. In each round of this game, the optimizer makes an action selection, while the adversary selects a reward function.
be conceptualized
The optimizer is then allowed query this reward function, either at any arbitrary point within the domain (full information) or specifically at the chosen action (in the case of semi-bandit/bame scenarios). The adversary provides noisy version of the gradient/value the queried point. This framework gives rise to a set of significant challenges, varying based on the properties of the DR- submodular function, the constraint set, and the types of queries involved.
This paper presents comprehensive investigation into online continuous adversarial DR- submodular optimization. There have been significant advances in recent years, though most re- search has predominantly focused on monotone (i.e., non-decreasing) objective functions and/or full information feedback via stochastic gradient queries. contrast, our study encompasses a broader spectrum, addressing combinations of: (i) monotone under downward closed (or convex sets containing the origin) or general convex sets, (ii) gradient value queries, and (iv) queries at arbitrary points only the current action. See Table 1 for
non-monotone functions, (ii) optimization

---

Published as a conference paper at ICLR 2024
enumeration of the cases along with corresponding approximation ratios a, query complexities (for full-information feedback), and a-regret bounds for prior works and ours.
In this paper, we propose Frank-Wolfe based algorithms for this diverse family of problems. For many cases in Table II our algorithms are the first to achieve sub-linear regret or improve on the state of the art. For non-monotone objective functions (i.e., the bottom half of Table []. our algo- rithms beat the state of the art for almost every combination of convex feasible regions (downward- closed or general), feedback models (full-information (with 7 queries for various 8), semi-bandit, bandit), and feedback type (exact/noisy gradient/value). See Fig. [ for a visual depiction of the im- proved regret bound and query complexity trade offs for non monooooo functions with downward closed feasible region and full- full-information feedback with (noisy) gradient queries. The single case for non-monotone objectives that our algorithms do not strictly improve on the prior works for general convex sets with full-information feedback of T1/2 gradients (per round), in which case the regret bound of our algorithm and that proposed by (Mualem & Feldman 2023 both have ÖVVT) dependence. We note for 7 queries with 0 S 3 2. our algorithm ' regret bound is strictly better.
For monotone objective functions (i.e., the top half of Table our algorithms achieve the first sublinear regret for general convex sets with full information value feedback and for gen- eral convex sets with bandit feedback. Our algorithms also achieve the first or better regret bounds than prior projection- free methods (those without "f" symbols in Table for all but one case, i.e. for general convex feasible regions with ban- dit feedback where match the results of Niazadeh et al. 2023 See Appendix A for more discussion.
Ó(T)
ODC
Regret Bound
Mono
Ours
((7))
OcT5)
6(r+)
1/4 1/2 3/4 5/4 3/2
P queries round)
Figure 1: :-rrgret bounds for non-monotone ffunctions with downward-closed feasible region and full-information (noisy) gradient feedback, as a function of query- complexity. ODC is from (Thang & Srivastay 2021). Meta and Mono are from (Zhng et al. 2023). Better per- formance corresponds to the bottom left corner. Our algorithm's regret bounds dominate the state of the art.
Our algorithms and most prior Frank-Wolfe based methods can rely on solving only linear optimization problems as sub- routines (hence referred to as "projection-free") Some of the prior works that use projected gradient ascent, in particular (Zhang et al. 2022] Chen et al., 2018b) (marked with "t" Table I. achieve superior regret bounds of Ö(VT) other prior works and our algorithms. In some instances, solving projection (or other non-linear optimization problems like Wann et al., 2023 Thang& & Srivastav 202Ib) as a sub-routine can be computationally expensive. Braan al. (2022) identify matrix completion, routing and graph problems. and problems with matroid polytopes as example problems for which efficient to solve linear optimization problems but solving projections can be expensive. (Chen et al. 2018a &a) showed projected gradient ascent took between five to eight times longer than several Frank- Wolfe based methods even for small matrix completion tasks. Thus, for some large-scale problems, if the agent has limited per-round computational resources, the regret bounds achieved by projection- free methods (for which our methods match or improve on the state of the art) could represent the best aaeetcclly-achievabbee
regret-bounds.
The key contributions of this work can be summarized as follows:
1. We propose unified framework for Frank-Wolfe type (projection-free) algorithms for adversar- ial continuous DR-buboodular optimization, spanning scenarios with different types of feedback (full information, semi-bandit, and bandit; exact stochastic), objective function classes (mono- tone and non-monotone), and convex feasible region geometries (downward-closed, origin fea- sible, general). In particular, we provide the first projection-free algorithm for online adversarial maximization of monotone functions over general convex sets for any feedback and oracle type.
2. For the class of non-monotone DR-subnodular functions, our algorithms achieve the best (in some cases the first) sublinear a-regret bounds for all feedback models and feasible region ge- ometries considered.
The result of [Niazadeh et al. 2023 is proven for monotone functions over d-dimensional downward- closed convex sets given a deterministic value oracle. However, as we discuss in Appendix[C] replacing their shrunk constraint set with the construction presented in (Pedramfar et al. 2023) together with a more detailed analysis of their algorithms can be used to obtain the same regret bounds for monotone functions over all convex containing the origin when we only have access stochastic value oracle.
2

---

Published as a conference paper at ICLR 2024
Table I: Online DR-submodular optimization results.
Set
Feetback
Relerence
Appx.
ool queries
Chen et all 2018b (*)
I-e"t
( 0. 1/2)
Niazadeh ct al. 2023
1-e-t
(8 c 0. 1/2)
Chen el al 201
(3 e (0,3/2)
8/3
V.
Full Information
Zhang 2019
stoch.
1800 et ml 212.5
----
3/4
0 K
hang ot al 2022
1/2
Monotone
This paper
( [0. 1/2))
2/3
8/3
Semi-bandit
stoch.
This paper
1-
3/4
Full Infiormation
stoch.
This paper
1-
7 1/2)
3/5 3/5
ZZhany et
8/9
det.
(Niazadch 2025
5/6
Bandit
Waan ala 2025
3/4
stoch.
T1is paper
Full Information
stoch.
This papey
1/2
( 1/2))
2/3 9/3
general
Somi-bandit
stoch.
Chen ct ol. 20186
THBN [Spper
172
1/2
3/4
1/2
F
Full Information
Bandit
stoch.
stoch.
This paper
This paper
1/2
172
T 1/2)
3/6 3/6
Thang & Srivastav 2021
T' (0, (0,3/4]
5/3
Full Informmation
stoch.
Zhang et al. 2023
e-1
(3 (0,3/2]
0/3
F
Zihang al.
4/5
d.c.
Tlass puper
( [0. 10.1/2)
2/3 8/3
Non Monotone
Semi-bandit
stoch.
This paper
3/4
Full Information
stoch.
This paper
(3 00. 1/2]:
3/4 37b
F
det.
Zhhnn al. 2025
stoch.
Tais paper
e
3/6
Thane & Srivastav
2021
(1 h)/3/3
T > 0)
Full Information
stoch.
Mualem & Foldman
2023 (2)
(1 1//1
(3 1/2])
Tlass paper
(1 h//1
2 e 10.1)
2/3
9/3
Somi-bandit
stoch.
This paper
(1 hy4
3/1
Full Information
stoch.
This paper
(1 A)/4
(
00. 1/2)2
3/5 8/5
Bandit
stoch.
This paper
(1 1074
5/6
Here / := minaek: ||/|
The rows marked with (*) are special cases of our algorithms with appro-
priate hyperparameters. The rows marked with use gradient ascent, requiring potentially computationally expensive projections. $ (Wan al.) (023) uses a convex optimization subroutine in each iteration. The logarithmic terms in regret are ignored. Sce Appendix [A.2] for details.
3. For the class of monotone (i.e., non-decreasing) DR-submodular functions, our algorithms achieve the state of the art a-regret bounds 4 of the cases P Moreover, if we only com- pare with other projection-free algorithms. then we obtain the state of the art in 7 out of the 8 cases and match the result of (Niazadeh et al. 2023) in the last case
In addition to the enumerated list above, our technical novelties include (i) novel combination of the idea of meta-actions and random permutations to obtain a new algorithm in ooll-information set- ting; (ii) handling stochastic (gradient/value) feedback without using variance reduction techniques like momentum, which in turn leads to state of the art regret bounds; and (iii) a unified approach that specializes multiple scenarios considered in this paper. See Sections 3.1 and 3.2 and Ap- pendix [A.2] for more details. Table I describes the key comparisons of our works, where the related works are expanded in Appendix
BACKGROUND AND NOTATION
We introduce some basic notions, concepts and assumptions which will be used throughout the paper. For any vector x E Rd, [x]: is the i-th entry of x. We consider the partial order on Rd where x S y if and only if [x]; S [y]e for all < i < d. For two vectors x. y Rd the join of x and y, denoted by x V y and the meet of x and y, denoted by x A y, are defined
x Vy = (max Mi and
X A y == [min([x]: M
(1)
respectively. Clearly, we have x Ay S X xVy. We use x y for coordinate- wise multiplication. We use || to denote the Euclidean norm, and || Il to denote the supremum norm. In the paper, we consider a bounded convex domain and w.l.o.g. assume that X. C [0, 1fd. We say that IC is downward-closed (d.c.) if there is point E K. such that for all z E K. we have (x u x < z} S K. Unless explicitly stated, we will assume that downward-closed convex sets contain the
Algorithms for bbandit feedback can be used in full-information setting. Therefore (Cen et al. 2018h) obtains the state of the art in both semi-bandit and full-information setting for monotone functions over general convex set when given access to gradient oracles.
3

---

Published as a conference paper at ICLR 2024
origin. The diameter D of the convex domain I, is defined D supx,yxx//x y/|. We use (x) denote the open ball of radius r centered at x. More generally, for a subset X _ Rd, we define (x) == Uxex (x). For an affine subspace A of IR", we deñine [B == A (X). We will use R to denote the set {x Ix 2 0}. For any set X [ IR the affine hull of X, denoted by aff (X), is defined to be the intersection of all affine subsets of TRd that contain X. The relative interior of a set X is defined by
relint(X)= :- E 3s > O, B (x) S CX.
It is well known that for any non-empty convex set K,, the set relint(K)) is always non-empty. We will always assume that the feasible set contains at least two points and therefore the dimension d' == dim = dim((af(
2 1, otherwise the optimization problem is trivial.
A set function {0, 11dd + R called submodular if for all x,y E {0, with x yy.
f(xVa) - fxx - fly v a) - f(y),
Va E {0.1)a.
(2)
Submodular functions can be generalized over continuous domains. A function F [0, 1|d
IR is called DR-submodular if for all vectors x, E [0, 1] with x y. any basis vector e; (0, ... 0,1,0,... ... .0 and any constant e > 0 such that x + ce, E [0, 1] and y + ce, E (0, 1Ja
F(x co.) - F(x) 2 Fly + ce,) - Fly).
Note that if a function F is differentiable then the diminishing-retura (DR) property (3) is equivalent to Fx) Fly) for S y with x,y E 1]4. A function F D - R is M1 Mi-iipschizz continuous if for all x, E D, (77(x)=PPyl) M2-smooth if for all x,y D, [V(()) VF())] S M2 yll. DR-submodular F is monotone if F (x) 2 Fly) for all x 2 y.
S. Mi]lx-ylll A differentiable function F D + I
2.1 PROBLEM SETUP
Adversarial bandit optimization problems can be formalized as a repeated game between an opti- mizer and an adversary. The game lasts for T rounds and T is known to both players. In t-th round, the optimizer chooses an action x, from an action set K, then the adversary chooses reward func- tion F. E F. We assume that the function class F has functions that map K. to a bounded interval [0, Mo] C R. We consider the setting with oblivious adversury where the choice of the sequence of functions F; is not affected by the choice of the optimizer. In other words, may assume that the adversary chooses the sequence {Fi before the first action of the optimizer.
Before we discuss different forms of feedback, we first formally define the notion of oracle. A stochastic non-oblivious value oracle for the function F : I.C + R is tuple (30, F) where 30 is an arbitrary measure space, Po : 30 X K. + IR is a non non- -eggatitt measurable function such that So, pz(z; x)dz for each x E and F: 30 x K +
IR is a measurable function such that
F(x) = Ex (:xx [F(z,
for all x E K. We will use F(x) denote the random variable F(x, 2) where z is random variable samples according to the distribution (=)):)). Such an oracle would be called an oblivious oracle when Po(:; x) independent of the choice of We consider the more general setting where we only have access to a non-oblivious oracle, i.e., where x-(::) may depend on x.
Similarly, non-oblivious gradient oracle for the function F K. R is tuple (31,Pı. F) where 31 is an arbitrary measure space, P1 : 31 x IC - R is a neg-tegetive measurable function such that f3, Pi (z(z: x) for each K and VF 31 + R is measurable function such that
VF(x) = E EEzpi VF (x,,))),
for all x K. Similarly, we will use FF(x) to denote the random variable FF z) where is random variable sampled according to the distribution P1 (:)
Assumption 1. We assume that the functions F. [0, 1] - R are DR-submodular, first-order differentiable, non-negative bounded by My. M1 Mi-Lipcchizz and Mæ-smooth for some values of My. M1, M2 cc. Note that this implies that V [x)ll < Mr. Moreover, we also assume that either have access to a value oracle bounded by By or a gradient oracle bounded by B for some values for some Bo, B₁ < xc.
4

---

Published as a conference paper at ICLR 2024
Remark 1. The proposed algorithm does not need know the values of Mo. M1, M2. Bu B1, in advance. However these variables appear in the regret bounds. Note that we always have Bo 2 Mo and B 2 M1. Exact oracles special cases of stochastic oracles with Bo Mo and Bı M When we have access to exact oracles, the performance of the proposed algorithms does not change beyond the replacement of Bo with Mo and B1 with M1.
We consider different forms of feedback to the optimizer:
Full Information with gradient query oracle: In this feedback model, the optimizer allowed to query a stochastic non-oblivious gradient oracle V Fx()) for Fe : K. at multiple points. We assume that the optimizer can query P. total of 7 times, where 3 2 0 gives range from constant queries to infinite queries.
Full Information with value query oracle: Same as the previous case, but the adversary reveals stochastic non-oblivious value oracle (x)).
Semi-Bandit: In this feedback model, the adversary reveals a gradient sample (y.)) for the specific action yt taken, where FF, a stochastic non-oblivious gradient oracle for Fe.
4. Noisy Bandit: In this feedback model, the optimizer can only observe sample of (y.)). where Fe is stochastic non-oblivious value oracle for F, Such feedback model is generalization of what called full-bandit feedback in the literature. In the full-bandit feedback setting, the optimizer observes the exact value of (y.).
We note that the full information feedback can query at any point in KC, while the semi-bandit and bandit feedback can only query at yt in time f. Also note that the distributions Pa and p1. described in the definition of stochastic oracles, may depend on the function Fg. We will use a superscript, i.e., ph and pi, to specify the function in question.
Please note that even when dealing with offline scenarios, is NP-hard to solve a DR-submodular maximization problem (Bian al. 2017b). For the problems consider, however, there are poly- nomial time approximation algorithms. We let a denote corresponding approximation ratios. Thus, the goal of this work is to minimize the a-regret, which is defined as:
R₂
Σ F.ly) Σ F.(y.) t=1
(4)
YεK
In Appendix A.I
we discuss the best known approximation ratios different settings.
Remark 2. Any algorithm designed for semi-handit setting may be trivially applied in full- information setting with a gradient oracle. Similarly, any algorithum designed for bandit setting may be applied in full-information setting with a value oracle.
Remark 3. As special case, if all of the functions F; are equal, then the semi-bande setting we consider reduces to online stochastic continuous oR-submodulaar maximization. See Table function, (ii) constraint set choices, or (ūi) handit/semi-bande feedback. These results achieve the same regret guarantees in (Pedramfar et al. 2023). and thus match the state of art for projection-fres algorithms all cases.
in Appendix for the list of previous results in this setting for (i) monotone/non-monon
PROPOSED ALGORITHMS
In this section, we describe the proposed algorithm with different forms of feedback and the dif- ferent problem setups (based on the properties of the functions and the feasible set). For efficient description of the algorithm, we first divide the problem setup into four categories:
(A) The functions {F.)T= are monotone DR-submodular and K.
(B) The functions (F.TT containing
[ non-monotone DR-submodular and K. is downward closed set
(C) The functions ( are monotone DR-submodular and K. is general convex set.
( The functions (F.)_= non-monotone DR-submodular and IC is general convex
5

---

Published as a conference paper at ICLR 2024
The four divisions here for the problem provide different approximation ratios for the problem. Thus, the algorithm steps and the proofs change with these cases. For combining definitions in the different forms of feedback, we define
x K (v - u1
(A);
oracle-ady (d. (d. dd x)
(B); otherwise,
x K (v 2 (
(B);
.update(x, v.
(1 EC)x EOV
(C);
EDD-EDX+-20 TEDV
(D),
where Sc (A), for case (B), for case (C), and 1-h for case (D), where h == minger |z||000 Further,
K)) and (2) K
We also define the approximation ratio as for case
2K
FF()) d' 8
gradient oracle;
grad-estimate((Pxx..
F(x ōu)u value oracle.
In the following subsections, we divide the proposed algorithm into different feedback scenarios.
Input:
smoothing radius 6, shrunk
3.1 FULL INFORMATION
constraint set K. horizon T' block
size L,, number of lincar maximization oracles K, online
There are four main ideas used Algorithm D that allows us obtain the desired regret bounds.
linear maximization oracles on C: g(), ..... ,E g(R), number of blocks
T
Offline bounds Given a submodular func- tion F, sequence of vectors (v(K)) in the con- set K. and sequence of points x(++1) update(x(()) v(()) for k E [K] for any x" E K. we may bound aF(x") - ((x((++)) from above by the sum of a known lerm and a linear combi- v(k) -x)),
for 4 1,2,. do
Pick any u argmin ||x||
Xi
t u .....,K
for le = ....... K do
ve vo E K be the output of g(k) in round
nation of (oracle-ady( (ood Fx)()),,
(k+1)
update(xx (N) (K)
for k [K].
Xg
end
See Lemma g for the exact statement for different cases. This Jemma captures the core idea behind all Frank- Wolfe type algorithms for DR- Dubbuuuod maximization. In particular, if we choose
X₂ x4 Let (fq.1..... ..) be random
(K+1)
permutation of {q 1)L + .LL
for t = (q 1)L 1.....q. .6. do Play yt = xg and obtain the reward
(k) E argmaxvex (oracle-ady (VF(()()) (k)),
Fy
Find the corresponding [4] such that
recover the results in offline setting with ac-
L= 1=4g
cess to a deterministic gradient oracle. Lemma g is reformulation of some of the ideas presented
for [K] such = (mnod L)
we have value oracle, sample
in (Bian et al.] [017b]aa Zhang et al.] 2023 Du 2022
(k)
get11 n Co uniformly, otherwise
u,
Mualem & Feldman 2023) and (Pedramfar
(+) +
u,
et al. 2023).
d(a
grad-estimnate(FF Fe,, (.::1 uy (1)
(b)
(k)
+ oracle-adv(d))) (k)
X2 (k)
Meta actions Having 1, 0, and ac- cess to gradient oracles corresponds to the idea of meta-actions (without using Ideas 3 and 4). The idea of meta-actions, proposed in (Streeter & Golovin 2008) for discrete submodular functions, was first used for continuous DR DR-submodular maximization (Chen et al., 20188). This idea allows us to con- vert offline algorithm into online algorithms. To be precise, let us consider the first iteration and the first objective function F1 of online optimization setting. Note that F1 remains unknown until the algorithm commits to a choice. we were in the offline setting, we could have chosen
ga
Pass sa the adversarially chosen
(k)
vector to g(k)
end
end end
Algorithm 1: Generalized Meta-Franks Wolfe
(K) argmaxvex (oracle-adv(V/I
(k)), v),
obtain the desired regret bounds. The idea of meta-actions is mimic this process in an online setting as follows. We run K instances of an online linear optimization (OLO) algorithm, (g(K) 1==--

---

Published as a conference paper at ICLR 2024
Here the number K denotes the number of iterations of the offline Frank-Wolfe algorithm that intend to mimic. Thus, to maximize (oracle-adv(VF) (x(A)) )),,
.), we simply use E(,), Once the function Fi is revealed to the algorithm, knows each linear maximization oracle "adversaries" foraclo-adv (x) ) B Now, we simply feed each online algorithm g()) with the re- ward {oracle-adv V F (x (10), )1) We repeat this process for each subsequent function (22. This idea, combined with Idea I, allows us to obtain the desired a-regret bounds.
Remark 4. We assume that every instance E(k) has the following behavior and guarantee. In every block S a950
U.Q. Q, the oracle g(k selects a vector Va
(k) and then the adversary reveals
vector By to the oracle that was chosen independently of Vq
(K)
(k) The OLO oracle guarantees that
i (g))) ,x' xx') S R&² for some regret function Reth. One possible choice for such
an oracle is hewrw-ttee-ertubeed---ee Leader by (Kalai & Vempala 2005 that guarantees RQQ S
CDBVQQ where D is the diameter of K. B maxx, & l|gg || || and C > 0 a constant. It follows from the definition of grad-estinate that if we have access to gradient oracles, then B < B,, while if we have access to value oracles, then B < d' Bo-
Input: smoothing radius 8, shrunk constraint set K,
3. Random permutations Using ran- dom permutations allows us to use less queries at the cost of increased regret. In the context of DR- DR-submodular maximiza- tion, this idea was first used in Mono- Frank-Wolfe algorithm in (Zhang et al.) 2019). The Mono-Frank- Wolfe corre- sponds to Algorithm [ when K L and we have access to a gradient oracle. Here describe this idea in the general set- ting where we allow K * L, while we still assume access to gradient oracle. We start by dividing the ''' functions into Q TT/LL blocks of length L. We define : as the average of functions in the q-th block. For each block q. we pick a random permutation 14g.1,.... r.) of 1) 1,....qL) .L)) uniformly from the set of all of its permutations. The key insight is that for all (q- L)L < t < qL, the expected value of F2 is Fg. Therefor we can estimate F using information obtained from functions F, for (q - us to apply the idea of meta-actions on the sequence of functions (Fg (
horizon T, block size L, the number of exploration steps per block K L, online linear maximization oracles on A::
(()) (K)), number of blocks Q = T/L.
for = 1,2. Q do
Pick any E arginin ER ||x 1oo (3)
for k 1,2,.... K do
Let ve (k) R be the output of g()) in round x (k+1) update(x (k) (1)
v
end
(K+1)
X₂ f- x Let (fq. 1.... tq.t) be a random permutation of {ig 1)L + 1, 1.....999.. 9L}
for (q 1)L + 1.....II.
qL do if t E [ly.1.... .,, then Find the corresponding & E [K] such that t ty. If we have value oracle, sample u sd Lo uniformly, otherwise un! O Play y: = y = x, + ōu, for P. (i.c., Flg
// Exploration
d! - grad--stimate(ff" (ii Fi, x. (() (()
S 9L which allows
B7 +- oracle-adv (d! )
Q
Pass ga as the adversarially chosen vector to g())
(k)
else
Play y: =x, for Fi
// Explastation
4. Smoothing trick When we do not have access to a gradient oracle, we rely on samples from value oracle to estimate the gradient. The "smoothing trick" (Flaxman
end
end
end
Algorithm 2: Generalized (Semi-)Banddit-raak- Wolfe
al.. 2005:
Hazan et al. 2016 Agarwal
et al. 2010; Shamir 2017 Zhhan et al.
2019
Chen al. 20200] Zhang et al.] 2023) Niazadeh et al. 2023 Pedramiar al. 2023) involves
averaging through spherical sampling around a given point. Here we use a variant that was intro- duced in (Pedramfar et al.) 2023).
Definition 1 (Smoothing Trick). For function F D R defined D C Rd, its 8-smoothed version F is given as
(x(x) == E, 22BBBH1 [F(z)] = [F((
|F ( 8v)],
(5)
7

---

Published as a conference paper at ICLR 2024
where is chosen uniformly random from the (D) dimmensional ball B3, the function value (x) is obtained by "averaging" " F over a sliced ball of radius 8 around
(=ft(())x((0 Thus,
The power of the smoothing trick lies in the facts that is good approximation of the original function (Lemma 1 and there is a simple one-point gradient estimator for the smoothed version of the function (Lemma We will drop the subscript when there is no ambiguity.
Note that the domain of F is smaller than the domain of F. Therefore, our ability estimate the gradient is limited to a smaller region compared to the entire feasible set. This limitation should be considered when developing an algorithm for DR-submodular maximization. The notion of "shrunk constraint set" (Zhang et al. 2019 2023 Niazadeh et al. 2023; Pedramfar et al., (023) was designed to address this concern. Here we use the variant designed by (Pedramfar et al. 2023). Formally, we choose a point E relint(A.) and real number r > 0 such that (,
(c) S K. Then, for given 8 r, we define A (1 - ) + cc. Clearly if K. is downward-closed then is K.g... We will use the notation I to denote this set when there is no ambiguity.
Putting these ideas together, in order to maximize F over IC with value oracle, we restrict ourselves to the shrunk constraint set K. and maximize F over this set using the one-point gradient estimator.
3.2 (SMII))ANNE FEEDBACK
In the (semi-)bandit feedback setting, we only observe the value or gradient at the point where the action is taken. To adapt Algorithm T to this setting, we start by assuming K < L. In each block, there are L functions that are used update K linear maximization oracles. Therefore, we may choose K exploration steps in each block where we take actions according to what we queried in Algorithm ] These actions are informative and allow us to earry out similar analysis the full information setting. In the remaining L K steps, we exploit our knowledge of the best action so far to minimize total a-regret. See Algorithm 2 for pseudo-code.
4 a- a-REGRET GUARANTEES
For brevity, we define R" as
T5 R" (Mo + (3+ D)M,
(8Mg + M2D² log (K)g T + LCDBB/log(K)) (Mo 2M2 IR -CDBVQQ
(C); Otherwise,
where B < Bi if we have access gradient oracle and B S d' o By otherwise and C is the constant in Remark
Theorem 1. Using Algorithm 7 we have [[(R.]] S R".
The proof is in Appendix F Note that the number of times any function F; is queried in Algorithm
is K/L. Let B be real number such that T K/L. Given gradient oracle, for any choice of
0 ss 3 < 1 we may set 0, = T 2-29 and therefore K = T
1+. and Q = T/L L = T 2+28
to
obtain E[Ra] O 8-8 (T) in case (C), and OTT 2-
otherwise. The special case L corresponds to BeaaaFraan- Wolfe (Chen et al.) 2018b Zhang et al.) [023] Thang & Srivastav)
2021 Mualem Feldman 2023) while the special case
T.= K corresponds to Mono-Frank Wolfe
Zhang et al. 2019: 2023 Similarly, given value oracle, for any choice of 0 < B < 1 by
setting 6 = T
L
2-d and therefore K = 2 and Q = T/T. = 2440 we see that
E[Ra] = O ?T) in Case (C), and =5 3-1
otherwise.
Theorem 2. Using Algorithm 2 we have E[R.] < R" n 2M,QK.
The proof is in Appendix In particular, given a gradient oracle, we may set 5 0. K T1/1 and 1/22 and therefore Q 71/2, to obtain E[R.] 3/33/4 log(T))3 in Case (C) and 8/44)) otherwise. Similarly, when given value oracle, if we set K 1/6 L 1/3 8 T 1/6 and 5/6 log(T)2) in Case (C) and OTT5/6), otherwise.
therefore Q 22/3 that [R.... O
8

---

Published as a conference paper at ICLR 2024
25,
40.m
20
15
More
CBC
Lato wo..-e--- LM]
30
Mire
40
006
Meno
GHAMLS
GHIML1S-20 2010
(arragg 1.1
25
30-
137W
10
15
20-
10
10-
01
0-
0
250 Iteration indext
250
Iteration
Reration
25.m 15
n 40,m m 20
n m
50,m 50
107
10a
10a
Cumuistive
102
10a
10a
20
320
160
40
160
Horizon
Horizon
Figure 2: Empirical regret plots for the experiments. The top row depicts time-averaged regret for each round for a horizon of T 500. The bottom row depicts cumulative regret for multiple horizons with logarithmic scaling. Grey lines in the bottom row represent y aTT'/2 curves for different for visual reference. Colors correspond to regret bounds (i.e. black for O Our methods (solid lines) use significantly fewer queries and less computation than baselines (dashed and dotted lines) with similar regret bounds and achieve better regret than baselines using similar numbers of queries and computation.
EXPERIMENTS
We test our online continuous DR-submodular maximization algorithms for non-monotone objec- tives, a downward-closed feasible region, and both full-information and semi-bandit gradient feed- back. We briefly describe the setup and highlight key results. See Appendix H for more details. We use online hatr--covccoooccooeeeee concave non-monotone quadratic maximization following (Bian) eet al., 2017a| Chen et al., 2018b: Zhang et al., 2023), randomly generating linear inequalities to form a downward closed feasible region and for each round t we generate a quadratic function Fx(x) f Hx h x + c. Similar to (Zhang al. 2023), we considered three pairs m) of dimensions n and number of constraints m. [(25, 15), 20), 50)).
We three online algorithms from prior works, ODC from Thang & Srivastav 2021 Mono (full information single query) from (Zhang et al. 2023), and Meta(3) from (Zhang et al. 2023), where we used query parameters 3 [3/4, 3/2]: here and in the following we only explicitly mention the query parameter so that there are T queries per round and other algorithm parameters implicit. We ran our Algorithm (GMFW(3) for short) with query parameter f 1/4, 1/2) and our Algorithm (SBFW for short). Fig. T depicts regret bound and query complexity trade offs for full-information methods.
Figure 2 shows both averaged regret within runs for fixed horizon (top row) and cumulative regret for different horizons, averaged over 10 independent runs. See Fig. 2 caption for description. Average run-times for a horizon of T 100 are displayed in Table in Appendix H Major dif- ferences in run-times is in large part due to the number of online linear maximization oracles used, which is in part related to the number of per-round queries.
In each experiment, our GMFW(3 = 1/2) (black solid line) performs the best overall, despite using significantly fewer gradient queries and significantly less computation than any of the Meta algorithms. Our GMFW(3 = 0) (red solid line) performs better than the baseline Mono (orange dashed line; designed for the same amount of feedback).

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported in part by the National Science Foundation under grants CCF-2149588 and CCF-2149617. We also thank the authors of (Zhang et al. 2023 for sharing their code.
REPRODUCIBILITY STATEMENT
Source code for our algorithms is available at see-ieddddd-suumoduulldl All assumptions are included the main paper Assumption All proofs are included in the appendices.
REFERENCES
Alckh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Proceedings of the 23rd Annual Conference on Learning Theory, 2010.
An Bian, Kfir Levy, Andreas Krause, and Joachim M Buhmann. Continuous DR-submodular max- imization: Structure and algorithms. In Advances in Neural Information Processing Systems, 2017a.
Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, April 2017b.
Yatao Bian, Joachim Buhmann, and Andreas Krause. Optimal continuous DR-submodular maxi- mization and applications to provable mean field inference. In Proceedings of the 36th Interna- tional Conference on Machine Learning, June 2019.
Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional Gradient Methods. arXiv preprint arXiv:2211. 141003 November 2022.
Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free online opti- mization with stochastic gradient: From convexity to submodularity. In Proceedings of the 35th International Conference Machine Learning, July 201 8a.
Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. In Proceedings of the Twenty-Firsl International Conference on Artificial Intelligence and Statistics,
April 2018b.
Lin Chen, Mingrui Zhang, Hamed Hassani, and Amin Karbasi. Black box submodular maximiza- tion: Discrete and continuous settings. In Proceedings of the Twenty Third International Confer- on Artificial Intelligence and Statistics, August 2020.
Shengminjie Chen, Donglei Du, Wenguo Yang, Dachuan Xu, and Suixiang Gao. Continuous non- monotone DR-submodular maximization with down-closed convex constraint. arXiv preprint arXiv:2307.09666, July 2023.
Alon Cohen and Tamir Hazan. Following the perturbed leader for online structured learning. In Proceedings of the 32nd International Conference on Machine Learning, July 2015.
Josip Djolonga and Andreas Krause. From map to marginals: Variational inference in Bayesian submodular models. Advances in Neural Information Processing Systems, 2014.
Donglei Du. Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization. arXiv preprint 2205 2022.
Donglei Du, Zhicheng Liu. Chenchen Wu, Dachuan Xu, and Yang Zhou. An improved approxi- mation algorithm for maximizing a DR-submodular function over a convex set. arXiv preprint arXiv:2203. 14740, 2022.
10

---

Published as a conference paper at ICLR 2024
Christoph Dürr, Nguyen Kim Thang. Abhinav Srivastav, and Léo Tible. DR-submodular maximization: Approximation and regret guarantees. TrXX:::905.09595. 2019.
Non-monotone
arXiv preprint
Uriel Feige. threshold of In for approximating set cover. Journal of the ACM, 45(4):634-652,
July 1998.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 385-398-- 2005.
Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp- 1098 16, January 2011.
Shuyang Gu, Chuangen Gao, Jun Huang, and Weili Wu. Profit maximization in social networks and non-monotone DR-submodular maximization. Theoretical Computer Science, 957: 357:113844 13884,, 2023.
Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular max- imization. In Advances in Neural Information Processing Systems, 2017.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
Shinji Ito and Ryohei Fujimaki. Large-scale price optimization via network flow. Advances in Neural Information Processing Systems, 2016.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-37,, 2005.
Amin Karbasi, Hamed Hassani, Aryan Mokhtari, and Zebang Shen. Stochastic continuous greedy ++: When upper and lower bounds match. Advances Neural Information Processing Sys- tems, 2019.
Yuanyuan Li, Yuezhou Liu, Lili Su, Edmund Yeh, and Stratis loannidis. Experimental design net- works: paradigm for serving heterogencous learners under networking constraints. IEEE/ACM Transactions Networking, 2023.
Yucheng Liao, Yuanyu Wan, Chang Yao, and Mingli Song. Improved Projection-free Online Con- tinuous Submodular Maximization. arXiv preprint (tt.:2305./8442 May 2023.
Siddharth Mitra, Moran Feldman, and Amin Karbasi. Submodular+ concave. Advances in Neural
Information Processing Systems, 2021.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods:
From convex minimization to submodular maximization. The Journal of Machine Learning Re- search, 21(1):4232-4288 2020.
Loay Mualem and Moran Feldman. Resolving the approximability of offline and online non- monotone DR-submodular maximization over general convex sets. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, April 2023.
Rad Niazadeh, Tim Roughgarden, and Joshua R Wang. Optimal algorithms for continuous non- monotone submodular and Dussubmodular maximization. The Journal of Machine Learning Research, 21(1):4937-4967, 2020.
Rad Niazadeh, Negin Golrezaei, Joshua Wang, Fransisca Susan, and Ashwinkumar Badanidiyuru. Online learning via offline greedy algorithms: Applications in market design and optimization. Management Science, 69(7):3797-381) July 2023.
Mohammad Pedramfar, Christopher Quinn, and Vaneet Aggarwal. A unified approach for maximiz- ing continuous DR-submodular functions. Advances in Neural Information Processing Systems, December 2023.
11

---

Published as a conference paper at ICLR 2024
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Proceedings the st International Conference on Neural Information Processing Systems, pp. 1577-1584, December 2008.
Nguyen Kim Thang and Abhinav Srivastav. Online non-monotone DR-submodular maximization. Proceedings of the AAAI Conference on Artificial Intelligence, May 2021.
Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal Computing, (2(1):655-304 2013.
Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, and Zhijie Zhang. Bandit multi-linear dr- submodular maximization and its applications on ad adversarial submodular bandits. In International Conference on Machine Learning. 2023.
Mingrui Zhang, Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization: From full-information to bandit feedback. In Advances in Neural Information Processing Systems, volume 32, 2019.
Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submod- ular maximization: Boosting via non-oblivious function. In Proceedings of the 39th International Conference on Machine Learning, 2022.
Qixin Zhang, Zengde Deng, Zaiyi Chen, Kuangqi Zhou, Haoyuan Hu, and Yu Yang. Online learning for non- oon-oontonee Duusuboodular maximization: From full information bandit feedback. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, April 2023.
12

---

Published as a conference paper at ICLR 2024
A DETAILS OF RELATED WORKS
A.1 OFFLINE UR-SUUMODULAR MAXIMIZATION
The problem of continuous DR- submodull where they introduced a variant of the maximization was considered by Bian et al. 7017b)
algorithm for maximizing a monotone DR-
submodular function a convex set containing the origin. They assumed access to a deterministic gradient oracle and guaranteed an optimal (1 -pappooximaaoonn with an additive error of (e)
using (1/)) oracle queries. We will refer to this guarantee as having the query complexity of O(1/E). Feige 1998) proved that discrete submodular maximization for monotone functions with cardinality constraint NP-hard for any approximation coefficient higher than (1 - 1/e). Using the results of (Feige) 1998), Bian et al. (2017b) showed that, for continuous DR-submodular functions over downward closed set, obtaining hard. Karbasi et al.] (2019) proposed a Frank- Wolfe variant with access to a stochastic gradient oracle with known distribution that obtains (1 1/e >aappoxximation coefficient with (11/e") oracle queries. They also proved that, in this setting, the oracle complexity of ( /s²) is optimal.
approximation coefficient higher than (1 - 1/e) is NP-
Later, another Frank- Wolfe variant with different update rules was proposed by Bian al. (2017a) for non-monotone DR-submodular maximization over downward-closed convex sets given a deter- ministic gradient oracle, obtaining a c d-approximation with the same query complexity of O(1/s). Gharan & Vondrák (2011) showed that obtaining an approximation ratio of higher than 0.491 re- quires exponentially many queries of the oracle. Very recently, Chen al. (2023) obtained 0.385- approximation with a query complexity of O(1/s). It is not known if that coefficient is optimal; finding an algorithm with the optimal approximation coefficient in this setting remains an open problem.
The first projection based algorithm for DR-submodular maximization was proposed by (Hassani et al. 2017) for monotone functions over a general convex set. They obtained a 1 g-approximation guarantee with query complexity of ((1/E) for deterministic gradient oracles and O(1/=²) for stochastic gradient oracles. They provided an example showing that projected gradient ascent can not obtain better approximation coefficient in this setting. Currently, it remains open prob- lem whether it is possible to achieve a higher approximation coefficient with sub-exponential query complexity. Later Pedramfar et al. (203)) used Frank-Woo -Wofe variant to obtain --approximation guarantees for maximizing a monotone function over a general convex set with (11=)) query com- plexity for deterministic gradient oracles.
Hassani et al. (211)) also constructed an example showing that directly replacing a deterministic gradient oracle with stochastic one in (Bian et al. (017b) can result in arbitrarily bad results. To solve this issue, |Mokhtari et al. (2020) used a variance reduction technique, namely momentum, which reduces variance but introduces bias in controlled manner, obtain query complexity of O(L/=3) for monotone functions over convex sets containing the origin. Similarly, they also obtained a query complexity of ((1==²) for non-monotone functions over downward-closed convex sets. Zhang et al. (2022) proposed a novel gradient-based approach for monotone functions over convex set containing the origin to obtain an approximation coefficient of (1 1/e) with ((1/²²)
query complexity.
Vondrák 2013) proved that, for non-monotone functions over a general convex set, no constant approximation ratio can be guaranteed in sub-exponential time. However, as demonstrated in (Dür al. 2019), we may obtain approximation ratios that depend on the geometry of the convex set. Specifically, given deterministic gradient oracle for non monotone function over a general convex set, they proposed an algorithm that obtains a 1 (1 - h) apparooxxittaoon of the optimal value with 3/3
an oracle complexity of O(ev d/e where h == minger ||z||>o and is the dimension of the domain 2022) obtained a (1~A) approxxmmaiion guarantee with the same oracle complexity and Du 2022)) obtained a (1-h)- approximaain guarantee with O(1/e) query
of the function. Later, Du et al.
4
complexity. Mualem & Feldman (022)) proved that the approximation coefficient (1-A) is optimal in this setting and obtaning any higher approximation coefficient requires exponentially many oracle
queries.
13

---

Published as a conference paper at ICLR 2024
The problem of DR-submodular maximization when given access to value oracle was first con-
sidered by Chen et al. (2020) where they obtained a (1 - 1/ee) laprooxapoinnnioonn coefficient with a query complexity of O (1)E") (for deterministic value oracles) and O(1/E²) (for stochastic value
oracles) for monotone functions over general convex sets. However, as mentioned in Appendix B of (Pedramfar et al. 2023), they require access to the value oracle outside the feasible set. [Pedramfar al. (2023) used a comprehensive approach to obtained Ö(1/s) for deterministic gradient oracle, O(1/E") for stochastic gradient oracle and deterministic value oracle and Ó(1/=²) for stochastic value oracles with an approximation coefficient of (L -1-11 1/e) for monotone functions over convex sets containing the origin, 1/c for non-monotons functions over downward closed sets, 1/2 for monotone functions over general convex sets and (1~h) for non-monotone functions over general convex sets.
Note that the problem of maximizing a non-monotone DR-submodular function over a box, i.c. [0, 1]d, can be solved using discretization of the domain and applying algorithms designed for discrete settings. For example, Bian et al. (201);; NNazadeh et al. (2020) used discretization to obtain 2 -approximations of the optimal value. We have not considered this setting in our work since such discretization techniques have not been successfully applied in more general settings where the convex set is not a box.
A.2 ONLINE DR- SUBBUUUR MAXIMIZATION
Chen et al. 20) considered the problem of online adversarial continuous Du-subood maxi- mization for monotone functions over convex set that contains the origin. They obtained (1 (1- I/e) approximation guarantees given full information deterministic feedback. More specifically, they extended the idea of meta-actions, introduced by (Streeter & Golovin (008) for the discrete set- ting, to continuous setting and introduced the first version of Meta-Frank-Wooie
for continuous DR-submodular maximization. They obtained (1 - -1e)-rreret of O(T1-9) when allowed to query each function 7 times for 0 S / < 1/2. was shown by Hassani et al.] (2017) that a direct usage of unbiased estimates of the gradients in Frank-Wolfe type algorithms can lead arbitrarily bad solutions in the context of offline submodular maximization. This led [Cenn el al. (2018) 8b) to consider a different approach when only unbiased estimates of gradients are available. In particular, they showed that online gradient ascent can obtain l-regrrtt of O(T(/2) in the semi-bandit feedback setting, where the algorithm is allowed to query the stochastic gradient oracle at the point where the action taken. Later, Chen al. (2018)) extended the Meta-Frank-Wor Wolfe algorithm work with stochastic gradient oracle using the momentum technique, described in (Mokhtari et al.) 2020) for offline setting, to control the variance of the stochastic oracle. For monotone functions over convex sets containing the origin, they obtained (1- 1/ee-reggrt of O(TL-8/3) when allowed to query each function T times for 0 < 3 < 3/2. Zhang et al. (2019) continued this line of work by combining meta- acctinac momentum and novel idea of random permutations (see Idea 3.1] to obtain (1 1/e) /regret of O(T1/5) when allowed to query the stochastic gradient oracle once for each function. Their algorithm, called Mono-Franke FetooFrann-Woorr Wolfe, requires access to the oracle at some point other than the point where the action is chosen. Using similar ideas, they also introduced Bandit-Frank-Wor which obtains (1 rrerett of O(T8/9), when deterministic value oracle is available, for monotone functions over convex sets containing the origin.
For non-monotone function maximization over downward-closed convex sets, Thang & Srivastav (202T) introduced a novel technique which uses an online non-convex optimization oracles referred to an online vee-learning oracle (as opposed online linear maximization oracles used in most other Frank-Woll based methods) to obtain reegret bound of -(T1))/3) using T oracle queries per function for all 0 < 3 < 3/4. Note that while their online vee-learning oracle is solving a non- convex optimization problem, it can obtain its guarantees in projection-free manner. Later Zhang et al. (2023) extended the results of (Zhang et al. 2019) to the setting of non-monotone functions over downward-closed convex sets. More specifically, they showed that using their update rules, Meta-Frank-WWor Wolfe obtains 1 regrett of O(T1-3/33 when allowed to query each function T times for 0 < 3 < 3/2, Mono-Frank- Wolfe obtains 1 regret of O(T4/5) with only a single access to a stochastic gradient oracle and Bandit-Frank- Wolfe obtains 0 with access to a deterministic value oracle. For monotone functions over convex sets containing the origin, Zhang et al.) (2022) developed boosting framework which allowed them to obtain (1 ree)-regret of O(T with
e
14

---

Published as a conference paper at ICLR 2024
only single access to stochastic gradient oracle. Note that their result is not in the semi-bandit feedback setting, since they require access to the gradient oracle at points other than the points where the actions are taken. Also note that their algorithm uses projected gradient ascent which involves the computationally expensive projection operation. (Liao et al.) 2023) adapted the boosting framework to obtain a projection- freee Frank- Wolfe type algorithm with (1 1/ee -rrrgeett of (TT3/4) with only a single access to stochastic gradient oracle. (Wan al. 2023) also adapted the boosting framework to obtain an algorithm for deterministic bandit feedback setting with (1 1/e)-regret of O(T5/4). However, while their algorithm does not directly use projections, they require solving convex optimization subroutine at each iteration which could be computationally expensive. (Niazadeh 2023) showed that for monotone functions over convex sets that contain the origin, their ct al.
algorithm obtains (1 - 11-1/e)-regre of (TT5/) in the deterministic bandit feedback setting. Recall that (Hassani et al., 2017) showed that direct usage of unbiased estimates of the gradients in Frank- Wolfe type algorithms can lead to arbitrarily bad solutions in the context of offline submodular maximization. However, in the algorithm proposed by (Niazadeh al., 2023), the exact gradient directly replaced with a one-point estimate of the gradient without using momentum or similar variance reduction techniques.
For non non-monotone functions over a general convex set, (Thang & Srivastav 2021 considered a vari- ant of Meta-Frank-WW Wolfe with different update rules to obtain 3v3 (1 h regreet of O log(T)) using 7 number of queries per function for any constant 3 >> O. While their algorithm used mo- mentum, (Mualem & Feldman 2023) considered the same algorithm without using momentum and used an improved analysis to obtain (lhh) -regret of 0(T when allowed to query each function T times for 0 < 3 < 1/2. While their result seems to match the first Meta-Frank- Wolfe result of (Chen et al. 201 8b), it should be noted that this result works for stochastic gradient oracles, while the result of (Chen al. 2018b) was for deterministic gradient oracles.
As previously mentioned, a notable challenge in this problem domain has been transitioning from deterministic gradient oracle to stochastic one. The existing solutions range from using the momentum technique of (Mokhtari et al., 2020), for cxample in (Chen et al. 201 Zhang et al. methods. One of our main technical novelties
2019 2022), to using projection-basse analysis which allows us to demonstrate that we can move from a deterministic gradient oracle to stochastic one while keeping the same order of regret bounds. It also allowed us to move from deterministic value oracles to stochastic value oracles, both in the full-information setting and in the (semi- (semi-)bandit setting. This is the first work that considers online adversarial DR-submodular maximization with noisy (semi-) bbnndit feedback. As a special case, if we assume the sequence of functions F. constant, then this problem reduces to online stochastic DR-submodular maximiza- tion with (semi-) feedback. This problem has been studied for monotone functions over con- vex sets containing the origin in (Chen et al. 2018a) where they obtained 4-regret of O(T2/3). For monotone functions over general convex sets -regrrtt of (TT1/2) using projected gradient ascent. Finally, (Pedramfar al. 2023 obtained results in all cases as described in Table 2 Our unified online algortthm, when applied to the non- adversarial setting, matches the state of the art among all projection-free free algorithms. If we include the projection based algorithms in our comparison, then we match the state of the art in 7 out of 8 cases.
refined
setting, (Hassani et al. 2017) obtained
15

---

Published as a conference paper at ICLR 2024
B COMPARISON FOR ONLINE STOCHASTIC DR-SUBMODULAR MAXIMIZATION
Table 2: Online stochastic DR-submodular optimization.
F
Set
Feedback
Reference
Coef. a
a- a-Regret
Chen et al.
2018a f.
1/e
0
FF
PPdramfarr et al. 2023
1 1/e
O(T3/4)
0 E IC
This paper
1 - 1/e
O(T3/4)
Monotone
(Pedramfar et al. 2023
1 1/e
O(T5/6
This paper
1 1/ee
O(T5/6)
(Hassani et al.
2017
1/2
O(T
VF
Pedramfar et al.
2023
1/2
Ö(T3/4)
general
This paper
1/2
Ó(T3/4)
(Pedramfar et al.
2023)
1/2
O(T6/0)
F
This paper
1/2
Ó(T5/6)
(Pedramfar et al.
2023)
1/e
O(T9/1)
F
This paper
1/e
O(T3/4)
Non-mono.
d.c.
(Pedramfar et al.
2023)
1/e
O(T5/o)
F
This paper
1/e
O
(Pedramfar et al.
2023
1-h
O(T3/4)
VF
This paper
1-h
O(T3/4)
general
(Pedramfar al. This paper
2023
O
F
O(T5/6)
This table compares the different results for the expected a-regret for online stochastic DR-submodular maxi- mization for the under bandit and semi-bandit fcedback. In this setting, our algorithm matches the state of the art in 7 of the cases. When only compared with other projection-free frre algorithmss of the art in all cases. i the analysis in (Chen et al. (2018a) has an error (Appendix B in (Pedramfar et al. 2023)) )
result matches the state
(Hassani al. 2017 uses gradient ascent, requiring potentially computationally expensive projections.
C COMMENTS ON PREVIOUS RESULTS IN LITERATURE
Constraint set: Following (Pedramfar et al. 2023), one of assumptions is that we are only allowed to query the oracles within the constraint set. This assumption allows for a more detailed exploration of the problem space and clarifies the reason why some algorithms for monotone DR- submodular maximization obtain 2 approximation coefficients while others obtain (1 - 1/e). In Appendix A while discussing some of the related works, have cited results that encompass broader scope than what was initially claimed in the original paper, while some have seemingly narrower scope. this section, we delve into how the proof's or algorithms from those works may be adapted to the more general setting we have considered.
As mentioned in Appendix A in (Pedramfar et al. 2023), the result of (Bian monotone functions are presented for downward-close sets, but the same proof can be used in the setting where the convex set only contains the origin and is necessarily downward closed. The regret bounds of Bandit-Frank- Wolfe in (Zhang et al.) 2019) are presented for downward-closed convex sets that are d-dimensional. By replacing their construction of shrunk constraint set with the construction described in (Pedramfar et al. 2023), one can show that their result applies to all convex sets that contain the origin. The Bandit-Frann Frantt-FFnnkoooa non-monotone functions over d-dimensional downward closed sets. Similarly, by improving their construction of shrunk constraint set, one can show that their results apply to all downward-closed sets. The result of (Niazadeh et al. 2023) for monotone functions is also presented for d-dimensional downward closed sets which can be similarly modified to apply to all convex sets that contain the origin. The results of (Wan al. 2023) for d-dimensional convex sets that contain the origin
2017b) for
of Zhang et al. (022)) presented for
16

---

Published as a conference paper at ICLR 2024
and not lower dimensional convex sets. We believe similar approach may be applied extend their result to all convex sets containing the origin.
For convex set K S [0, 1 let XC* denote the convex hull of U (0). If F is monotone DR- submodular function over [0, 1]". then the maximum of F over the feasible set KC is the same as the maximum of F over the feasible set K." Therefore, these problems are identical if we have no further assumptions. However, if we assume that we may only query F within the feasible set, then these problems become different. In fact, as discussed in (Pedramfar et al. 2023), the best known approximation coefficient for the first problem is while the optimal approximation coefficient for the second problem (1 1/e). The results of (Mokhtari al.) 2020) for monotone functions are presented for general convex sets, but if we assume that we can only query the oracle within the feasible set, then their algorithm and proofs apply when the convex set contains the origin. The same is true for the Meta-Frank Wolfe algorithm of (Chen et al. (018b) and (Chen et al., 201 and the Mee-Shot-Frank Frank-Wolfe algorithm of (Chen et al.] 2018a). Note that the Tine-Shot-Frann SeootFFrak--We Wolfe is claimed to obtain (1 - 1/e) aapproximation, but as mentioned in Appendix B of (Pedramfar et al. 2023 the proof only results in an approximation coefficient of 1/e.
Similarly, Zhang et al. (2022) considered the general convex set. However, their boosting technique involves line integral over the line segment connecting the origin to the points in the feasible set and the algorithm queries the oracle on that line segment. Hence classify their result as algorithm
that maximizes monotone DRsuubmodular functions over convex sets containing the origin.
Bandit feedback: As we have mentioned in Appendix A this is the first work that considers the online adversarial DR-submodular maximization with noisy bandit feedback. We have mentioned four papers in Table [ that consider a similar problem. but with deterministic feedback, namely (Zhang et al., 2019; 2023 Niazadeh et al.) 2023 Wan al. 2023). We believe similar analysis to ours may be used to extend their results to the noisy feedback setting, likely without much change in their algorithms.
Boundedness of stochastic gradient/value oracle: Another one of our assumptions is that the stochastic gradient/value oracles are bounded. At first glance, this seems more restrictive than some of the previous works, such as Chen et al. (2018)). Thang & Srivastav (202I) and Zhang et al. (2023) which only claim to require that the stochastic gradient oracle should have bounded variance. However, a more careful review of their assumptions and proofs reveals that they require extra assumptions for their proofs work. In particular, if they assume the boundedness of the stochastic gradient oracle, then their results hold up to a constant multiplicative factor.
In Chen et al. (2018a), Assumption only requires that the stochastic gradient oracle should have bounded variance. However, in the last paragraph of their Section 4.1, they claim that "From Theo- rem 1, we observe that by setting K T and choosing projection-free online linear optimization oracle with R(T') = O(T)), such as Follow the Perturbed Leader (Cohen & Hazan 2015), both re- grets are bounded above by O O(VT)." The cited paper does not contain such an algorithm that can be applied to this setting. Moreover, to the best of our knowledge, there is no online linear optimization algorithm that can obtain a regret bound of (T) = O(VT) without any extra assumptions. On the other hand, as stated in Remark 4 there are algorithms that obtain R(T) O(DBVT) where D is the diameter of the convex set and B is an upper bound on the norm of the vectors that are passed to the algorithm. Therefore, if we add the assumption that the stochastic gradient oracle is bounded by some constant B, then the regret bound O(r2-8/3) holds.
Similarly, for Seta-Frann-Waid
and Mono-FFank--Ve sumption 2 only requires that the stochastic gradient oracle should have bounded variance and As- sumption 1-(ii) assumes access to an online linear maximization oracle with the regret bound of O(VT). As in Chen et al. 2018a)). if we add the assumption that the stochastic gradient oracle is bounded by B, then their regret bounds, i.e. Theorems and 2 in their paper, hold up to multi- plicative factor of DB.
algorithms of Zhang et al. (2023), As-
In Thang& & Srivastav (2021 1) , in the case of general convex sets, the same issue appears in Theorem 3 and could be resolved similarly by adding the assumption of the boundedness of the stochastic gradient oracle.
17

---

Published as a conference paper at ICLR 2024
Finally, in Thang & Srivastav (2021). in the of downward-closed convex sets, Theorem 1 only assumes we have access to a stochastic gradient oracle with bounded variance. However, in the por- tion of proof of Theorem 1 before Claim I, we
that d' corresponds to a' in Algorithm and Lemma 4. (Note within the proof of Claim 1, V (xx) corresponds to ag in Lemma 3) Hence, the assumption ||a']l S G stated in Lemma 4 does not follow from the stated assumptions in Theorem 1, e.g. the assumption that the norm of the gradients V || are bounded by G. Instead, it requires d' be bounded which is satisfied the stochastic gradient oracle bounded.
D USEFUL LEMMAS
Here state some lemmas from the literature that we will need in our analysis of DR-submodular functions.
Lemma 1 (Lemma (Pedramfar et al., 2023). If D - is DR-submodular, bounded by My. Mi-Lipschitz continuous, and M2-smooth, then so is its smoothed version F, and for any E D such that B& B)ft(D)()) - DD we have
[1((x) - F(x)l 8M1
Moreover, if is monotone, then so Fo.
Lemma 2 (Lemma 13 in (Pedramfar al. 2023 Let D C Rdd and A == afl(D). Also let Ao be the translation of A that contains O. Assume F D - R is a Lipschitz continuous function and let F be its d-smoothed version. For any z E D such that B3 (z) C D, we have
Eu indg
8 Flz Suju = Fz))
where d' dim((o).
Lemma (Lemma 14 in (Pedramfar al. 2023 ). Let S [0, 11sh be a comvex set containing the (()
origin. Then for any choice of c and with B,
(c) S K. we have
8
arg min ||2||00
and
min zek
| S
Lemma 4 (Lemma 15 in (Pedramfar et al. and 8' : &D We have
2023
Let K. be arbitrary convex D diam(A)
(f)((C) 8
(fC)
C
K
C 18 (fC) (R)).
Lemma (Lemma 2.2 of Mualem & Feldman, 2023 ). For any two vectors x,y [0, 1] and any
continuously differentiable non-negative DR-submodular function we have
F) (1 -1-110 ((x)))))))(())))
Lemma 6 (Lemma 6 of ZZang et al. ously differentiable non-negative DR- RR-submodular function F have
2023)). For any two vectors x, E (0, 1]d and any continu-
Fly -
-1-y) y) xx) 2 (1
Lemma (Lemma 1 of (Dür al. 2019)). For every two vectors x, y E [0, 1]d and any continu- ously differentiable non-negative DR Dussuboaularr function F we have
(VF(x), x) F(x v)) + 2x()).
E OFFLINE
As we mentioned Section 3.1. when given value oracle, we solve the problem of Subsuoodallar maximization over the convex set K. However, 0 e Ic, then it can be immediately seen from the definition that & Ê. Here we want to present statements in the offline setting that could also be applicd to & as well as IC. For this reason, we adapt the categories (A)-(D) described in Section to accommodate general feasible sets.
18

---

Published as a conference paper at ICLR 2024
(A') The functions F is monotone Dussuboodular and K. has minimum point, i.e. there is unique point u E ΣC such that for all z E K. we have u S z.
(B') The function F is non-monotone DR-submodular and IC is downward-closed convex set.
(C") The function is monotone DR-submodular and a general convex set.
(D') The function is non-monotone Dussubndula and
general convex set.
Note that since we are considering the offline case here, there is only a single function and not sequence of functions. Here use the value for and the functions updale and oracle-adv as before.
Lemma 8. Let K. S [0, 11 be a closed convex set and let F be non-negative M1 Mi-Lipschitz M2- smooth continuous DR- submodular function over K. that is bounded by My- Moreover, assume that the pair (F,K) belong one of the categories (A')-(D') described above. Let (v(k)) be sequence of points in K,, E argmingex || and let k generated using the following rule.
K+1 be sequence of points
x1)) = u.
Vk E [K], x (k+1) = update(x( (A), (1), (x))..
Then, the sequence (x (x+)
K+1 is contained in K. and for any x E K. we have
K
F(x(K+1)) 2 aF((x) - r+
(k) (oorcce-adv((eal (VF(x()), x(1)) v(0) -x),
where
M
(A'):
M,D²
2K
+ (Mo + Mi)lu
(B');
K-k K
(A)) or (B";
T=
2K
(
20c) k k EC
(C");
M,,+M, 1og(K)
(C');
&K
2E k -
(D'),
Mo+2M,D
(D')-
4K
for all l E [K].
Remark 5. Note that we always have 0 S (b(
S and
log(K)
(C"); Otherwise.
(k)
Proof. We consider each case separately.
Case (A'): First we show that the sequence (x( K+1 k=1
is contained in K., For any k E [K], we have
( = -u K
Σ (v()) u)
(K k) Σ (())
K
which is a convex combination of K l copies of u and the i points v(0), for s E [b.]. Therefore
we have (I+1)) E K.
Let $s. We want prove that
F(x(K+11) z (1-2) F(x")
M2D²
6
2K
+ ΣΣ (1 - k <(VE(x(()), ((k) - xx).
Using the fact that F is My-smooth, we have
F(x( ((x( 2 (VF(x())), (((+1) x((x xx()))
M2
(k+1)
x 1x
2
e²M2
= =e(VF((((t), v(A)) -1)
u1
2
222212
2 +(VF(((()) (())
19

---

Published as a conference paper at ICLR 2024
Since is the minimum point of K, we have x+ 2 and x* 2 u. Therefore we have x" - 0
and x" - = 2 x" x(*), Hence x" x"-u u 2 (x* x (k) vo Using monotonicity of F and its concavity
along non-negative directions, we have
(VF (8)) ) x - u) 2 (VF(x(()), - (x)) VO)
-(FF(x(()) Vx((1) - (x))
2 F(x V vx( - -x)
2 F(x') - =(x((1)).
Therefore
F(x((+1)) 2 ) + +=(VF(((()) v(()) c²M2DD2
2
+ +V(VF(((()) v(() -x)- &2M2DD
2 (1- (F)x))((x()) + +
2
Using this inequality recursively for 1 k S K, we see that
K
=x((xx - > (1 5) K K- xx222
K
2 (1 F(x(
F(x(1)) + Σ (1 - 2) K-
2
k=1
k=1
K
k kk=* (VF((x( v(t) - -x"
8)
k=1
K
K
e2M2D²
8) K =x((') Σ
2
K
Σ k=1
(1 - E) k k < (VF((())) (()) x*)
11 - (1 - (1=))k) F(x*) - D22
2
K
Σ (1 (K<-*((V((e v(k) -x"
2 1
F(x*)= - M₂D2
2K
K
+
(1 - 8) K ->> ( v()) - xx),
k=1
where we used (1 - 2)* k
(1 ) k _ in the last inequality.
Case (B'): First we use induction to show that x(6) e XC for all 1 < s < K +1. The claim is true
for = since (x)) = E K. Assume that the claim is true for 1 5 s < k. We have
1 x(++1) = (R) + K
(K)
3 (1)x(*) (*)
(())
= =u+ +
K
s=1
(x())
= K
1
(K (K- k)u + (s)
K
20

---

Published as a conference paper at ICLR 2024
where ((() == 11 + (v(*) - m e (1 - x()). According the induction hypothesis, for 1 S k,
have x(*) E KC which implies that 0 S x(*) 1. Hence we have
S (yl*) о (1 x( (+)) u.
Therefore u S ((5) S <v()), Since K is downward this implies that v(x) E K. In other word, x ((++1) is a convex combination of K l copies of u and the k points v()), for E [k]. Therefore we have (k++1) E K.
Let = k.. We want to prove that
F(x(K+1)) 2 - (1 u Fx MzD²
2K
(1 8) K-k ((F (1 - x()),, v(0) -x))
We start by showing that
[x 1oc 2 (1 -1-6) ---))=11 |
(6)
for all 1 < k K 1. We use induction on n to show that for each coordinate 1 I < d, we have
1 - [x (1 - c1 [u],)- The claim is obvious for k = 1. Assuming that the inequality
is true for k, using the fact that V S 1, we have
1 1 [x(+ 1 [x(*)] =l(VE= u) 3 (1 (*))
- [x [. <((vx] [u]:)(1 - (x(*)},)
2 1 [x (x) -a(1 - -(x(()),,)
(1 <) [x( 2 (1 (1- -E)=((11 - [u),).
which completes the proof by induction.
F(x(k+1))- - ((x(())= 2 (VF(x!+)), x((+1) - x(()) M₂ |xx(+1] - 1 122
2
&²M2 [[(((k) u) о (1 112
=<(VF(((()), (v(R) -
0 (1 - xx()))
2
2²
2 = (v(()) u) (1 (k))))
Since F is DR-submodular, it is concave along non-negative directions. Therefore, using Lemma and Equation equation 6. we have
(VF(( (1 ())))) 2 F(x(1) x" 2 (1 (1-x(1)) (x(x
2 (1 - 12xxx)) - -((())
2 (1 - (1-
- F(x(
Therefore
e²M2D²
((x( F(x + (v(() u) о (1 x (1))
2 (1- =) + 5(1 - ()- (1 || F(x*)
2 M2D2
+ + (v(() - -
x²) o - -x x())))
2
21

---

Published as a conference paper at ICLR 2024
Using this inequality recursively for 1 S k < K, we see that
K
F(x(K+11) 2 (1 (1- (1- )) +
k=1
Σ (1 5)K xk< MM
k=1
K
+ Σ (1 8) - 8 (VF(((())))) (vit) - - -
0 (1 - xx(x))
k=1
K
K
M2
2
(1 K- K--E(1 E((1
-
1(x -
Σ
2
km 1
k=
5) k k (VF(( (v u - - 10 (x))(
+
k=1
1 K)
K-1
(1 (1xx)) M2D
2K
K
+
>
5 (VF(x - -x
k=1
2 (1 1x (100) F(x') M₂D
2K
+ Σ
(1 8) k k-t sVFF
(8) 3 (1-x x00x))))())))x
11 ==x"))
1=1
1 (1 |x00) (100 )(x') M2D2
2K
K
(1 - 5) K-* <(VF(x(())
O (1 - (+)) u)
k=1
Σ (1 - 5) K k sVFF 0 (1-1 xx))) v(() -x)),
+
k=1
where we used (1- ) _/2 and the fact that (a o b, c) = (a.cb)) = =Ein abbic for all
points a, b. E Rd in the last inequality. Finally, we note that
K
K
Σ (U-=)K*E((FFU) k=1
@ (1 x x(()), u) S
(1-
x)k 8 /F(x(()) o (1 -x-x(())||)) x(*)|||||| |al||
1=1
K
(1 $) k k EMillu
k=1
K
MM |||||| = M |ull S M |
k=1
and
F(x*) |(x*)|((()) 1lcc S Mollu|i>o
Therefore
M₂D² - -(M1 + Mo)l[ulloo
F(x*) F(x(K+1)) 2 -
2K
K
(1 - 5) K k> xVVF(( (k)) 2 (1 - x(1)), v(()) -x)).
+
k=1
22

---

Published as a conference paper at ICLR 2024
Case (C"): Since the update rule is convex, the the sequence (x(*) K+1 k=1
is contained in K. Let
E = EC. We want to show that
1 F(x") 8Mo + M2 log K)²
F(x(K+u)
2
8K
K
(1 26) R - 5 > (VF(x(()), v(x)
+
k=1
Using the fact that F is M2-smooth, we have
F(x()+1)) - F(x (0) 2 (VF(x(()), x, (k+2) -
L
11x (k+2) - x2
2
E²L L
= =VV((x(()) v.(k) -()))(()) x²)
||v(()
- xx
2
=² 222
2 <V((((((*) v()) ()
2
Using Lemma 7 and the fact that F is monotone, we see that
()) x* - x (1)) 2 F(x' )x) + F(x* ^ (8)) - 2F (x)
2 F(x') + F(x" ) -2F(x())
-
2 F(x') (
Therefore
F(x((tl)) 2 (0) + (V(( v(() - xx1) 2²
2
21- (x) + +x('') + (VF((()))) v() -x)) M2D
Using this inequality recursively for S k S K, we see that
K
K
(1 28) - === M2
F(x((+1)) 2 - (1-22) K F(x(1)
+ Σ
(1 - 22) K (F((x))
2
1=1
+ Σ
(1 22) k k ( (x))) v(()) -x")
1=1
K
M222
>
(1 - 22) K- 1-1-k1eFt [F((x') Σ
2
k=1
K
+ Σ (1 22)
"o-K"K(VVFF (k) - xx")
k=1
1
1 (1 (k) F(x') - Kc2
2
>
(1 - 22 K-k KKK (x((F(((()) v(()) - xx)
+
1=1
> Fx*)) 8M0 + D2 log(K) (K)
2
8K
(1 22) (VF(( (K)), v()) x"),
where the last inequality follows from the fact that F is bounded by Mo and
(1 (1- (1
log( K)
< < logg(((K)
K
K
23

---

Published as a conference paper at ICLR 2024
Case (D'): Since the update rule is convex, the the sequence (x(*)) K+1 )
is contained in K. Let
E = ED. We want to show that
F(x(K+11)
1 (1
Mo + 2M
4
4K
K
(1 22) K-k (VE(((()( (1) xx)..
+
k=1
First we prove that
(x) 0c 2 (1 (1-6)*-1(1 ||
(7)
for all 1 1< k < K +1. 1. We use induction on 1 to show that for each coordinate 1 < i S d, we have
1 - [x(*)] 2 (1 - ()) 1)h-1(11 (11 [u]+). The claim is obvious for k 1. Assuming that the inequality
is true for k, we have
1 1- [x(x+ =1 (1 (1- |x
(1=))())))),, - e(v(0)],
2 1 - (1 - =) [xxx -8
= (1 - e) (x()))))) 2 (1 (1) - [w)e),
which completes the proof by induction.
Using the fact that F is L-smooth, we have
L
((x( ()x 2 x((+))
[|x(111)- - xx0
2
e² L ||(((t - -x( xx
= =VF(((( v(()) - -x(1))
(8)
2
e² ²MzD²
2 2<(VF(( ((k) x11))
2
Using non-negativity of F, Lemmas 7 and 5 and Equation 7 we see that
[x) x - (x)
2 F(x V x (k)) ) + F(x" A x (bb)) - (x(
F(x vx ( -
(xx)
2 (1 - |10)) F(x") - (x)))
2 (1 2) (1 n F (xx
Therefore
5² M222
(1x 2 -(x(())++((V(((( ((VF(x((M)
v(() - xx(1))
+
2
2 (1 - 2x) + s(1 -e)- ||ا|| o0 Fx(")
e² D²
(x)) v(a) -x")
2
Using this inequality recursively for 1 S k < K, we see that
K
F(x((+11) 2 - (2))-2)*-0 F() +
Σ
(1 26)
c(1 -
k=
K (1 K-
E² 22
K
(1 - 22) x (VF(((())) v(k) -x)
2
k=1
k=1
K
>
(1 22) K- [6(1 - =))
(1- (f
KEa M₂D2
K
Σ
(1 - 2s) K k (V)((x())) v(()) v(0)=x)) -x").
2
1=1
24

---

Published as a conference paper at ICLR 2024
We have (1+ 2
2 2N for 0 and N 1. Therefore
2τ) k k-k k- (1 - -e)x-1=
(1 26) 2=)
1-1 (11 + o)* -1)
k=
(1 (1+ log(2)
2 (2g(
-1
K
log 2))
2log(2)
log
- -11
2K
1
12)
1
4
K
1
4K"
Hence
F(x( N
Σ
28) K K-te(1 -e)6-1 (1 (1=
log( (2) J2222 DD2
Σ 25)KK1 (1_2s)<=*<(VF(((>>
(VVF(x(()) v
xx")
2K
2
(1 - |llll)))F(('))
4K
log(2) (on(2222M))) 22
K
Σ (1 25) K-k (<< (1),, v(t) - xx))
2K
k=1
1
2 (1 |l[ll=))F((())
4
K
Mo + -2M
Σ
(1 - 22) K *=F(== (+)) -x))
4K
k=1
F PROOF OF THEOREM 1
Proof. The key idea of Algorithm is to use the average of several functions in a certain group (e.g.. block) represent the functions. Note the regret is calculated by the sum of all the reward functions, and the sum of average functions is exactly the sum of all the functions divided by the block size, so we can use the average function to analyze the regret. Let
Fx(x) = Σ Pr,,()) (x),
Fx(x) = T, Σ (x),
denote the average of functions in block g and the average of smoothed version of the functions in block q respectively.
maxyek Let y = arg max 1 Fy( and ÿ = arg max yek ΣT, Ft Note that both y" and ý
maximize the same expression, but over different domains. Using the definition of the a-regret and
For 2 0, we have log(1 + x) >
and x 2 log(1 x). Therefore N Vlog(1 + )) 2
N(S 2 = 2x 2 c log(1
2N )
2
25

---

Published as a conference paper at ICLR 2024
Lemma 1
we have
R₂= (
T
T
Σ
- -F(yi)) + Σ a (F((9*) - F((F)) + Σ a - -(()"))
=
1=1
1=1
T
Σ
(afi())-- - -i((y))
+
t=1
Σ (Fi(y") F(())) + Σ (af((*"- - -Pi(y))).
s 2M,78 +
According to Lemma 4 there exists y' E E such that Ily 1y'l-''1
5'118' 8= 6D Therefore
T -F(y"))((33') Σ -(ly"))F((y')) + (Fily') - F(()))
2 Σ -
$ M,T8'.
Hence we have
T
R₂ 2M1T8 + Σ
a (Fi(y) (,(8))) + Σ (afi(*) - -f(()))
T
s 2 D
M + Σ
(af((""-f((t)))))
- P.lyr))
2+ m)
a L
MIT8+L
Σ
RT. - -T. Σ Pews (ytui)
T.
1=1
2+ r
1)
M,T6+L
MM
Σ
(3*) (3") Σ (x))
(xx)
L
D = 2 -(2+ M T
Σ
(FF) - F (x(x)))
(10)
Recall that (Lg.t....,, is random permutation of {(q - ((g-1)-+ + random function and we have E[Fr,, (x)) (x). Therefore, we see that B[F (x)] = (x( and EIVF, n (x)] (x)... Define Fg to be the o-algebra generated by all of the random variables in blocks 1, . and > Then, conditioned on F,P- the values of v((h) and x
1,... ,9L,, +,, thus Fr,. (x) is a
deterministic. If we have access to stochastic gradient oracles, using the definitions of d and stochastic gradient oracles, we have
d VF (xx(k) F Fty. (x(+)) 22 2(()),
26

---

Published as a conference paper at ICLR 2024
where 2 is random variable distributed according r1 "1
(;xx (8)). Hence we have
(2)
F
E
V Ft
[ (k) (k))
2 |
E
Fi (x 2 (k)) 12 15
(k)
E
VEr.. (xx/ 11,
(x())
(x(()
where the third equality follows from the unbiasedness of the gradient oracle and the last equality follows from the fact that when are given gradient oracle, we have 5 0 and F; Ft- Similarly, if we have access to stochastic value oracles, using the definition of dx and stochastic value oracles, we have
d' 5 Pige (x + su! u 5 Bens (x!+)
(b) (k) (k) + ou 22g un (k)
(k)
(k) where zi
is random variable distributed according to po ((;x)) + ou, )u Hence we have
kk)
(k) + +ou!! Ft,, (x)
(k), x 15
4
d'
8 Fig,, (xx{a) + dulh 2 1k.. Fg
d'
E
Pins (x!²) + tōu ((a m (u(")
Maa
1Fg
5
d'
IR
Pru. (xxta) + oo m 1 169d
|Fg
(xx( |5
(x(" (x),
where the fourth equality follows from the unbiasedness of the value oracle, the fifth equality follows from Lemma 2
Therefore, given any type of oracle, we always have Eldd (+) [F
(x())) which implies that
Fgl = Fracle-ady(VF, (x) (1)).
g
Hence
Citoralle-adv//P.ttee xxx))) (k) x E
[E g
(k)
[Fg, v(th) xx))
E
[[(s (k)
v xx) FFll
(11)
E(
(k) v (k) xX]]
Each Fr : KC + RR is a non-negative Mi-Lipschitz My-smooth continuous DR DR-submodular function
that is bounded by My. Therefore, according Lemma Lemma 8 we have
so is Fg K + R. Therefore, using
K
F, [2 (K+1)) 2 (F,("")) - (V Fx (k)), v,(()) -5)
k=1
27

---

Published as a conference paper at ICLR 2024
Using Equation we have
E (x/ []]
2 aF,(5))) r
Ekg (8) v(() -
A=1
Plugging this into 10 and using Remark
we see that
Q
B B[Ra]
S + P) M MITO + L
Σ
B
-
(x))))
9=1
D
Q
K
s + ) Mi75 + I.
Σ
(k) (( (A:) v(() - 87)]
9-1
1=1
2 + () + + L
Σ
K
(K)
E [g (k) . - |(
(k)
k=1
D )
K
$ 2 r
M,75 + IT +
19)
CDBVQ
Using the definition of l and Lemma
3 for case (B) we have
D
D
T
2 +
M,T6 +TT
2
MiT8 + (Mo + 2M²
+ (Mo + +M)llulle
4K
D
T
+ (Mo M,)T 8
2
M1T8 + (Mo + 22)
4K
T5 + (Mo + +M2
$ (Mo + (3 + D)Mi
4K'
for cases (A) and (D), we have
D
M M, -TT 2 P) M,T6 + (Mo + 2M2D2) T
2 +
4K
Tø + (Mo + 2M2222
T
< (Mo + (3 + D)Mi)
4K"
and for case (C), we have
(2+ 2 M (Mo (3 D)Mi T8 (8Mo + M2 log(k)?) T
D
8K
On the other hand, following Remark 5 we have
K
(log(K) (C"); Otherwise.
L
Σ (8) CCDB/Q
LCDBB/C
Putting these bounds together, we see that
[[Ra] 5 (2+ - 4) M,T8 + IT Σ
K
(6) n
CCDBVQ
k=
TT +
(8Mg + M2 log (K) I + LLCBB/Qlo(()) (C"); (Mo 22M2 2 +LCDBVQ
< (Mo + (3 + D)M:
Otherwise.
= R".
G PROOF OF THEOREM 2
Proof. Let arg maxyek Σt= Fy) and 3 arg max yek ΣT Fy( as in the proof of Theorem With the same argument as the proof of Equation 9
we see that
R. < (2+ D P) M,T6+ + Σ (aFi()") f.(y.))
r
28

---

Published as a conference paper at ICLR 2024
On the other hand, using Lemma
that F is bounded by Mo. Therefore we have
Q
Σ (af((*)) - F((y,)) =
(x - -Fig.t (v1g,x)) +
(aFin. (F*)) -Fig. (xx)) (x4)
k=1
1=1
K
Q
1
2Mo +
a (aFt,.(("))) -x)n((x)))
k=1
9=1
Q
L
= 2MOK +
Σ
(aFi, - FFaa (x())
911
2M + I
Σ
(af(()")) Fg(x)))
q=1
where Fg and F2 are defined in the proof of Theorem
Hence
D R. S 2MoQK + (2+ 7) MiT8 Σ
-aF((5))-(((())))) (x(x))
q=1
The update rule for x, in Algorithm 2 is the same as Algorithm
Therefore, the same arguments - -Fx(,)))));xx,,)))) can be directly used here
in the proof of Theorem to bound E -S
without any modifications. Similarly, since the update rules of x the proof of Equation [1 applies verbatim. Hence we see that
(k) are the same in both algorithms,
Q L
E[Ral S 2MQQK+ (2+
D
M,T8
Σ
E
(F
-Fa())))()x())
9=1
< 2MQK +
(2+-)
D
Mi78 75 + IT + L
K
CDBVQ
k=1
< 2MQK R
H EXPERIMENTS EXTENDED DESCRIPTION
H.1 EXPERIMENT SETUP
We next test our algorithms for online continuous DR-submodular maximization in the setting of non-monotone objectives, a wwwpward-wlowodoo gradient feedback. Specifically, we use online non-convex/non-come
feasible region, and full mullrinfonnniinn and semi-bandit
quadratic maximization. Following (Bian et al., 2017a: Chen et al. 2018b Zhang et al.] 2023), for each round / we randomly generate a quadratic function Fx(x) = x Hx + h x + c. Here, the coefficient matrix H is a symmetric matrix whose entries Hij are drawn from uniform distribution in [-10 -10, 0J. Note that this matrix is the Hessian of Ft, so having negative entries ensures F, is DR-submodular. To make Ft non-monotone, set h -0.1 x H where E R Similar (Zhang al. 2023). we set u= 1. In addition, to ensure non-negativity the constant term is set to c -0.5 * Li,j Ha.-
To form a www.wwrd-wloooeooooooooooooooodd using random samples from the uniform distribution over [0, 1]. setting K. {x E |= < 1, <
feasible region, we generate a coefficient matrix A for linear constraints
x < 1}. Like Zhang et al. (2023). we considered three pairs (n, m) of dimensions n and number of constraints m, {225, 15), 40, 20). (50, 50)). For gradient query V (x)),, generate random noise vector n, AO, 1) and return the noisy gradient F, = V (x)) +
| with a noise
ne
scale = 0.1. For the online linear maximization oracles, for simplicity we use the same gradient ascent based oracles the experiments in (Zhang al. 2023)
We vary horizons between T = 20 and T = 500. For each problem instance (T objective functions and specified feasible region), first obtain (1/e)- -pprroxmieee solutions (x}) for the running
29

---

Published as a conference paper at ICLR 2024
-regret
Algorithm
n=225, m=
n= m=
n=50, m=50
T1/2
Meta(B = 3/2)
225.43 = 7.62
598.11 45.39
872.00 56.26
GMFW(3 = 1/2)
2.28 + 0.24
5.97 + 0.84
9.41 + 2.88
Meta(3 =
22.27 = 1.67
59.83 _ 6.19
89.57 _ 9.45
T2/3
GMFW(3 0)
0.25 + 0.03
0.63 + 0.24
0.82 + 0.14
Meta( = 3/4)
7.49 + 0.65
17.88 _ 1.94
26.11 - 3.27
T3/4
ODC
21.92 + 2.19
37.78
4.71
55.59
6.43
SBFW (semi)
0.07 + 0.01
0.17 + 0.03
0.30 + 0.18
74/5
Mono
0.23 + 0.03
0.49 + 0.04
0.92 + 0.29
Table 3: Mean values and standard deviations of run times in seconds over ten runs for a horizon T 100. For each regret bound, our full information GMFW and semi-bandit SBFW have the lowest run-times. The run-time differences are primarily due to the number of online linear maxi- mization oracle updates each round (which increase with 3).
sum Ex- (x) using an offline algorithm (Bian et al. 2017a). Note that in these experiments,
the empirical regret is not based on 1/e times the value of the optimal solution, but instead against the value achieved by a near-optimal solution (obtained from a 1/e-approximation algorithm).
more challenging baseline. Following that, we run three online algorithms from prior works: ODC
from (Thang & Srivastav
2021). Mono (full information single query) from (Zhang et al.) 2023
and (5) from (Zhang et al. 2023) for B = (3/4, 1,3/2): here and in the following we only explicitly mention the query parameter / so that there are T queries per round and other algorithm parameters are left implicit. We ran our Algorithm [ (GMFW(3) for short) with query parameter = {0, 1/2} and our semi-bandit Algorithm 2 (SBFW for short). (Fig. depicts regret bound and query complexity trade offs for full-ifformation methods.) For each algorithm and experiment setup, we compute the rumning average cumulative regret F
F((x)))t)
Figure shows these regrets plotted across time and averaged over 10 independent runs. Mcan values and standard deviations shown. Curves corresponding our method are depicted with solid lines. Curves are color-coded to match regret bound horizon dependence. For example, our GMFW = 1/2) and Meta( = 3/2) both have Ö(vT) dependence and are both colored black. We note, however, that the number of queries used and the per-round computational complexity can vary significantly between methods with similar regret bounds. Our methods are generally faster and use significantly fewer queries. Average run-times for horizon of T 100 are displayed in Table 3 Major differences in run- cun-times are in large part due to the number of online linear maximization oracles used, which in turn related to the number of per-round queries.
For the experiments we ran to generate Fig. 2, we used compute cluster. The nodes had AMD EPYC 7543P processors. Individual jobs used 8 cores and GB of memory. For the rumning times reported in Table 3 we conducted the experiments on a single desktop machine with 12-core AMD Ryzen Threadripper 1920X processor and 64GB of memory. We used Python (v3.8.10) and CVXOPT (v1.3.0), free software package for convex optimization.
H.2 RESULTS AND DISCUSSION
The relative performances of our methods (solid lines) and those from prior works (dashed and dotted lines) do not vary dramatically across the different numbers of dimensions n and numbers of constraints
tested. In each experiment, our GMFW(3 1/2) (black solid line) performs the best. It has the same empirical regret as Meta(ß) baselines for small horizons, but for larger horizons and especially for larger dimensions n,, our GMFF (33 1/2) performs better than even Meta(3 = 3/2) despite using significantl, fewer gradient queries and significantly less computation than than Meta( 3 3/2) does. As shown in Table 3] for horizon of T 100 with dimension n = 50 and m = 50 constraints, on average our CMFW(3 = 1/2) ran in less than 10 seconds while Meta( 3/2) took over 14 minutes.
Our GMFW(3 = 0) (red solid line) is a full-information method using a single gradient query per round. It has a regret bound of ( Compared to the baseline Mono (orange dashed line), which is also full-information method using a single gradient query per round, our GMFW(3 0)
30

---

Published as a conference paper at ICLR 2024
performed significantly better across different dimensions and horizons, with as little seventh of the regret of Mono(3 = 0) in some experiments.
Comparing our GMFW(B 0) with Meta(B 1) (solid red and dashed red respectively). both of which have ((T2/3) regret bounds, we see Meta(3 1) has significantly lower cumulative regret, though the gap between them shrinks in experiments for higher dimensions. As shown in Table 3 however, for horizon of T 100 with dimension GMFW(3- = 0) took less than a second while Meta( = 1) took about one and half minutes.
50 and 50 constraints, average
Lastly, remark that semi-bandit SMFW (solid blue line), which also uses only single gradient query evaluated at the action y: played, has regret bound of Õ(T3/4) and empirically has among the highest empirical regrets. Our the baseline Mono (full information, single gradient query; dashed orange line). Our semi-bandit SMFW's empirical regret is also similar to the baseline ODC's (dotted blue line) regret for low horizons and significantly better for large horizons. ODC has the same regret bound, uses full- information feedback, uses more gradient queries, and has much higher computational complexity. As shown in Table 3 for horizon of T 100 and dimension
SMFW's empirical regret is similar to
50, for instance, our semi-bandit SMFW takes on average about 0.3 seconds while ODC takes almost minute.
31


Reviews:
[{"review_id": "SWOHLvhCa2", "reviewer": "Reviewer_ZRDt", "summary": "The paper proposes an expedient and highly generalized projection-free Frank-Wolfe type algorithms for adversarial and continuous DR-submodular maximization problems. The settings they consider can be a full information or a (semi-) bandit feedback, with monotone or non-monotone functions, having different constraints, and types of stochastic queries. Notably, for every problem they consider in the non-monotone setting, they either provide the first algorithm with proven sub-linear $\\alpha$-regret bounds or they improve the already existing $\\alpha$-regret bounds. They also report obtaining the state-of-the-art sub-linear $\\alpha$-regret bounds among projection-free algorithms in the majority of the monotone settings they consider. In the remaining monotone setting, they match their result to the existing one.", "questions": "I do not have any clarifying questions on my mind at the moment.", "limitations": "", "rating": 10, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper's efforts to present unified projection-free algorithms is convenient and worthy of exploration. The main technical contributions of the paper, a.k.a. combining the ideas of meta-actions and random permutations and providing a refined analysis that does not rely on variance reduction techniques, are original. The ideas, contributions, and techniques are expressed clearly. I especially enjoyed the level of detail in Table 1 and Appendices A.2 and C.", "weaknesses": "I have not noticed particular weaknesses so far.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "ip7iqejjd7", "reviewer": "Reviewer_5yTK", "summary": "This paper investigates online adversarial continuous DR-submodular optimization. The authors propose unified projection-free Frank-Wolfe type algorithms under many settings, e.g., full information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. Compared with the related works, most of the proposed algorithms achieve state-of-the-art $\\alpha$-regret bound.", "questions": "I have the following questions to ask the authors:\n\n* Could you elaborate on the technical challenges of this paper? The proposed algorithms seem to combine existing techniques without introducing novel technical tools. \n* This paper proposes two unified projection-free Frank-Wolfe type algorithms for the full-information and bandit settings. Could you provide the reasons why previous algorithms couldn't achieve a unified framework? \n* Compared with Zhang et al. (2023) for non-monotone functions, the proposed algorithms achieve only a slight improvement in terms of $\\alpha$-regret guarantee. Can you explain the reasons for this, and the differences between two algorithms? \n* Could the authors provide a discussion on the technical contributions of this paper regarding online adversarial continuous DR-submodular optimization?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* This paper conducts a detailed investigation on online adversarial continuous DR-submodular optimization and proposes effective algorithms for various settings. \n* Compared with existing studies, the proposed algorithms achieves state-of-the-art $\\alpha$-regret bound in most settings.", "weaknesses": "The presentation of technical contributions and motivation in this paper requires further improvement. See **Questions** below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "qAw8MmMjjd", "reviewer": "Reviewer_EVLt", "summary": "The paper presents unified projection-free Frank-Wolfe algorithms for online continuous adversarial DR-submodular optimization. It covers various scenarios such as full-information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. The algorithms achieve state-of-the-art or improved regret bounds compared to existing methods. The paper also addresses semi-bandit and bandit feedback for adversarial DR-submodular optimization.", "questions": "Please refer to weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper presents a unified approach for online continuous adversarial DR-submodular optimization, covering a broad spectrum of scenarios. This comprehensive investigation is novel and expands the understanding of the field beyond previous research. The authors introduce technical novelties, such as the combination of meta-actions and random permutations, contributing to the originality of the research.\n\nThe paper is well-structured and clearly presents the problem formulation, algorithms, and theoretical analysis. The inclusion of tables and figures enhances the clarity of the presentation.\n\nIn summary, the research addresses a significant problem in the field of continuous adversarial DR-submodular optimization with numerous real-world applications. The proposed algorithms demonstrate practical relevance and significance, contributing to the development of efficient optimization techniques for DR-submodular functions.", "weaknesses": "While the paper mentions the applications of continuous adversarial DR-submodular optimization, it lacks a thorough empirical evaluation of the proposed algorithms on real-world applications. Including experiments that demonstrate the performance of the algorithms in practical scenarios would strengthen the paper's claims and provide empirical evidence of their effectiveness\n\nI guess that the authors have adopted a text-wrapping layout around the pseudocode due to space constraints. However, the limited space allocated to the pseudocode has resulted in somewhat disorganized format. I would suggest that the authors consider using algorithm2e to reduce the space occupied by the pseudocode, thereby enhancing its readability. Just a friendly suggestion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)