Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets
Authors: Taira Tsuchiya
Shinji Ito
Venue: NeurIPS 2024 poster (2024)
Keywords: online convex optimization
online linear optimization
curvature of feasible sets
strongly convex sets
uniformly convex sets
universal online learning
Primary area: online_learning
TL;DR: This study considers online convex optimization and introduces a new condition and analysis that provides fast rates by exploiting the curvature of feasible sets.

Abstract: In this work, we explore online convex optimization (OCO) and introduce a new condition and analysis that provides fast rates by exploiting the curvature of feasible sets. In online linear optimization, it is known that if the average gradient of loss functions exceeds a certain threshold, the curvature of feasible sets can be exploited by the follow-the-leader (FTL) algorithm to achieve a logarithmic regret. This study reveals that algorithms adaptive to the curvature of loss functions can also leverage the curvature of feasible sets. In particular, we first prove that if an optimal decision is on the boundary of a feasible set and the gradient of an underlying loss function is non-zero, then the algorithm achieves a regret bound of $O(\rho \log T)$ in stochastic environments. Here, $\rho > 0$ is the radius of the smallest sphere that includes the optimal decision and encloses the feasible set. Our approach, unlike existing ones, can work directly with convex loss functions, exploiting the curvature of loss functions simultaneously, and can achieve the logarithmic regret only with a local property of feasible sets. Additionally, the algorithm achieves an $O(\sqrt{T})$ regret even in adversarial environments, in which FTL suffers an $\Omega(T)$ regret, and achieves an $O(\rho \log T + \sqrt{C \rho \log T})$ regret in corrupted stochastic environments with corruption level $C$. Furthermore, by extending our analysis, we establish a matching regret upper bound of $O\Big(T^{\frac{q-2}{2(q-1)}} (\log T)^{\frac{q}{2(q-1)}}\Big)$ for $q$-uniformly convex feasible sets, where uniformly convex sets include strongly convex sets and $\ell_p$-balls for $p \in [2,\infty)$. This bound bridges the gap between the $O(\log T)$ bound for strongly convex sets~($q=2$) and the $O(\sqrt{T})$ bound for non-curved sets~($q\to\infty$).

Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets
Taira Tsuchiya The University of Tokyo and RIKEN tsuchiyadmist. u-tokyo. ac.
Shinji Ito
The University of Tokyo and RIKEN shinji@miss @mist i. 1..i..uutoon u-tuoooo.aaa jc.
Abstract
In this work, we explore online convex optimization (OCO) and introduce a new condition and analysis that provides fast rates by exploiting the curvature of fea- sible sets. In online linear optimization, it is known that if the average gradient of loss functions exceeds a certain threshold, the curvature of feasible sets can be exploited by the follow-the-leas This study reveals that algorithms adaptive to the curvature of loss functions can also leverage the curvature of feasible sets, In particular, we first prove that if an op- timal decision on the boundary of a feasible set and the gradient of an underlying loss function is non-zero, then the algorithm achieves a regret bound of O(p In T) stochastic environments. Here, P > is the radius of the smallest sphere that in- cludes the optimal decision and encloses the feasible set. Our approach, unlike ex- isting ones, can work directly with convex loss functions, exploiting the curvature of loss functions simultaneously. and can achieve the logarithmic regret only with local property of feasible sets. Additionally, the algorithm achieves O(vT) regret even in adversarial environments, in which FTL suffers an ??(T') regret, and achieves ( In + VC'pln 7') regret in corrupted stochastic environments with corruption level C. Furthermore, by extending our analysis, we establish a matching regret upper bound of 0 Ofrzt-1
(FTL) algorithm to achieve logarithmic regret.
(In गाक for q-uniformly convex feasible sets, where uniformly convex sets include strongly convex sets and lp- balls for E [2, oo). This bound bridges the gap between the T)) bound for strongly convex sets (g- = 2) and the O(VT)) bound for non-curved sets (q - oo).
Introduction
This paper considers online convex optimization (OCO), framework in which learner and an environment interact in a sequential manner. At the beginning, a convex body (or feasible set) K C Rd is given. At each round t 1, , T. the learner selects a decision I, E K from the convex body K using information obtained up to round t 1. Then, the environment determines a convex loss function fr: K + F. and the learner suffers loss fe and observes fa(e E Rd. The goal of the learner is to minimize the regret, which is the expectation of the difference between the cumulative loss of decisions (Ix) and that of single optimal decision x, fixed in hindsight, that T is, R₂ = E E (f)( - fe fe(2))) for x, = arg min k E [" +-1 fe:)]. OCO is called online linear optimization (OLO) when (fr); are linear functions, i.e., f((-) () for some 9t. Rd
In OCO and OLO, the well-known online gradient descent (OGD) achieves an O(vT) regret upper bound for Lipschitz continuous f, [27]. In general, this upper bound cannot be improved and is known match the 1?( ((VT) regret lower bound [8]. However, this lower bound can be cireumvented under certain conditions. The most typical way is to exploit the curvature of loss functions. It is known
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

Table 1: Comparison of regret upper bounds with existing bounds. All bounds assume that loss functions the boundary of K. The upper bounds that contain the variable assume l1g: + 9i ||a 2 for all t E [2]. We use f y [f]. 2 is the corruption level, and the f2 notation ignores logarithmic factors. The (r, -uunffrryy convex is x-strongly convex. Theorem abbreviated Thm, Corollary Cor, and pphere-encloseee in this study can be simultaneously achieved by the same algorithm with identical parameters.
G-Lipschitz (except Lines 1-3) and
sphere-enc. Note that regret bounds proven
Reference
Feasible set
Loss functions
Regret bound
[9]. This work (Thm 8)
ellipsoid Wa in Sec- tion 2.3.2 (A-strongly convex)
f(()) (1f Thm 6
AL In'r)
In (X
1112
1
This work (Thm 9)
corrupted
This work (Cor 12)
(.(+) (1t
ln
AL
Thm
G²p
This work (Thms 10, 14)
(p. x., J-) sphere-ene.
stochastic, convex
[ luT
G
CG
This work (Thm 13)
T. sphere-enc.
corrupted, convex
InT'
In
[V/
G In
Huang et al. [9]
X-strongly convex
adversarial, linear adversarial, linear
AL
Molinaro [17]
Gd
InT)
(d' (d'=max max [|]|=1 (u,
x
G
This work (Thm 15)
stochastic, convex
\ (x.))l ln
G T
Kerdreux et al. [11]
(k, q)- uniformly convex
adversarial, linear
(xL) --
G
This work (Thm 15)
stochastic,
(In 31
convex
that OGD with learning rate of @(1/t) and online Newton step (ONS) can achieve 0(1 In T)) and O In T) regret for a-strongly-convex and B-exp-concave loss functions, respectively [8].
Another way circumvent the lower bound is harness the curvature of the feasible K. Ex- isting studies proved that in OLO if the feasible set is curved and loss vectors are biased towards a specific direction, the follow-the-leade (FTL) algorithm can achieve a logarithmic regret. In par- ticular, Huang et al. [9] first proved that under the growth condition that there exists L > 0 such that 1/9: + ... gell2 2 tL for any [T] f1...., ... T), FTL achieves an O G2 for X-strongly convex and G-Lipschitz loss functions. This bound matches their lower bound of 2 2(xtz In T). Molinaro [17] also proves that FTL achieve logarithmic regret under the different assumption on the loss vectors that < 0 for all E [T], providing an intuitive and simple proof.
Az. In T)) regret
Their approach, however, has several remaining limitations. First, they only consider OLO. While the lincarization technique allows us to solve OCO by OLO, this may prevent us from leveraging the curvature of loss functions. Second, their analysis requires the curvature over the entire boundary of the feasible set, which a rather limited condition. Finally, some their approach suffers an Q(T') regret if the ideal conditions on loss vectors, such as the growth condition, are not satisfied. Note that we cannot know in advance whether such conditions are satisfied or not. Exceptions are the method based on the expert tracking algorithm in [9, Section 4], in which FTL is combined with follow-the wwweerrgllaizze--eeeee
and the work by Anderson and Leith [1], who investigated the online lazy gradient descent over the strongly convex sets.
To overcome these limitations, we consider using algorithms adaptive to the curvature of loss func- tions [21, 22, 24), also known universal online learning. The original motivation of this line of

---

work is to automatically achieve a regret bound that depends on the true curvature level of loss func- tions, e.g., parameters strong convexity or exp-concavity, without knowing them. The erux of their analysis is to derive a bound of E 1== (V))) - r+) =0)=0(( Olv E 1 - x- In
Contributions of this paper We introduce new condition for achieving fast rates in OCO. We first show that algorithms adaptive to the curvature of loss functions can exploit the curvature of feasible sets and overcome the three limitations mentioned earlier. We prove the following theorem:
Theorem 1 (informal version of Theorems 10 and 13). Any algorithm with Ei (V.r(zz),
S. ...) Occx Et= x. 11 In T) for some Ccc > 0 achieves R = O (Vf lnT) in stochastic environments, where f = [f) and p 0 is the smallest radius of a sphere that includes x, and encloses K. The same al algorithm achieves Ry =
in corrupted stochastic environments for corruption level C and Rr- = (VVT) in adversarial environments.
This upper bound matches an existing lower bound [9, Theorem 9], specifically when considering the environment employed to construct their lower bound. This will be formally stated in Corollary 12.
The advantage of our approach over the existing approach is that it overcomes all three limitations of the existing approach mentioned earlier. That is, (i) in contrast to existing studies, it can work with OCO without the linearization, allowing us to simultaneously exploit the curvature of feasible sets and the curvature of loss functions (see Theorem 14). (ï) Even in worst cases, where the specific conditions on loss vectors, such as the growth condition, are not satisfied. an O(VT) regret upper bound can be achieved. (ii) The local structure of K around optimal decision Fy is sufficient for our approach to achieve the logarithmic regret. As a further advantage, our approach can achieve an O(pIn T + VCpIn'T) regret bound for corrupted stochastic environments with corruption level C 2 O, which are intermediate environments between stochastic and adversarial environments (The- orem 13). We provide a regret lower bound that nearly matches this upper bound (Theorem 9).
Our approach can also be used to obtain fast rates on uniformly convex feasible sets, a broader class that includes strongly convex sets and Ep fp-balls for p E [2, 20). For q- q-uniformly convex K, Kerdreux et al. [11] proves regret bound of O ( ), which is smaller than O(VT) only when q (2, We improve this bound by proving the following upper bound, which matches the lower bound in [2]:
Theorem 2 (informal version of Theorem 15). online convex optimizatiion with q- q-uniformly convex
feasible set K, the same algoritlum as Theorem 1 achieves R1 ( [ [n अ,④
This becomes a fast rate for any q > 2 and is strictly better than the bound in [11]. Our bound interpolates between the Oln bound for strongly convex sets (when 4 2) and the O(VT) bound for non-curved feasible sets (when q oo). Table 1 summarizes the regret comparison.
Preliminaries
Let e, {0, 1]dd be the i-th standard basis of R and be the all-one vector. For p [1, oo] and vector x, let ||>||p be f--norm. Let & >> be a constant satisfying ||æ/|| S E||=||| for any x Rdd For norm ||-|]. we use ||ж||| = supl (z, y): ||vl| < 1} to denote its dual norm. Let B (x, be a ball with radius r centered at x associated with |1-11. i.e., []] B(x,r) r) to denote the Euclidean ball with radius r centered at x and B|1-1 to denote the unit ball. Let bd(K) ) be the boundary of K. A function f: Rd + (-00, oo) is convex if for all x E int dom f. f(y) 2 f(x) + (V)()) y - x) for all y E Rd For a > 0, f: - (-00, oo] is atsonngyyy convex over K C dom f w.r.t. ||-|| if for all x, y K, f(y) > f(z) + (Vf(z). x) + 2 l| yll For
{z: ||> - z|| S r). We use
0, f: K + (-o0, oo] is 3-exp-concave if (x)(-Bf(x) is concave.
For simplicity, this paper only considers the case that loss functions ft's are differentiable, but one can extend all the results to the subdifferentiable case in straightforward manner.
3

---

2.1 Online convex optimization
We consider online convex optimization (OCO). In OCO, a convex body (or feasible set) K C Rd is given before the game starts. Let D = maxx || yll2 be the diameter of K. At each round t E [T]. the learner selects a decision 2t E K using information obtained up to round - 1, and a convex loss function fr: K + IR is determined by the environment. The learner then suffers a loss f((zz) and observes f((z)) E R² The goal of the learner is to minimize the regret, which is defined as R = E| (f(z)) - (x.))) for the optimal decision I, = arg min E
E f((z))
When loss functions are restricted solely to linear functions, that is, when fe(.) = (9t, ) for some gr E R. OCO is referred to as online linear optimization (OLO).
2.2 Assumptions on loss functions
In this study, we assume that fa is G-Lipschitz, i.e., K I [( S G. In the following, we list three assumptions on how a sequence of fi...., fr is generated. In stochastic environments, ft is sampled in an i.i.d. manner from a certain probability distribution D. The expectation of ft denoted as f = E [f]] In adversarial environments, ft is arbitrarily determined depending on the past history, and fe may depend on 2t. The corrupted stochastic environment is an intermediate setting between stochastic and adversarial environments. The motivation for considering this environment is that in real-world problems, a sequence of loss functions is neither stochastic nor (fully) adversarial. In this environment, at each round E [T]. fe DD is obtained according to a certain distribution D, where the expectation of Je is defined by f = Ei Then, possibly depending on Je and the past history, loss function fe is determined by the environment so that E DΣ || - so < C, where E -
E
T Il f is the corruption level. In this paper, we consider these three environments.
2.3
Exploiting the curvature of feasible sets
We start by introducing the definition of strongly and uniformly convex sets. We then define new notion of convex bodies, sphere-enclosed set, for which we can also achieve the fast rates of (In We finally discuss the existing lower bound when exploiting the curvature.
2.3.1 Strong convexity and sphere-enclosedness
One common way to describe the curvature of a convex body is with the following strong convexity. Definition 3. A convex body K is X-strongly convex w.r.f. a norm |1-I1 if for any y E K and any 0 E [0, 1]. it holds that or + (1 f)y + A(1 - 0) y/ B S K.
For example, bp-balls for p E [1, [1 are (p /-toosyyy convex w.r.t. I1-1Ip 17, Theorem 2], and another various examples of strongly convex sets can be found in [6. Section 5J. A more general notion of the curvature is by the following uniform convexity;
Definition 4. A convex body K is (v. q) uniforrmly convex w.r.f. a norm ||-I| (or q- q-miforrmly convex) for any x, y E K and any 0 E [o, 1), holds that Oz + (1 (1-0) O)y 0(1 0)<| w/| -Bi-I S K.
For example, f--balls for p 2 2 are (1/p.p)-unifomml convex w.r.t. 1| [7. Theorem 2], and p- Schatten balls are (1/p, -Juiforyyy convex w.r.t. the Schatten norm |1-1(s(p)) (See [11] and Ap- pendix H for the connection between the uniform convexity of a normed space and the uniform convexity of sets.) Note that (x, unifformly convex sets are r-strongly convex.
In this paper, we introduce new, different character- ization of convex bodies.
Definition 5 (sphere-enclosed sets). Let K C IRd be a convex body, E bd(K), and f: K -> R. Then, K is (p, u, ff ensseeeeeeenclose (or simply sphere- enclosed facing u) if there exists sphere of radius p that has u it, encloses K, and the gradient of / at point u is directed towards the center of the sphere.
That is, there exists ball B(c, p) with E Rdd and
Figure 1: Examples of sphere-enclosed sets.

---

> 0 satisfying (i) E bd(B(c,p)), (ï) K C B((c,)). and (ii) there exists > 0 such that ro V((u)= c.²
One might think that the sphere-enclosed condition is complicated but Condition (ii) in Definition 5 only for the case when v., is at the corner of K. Figure 1 shows examples of sphere-enclosed sets. The area enclosed by the solid black lines is the convex body K. In the left figure, we can see that K sphere-enclosed facing x (the red dotted line is the minimum sphere facing x), but K is not pphere-enclosed facing y. In the right figure, we can see that K is dotted line is the minimum sphere facing 2 for K). Note that the notion of sphere-enclosedness. is local property defined for each point of the boundary of convex bodies, in contrast to the definition of strong convexity. In the next section, we will see that we can achieve a logarithmic regret if K schere-enclosed facing at optimal decision Z..
facing (the blue
2.3.2 Existing lower bound
Here, we discuss a lower bound when exploiting the curvature of feasible sets. For À (0, 1), let W = {xx y) E R²; x² + y²/ < } be an ellipsoid with principal curvature X. From [9, Proposition 4]. ellipsoid WA A-strongly convex w.r.t 11-112- The following lower bound provided in [9, Theorem 9] is for this Wx. which matches the upper bound in [9, Theorem 5].
Theorem Consider online linear optimization. Let X, L E (0, 1) and K W,. Then, for any algorithm, there existy sequence of linear loss functions fi,..., JT satisfying Jel.)) = (gt.
g1:-..,9T E {(1, L), (-1, L)),, and the growth condition that [|g1 + + ge 2 uL for all
t [T] such that RT 2 84v2 AL In for 8
xL (1
108
In their proof, they use the following sequence of linear functions fe(.) (hf: -). Let P be random variable following a Beta distribution, Beta(k, K, k), for some k >> 0. For this P. let (X+) be i.i.d. random variables following Bernoulli distribution with parameter P. Then for
(0, 1), let h = (2X;- - 1. L), which indeed satisfies the growth condition | + ... + h 2 tL for all t [T]. This construction of loss functions will be exploited prove lower bounds Section 3, and we will provide matching upper bound in Corollary 12.
2.4 Universal online learning
Our algorithm is based the results of universal online learning. In the literature, the following regret upper bound is the crux for being adaptivity to the curvature of loss functions:
Lemma 7. Consider online convex optimization. Then, there exists (efficient) algorithm such that (Vf()) x.) is bounded from above by the order of
T
T Σ ((Vf((z))) - x.))² I /D
min Csc
Σ
x.1
T I Gee
where Cscs Cscs Cec, dec, Cg 0 are algorithm dependent variables provided in the following.
For example, upper bound (1) can be achieved by the MetaGrad algorithm with Gsc Gvd, dgc d,
Cec Vd, dec d, and 0g In In T [21, 22] and the Maler algorithm with Gsc = G, dsc GD, Gec Vd, d'c GD + d, and cg = 1 [24, Theorem 1]. We will see that our regret bounds depend on Csc; c/a, Cec, dec Cg > 0, and one can use any algorithm with bound (1).
3 Regret lower bounds
In this section, we construct lower bounds that align with the assumptions of our regret bounds. Con- sidering sequence of loss functions to construct the lower bound in Theorem 6, we can immediately obtain the following lower bound.
We will see the third condition that the gradient f at point directed towards the center of the sphere necessitates careful consideration when optimal decision z, is on corners of feasible sets.
TTe subscripts and ec in esc and Cec are the abbreviations of strongly-conver and exp-concave.
5

---

Theorem 8. Consider online linear optinization. Let X, E (0, 1) and K = Wx. Then, for any algorithmm there exists a stochastic sequence of loss functions fi..... ........ fo satisfying f.(.) (9:.))
.1....19T E {(1,- 11,--T), [[), - -T.)), and V (x+))l such that Ry Z BAVE ( In where 6 defined in Theorem 6.
-T
Proof. Consider the sequence of loss vectors hf...., all E (T). For this sequence of (fe) holds that (V = [+4] 2l = [0, - -D)le L * 0, which completes the proof.
......., h4 after Theorem 6 and let ft(.) = (hl for
-
With this lower bound, we have the following lower bound for corrupted stochastic environments.
Theorem 9. Consider online linear optimization. Let X, L E (0,1) and K W.- Suppose that T 2 Cj(2)}² and C 2 1/L.). Then, for any algorithm, there exists a corrupted stochastic environment with corruption level at most 2 0 satisfying [ (x.)ll2 such that
C
RT 2
+ *V \| (
V'n
- 6,
168V2
where å is defined in Theorem 6.
The assumption that T 2 C/(A))2 makes some sense since the construction of this lower bound relies on Theorem 8, and if the assumption does not hold then the lower bound becomes vacuous.
Proof. We will construct (fo) a corrupted stochastic environment, where (ft), are generated so that fe(-) = (āc.) -) with 91...., Ôr following a distribution D and fi is corrupted function of ft-
We first note that we have T 2 C/(AL) 2 1/(AL)². Define Î > 0 such that AŻ VAL/C. Note that since C 2 1/(A)). we have AL XL, implying that L E (0, 1). We also define = [1/(Aī]²1 [C/(AL)] s T. which follows from XŻ /AL/C and 2 C/(AL).
With these definitions, we then consider the following corrupted stochastic environments:
Fort t E {l...., T). define ft by fe(-) = (gc. -) for g. = hf. where h is defined after Theorem 8, and define loss function fe by fe(-) (gt, +) with gr lif. For E (1 T). let fe(-) f+(-) (ge,)) with gr. 144 where there is no corruption.
In fact, the corruption level of this environment bounded by C since E E [llff - fell = ET, [[sup=ex (gg- 9t,z)) = < T Σ!Λ S [C/(AL)] IL Żμ S C, where in the first inequality we used the fact that the first elements of and Gt are the same and that K = WA and in
the second inequality we used I, > T>> 0. This implies that the sequence of (ft) is corrupted stochastic environment with the corruption level most C.
Hence, from Theorem with ī (0, 1). XĪ VAL/C. and the definition of T. the regret is V
1 bounded from below as R 2 84/2 XT. In - 8 8LV2 & (n(()) - 5 Z 6AV2 Taking the average of the last two inequalities completes the proof.
1 XL In (.) - 8.
Note that our lower bounds are not for general sphere-enclosed feasible sets, and establishing new lower bound is important future work.
4 Regret upper bounds
In this section, we provide regret upper bounds that nearly match the lower bounds in Section 3, by the universal online learning framework, whose regret is bounded as (1). Note that this section works with convex loss functions.
4.1 Regret bounds in stochastic environments

---

We provide logarithmic regret for stochastic environments, De- fine the ball B Rd for y >> by
B
1 ( 27
1 V (x+))1) 2
B B
(
2%.
By the definition, we have v, E bd(B, See Figure 2.
Remark 1. The ball B is determined in the following man- ner. We will see in the following proof that the inequality (v." x - x.) 2 >|| x.1l2 that holds for some y > key
Figure 2: The region enclosed by the black solid line is feasible set K and the red dotted line B is the smallest sphere enclosing K and facing 2..
and any action z plays key role in proving logarithmiic regret.
This incquality is equivalent to || - (x. + 27 V (a.) (a.) I
2y [V and define B& as the set of all E Rd satisfying this inequality.
Using this B we let let = sup(1 2 0: K B. Then, we can prove the following theorem.
Theorem 10. Consider online convex optimization in stochastic environments, where the optimal decision I. arg mingek fo (x). Suppose that K is (p, F. (a)ssffrrr-eeenclone and that (x.) + O. Then, any algorithm with the bound (1) achieves
RT 0 Sc In T csc (n =0 ( ( 7+
2 P
IT + cac ln
(VF(
The assumption that K is sphere-enclosed around x, satis- fied for many typical feasible sets. It holds if the feasible set K a ball, or a polytope with a mild condition on (x.). Specifically, the condition V ()xx)) E int(-Nx (r.)) )) is sufficient to ensure that the feasible K is sphere-enclosed {g E Rd: (g.z Z.) >
undesirable direction of V (r.)) Fx
around 2., where -Nx( O E K} is the negative normal cone. This condition is mild since, from the optimality condition of x.,, have (x.) E (x.( Hence the undesirable case is re- stricted to (x.) E bd(-Nx (see Figure 3 for an example). One might think that the assumption that x" is on the boundary of K is restrictive, but for example, when the loss functions linear, the minimizer is indeed on the boundary of the feasible set. We will see in Corollary 12 that this upper bound matches the lower bound in Theorem in the environment used to construct the lower bound.
K
Figure 3: An example of an undesir- able direction of V (x.).
> 2.)] 2 E[E 74 11]] where the first inequality follows from the convexity of fo, and the last inequality follows from Ie E K C B% and the defini- tion of 7 By combining this inequality with inequality (I), the regret is bounded as Rr s
Proof. The regret is bounded from below by R = E [ (1'(z)) E (V)
E E (V((t))
x.)]- O (GE Rr In + cac In Solving this inequation w.r.t. Ry, we
get Ry = O E In T + d6e In Tn. Observing that [ = which holds from the as- sumption that K is (p. -ss-sse--eclooeeeee we complete the proof.
The advantages of the regret bound in Theorem 10 compared to the existing upper bounds are the following: (i) The logarithmic regret can be achieved as long as the boundary of K is curved around the optimal decision x,, or x4 is on corners (see Figure 1), while the existing analysis requires strong convexity over the entire feasible set K. (ï) While the existing analysis only considers linear loss functions, our approach can handle convex loss functions and thus the curvature of loss functions (e.g., strong convexity or exp-concavity) can be simultaneously exploited (see Section 4.3). (ii) Even if the growth assumptions on loss vectors 9l, ... yr are not satisfied, the O(VT) regret upper bound can achieved in adversarial environments, while the existing approach, FTL, can suffer I(T) regret.
7

---

A limitation of the proposed approach is that it assumes stochastic environments. However, our approach at least guarantees an O(vT) bound in the (fully) adversarial environments, where the growth assumption needed for FTL to achieve the fast rates is not satisfied, and as we will see the following section, we can achieve the fast rates also in corrupted stochastic environments.
For the assumption on loss vectors, the existing studies consider the following assumptions on loss vectors gr: There exists L > 0 such that [| +... 2 2 IL for all t E [T,, or I 0 for all & E [7]. These assumptions cannot be directly comparable with our assumption that ( A O. Note that the assumption that znf || (x)) > 0 is standard in the literature of offline optimization, when deriving the fast convergence rate, see [4, 5, 14] and discussion in [6] for details.
Extending the sphere-enclosed condition to an arbitrary norm is challenging because the sphere- enclosed condition leverages the fact that the enclosing ball is an Euclidean ball. However, will see in Section 4.4 that fast rates for uniformly convex sets can be achieved for general norms (Theo- rem 15).
Remark 2. The sphere-enclosed condition is similar to the Bernstein condition investigated by Koolen et al. [13]. These conditions are different for general convex loss functions; however, when the loss functions are linear, the sphere-enclosed condition implies the Bernstein condition, allowing us to apply their analysis in this case. Thus, our research can also be viewed as identify- ing condition that satisfies the Bernstein condition. Still, our analysis is more general in the sense that we can deal with general convex loss functions. See Appendix for a detailed comparison between the sehere-enclosed condition and the Bernstein condition.
Tightness of regret upper bound in Theorem 10 In the remainder of this subsection, we investi- gate the tightness of the regret upper bound in Theorem 10. To see the tightness of our regret bound, we consider the case when K is an ellipsoid. The following proposition implies that the regret upper bound in Theorem 10 matches the lower bound in Theorem 8.
Proposition 11. For À E (0, 1), let W, be the ellipsoid defined in Section 2.3.2. Then, its minimum enclosing sphere S such that (0, -A) E is S {(x. v) R x² + [ (1 =
The proof of Proposition 11 is deferred to Appendix B. This result immediately implies the following:
Corollary 12. Let K be Wx and x (0,- Under the same assumption as in Theorem 10, in the environment considered in the construction of the lower bound in Theorem 6, the algorithm [24] achieves Ry- = O In
GD GDIn1 T).
This upper bound matches the lower bound in Theorem up to the additive GD In T factor.
Proof. From Proposition 11 and the fact that Euclidean ball with radius r is 1/r strongly convex w.r.t. 11.112, we have p = 1/2. This proposition with Theorem 10 gives the desired bound.
The upper bound in Theorem 10 is applicable when K is polytope. We will see that our approach work also in the corrupted stochastic environment Section 4.2, and to our knowledge, this the first upper bound that achieves fast rates when the feasible set is a polytope in non-stochastic environ- ments. A further discussion regarding the case when is polytope can be found Appendix C.
4.2 Regret bounds in corrupted stochastic environments
Another advantage of our approach is that it can achieve nearly optimal regret upper bounds even in corrupted stochastic environments. For 7 > 0, we define ball B.K S Rd by BK
B B( +
2 (7+), 2 [ which is defined in the same manner as B.K. For this B&K we let 7. = sup{> 2 0: K C B.). Then, we can prove the following regret upper bound. Theorem 13. Consider online convex optimization in corrupted stochastic environnents with cor- ruption level at most C, where T. = arg mingek (x)). Suppose K is (p. T... f f')-shhere enclosed and f (ā.) # O. Then, any algorithm with the bound (1) achieves
1o In T + 65e lnT (1
= =0
2 P
Ce.
RT 0
In T
In +
In + dhe InT
7+
[+.)l2))
8

---

The proof of Theorem 13 can be found in Appendix D. One can see that this upper bound matches the lower bound in Theorem up to logarithmic factors. Note that all upper bounds provided in this study can be extended following the same line as the proof of Theorem 13.
4.3 Exploiting the curvature of loss functions and feasible set simultaneously
One of the advantages of directly solving OCO over reducing to OLO is that we can obtain upper bounds that can simultaneously exploit the curvature of feasible sets and loss functions:
Theorem 14. Suppose that the same assumption as in Theorem 10 holds. fi...... fo are a-strongly convex w.E.f. norm
||- then Rr- =0( 7+ ta/E In + c'a (nTT If f1...., fr are 3-exp-coneave,
then Ry = 0 min (0(min
{ dee 7- 8' } In T max (ac In for B' s min 11.
dee
The proof can be found in Appendix E. Theorem 14 implies that one simultancously exploit the curvature of feasible sets and loss functions.
4.4 Matching regret upper bound for uniformly convex sets
Here, we prove that a regret bound smaller than O can be achieved when K is uniformly convex. This can proven by similar argument using the idea of exploiting the lower bound, as in the proof for sphere-enclosed sets. For uniformly convex feasible sets, we can prove the following theorem.
Theorem 15. Consider online convex optimization in stochastic environments, where the optimal decision is x= = arg mingek f (xx). Suppose that is (R, q) -uunffrrml convex w.r.t. a norm II-II for some q 2 2 and that (xx)) + O. Then, any algorithm with bound (1) achieves
RT 0
(ECsc) =
T (In (In I + dee (oIITT)
(=.)))
In particular, when K is X-strongly convex w.r.t. 11111. RT 0
Sce In T + d'e InT)
The dependence on T in this bound O ( (T (n which becomes O T) when q and Ö(VT) when y + xo, and thus interpolates between the bound over the strongly convex sets and non-curved feasible sets. This is strictly better than the O ( bound in [11]; their regret upper bound is better than O(vT) only when E (2, Notably, our bound matches the existing q-2 lower bound of ( 17) proven for a stochastic environment with d = 2 [2, Theorem C.1]. For example, when K is lp- ball, by ||01|2 I dt ||x||p for any x E Rd and p > 2, the regret bounded
as R = 0 ($ew) (I 1f T p-2 (In T) ب + d'e In T
(I
is worth noting that the result of Theorem 15 corresponds the result for sphere-enclosed sets when 2 and ||-|| is the Euclidean norm. Additionally, Theorem 15 does not require the feasible set K to be globally "curved." In fact, the proof of Theorem 15 only uses the inequality (V.'(x) ...) 2 || 1.119. f[ Il. for all E K, which describes the local curvature around the optimal solution x..
Before proving Theorem 15, we present the following lemma, which provides a characterization of uniformly convex sets. This directly follows from the definition in Definition 4:
Lemma 16. Suppose that convex body K is (1s, unifoormly convex w.r.t. norm ||-|| R. > Oand q 2 2. Let E K, E Rdd, and y, E arg miny k (g, v²)). Then, (-9, 9, y+
y) > + Ely 1-11 ||sll+.
The proof can be found in [12, Lemma 2. and we include the proof in Appendix F for completeness.
Proof of Theorem 15. From x. = arg min (x) and the first-order optimality condition, (2.),,, 2.) 2 0 for all K, which implies that x, arg min (V (v.) Hence,

---

by combining this with Lemma 16 and that K is (1., q) unifformly convex w.r.t a norm II-Il, we have x.,)
(V
I
1=11% 9
(x,))l for all x K. Using this inequality,
T
RT
E
(s.),, Jt. - xam z
| J. 1
9/2
T
T
x.
Σ
2.112
k (z. T T
Σ
r x. 112
(2)
45
4
where the first inequality follows from the convexity of fo, the second inequality by ||0||2 E||=|| for any Rd, and the last inequality by Jensen's 's inequality and the fact that + x0/2 is convex for 2 2. Combining (1) and (2), we can bound the regret as
R = 2R Rx
9/2
T
0
Csc
E
24
I. 11
In dge In
VI (x+))l
T1
E
20
x
112
450
(Eosc)
-0
(In 21 2 + dse In
(q/S) fx=)))))))))>>)>)))>)>))))))))))
where in the last line we used the inequality a/2x bx S a (qb)) न that holds for a, b, > and g 2. This completes the proof.
The above analysis can be extended to corrupted stochastic env environments in a straightforward manner: Theorem 17. Consider online convex optimization in corrupted stochastic environments with cor- ruption level C, where the optimal decision is F. arg min ge (x)). Suppose that K is (K, q)- uniformly convex w.r.t. a norm for some q 2 and that V (T.) + O. Then, any algorithm with the bound (1) achieves
(ECx)) -
Rr- O + ( for R
Tz--1)
(InT) ".
(In T)
(qKll fo (z.) (1.))l.)
When K is A-strongly convex w.r.t 11-11. Ry RT= = 0 ( Eox
In +
CE f
In T + dge Tn
((.)I
The proof can be found in Appendix G. When = 2, the dependence on the corruption level C' is the same as that in Theorem 13.
5 Conclusion
In this work, we introduce a new curvature condition for achieving fast rates in online convex opti- mization. Under this condition, we developed new analysis to achieve fast rates by exploiting the curvature of feasible sets. particular, by the algorithm adaptive to the curvature of loss functions, we proved an (Op In 7) regret bound for (p, x.. / J's-spe enclosed feasible sets. There are several advantages of our approach: it can exploit the curvature of loss functions, can achieve the O(I T) regret bound only with local curvature properties, and can work robustly even in environments where loss vectors do not satisfy the ideal conditions. Notably, following a similar analysis, we proved the matching regret upper bound for uniformly convex feasible sets, which include strongly convex sets and Ep balls for p E [2, oo) as special cases. This regret bound interpolates the O T)) regret over strongly convex sets and the O(VT)) regret over non-curved sets.
Acknowledgmentss and Disclosure of Funding
The authors would like to express their gratitude to Taiji Suzuki for the insightful discussions that led to the idea of exploiting the curvature feasible sets in online learning. The authors would also like to grateful to the anonymous reviewers for their insightful feedback and constructive suggestions, which have helped to significantly improve the manuscript. TT was supported by JST ACT-X Grant Number JPMJAX2 10E and JSPS KAKENHI Grant Number JP24K23852.
10

---

References
[1] Daron Anderson and Douglas Leith. The lazy online subgradient algorithm is universal on strongly convex domains. In Advances in Neural Information Processing Systems, volume 34, pages 5874-588 5884, 2021.
[2] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages $22-831, 2020.
[3] Ofer Dekel, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet. Online learning with a hint.
In Advances in Neural Information Processing Systems, volume 30, pages 5299-5308, 2017.
[4] Vladimir F. Demyanov and Aleksandr M. Rubinov. Approximate methods in optimization prob- lems. Elsevier Publishing Company, 1970.
[5] Joseph C. Dunn. Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals. SIAM Journal Control and Optimization, 17(2):1872211 1979.
[6] Dan Garber and Elad Hazan. Faster rates for the Frank-Wolfe method over strongly-convex sets. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 541-549, 2015.
[7] Olof Hanner. On the uniform convexity of Lp and lp. Arkiv för Matematik, 3(3):239-244, 1956.
[8] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69:169-192, 2007.
[9] Ruitong Huang, Tor Lattimore, András György, and Csaba Szepesvári. Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities. Journal of Machine Learning Research, 18( 1-3,, 2017.
[10] Shinji Ito. On optimal robustness adversarial corruption in online decision problems. In Advances in Neural Information Processing Systems, volume 34, pages 7409-7420, 2021.
[11] Thomas Kerdreux, Alexandre d' d'Aspremont, and Sebastian Pokutta. Projection-free optimiza- tion on uniformly convex sets. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 19-27, 2021.
[12] Thomas Kerdreux, Christophe Roux, Alexandre d' d'Aspremont, and Sebastian Pokutta. Linear bandits on uniformly convex sets. Journal of Machine Learning Research, 22(284):1-23, 2021.
[13] Wouter M Koolen, Peter Grünwald, and Tim van Erven. Combining adversarial guarantees and stochastic fast rates in online learning. Advances in Neural Information Processing Systems, volume 29, pages 4457-4465, 2016.
[14] Evgeny S. Levitin and Boris T. Polyak. Constrained minimization methods. USSR Computa- lional Mathmatics and Mathematical Physics, 665):1-50, 1966.
[15] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to ad- versarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 114-122, 2018.
[16] Zakaria Mhammedi. Exploiting the curvature of feasible sets for faster projection-free online learning. arXiv preprint arXiv:2205. 11470, 2022.
[17] Marco Molinaro. Strong convexity of feasible sets in off-line and online optimization. Mathe- matics of Operations Research, 48(2):855-884, 2022.
[18) Gilles Pisier. Martingales in Banach spaces, volume 155. Cambridge University Press, 2016.
[19] Sarah Sachs, Hedi Hadiji, Tim van Erven, and Cristóbal Guzmán. Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness. In Advances in Neural Information Processing Systems, volume 35, pages 691-702, 2022.
11

---

[20] Sarah Sachs, Hedi Hadiji, Tim van Erven, and Cristobal Guzman. Accelerated rates between stochastic and adversarial online convex optimization. arXiv preprint arXiv:2503.05222, 2023.
[21] Tim van Erven and Wouter M Koolen. MetaGrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems, volume 29, pages 3666-3674, 2016.
[22] Tim van Erven, Wouter M. Koolen, and Dirk van der Hoeven. MetaGrad: Adaptation using multiple learning rates in online learning. Journal of Machine Learning Research, 22(161): 1-61, 2021.
[23] Yuanyu Wan and Lijun Zhang. Projection-free online learning over strongly convex sets. Pro- ceedings of the AAAI Conference on Artificial Intelligence, 35(11):10066-1008 2021.
[24] Guanghui Wang, Shiyin Lu, and Lijun Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Proceedings ohe 35th Uncertainty Artificial Intelligence Conference, volume 1 15, pages 659-668, 2020.
[25] Yu-Hu Yan, Peng Zhao, and Zhi-Hua Zhou. Universal online learning with gradient varia- tions: A multi-layer online ensemble approach. In Advances in Neural Information Processing Systems, volume 36, pages 37682-37715, 2023.
[26] Lijun Zhang, Guanghui Wang, Jinfeng Yi, and Tianbao Yang. A simple yet universal strategy for online convex optimization. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 26605-26623, 2022.
[27] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-936, 2003.
12

---

A Additional related work
This appendix discusses the additional related work.
Fast rates on strongly uniformly convex sets Exploiting the curvature of feasible sets has been considered OLO. In addition to the previously discussed studies [9, 11, 17]. in online learning with hint, where context my satisfying m, 2 c||xx|12 { is given every round, we achieve an O I') regret [3], which was further extended in [2] with the lower bound for uniformly convex sets. The curvature
also exploited for improving regret upper bound and reducing the number of linear optimization oracle calls in constructing Frank-Wolfe-basee Wolfe-based algorithms [16, 23]. Beyond the scope of online learning, exploiting the curvature of feasible sets has been investigated also in offline optimization, where the goal is to solve min f() for given smooth convex function f [4, 6. 11, 14].
Fast rates on curved loss functions One classical and seminal work to exploit the curvature of loss functions is by Hazan al. [8]. Our approach is based the results of universal on- line learning, the motivation of which to be adaptive to parameters of loss curvature without knowing them. This line of investigation was initiated by van Erven and Koolen [21], van Er- ven et al. [22]. who establish an algorithm, MetaGrad, that achieves an O In 7) regret bound
if loss functions are c-exp-concave and an O In IT) bound otherwise, without knowing the curvature of loss functions. The underlying idea is to run several experts parallel with differ- ent curvature parameters, and then another expert algorithm integrates their results to choose de- cisions. This algorithm was later extended to achieve an O In T) regret bound when the loss functions are a-strongly convex [24]. Roughly speaking, this was made possible by considering MetaGrad with additional experts of OGD with learning rate of (1//t). They provided bound of
x. 11 In TD T) for D max,, || - vll2- This uni versal online learning framework has been extended to simpler form [26] and to form with the path-length bound [25]. worth noting that these algorithms are efficient since the number of experts is at most T'n
E (V (z(),, x.) OOGV
Ei=ilaz /
Intermediate environments in OCO The corrupted stochastic environments considered in this paper are similar to the formulations investigated in the context of expert problems and multi-armed bandit problems [10, 15], and this environment is also referred to as stochastic environments with adversarial corruptions. Sachs et al. [19, 20] considered more general environment, the stochasti- cally extended adversary (SEA) model. It would be important future work extend our results to the SEA model. Note that they do not consider the curvature of feasible sets.
B Proof of Proposition 11
Proof. Since K is Wx and = (0, -A), the optimization problem we need to solve is formulated as follows:
(0)
minimize +30,
subject to
sup (x.))EK
S S² B((O,c), is tangent to (3)
From geometric observations, have rewritten as
X. Hence, the optimization problem (3) can be
minimize oER
(c+ x) subject
sup {2² 2² 2cy) - 2ch X². (x.0)EK
(4)
In the following, make the constraint in the optimization problem (4) simpler, consider the following optimization problem:
y² x
maximize (a.v)eR2
x²+ ++ 3² 2cy subject to x² +
13

---

By the standard method of Lagrange multiplier, one can compute that the optimal value of this opti- mization problem is max
2Ac X2,2Ac A2
2Ac + 1²
+ #1] Since the inequality
2Ac + 22, 2Ac X2
1-11++1 X²
1
+1
2Ac X²
max
only holds when 1-X² the feasible set of the optimization problem (4) is singleton set Combining this fact with c- r ーX, we get the desired result.
1-12
C Discussion when feasible set is polytope
Here we discuss the pros/cons of our regret bound against an existing bound when feasible set K' is polytope. The results mentioned in Section 4 mainly focus on the case where the feasible set is curved. However,
from the definition of the sphere-ente encroredccsss,,sss,. even if the feasible set is polytope or does not have the curvature, regret upper bound better than O( (T) can be achieved.
In the existing study, the following upper bound is known in stochastic OCO over polytope [9, Corol- lary 11].
Theorem 18. Consider online online linear optimization stochastic environments with ge =Egge] Assume that K is polytope and ligelloc S M. Further assume that there exsits > 0 such that ((-) m (xr,)) is differentiable for any such that [| go S r. Then, the regret of FTL
bounded by RT 0 M M²d
The comparison of this bound with our regret upper bound is not straightforward. If V / (xr,) is toward the "unfavorable" direction in K, then is trivial that polytope K is (p, )-sheee- enclosed for some p, and thus the regret bound in Theorem 10 can be achieved. When T is large enough, the bound in Theorem 18 better since it does not depend on T. However, their regret upper bound depends on L/r² and M and the relation between them and V (xx))l is unclear, and our bound can be smaller than their bound. Note that the "unfavorable" direction coincides between these upper bounds when OLO is considered.
While the direct comparison is straightforward, bound, in contrast to their bound, is obtained as a corollary of the general analysis, and our bound inherits all the advantages discussed in Section In partieular, while their bound is valid only in stochastic environments, our regret guarantee is valid in stochastic, adversarial, and corrupted stochastic environments.
would like to emphasize that our regret upper
D Proof of Theorem 13
Proof. Recalling that т. = arg min (z),, we can bound the regret from below as
Ry max E
(f((z)) -f((z))
zEK
max zek
E
Σ (f(ct))
- -F(O))
+ Σ
((.)))
-
Σ (f((t))))(t)) -(Lo)
2 max E zeK
2C' -2C.
The first term in the last inequality is further bounded from below as
T Σ
T
(((or))
(x))) - (((x))
max TE zEK
2 E
E
v (7.
> E
Σ
7a 1| - x2113
14

---

where the first inequality follows by the definition of I. and the last inequality follows by 21 E K _ B Combining the above inequalities with (I), we have Rr O Csc
R
In T dge In
%
Solving this inequation and following the similar analysis as the proof of Theorem 10 complete the proof.
E Proof of Theorem 14
Proof. Following the same argument as in the proof of Theorem 10, we have
Ry 22 Rr 2R
E
74 1 x.12
(5)
From the strong convexity of ft, also have
RT S
f((zz), - -x.)
a
22i - I. 112)
k E
(Vif( xxx
α 2
2c - xz 2.133
(6)
Plugging (6) in (5) and from Lemma 7 and Jensen's inequality,
1
T
Ry 00
Csc
x. 12 In chec ln vt
+
7/
E
2'e - F.
2
In + dge lnT
a/C +
which completes the proof for the strongly convex loss functions.
Next, we consider the case where ft's are exp-concave. By [8, Lemma 3J, the G-Lipschitzness and B-exp-concavity of fe implies
8' ([V
f((x,) 2 f((xe) + (Vf((z)), xz) +
1 for 3' 1 min 4GD 3}. Using this and Lemma follow similar argument the strongly-
convex case, we can bound the regret as
Ry = = min
Σ (VV 221)) InT
c2 E
Σ
100a
xx
11
2 E
+ maxf coctlI In
- E.
||ate x=11
-B'E ((Vi)))))
= -0(min) E (7
&ec
+ max dec In
where in the last inequality used Mauchy-Schward incquality.
||2|
2.113 2 d (Vf((z)) (2, xI))² that holds by the
F Proof of Lemma 16
Proof. Since K is (K, -)uunfformly convex w.r.t. norm ||.
y + y
+
ll 8+11%
Bi--1 S K.
15

---

Hence, for any 2 BiI-1+ the definition of y. implies that
v.) 9. 2
+
Ill y.11 9.
+
+ (g.
ll
yo 112²))
2
8
Rearranging the last inequality implies (-g. U v) 2 $ 11 y- 11 ( 2). Choosing -9/ll91 B-I completes the proof.
L
G Proof of Theorem 17
Proof. The regret is bounded from below as
4/2
T E
RT
E
Σ (T.)).) xz)) -20 R t=1
(VF T 45"
x F+
20
(7)
where the first inequality follows from the same argument as in the proof of Theorem 13 in Appendix D and the second inequality from the same argument in (2). Recall that R
(E
T is (In ()) v. Then from (1) and (7), for any (0, 1] we have
(9n) (T.)..
Rr = (1 + A)RT ART
9/2
S (1 + A)CSE
E Σ Ir xx1
InT
V
1|
T
Σ x 3e 112
45
2AC + (1+ + X)cee InT
(1
R 2AC + 20 InT
-=-
< 4 7 1Q-11
(In T) কা + 2XC + 2che In
(8)
A (g2).1
where in the second inequality we used a bx S a <a->r/(qb)== that holds for a, b, x >
0 and
9=1
q 2 2 and in the last inequality used (1+ (1+ 2 4. Choosing À =
R
(0, 1]
C+R
in (8) gives Ry O(R + C.' + + In I"), which completes the proof.
H Connection between uniform convexity in Banach space and uniformly convex sets
This appendix discusses the connection between the uniform convexity in Banach space and the uniformly convex sets. While the notion of uniformly convex achieving fast rates by exploiting the curvature of feasible sets [11], some papers in the context of online learning with hint consider uniformly convex Banach spaces [2, 3]. This appendix may be useful in making the claims of the main body clearer by clarifying these relationships.
employed in the context of
Uniformly convex space and modulus of uniform convexity We start from the definition of the uniform convexity in Banach spaces [18, Definition 4.16).
Definition 19. A Banach space (B, |I-I]) is uniformly convex if for any (0, 2] there exists 8 >>> 0 such that
Va, BeyEl B, |||||| < 1, |vl| < 1, || vll 2
y
8.
2
The modulus of uniform convexity (g(E) the best possible for that e, that is,
(5()) inf
x |||||| - |vll 1, || vll 2
Further, say that B is (C, -uniformly convex if d5(s) Csa,
16

---

We say that Banach space B is uniformly convex if Óυ(c) > 0 for any E (0, 2]. The modulus of convexity captures the strength of convexity, and intuitively, the convexity of the space large, then any two arbitrarily chosen points on the unit sphere will have their midpoints located deep inside the unít sphere. From this intuition, one can imagine that loe space is not uniformly convex. In fact, = (1.1,1....)
= (-1,1,1,...) satisfies || llvlloo 1, || - yll = 2 but
1- [( z + 2l
Uniformly convex sets Here, we adopt slightly generalized definition of uniformly convexity.
Definition 20. A convex body K is Tx (xc())-mm -uniformlly convex w.r.t. norm ||-II if for any z, E K and any 8 E [0, 1]. holds that
Or + (1 fly + 0(1 0)>k( vll) B|1| S K.
In particular, we we say that convex body K is (1s, q) uniffrrmly convex w.r.t. norm ||-Il (or q-uniformly convex) if (r(r)= 2 kr
Connection between uniform convexity in Banach space and uniformly convex sets is known that the unit ball on a uniformly convex space is uniformly convex set and their uniform convexity matches up to a constant factor [11, Lemma 4.2].
Proposition 21. Suppose that Banach space is uniformly convex with modulus of convexity 8(-). Then the unit ball on the Banach space, B ||. is 28( -uiiformly convex set w.r.t. ||-||. That is, for any x, E |-1|| and any 0 E [0, 1}, Or + (1 0)y + 0(1 0)20([1=z -aaee--yp vll) BB1-11 S 11-111
In existing studies, there is no explicit discussion on whether the converse of Proposition 21 true. However, they are necessary to convert the major result known for uniformly convex spaces (e.g., [7, Theorem 2)) into a result for uniformly convex balls. the following, we show that the converse of Proposition 21 indeed holds for completeness:
Proposition 22. If a ball K = B1 is 7:))-(ifoormly convex set w.r.f. a norm ||-|], then a Banach space with the norm ||-]| is uniformly convex with modulus of convexity 17(-).
Proof. Since K is (0)))((-(fonn) (uniforrrylly convex w.r.t. a norm that
|1-I], it holds for any x. y E K and 2 E Bi--1
x +
1
+
4 7
-1)) e K.
2
Taking = = -/x + 0)/ll(( y)ll E BIH implies
x +
1
(x+
+ 4 711 bll)
E K.
2
[1x + y)/2
From this observation, we obtain
+ y
1
x11 vll)
(x
4 711 v/l
11 + y) /)/211 )
+ y
4
[1( /)/
y
+ 4 < yll) - 1,
where the last inequality follows from the assumption that K ||||| Hence, for any z, K B.g it holds that
x +
- wll),
1
which implies that Banach space with the norm of 5(.) = +-())
||-|| is uniformly convex with the modulus of convexity
I Comparison of sphere-enclosed condition and Bernstein condition
This appendix discusses the relation between the sphere-enclosed condition and the Bernstein con- dition. We use .. to denote the expectation given f1.... J1....Jt-1. ft-1-
17

---

Bernstein condition The seminal paper by Koolen et al. [13] provides the following Bernstein condition obtain fast rates in OCO:
Definition 23. In online convex optimization, sequence of loss functions (fi) satisfies the (B, k))Bersttein condition if 10
Es ((Vfil)) xx,)) < (
(9)
almost surely for all E K and E [T].
When & = 1, this condition is also known as the Massart condition. They proved that the (B, k)- Bernstein condition is satisfied, then the MetaGrad algorithm achieves regret bound of RT
7)
Sphere-enclosed condition Under the same assumption as in Theorem 10, the (p, J. --phere- enclosed condition implies that
[V.(()))]
V f (x+), - r.) 2 > x.
11 x2112
2p
for any x E K. Rearranging the last inequality gives that
2p
I 22
(Vf(I.),
(10)
(x.)))
holds for any x E K. When loss functions are stochastic, the last inequality implies
2G
Eg 2 - G - - (x.)ll) x
(11)
where the first inequality follows from the Cauchy-Schie Schwarz inequality and the second inequality follows from (10).
Comparison between Bernstein condition and sphere-enclosed condition Comparing (9) and (11), sphere-enclosed condition and the Bernstein condition, since the RHS of (9) has x in V fx) while the RHS of (11) has x, in f However, when loss functions are linear with V (x) for all x E K, Eq. (11) is equivalent to
that they look similar but different and there no direct connection between the
2G
2G2p E. EVV x x.)]. 11
Es ((Vff(())==a))) z2))
<
(V.) x.) 1
Therefore, when loss functions are stochastic and linear, the (p. T.. f sphher--enclosee condition implies the (2G*p/llg 1)-Bernstein condition for = V Hence, in stochastic OLO one can directly apply the result in [13] to obtain fast rates. Still, our analysis deals with general convex loss functions, can also be extended OCO over uniformly convex sets, and has several advantages as detailed in Section
18

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction, claim that consider online convex optimization and introduce a new approach and analysis for achieving fast rates over curved feasible sets.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provided a comparison of our regret bounds against existing regret bounds Table 1 in the introduction, after Theorems 10 and 15, and Appendices and
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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 au- thors should reflect how these assumptions might be violated 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. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-ter system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The problem setting of online convex optimization is detailed in Section 2 and the complete proofs are provided 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 proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification:
The focus of this study is on theory and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not 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 make their results reproducible verifiable.
Depending on the contribution, reprodueibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it 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 to 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 sub- missions provide some reasonable avenue for reproducibility, which may depend the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe
the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results way to produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results.
20

---

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, described in supplemental material?
Answer: [NA]
Justification: The focus of this study is on theory and does not provide open access the data nor code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nipp cc/
ssooioicccyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips... cccpublic/guiiee. Seaeiiddee/oeeubbbeee CCodeSubeeiiicccc
onPolicy)
more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specifyy all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The focus of this study on theory and does not include experiments. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification:
The focus of this study is on theory and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
21

---

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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI. if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The focus of this study is on theory and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:///enurii....eoeeo cc/ppblic/ ceabbiie/Ehiisuuieeliiiini
Answer: [Yes]
Justification: The focus of this study is on theory and does not include contents that can violate the NeurIPS Code of Ethics.
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 circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Does the paper discuss both potential positive societal impacts and negative so- cietal impacts of the work performed?
Question:
Answer: [NA]
Justification: The focus of this study is on theory and does not have societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address socictal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the tech- nology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does 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:
The focus of this study is theory and does not include experiments.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse 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 restrictions to access the model implement- ing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The focus of this study on theory and does include experiments using existing assets.
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 or 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 (e.g., website), the copyright and terms of service of that source should be provided.
23

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi paperswithcode thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged reach out the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The focus of this study is theory and does not introduce assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicaalle). You can either create anonymized URL or include 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: The focus of this study is on theory and does not involve crowdsourcing and human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contri- bution of the paper involves human subjects, then much detail possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, 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 the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The focus of this study is on theory and does not involve study participants.
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 we expect authors 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.
25


Reviews:
[{"review_id": "LqnZRjBU1k", "reviewer": "Reviewer_b39D", "summary": "This paper considers the influence of feasible set geometry on the OCO regret. For a class of algorithms satisfying certain regret upper bounds (including MetaGrad and Maler), the authors provide new fast-rate results in the stochastic convex loss setting and the corrupted convex loss setting. Their results also match existing lower bound results.", "questions": "What's the main technical challenge in extending existing results for OCO from the stochastic setting to the stochastically extended adversary (SEA) setting or even the adversarial OCO setting? Could the authors explain more about the gap in simply applying the linearization technique in this setting?", "limitations": "N.A.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Most contributions of this paper are new in the OCO area, including:\n\n1.A novel generalization of previous curvature-dependent regret for linear optimization to general stochastic convex loss.\n\n2.New regret results in the corrupted setting.\n\n3.A new result that simultaneously utilizes the curvature of the loss and the feasible set.", "weaknesses": "One possible limitation of the results is that, unlike the OLO results, the action set curvature-dependent rates for the convex losses in this paper don't hold for the adversarial setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and careful review. We will address the minor comments and typos in the revised version. Below are our responses to the review.\n\n**Rebuttal to Weaknesses**\n\n> One possible limitation of the results is that, unlike the OLO results, the action set curvature-dependent rates for the convex losses in this paper don't hold for the adversarial setting.\n\nWe acknowledge that this is indeed a shortcoming of our approach, as you pointed out.\nStill, note that our approach can achieve fast rates when the environment is stochastic while achieving $O(\\sqrt{T})$ in adversarial environments.\nFurthermore, please note that the conditions under which Follow the Leader (FTL) achieves fast rates are neither sufficient nor necessary for the conditions under which universal online learning achieves fast rates.\nInvestigating whether it is possible to achieve fast rates similar to FTL using universal online learning in adversarial environments is an important direction for future work.\n\n**Replies to Questions**\n\n> What's the main technical challenge in extending existing results for OCO from the stochastic setting to the stochastically extended adversary (SEA) setting or even the adversarial OCO setting? Could the authors explain more about the gap in simply applying the linearization technique in this setting?\n\nThank you for the question.\nAt this point, we are uncertain whether an extension to the SEA model is possible, and exploring this is an important direction for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9223mSer3a", "reviewer": "Reviewer_kmSZ", "summary": "The paper relates the regrets of (stochastic) online convex optimization to the geometry of the feasible set. Precisely, the paper proposes the sphere-enclosed-feasible-set property which measures the local curvature condition of the feasible set at the offline optimal solution, and shows that many existing online convex optimization algorithms, under this property, achieves regret O(\\rho*\\log(T)), the fast rate. In addition, similar regret upper bounds are shown to be valid in various settings, including the stochastic with corruption, convex (nonlinear) objectives, etc.", "questions": "I’m wondering if there is any connection between the \\lambda-strongly convex feasible set and the sphere-enclosed feasible set? The lower bounds are provided for the case when the feasible sets are ellipsoid or \\lambda-strongly convex, but the upper bounds are provided under the sphere-enclosed condition. It would be great to compare the lower and upper bound under the same set of conditions.", "limitations": "Yes, the paper points out that one limitation is that the main results hold under stochastic environment.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduced sphere-enclosed-feasible-set property appears innovative, and provide insights into conditions under which fast rate is achievable.", "weaknesses": "The paper shows that many existing algorithms can converge at the fast rate under the proposed sphere-enclosed-feasible-set condition. Thus, one might argue that there is not too much improvement over previous works on the algorithmic side. In addition, the lower and upper bounds provided appear to hold under slightly different conditions (see the question below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your valuable time and insightful review. \nBelow are our responses to the review.\n\n> In addition, the lower and upper bounds provided appear to hold under slightly different conditions (see the question below).\n\nand\n\n> I’m wondering if there is any connection between the \\lambda-strongly convex feasible set and the sphere-enclosed feasible set? The lower bounds are provided for the case when the feasible sets are ellipsoid or \\lambda-strongly convex, but the upper bounds are provided under the sphere-enclosed condition. It would be great to compare the lower and upper bound under the same set of conditions.\n\nThank you for pointing out this important point.\nThe upper bound for sphere-enclosed sets (Theorem 10) corresponds to the lower bound for the ellipsoid $W_{\\lambda}$ (Theorem 8). This is because, as stated in Proposition 11, the ellipsoid $W_{\\lambda}$ is sphere-enclosed with $\\rho = 1 / \\lambda$.\n\nThe upper bound for uniformly convex sets (Theorem 15) corresponds to the lower bound for the ellipsoid $W_{\\lambda}$ (Theorem 8). This is because uniformly convex sets include strongly convex sets as a special case, and $W_{\\lambda}$ is $\\lambda$-strongly convex with respect to $\\\\|\\cdot\\\\|_2$.\n\nHowever, as the reviewer pointed out, our paper does not provide a lower bound for general sphere-enclosed feasible sets.\nIn the revised version, we will emphasize this point and also note that the ellipsoid $W_{\\lambda}$ is sphere-enclosed with $\\rho = 1 / \\lambda$.", "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": "T8do7kV4hR", "reviewer": "Reviewer_Mo5s", "summary": "In this work, the authors study stochastic online convex optimization (SOCO), and establish a tighter regret bound of $O(\\log T)$ for sphere-enclosed sets. Specifically, such a regret bound is derived by exploiting an immediate result of several existing universal online learning algorithms. Moreover, the authors also demonstrate that the immediate result can be utilized to recover the existing regret bound for SOCO over strongly convex sets, and could improve the existing regret bound over uniformly convex sets. In addition, a corrupted setting is also considered, and lower bounds for non-corrupted and corrupted are also provided.", "questions": "Besides the weaknesses discussed above, I also have the following questions.\n1) Can the authors summarize the fully new contributions compared with existing studies?\n2) In Theorem 14, the authors exploit the curvature of loss functions and feasible sets simultaneously. Are those regret bounds better than the existing regret bounds derived by only exploiting the curvature of loss functions?", "limitations": "The authors have discussed some limitations of this work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper studies stochastic online convex optimization (SOCO), and mainly focuses on feasible sets with special curvature. Although this paper is not the first to study the problem, it has the following strengths compared with previous studies.\n1) Different from previous studies that need the strong convexity of sets to achieve an $O(\\log T)$ regret bound for SOCO, this paper introduces a new condition on the set to obtain the $O(\\log T)$ regret bound, i.e.,  sphere-enclosed sets.\n2) For SOCO over the uniformly convex sets, this paper has established a better regret bound than existing results.\n3) The authors also consider a corrupted setting that interpolates the fully adversarial and stochastic settings.\n4) Matching Lower bounds for a special case of ellipsoid sets are provided for the non-corrupted and corrupted settings.", "weaknesses": "Although this paper provides some new results for stochastic online convex optimization (SOCO), I have some concerns. First, compared with stochastic (offline) optimization, the main challenge of online convex optimization (OCO) is how to deal with a fully adaptive adversary. However, this paper mainly focuses on SOCO, where the adversary is even weaker than the oblivious one, which is not very interesting to me.\n\nSecond, although it seems that this paper has made many contributions, some results have already been achieved, and some results can be simply derived. \n1) The authors argue that previous studies [8,16] only consider online linear optimization (OLO) that may prevent us from leveraging the curvature of loss functions, and the existing FTL algorithm [8] will suffer an $\\Omega(T)$ regret if the ideal condition is not satisfied. However, in Section 4 of the existing work [8], Huang et al. have already proposed an adaptive algorithm to avoid the $\\Omega(T)$ regret of FTL, whose regret is at most $O(\\sqrt{T\\log T})$. The main idea is to utilize an expert tracking algorithm to combine FTL with an optimal algorithm for the general OCO. I also refer the authors to a missing related work [*], which provides an online lazy gradient descent algorithm, which enjoys the same regret bound as the algorithm of Huang et al.\n2) Note that universal online learning algorithms utilized in this work follow a very similar idea of using the expert tracking algorithm. Moreover, it is easy to combine FTL with universal online learning algorithms. Without the analysis provided in this paper, one can simply prove that such a combination can achieve the $O(log T)$ regret of FTL for SOCO under ideal conditions, and leverage the curvature of loss functions (and the convexity) to recover the optimal regret bounds for general OCO.\n3) The derivation of the lower bound in Theorem 8 seems to be very simple, i.e., just computing and replacing a constant of an existing lower bound with the gradient norm in the fixed optimal solution. Moreover, the extensions (about both the lower and upper bounds) to the corrupted setting do not bring noteworthy challenges.\n4) The sphere-enclosed sets seem to be a bit complicated. Moreover, as discussed by the authors it is very similar to the Bernstein condition, which is more common and has been used to achieve a tighter regret bound for SOCO. So, it is not surprising that the sphere-enclosed sets can also be used to derive similar results.\n\nThird, the writing and organization of this paper are not very sound.\n1) The context of Section 2.1 is almost the same as the first paragraph in Section 1.\n2) Many short proofs are interluded in the main text, which reduces the readability of this work.\n3) In line 340, \"a similar analysis ideas\" seems to be a typo.\n\n[*] Anderson and Leith. Online Lazy Gradient Descent is Universal on Strongly Convex Domains. In NeurIPS 2021.\n\n----After Rebuttal----\nAfter reading the authors' response, I realize that it is very hard (and even impossible) to combine FTL with an existing universal online learning algorithm. So, the analysis of universal online learning algorithms provided in this paper is valuable, and I increase my score to 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable time to give the insightful review. Below are our responses to the review.\n\n**Rebuttal to Weaknesses**\n\n> First, compared with stochastic (offline) optimization, the main challenge of online convex optimization (OCO) is how to deal with a fully adaptive adversary. However, this paper mainly focuses on SOCO, where the adversary is even weaker than the oblivious one, which is not very interesting to me.\n\nWe acknowledge that our approach cannot achieve a fast rate in fully adversarial environments.\nStill, note that our approach can achieve fast rates when the environment is stochastic while achieving $O(\\sqrt{T})$ in adversarial environments.\nFurthermore, please note that the conditions under which Follow the Leader (FTL) achieves fast rates are neither sufficient nor necessary for the conditions under which universal online learning achieves fast rates.\nInvestigating whether it is possible to achieve fast rates similar to FTL using universal online learning in adversarial environments is an important direction for future work.\n\n> ... in Section 4 of the existing work [8], Huang et al. have already proposed an adaptive algorithm to avoid the $\\Omega(T)$ regret of FTL, whose regret is at most $O(\\sqrt{T \\log T})$. The main idea is to utilize an expert tracking algorithm to combine FTL with an optimal algorithm for the general OCO. \nI also refer the authors to a missing related work [*], ..., which enjoys the same regret bound as the algorithm of Huang et al.\n> Anderson and Leith. Online Lazy Gradient Descent is Universal on Strongly Convex Domains. In NeurIPS 2021.\n\n\nWe apologize for not noticing and not mentioning Section 4 of Huang et al. [8] in the main text.\nIn the revised version, we will appropriately address this and revise the explanation in the introduction.\n\nWe also apologize for overlooking the paper by Anderson and Leith (2021). Thank you for bringing it to our attention.\nIn the revised version, we will thoroughly review its content and cite it appropriately.\n\n> Note that universal online learning algorithms utilized in this work follow a very similar idea of using the expert tracking algorithm. \n\nThank you for your insightful feedback.\nWe will mention the expert tracking algorithm in the revised version.\nStill, please note that our research focuses on identifying new conditions under which universal online learning can be accelerated, and we are not proposing a new algorithm.\n\n> it is easy to combine FTL with universal online learning algorithms. Without the analysis provided in this paper, one can simply prove that such a combination can achieve the regret of FTL for SOCO under ideal conditions, ...\n\nThank you for your valuable comments.\nIn fact, we were unable to combine FTL with universal online learning. If you have time, could you please explain how they can be combined?\nAdditionally, if there are any relevant references, we would appreciate it if you could share them.\nIn the framework of universal online learning (e.g., MetaGrad), different learning rates are set for the base learners and then integrated. Should we introduce a base learner corresponding to $\\eta \\to \\infty$ for FTL?\n\nStill, please note that the conditions under FTL achieves fast rates, $\\|g_1 + \\cdots + g_t \\| \\geq t L$ for some $L > 0$, are neither sufficient nor necessary for the conditions under which universal online learning achieves fast rates, $\\nabla f^\\circ(x_\\star) \\neq 0$.\nTherefore, even if FTL could be incorporated into universal online learning, it does not diminish the value of our contribution.\n\n> as discussed by the authors it is very similar to the Bernstein condition, which is more common and has been used to achieve a tighter regret bound for SOCO. \n\nAs you pointed out, when loss functions are linear, online linear optimization over a sphere-enclosed set satisfies the Bernstein condition, as discussed in Appendix H.\nHence, our research can also be seen as identifying new conditions under which the Bernstein condition is satisfied.\nHowever, it is important to note that the sphere-enclosed condition can only be reduced to the Bernstein condition when the underlying loss functions are linear, while our results apply to convex functions that are not necessarily linear.\n\n**Replies to Questions**\n> Can the authors summarize the fully new contributions compared with existing studies?\n\nOur contribution lies in identifying new conditions under which the framework of universal online learning can achieve fast rates.\nSpecifically, we introduced the new characterization of feasible sets called sphere-enclosed sets and demonstrated that fast rates can be achieved on these sets by universal online learning.\nOnline linear optimization over the sphere-enclosed set can be reduced to the Bernstein condition in the context of online linear optimization.\nStill, our results hold for more general convex loss functions.\nFurthermore, by extending the analysis for sphere-enclosed sets, we showed that universal online learning can achieve fast rates for more general sets, such as strongly convex sets and uniformly convex sets, and this result matches the existing lower bound.\n\n> In Theorem 14, the authors exploit the curvature of loss functions and feasible sets simultaneously. Are those regret bounds better than the existing regret bounds derived by only exploiting the curvature of loss functions?\n\nWhen the curvature of the feasible set is greater than the curvature of the loss functions, our results improve upon the existing regret upper bounds that only utilize the curvature of the loss functions.\n\nDue to space constraints, we will respond to the points that are considered to have a relatively small impact on the evaluation in the following Comments.", "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": "PkR8u1Fe9o", "reviewer": "Reviewer_BHA1", "summary": "- This paper studies online convex optimisation on feasible sets with curvature conditions. They introduce a new way to exploit the curvature of the feasible set through sphere enclosure. For feasible sets satisfying this condition, they leverage results from universal online learning to show that there exists algorithms whose regret is logarithmic in $T$ (for stochastic environments). \n- Compared to prior work, the conditions of curvature on the feasible set are more general, the losses are not restricted to be linear (and conditions such as strong convexity of the losses can be simultaneously exploited) and a growth condition on the gradients is not needed. These results are also extended to stochastic corrupted environments. \n- For feasible sets that are uniformly convex, they show that there exists algorithm which can achieve regret bounds interpolating between the $\\log T$ rate of strongly-convex sets (q=2) and the $\\sqrt{T}$-rate of sets without curvature ($q \\rightarrow \\infty$) (in stochastic environments) while prior work suffered linear in $T$ regret when $q \\rightarrow \\infty$.", "questions": "Some questions are asked in the weaknesses above.\n- In Corollary 12, do you think the dependence on $GD$ can be removed? Would it be possible to adjust the lower-bound so that these also appear ?\n- The upper bound in Theorem 10 is shown to be tight in the case of $K = W_\\lambda$ with $d=2$. Is there any dimension dependence that is hidden in some of the terms in the bound of Theorem 10 ? And could these be shown to be necessary by considering the lower-bound on $W_\\lambda$ in higher dimensions ?\n- For the result on uniformly convex sets, it is mentioned that a similar analysis is possible for corrupted stochastic environments. Without necessarily giving the details of the analysis (which I realise might be quite similar to the one already given), it would be nice to include a statement of the result in this case or at least what the dependence on the corruption level $C$ is in the bound and a bit of a discussion of this. In particular so that the reader can get an idea of the result in the fully adversarial setting when $C = T$ (which is the setting [10] consider it seems) and whether the $\\log T$-$\\sqrt{T}$ interpolation still holds in this case.", "limitations": "In general yes, though it is not necessarily apparent that in the fully adversarial setting, the results do not improve upon FTL.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Sphere-enclosure, a new interesting characterisation of the feasible set is introduced, which allows to obtain $\\log T$ regret with improvements with respect to prior work (see Summary) that are clearly explained. Sphere-enclosure captures previously considered sets with curvature as well as some other more general ones. Helpful figures are also provided to help understand and visualise sphere-enclosure.\n- The theoretical contributions are strong with upper and matching lower-bounds. \n- Exploiting the framework of universal online learning allows proofs that are generally simple to follow.\n- For uniformly convex sets, the interpolation of $\\log T$ and $\\sqrt{T}$ rates closes a gap left by prior work (in stochastic environments).", "weaknesses": "- The improvement over FTL is mostly in the stochastic environment. In Theorem 13, if we consider the fully adversarial environment ($C=T$) for example, then the regret is $\\sqrt{T}$ and the $\\log T$ results for FTL are not improved on. Do you believe this is a fault in the analysis or that something beyond the universal online learning conditions are required ?\n- Many of the results work with the $\\ell_2$-norm and it is not clear what the results would be when working with respect to an arbitrary norm $||\\cdot||$. In particular, it would be nice to at least have a discussion of if/how these results could be extended to arbitrary norms. It also seems that considering the euclidean ball in Definition 5 means that $\\ell_p$-balls for $p > 2$ are not sphere-enclosed sets. It would be good to have a discussion of the relationship between uniformly convex sets and sphere-enclosed sets as well as a discussion on how the results from Section 4.1 link to the results in Section 4.4.\n- The generality of the assumption of sphere-enclosure of the feasible set is well motivated (what is the mild condition on $\\nabla f^{\\circ}(x_\\star)$ in line 231 ?). But the assumption that $x^\\star$ is on the boundary of $K$ could be discussed further. In particular, it is only justified for linear losses. Perhaps a slightly more developed discussion of this could help (or/and more pointers to the literature). Moreover, it would be nice to have an explanation of why this assumption is needed - is it just to guarantee $||\\nabla f^{\\circ}(x_\\star)||_2 \\neq 0$?\n\nSome sections are slightly unclear and a bit confusing:\n- In the statement of Theorem 9, it is stated that $T \\geq C/(\\lambda L)^2$ (which is also stated in line 195) but in the proof the steps are: $T \\geq C/(\\lambda L) \\geq 1/(\\lambda L)^2$, which seems to suggest the condition is $T \\geq C/(\\lambda L)$ - is there a typo ? Furthermore, it is not clear why if the assumption does not hold, the lower-bound becomes vacuous ? Is it that the lower-bound of Theorem 8 then dominates the lower-bound of Theorem 9 ? In addition, the key step in line 207 seems to be that $|L-\\hat{L}|/L| \\leq 1$, which is not the step that is explained and seems non-trivial. In line 211 a square root appears on the ln term in the second inequality but is not present in the inequality before and after ? And then the final result in Theorem 9 has a square root on the ln term again making things quite confusion (and this seems to contribute to the confusion around the bound becoming vacuous compared to Theorem 8). Finally, beside the issue around the square-root on the ln term, it seems that Theorem 9 follows from line 211 by taking the average of the final two inequalities (of line 211) and if so this could be explicitly stated for clarity. Overall, this part is quite confusing and could be made clearer.\n- In line 224-225, you use the notation $x_t$ to discuss the definition of $B_\\gamma^K$ but $x_t$ is the notation used for the point played by the algorithm at time step $t$. It is unclear why this notation is used here (similarly for $\\nabla f^{\\circ}(x_t)$ in the statements of Theorem 8 and 9).\n- In line 249, the assumption on the loss vectors refers to the growth condition assumptions from line 42 ? If so, this could be made clearer, for example just adding “growth” in front of assumptions. This is discussed 2 paragraphs down but it is not necessarily clear at this point.\n- Line 251-254: am I correct in understanding that your approach guarantees a $O(\\sqrt{T})$ regret even in the adversarial setting because it satisfies the universal online learning condition ? If so, it would be nice to make this more explicit.\n\nTypos:\n- Line 222 missing a “the” in front of inequality. \n- Line 219, missing a “the” in front of ball.\n- Line 245: typo “$x_\\star$ in on corners\" ?\n- Line 30, the definition of the regret $R_T$ is written with $f_t(x)$ and not $f_t(x_\\star)$. A similar point for line 102 - perhaps defining the regret directly w.r.t. $x_\\star$ would make the notation clearer instead of with respect to an arbitrary point $x$ without making this dependence explicit in the notation $R_T$.\n- line 147: missing \"a\" in front of \"convex body K\".\n- Line 287: missing “the” in front of ball. \n- Line 286: \"for this $\\tilde{B}^K_\\gamma$\" is at the start of a sentence but not capitalised and $\\tilde{B}^K_\\gamma$ is not defined yet.\n- Line 20: you state that uniformly convex sets include $\\ell_p$-balls for $p \\in [1, \\infty)$ but this should be for $p \\in [2, \\infty)$ I think. (same issue in line 78).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable time and thorough review. We will correct the minor comments and typos in the revised version. Here are our responses to the review.\n\n**Rebuttal to Weaknesses**\n\n> The improvement over FTL is mostly in the stochastic environment. In Theorem 13, if we consider the fully adversarial environment ($C=T$) for example, then the regret is $\\sqrt{T}$ and the $\\log T$ results for FTL are not improved on. Do you believe this is a fault in the analysis or that something beyond the universal online learning conditions are required ?\n\nWhen the environment is completely adversarial, it is unclear whether the regret of $\\sqrt{T}$ is due to a fault in the analysis or if additional assumptions are needed for universal online learning.\nExploring this is an important direction for future work.\nHowever, it is important to note that the conditions under which FTL achieves fast rates and the conditions under which universal online learning achieves fast rates are neither sufficient nor necessary for each other.\nFTL can achieve fast rates under the assumption of the growth condition $\\\\|g_1 + \\dots + g_t\\\\| \\geq tL$ for some $L > 0$, which is neither a sufficient nor necessary condition $\\nabla f^\\circ(x^*) \\neq 0$, under which universal online learning to achieve fast rates.\n\n> Many of the results work with the $\\ell_2$-norm and it is not clear what the results would be when working with respect to an arbitrary norm $\\\\|\\cdot\\\\|$. \nIn particular, it would be nice to at least have a discussion of if/how these results could be extended to arbitrary norms.\nIt also seems that considering the Euclidean ball in Definition 5 means that $\\ell_p$-balls for $p > 2$ are not sphere-enclosed sets. It would be good to have a discussion of the relationship between uniformly convex sets and sphere-enclosed sets as well as a discussion on how the results from Section 4.1 link to the results in Section 4.4.\n\nExtending the sphere-enclosed condition to an arbitrary norm $\\\\|\\cdot\\\\|$ is challenging because the sphere-enclosed condition leverages the fact that the enclosing ball is an Euclidean ball.\n\nHowever, our result for uniformly convex sets (Theorem 15) holds for general norms, making this a very general result.\nIt is worth noting that the result of Theorem 15 corresponds to the result for sphere-enclosed sets when $q = 2$ and $\\\\|\\cdot\\\\|$ is the Euclidean norm.\nAdditionally, Theorem 15 does not require the feasible set $K$ to be globally \"curved.\"\nIn fact, Theorem 15 only uses the inequality \n$\\langle \\nabla f^\\circ(x\\_\\star), x - x\\_\\star \\rangle \\geq \\frac{\\kappa}{4} \\\\| x - x_\\star \\\\|^q \\cdot \\\\|\\nabla f^\\circ(x\\_\\star) \\\\|\\_\\star$ for all $x \\in K$, which describes the local curvature around the optimal solution $x_\\star$.\nIn the revised version, we will discuss these points in detail.\n\n> The generality of the assumption of sphere-enclosure of the feasible set is well motivated (what is the mild condition on $\\nabla f^\\circ(x_\\star)$ in line 231 ?). However, the assumption that $x_\\star$ is on the boundary of $K$ could be discussed further. \nIn particular, it is only justified for linear losses. Perhaps a slightly more developed discussion of this could help (or/and more pointers to the literature). Moreover, it would be nice to have an explanation of why this assumption is needed - is it just to guarantee?\n\nThe mild condition on $\\nabla f^\\circ(x_\\star)$ in line 231 refers to Condition (iii) of the sphere-enclosed set definition (Definition 5).\nWhen the feasible set $K$ is a polytope, if $\\nabla f^\\circ(x_\\star)$ is aligned with the direction parallel to the face of the polytope passing through $x_\\star$, it becomes impossible to enclose $K$ with a sphere passing through $x_\\star$.\nTherefore, such a polytope is not sphere-enclosed.\nIn the revised version, we will add an explanation with a figure to illustrate this point and clarify the description in line 231.\n\nAdditionally, the assumption $\\nabla f^\\circ(x_\\star) \\neq 0$ is common in offline optimization, as discussed in lines 255-259. Although we do not yet have a complete intuition for this, we believe that $\\\\| \\nabla f^\\circ(x\\_\\star)\\\\|$ serves a similar role to the minimum suboptimality gap in the bandit problem.\nWe will try to include it as much as possible in the revised version.\n\n> In the statement of Theorem 9, it is stated that $T \\geq C / (\\lambda L)^2$ (which is also stated in line 195) ..., is there a typo ?\n\nThank you for pointing this out. We apologize for the typo; as the reviewer pointed out, it should be $T \\geq C / (\\lambda L)$.\n\n>  the key step in line 207 seems to be that $|L - \\hat{L}| / L \\leq 1$, which is not the step that is explained and seems non-trivial.\n\nFrom the discussion in lines 199-120, we have $L \\geq \\hat{L} (> 0)$. Therefore, $|L - \\hat{L}| / L = L / L = 1$.\nIn the revised version, we will clarify this point.\n\n> In line 211 a square root appears on the ln term in the second inequality but is not present in the inequality before and after ?\n\nThank you for pointing this out. We apologize for the error; the square root in $\\ln(\\cdot)$ in the second inequality is unnecessary. We will correct this in the revised version.\n\nDue to space constraints, we will respond to the points that are considered to have a relatively small impact on the evaluation in the following Comments.", "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: This paper considers how to achieve fast rates in stochastic environments of online convex optimization by exploiting the curvature of feasible sets. The authors present various interesting results, including leveraging the nice results from universal online learning. All the reviewers unanimously appreciate these new contributions! 

Nevertheless, one (expert) reviewer raised valid concerns about the paper presentation and also proposed several technical discussions, such as the potential triviality of combining FTL with existing universal online algorithms (though we all realized that it is not easy to achieve so after back-and-forth discussions). The authors are encouraged to revise the manuscript to reflect this point and incorporate all the constructive comments from the reviewers. 

Two additional comments after my own reading of the paper:

- The NeurIPS’16 paper "Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning" also provides fast-rate implications for stochastic OCO/PEA with the "second-order regret bound" (achieved by MetaGrad or Squint), which should be discussed more carefully.

- It's interesting to see the authors considering extending these results to the SEA model. The gradient-variation universal online learning algorithms (such as NeurIPS’23 Universal Online Learning with Gradient Variations) could be useful.
Decision: Accept (poster)