Universal Online Convex Optimization with $1$ Projection per Round
Authors: Wenhao Yang
Yibo Wang
Peng Zhao
Lijun Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Convex Optimization
Universal Online Learning
Projection
Primary area: online_learning

Abstract: To address the uncertainty in function types, recent progress in online convex optimization (OCO) has spurred the development of universal algorithms that simultaneously attain minimax rates for multiple types of convex functions. However, for a $T$-round online problem, state-of-the-art methods typically conduct $O(\log T)$ projections onto the domain in each round, a process potentially time-consuming with complicated feasible sets. In this paper, inspired by the black-box reduction of Cutkosky and Orabona [2018], we employ a surrogate loss defined over simpler domains to develop universal OCO algorithms that only require $1$ projection. Embracing the framework of prediction with expert advice, we maintain a set of experts for each type of functions and aggregate their predictions via a meta-algorithm. The crux of our approach lies in a uniquely designed expert-loss for strongly convex functions, stemming from an innovative decomposition of the regret into the meta-regret and the expert-regret. Our analysis sheds new light on the surrogate loss, facilitating a rigorous examination of the discrepancy between the regret of the original loss and that of the surrogate loss, and carefully controlling meta-regret under the strong convexity condition. With only $1$ projection per round, we establish optimal regret bounds for general convex, exponentially concave, and strongly convex functions simultaneously. Furthermore, we enhance the expert-loss to exploit the smoothness property, and demonstrate that our algorithm can attain small-loss regret for multiple types of convex and smooth functions.

Universal Online Convex Optimization with 1 Projection per Round
Wenhao Yang!,, Yibo Wangh Peng Zhao 12,, Lijun Zhang
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China School of Artificial Intelligence, Nanjing University, Nanjing, China {yangwh, wangyb, zhaop, changlj>@lame wju.edu..c....ee...m edu. cn
Abstract
To address the uncertainty function types, recent progress in online convex optimization (OCO) has spurred the development of universal algorithms that simultaneously attain minimax rates for multiple types of convex functions. How- ever, for a T -round online problem, state-of-the of-the-art methods typically conduct Oloog projections onto the domain in each round, a process potentially time- consuming with complicated feasible sets. In this paper, inspired by the black-box reduction of Cutkosky and Orabonal 2018). we employ a surrogate loss defined over simpler domains to develop universal OCO algorithms that only require 1 projection. Embracing the framework of prediction with expert advice, we maintain of experts for each type of functions and aggregate their predictions via a meta-algore meta-algorithm. The crux of our approach lies in a uniquely designed expert-loss for strongly convex functions, stemming from innovative decomposition of the regret into the meta-regret and the expert-regret. Our analysis sheds new light on the surrogate loss, facilitating a rigorous examination of the discrepancy between the regret of the original loss and that of the surrogate loss, and carefully controlling meta-reegre under the strong convexity condition. With only projection per round, we establish optimal regret bounds for general convex, exponentially concave, and strongly convex functions simultaneously. Furthermore, we enhance the expert-loss to exploit the smoothness property, and demonstrate that our algorithm can attain small-loss regret for multiple types of convex and smooth functions.
Introduction
Online convex optimization (OCO) stands as a pivotal online learning framework for modeling many real-world problems (Hazan 2016). OCO is commonly formulated as a repeated game between the learner and the environment with the following protocol. In each round E [T). the learner chooses decision x, from convex domain X Rd. after submitting this decision, the learner suffers loss fe(x;), where f:: X + I is convex function selected by the environment. The goal of the learner is to minimize the cumulative loss over 7' rounds, i.c., ΣT fx(x),, and the standard performance measure is the regret (Cesa-Bianchi and Lugosi 2006]:
REGT Σ fx(x))
min m(x),
[=1
1=1
which quantifies the difference between the cumulative loss of the online learner and that of the best decision chosen in hindsight.
"Lijun Zhang is the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: A summary of our universal algorithms and previous studies over 7 rounds d-dimensional functions, where LT denotes the small-loss quantity. Abbreviations: cvx - convex, exp-concave >> exponentially concave, str-cvx + strongly convex, # PROJ + number of projections per round.
Regret Bounds
Assumption
Method
# PROJ
Cvx
exp-coneave
str-evx
van Erven and Koolen
2016
((VT)
Od T)
O
Mhammedi et 2019
O(VT)
O(d
Od T)
Wang et al.
2019
O(VT)
O(d
O(og T)
O
Zhang al.
2022
O(vT)
O(dlog
O(log T)
Ollog T)
Theorem of this work
O(VT)
Oo
O T)
Wang et al.
2020b
O(vIT)
Oldlog Lr)
Olog Lr)
Ollo T)
fi(+) is smooth
Zhang ct al. [2022
O(vI,)
Old Lr)
Olog Lr)
Ollo T)
Theorem of this work
O(VLT)
Od LT)
Oloo LT)
Although there are plenty of algorithms to minimize the regret of convex functions, including general convex, exponentially concave (abbr. exp- exp-concave) and strongly convex functions [Zinkevich] 2003 Shalev-Shwartz al. 2007 Hazan et al. [007]. most of them can only handle one specific function type, and need to estimate the moduli of strong convexity and exp-concavity. The demand for prior knowledge motivates the development of universal algorithms for OCO, which aim to attain minimax optimal regret guarantees for multiple types of convex functions simultaneously [Bartlett et al. 2008 van Erven and Koolen| 2016 Wang et al. 2019 Mhammedi et al., [019 (Zhang et al. 2022]. State-of-the-art methods typically adopt two two-layer structure following the prediction with
expert advice (PEA) framework [Cesa-Bianchi and Lugosi| 2006). Specifically, they maintain Olog 7') expert-algorithms with different configurations to handle the uncertainty of functions and deploy a meta-algorithm to track the best one. While this two-layer framework has demonstrated effectiveness in endowing algorithms with universality, it raises concerns regarding the computational efficiency. Since each exper-aagoorihh needs to execute one projection onto the feasible domain X per round, standard universal algorithms perform Olog I') projections in each round, which can be time-consuming in practical scenarios particularly when projecting onto complicated domains.
In the literature, there indeed exists an effort to reduce the number of projections required by universal algorithms tailored for exp-concave functions (Mhammedi et al. 2019]. This is achieved by applying the black-box reduction of Cutkosky and Orabona| [2018). which reduces an OCO problem on the original (but can be complicated) feasible domain more manageable one on a simpler domain, such as an Euclidean ball. Deploying an existing universal algorithm vvan Erven and Koolen 2016) on the reduced problem enables us to attain optimal regret for exp-concave functions, crucially, with only one single projection per round and no prior knowledge of exp-concavity required. However, this black-box approach cannot be extended to strongly convex functions (see Section 3.1 for technical discussions). Therefore, it is still unclear on how to reduce the number of projections of universal algorithms to 1, and at the same time ensure optimal regret for strongly convex functions (as well as general convex and exp-concave functions).
In this paper, we affirmatively solve the above question by introducing an efficient universal OCO algorithm. Our solution employs the black-box reduction Cutkosky 2220 to cast the original problem on the constrained domain X' an alternative one in terms of the surrogate loss simpler domain y 2 X. Specifically, we construct multiple experts updated in domain V, each optimizing a expert-loss specialized for distinct function type. Then, we combine their predictions by a meta- algorithm, and perform the only projection onto the feasible domain X'. The meta- meta-algorithm chooses the linearized surrogate loss to measure the performance of experts, and is required to yield second- order regret [Zhang et al.) 2022]. The key novelty of our algorithm lies in the uniquely designed expert-loss for strongly convex functions, which is motivated by an innovative decomposition of the regret into the meta-regret and the expert-regret. To effectively deal with strongly convex functions, we explore the domain-converting surrogute loss depth and illuminate its refined properties. Our new insights tighten the regret gap in terms of original loss and surrogate loss, and further exploit strong convexity to compensate the meta-regret, thus achieving the optimal regret for strongly convex functions. Section 3.2 provides a formal description of our key ideas. With only 1 projection

---

per round, our algorithm attains O(VT), O logT), and O log regret for general convex, a-exp-concave, and X-strongly convex functions, respectively.
We further establish small-loss regref for universal OCO with smooth functions. The small-loss quantity L1 = minxex Σi=1 fi( is defined as the cumulative loss of the best decision chosen from the domain X, which most O(T) under standard OCO assumptions and meanwhile can be much smaller in benign environments. To achieve small-lost regret bounds, we design an enhanced expert-loss for smooth and strongly convex functions and integrate it into our two-layer framework, which finally leads universal OCO algorithm achieving O(VLT), O log LT). and O(² log LT) small-loss regret for three types of convex fiunctions, respectively. Notably, all those bounds are optimal and the algorithm only requires one projection per iteration. We summarize our results and compare with previous studies of universal algorithms in Table
Organization. The rest of the paper organized as follows. Section presents the preliminaries and reviews several mostly related works. DactionBiillminnee the technical challenges and describes our key ideas. Section provides the overall algorithms and regret analysis. We finally conelude the paper in Section 5 All the proofs and omitted details are deferred to appendices.
2 Preliminaries and related works
In this section, we first present preliminaries for OCO, and then review several most related works to paper, including universal algorithms and projection-efficient algorithms.
2.1 Preliminaries
We introduce two typical assumptions of online convex optimization (Hazan 2016
Assumption (bounded domain) The feasible domain X C Rdd contains the origin O, and the diameter is bounded by D, i.e., ||x - yll D holds for any x, y X.
Assumption (bounded gradient norms) The norm of the gradients of all online functions over the domain X is bounded by G, i.e., (x))l S G holds for all x E X and E [T].
Throughout the paper we use || for lg noom in default. Owing to Assumption I we can always construct Euclidean ball [x [ D} containing the original feasible domain X.
Next, we state definitions of strong convexity and exp-concavity Hazan 2016), and introduce an important property of exp-concave functions [Hazan et al.) 2007
Lemma
3].
Definition (strongly convex functions) A function f X + R is called X-strongly convex, if the condition f(y) 2 fxx (Vʃ(x), -x) + E lly x|12 holds for all x, E X.
Definition 2 (exponentially-concaae functions) A function X TR is called a-exponentially- concave, if the function exp(-af()) is concave over the feasible domain X.
Lemma For an t-exp-concave function f + R. if the feasible domain X has diameter D and [x)]] G holds for Vx E X, then have
8
f(y) 2 [xx (VI(x), - x) ( xx)² -xx²
for all x,y E X, where = min a.. a).
There are many efforts devoted minimizing regret, including general convex, a-exp-coneave, and X-strongly convex functions. For general convex functions, online gradient descent (OGD) with step size = O(1/vt) attains an O(vT) regret [Zinkevich 2003 For a-exp-coneave functions, online Newton step (ONS) is equipped with an O log 7') regret HHzaan et al. 2007 For X-strongly convex functions, OGD with step size 7/t (11/(A]), achieves an O log T") regret [Shalev. Shwartz et al. 2007]. These regret bounds are proved to minimax optimal (Ordettiih and Cover 1998 Abernethy al. 2008 Furthermore, tighter bounds are attainable when the loss functions

---

enjoy additional properties, such as smoothness [Shalev-Shwanl 2007 Luo and Schapire 2013
Srebro et al., 2010 Orabona et al., 2012 Chiang et al. [012] Yang et al. 2014, Mohri and Yang
2016
Zhang et al.
Zhao Zhao et al. 20200] | [Chen et al. 2024 and sparsity of gradients Duchi
et al.
2010
Tieleman and Hinton| 201 Mukkamala and Hein 2017 Kingma and Baj 2015 Reddi
et al.
2018
Loshchilov and Hutter 2019 Wang et 2020a We discuss small-loss regret below.
For general convex and smooth functions, Srebro et al. 2010 prove that OGD with constant step size attains an O(vL) regret bound, where L is the upper bound of LT. The limitation of their method is that it requires to know L beforehand. To address this limitation, Zhang et al. [2019] propose scale-free online gradient descent (SOGD), which algorithm [Orabona and Pál 2018). and establish an O(vLT small-loss regret bound without the prior knowledge of LT. For a-exp-concave and smooth functions, ONS attains an O log LT) small-loss regret bound (Orabona al. 2012]. For X-strongly convex and smooth functions, variant of OGD, namely SOGD, is introduced to achieve an O( log Lr) small-loss regret bound (Wang jtt al., 2020bb. Such bounds reduce to the minimax optimal bounds in the worst case, but could be much tighter when the comparator has small loss, i.e., LT is small.
special case of scale-free mirror descent
2.2 Universal algorithms
Most existing online algorithms can only handle one type of convex function and need to know the moduli of strong convexity and exp-concavity beforehand. Universal online learning aims to remove such requirements of domain knowledge. The first universal OCO algorithm is adaptive online gradient descent (AOGD) [Bartlett et al. 2008), which achieves O(VT) and O(log T) regret bounds for general convex and strongly convex functions, respectively. However, the algorithm still needs to know the modulus of strong convexity and does not support exp-concave functions.
An important milestone is the multiple eta gradient (MetaGrad) algorithm [van Erven and Koolen 2016). which adapt general convex and exp-concave functions without knowing the modulus of exp- concavity. MetaGrad constructs multiple axpert-algorihmm with various learning rates and combines their predictions by alga-tagg called Tilted Exponentially Weighted Average (TEWA). To avoid prior knowledge, each expert minimizes the expert-loss parameterized by a learning rate 1/,
(x) n (x.)). x x) n7² (V x)²
MetaGrad maintains (log T) experts to minimize 3 and attains O ((VT log 7) and O log T) regret for general convex and n-exp-concave functions, respectively. To further support strongly convex functions, Wang et al. [019 propose a new type of expert-losses defined as
4, (x) (V (x,,,, x, x) + n²²2²l|x, x||2
(4)
where G is the gradient norm upper bound, and introduce an expert-loss for general convex functions ex - (x))) x) + G22
(5)
where D is the upper bound of the diameter of X. Their algorithm, named as Maler, obtains O(VT), 2 T) and O( log T) regret for general convex, X-strongly convex functions, and a-exp-concave functions, respectively. Later, Wang et al. (020b) extend Maler by replacing G2 in 4 and 5) with f. thereby enabling their algorithm to deliver small-loss regret bounds. Under the smoothness condition, their algorithm achieves O LT), O(+ log LT) and O di log Lr) regret for general convex, X-strongly convex, and a-exp-concave functions, respectively.
MetaGrad and its variants require the carefully designed expert-losses, Zhang et al. [2022] propose a different universal strategy that avoids the construction of losses. The basic idea is to let each expert handle original functions and deploy meta- aleaa-algorttm over linearized loss. Importantly, the algorithm is required to yield a second-order regret [Gallard et al.) 2014] to exploit strong convexity and exp-concavity. By incorporating existing online algorithms as experts, their approach inherits the regret of any expert designed for strongly convex functions and exp-concave functions, and also obtains minimax optimal regret (and small-loss regret) for general convex functions.
Although state-of-the-ard universal algorithms can adapt to multiple function types, they create Ollg 7') experts per round. As result, they need to perform O(log 7') projections in each round, which can be time-consuming in practical scenarios with complicated domains. To address this limitation, aim to develop projection-efficien algorithms for universal OCO.

---

2.3 Projection-efficiet algorithms
In the studies of parameter- online learning. Cutkosky and Orabona [2018) propose a black-box reduction technique from constrained online learning to unconstrained online learning. To avoid regret degeneration, they design the domain- -oomaiincooovrttnng surrogate loss 9t : y IR defined as,
(6) where Sx(y) = yy xy is the distance function to the feasible domain X. Then, we can employ unconstrained online learning algorithm that minimizes (6) to obtain the prediction yt- and output its prediction on domain X. i.c., X2 1Lx [ycl Cutkosky and Orabona [2018 Theorem 3] have proved that the above surrogate loss satisfies (V+)l S [x)]l and
(y) = ( ( + [[Vx((x)) Sx(y)
(x)), X, x) 2 (v. - Te (x)) S 2 -
for all E [T'] and any E X. Based on this fact, we know that the regret of the unconstrained problem directly serves as an upper bound for that of the original problem, hence reducing the original problem an unconstrained surrogate problem and retaining the order of regret.
Subsequently, DinneuuuentlyCCukkkkky [2020) introduces a new surrogate loss 9: y -> IR defined as,
(x (V fx - 1 ((Vf(())) (x.)), vz) -x(y))
(8)
V.-Xx is the unit vector of the projection direction. As depicted in the following where V, ly: [x]l
lemma, this surrogate loss avoids the multiplicative constant 2 on the right-hand side of 77.
Lemma (Theorem of Cutkosky 2020) The function defined in (8) is convex, and it satisfies (V:)) & (xx)ll Furthermore, for all and all x E X, we have
(xxx), x) S g:(y,) 9x(x) I (V x).
While the black-box reduction is proposed for the constrained- to unconstrained conversion, it also facilitates the conversion to another constrained problem (i.e., ) * Fd)). This enables us to transform simpler domains such that the projection is much easier. Building on this idea, Mhammedi et al.) [2019] introduce an efficient implementation of MetaGrad [van Erven and Koolen [016]. which only conducts 1 projection onto the original domain in each round, and keeps the order of regret bounds. However, as detailed in the following section, the black-box reduction does not adequately extend strongly convex functions. We also mention that Zhao et al. 2022 recently employ the technique to non-stationary OCO with non-trin con-trivial modifications develop efficient algorithms for minimizing dynamic regret and adaptive regret. However, they focus on the convex functions and do not involve the considerations of exp-concave and strongly convex functions concerned in our paper.
OCO problem on complicated domain into another
3 Technical challenge and our key ideas
In this section, we elaborate on the technical challenges and our key ideas.
3.1 Technical challenge
As mentioned, Mhammedi et al. 2019 exploit the black-box reduction scheme of CCtkkosky and Orabona 2018 improve the projection efficiency MetaGrad van Erven and Koolen 2016]. We summarize their algorithm in Algorithm | In the following, we will demonstrate its effectiveness for exp-concave functions and explain why it fails for strongly convex functions.
Success in exp-concave functions. By applying the black-box reduction as described in Section 2.3 Mhammedi et al. (2019) utilize MetaGrad minimize the surrogate loss Tt (-) in (6) over Fuclidean ball y. The projection operations inside MetaGrad are over y and thus negligible. Notice that Algorithm demands only 1 projection onto in Step 4. According to regret bound of MetaGrad. Algorithm enjoys a second-order bound [Mhammedi et al. 2019 Theorem 10].
(1
T
T
xx) x) 5
(Vdl()).. -
dlog
Vglly)). - x)2 dlogT
(10)
5

---

Algorithm Black-box reduction for projection-efftcient MetaGrad MMhammedi et al. 2019
Construct a ball domain y {x
x - D) X
2: for t = 1 to T do
3: Receive the decision y: y from MetaGrad
4: Submit the decision X2 = [yr]
D> The only step projects onto domain X' per round.
5: Suffer the loss fr (x;, and observe the gradient fx,,
6: Construct the surrogate loss (+) as (6) and send it to MetaGrad
7:
end for
The above bound measured by surrogate loss, thus requiring further analysis that converts back to that of the original function. Since = min a0D a J. the function -8x² is strictly increasing when r E 1-,,,GD) Therefore, the property of surrogate loss De in implies
B Combining 10P with
f((x),,, - x) (V)+(x)), - x)² S (VD(y.)) - x) - vy) - x) (11)
and applying the AM-GM inequality, we obtain
Σ
(((x)) (vv(())) x)² s log
t=1
thus achieving the optimal regret based on Lemma
Failure in strongly convex functions. To handle strongly convex functions, straightforward way to use a universal algorithm that supports strongly convex functions, such as Maler (Wang et al.) 2019). , the black-box subroutine in Algorithm [ However, for strongly convex functions, the above analysis cannot be applied, and we are unable to derive a tight regret bound. Specifically, according to the theoretical guarantee of Maler (Wang al.
2019 Theorem 1], we have
T
(1 log T
(Vl(y))) - x) 5o
Σ Iy - x|| + log
(12)
From the standard black-box analysis and the definition of strong convexity, we know
T
T
s(x))
Σ f((x)
Σ
2(Vo
x) X x||
(13)
Substituting
into
13 we encounter an Ö(v ΣT lly: - x12 E ||
x| term,
which is unmanageable since ||y:
x||
2 ||x: - x||. Here, Ö(-) further omits the ploy(log T) factors.
3.2 Key ideas
To address above challenges, we introduce novel ideas in both algorithm design and regret analysis.
Algorithm design. Our algorithm is still in two-layer structure. The main contribution lies in uniquely designed expert-loss for strongly convex functions. For simplicity, we consider that the modulus of strong convexity À known for moment, and define
(f) (Vg. 1 Ily 11
(14)
where ge(-) is the surrogate loss defined in Let us compare our designed expert-loss (14) with the one when applying existing universal algorithms in a black-box manner. Suppose Maler Wang et al. 2019 is used, their expert-loss construction (4) indicates that the algorithm over domain essentially optimizes the expert-loss formulated as (up to constant factors).
> 1I -y.l-
?y (y) = (Vg. v)
y.ll
(15)
2

---

An important caveat is that our expert-loss (14 evaluates the performance of the expert (associated with strongly convex functions) based on the distance between its output y and the actual decision X E Xt as opposed to the unprojected intermediate one y: E ) in 15
In fact, this design of expert-loss (4) stems from a novel regret decomposition as explained below. First, by strong convexity of ft and the property of the domain-ccnverting surrogate loss, we have
T
T
T
A 2
T
f(()))
Σ f((x)
(v) -
X2
x||
1=1
(16)
T Σ (Va(v))) vt) + (Vlly))) - -x
T
Σ
X - x |
where ya denotes the decision of the i-th expert. The first term of the above bound is the meta-regret terms of linearized surrogate loss. Then, we reformulate the remaining two terms as follows
+ A +11xx xill?)
(g x)
X
x12 =
Σ
(Vge(ee).))
(17)
T
(Va(l))) + A + ||x - x||3)
Σ
| yill?.
2
where the expert-loss in [14 naturally arises. Combining 16) with 17
arrive
A
f(x.)) Σ f((x S
(y)) (x))
(Valyy)) vt)
|
y/1
t=1
axpart-ragret
nota-ragret
(18)
Theoretical analysis. For the expert-regret, since expert-loss (4) is X-strongly convex and its gradients are bounded (see Lemma 6), we can use OGD to achieve an optimal O log regret. Following Zhang et al. 2022). we require the meta-algorithm to yield a second-order regret bound
(1
(
Σ v - So (
Σ
-
(19)
Notably, the upper bound (19) and the negative term in (8) cannot be canceled due to the dismatch between y, -y¹ and x4 - yi. To resolve this discrepancy, we demonstrate that the surrogate loss defined in enjoys the following two important improved properties.
Lemma 3 In addition to enjoying all the properties outlined in Lemma the surrogate loss function 9e : y + defined in (8) satisfies
(V(((x)) Xt x) < (Vgr(y:). (17(())))))) (V)(())) -xx),
(20)
for all t and all x E X. Furthermore, we also have
(V y1) 0, when (V v.) < O,
(21)
(Vg. - yt) S 0, otherwise.
Remark We highlight the improvements of Lemma 3 over Lemma First, we provide tighter
connection between the linearized original function and the surrogate loss in (0)). Second, we analyze
the difference between the actual decision x, and the intermediate decision y.. along the direction
Vy. in 21. As shown later, both of them are crucial for controlling the meta-regret.
Utilizing
20 in Lemma
we refine the decomposition
18 to establish a tighter bound
T
T Σ
16
20
fx(xx))
(x
ER(T)
(V..y.). - vi)
xx
yil
AT (22)
7

---

where (R) is the expert-regret, and Ar - Si=1 (x (x;) -x,) 2 is the negative term introduced in the surrogate loss. Compared (18). the new upper bound (22) enjoys an
-
additional negative term AT, which is essential to achieve a favorable regret bound in the analysis.
To utilize the negative quadratic term - Ei= | in (2 for compensating the second-order
bound (19), we need convert Ye to X place where comes into play. From (19) and (2I).
we prove that for any (0, 2D5
G it holds that (see Lemma 8 for details):
G2 27
Σ (Vg.(y)), - yt)
+ 2G
(V.(y.). - vi)² + Dr.
(23)
Substituting 23
into
the additional term Dr automatically canceled out, and we have
Σ f(()))
T
Σ
T
fx) ER(T) +0
G
+
7
T
Vg. -y1)² A
T
X
- will?
27
2G
2
1=1
1=1
1=1
G
(
X - y213= =0 log
$ ER(T) +0
+
27
2
2
t=1
where the final regret bound because we set y min 2D: A}.
describes two kinds of surrogate loss, as specified in (6) and (8). Indeed, they both are suitable for parameter-frre online learning [Cutkosky] 2020 and non-stationary online learning Zhao et al. 2022 However, is essential adopt the new surrogate loss in our purpose: as established in Lemma both negative terms and the mild difference between x, and are exploited in our regret analysis. By contrast, the old surrogate loss (6) lacks these advanced properties.
Remark 2 Section
2.3
Efficient algorithm for universal online convex optimization
In this section, we present our efficient algorithms for universal OCO. To reduce the cost of projections, we deploy multiple experts on a ball y = {x ||ж|| I D} enclosing domain X. After combining their decisions, project the solution in y onto X, which is the only projection onto X' per round.
4.1 Efficient algorithm for minimax universal regret
To handle unknown parameters of strong convexity and exp-concavity, we construct two finite sets, i.e., Pu and exp: to approximate their values (Zhang et al. 2022). Taking X-strongly convex functions as example, we assume the unknown modulus À is bounded by À E [1/T, 1 and set Px = [1/T,2/11 .T ... 2 /T)) where N [log, 77. In this way, for any À E [1/T, 1]. there exists A E Pso such that À < A < 2λ. Moreover, we design three types of expert-losses. For general convex functions, we construct the expert-loss as
(y) (Vary))) -
(24)
where yy(y) is defined in Since (.) is convex, we use OGD as the expert-algorithm to minimize To handle exp-concave functions, we construct the expert-loss for each â E Pexp as
B 2
en (y) (Vgi(y:),y yı) + (Va(y)) yz)²,
(25)
where 3 = minf : a}. It is easy to verify that (. is
4 concave, so we use ONS as the expert-algorithm. For strongly convex functions, we construct the expert-loss for each X E Pse as
(y) = (Va.())). - yz) 2 Ily 1
(26)
Since goc (.) X-strongly convex, we use OGD with step size T/ = 1/ as the expert-algorithm
Finally, deploy meta-algorithm to track the best expert the fly. Following Zhang al.
8

---

Algorithm 2 Efficient Algorithm for Universal OCO
I: Input: The modulus set Pse and Pexp, the expert set A 0, the number of experts
2: k <- k +-1 create expert E by running OGD with loss (24) over
3: for all ā E Pexp do
4: k + k + 1, create an expert E* by running ONS with loss
25 and parameter à over y
5: end for
6: for all X Pse do
7: k + k 1, create an expert E by rumning OGD with loss 26 and parameter À over y
8: end for
9: Add all the experts to the set: A = (E' E
EE}
for 1 to T do
11: Compute the weight pł of each expert E by
(7
Receive the decision y; from each expert E A
13:
14: Submit the decision X, = [ye] 1i=1 ply!
Aggregate all the decisions by y: = Σ
|Al
The only step projects onto domain X' per round.
15:
Suffer the loss fxx) and observe the gradient (x+)
Construct the expert-loss (.)) (-) or (t) and sent it to corresponding expert A
17: end for
2022]. we use the linearized surrogate loss to measure the performance of the experts, and choose Adapt-ML-Prot [Gaillard et al. 2014] as the algoritgo to yield second-order bound.
Our efficient algorithm for universal OCO is summarized in Algorithm 2 From Steps to 9, creates a set of experts by running multiple online algorithms over the ball ) each specialized for a distinct function type. Then, it maintains set A consisting of all experts, and the i-th expert denoted by E'. In the t-th round, it computes the weight P of each expert E' in Step 11 according to Adapt-ML-Prod. After receiving all the predictions from the experts in Step 12, aggregates them based on their weights to attain y: in Step 13. Next, it conducts the only projection onto the original domain X' obtain the actual decision x; Step 14. In Step 15, evaluates the gradient V. to construct the expert-losses in (24). (25 and (26). In Step 16, it sends the corresponding expert-loss to each expert so that can make predictions for the next round.
Finally, we elucidate how our algorithm determines the weight of the i-th expert E*. We measure the performance of expert E' by the linearized surrogate loss, i.e., = (V (ye). yı). According
to Lemma 2 we have [7 < ( y: < 2GD. Since Adapt-ML-Proo requires the loss
to fall within the range of [0, 1]. we normalize Uł to construct the meta-loss as E = ( (V (yt...;
()GG) + E [0, 1]. The loss of the meta-algorithm in the f-th round is l, Σ pifi which is a constant 1/2 due to its construction and Step 13. For each expert E*, its weight is updated by:
wi-1 w (1f (1 ni 2 -- (_1))
pt
(27)
A E 1/( (/
where mi_1 min 1 / (In (A)) E (())) In the first round, set w/ 1/|-A/.
Remark 3 While the surrogate loss in (8) involves the projection operation, our proposed meta-loss and expert-losses only access g through Vge(y.), which is given by Cutkosky 2020
Vg.yy.) (xx,) (((7))()))))))))) f((.)),v.) -v,
According to its formulation, the gradient can be directly computed from X and yt, which means no additional projections are needed. Therefore, in each round, our algorithm requires only 1 projection onto domain X.
where V. I>+ x
Due to page limit, we provide the sxpert-algorithnng as well as all the proofs, in Appendix The theoretical guarantee of Algorithm 2 is given below.
"One can verify the degenerated situations where the unknown modulus falls outside the range, which will not be concern. Formal justitications provided in Appendix

---

Theorem Under Assumptions I and Algorithm 2 attains O(vT). O log T) and O log T) regret for general convex functions, convex functions with X E [1/T,1], respectively.
junctions with E [1/T,, 1], and X-strongly
Remark 4 Similar to previous studies [Wang et al. 2019 Zhang et al. 2022), our universal algorithm also achieves the minimax optimal regret, but only requires projection.
4.2 Efficient algorithm for small-loss universal regret
Furthermore, we consider the small-lost regret for smooth and non-negative online functions. To this end, an additional assumption is required (Srebro et al. 2010].
Assumption All the online functions are non-negative, and H H-smooth over X.
To exploit the smoothness, we enhance the expert-loss for strongly convex functions in 26 as
π (x) = (Va.ly)) ye) + 2G (or(y:)) x,11?.
(28)
Since ()) is strongly convex and smooth, we use S2GGD Wang et al. 2020b as the expert-
())
algorithm. For general convex and exp-concave functions, we reuse (24 and (25) as the expert-losses,
and employ ONS [Orabona et al., 2012] and SOGD (Zhang et al. 2019] as the expert-algorithms.
The meta-algorithm remains unchanged. In this way, we obtain the following regret guarantec.
Theorem Under Assumptions and 3 the improved version of Algorithm 2 attains O(VTor (OT)), O _ log LT) and O log [r)) regret for general convex functions, a-exp-concave functions with oo [1/T, 1]. and X-strongly convex functions with X E [1/T, 11, respectively, where the small-loss quantity LT = minxex Σ f((x) is the cumulative loss of the best decision from the domain X.
Remark 5 With only 1 projection in each round, our universal algorithm is able to deliver optimal small-loss regret bounds for multiple types of convex functions simultaneously. In contrast, WWang et al. [020bb and Zhang et al. [0022 take (log 7) projections to achieve the small-loss regret.
5 Conclusion and future work
In this paper, we propose a cnjjection-efficien universal algorithm that achieves minimax optimal regret for three types of convex functions with only 1 projection per round. Furthermore, we enhance our algorithm to exploit the smoothness property and demonstrate that it attains small-loss regret for convex and smooth functions. To demonstrate the effectiveness of our proposed method, we also conduct empirical experiments, and the results are presented in Appendix E
There are several directions for future research. First, one potentially unfavorable characteristic of our work is the requirements of domain and gradient boundedness. Motivated by the recent developments in parameter-free free online learning for unbounded domains and gradients OOraoonal
2014
Orabona and Pál 2016 Cutkosky and Boahen 2016 2017 Foster et al. 2017 Luo et al. Jacobsen and Cutkosky 2022 2023), we will investigate whether our algorithms can further
2022
avoid these prior knowledge in the future. Second, in addition to the small-loss bound, another
important type of problem-dependen guarantee is the gradient- gradient-variation regret bound (Zhao et al.
2020, 2024]. which has been actively studied recently due to its profound relationship to games and
stochastic optimization. In the literature, recent studies (Yan et al. 2023] 2024 Xie et al. 2024 Wang et al.] 2024a] achieve almost-optimal gradient-variation regret in universal online learning, but also suffer high projection complexity. Therefore, it remains challenging and important to develop crojection-efficien universal algorithm with optimal gradient-variation regret guarantees. Third, to deal with changing environments, adaptive regret has been proposed to minimize the regret over every interval in various setting of online learning [Hazan and Seshadhri] 2007 Daniely et al. 2015 Wan et al. 22021a Wang et al. 2024b). Existing universal algorithms [Zhang et al. 2021 Yang et al. 2024) typically conduct (log" T) projections per round. In the future, we will investigate whether whether we can reduce the projection complexity of universal algorithms for adaptive regret.
10

---

Acknowledgments
This work was partially supported by National Science and Technology Major Project (2022ZD01 14801), NSFC (62361 146852, 621 62122037), and the Collaborative Innovation Center of Novel Software Technology and Industrialization.
References
Abernethy, P. L. Bartlett, A. Rakhlin, and Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 415 423, 2008
L.. Bartlett, E. Hazan, and A. Rakhlin. Adaptive online gradient descent. Advances in Neural Information Processing Systems 20 (NIPS), pages 65-72, 2008
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions Intelligent Systems and Technology, 2 2011.
S. Chen, Y.-. Z. W.-W. Tu, P. Zhao, and L. Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, pages 1 - 62, 2024.
C.-K. Chiang. T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and S. Zhu. Online optimization with gradual variations. Proceedings of the 25th Anmual Conference on Learning Theory (COLT), pages 1-20, 2012.
A. Cutkosky. farameter-free, dynamic, and strongly-adaptive online learning. In Proceedings the 37th International Conference on Machine Learning (ICML), pages 2250-2259, 2020.
A. Cutkosky and K. Boahen. Online learning without prior information. In Proceedings of the 30th Annual Conference on Learning Theory (COLT), pages 643-677, 2017.
A. Cutkosky and K. A. Boahen. Online convex optimization with unconstrained domains and losses. In Advances in Neural Information Processing Systems 29 (NIPS), pages 748-756 2016.
A. Cutkosky and Orabona. Black-box reductions for parameter-free online learning in Banach spaces. In Proceedings of the 31st Conference On Learning Theory (COLT), pages 1529-1529, 2018.
A. Daniely, A. Gonen, and S. Shalev-Shwarzz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference Machine Learning (ICMI.,, pages 1405-1411, 2015.
Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), pages 257-269, 2010.
D. J. Foster, Kale, M. Mohri, and K. Sridharan. Parameter- online learning via model selection. In Advances in Neural Information Processing Systems 30 (NIPS), pages 6020-6030 2017.
Gaillard, G. Stoltz, and T. van Erven. A second-order bound with excess losses. In Proceedings of the 27th Conference on Learning Theory (COLT), pages 77-196, 2014.
D. Garber and B. Kretzu. Projection-free online exp-concave optimization. In Proceedings of Thirty Sixth Conference on Learning Theory (COLT), pages 1259-1284, 2023.
E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
Hazan and Kale. Projection-free online learning. In Proceedings of the 29th International Conference Machine Learning (ICML), pages 521-528, 2012.

---

E. Hazan and E. Minasyan. Faster projection-frt free online learning. In Proceedings of Thirty Third Conference on Learning Theory (COLT), pages 1877-1893, 2020.
E. Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. Electronic Colloquium Computational Complexity, 88, 2007.
E. Hazan, Agarwal, and Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, (9(2-3):169-19)) 2007.
A. Jacobsen and A. Cutkosky. Parameter-free mirror descent. In Proceedings of 35th Conference Learning Theory (COLT), pages 4160 2022.
A. Jacobsen and A. Cutkosky, Unconstrained online learning with unbounded losses. In Proceedings of the 40th International Conference on Machine Learning (ICML). pages 14590-14630, 2023.
D. P. Kingma and Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2015.
I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations (ICLR), 2019.
H. Luo and R. E. Schapire. Achieving all with no parameters: AdaNormalHedde. In Proceedings of the 28th Conference on Learning Theory (COLT), pages 1286-1304, 2015.
H. Luo, M. Zhang, P. Zhao, and Z.-H. Zhou. Corralling a larger band of bandits: A case study on switching regret for linear bandits. In Proceedings of the 35th Conference on Learning Theory (COLT), pages 3635-3684, 2022.
Z. Mhammedi, W. M. Koolen, and T. Van Erven. Lipschitz adaptivity with multiple learning rates in online learning. Proceedings of the 32nd Conference on Learning Theory (COLT), pages 2490-2511, 2019.
M. Mohri and S. Yang. Accelerating online convex optimization via adaptive prediction. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 848-856, 2016.
M. C. Mukkamala and M. Hein. Variants of RMSProp and Adagrad with logarithmic regret bounds. In Proceedings of the 34th International Conference Machine Learning (ICML), pages 2545-2553, 2017.
F. Orabona. Simultancous model selection and optimization through parameter-free stochastic learning. In Advances in Neural Information Processing Systems 27 (NIPS), pages 1116-1124, 2014.
F. Orabona and D. Pál. Coin betting and parameter-free online learning. In Advances in Neural Information Processing Systems 29 (NIPS), pages 577-585, 2016.
F. Orabona and D. Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69, 2018.
F. Orabona, N. Cesa-Bianchi, and C. Gentile. Beyond logarithmic bounds in online learning. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 823 831, 2012.
E. Ordentlich and T. M. Cover. The cost of achieving the best portfolio in hindsight. Mathematics of Operations Research, 23(4):960-922, 1998.
D. Prokhorov. IJCNN 2001 neural network competition. Technical report, Ford Research Laboratory, 2001.
S. J. Reddi, S. Kale, and S. Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations (ICLR), 2018.
Chalev-Shwarte Online Learning: Theory, Algorithms, and Applications. PhD thesis, The Hebrew University of Jerusalem, 2007.
12

---

S. Chalev-Shwarde Y. Singer, and N. Srebro. Pegasos: primal estimated sub- sub-gradient solver for SVM. In Proceedings the 24th International Conference on Machine Learning (ICML), pages 807-814, 2007.
S. Shalev-hhhheee Shwartz, Y. Singer, N. Srebro, and A. Cotter. Pegasos: primal estimated sub- gradient solver for svm. Mathematical Programming, 127(1):3 300,, 2011.
N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low-noise and fast rates. In Advances in Neural Information Processing Systems 23 (NIPS), pages 2199-2207, 2010.
T. Tieleman and G. Hinton. Lecture 6.5-RMSProp: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, pages 26-31, 2012.
T. van Erven and W. M. Koolen. MetaGrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29 (NIPS), pages 3666-3674, 2016.
Y. Wan and L. Zhang. Projection-free online learning over strongly convex sets. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 10076-10084, 2021.
Y. Wan, W.-W. Tu, and L. Zhang. Strongly adaptive online learning over partial intervals. Science China Information Sciences, 2021a.
Y. Wan, B. Xue, and L. Zhang. Projection-free online learning in dynamic enviromments. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 10067-10075, 2021b.
Y. Wan, W.WW Tu, and L. Zhang. Online wolfe with arbitrary delays. In Advances in Neural Information Processing Systems (NeurIPS), pages 19703-19715, 2022.
G. Wang, S. Lu, and L. Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI), pages 659-668, 2019.
G. Wang, S. Lu, Q. Cheng, W.-W. Tu, and L. Zhang. SAdam: A variant of Adam for strongly convex functions. In International Conference on Learning Representations (ICLR), 2020a.
G. Wang, S. Lu, Hu, and L. Zhang. Adapting to smoothness: A more universal algorithm for online convex optimization. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 6162-6169, 2020b.
Y. Wang, Y. Wan, S. Zhang, and L. Zhang. Distributed projection-free online learning for smooth and convex losses. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 10226-10234 2023.
Y. Wang, S. Chen, W. Jiang, W. Yang, Y. Wan, and L. Zhang. Online composite optimization between stochastic and adversarial environments. Advances in Neural Information Processing Systems 37 (NeurIPS), 2024a.
Y. Wang, W. Yang, W. Jiang, S. Lu, B. Wang. H. Tang, Y. Wan, and L. Zhang. Non-stationary projection-free online learning with dynamic and adaptive regret guarantees. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 15671 115679, 2024b.
Y.-F. Xie, Zhao, and Z.-H. Zhou. Gradient-variatee variation online learning under generalized smoothness. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.
Y.-H. Yan, P. Zhao, and Z.-H. Zhou. Universal online learning with gradient variations: A multi-layer online ensemble approach. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 17682-37715. 2023.
Y.-H. Yan. P. Zhao. and Z.-H. Zhou. A simple and optimal approach for universal online learning with gradient variations. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.
T. Yang, M. Mahdavi, R. Jin, and Zhu. Regret bounded by gradual variation for online convex optimization. Machine Learning, 95:183-223, 2014.
13

---

W. Yang. W. Jiang, Y. Wang, P. Yang. Y. Hu, and L. Zhang. Small-loss adaptive regret for online convex optimization. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 56156-56195, 2024.
L. Zhang, Liu, and Z.-H. Zhou, Adaptive regret of convex and smooth functions. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 7414-7423, 2019.
L. Zhang, G. Wang, W. Tu, W. Jiang, and Z.-H. Zhou, Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 24968-24980, 2021.
L. Zhang, G. Wang, J. Yi, and T. Yang. A simple yet universal strategy for online convex optimization. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26605- 26623, 2022.
P. 7hao, Y.J. Zhang, L. Zhang, and Z.-H. Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems (NeurIPS), pages 12510-12520, 2020.
Zhao, Y.-F. Xie, L. Zhang, and Z.-H. Zhou. Efficient methods for non-stationary online learning. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 11573-11585, 2022.
Zhao, Y.J. Zhang, L. Zhang, and Z.-H. Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):: 52, 2024.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928 936, 2003.
14

---

A Algorithms for experts
In this section, we provide the detailed procedures of the expert-algorithms in our efficient algorithm.
A.1 Online gradient descent for convex functions
We use OGD Ziikeeiich, 2003] to minimize (-) in 24 for general convex functions is summarized in Algorithm
The procedure of the expert-algorithn
Algorithm 3 Expert E OGD for Convex Functions
1: Let y be any point in y
2: for t= 1 to 7 do
3: Submit y the meta-algorithm
4: Update
1 Vi41 y
Vy((y))
Vi
5: Conduct projection onto
Vi+1 Vit1
if 1 D,
vi+1
otherwise.
18
6: end for
A.2
Online newton step for exp-concave (and smooth) functions
Lemma 4 Under Assumptions 1 and 2
in 25 is
3 eepp-concave, and [y) 2G
Thus, we use ONS to minimize (-). Different from OGD, the projection of ONS onto ) cannot be achieved through a simple rescaling like Step 5 in Algorithm 3 Here, we employ an efficient implementation of ONS [Mhammedi
2019 that enhances the efficiency of its projection V. The procedure is summarized in Algorithm
Algorithm 4 Expert E:: ONS for Exp-concave (and Smooth) Functions
1: Let yi be any point in )' and Σ 3DD= Ia
2: for = 1 to T do
3: Submit yf to the meta-algorithm
4: Update
Σ+1 E, (
844 === yf 3 VC
where
( (g.()) + Va -
5: Conduct projection onto y in 29
6: end for
Lemma Let A4t1 diag((X) ke((4) and Q++1 are the matrices of eigenvalues and eigenvectors
of (E++1 Da Ia), respectively. Then, the projection onto the ball y in Step can be formulated as
F D,
yi- =
(29)
Qun (0i4) I+ A141)
D441 1411
otherwise
where she1 is the unique solution of p(x) == Ed=
2
(x+15)²
15

---

A.3 Online gradient descent for strongly convex functions
We establish the following lemma for function (.) in (4
Lemma Under Assumptions / and the loss functiin (.) in 14) is X-strongly convex, and ( & (G 2D)
Since in (26 shares the same formulation (7()) f 1 (-) also benefits from the aforemen- tioned properties, with the distinction being the substitution of À for X. Therefore, we use a variant of OGD Shalev-Shwardh et al. 2007 to minimize f (x)()). The procedure is summarized in Algorithm
Algorithm 5 Expert E OGD for Strongly Convex Functions
1: Let yí be any point in y
2: for t= 1 to T do
3: Submit yf the meta-algorithm
4: Update
1
F/41 = y2 - Ve,.5(()))
At
where
Ve Vai(y)) T(y! -x)
5:
Conduct projection onto y
Fe+1: if 18 S D. si+1
ye+1
otherwise.
6: end for
A.4 Scale-free online gradient descent for convex and smooth functions
To exploit smoothness, we use scale-free online gradient descent (SOGD) Zhang et al. 2019 to minimize (xxx()) (2).. The procedure summarized in Algorithm 6
Algorithm Expert E": Scale-free OGD for Convex and Smooth Functions
1: Let yi be any point in y
2: for = 1 to T do
3: Submit y the meta-algorithm
4: Update
Vi+1 yi 7t Vg((ye)
where
a, 0 V8 + Σ ===1 (y
5: Conduct a projection onto y
Vi+1: Stal
if if s D. otherwise
yi+1
6: end for
A.5
Smooth and strongly convex online gradient descent
Recall that to exploit smoothness, enhance the expert-loss for strongly convex functions as follows
1 (x)
(Vg.(v)). y.) + 2G (aaly:)) x11
16

---

The above expert-loss enjoys the following property.
Lemma 7 Under Assumptions
and
in 28 is
(y.)l -strongly convex, and
(x)(())) < (1 + 22)² (
Due to the modulus of strong convexity is not fixed, choose Smooth and Strongly Convex OGD (SOOGD) as the expert-algorithm [Wang al. 2020b) minimize eo (xx()) The procedure is summarized in Algorithm 7
Algorithm 7 Expert E Smooth and Strongly Convex OGD
1: Let yí be any point in y
2: for = 1 to T do
3: Submit yf the meta-algorithm
4: Update
1+1 yj
7o (y()))
where
11
a,5> 0
8 + Σ1 s=
V (y:)
5: Conduct projection onto y
V1+1:
if 1 s D, otherwise
y
=
si+1
6: end for
B
Proofs
In this section, we provide the proofs of the theorems presented in the main paper (Theorem 1 and Theorem 2) well as proofs of two important lemmas (Lemma 3 and Lemma 8)
B.1 Proof of Theorem 1
We present the exact bounds of the theoretical guarantee provided in Theorem general convex, we have
When functions are
Σ (xx))
Σ (((x) 4TGD 2
+
2TGD
+ +2D
2DD+GG+
G
VT
G
Vin|Al
[
=((VT)
where [A| 1 2|log, l" and
A 2e
r= 3 A| + In 1
(1
In( + +1))
O(log log T).
(30)
When functions a-exp-concave, we have
Σ f((x)) - f(x) 4NGD 2+ VIn (A
)+
r2
+5
8
+2V2GD) dlog
3lm
3
=0 d logT)

---

When functions are A-strongly convex, we have
G
(G 2)
Σ f((x))
f((x) 4TGD
2
log T
Vln |A|
min D. 11
À
-0(Hl0g8) Logg)
B.1.1 Analysis for general convex functions
We introduce the following decomposition for general convex functions,
Σ fx()))
E1(
(x,(x,,,,, x)
Vo -x) x)
(gecy)). -y)) (y),,, -xx
(31)
v. +
(x (x)
neta-ragret
expert-rogee
First, we start with the expert-regret. Since we are employing OGD to minimize (.)) using standard OGD analysis [Zinkevich] 2003 Theorem 1] can obtain the following upper bound
G²
2 (y+)
Σ
eax (x) S 22D² + 2
(32)
for any expert y E y and any x E X. Next, to bound the meta-regret. According to 448
have
T
Σ (V..(v)). - -y) < STGD
16G
(v - -y1)²
In [
T Vg -y1
4TGD
2+
+
/in|Al
v In A
T
S 4DGD
2+
+ Vin
Σ
[V(()))))11l - yfll
Vin |A|
2GGD
<TGD
2
VT,
Vln |A|
(33)
for all expert E A, where N is defined in (30 and the last set is due
Vy.(
ff(x G.
(34)
Finally, substituting 32 and
33 into
3 we have
2IGD [mnlA|
G²
f((())
Σ f((x) 4NG
2
+22 + G2
VT
VInlAi
1=1
B.1.2 Analysis for exp-concave functions
For a-exp-coneave functions, there exits ă' E Pexp that ā' S < 2 where â is the modulus of the i-th expert E., This inequality also indicates
8 23"
min
a*)
(35)
2
4GD
18

---

Since 2² is strictly increasing where 3- min( a0D a*} when æ (-o0, 2GD). (
implies that
3r (VI(())) x) 10022VVilee xV - x)2 (Vg.(y.). x) v. (36)
3+
2
Then, we introduce the following decomposition for a-exp-coneave functions,
T E f((x)) Σ
T
T Vf(x)), x1 - x)
8 T
f((x)
S
Σ
(xi() x - x)²
2 t=1
t=1
t=1
3r
T
(V(((x)), x -x)
(v)))))), x - x)2
2
36
(V -xx 8"
y.
(37)
T
(V.(y.). -x) -x)- 3
(Vg:(y:). - -Y) +
v. y. - x)2
T
25
pssp t,
(y:)
(x)
,,a+
2
t=1
nets-regret
expert-regret
For the expert-regret, we can use the analysis of ONS (Hazan al.
2007
Theorem 2] obtain
T
T
eop
l
(yi)
exp la
(x)
5
+ +2V2GD
dlog T
(38)
for any expert y E y and any x E X, where 3 is defined in 335 Next, we move to bound the meta-regret. According to 48
we have
r
vt) S STGD (yl)))) -
D2 D2 +
(Vr yf)
In A
1
r
Vg.(y.)) - yt? (39)
S 4DGD
In [A|
An
1
r2
3
4TGD
2 +
(V.. -y?
In [
2
In
2
for all expert E E where is defined in 30 and the last step due to Vab < + Substituting
38 and 39 into have
r2
Σ f((x))
Σ fi(x) < 4NGD
2+
+
+5
+2V2GD) dlog
In
[
2,9
In
LA|
8.
Finally, use 35 to simplify the above bound.
19

---

B.1.3 Analysis for strongly convex functions
For A-strongly convex functions, there exits X &s that X S A 2²,, where X is the modulus of the i-th expert E". Then, we introduce the following decomposition for X-strongly convex functions
(x.x T(X) Σ (V), x)
Σ Xx x||
X T
xx) -x)
|x
x|1
2
t=1
T
X+
T
(40)
(Vecy))).. - x) AT
Σ
|x - x|2
2
1=1
T
T
X T
(v.)))) - yt)
(yi)) e0 (x)
lly:
xx11²
AT
1,7.
2
t=1
neta-ragret
expert-ragre:
where AT = Ei= ()) following theoretical guarantec.
(V - x.). To bound the meta-regret, we derive the
Lemma 8 Under Assumptions annd? 2 the mela-regret of Algorithm 2
satisfies
T
T
r
Vgc(y.). - yb) s STGD +
D2
+
Vg
-y1)
In [
G
SArGD
2+
y
Vg. X -ii) + Ar
In [A]
27 In
2G
for any y (0, 2D. where AT ET ((VF)))))))))) (x()))). - xx) and is in (30)
Remark As mentioned in Section 3.2
Lemma S is pivotal delivering optimal regret for strongly
convex functions. Specifically, when the meta-algorithm enjoys second-order bound in terms of the
surrogate loss in (8. we can then convert the intermediate decision y: in the meta-regret bound to the actual one xx, the cost of adding addition positive term, as presented in the analysis in 23
Combining Lemma 8 with (40
we have
T
Σ
f((x))
f((x)
< 4TGD
2+
1
+ 17
G2
+
7 T
Σ
(Vi(v))) x -zi)
V
In |
|A|
2G
T
+ +ER(T)
llv:
1111
(41)
2 t=1
4GGD
2
1
G2
A+
Σ xx rill2 + ER(T)
Vn
[
2n |A|
2
1
G2
< <IGD
2
+ ER(T)
In A
17 |A|
where ER(T) = EL
(xf)
x-
(x)) and the last step is because we set min G.
2D X+).
Next, we bound the expert-regret SShale--Shwarrs et 201T Lemma 1]
T
(x) < (G + (D²
ER(T)
Σ
pce
(y1)
pcc 6,5
log T.
(42)
2
20

---

for any expert yi E ) and any x E N. Substituting
42 into
41
we have
T
G
(G + D)2
((xx))
- - f(() S 4GG 2+
+
log T.
Vm
A
27 In A
2X*
[=1
Finally, we use X+ <>> 2 to simplify the above bound.
B.2 Proof of Lemma
According to 8). the (sub-)gradients of 9: g+))) can be formulated as
V f (xx),
if ( vt) 2 0,
Vgr(y) = V (x()) (V)((x)), vz). x-Il-ly
(43)
if (x vı) <0.
(i) When (Vii(x)),, vi) 2 O. We have (y) (Vf((x)))) y) and Vgr(y) = (x((x)). Thus,
(Vf((x)). X2 x) (V.. x) (V)(())) xx).
(44)
By the definition of v: (y: xx,)/llly xxlle have (xx)) x1) (Vf((x)).))) and thus (V))(y)), x,) S (V..
(45)
(ii) When (Vfe(x)).vi 0. According to Lemma we obtain
(v,)x X x) < (Vge - -x).
(46)
Moreover, we derive the following equation
(Vacly)) xx) (V xx) (V (xx); vi) (Ve, xx)
1
Yt
(47)
(VI((x)) -x,) (V)((x)).) x1) yy
x,)
Ily: xt|| Yt X, 0.
X
Finally, combining (44) and 446 obtains 20 further combining (45) and 447 yields (1
B.3 Proof of Lemma
g
By the regret guarantee of Adapt-MM--Prod
[Gaillard et al.
2014 Corollary 4], we have
T Σ
T
r
(Le
1+
Σ t=1
(4 - e?)²
In |
t=1
for all expert E E A, where I' 3 In |A| definition of L, and Et we have
+
In(1 +
2c
(1 + In + 1))) O(log log 7'). By the
Σ (v. yt) STGD
r
16G2D2 Σ
v) -t)
Vnn |A|
(48)
GºG²
< 4DGD
2
+ 2y In
Σ
(VVol -
/nn [A
A
2G
1=1
for any 7 > O, where the last step uses AM-GM inequality.
Next, we handle the term (V9.())) y. 2 We will consider two cases separately.
(i) When (V.)( v.) O, we have
(V),,,)), x, yt) < (Vf((x))); yt) < [V
-fll 2GD.
(49)
As the function ((x) = x - 2, 2 is strictly increasing when æ E (-o0, G² 49 implies that
(V)((x)) -() 7 (Vf((x)) xt)² (V.. y!)
7
(xx)). - -
2G
2G
21

---

for any E (0, 1. By rearranging terms, we obtain
20 (Vgc y1)
V Vx(())), v2)²
2G
(x( - xx,) +
7
(V(((xi),, Xt - -y2
(50)
2G
( -x) 2G
7
(y)())): yt)
(ii) When (Vf((x)). 0, directly implies (y.) X, vi) (Voi -v))- Thus,
2G Vely.) vi)²
7
Vgt (yr), X -y))
(51)
2G
Combining 50 and 51 we have
2G (yr).. v ((VA)()))))))) (V xx)
20 (V xx x (52)
for any 7 E (0, ) Substituting (22 into (48) we finish the proof.
B.4 Proof of Theorem 2
The analysis similar to Theorem Also, we present the exact bounds of the theoretical guarantee provided in Theorem 2 When functions are general convex, we have
T
Σ 1=1
f((x))
Σ t=1
f((x)
2
2LD
< 4TGD
2+
+ V2D282 +4H
+ V2(D +GD++2))
Vin [Al
In |A|
)
2
+2VH
+ +V2(D+20 + +2G)
LT 4TGD
2+
+ 12228
VIn JA
V Vnn A
=O(VTT).
where |A|= + 2oog 71. r is defined in 30 and b minxex Σ fx().. When functions are a-exp-concave, we have
Σ f(()))
Σ fx(x)
2d
D T
2
< 4TGD
2+
+
log
Σ ((xx) +1
+
In |A|
2, |A|
3
2d
2.3² D2H
T
2,3 D2
< r +
log
fx(x) +
+
2D H
Hog +
B
d
d
= 0
log Lor
where i = 4TGD
2+ Vinld
+ 2m
+ 3.
When functions are X-strongly convex, we have
T
Σ fx(x))
Σ fc(x)
t=1
(G + 2D)²
8HA
T
8HA F + 2H log(2H) +
< <
log
f((x) +
21
(G + 2D
(G +
2D)
1=1
= =0 log Log LT
where -= 4IGD
2+ VnlA
+
G2G² In +1.
22

---

B.4.1 Analysis for general convex functions
We start with the meta-expert regret decomposition presented in
31
T Σ (x(x) S
T (e (y:)
s(x))
Σ
Vy.(y)). yt)
2 (x))
(53)
1=1
meta-zegret
expert-rogret
For the meta-regret, we reuse obtain
Σ Va.())) - < 4LGD
2+
(g.(y.))3lly vill
In
A
In A
2DD
S 4TGD
2+
Vgo(y.)1
VIn
A
Vn A
(54)
for all expert E E EAA, where T is defined in SOGD Zhang al. 2019 Theorem 2] to obtain
30
For the expert-regret, we can use the analysis of
2G 1+
Σ (y!)
(x) < V2D2
8 +
Vg.(y.11
D
for any expert yi y and any N. From the above formulation, have
T
(x) < V2D25 +
2 2 (DD+2G)
V9.(y:)1..
(55)
Substituting [44] and 55
into 53
we have
fx(x;)
Σ
fx(x)
t=1
1=1
T
2TD
4GG
2
2D'8+
+ +2(D+2G))
fxx:))11
VIn
|A
/mn |A|
Next, introduce the self-bounding property of smooth functions.
Lemma 9 (Lemma 3.1 Srebro et al. (0100) For an H-smooth and nonnegative function, we have fx)]l S (xH
Thus, when functions are smooth, we have
T
fx))
Σ f(()
1=1
1=1
2DD
V2(D+ 26) )
4FGD
2+
V2
(2()+2))
4H f(())).
Vn A
In A
To simplify the above inequality, we use the following lemma.
Lemma 10 (Lemma 19 of Shale--Shwarttz (007]) Let x. b.C. C. E I Then, we have x b/i c c2 +bc
S
By utilizing Lemma 10 we finish the proof.
23

---

B.4.2 Analysis for exp-coneave functions
The analysis is also similar to Theorem We start with 37
T
Σ f(()))) f((x
8 2
T
(56)
(V
Co G
(yf)
gonp (x)
y y()?
neta.regret
export-rogret
For the meta-regret, we also use under the smoothness condition
39
to bound. For the expert-regret, we can use the analysis of ONS
Orabona al. 2012 Theorem 1] to get
T
T
x
2d
log
3 fr'D2
D2
Σ
I
+1 +
2
B
16d
3-
for any expert yf E and any x E X. Next, we provide an upper bound for
||
V
cap
1,a (y:)
(x!)12
(V(()))) + V v.). 3 (y yy)) =
- 111 yell
$ (1+ (1+23 23 + Vg. Vo.
Thus, we have
Σ cap (y))
exp v
2d
log
3 D2
[V((x)))++1)
(v +1)
2
(57)
8
4d
3
Substituting 39 and
57
into 36
we have
[x(x))
f((x)
1
1
2d
3O'D 1
T
< 4TGD
2
log
[V +1
+
(58)
VIn [A|
2.3 In |A|
3
4d
3
4TGD
2+
1
r
log
3d
D2 H
Σ
T
f((x)) +1)
+
2
In
|A]
23 In
|A|
3
d
3
where the last step is due to Lemma
9 Finally, use the following lemma to simplify the bound.
Lemma (Corollary 5 of Orabona al. (0022) Let Let b, e, x > satisfy x-d S a aln(kr+c)) + db + c)).
Then, we have < a (n
B.4.3 Analysis for strongly convex functions
Recall that we construct the expert-loss for strongly convex functions follows
(x) (Vg.(v)). y.) +
2G (ally)) x,
24

---

Then, we introduce new decomposition for X-strongly convex functions
Σ
f((x))
(x,) Xt= x)
X x| |
T
X+
T
Σ
xxc - x|1
t=1
T
x-
T
(VI((x)),x -x 20
[1 -
t=1
(Vec(s)).. -x) AT
(v.()1))1 x11
2G
X-
(Voc(y)). - -
Σ
( (x-()) (x
V9e(y;) y-ll3 -A
2G
neta-regret
expert-rogret
(59)
where AT Et= (1)))))))))) incorporate with Lemma to get
(Vi((x)). - -x,).
To bound the meta-regret, we still
T
T Σ f((x) 2 [m||A]
r
f(((
Ce (x. - 250 (xx)
2 In A
For the expert-regret, derive variant of theoretical guarantee of SPGD
Lemma 12 Under Assumptions and 2 for any expert yi y and any x E X, we have
(G+2D)²
Σ
1+
log
Σ (o.(y:)11+11
2
(G + 2D
Combining the above bounds, we have
Σ f((x)) Σ fe(x)
g2G²
(G +
2D)
4HX*
Σ [((())+1
T
<4GGD
2+
+
+1+
log
2 |n||
2
(G + 2D)²
1=1
Finally, we simplify the above bound by utilizing Lemma
C Supporting Lemmas
C.1 Proof of Lemma[4 4
According to the definition of (.)()) in (55.. we have Ve
Vgrly.)
VVll.) (y y.). Thus, for all V. it holds that
t. ( (T) = Vg.ly.)Va..v..) T + 23V v.) Vo)
+ (y yy) - -x) VV
= (1+ - yi) 2
Vg((x)V
[ (2
25

---

where (2 (y) denotes the Hessian matrix of gexp (y) and the last inequality is due to and the 8
4,a (.a
definition of 3. Therefore, (-) is 4 eex--concvve Hazan 2016 Lemma 4.1]. Next, we provide the upper bound of the gradient of e, (-) as follows
25 (G 23G - G < 2G
2
16
This ends the proof.
C.2 Proof of Lemma 6
According to the definition of (7(() in 14) it holds for any x, y E X' that
> 1| yl?
(y), x- y) By Definition it can be seen that (-) is A-strongly convex. Next, we provide the upper bound of the gradient of (-) as follows
(x)
|V < (v.)). A(y xx)Il (C+2)D)* s (G + 2D)²
where the last step is due to our assumption that À E [1.
C.3 Proof of Lemma
Similar to analysis of Lemma 6 for any x, E X, we have
1xx (x) 2
1,5 (y) (V x y)
|1: y|l
2G
By Definition it is established that e 2,, is T bound the gradient of (-) as follows
Vgr(y;) 1 convex. Next, we upper
ī G
π [V - xi)
(x))
Vyr(y) +
+
G
27
X (a xil1
[VVV
-xx) G
2dD
2D [y)a))))
1+
(y:
1+
G
where the last step is due to our assumption that Ā E [1/7, 1].
C.4 Proof of Lemma 12
The analysis is similar Wang al. 2020b] Let y yi
LV Vetaaaa (y.). According to the
definition of 28 we have
X
C (x) S (Ve (y:). - x)
Tg (y: 1
x
2G
=m F/ x)
Vg:(y:))1111)) x112.
20
For the first term, can be verified that
y Fi.1.y x)
||y - x|| + (x V1+1. y xx)
=Ily? x|| || - x (y: 3/ 9141.8411 -xx x)
||y/ - x|| | - xx12 + | - -ill + (8i41 -t,y/ -x)
26

---

which implies that
1
(rr F4.1.1 x) = (1lv) x|1² 15 x||2 + +157+1+++ y(ll²).
Thus,
Ce (x - (,,e(w) -
N1
(lly) x|| - -115t11 - -1 -x
2
1
X
V see Ga
(y:))12
[Voc(s)) x||2
277
2G
Summing the above bound up over t to T, we attain
(x)
1=1
-
T
71
lly
x||
[Vgcy:))1
| V. (x)))11)
2
1/1 17-
G
21
(G + 2D)
(
$1 +
V 2 (y)ll
11+
2T
2X
(G+2D) E (y:
where the last two inequalities is due to nh = (1 + 2D/G)² + tz E (y, which is specifically set for expert-loss. Further, will use the following lemma bound the last term.
Lemma 13 (Lemma 11 of Hazan et al. (007 Let h,.., ,rr and 8 be non-negative real numbers.
Then, we have Σ 174 1745
12
S log Ei= 12+1).
This completes the proof of Lemmal 12
C.5 Proof of Lemma
The analysis similar Mhammedi al. 2019 Lemma 9]. When |5 2 D, then we need to solve the following quadratic problem:
vi+1 arg min (+ y) T) Ex+1 y). yEy
We the Lagrangian multiplier to solve the above problem
C(y. n)) (8 y) Ee+1 (F - y) + uly y- D²).
We set By
BC = 0 to attain E - V141) + py = 0, which implics
= (μIa + E141) -1 344131+1 = Q. (II + A++1) Q++1 E4t18
where x = p+ 1/ D2). Due to y y = D2, x the solution of the following problem
p(x)= (ex. Q++1 D(41)) D2
(x x
D Clarifications on bounded modulus
In this section, we explain that bounded moduli are generally acceptable in practical scenarios, which also stated in previous study [Zhang et 2022]. Taking X-strongly convex functions as an example, we assume that X E [1/T.1], 1/, since other cases that À < 1/T and À > 1 can be disregarded. (i) À < 1/T, the regret bound for strongly convex functions becomes (2T)), which cannot benefit from strong convexity. Therefore, we should treat these functions as general convex functions. (ii) If
1, X-strongly convex functions are also 1-strongly convex according to Definition | Thus, we can treat these functions as 1-strongly convex functions.
27

---

Veated teNanieed
Veatie teMaarie
Mitiiid
Begret
Regret
Roggret
Iterations
Iterutions
Iterations
(a) Exp-concave functions
(b) Strongly convex functions
(c) Convex functions
Darc
Oan
Dan
ESC
Ronning Time
Running Time
Rumninng Time
100
330
1890
1500
3000
300
1000
1500
380
330
1806
1580
2000
Iterations
Iterations
Lterations
(d) Exp-concave functions
(c) Strongly convex functions
(f) Convex functions
Figure 1; Regret (first row) and running time (second row) of different methods.
E Experiments
In this section, we conduct empirical experiments to validate the effectiveness of our proposed methods, and present the details of experiments.
Settings We conduct experiments on the ijenn1 dataset from LIBSVM Data [Chang and Lin 2011
Prokhorov 2001]. where the dimension features is d 22. We consider the following online
classification problem. In each round E [T], the online learner chooses decision x, E X. After
submitting the decision, the online learner receives a batch of data samples ((x. Di (8)
)mm which
sampled from the dataset, where x.{') is the feature vector of the i-th sample, and y/- is the corresponding label. The learner can evaluate the model by the online convex loss fr(x,) and update the decision for the next round. In our study, set T 2000, the domain diameter D 20, and the gradient norm upper bound as G /22. Following the general setup of Zhao al. 2022)) set the feasible domain to be an ellipsoid X' {x E R x Ex < Amin (E) (D/2)²J, where E is certain diagonal matrix and Amin (E) denotes its minimum eigenvalue. We remark that the cost of one projection onto X' is generally expensive since it requires solving a convex programming.
(6)
In the following, consider three types of online convex functions to simulate the unknown environment and demonstrate the universality of our method. First, for exp-concave func- tions, the online learner suffers logistic loss: f((x)) 1
m Σm log [1+esp [x+epp(-x) (6) xT (())
Second, for strongly convex functions, choose the regularized hinge loss: f((x)
1 EE max (0, y/ x =t + $ 11 Third, for general convex functions, the online learner
suffers the absolute loss: (xx) Σm xT=(() settings, we conduct the empirical studies of our method, as well as other universal algorithms the literature.
// Based the above experimental
Algorithms We compare the performance of our proposed method for minimax universal regret with existing universal algorithms, including MetaGrad [van Erven and Koolen 2016). Maler [Wang] al. 2019), efficient implementation MetaGrad [Mhammedi et al. 2019). and USC (Zhang et al. All the baselines share the same experimental setting as method.
2022
28

---

Table 2: A summary of state-of-the-art projection-free free algorithms for different types of convex functions.
Algorithm
Condition on Loss convex
Regret Bound
OFW
Hazan and Kale 2012
O(T3/4)
OSPF
Hazan and Minasyan 2020
convex and smooth
O(T2/3)
SC-OFW
Wan and Zhang 2021
strongly convex
O(T2/3)
AFP-ONS
Garber and Kretzu 2023
exp-concave and smooth
O(T2/3)
Results We repeat the experiments for five times and record the results in Figure [ We conduct the experiments on machine with single CPU (Apple MI pro) and 16GB memory. We record both regret and running time (in seconds) for all methods. As shown Figure] 1 the running time of our method is comparable to that of EffMetaGrad, yet it achieves better results for strongly convex functions. Compared to other algorithms which conduct (llog T') projections, i.c., USC, Maler, and MetaGrad, the running time of projection-efficiee method is 5 to 20 times faster, and it also attains nearly optimal regret for three types of convex functions. In conclusion, the empirical results demonstrate the effectiveness of method in achieving optimal regret guarantee and also significant enhancement in computational efficiency.
Further discussion on projection-free algorithms
In the literature, there exists class of projection-free algorithms HHazan and Kale 2012 Hazan
and Minasyan 2020 Wan and Zhang 2021 Wan et al. 2021b 2022 Wang et al. 2023 Garber and
Kretzu 2023 Therefore, is natural to whether projection free algorithms such variants of Online Frank Wolfe could be used instead of OGD and ONS to remove all projections while still being adaptive the smoothness. Here, we provide some targeted discussions on this matter.
In fact, we can choose projection-free algorithms as the expert-algorithms. However, given the current studies on projection-free algorithms, this approach will lead to deterioration of the regret bound and can not handle certain cases. As is shown in Table 2 in the literature, there are no suitable projection-free algorithms for exp-concave functions, neither for strongly convex and smooth functions. Moreover, when funcction are smooth, existing projection-free algorithms are unable to achieve problem-dependent bounds, such the small-loss bounds in this work.
Finally, we would like to highlight that although using projection- free algorithms can remove all projections, they may not achieve greater efficiency based the universal framework. Specifically, most projection-fre algorithms, such as OFW and its variants, replace the original projection operation with linear optimization step. Since the universal framework requires maintaining Ollgg 7') expert-algorithms, this approach needs to perform O(log 7) linear optimization steps per round, which be time-consuming when T is large.
29

---

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:
Our contributions and scope are clearly written in the abstract and introduction.
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the future work in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not 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-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to 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: [Yes]
30

---

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

---

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

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See the experiments in Appendix
E
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //te:r:////uis..eeeeeeeee http://........ccccccccccceeieia
Answer: [Yes]
Justification:
We have read the ethics carefully.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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: This work is mainly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 improvement in the quality of generative models could be used to
33

---

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 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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: This work is mainly theoretical.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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: [Yes]
Justification: We cite the creators of the dataset used our experiments properly.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, snperswwihcoode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
34

---

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


Reviews:
[{"review_id": "RFtqS7BKDS", "reviewer": "Reviewer_uhFC", "summary": "This paper studies universal OCO algorithms with fewer projections. Previous work either use $O(\\log T)$ projections per round, or have a sub-optimal dependence on $d$ for strongly-convex loss. This work designs a new surrogate loss to achieve tight regret for Lipschitz convex/exp-concave/strongly-convex losses simultaneously, with only 1 projection per round.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The technical contributions are solid: this paper makes a strict improvement over previous results.\n\nThe paper is very well-written, clearly introducing the challenges and the main ideas. Details of the analysis and algorithm are nicely explained.", "weaknesses": "The contribution seems somewhat incremental to me. The only improvement is a $d$ factor for strongly-convex loss. Such result is nice to know but I'm not sure how significant such it is. In addition, the technical novelty isn't significant either.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews. We will revise our paper accordingly.\n\n---\n\n**Q1:** The significance of our result.\n\n**A1:** We emphasize that the $d$-dependence is significant in online learning studies. We provide the following elaborations and will also revise the paper to highlight this significance more clearly.\n\n* For online convex optimization, knowing the minimax optimality regarding $d$ and $T$ is a fundamental question to investigate. It is well-known that for convex/exp-concave/strongly convex functions, the minimax rate is $O(\\sqrt{T})$ , $O(d\\log T)$ and $O(\\log T)$. Therefore, in universal online learning, achieving the regret bounds that match these minimax rates is also of great significance. As explicitly mentioned by the authors of MetaGrad, van Erven et al., the extra factor $d$ in the regret bound for strongly convex functions is a \"real limitation\". Our results have successfully achieved minimax optimality in terms of $d$ and $T$ through non-trivial technical ingredients.\n* Numerous studies in online learning are dedicated to improving regret bounds by reducing dependence on the $d$. For example, prior work on private OCO achieved an $\\tilde{O}(\\sqrt{dT}/\\epsilon+\\sqrt{T})$ regret bound [2], where $\\tilde{O}(\\cdot)$ hides polylog factors in $T$. In a subsequent study, this result is improved to $\\tilde{O}(d^{1/4}\\sqrt{T}/\\sqrt{\\epsilon}+\\sqrt{T})$ [3], which is a significant advancement. Other examples include improving $d$-dependence for multi-armed bandits, bandit convex optimization, etc.\n\nTherefore, we believe that the result in this paper is significant.\n\n**Reference:**\n\n[1] van Erven et al. MetaGrad: Adaptation using Multiple Learning Rates in Online Learning. JMLR, 2021. \n\n[2] Jain et al. Differentially Private Online Learning. COLT, 2012.\n\n[3] Kairouz et al. Practical and Private (Deep) Learning Without Sampling or Shuffling. ICML, 2021. \n\n---\n\n**Q2:** The significance of our technical novelty.\n\n**A2:** We would like to take this chance to emphasize our technical novelty. \n\n* **Challenge:** This work focuses on universal algorithms with $1$ projection per round. Prior work applied the black-box reduction to existing universal algorithm, i.e., MetaGrad, which achieves optimal regret for exp-concave and convex functions with $1$ projection per round. The basic idea is to cast the original problem on the constrained domain $\\mathcal{X}$ to an alternative one of the surrogate loss on a simpler domain $\\mathcal{Y}$. To handle strongly convex functions, a straightforward way is to use a universal algorithm that supports strongly convex functions, e.g., Maler, as the black-box subroutine. However, this black-box approach fails in deriving a tight regret bound for strongly convex functions, because we are unable to bound this term,\n\n$$\n\\tilde{O}\\left(\\sqrt{\\sum_{t=1}^T \\Vert y_t-x\\Vert^2}  -\\sum_{t=1}^T \\Vert x_t-x\\Vert^2\\right),\n$$\n\nwhere $y_t\\in\\mathcal{Y}$ is the fake decision on the surrogate domain, and $x_t\\in\\mathcal{X}$ is the true decision on the feasible domain. The above term is unmanageable since $\\Vert y_t-x\\Vert\\geq\\Vert x_t-x\\Vert$. To the best of our knowledge, this technical challenge is entirely new for both universal algorithms and the black-box reduction, with no prior work to draw upon.\n\n* **Analysis:** In this work, we address the above challenge in two steps. First, we introduce a novel meta-expert decomposition and, motivated by this, we specifically design a novel expert-loss. This expert-loss offers the advantage of bounding the meta-regret by the following term,\n\n$$\n\\tilde{O}\\left(\\sqrt{\\sum_{t=1}^T\\langle\\nabla g_t(y_t),y_t-y_t^i\\rangle^2}-\\sum_{t=1}^T\\Vert x_t-y_t^i\\Vert^2\\right).\n$$\n\nSecond, to bound the above difference, we dig into the properties of the surrogate loss of the black-box reduction. The technical novelty of our theoretical analysis is that the second-order bound in terms of the decision on the surrogate domain (fake decision) can be converted into the one of the decision on the feasible domain (true decision), at the cost of adding an addition positive term $\\Delta_T$ (See Lemma 7 for details), that is\n$$\n\\sum_{t=1}^T\\langle\\nabla g_t(y_t),y_t-y_t^i\\rangle^2\\leq O\\left(\\sum_{t=1}^T\\langle\\nabla g_t(y_t),x_t-y_t^i\\rangle^2\\right) +\\Delta_T,\n$$\nwhere $\\Delta_T$ is defined in our paper. Furthermore, compared to previous work on black-box reduction, we also prove a tighter connection between the original function and the surrogate loss (See Lemma 3 for details), which introduces a negative term $-\\Delta_T$ that can automatically offset the cost arising from the aforementioned conversion. By combining these two bounds, we are able to control the meta-regret under the strong convexity condition, thus ensuring that it does not affect the algorithm's optimality. Therefore, we believe that the technical novelty in our theoretical analysis is valuable for both universal algorithms and the black-box reduction.\n\n* **Applications:** Two-layer algorithms are widely adopted in modern online learning, including universal online learning studied in our paper and also non-stationary online learning. Therefore, our developed techniques can be also useful for non-stationary online learning, especially regarding strongly convex/exp-concave functions. For example,  Baby et al. [2022] propose a two-layer algorithm with optimal dynamic regret for strongly convex functions, which also suffers from $O(\\log T)$ projection complexity. By applying our technique to a strongly adaptive algorithm with a second-order bound, it is hopeful to reduce the number of projections of their method to $1$ per round.\n\nOverall, we believe that the technical novelty of our work is significant. Thanks for your comments, and we will revise the paper to further highlight the technical novelty.\n\n**References:**\n\n[4] Baby and Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. AISTATS, 2022.", "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": "Gcp4drRCNA", "reviewer": "Reviewer_aw3E", "summary": "This paper addresses the challenge of online convex optimization with unknown smoothness properties of the loss functions, which can be convex, strongly convex, or exp-concave. The authors propose an algorithm that achieves regret bounds of order $\\sqrt{T}$, $\\log T$, and $d \\log T$ respectively, while requiring only a single projection step per round on the original domain $\\mathcal{X}$. Such projections can indeed be computationally expensive. Additionally, the authors present regret bounds with improvment for small losses.\n\nMost algorithms that achieve similar adaptive regret upper bounds rely on meta-algorithms that combine experts (running ONS or OGD with surrogate losses), inspired by the MetaGrad algorithm. Typically, these algorithms necessitate $\\log(T)$ projection steps per round (one per expert), which can be computationally burdensome. Mhammedi et al. (2019) reduced this projection cost to $O(1)$ but at the expense of a $d \\log T$ regret for strongly convex losses. To overcome this, the authors introduce new surrogate losses based on a black-box reduction technique by Cutkosky et al. (2018), which simplifies the constrained optimization problem on $\\mathcal{X}$ to another domain, such as the Euclidean ball, where projections are easier.", "questions": "- The algorithm requires prior knowledge of the parameters $G$ and $T$, would simple doubling trick allow to tune these?\n- Your algorithm still requires O(1) projection steps on $\\mathcal{X}$ and O(log T) projection steps on $\\mathcal{Y}$. Do you think that projection free algorithms such as variants of Online Frank Wolfe could be used instead of OGD and ONS (up to deteriorating slightly the rate) to remove all projections (or at least the O(log T) on $\\mathcal{Y}$) while still being adaptive to the smoothness?", "limitations": "The authors have addressed the limitations.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written and offers valuable insights into the use of surrogate losses to adapt to strong convexity or exp-concavity. It may serve as a comprehensive entry point into the extensive literature on universal OCO algorithms.\n- Despite combining various existing techniques, the results are non-trivial and required solving technical challenges, especially for the strongly convex case. The authors introduce novel negative terms in the analysis to achieve their results.\n- Experiments included in the appendix demonstrate that the computational improvements can be significant.", "weaknesses": "- The theoretical improvements may appear incremental, appealing to a niche audience interested. The improvement being only in the specific case of strongly convex $\\log T$ regret with $O(1)$ projection steps. The primary high-level ideas in the algorithm and analysis are based on prior work.\n- The paper still relies on a meta-aggregation procedure, which, although theoretically effective, is not particularly elegant and maintains a per-round complexity of order $O(\\log T)$. Achieving $O(1)$ complexity per round seems however highly challenging.\n- The convex rate is actually $O(\\sqrt{T \\log\\log T})$, not $O(\\sqrt{T})$ as stated in the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews! We will revise our paper accordingly.\n\n---\n\n**Q1:** Would simple doubling trick allow to tune prior knowledge of the parameters $G$ and $T$? \n\n**A1:** In fact, the doubling trick enables our proposed algorithm to avoid the prior knowledge of $T$, at the cost of an additional $\\log T$ in the regret bound. However, this trick is inadequate for removing the requirement of the prior knowledge of $G$, as the variability in function gradients is unknown. Therefore, designing lipschitz adaptive online learning algorithms is a highly challenging task and merits further exploration in the future. \n\n---\n\n**Q2:** Your algorithm still requires $O(1)$ projection steps on $\\mathcal{X}$ and $O(\\log T)$ projection steps on $\\mathcal{Y}$. \n\n**A2:** We would like to clarify that, in contrast to the expensive projection operations onto the complicated domain, projection operations on the surrogate domain $\\mathcal{Y}$ are much cheaper and can be considered negligible. In this work, we construct a ball $\\mathcal{Y}=\\\\{x | \\Vert x\\Vert\\leq D \\\\}$ as the surrogate domain. For the OGD algorithm, the projection operation of the reduced algorithm on $\\mathcal{Y}$ can be realized by a simple rescaling, i.e., $y_t = \\hat{y}_t$ if $\\Vert \\hat{y}_t\\Vert \\leq D$; otherwise $y_t=\\hat{y}_t \\cdot \\frac{D}{\\Vert \\hat{y}_t\\Vert}$, where $\\hat{y}_t$ denotes the unprojected decision and $y_t$ denotes the decision on the ball $\\mathcal{Y}$. For the ONS algorithm, there exists an efficient implementation of ONS in the literature, where the time-consuming projection operation can be replaced by a more efficient singular value decomposition [Lemma 7, Mhammedi et al., 2019]. After combining all the experts' decisions by a meta-algorithm, we project the solution in $\\mathcal{Y}$ onto $\\mathcal{X}$, which is the only projection onto $\\mathcal{X}$ per round. \n\n---\n\n**Q3:** Do you think that projection-free algorithms such as variants of Online Frank Wolfe could be used instead of OGD and ONS to remove all projections while still being adaptive to the smoothness?\n\n**A3:** Thanks for your insightful comments! We can choose  projection-free algorithms, such as variants of Online Frank Wolfe, as the expert-algorithms. However, given the current studies on projection-free algorithms (summarized in the table below), ***this approach may suffer a deterioration of the regret bound and can not handle certain cases***. \n\nMore specifically, as is shown in the table, in the literature, there are no suitable projection-free algorithms for exp-concave functions, neither for strongly convex and smooth functions. Moreover, when functions are smooth, existing projection-free algorithms are unable to achieve problem-dependent bounds, such as the small-loss bounds in this work. \n\n|  Algorithm  |   Condition on Loss    | Regret Bound |\n| :---------: | :--------------------: | :----------: |\n|   OFW [1]   |         convex         | $O(T^{3/4})$ |\n|  OSPF [2]   |   convex and smooth    | $O(T^{2/3})$ |\n| SC-OFW [3]  |    strongly convex     | $O(T^{2/3})$ |\n| AFP-ONS [4] | exp-concave and smooth | $O(T^{2/3})$ |\n\nFinally, we would like to highlight that although using projection-free algorithms can remove all projections, they may not achieve greater efficiency based on the universal framework. Specifically, most projection-free algorithms, such as OFW and its variants, replace the original projection operation with a linear optimization step. Since the universal framework requires maintaining $O(\\log T)$ expert-algorithms, this approach needs to perform $O(\\log T)$ linear optimization steps per round, which can be time-consuming when $T$ is large.\n\n**References:**\n\n[1] Hazan and Kale. Projection-free Online Learning. ICML, 2012. \n\n[2] Hazan and Minasyan. Faster Projection-free Online Learning. COLT, 2020. \n\n[3] Wan et al. Projection-free Online Learning over Strongly Convex Sets. AAAI, 2021. \n\n[4] Garber and Kretzu. Projection-free Online Exp-concave Optimization. COLT, 2023.", "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": "9irEgEan0n", "reviewer": "Reviewer_VeB9", "summary": "This paper introduces methods for constrained OCO\nwhich automatically achieve the optimal rate without knowing\nin advance whether the losses are convex, strongly convex,\nexp-concave, or smooth, while using only 1 projection per round.\nThis is notable because the standard approach proceeds by combining\nseveral expert algorithms with a meta algorithm; in constrained settings\nthese expert algorithms require implementing a potentially expensive\nprojection. This work avoids projecting each of the expert algorithm\niterates leveraging the constrained-to-unconstrained reduction of Cutkosky 2020.", "questions": "Do you think there could possibly be a more abstract way to formalize these universal algorithms? The strange thing about these universal algorithms is that a whole new algorithm seemingly needs to be devised every time one wants to incorporate a new kind of loss (e.g. meta-grad -> mahler to handle strongly convex losses). The ideal result would more generally be a reduction which just passes the losses to each of the experts, maybe with some additional side-information, and lets them construct whatever surrogate loss they want with it. In this way there might just be one \"final\" paper on universal guarantees.", "limitations": "Yes, the paper points out in the conclusion that the bounded domain / gradient assumption is\na significant limitation that they hope to address in future work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper addresses a clear and real problem that has been left unaddressed\nby the majority of literature on this topic. The approach is a pretty straight-forward\nmodification of existing reductions, but uses them in a new and unexpected way.", "weaknesses": "The main weakness is that the paper feels poorly factored. There is\na very large number of back references to previous equations, and the paper would be\nvery hard to read in print. To actually follow the math, it's almost necessary to\nread the paper with a pdf viewer which can display pop-up previews when hovering over links.\nI think this would be remedied by better factoring the results into lemmas and propositions.\n\nAs noted, the approach is a fairly straight-forward modification of the results from\nCutkosky \\& Orabona (2018) and  Cutkosky (2020), and essentially boils down to\nnot dropping negative terms in the analysis, and then exposing matching terms\nin the regret decomposition. I think this is fine overall; these considerations\nare missing from the literature, and this is a fitting\nplace for them to enter the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews! We will revise our paper accordingly. \n\n---\n\n**Q1:** The main weakness is that the paper feels poorly factored. \n\n**A1:** We apologize for the confusion caused by the numerous references to previous equations in this paper. Due to page limit, we attempted to include all the math equations of our key ideas in this paper, which made it difficult to follow in the printed version. We promise to polishing our writing and will follow your suggestion to factor the results into lemmas and propositions. \n\n---\n\n**Q2:** Do you think there could possibly be a more abstract way to formalize these universal algorithms? \n\n**A2:** Yes, there do exist a general framework in the studies of universal online learning that allows expert-algorithms to process the original functions [Zhang et al., 2022]. We are pleased to briefly describe the basic idea of their method here. Following the two-layer structure, the regret can be decomposed to the meta-regret and the expert-regret, that is, \n$$\n\\sum_{t=1}^T f_t(x_t) -\\sum_{t=1}^T f_t(x) = \\underbrace{\\sum_{t=1}^T f_t(x_t)-\\sum_{t=1}^T f_t(u_t)}\\_{\\texttt{meta-regret}} + \\underbrace{\\sum_{t=1}^T f_t(u_t)-\\sum_{t=1}^T f_t(x)}\\_{\\texttt{expert-regret}}\n$$\nwhere $x_t$ and $u_t$ denote the output of the meta-algorithm and expert in the $t$-th round. To bound the expert-regret, we can directly use existing online algorithms as the expert-algorithms that achieve optimal regret bounds for different types of convex functions, e.g., $O(\\sqrt{T})$ and $O(\\log T)$. To control the meta-regret, their meta-algorithm employs the linearized loss, i.e., $l_t(x)=\\langle \\nabla f_t(x_t), x-x_t\\rangle$, to measure the performance of each expert. Furthermore, they also require the meta-algorithm to yield a second-order bound in terms of $l_t(\\cdot)$. In this way, the meta-regret is small for exp-concave functions and strongly convex functions, i.e., $O(\\log\\log T)$, and is also tolerable for convex functions, i.e., $O(\\sqrt{T})$. By incorporating existing online algorithms as experts, their approach inherits the regret of any expert designed for strongly convex functions and exp-concave functions, and also obtains minimax optimal regret for convex functions. We feel that this framework is close to the \"final\" paper on universal guarantees that you mentioned. \n\nWe acknowledge that our work indeed follows this universal framework. However, to address new problems, we have to make essential modifications to this framework. In this paper, we focus on reducing the projection complexity of universal online learning, and have made innovative technical contributions based on this framework. These include specially designed expert-losses for expert-algorithms that handle strongly convex functions, and novel theoretical analysis that advances universal algorithms and the black-box reduction.", "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 considers the problem of handling various function classes like convex, exp-concave and strongly convex via 1 algorithm. This sub-area called universal algorithms has been studied significantly in literature. The typical solutions are running log T experts at different learning rates. The default such solution requires log T projections,1 for each expert. This was resolved by Mhammedi et al who gave an algorithm with 1 projection. That algorithm gets the right rate for convex and exp concave but misses the right rate for strongly convex suffering an additional d factor. This is the rate that this paper improves. They do so by changing the problem to the domain of a sphere via a construction by Cutkosky and Orabona. 

The paper is pretty well written and as the reviewers point out it lays out the results and the techniques pretty well. Overall the paper makes somewhat of a niche theoretical improvement in my opinion (shared by other reviewers), which is not very surprising. However since the reviewers have given a high score to the paper I am recommending acceptance.
Decision: Accept (poster)