From Linear to Linearizable Optimization:  A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
Authors: Mohammad Pedramfar
Vaneet Aggarwal
Venue: NeurIPS 2024 poster (2024)
Keywords: convex optimization
DR-submodular optimization
Primary area: optimization

Abstract: This paper introduces the notion of upper-linearizable/quadratizable functions, a class that extends concavity and DR-submodularity in various settings, including monotone and non-monotone cases over different types of convex sets. A general meta-algorithm is devised to convert algorithms for linear/quadratic maximization into ones that optimize upper-linearizable/quadratizable functions, offering a unified approach to tackling concave and DR-submodular optimization problems. The paper extends these results to multiple feedback settings, facilitating conversions between semi-bandit/first-order feedback and bandit/zeroth-order feedback, as well as between first/zeroth-order feedback and semi-bandit/bandit feedback. Leveraging this framework, new algorithms are derived using existing results as base algorithms for convex optimization, improving upon state-of-the-art results in various cases. Dynamic and adaptive regret guarantees are obtained for DR-submodular maximization, marking the first algorithms to achieve such guarantees in these settings. Notably, the paper achieves these advancements with fewer assumptions compared to existing state-of-the-art results, underscoring its broad applicability and theoretical contributions to non-convex optimization.

From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
Mohammad Pedramfar
Vaneet Aggarwal Purdue University vaneet@purdue. edu
McGill University and Mila mohammad, pedramt ar@mila. quebec
Abstract
This paper introduces the notion of upper- ooperr/inarizahhequuaaiiizaz functions, a class that extends concavity and Dussubmodulariity in various settings, including monotone and non-monotone cases over different types of convex sets. A general meta-algorithm is devised convert algorithms for linear/quadratic maximiza- tion into ones that optimize oopeerrineerizaaleqquuaaaizzzz unified approach tackling concave and OR-submodular optimization problems. The paper extends these results to multiple feedback settings, facilitating conver- sions between comi-bandit/fist-orrre as well as between first/zeroth-orss order feedback and semi remi-bandit/bandit feedback. Leveraging this framework, new algorithms are derived using existing results as base algorithms for convex optimization, improving upon state-of-the-ar results in various cases. Dynamic and adaptive regret guarantees are obtained for DR- submodular maximization, marking the first algorithms to achieve such guaran- tees in these settings. Notably, the paper achieves these advancements with fewer assumptions compared to existing state-of-the-a results, underscoring its broad applicability and theoretical contributions to non-convex optimization.
functions, offering a
feedback and bandit/zeroth-orde feedback.
Introduction
Overview: The prominence of optimizing continuous adversarial y-weakly up-concave functions (with DR-submodular and concave functions as special cases) has surged in recent years, marking crucial subset within the realm of non-convex optimization challenges, particularly in the forefront of machine learning and statistics. This problem has numerous real-world applications, such as
1X 26) This problem is modeled as repeated game between an optimizer and an adversary. In each round, the optimizer selects an action, and the adversary chooses a 7-weakly up-concave reward function. Depending on the scenario, the optimizer can then query this reward function either at any arbitrary point within the domain (called full information feedback) or specifically at the chosen action (called semi-bane aimi-bandit/bandii feedback), where the feedback can be noisy/deterministic.. The performance metric of the algorithm is measured with multiple regret notions static adversarial regret, dynamic regret, and adaptive regret. The algorithms for the problem are separated into the ones that a projection operator to project the point to the closest point in the domain, and the projection- free methods that replace the projection with alternative such Linear Optimization Oracles (LOO) or Separation Oracles (SO). This interactive framework introduces a range of significant challenges, influenced by the characteristies of the up-concave function (monotone/non-monne monnonne)))) the constraints imposed, the nature of the queries, projection-freeppooeciiin--bes algorithms, and the different regret definitions.
revenue maximization, mean-field inference, recommendation systems 4 20 30
12
24
Work done while at Purdue University
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Online up-coneave maximization
Feedback
Reference
Appa.
# Ol queries
logr (a-regret)
46
1/2
Full Information
stoch.
T 1/2)
2/3 8/3
V.
Corollar
1-e
1/2
85
1-0
3/4
Semi bandit
stoch.
0 K.
Corollary
7
1 1-
2/3
det.
Corolaar
1/2
Full Information
stoch.
35
1-6
T 1/4])
4/5 8/5
Monotone
Corollar
3/4
339
1-e
3/
det.
A8 I(*)
--e
4/5
Bandit
B5
1
5/6
stoch.
Corollary
1ee
4/5
Information
stoch.
1/2
T 1/2)
2/3 8/3
1/2
general
Semi handit
stoch.
Corollary
15
<P/(1 232))
1/2
3/4
1/2
det.
Corollay
77/1+
1/2
Full Information
1/2
THE O. 1/4)
475 8/5
Bandit
stoch.
Corollary
35
72/(1 + exd)
1/2
576
3/4
15
(1 8/44
(" 0, 1/2]
2/3 0/3
Information
stoch.
(1 4/44
1/2
F
Corollary
(1 4//4
1/2
Non- Monotone
Semi-band
stoch.
85
(1- 43/4
3/
general
Corollary
(1
2/3
det.
Corollary
(1- 63/4
2
1/2
Full Information
35
(1-
T" O. 1/4]
4/5 0/5
stoch.
Comolaay
3/4
det.
48
475
Bandit
5/6
stoch.
Corollary
(1 2//1
4/5
This table compares different static regret results the online up-coneave maximization. The logarithmic terms in regret are ignored. Here h == minagk | Our algorithm is projection free and use a separation oracle. The rows marked with $ use gradient ascent, requiring potentially computationally expensive projec- tions. The rows marked with (*) denote results that could be considered special of our framework. In particular, obtain those results if
Online Gradient Ascent instead of SO-DGA the base algorithm in Corollary 7 Note that result (39], marked by fE. uses convex optimization subroutine in each iteration, which could potentially be more expensive than projection and therefore not considered a projection-free result. It is also the only existing result, in all the tables, that outperforms ours. We note that stochastic results be used in deterministic, and bandit'semi-bandee in full information and thus cases where result is result because of result in less information setup.
added, our result improves state-of taae-of-thhe-at the-art projection All results assume that functions are Lipschitz. Except for our results on monotone functions over general con- vex sets, all results also assume diffcrentiabiliiyy All previous results assume that functions are DR-submodular, also assume functions are smooth, i.c., their gra-
while only require up-concavity. Results of 35 and 30 dients Lipschitz.
In this paper, we present comprehensive approach to solving adversarial up-concave optimiza- tion problems, encompassing different feedback types (including bandit, semi-bandit and full- information feedback), characteristics the up-concave function and constraint region, projection- free/projection-bart based algorithms, and regret definitions. While the problem has been studied in many special cases, the main contribution of this work is a framework that based on novel notion of the function class being upper-lineanee lpper-lineerizablee (or upper-quadratizable), We design meta- algorithm that converts certain algorithms designed for online linear maximization to algorithms capable of handling upper-linearizable function classes. This allows us to reduce the problem of up-concave maximization three different settings to online linear maximization and obtain corre- sponding regret bounds. In particular, our results include monotone 7-weakly up-concave functions over general convex set, monotone w-weakly up-concave functions over convex sets containing the origin and non-monotone up-concave functions. While the above result is for first order feedback, we then derive multiple results that increase the applicability of the above results. We extend the ap- plicability of FOTZO and STB algorithm introduced in 34 algorithms for firt-order/semii bandit feedback into algorithms for srdtth-oderrbaandit feedback. convert algorithms that require full-informatio
setting which allows to convert
We also design meta-all meta-algone algorithm that allows feedback into algorithms that only require hami-bandi//bandie feedback.
We demonstrate the usefulness of results through two applications as described in the following. In the first application, we use the SD-OGD Algorithm in [17] as the base algorithm for online linear op- timization, which is projection-five free algorithm. Using this, first obtain the adaptive regret (and

---

therefore also static regret) guarantees for the three setups of Duusmbood (or more generally, up- concave) optimization with mami-baniit feedback/first order feedback in the respective cases. Then, the meta-algorithms for conversion of finst-order/smmi-bane result with zeroth-order/bandit feedback. In the cases where the algorithms are full-information and not (semi-)bandie we use another meta-algorithm to obtain algorithms in (bai-itandiit feedback setting. In the next application, we use the "Improved Ader" algorithm of [43] which is a projection based algorithm providing dynamic regret guarantees for the convex optimization. Afterwards, the same approach as above are used to obtain the results the three scenarios up-concave optimiza- tion with first-order feedback.
to veroth-order/bandit are used to get
Technical Novelty: The main technical novelties in this work are as follows.
1. We proposes novel notion of linentizblelquudratiizzllle functions and extend the meta- algorithm framework of (34] from convex functions to linearizableqqudraatabblll functions. This allows us relates large class of algorithms and regret guarantees for optimization of linear/quadratic functions to that for linearizableqqaarraiiabbel functions.
2. We show that the class of quadratizable function optimization is general, and includes not only concave, but up-concave optimization in several cases. For some of the cases, this proof uses generalization of the idea of boosting (146) 48) ) which was proposed for Dussubood
maximization, mentioned in Corollaries anddeessnnnn]n and
3. We design new meta-algorithm, namely SFTT, that captures the idea of random permutations
(sometimes referred as blocking) used in several papers such as [45] 47 35). While
previous works used this idea in specific settings, our meta-algorithm is applicable in general
settings.
4. We note the generality of the above results in this paper. results are general in the following three aspects:
a) In this work, we improve results for projection-free static regret guarantees for DR- submodular optimization in all considered cases and obtain the first results for dynamic and adaptive regret. Moreover, these guarantees follow from existing algorithms for the linear optimization, using only the statement of the regret bounds and simple properties of the algo- rithms.
b) We consider 3 classes of DR-submodular functions in this work. However, to extend these results to another function class, all one needs to do to (i) prove that the function class quadratizable; and (ii) provide an unbiased estimator of g (as described in Equation [T]
c) We consider 2 different feedback types in offline setting (first/zero order) and 4 types of feedback in the online setting (first/zero order and nall-ifformation/ttivaaall query). Convert- ing results between different cases is obtained through meta-algorithns and guarantees for the meta-algorithms which only relies on high level properties of the base algorithms (See Theorems and g
Key contributions:
The key contributions in this work are summarized as follows.
1. We formulate the notion of apper-uuabaazzuhbllpee---eeeeiee that generalizes the notion of strong-concavityyconevvttt and also DR-submodularity in sev- eral settings. In particular, we demonstrate the the following function classes are upper- quadratizable: (i) monotone 7-weakly μ-strongly DR-submodular functions with curvature over general convex sets, (ii) monotone 7-weakly DR-submodular functions over convex sets containing the origin, and (iii) non-monotone DR-suboodular optimization over general convex sets.
functions, which is a class
2. We provide a general meta-algorithm that converts algorithms for linear/quadratic maximiza- tion to algorithms that maximize apper-quadratizabbe functions. This results is unified ap- proach to maximize both concave functions and DR- subuoouuuaa functions in several settings.
3. While the above provides results for semi-bandit feedback (for monotone subsubuod op- timization over general convex sets) and first-order feedback (for monotone DR subsuuua optimization over convex sets containing the origin, and non-monotone DR-submodular op- timization over general convex sets), the results could be extended to more general feedback settings. Four meta algorithms are provided that relate cami-baaditffisttordee feedback to ban- dit/zeroth order feedback; that relate; first order to deterministic zeroth order; and that relate
3

---

first/zeroth order feedback to semi memii-aanii/bbaddae feedback. Together they allow us to obtain results in 5 feedback settings (first/zeroth order cullrinformation and comi-bandi//baditt and deterministic zeroth order). We also discuss meta-algorithm to convert online results to of- fline guarantees.
4. The above framework is applied using different algorithms the base algorithms for linear optimization. S0-OGD [17] is a projection-free algorithm using separation oracles that provides adaptive regret guarantees for online convex optimization. We use our framework cover the 18 cases in Table [ We improve the regret guarantees for the previous SOTA projection- free algorithms in all the cases. If we also allow comparisons with the algorithms that are not projection-free free, we still improve the SOTA results in 12 cases and match the SOTA in 5 cases.
5. Using our framework, we convert online results using SO-OGD to offinn results to obtain 6 projection free algorithms described in Table 2 We improve the regret guarantees for the previous SOTA projection-free algorithms in all the cases, except for deterministic first order feedback where existing results are already SOTA. If we also allow comparisons with the algorithms that are not projection-free, we still improve the SOTA results in 6 cases and match the SOTA in the remaining 3 cases.
6. We use our framework to convert the adaptive regret guarantees of SQ-OGD to obtain projection- free algorithms with adaptive regret bounds that cover all cases in Table 3 Our results are first algorithms with adaptive regret guarantee for online Du-suboodular maximization.
7. "Improved Ader" 43 is an algorithm providing dynamic regret guarantees for online convex optimization. We use our framework to obtain 6 algorithms which provide the dynamic regret guarantees as shown in T Our results are first algorithms with dynamic regret guarantee for online DRssubmodular maximization.
8. For monotone 7-weakly functions with bounded curvature over general convex sets, we im- prove the approximation ratio (See Le
9. As mentioned in the descriptions of the tables, in all cases considered, whenever there is an- other existing result, we obtain our results using fewer assumptions than the existing SOTA.
2 Problem Setup and Definitions
For a D S Rd, we define its affine hull (D) to be the set of ax + (1 (1-a)) anyy for x, in K. and
E R. The relative interior of D is defined as relint (D) == (x E D 3r > 0, (x) n aff aff S
D). For any u E K", we define the path length Pr := Σ IM - u,+1ll- Given 2 0 and 0 <<> <
say differentiable function ʃ : KC + R is p-strongly 7-weakly up-concave if it is p-strongly 7-weakly concave along positive directions. Specifically if, for all x y in K, we have
(V)()))) - x) x) - xIp) S
S 1 ( (IVI()))) - x) - xIP)
We say Vʃ k Rd is u-strongly 7-weakly up-super-gradient of ʃ if for all x S y in XC, the above holds with V instead of V. We say f is u-strongly 7-weakly up-concave it is continuous and it has a p-strongly 7-weakly up-super-gradient. When it is clear from the context, we simply up-super-graten gradient for f. When 7 1 and the above inequality holds for all
refer to V f x,y E K., we say [ is p-strongly concave. A differentiable function f IC - IR is called --weakly continuous DR-submodular if for all < y, have ff(x) 2 vVl(y.. It follows that any 7- weakly continuous DR-subnod functions is 7-weakly up-concave. We refer to Appendix B for more details.
Given a continuous monotone function f: + R. its curvature is defined as the smallest number E [0, 1] such that f(y + 2) -f(y) > (1 (1- (1-c)(f(x + z) f(x)), for all x,y K. and z > 0 such that x + y + z E K.. We define the curvature of a function class F as the supremum of the curvature of functions in F.
Online optimization problems can formalized as a repeated game between an agent and an ad- versary. The game lasts for T rounds on convex domain K. where T and K. are known to both players. In 1-th round, the agent chooses an action x, from an action set K. C TRdd then the adversary chooses loss function fo F and query oracle for the function fc. Then, for 1 < < k.
4

---

Table Offiie up-coneave maximization
Set
Feedhack
Reference
Appx.
Complexity
61
1-6-
0
F
stoch.
19
1-67
0
001/4
0 K
Corollary
1-e"t
0(1/2)
Monotone
det.
Corollary
36
1-e"
1-67
0(1/2")
O[17e")
36
1-e"
O[17e")
stoch.
Curollary
1-
001/")
20
77111
O(1/e))
stoch.
56
72/01 +
0(1/2)
geneal
Corollary
T//11 +
0(1/
37
72/11
0
Curollar
7-/11
0(1/2)
37
72101 +7")
stoch.
Corollar
7 //1 +c7
001/4)
36
010 (11--A1
-
0(142)
Non. Monotme
V
stoch.
A)/1
00/33)
geacral
Coeollary
A)/4
001e2)
det.
36
211--81
7--1
(+
Corollary
A1/1
00127)
36
70
o(1e)
stoch.
Conollary
A3/4
This table compares the different results for the numher of oracle calls (complexity) within the constraint set for up-concave maximization. We refer to (36) for a more comprehensive table that includes results for deterministic first order feedback. Here h == mitlag:: | and
1/7-
t [20]. [46] [48] use gradient ascent, requiring potentially computationally expensive projections. All previous results assume that functions are differentiable, DR-submodular, Lipschitz and smooth (i.c., their gradients are Lipschitz). Result of [19] also requires the function Hessians to be Lipschitz. It also requires the density of the stochastic oracle to be known and the log of density to be 4 times differentiable with bounded 4th derivatives. We only require the functions be up-concave, differentiable and Lipschitz, except for results on monotone functions over general convex sets where we do not need differentiability.
the agent chooses points Yt,i and receives the output of the query oracle. The precise definition of agent (124 _ A4uurry) is given in Appendix B with the query oracle being any of stochas- tic/deterministic first/zeroth order or aami-bandit/bandi..
An adversary Adv is set of realized adversaries B = (Bi,..., where each B, maps (xi,-.. xx) KCT (fe, Q.) where fr F and Q, query oracle for fi Adversaries can be oblivious (B, are constant and independent of (x1,".., independent of x.), or fully adaptive (no restrictions). We use (F) to denote the set of all possible realized adversaries with deterministic i-th order oracles. the oracle is instead stochastic and bounded by B, we use AFv B) denote such an adversary. Finally, we use (F) and AFv B) denote all oblivious realized adversaries with i-th order de- terministic and stochastic oracles, respectively. In order handle different notions of regret with the same approach, for an agent A. adversary Adv, compact set U C KT, approxima- tion coefficient < a < and S c < T. we define regret as R. Ad)))a (a, bj ==
weakly adaptive (B, are
where the expectation in the definition of the regret is over the randomness of the algorithm and the query oracle. We use the notation Ra,((U)aa bj == RA (a.aaa)))aa b] when Adv {B} is singleton. We may drop a when it is equal to 1. When a < 1, we often assume that the functions are non- negative. Static adversarial regret or simply adversarial regrer corresponds 1, T and U contains only sin- gle element then it is referred to as the dynamic regret [51 43). Adaptive regret defined as max gaggT R.AAdy (c,))a b] [23 We drop a, b and ' when the statement is independent of
SUPBEAdv E (ax jureuu El= fi(u.) Si
a 1, T
and U = KT == ((x,.... x) x E K). When
their value or their value is clear from the context.
3 Formulation of Upper-Quadratizaley Functions and Regret Relation to that of Quadratic Functions
Let K. C IRd be convex set, be function class over IC. We say the function class is upper- quadratizable if there are maps F K. Rd and h K. - K. and constants 2 0, < <
5

---

Table 3: Non-stationary up-coneave maximization
F
Feedback
Reference
Appx.
regret type
ae-regret
Corollary 8
dynamic
T PT) 1/2
Full Information
stoch.
F
Corollary
1-
adaptive
T
0 K.
Semi-bandit
stoch.
Corollary
c
1 1-
adaptive
72/3
Corollary
c
1 - 6
dynamic
T + Pr)
det.
Momotone
Full Information
Corollary
c-c
1 1-
adaptive
T
F
Corollary
c
1 1-
dynamic
T P/)1/2 7//4
stoch.
Corollary
7
1-c" 1-
adaptive
Bandit
stoch.
Corollary
1-
adaptive
T
Corollary
b
7/11
dynamic
T² + PT)
VF
Semi-bandit
stoch.
Corollary
b
2/11 +
adaptive
T1/2
general
Corollary
72/(1 +11+ 7/(1+
dynamic
TV + PT)
Full Information
det.
F
Corollary
c
adaptive
T1/2
Corollary
8-b
72/(1
dynamic
T + 77
Bandit
stoch.
Corollary
7//(1
adaptive
T3/4
Corollary
8-d
(1-h)/4
dynamic
T T1 Pr) 71/2
Full Information
stoch.
Non- Mon-Monotone
VF
Corollary
7
(1 b)/4
adaptive
general
Semi-bandit
stoch.
Corollary
(1 1)/4
adaptive
T:T
Corollary
8-
(1 - h)/4
dynamic
(1 (I+A)) Pr)
det.
Full Information
Corollary
7d
(1 h)/4
adaptive
T:/2
F
Corollary
8
(1 13/4
dynamic
PT)
stoch.
Corollary
7
(1 b)/4
adaptive
73/4
Bandit
stoch.
Corollary
A1/4
adaptive
77/55
This table includes different results for non-stationary up-concave maximization, while no prior results exist in this setup to the hest of our knowledge. The results for adaptive regret are projection-free and use a separation oracle while results for dynamic regret use convex projection. Note that full-information algorithms with deterministic feedback require 2 queries per function while the ones with stochastic feedback only require one, at the cost of higher regret.
and B > 0 such that
afly) - f(h(x)) 3 (o(f,))), - x) x)- -ly-
- x x1(3)
(I)
As a special case, when / 0, say F is upper-linearizable We use the notation Fr.g to denote the class of functions q(y): = (g(f,)), - -x) = - x||² : K. + R, for all f F and x E I. Similarly, for any B, > O, we use the notation [u|[B]] to denote the class of functions q(y) == (o.y - x) ly x|| : K. + R, for all x E AC and o E B (0). A similar notion of nower--uaddaatzzaalleemee Iinerizaale may be similarly defined for minimization problems such as convex minimization. F
Algorithm 1: Online Maximization By Quadratization DMBQ(A, G,h)
We say an algorithm G is first order query algorithm for g if, given point x E K and a first order query oracle for f. it returns (a possibly unbiased estimate of) xf, We say G is bounded by B, if the output of G is always within the ball B, (0) and we call it trivial if it simply returns the output of the query oracle at x.
Input horizon T, semi-bandit algorithu A, query algorithm ç for g. the map ht X. -> K
for t 1,,,..., T do
Play l(xx)) where is the action chosen by A
Recall that an online agent A is composed of action function Auetion and query function Aquery Informally, given an online algorithm A with semi-bandi, feedback, we may think of A' == OMBQ G, h) as the online al- gorithm with (A4')actionn ~ h([Aaction) and (A')ueey x G. As special case, when = Id and G is trivial, we have A' A.
The adversary selects Si and a first order query oracle for ft Run G with access to and the query oracle for fa to calculate o, Return on as the output of the query oracle to A
end
Note that, without any loss in generality, may replace (8, n. with (1, 8u, 3g) and therefore assume
However, we keep / as a separate variable makes some expressions in future sections simpler.
"Specifically, we say Fi is lower-quadrattzabbee if a ((((x))) 2 3 (a(f))),) x) + f x||
Note that this is equivalent FF being upper--uadrraizzale with the same a,3, and μ. but with f(=ffx)..

---

Theorem 1. Let A be algoritiu for online optimization with semi cemi--andit feedback. feedback, Also let F be function class over K. that is quadratizable with μ Z and maps g F X R and h K. K, let G be a query algorithm for and let A' OMBQ 9, h.. Then the following are true.
1.If returns the exact value of g. then we have RA a,Advi (F) S $ 1,Adv, (o)
On the other hand, i returns an unbiased estimate of g and the output of G is bounded by B1,
then we have R.A (F, I BRA (Q.(B)..
As a special case, when f is concave, we may choose a = 3 = 1, h = Id. and g(f, to be a super-gradient of f at In this case, Theorem reduces the concave version of Theorems and in [4].
Up-concave function optimization is upper-quadratizable function optimization
In this section, we study three classes of up-concave functions and show that they are upper- quadratizable. We further this property to obtain meta-algorithms that convert algorithms for quadratic optimization into algorithms for up-concave maximization.
4.1 Monotone up-concave optimization over general convex sets
For differentiable DR-submodular functions, the following lemma is proven for the case = 1 in Lemma 2 in [13] and for the case μ = in (20] (See Incquality 7.5 in the arXiv version). We show the result for general ju-strongly 7-weakly up-concave function with curvature bounded by See Appendix for proof.
Lemma Let f [0, TR be non-negative monotone je-strongly 7-weakly up-concave
function with curvature bounded by c. Then, for all x, [0, 1] we have
72 + cx2 f(y) - f(x) - 1 cy
7
(1V((x), x)
~ lly x|3
where V is an up-super-gradient for f-
Further, we show that any tive adversary is also online up-concave optimization algorithm.
feedback online linear optimization algorithm for fully adap-
Theorem 2. Let K C [0, 1]d be convex set, let p. 2 0, Y E (0. 1], E [o, 1] and let A be algorithm for online optimization with semi-bandit feedback. Also let F be an Mi-Lipschitz function class over K. where every f E F may be extended to a monotone p-strongly 7-weakly up-concave function functioon curvature bounded by e. defined over
[0, 1] Then, for any B1 2 M1. we have
R-A 1-ey2 Adv, (F)
R-A ey "AAV
7
RA 22 14e5 Adv (F, S 1+ oy (d.
R
These results follows immediately from Theorem and Lemma [ Note that it is important to as- sume that every function in may be extended to non-negative up-concave function over (0, 1]d for Lemma T to be applied.
Algorithm 2: Boosted Query oracle for
Monotone up-concave functions over con- vex sets containing the origin BQMO
Input: First order query oracle, point Sample E [0, 1] according to Equation Return the output of the query oracle at
Corollary 1. The results of (20). 181 and [13]
monotone continuous DR-submodular maximiza- tion over general convex sets may be thought of as
special cases of Theorem 2 when A is the online gradient ascent algorithm.
4.2 Monotone up-concave optimization over convex sets containing the origin
The following lemma is proven for differentiable Dubbubuua functions in Theorem 2 and Proposition of [46]. The proof works for general up-coneave functions as well. We include proof in Appendix E for completeness.
7

---

Lemma 2. Let f:
: [0, 1]d + R be a non-negative monotone 7-weakly up-coneave differentiable
function and let F [0, 1j + RR be the function defined by
y="(=-1) F(x) J.' (1-0-7)2 (f f(O))dz.
Then F is differentiable and, if the random variable Z E [0. is defined by the law
V2 [0, P(Z S Lo yen(u-1)
1-e du,
(2)
then have E [V * x)] VF(x). Moreover, we have (1- f(x)
S
1-e (VF(x), x).
Theorem 3. Let K S 10, be convex set containing the origin, let E (0, 1] and let A be algorithm for online optimization with semi-bandit feedback. Also let be a function class over K. where every f E F is the restriction of a monotone 7-weakly up-concave function defined over
[0. 1] the set K.. Assume differentiable and M1-Lipschitz for some M1 > 0. Then, for any
B1 M1, we have
RA (F I 1-07
RA
where A' OM,Q BQMO, Id).
This result now follows immediately from Theorem 1 and Lemma
2
Corollary 2. The result of [46] in the online setting (when there no delay) may be seen as an application of Theorem 3 when is chosen to be online gradient ascent.
4.3 Non-monotone up-concave optimization over general convex sets
The following lemma is proven for differentiable DR-submodular functions in Corollary 2, Theo- rem 4 and Proposition of of [8]] The arguments works for general up-concave functions as well. We include proof in Appendix F for completeness.
R be non-negative continuous up-concave differen- tiable function and let x E K. Define F [0, + E the function F(x)
Lemma 3. Let
[0, 1jd
So 32(1- (f(z (x - x) + x) ++)))(ff -(x))
dz. Then F is differentiable and, if the random vari-
able 2 E [0, 1] is defined by the law
V2 E 10, P() = Jo 3(1
du,
(3)
a 2
then we have E
VS
2 2 (x x) + x
(x). Moreover, we have
1 - ||||> f(y) ff
x +
3 VF(x). x).
Theorem 4. Let K. C. 1]d be a convex set. u K, h= |uloc and A be algorithm for online
optimization with semi-bar banibb feedback. Also let F be a function class over K. where every f E F is the restriction of an up-concave function defined over [0, 10, the set K. Assume differentiable and M, -Liischhir for some M, > 0. Then, for any B, 2 M1 and A' OMBQ
xxtx
we have RAA', AFV B,) < RR (.A
Algorithm 3: Boosted Query oracle for Non- con-monotone up-concave func- tions over general convex sets BQN
These results now follows immediately from Theo- and Lemma
Input: First order query oracle, point x Sample E [0, 1] according to Equation Return the output of the query oracle at
Corollary 3. The result of [48] in the online setting without delay may be seen as an application of Theo- rem 4 when A is chosen to be online gradient ascent.
$ (x x) +

---

Meta algorithms for other feedback cases
In this section, we study several meta-algorithms that allow convert between different feedback types and also convert results from the online setting to the offline setting.
First order/semi-bande to zeroth order/bandit feedback: In this section we discuss meta- algorithms that convert algorithms designed for first order feedback into algorithms that can handle zeroth order feedback. These algorithms and results are generalization of similar results in (3 to the case where a
We choose a point E relint (K) and real number r > 0 such that aff (IC) (C)) S K. Then, for any shrinking parameter 0 S 6 < define K,s (1 )CC + f.c. For a function f K. + R
defined on convex set _ IRd, its d-smoothed version fs Ks - R is given as
= c (0) [f + 8v)], where Co aff (K) - x, for any K,, is the linear space that is translation of the affine hull of IC and v is sampled uniformly at random from the k dim (aatm(oo-dddeenee -dimensional ball Co n ((). Thus, the function value (x) is obtained by "averaging" f over a sliced ball of radius 8 around x. For a function class F over K., we use F, to denote {.ss ʃ E F). We will drop the subscript when there is no ambiguity (See Appendix for the description of the algorithms and the proof.).
(x) == L8 (Xx)
Theorem 5. Let F be an M₁ Mi-Lipschitz function class over a convex set I. and choose and r as described above and let 8 r. Let u K" be compact set and let úi (1 1) + fc. Assume A is an algorithm for online optimization with first order feedback. Then, if A' FOTZO(AA) where FOTZO is described by Algorithm and O < a S. 1, we have
RA (F (F,ag(F,Bo))) Bo) (U) S R- ",Adv Bo) (i) +
2D
8.,
On the other hand, we assume that A is semi-bandit, then the same regret bounds hold with A' = STB( where STB is described by Algorithm 6
Theorem 6. Under the assumptions of Theorem
5 A' = FOTZO-2P(A) where FOTZO-2P is de-
scribed by Algorithm Jand O < a S 1, we have
RA advg (U) S R- a.Advy( ( + 3+ 2D 8M,T.
Full information to trivial query: In this section, we discuss meta-algorithm that converts algo- rithms that require full-information feedback into algorithms that have a trivial query oracle. In par- ticular, it converts algorithms that require first-order full-information feedback into semi-bandit al- gorithms and algorithms that require zeroth-order full-information feedback into bandit algorithms.
Here we assume that Atteery does not depend on the observations in the current round. If the number of queries kn is not constant for each time-step, we simply assume that A queries extra points and then discards them, so that we obtain an algorithm that queries exactly K points at each time-step, where K does not depend on We say a function class F is closed under convex combination if for any f..... fu
E F and any 8,,".. ... 56 2 O with Σ, 5; = 1, we have 5ef E F.
Theorem 7. Let A be an online optimization algorithu with full- full-information feedback and with K queries at each time-step where Aquery does not depend on the observations in the current round and A' = (AT. Then, for any M1 -i-Lipcchitz function class F that is closed under convex combination and any Bi 2 Mr. O < a S 1 and < < b S T, let a' = [aa (allaa)))) 1) + 1, diam(K) and let (T) and (T/L.) denote the horizon of the adversary. Then, we
= [b/]],
have
R.A' a.dv (F. (K? (a, 6] M,DK(E a' + +1 LRA
A. (dc (C) T/
This result (proof in Appendix H is based on the idea of random permutations used 45 47 35
Online to Offline: An offline optimization problem can be though of as instance of online op- timization where the adversary picks the same function and query oracle each round. Moreover, instead of regret, the performance of the algorithm is measured by sample complexity, i.e., the mini- mum number of queries required so that the expected error from the a-approximation of the optimal value is less than 6.

---

Conversions of online algorithms to offline are referred to online-to-bee toline-to-batch techniques and are well-known in the literature (See (38). A sim- ple approach to simply run the online algo- rithm and if the actions chosen by the algo- rithm are " .XT, return x; for 1 < t S T with probability 1/T". We use OTB denote the meta-algorithm that uses this approach to con- vert online algorithms offline algorithms. The following theorem is a corollary which we in- clude for completion. (See Appendix for the proof.)
Algorithm 4: Stochastic Full-information To Trivial query (AFTT(A)
Input base algorithm A, horizon T, block size L> K.
for q = 1,2....,T/Ld.
Let X be the action chosen by A
Let (5)))= be the queries selected by A
Let (lq.1,...,.4
be random permutation
of {(g 1}L
9b}
for t (q- 1)L 1, .............................. ql. do
if typs for some 1 S Sisi K then
Play the action = y Return the observation to the query oracle as the response to the i-th query
Theorem 8.
Let A be an online algorithm that
queries more than K = T times per time- step that obtains an o-regret bound of O(T") over oblivious adversary Adv. Then the sample complexity of (TB(A) over {(f. 11)
else
Play action X = Xg
end
(ff.2)). (f. Adv] is O(E i-n).
end
end
Applications
Figure 6 captures the applications that are mentioned in Tables 1 and The exact statements are stated in Corollaries 7 and 8 in the Appendix. To obtain a result from the graph, let A one of S0-OGA or IA and select directed path that has the following properties: (i) The path starts at one of the three nodes on the left. (ii) The path must be at least of length and the edges must be the same color. (iii) If A is IA, the path should not contain SFTT OTB.
For example, if A SO-OGA and the path starts at the middle node on the left, then passes through OMBQ, FOTZO, SFTT, we get SFTT(FOTZO (BBOOOC(MMMMS-OOO (SO-OGA, BQMO, Id))). which a projection-free algorithm (using separation oracles) with bandit feedback for monotone up-concave functions over convex sets that contain the origin. As mentioned Table and Corollary (c). the adaptive regret of this algorithm of order O(T4/55. Note that the text written in the three nodes on the left correspond to the inputs of the meta-algorithm OMBQ. Also note that the color red corresponds to the setting where G is trivial query algorithm which means that the output of OMBQ is semi-bandit.
Figure 1: Summary of applications
A.QM_
OMBQ
FUTRO-P
A,DON
PO120
8FT2
7 Conclusions
In this work, we have presented a comprehensive framework for addressing optimization problems involving upper-quadratizable functions, encompassing both concave and DR-submodulaa functions across various settings and feedback types. Our contributions include the formulation of upper- quadratizable functions a generalized class, the development of meta-algorithms for algorithmic conversions, and the derivation of new algorithms with improved static/ dynamic/ adaptive regret guarantees. Exploring more subset of classes of upper-quadratizable functions where such frame- work could be applied is an important future direction.
8 Acknowledgement
This research was supported in part by the National Science Foundation under grant CCF-2149588.
10

---

References
[1] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- tions Research, 63(5):1227-1244, 2015.
[2] An Bian, Kfir Levy, Andreas Krause, and Joachim M Buhmann. Continuous DR-submodular maximization: Structure and algorithms. In Advances in Neural Information Processing Sys- lems, 2017.
[3] Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guar- anteed Non-convex Optimization: Submodular Maximization over Continuous Domains. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, April 2017.
[4] Yatao Bian, Joachim Buhmann, and Andreas Krause. Optimal continuous DR-submodular maximization and applications to provable mean field inference. In Proceedings of the 36th International Conference on Machine Learning, June 2019.
[5] Gruia Calineseu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740 1766, 2011.
[6] Chandra Chekuri, T.S. Jayram, and Jan Vondrak. On multiplicative weight updates for concave and submodular function maximization. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 201-210, 2015.
[7] Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free online optimization with stochastic gradient: From convexity to submodularity. In Proceedings of the 35th International Conference on Machine Learning, July 2018.
[8] Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximiza- tion. In Proceedings of the Twenty-First International Conference Artificial Intelligence and Statistics, April 2018.
[9] Lin Chen, Mingrui Zhang, and Amin Karbasi. Projection-free bandit convex optimization. In Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, pages 2047-2056. PMLR, 2019.
[10) Shengminjie Chen, Donglei Du, Wenguo Yang, Dachuan Xu, and Suixiang Gao. Continu- non-monotone DR-suboodular maximization with down-closed convex constraint. arXiv preprint arXivv2307.09616, July 2023.
[11] Amit Daniely. Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning, pages 1405-1411. PMLR, 2015.
[12] Josip Djolonga and Andreas Krause. From map to marginals: Variational inference in Bayesian submodular models. Advances in Neural Information Processing Systems, 2014.
[13] Maryam Fazel and Omid Sadeghi. Fast first-order methods for monotone strongly dr- submodular maximization. In SIAM Conference on Applied and Computational Discrete Al- gorithmms (ACDA23), 2023.
[14] Yuval Filmus and Justin Ward. A tight combinatorial algorithm for submodular maximization subject to matroid constraint. In 20/2 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 659-668, 2012.
[15] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex op- timization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385-394, 2005.
[16] Dan Garber and Ben Kretzu. Improved regret bounds for projection-free bandit convex opti- mization. In Proceedings of the Twenty Third International Conference on Artificial Intelli- gence and Statistics, pages 2196-2206. PMLR, 2020.

---

[17] Dan Garber and Ben Kretzu. New projection free algorithms for online convex optimization with adaptive regret guarantees. In Proceedings of Thirty Fifth Conference on Learning Theory, pages
PMLR, 2022.
[18] Shuyang Gu, Chuangen Gao, Jun Huang, and Weili Wu. Profit maximization in social networks and non-monotone DR-submodular maximization. Theoretical Computer Science, 957:1 13847, 2023.
[19] Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic conditional gra- dient++: (non)convex minimization and continuous submodular maximization. SIAM Journal on Optimization, 30(4):3315-3344, 2020.
[20] Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, 2017.
[21] Elad Hazan and Satyen Kale. Projection-fiees frree online learning. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, pages 1843-1850. Omnipress, 2012.
[22] Elad Hazan and Edgar Minasyan. Faster projection-free online learning. In Proceedings of Thirty Third Conference on Learning Theory, pages 1877-1893. PMLR, 2020.
[23] Elad Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th Annual International Conference on Machine Learning. ICML '09, pages 393-400. Association for Computing Machinery. 2009.
[24] Shinji Ito and Ryohei Fujimaki. Large-scale price optimization via network flow. Advances in Neural Information Processing Systems, 2016.
[25] Duksang Lee, Nam Ho-Nguyen, and Dabeen Lee. Non-smooth, h) "older-smootth and robust submodular maximization. arXiv preprint arXiv:221000666,, 2023.
[26] Yuanyuan Li, Yuezhou Liu, Lili Su, Edmund Yeh, and Stratis loannidis. Experimental de- sign networks: A paradigm for serving heterogeneous learners under networking constraints. IEEE/ACM Transactions on Networking. 2023.
[27] Yucheng Liao, Yuanyu Wan, Chang Yao, and Mingli Song. Improved Projection-free free Online Continuous Submodular Maximization. arXiv preprint arXiv:2305. 18442 May 2023.
[28] Zhou Lu, Nataly Brukhim, Paula Gradu, and Elad Hazan. Projection-free adaptive regret with membership oracles. In Proceedings of The 34th International Conference on Algorithmic Learning Theory, pages 1055-1073. PMLR, 2023.
[29] Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. In Proceedings of Thirty Fifth Conference on Learning Theory, pages 5314-5390. PMLR, 2022.
[30] Siddharth Mitra, Moran Feldman, and Amin Karbasi. Submodular+ concave. Advances in Neural Information Processing Systems, 2021.
[31] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. The Journal of Machine Learning Research, 21(1):4232-4280 2020.
[32] Loay Mualem and Moran Feldman. Resolving the approximability of offline and online non- monotone Subuumoou maximization over general convex sets. In Proceedings of The 26th International Conference Artificial Intelligence and Statistics, April 2023.
[33] Rad Niazadeh, Negin Golrezaei. Joshua Wang, Fransisca Susan, and Ashwinkumar Badani- diyuru. Online learning via offline greedy algorithms: Applications in market design and optimization. Management Science, 69(7):3797-338 -3177777777777 July 2023.
[34] Mohammad Pedramfar and Vaneet Aggarwal. unified framework for analyzing meta- algorithms in online convex optimization. arXiv preprint 20X1v2240..08621, 2024.
12

---

[35] Mohammad Pedramfar, Yididiya Y. Nadew, Christopher John Quinn, and Vaneet Aggarwal. Unified projection-free free algorithms for adversarial Su-submodular optimization. The Twelfth International Conference on Learning Representations, 2024.
[36] Mohammad Pedramfar, Christopher Quinn, and Vaneet Aggarwal. A unified approach for maximizing continuous ?-weakly DR-submodular functions. optimization-onliee preprini optimizaation-omline:55555... 2024.
[37] Mohammad Pedramfar, Christopher John Quinn, and Vaneet Aggarwal. unified approach for maximizing continuous DR-submodular functions. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[38] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trendy@ in Machine Learning, 4(2):107-194, 2012.
[39] Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, and Zhijie Zhang. Bandit multi-linear dr-submodular maximization and its applications on adversarial submodular bandits. In Inter- national Conference on Machine Learning. 2023.
[40] Yibo Wang. Wenhao Yang, Wei Jiang, Shiyin Lu, Bing Wang, Haihong Tang, Yuanyu Wan, and Lijun Zhang. Non-stationary projection-free online learning with dynamic and adaptive regret guarantees. Proceedings of the AAAI Conference on Artificial Intelligence, 38(14):15671- 15679, 2024.
[41] Bryan Wilder. Equilibrium computation and robust optimization zero sum games with sub- modular structure. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 32, 2018.
[42] Jiahao Xie, Zebang Shen, Chao Zhang, Boyu Wang, and Hui Qian. Efficient projection-free online methods with stochastic recursive gradient. Proceedings of the AAAI Conference on Artificial Intelligence, 34(4):6446-644 6463,66633300000 2020.
[43] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environ- ments. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[44] Lijun Zhang, Tianbao Yang, jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning, pages 5882 5891. PMLR, 2018.
[45] 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.
[46] Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodular maximization: Boosting via non-oblivious function. In Proceedings of the 39th International Conference on Machine Learning, 2022.
[47] Qixin Zhang, Zengde Deng, Zaiyi Chen, Kuangqi Zhou, Haoyuan Hu, and Yu Yang. Online learning for non-monotone DR- -ubbuuuod maximization: From full information to bandit feedback. In Proceedings of The 26th International Conference Artificial Intelligence and Statistics, April 2023.
[48] Qixin Zhang, Zongqi Wan, Zengde Deng, Zaiyi Chen, Xiaoming Sun, Jialin Zhang, and Yu Yang. Boosting gradient ascent for continuous DR-submodular maximization. arXiv preprint arXiv:2401.08333 2024.
[49] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. Journal of Machine Learning Research, 22(125))1-455 2021.
[50] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. Advances in Neural Information Processing Systems, volume 33, pages 12510-12520, 2020.
13

---

[51] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings the 20th international conference on machine learning (icml-03), pages 928-
936, 2003.
14

---

A Related works
DR-submodular maximization Two of the main methods for continuous DR-submodular maxi- mization are Frank- Wolfe type methods and Boosting based methods. This division is based on how the approximation coefficient appears in the proof.
In Frank-Wole type algorithms, the approximation coefficient appears by specific choices of the Frank- Wolfe update rules. (See Lemma
35
The specific choices of the update rules for
different settings have been proposed in 3
2
32
37 10]. The momentum technique of [31] has been
used convert algorithms designed for deterministic feedback to stochastic feedback setting. [99 proposed a Frank- Wolfe variant with access to a stochastic gradient oracle with known distribution. Frank- Wolfe type algorithms been adapted the online setting using Meta-Frank- -Wlfe X8 9 or
using Blackwell approachablity [33] Later [45] used a Saata-Frank-Woon with random permutation technique to obtain full-information results that only require single query per function and also bandit results. This was extended to another settings by 44 and generalized to many different settings with improved regret bounds by (35).
Another approach, referred to as boosting, is to construct an alternative function such that maxi- mization of this function results in approximate maximization of the original function. Given this definition, we may consider the result of [20] 8 [3] in these cases (i.e., the case of monotone DR-submodular functions over general convex sets), the alternative function is identical to the original function. The term boosting in this context was first used in 46 for monotone functions over convex sets containing the origin, based on ideas presented in [14 30 This idea was used later in [39 27 in bandit and projection-fre full-information set- tings. Finally, [48] a boosting based method was introduced for no-monotone functions over general convex sets.
as the first boosting based results. However,
Up-concave maximization Not all continuous DR-submodular functions are concave and not all concave functions continuous DR-submodular. [30) considers functions that are the sum of a concave and a continuous DR-submodular function.
well-known that continuous DR- submodular functions concave along positive directions [5] 3. Based this idea, 41 defined an up-concave function as a function that is concave along positive directions. Up-concave max- imization has been considered in the offline setting before, e.g. (25), but not in online setting. In this work, we focus on up-concave maximization which is a generalization of DR-submodular max- imization.
Projection-fiee optimization In the past decade, numerous projection-free online convex opti- mization algorithms have emerged tackle the computational limitations of their projection-based counterparts 22 7 42
17]. In the context of DR-submodular maximization, the Frank-Wolfe type methods discussed above are projection-free.
16
Non-stationary regret Dynamic regret was first analyzed in 51 for first order determinis- tic feedback. Later [43 obtained the lower bound and optimal algorithm in this setting. This
was later expanded to bandit setting in [49]. Adaptive regret was first analyzed in [23] and
the first optimal algorithm for projection-free adaptive regret was proposed [17] We refer to 23
43 50 49
40 and references therein for more details.
Optimization by quadratization The framework discussed here for analyzing online algorithms is based on the convex optimization framework introduced in [3]] We extend the framework to allows us to work with a-rrgret.Moreooeer [34] also demonstrates that algorithms that are designed for quadratic/linear optimization with fully adaptive adversary obtain similar regret in the con- vex setting. In this paper we introduce the notion of quadratizable functions generalizes this idea beyond convex functions all quadratizable functions. (see Theorem [1
This allows to inte- grate the boosting method with our framework to obtain various meta-algorithms for continuous DR-submodular maximization.
B Problem Setup in Detail
In this section, we further expand on the description in Section 2
15

---

A function class is a set of real-valued functions. Given a set D, function class over D is subset of all real-valued functions on D. A set K S R is called a convex set if for all x, I. and E [0. we have ox + (1 - ojy E K. For any E KP" we define the path length U++1 -
Pr(u)== :- 7
real-valued differentiable function f called concave if f(y) - f(x) s (y - z), for all J,y E Dom(J)) More generally, given 2 0 and O <> S 1, we say real-valued differentiable function is p-strongly w-aekll concave if
((v) - (()) s 1 (1G)(( - x) - x1²)
for all x, y E Df
We say differentiable function f: K R is u-strongly 7-weakly up-concave if is p-strongly y-weakly concave along positive directions. Specifically if, for all x S y K. we have
7 (1716))
- x) x f1y xxI² S [(y) S (VV)()), - x) - 4 - x x1(²
This notion could be generalized in the following manner. We say Vf K - Rdd is p-strooggy 7-weakly up-super-gradient of f if for all x S y in K., we have
(V)())) - x) + ~/2 lly xx(² = fly) f(x) - (Vf(x),) - x) - lly x
2
Then we say f is justtronlyy 7-weakly up-concave if is continuous and has a j-strongly 7-weakly up-super- suupe--gadieet. When it is clear from the context, we simply refer to ff as an up up-super-gradinn graddeet for f. When y 1 and the above inequality holds for all x. y K. say f is p-strongly concave.
A differentiable function f : K R is called continuous DR-submodular if for all x S y, we have fx(x)= 2 Vy(y). More generally, we say f is 7-weakly continuous DR DR-submodular if for all x S y, we have fx() 2 fy)( follows that any 7-weakly continuous Dubsuuuda functions is y-weakly up-concave.
Given a continuous monotone function f KC - R, its curvature is defined as the smallest number c E [0, 1] such that
+zy f(y) 2 (1 cf + z) f(x)).
for all y E and z 2 0 such that + z, y + K. We define the curvature of a function class F as the supremum of the curvature of functions in F.
Online optimization problems can be formalized sary. The game lasts for 7 rounds on a convex domain I. where T and K. are known to both players. In f-th round, the agent chooses action x, from action set I. Rdd then the adversary chooses a loss function ft E F and a query oracle for the function ft- Then, for 1 S i S ky, the agent chooses a points yt, and receives the output of the query oracle. Here k; denotes the total number of queries made by the agent at time-step I, which may or may not be known in advance.
repeated game between an agent and an adver-
To be more precise, space that captures all the randomness of A. We assume that, before the first action, the agent samples w E Ω. The next element in the tuple, A (AApction .... A Anation) is a sequence of functions such that A that maps the history 2 KC-1 I'' (KC x O)a, to x, E K. where we use O to denote range of the query oracle. The last element in the tuple, A is the query policy. For each 1 < t < T and S i < ke. Attieryy 2 x XC x II'2] (KC O)h, (K O)i is function that, given previous actions and observations, either selects point yi E K. i.., query. or signals that the query policy at this time-step is terminated. We may drop w as one of the inputs of the above functions when there is no ambiguity. We say the agent query function is trivial if
agent consists of tuple (S2- A ,Aquery), where Q is probability
"In the literature, the curvature is often defined for differentiable functions. When f is differentiable, we have
[V(());
c inf
x.ck,
[V/())]
16

---

I T. In this case, we simplify the notation and use the notation A Auction = (A,... Ar) to denote the agent action functions and assume that the domain of A is Ω (K x O)-
k. and ye,1 = x, for all 1 <
A query oracle is a function that provides the observation to the agent. Formally, query oracle for a function f is map Q defined on IC such that for each x Λ., the Q(x) is random variable taking value in the observation space O. The query oracle is called a stochastic value oracle or stochastic zeroth order oracle if O R and f(x) [x Similarly, it is called stochastic up-Super- gradient oracle stochastic first order oracle if O Rd and E [(x) is up-super up-super-gradient gradient of at x. In all cases, if the random variable takes a single value with probability one, we refer to it as deterministic oracle. Note that, given function, there is most single deterministic gradient oracle, but there may be many deterministic up-super-gradicg deterministic gradient oracle. We say an oracle is bounded by B if its output is always within the Euclidean ball of radius B centered at the origin. We say the agent takes semi-bandit feedback if the oracle is first-order and the agent query function is trivial. Similarly, it takes bandit feedback if the oracle is zeroth-order and the agent query function is trivial. If the agent query function is non-trivial, then we say the agent requires full-information feedbuck.
oracles. We will use V to denote the
An adversary Adv is a set such that each element B E Adv, referred to as a realized adversary,
is sequence (B), Br) of functions where each B, maps tuple (x1.-.. .x)) Xx) E K tuple (fe, 2.) where ft E F and Qe is a query oracle for ft. We say an adversary Adv is oblivious for any realization B (B1. ........ Br all functions B, are constant, i.e., they are independent of (x,,.., x.). In this case, a realized adversary may be simply represented by a sequence of func- tions (fi.... fr) E F" and sequence of query oracles (Q1," QT) for these functions. We say an adversary is a weakly adaptive adversary if each function B, described above does not depend on x, and therefore may be represented as map defined on Kt-1 In this work we also consider adver- saries that are fully adaptive, i.e., adversaries with no restriction. Clearly any oblivious adversary is a weakly adaptive adversary and any weakly adaptive adversary is a fully adaptive adversary. Given a function class F and i {0, 1). we use (F) to denote the of all possible realized adver- saries with deterministic i-th order oracles. If the oracle is instead stochastic and bounded by B, we use Adv; (F, B) to denote such an adversary. Finally, we use Adv; (F) and Adv B) to denote all oblivious realized adversaries with i-th order deterministic and stochastic oracles, respectively.
In order to handle different notions of regret with the same approach, for an agent A, adversary Adv, compact l C KT, approximation coefficient 0 < S 1 and S S T, we define regret as
R...av (1)
sup E BE
max u=(u EEU f(()) - Σ fe(xs)
where the expectation in the definition of the regret is over the randomness of the algorithm and the query oracle. We use the notation RA (u,,s(()a,, ba == Ag (a) b] when Adv = {B} is a singleton. We may drop a when equal to 1. When a < 1, we often assume that the functions are non-negative.
Static adversarial regret or simply adversarial regret corresponds to a b= and U KT (xx...,,x) x E KJ. When a 1, b T and U contains only a single element then it is referred to as the dynamic regret [5] 43). Adaptive regret, is defined as maxiçasiST R-A (K.)) Ja 6]
23 We drop a, b and U/ when the statement is independent of their value or their value is clear
from the context.
C Proof of Theorem
I
The proof is similar to the proof of Theorems and 5 in (34)
Proof.
Deterministic oracle:
'This is a slight generalization of the common use of the term bandit feedback. Usually, bandit feedback refers to the case where the oracle is deterministic zeroth-order oracle and the agent query function is trivial.
17

---

We first consider the case where G is a deterministic query oracle for g. Let or = g(fe, x1) denote the output of g at time-step t. For any realization B = (B,, Bi(x),,". Xx) to be the tuple (gt, V) where
Adv we define
(11, (X x.)
qi y (o,, x1) 1 2 ly x x1
and (Bi,.... B)), Note that each Bi is a deterministic function of x.,... X2 and therefore B' E (Fv Since the algorithm uses semi-bandit feedback, the sequence of random vectors (X1,... .x)) chosen by A is identical between the game with B and B'. Therefore, according to definition of quadratizable functions, for any E K. we have
- ((lly))((xxx))) = (1OL.) - x1) 2 fly xell²) 2 al((y) - fi(h(x))),
B
Therefore, have
h
h
h Σ (u,) - Σ (x(x)))
b
max ueZ/
a
Σ f((u.)
> s(((xx)))
3 max uell
(4)
t=a
t=
1=a
t=
Hence
RA' Rd (F))
RAA
sup
BEAdv (F)
fe(u.) Σ Enonbei))
sup (EAdv((F)
E
max uell
==a
b
sup Be Ad
3 max uell
Σ ce(u)) t=a
-[a(xe))
Σ (xxxx)
t=a
< 8
sup B'EAdv p..))
R1 = BR L,dv (FF
Stochastic oracle:
Next we consider the case where 9 is a stochastic query oracle for g.
Let S2 f x.. x f2 capture all sources of randomness in the query oracles of Adv (F, B1), i... for any choice of 0 E Ω2, the query oracle deterministic. Hence for any 0 E no and realized adversary B E AF, Br), we may consider B3 as an object similar to an adversary with a deterministic oracle. However, note that B, does not satisfy the unbiasedness condition of the oracle, i.., the returned value of the oracle is not necessarily the gradient of the function at that point. Recall that B, maps a tuple (x..... x1) to a tuple of fa and a stochastic query oracle for ft. We will use Ege to denote the expectation with respect to the randomness of query oracle and [ == Ena [,,e,, xx] to denote the expectation conditioned the action of the agent and the adversary. Similarly, let Ena denote the expectation with respect to the randomness of the agent. Let o, be the random variable denoting the output of G at time-step and let
o, := Efoz Sc, xt) = a [o.] = g(f(,
Similar to the deterministic case, for any realization B (f1, ... .fr) E (F) and any 0 e Ωo, we define (x),,. "x.,"..,x... to be the pair (4t, V) where
Xx)
qt y (o., y x,) lyy 11
We also define By, : (B) ). Note that specific choice of is necessary to make sure that the function returned by By,, a deterministic function of x.. X2 and not a random variable and therefore 1% belongs to Adv[ (Q,,
18

---

Since the algorithm uses (semi-) benni-Jaaniit feedback, given a specific value of 8, the sequence of random vectors (X).-... Xy) chosen by A is identical between the game with Bi and Bgg Therefore, for any E K. we have
af((ue) - fc(h(xi)) 3 (o,, us - -xi) - H --11l1, xel1?
3 (B |r fe, u, xxi) - I|uu - xze1?
3 E (o ut -x-x xx1) 2
_ - x2112 ser x:
P
= 3 E (u:) - gx(x)) fcr xx
where the first inequality follows from the fact that fo is up-quadratizable and or g(fe, x1). Therefore we have
b
E
f(():)
Σ f((h(x)))
s BE
Σ
I2 [gc(u:) 2e (x(e))lfe
1=0
1=0
t=a
b
qe (u,) (x(()))
BE
Since oblivious, the sequence (f1, ... .r) is not affected by the randomness of query oracles or the agent. Therefore we have
RAA
Σ f(())) Σ f((((x)))
max well
max E uelf
Se(u.) Σ s((((x)))
max E ueld
(c( Σ (xx))
t=a
t=a
Σ yr (u.) - Σ 2e (x((x)) )
b
BE (
< ,E
max
tma
where the second inequality follows from Jensen's inequality. Hence we have
R.A. R.d.Av
sup (EAdv)(F,BL)
R.A R
sup BRA11 A.d
BR
sup B'EAdv( (Q,
D Proof of Lemma I
Proof. We have x V + = y. Therefore, following the definition of curvature, we have
f(xVy) f(y) 2 (1 (x(() - f(x A y)).
19

---

Since f is non non-negative, this implies that
1
(f(xVy) - ((x)) + 72 (f(xA))- ((x))
(f(y) f(x)) + v)((x)))) -
7/ ( f(x))
72
2 (f(y) - [(x)) + (1 - c- 1 --)) c- f(y) - (c+ 77 ff(x)) + (-1+ 1 ()
- s(xAy))
(5)
2 f(y) - (c+ 7 (xx)
On the other hand, according to the definition, we have
((v [(x) s 1
[(][x), x) 11 V y x1|?)
2
- ((x)))(x)))2) (V](x), x # |xx xx-
2
Therefore, using Inequality 5 and the fact that f(x ^ y) 2 O, we see that
fly) 1+ c7² f(x) - (f(x - f(x)) + 72 (f(x (f(xA))-f(s -
1
72
1
(7f(x), x vy- -x) - - vy v x112
x11 + (VI(x),
-
(Vf(x), x -2x)- H -
Vy x||²= - x -1xx1
7 (75((s).) x)
1
1 x y1p) 2
where we used x V y +x y x y and
Vx - x + || - x x1
Σ (wi- - xz1) + Σ
(x; - vi)
[w]
Σ [ wi)² = |x 1x-1l" 1
in the last equality. The claim now follows from multiply both sides by 14092-
E Proof of Lemma 2
Proof. Clearly we have F(O) 0. For any O, the integrand in the definition of F is continuous non-negative function of a that is bounded by
(=-(==1) (1 (1-e (1- (f(2 * x) f(0)) < (1 e- Milla * x|| S -- Mr||x||-
(=-1)
Therefore F is well-defined on [0, 1|d Moreover, we have
L. (e)(=-1) (1-e>) Vf(2 x V /'' (=-
f(0))dz = (1 (1- -(0))) VF(x).
"Note that we do not require the gradient Vf to be detined everywhere for this equality to hold. is sufficient for f to exist at Lebesgue almost every point on every line segment. This is satisfied when the I I-dimensional Hausdorff measure of the set fx E [0, 1 V undefined) is zero
20

---

It follows that F is differentiable everywhere and E [V * *x]] VF(x). To prove the last claim, first we note that
7 (VF(x),))
e (f
2 (V f(= x), x)dz
2 1) df(2 xx)
(2 ((=-))((2 12 x) x) Lo f(z [(z x)) derlo-1)
dz dz
f(x) f(0) L// 7)>(=-1) f(2*x)dd.
On the other hand, using monotonicity and up-concavity of f, we have
1 VF(x),))
(V)=
(V V * xx)2
707(=-1) (ʃ V (z* f(z x)) dz
2 yel(x-1) (fly) - f((z x)) dz
(1 - (-- - (1. ge s(2 x)dz
where we used J0 cr(x-1) e in the last equality. Therefore
1 (VF(x),) xx) x) (1 T) fxx f()) 2 (1-e -(x))
7
F Proof of Lemma 3
We start by extending a useful lemma from the literature. Versions of the following lemma for DR- submodular functions appeared in [2 32 and was later extended y-weakly DR-submodular functions in [36]. Here we further extend it to y-weakly up-concave functions. The proof is similar, but we include it for completeness.
Lemma 4. For any two vectors x,y E y-weakly up-concave function I have
[0, 1] and any continuously differentiable non-negative
f(x 2 (1-1111) (fx)
Proof of Lemma |f| x0. then x is the zero vector, and the lemma is trivially true. On the other hand, if x V y = y. the lemma follows from non-negativity of f. Thus, we may assume that
x= y > 0 and |x|| 30 O. We have
f(x - f(y) = S'' df +r-z)
dt= 1.' (z, Vfll + t z))
dr ///1xll
= ||x||>00
V + ||x||00 t' 2))dt'
~1/1xxl|x
> ||x||100
(z, f + t'- 22))d'',
(6)
21

---

where (6) holds by changing the integration variable to t' = x/||x|//>>>> and the inequality follows from y-weakly up-concavity of f, in particular because f is y-weakly concave along the line seg- ment y + 1' .z) C [0, 1].. To see that the last inclusion holds, note that, for every S i S d. if
Jy S ye. then yo + Zi yi I 1, and if x; 2 ye. then
24
T3 V1
24 |
+ 24 S +
Uss +
S 1.
|
x 00
00
Next we see that
x/
(z. Vzy +t' +z22))d =7 1/1|x|
(z. Vfl + +t' dt)
1/||x| df(y + r z)
=7 Jo
dt'
dr
1==
=7f y |1x||00 )
z
- -f(yy,
where the inequality follows from non-negativity of f. The lemma now follows by plugging this inequality into Inequality (6 and rearranging the terms.
Clearly we have F(x) = O. For any x # x, the integrand in the definition of F is a continuous function of that is bounded by
Proof of Lemma 3
2
(1(2=(x-x)
x) + - f(x))
S
2
Mi
1 2
* (x-x))
x)1 S 3 Millx x||-
8
32(1 2)3
3z
Therefore F is well-defined on [0, 119. Moreover, we have !
2 [ (x x) + d= /
3z(1 - 2)3 (xxx(xxx)++x +x) s(x) dz
3(1 33
(x()
follows that F is differentiable everywhere and E V 2 (x- + xx) = VF(x).
To prove the last claim, let x := 2/2 * (x xxxx++ + x and w(z) = 81- We have
3 (VF()).))
[ w(2) (V)(()) y)dz
/ w(2) ((V)(x)) y X Ay) (Vf(x.), Ay (V/xx) xx)) dz
[' w(x) ((V)(())), x3 Vy- - xz) + (Vf((x) X, Ay- x.) + f ) xx)) dz
/ w(z) ((f(x, vy) - f(xx)) + (f(x; y) - f(xx)) + (Vf(xx),, dz
w(2) (f(x: vy) (xx) + (V (x. xx)) dz.
"Similar to Lemma we do not require the gradient V f to be defined everywhere for this equality to hold. It is sufficient for V.f to exist at Lebesgue almost every point on every line segment. This is satisfied when the I I-dimensional Hausdorff measure of the set {x E [0, 1Jth V f undefined) is zero
22

---

Using Lemma we have
v(x+Vy)= 2 (1 - (x2
)) f(v)
IV
1 (1 (1-2)
2
|xx +
2 (1xx1/o
2)
ox + _ )) f(w)
2
z 2
(1 | ((v).
Therefore
3 (VF(x).)) 2 S/" w(z) (1-2) (1 f()) - -f(()))x))))) + (Vf(((()))))) dz. (7)
3
Next we bound (VF(x), x). We have
3 (F) L' ((x)) x,)dz + S." (x))
For the first term, we have
L (z))() -x,)dz L/¹ w(z)) ()((x), 1 2 2) (x x) dz
[ (2 =)m(z) ( (V((x), x-x
2 dz
/ (2 2))(2)df
(2- 2)w M=== L.' ((2 ((2- ((2=2)o(()) - (xx))
f(x1) 1 f(x))
1/-
1
4(1 2)3 f(xx)
which implies that
3 XVF(x), 1 f(x) L.'
4(1 - 5)3 f(xx) )d + L. (())Vf(x)xxx))
1
5x(x)) 1'' 2w((2), (xx))) + //' (()))([((xx, x.)dz
(8)
Combining Equations 7 anddn 8 we have
3 VF(())) x) > f' w(z) (11-)) (1-1xx)))))
[x|100) f(v) - 2f(xx) + (V)(())), xx) dz
-((x)) + S' 2w(z)) 2w(2){(xx)dz
S. [(=)VV((x)xx))
||x||00 f(y) //'
11-2 2
1
w(z)dz - f(x))
4
2
||x|00 f(y)= ff
x x
x
4
2
23

---

G Proof of Theorem
The algorithms are special cases of Algorithms and in [34] where the shrinking parameter and the smoothing parameter are equal. We include description of the algorithms for completion.
Algorithm 5: First order to zeroth order FOTZO(A)
Input: Shrunk domain Kss. Linear space La, smoothing parameter S horizon 7', algorithm A
Pass KJs as the domain to A
k 4- dim(Co)
for 1,2.....,T do
X; f- action chosen by Play X
Let fi be the function chosen by the adversary
for starting from while Auuiry is terminated for this time-step do
Sample Ve, E s Lo uniformly
Let yt.s be the query chosen by A
Query the oracle the point Yt.: ōv.,, to get oz,i
Pass Ve the oracle output to A
end end
Algorithm 6: Semi-bandit to bandit STB(AA)
Input: Shrunk domain K.,, Linear space Lo, smoothing parameter S r, horizon T, algorithm A
Pass Kc, as the domain to A l: dim(Co) for 1.2..... do
Sample v; E 8 n Lo uniformly f the action chosen by A
Play + 5v..
function chosen by adversary Let o, be the output of the value oracle
Let fa
Pass Socv, as oracle output to A
end
Algorithm 7: First order zeroth order with Two Point gradient estimator FOTZO-2P(A)
Input: Shrunk domain Ês, Linear space La, smoothing parameter < r, horizon T, algorithm
Pass K3s as the domain A
lo dim(Co) for 1,2..... do
X. <- the action chosen by A
Play
Let fi be the function chosen by the adversary
for starting from while Auery not terminated for this time-step do
Sample Ve,i E S! O Co uniformly
Let Yt,i be the query chosen by Aquary
Query the deterministic oracle the points yt, ov., and ye, + 8va,
Pass 28 (fr + 8v..) fe(y..- 5v.,))) the oracle output A
end end
The proof of Theorems and 6 are similar to the proof of Theorems and 8 in 34 The only difference being that we prove the result for a-regret instead of regret. We include proof for completion.
Proof of Theorem 5
Regret bound for STB:
24

---

Note that any realized adversary B E (F, Bb) may be represented as a sequence of func-
tions (fi...., fr) and a corresponding sequence of query oracles (Q). -r)) For such real- ized adversary B, we define B to be the realized adversary corresponding to . with the stochastic gradient oracles
h 2x + +vvv,
(x(x) =
(9)
where is random vector, taking its values uniformly from 3! Lo = n (aff(K) 2), for any z E K and k = dim(Co). Since 2, is a stochastic value oracle for ft. according to Remark
in 37 (x) is an unbiased estimator of V (x) S Hence we have B Advi & BBo. Using
Equation g and the definition of the Algorithm we see that the responses of the queries are the
same between the game (A, B) and (A', BB. It follows that the sequence actions (XI.-. ,X)) in (A, B) corresponds to the sequence of actions (x1 + .v .xr + ōvT) in (A',
Let E arginaxueu uell Eiza Se(us) and ú E argmax ueú Eisa Se(ue). We have
RA-
E
f(().)
fixe fi(x + ovi)
-E Σ
f((
Σ f((x))
a,
1=0
t=
[=a
t=
b
E
f((x))
fe(x; + ove) Σ t=a
+5vi)
+a
fe(ue)
Σ -E(((a)))
f(((u))
(10)
According to Lemma in (37, have ( - f(( S 8M1, By using Lipschitz property for the pair (X,, X2 + ove), we see that
fx( 8v.) fxx))) & 1f((x + ov.) f((x:)) (f((x)) fe(xx)) 25M. (11)
On the other hand, we have
f())))) max deú
fūs))
t=a
-
max ueti
f((ū,)
(Lemma 3 in 37
0
8 -c
SM,T
max uelf
fc
1 -1_
u,
(Definition of úi)
r
ut + -(c x)
SMAT
max
fi
uek
2
2 -MMI + max
Σ
[e(w))
(Lipschitz)
uell Ima
1+ 2D
8M +
fe(u.)
t=
Therefore, using Equation 10 we see that
R
R < 25MT + a (1+
2D ) SM,T < 33 SM,T.
( 2D
'When using a spherical estimator, was shown in [SS that f is differentiable even when is not. When using sliced spherical estimator we do here, differentiability of is not proved in [37. However, their proof is based on the proof for the spherical case and therefore the results carry forward to show that f is differentiable.
25

---

Therefore, we have
RA Advg(FF
Rg
sup
(EAdv
2D
sup
R +
3+
SM4T
(F,
3 2D
sup (F.
RA +
8
SM,T
2D
RA S Adv
+
3
8.
Regret bound for FOTZO:
The proof of the bounds for this case is similar to the previous case. As before, we see that the responses of the queries are the same between the game (A, and (AA', B). follows from the description of Algorithm 5 that the sequence of actions (x1,".1, ;x)) in (A, B) corresponds to the same sequence of actions in (A',1))
Let argmaxneu Eimo (u)) and ú E argmax net Σ fe(we). We have
6 f.(()r))
R - R
= E
a fe( Σ [x(x))
Eixi))
E
Σ f((x;)
f(xe)
+
Σ fe(ue) Σ E((a)))
(12)
To obtain the same bound as before, instead of Inequality 11 we have [f((x)) fx(x:)) S 5M1 25M.
The rest of the proof follows verbatim.
Proof of Theorem Note that any realized adversary E AFv may be represented as a se- For such realized adversary B, we define å to be the realized adversary corresponding to (f1, .. fr) with the stochastic gradient oracles
quence of functions
k
2x(x) 28 (f((x+ fi(x 8v)) v,
(13)
where v is random vector, taking its values uniformly from S n Lo = S n (aff z), for any z E KC and dim(Co). Since 2, is stochastic value oracle for ft, according Lemma in [37).
2x an unbiased estimator of V fxx).. Moreover, we have
A
k Mil(( 5v) (x 8v)ll < kM
fi(x 8v)) vll S (J((+
25
28
Hence we have E Adv kM1). Using Equation that the responses of the queries the same between the game (A, B3 and (B', It follows that the sequence of actions (xI....,, .x) in (A, corresponds the same sequence of actions in (A', BB.
13 and the definition of the Algorithm 5 we
Let argmax,eel nell El fu, and ú E argmax
Σb tt fl())) We have
net
R R = E
Σ fe(wx) Σ fe(xx)
E
f(( Σ ((x))
t=a
E
Σ f((x)) Σ
s(xe)
+a
Σ
fe( Σ R.(ae)
(14)
1m0
i=o
tma
t=a
26

---

According to Lemma 3 in [31, we have 1f((x)) - f((x:) - 8M1. On the other hand, we have
Σ f((ú)) = max
Σ ((.)
nell
max 2 -
fe(ū,))
(Lemma 3 in
t=a
0
-5M T
max
uEl/
Jt
r (c x)
u.
=c
(Definition of ii)
t
8
-8M
max
fe
u.
28M 1)
max -8MT
f((w))
(Lipschitz)
ued
2D
1+
8MT Σ f((u))
Therefore, using Equation 14 we see that
2D
2D
RS
RS < SMiT+a
1+
SM T S
2
8.,T.
Therefore, have
RA' Advg(F)
= sup RS (FA
2D
RA + (FA
sup
2
SM,T
r
2 2D
sup (FA
RA B
+
8M,T
r
2D
RA Adv
2
8M,T.
Corollary 4. Under the assumptions of Theorem
if we have RA
add O(B,7") and
8 = =T(o-1)/2 1)/2 then we have
R- Advg O(BTT(()))/))
Corollary 5. Under the assumptions of Theorem 6 if we have ö = T-1, then RA' Advg(())) has the same order of regret as that of A (F, with B, replaced with kM,
H Proof of Theorem 7
Proof. Given realized adversary B E (F, B){T), we may define B = (Fv (T/L) be the realized adversary constructed by averaging each T/L block of length L. Specifically, the functions chosen by B are f1," ... fr, the functions chosen by B are fg = 21 1)1.11 fc
for < S T/L. Note that, for any x E K. and (g 1)L < S qL, we have [x) = fx(x) and if each fe is differentiable at x, then [x))( = (x)... If the query oracles selected by B are -.,-.., Qr, then for any first selects an integer (g - 1)L < S 9h with uniform probability and then returns the output of O, It follows that 2, is query oracle for fg. It is clear from the description of Algorithm
g < T/L define the query oracle é, as the algorithm that
27

---

that, when the adversary is B, the output returned to the base algorithm corresponds to B. We have 1 - a a D' T. Hence
(K,)), = E R
max uoEK
f((wo)
Σ (xx)
t=a
t=a
1
E
L
Uh T.
max
Σ
fi(uo)
T.
Σ mma
t=c
81 Σ
E
L
a' max
f((wv) 1
Σ
fi(xx))
untk L
(=(a-11)4+1
(=(a-11)
|
qb
E
Σ
E
(f((E,) - f((x)) + L
a max
Σ (e(w - Σ Falle))
usEK
g=a'
111-1)411111
a=a!
q=a!
2 KM, LE
A max
Σ (uo) - - ((()
uEEK
g=a
q=
g=a
S (b' a' + 1)KMD LRA (K] (1d11")aa''
Therefore
RA
(aAAdv((F (a,
Rdy (K. (a,
sup (EA
I &iDK(B' - d' + 1) L
RA (KTT/4))) Ja', b'
sup
BEAdY (F ()TT))
MIDK(U' a + 1) + LR AI Ma' 6%).
Remark 1. Note that in the above proof, we did not need to assume that the query oracles are bounded. Specifically, what we require is that the set of query oracles be closed under convex combinations. This holds when all query oracles are bounded by B, but it also holds under many other assumptions, e.g., if we assume all query oracles variances are bounded by some o² > 0.
Corollary 6. Under the assumptions of Theorem 7 if we have RA' a, By (K. b] = O(BT"),
K = = and L = T 140-2 "
then we have
R- FF (K. [a, (a, O BT
2-9
As a special case, when K 0(1,, then we have
RAd' Adv (K)) 0 =0(BTZ))
Proof. We have
RA' ((LA (1,)), & MDK(K - d' +1) + T.R.A
A.v B. (K]
< (TD + LRA BI (k""")
= O(KT/L + +((L((T/))")
=0 COT
BT 0+000-09
28

---

I Proof of Theorem g
Proof. Since A requires 7 queries per time-step, it requires total of queries. The expected error is bounded by the regret divided by time. Hence we have 0 after T'+0 queries.
Therefore, the total number of queries keep the error bounded by O 1-))
Projection-free adaptive regret
The SO-OGD algorithm in [17 is deterministic algorithm with semi-bandit feedback, designed for online convex optimization with a deterministic gradient oracle. Here we assume that the separation oracle is deterministic.
Here the notation and K2 described in Section
Algorithm 8: Online Gradient Ascent via a Separation Oracle SD-OGA
Input: horizon T,, constraint K., step size
X1 t - R&
for f 1,2,.... T do
Play x; and observe o, fx(:)
x++1 + 1/0,
Set x++1 = S0-IPx (x(41) the output of Algorithm 9 with initial point x
end
Note that here Px denotes projection into the convex set K. The original version, which designed for minimiza- tion, uses the update rule x X₁ 7/, in Algorithm g instead.
maximization version of the algorithm, which denote by SO-OGA. Here
Algorithm 9: Infeasible Projection via a Separation Oracle SO- (yo)Px((y))
Input: Constraint set K, shrinking parameter 8 initial point y1 Pa (yo)
Y2 + c Lyy
/* y1 is projection of yo over BB(c) +/
for i = 1,2, do
Call SOx with imput y:
y; then
Set gi to he the hyperplane returned by SOx
/ Vx VX 1y:-xggi) > 0 */
g' Pa
Update Y y.
else end
10
Return y < Y:
11
12
end
Lemma 5. Algorithm 9 stops after at most (yist K&)² dist(y, R3)2)/82 iterations and returns y E KC such that vzz Ks, we have lly z|| s Ilyu z||.
Proof. We first note that this algorithm is invariant under translations. Hence it is sufficient to prove the result when c= 0.
Let SO's denote the following separation oracle. If K or y aff(K.), then SOyr returns the same output as SOx. Otherwise, it returns P Pa (g) where E IRd is the output of SOx. To prove that this indeed separation oracle, we only need to consider the case where y E aff(AC) KC. We know that g is vector such that
Vx E K.,
-y-x,8h
>
Since Pa (K)) is an orthogonal projection, we have
P (a)()) (P (Pancyyyy x). g) (y x, x, > 0.
for all x E KC, which implics that S0's is separation oracle.

---

Now we see that Algorithm iis an instance of Algorithm 6 in [17] applied to the initial point y1 using the separation oracle '. Hence we may use Lemma 13 in [T7 directly see that Algorithm stops after at most (dist(y' Ks}² (y, K&) //8² + iterations and returns E such that vz E Rs, we have lly 2|| & lly: - z|| Since y1 is the projection of over aff( we see that
Algorithm 9 stops after most
dist(y kz)² - dysttyy +1= dist K2z)² dist Rz)²
llyo -yll
82
8²
82
dist K2z) - distly, R₂)²
+
8²
steps and
Vz E Ks S aff()C)
Iyy z|| S yy z|| S
y0y z||-
In the following, we use the notation
ARA AdA
max
RA Ra, (K²) )a, b].
SeshST
to denote the adaptive regret.
Theorem 9. Let L be a class of linear linear functions over K. such that ||||| < M1 for all E L and let
D = (Kamm(C). Fix v >> O such that 5 = 1/221/2 E (0, 1) and set n) or T-1/2, Then we have 2M,
AR80-OGA (L))V( O(M.T1/3).
Proof. Since the algorithm is deterministic, according to Theorem in [34], it is sufficient to prove this regret bound against the oblivious adversary Advi(L)
Note that this algorithm is invariant under translations. Hence it is sufficient to prove the result when If aff (AC) Rd then we have (0) S K. S (0) and we may use Theorem 14 from [T7] to obtain the desired result for the oblivious adversary i On the other hand, the assumption
(0) C IC is only used in the proof of Lemma 13 in [17 Here we use Lemma instead which does not require this assumption.
The following corollary is an immediate consequence of the above theorem and Theorems and Corollaries 4
2
5 and 6
Corollary 7. Lei SO-OGA denote the algorithm described above. Then the following are true.
a) Under the assumptions of Theorem
we have:
AR S0-OGA
O(MiT13)
Ile Adv (FF
AR SD-OGA
1(BIT112),
It (F.
AR AR (S-20A))
S O(M,T2/2)
1oo7 Advg(E)
If we also assume F is bounded by Mn and Bo Mo. then
3 Adg
S ((B,78/4)
b) Under the assumptions of Theorem
we have:
ARA Add 10
AR. POTZO(A)
1-6-T,
30

---

where A = OMBQ SO- BQMO, Id). Note that A is a first order full-information algorithm that requires single query per time-step. If we also assume F is bounded by Mo and Bg 2 Mo. then
AR AR hamt-
-e - Adv (F B.) - {(B,T2/3)
AR Artliinto
Add Bb) SOBB
A AR Abandi
1-0 (FV SO(B07415)
where
Asemi-bandit SFTT(A), Atall-info-O (OTZO(A),
Abaudit SFTT -f
c) Under the assumptions of Theorem 4 we have:
AR1 (B, S {(BIT(/)
AR A) - (O(
Iu (dv
where = = OMBQ(SO-OGA, BQN, x + x Note that A is a first order full-information algorithm that requires a single query per time-step. we also assume F is bounded by Mo and Bo 2 My, then
AR Augui- b Advi
I _0(B,d//220
AR
Amiliiatoo
< (BBd 127(3/4)
1 (Fv
AR Abandic
0( / / 1h Adv
where
Asemi-bandit SFTT(A),
Atull-info = FATZO(A),, Abandit SFTT o).
K
Dynamic regret
Improved Ader (IA) algorithm is deterministic algorithm with semi-bandit feedback, designed for online convex optimization with a deterministic gradient oracle.
Algorithm 10: Improved Ader IA
Input: horizon 7', constraint set K., step size À, set H containing step sizes for experts
Activate of experts (E" 7 E H} by invoking Algorithm for each step size rj E H. S nn,, and set wit xI+IJ
Sort step sizes in ascending order 7n
where C + [
for 1.2..... do Receive x" from each expert Play the action Xx = ΣnEn w. and observe o, = (x((x))
Define ((y) = (o.. xx)
Update the weight of each expert by w
EpEn wffe (oxf
Send the gradient oz to each expert E" end
Algorithm 11: Improved Ader Expert algorithm
Input: horizon constraint K., step size 7
Let x any point in X
for = 1, ..,,. do
Send x to the main algorithm
Receive from the main algorithm x"_1 Px n7,))
end
31

---

Pxc denotes projection into the convex set K. Note that here we used the maxi- mization version of this algorithm. The original version, which is designed for minimization, uses the update rule x2+1 = Px(x" -ooo)) in Algorithm 11 instead.
In Algorithm 11
Theorem 10. Let L be class of linear functiion over K. such that ||4|| S M1 for all I E L and let
D diam(XC). Set H (n/
2
Mr V 2T sis S NJ where N = =[2 logg(1 (1 + 4T/7)1
and x = 2 D2). Then for any comparator sequence u E K", we have
RIA. (L) (u) O ((1 Pr(u)))
Proof. If we use the oblivious adversary Adv (L) instead, this theorem is simply restatement of the special case (i.e. when the functions are linear) of Theorem in [43]. Since the algorithm is deterministie, according Theorem in [34], the regret bound remains unchanged when replace Adv; (L) with (L).
The following corollary is an immediate consequence of the above theorem and Theorems and Corollaries
[nd [
Note that we do not use the meta-algorithm OTB since Improved Ader is designed for non-stationary regret and does not offer any advantages in the offline case. On the other hand, we do not use the meta-algorithm SFTT in this case since Theorem / is only for the setting where the comparator is K.?" and does not allow us to convert bounds for dynamic regret.
Corollary 8. Let IA denote "Improved Ader" described above. Then the following are true.
a) Under the assumptions of Theorem
we have:
RA
(n) =O(M, TMMIVT(1PPPpp Pr())),
Adv (F)
14zy
RIA
(u) O(8 ((BIVT(1+ Pr (r))))
1toy Adv
R FOTZO(IA)
(u) O(MI v T(1 Pr Pr(u))
1ee (Fv
we we also assume F is bounded by Mo and Bo Mo. then
R (TB(
(F. (n) O + 1/
x
b) Under the assumptions of Theorem we have:
R Ri-e-r,ddv (F, (u) O(BI v T(1 Pr(u))
R ----Y,AdvyEE (u) OMM Pr
FOTZO(IA)
where A OMBQ(IA, BQMO, Id). Note that A is a first order full-information algorithm that requires single query per time-step. If we also assume F is bounded by Mo and Bo 2 Mo, then
R Amil-inf Ri-e (F (u)
where Afull-info o = FOTZO(A).
c) Under the assumptions of Theorem 4 we have:
R1 (F,B) (u) O(BI Pr))),
R L (Fv (u)
(IA)
4 assumes that the convex set contains the origin, this assumption is not really needed. In fact, for any arbitrary convex set, we may first translate it to contain the origin, apply Theorem 4 and then translate it back obtain the results for the original convex set.
"We note that although Theorem 4 in
32

---

where A = (MAQ BQN. X + xx Note that A is first order full- infoomaffomaonnn algo- rithm that requires single query per stme.step. If we also assume F is bounded by Mo and Bg 2 Mo, then
R o o L (F
(u) - O(BoT (1+ Pr(
where Afull-info-- FOTZO(A).
33

---

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

---

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

---

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

---

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

---

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

---

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


Reviews:
[{"review_id": "OgkhgrfCq4", "reviewer": "Reviewer_VK3w", "summary": "The paper introduces a novel notion of upper linearizable / quadratizable functions. Using this notion of functions, the paper proposes a general meta algorithm that extends certain online linear / quadratic maximization algorithms to handle upper linearizable / quadratizable function classes. This general meta algorithm features multiple variants, obtaining results for different feedback settings.", "questions": "I don't have specific questions.", "limitations": "The limitations are adequately discussed.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Disclaimer: This paper is out of my expertise area. I do not have a good understanding of this paper. My review should be considered an educated guess.\n\nThe technical contribution of this paper is strong. The meta algorithm is general and leads to several theoretical results.", "weaknesses": "I find this paper hard to follow. It is largely due to my lack of familiarity with this topic, but I think the authors could do a better job with the presentation. E.g. add examples and figures, when showing theoretical results, also add some explanation and intuition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nWe will expand the explanations for each theorem to make the core ideas more clear.\nWe will also expand section 6 to include more explanations and intuition about the applications in the final version.", "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": "7UL82CZxTC", "reviewer": "Reviewer_Rpsk", "summary": "A new class of functions are introduced: upper linearizable/quadratizable functions, which extend concavity and DR-submodularity. It is shown how to apply algorithms for linear / quadratic maximization to this class, which offers a unified approach to DR-submodular optimiziation problems. The abstract framework is then applies to yield results for a broad variety of optimization settings, including online up-concave maximization with monotone functions, non-monotone, and a variety of feedback settings. Many of these settings had been studied previously in the literature, and the results obtained here either match or improve in many cases. They also convert the online results to offline ones, and apply the framework to non-stationary up-concave maximization.", "questions": "- Are there any implications for non-monotone maximization over downward closed sets?\n- The results for non-monotnoe functions don't seem to apply to gamma-weakly up-concave functions or improve with curvature. Can these results be extended to such cases?", "limitations": "Yes", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The abstraction of the class of linearizable functions unifies and improves results in many settings by making a connection with linear optimization. \n- In many cases, the results are achieved under fewer assumptions. For example, offline, monotone, maximization over a set containing the origin with access to the gradient of the function, the authors obtain the same sample complexity and approximation ratio as [18], but only require the function to be up-concave, differentiable, and Lipschitz, while [18] has more requirements, such as the function's Hessian to be Lipschitz.\n- Obtaining these results from one general framework enhances the understanding of these problems and the relationship between them\n- Figure 1 shows how to obtain various results from the theorem statements by following a directed path on a graph.", "weaknesses": "minor comments:\n- line 169: expect -> except\n- line 251: every function of F", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nWe will correct the typos in the final version.\n\nQ1. Currently, there is no result showing linearizability of non-monotone functions over downward closed sets, with a better approximation coefficient/sample complexity than that can be specialized from the results of general convex sets.\nHowever, we believe this framework to be general enough to allow for such results. \nAll we needs is to show that such functions are linearizable (i.e., something similar to Lemmas 1, 2, or 3 for non-monotone functions over downward closed convex sets) and almost all of the results that are valid for linearizable functions would follow through even in this case.\n\nQ2. Note that, in the literature, the notion of curvature or gamma-weakly DR-submodular is almost always considered in the context of monotone functions.\nIn fact, we only define curvature for monotone functions in this paper.\nIn order to properly address the question, we would need to formalize and justify appropriate definitions for gamma-weakly non-monotone functions with non-zero curvature and also generalize Lemma 3 so that it would be applied to such functions.\n\nSpecifically, for a continuous monotone function $f : \\mathcal{K} \\to \\mathbb{R}$, we define the curvature to be the smallest number $c \\in [0, 1]$ such that \n$\nf(y + z) - f(y) \\geq (1 - c) (f(x + z) - f(x)),\n$\nfor all $x, y \\in \\mathcal{K}$ and $z \\geq 0$ such that $x + z, y + z \\in \\mathcal{K}$. \nThis is already a generalization of what is commonly considered in the literature where the function $f$ is assumed to be differentiable and the curvature is defined as \n$\nc := 1 - \\inf_{x, y \\in \\mathcal{K}, 1 \\leq i \\leq d}\\{ \\frac{\\nabla_i f(y)}{\\nabla_i f(x)} \\},\n$\nwhere $\\nabla_i$ is the $i$-th component of the gradient vector.\nMoreover, the definition of curvature and $\\gamma$-weakly, in the non-monotone case, should be formulated in a way that would allow for a version of Lemma 3 to work.\nWe leave the extension of this notion for non-monotone functions and proving the variant of Lemma 3 in this case as a future work.", "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": "FhDvFKie56", "reviewer": "Reviewer_eLhz", "summary": "This paper studies online optimization with upper linearizable/quadratizable functions which are a new class of objectives considered in this field. This class extends concavity and DR-submodularity in various settings, including monotone and non-monotone cases over different types of convex sets. A general meta-algorithm is proposed which can convert linear/quadratic maximization algorithms into ones that optimize upper quadratically functions. In this way, once can solve the concave and DR-submodular optimization problems through a unified approach.", "questions": "none", "limitations": "none", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper proposes a novel framework and novel notion of quadratizable functions and relates the algorithms and regret guarantees for the optimization of linear functions to that of quadratizable functions.\n\nThis paper shows that the class of quadratizable function optimization is general, and includes not only concave, but up-concave optimization in several cases.\n\nThe authors design a new meta-algorithm, namely SFTT, that captures the idea of random permutations (sometimes referred to as blocking) as used in several papers such as [44, 46, 34]. While previous works used this idea in specific settings, the meta-algorithm is applicable in general settings.", "weaknesses": "1. The mentioned upper linearizable/quadratizable functions seem to extend the online optimization framework. It is good as a theoretical paper. Though it will be great if the authors can provide motivations for this kind of model from practial applications\n\n2. I think it will be better if the authors can provide numerical results or emperical intuitions other than the theoretical guaranttees?\n\n3. Another way to strengthen this work is providing a lower bound, or at least a discussion on it\n\n\nI am not familiar with this topic and will look at the comments by other reviewers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nW1. Our notion of linearizable/quadratizable functions generalizes both DR-submodularity and convexity. There are many applications for DR-submodular maximization. \nExample applications include experimental design [7], resource allocation [Designing smoothing functions for improved worst-case competitive ratio in online optimization - Eghbali, R. and Fazel, M. (2016)], influence maximization [Maximizing the spread of influence through a social network - Kempe et al., 2003], [Influence estimation and maximization in continuous-time diffusion networks - Gomez-Rodriguez et al., 2016] mean-field inference in probabilistic models [3], and MAP inference in determinantal point processes (DPPs) [Determinantal point processes for machine learning - Kulesza et al., 2012] as well as more recently identified applications like serving heterogeneous learners under networking constraints [Experimental design networks: A paradigm for serving heterogeneous learners under networking constraints - Li et al. 2023] and joint optimization of routing and caching in networks [Jointly optimal routing and caching\nwith bounded link capacities - Li et al., 2023].\nWe will add a section to the appendix and include some of such applications as discussed in the literature.\n\nW2. Note that our framework is so general that, as corollaries (Specifically Corollaries 7 and 8 and Theorem 8), we obtain 33 (14 + 10 + 9) algorithms covering 41 (12 + 12 + 8 + 9) cases where there is only 1 case where there exists an algorithm in the literature that (both with more assumptions and in a more limited settings) can obtain a better regret bound than our result. (There are also 3 of the results of [35], mentioned in Table 2, which require both more assumptions and also obtain worse sample complexity for $\\gamma=1$ than our result, but obtain a better approximation coefficient when $\\gamma < 1$.)This makes it a bit difficult to run experiments that cover a meaningful subset of results without adding significantly more to the paper. Given the theoretical focus of this paper, we hope that future application papers related to these 41 cases will evaluate and compare the described algorithm in their works.\n\nW3. There are several types of lower bounds one can consider. Approximation coefficient, time complexity, sample complexity, static regret, dynamic regret and adaptive regret. \nApproximation coefficients discussed in this work are either proven or conjectured to be optimal. \nFor monotone functions over convex sets containing the origin, given full-information first order feedback, it is known that $T^{1/2}$ is the optimal $(1-1/e)$-regret.\nIn general, as long as the approximation factor $\\alpha$ is optimal, we expect $\\alpha$-regret of $T^{1/2}$ to be a lower bound.\nNote that this is the first work the obtains sublinear dynamic regret or adaptive regret over DR-submodular functions.\nThe base algorithms that are used here are known to be optimal in the context of convex optimization.\nHowever, proving lower bound would require a more detailed analysis which we will leave to a future work.\nWe will write a discussion on the lower bound based on the above in the final version.", "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:

Meta-review: The paper explores the concept of linear/quadratic approximation and suggest generic templates towards using such approximations within black box regret-minimization/optimization algorithms. While this approach is quite prevalent and well investigated in convex optimization, the authors show variants of these approximations that apply to DR-submodular function --- a function class which was well studied in the past years. Through their approach the authors have been able to restore as well as improve SOTA results in various settings, which demonstrates the power of their framework.
I will therefore accept.
Decision: Accept (poster)