Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets

Authors: taira  tsuchiya
shinji  ito
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 15:10:25

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$).

Main paper: 
 introduction: 
 This paper considers online convex optimization (OCO), a framework in which a learner and an environment interact in a sequential manner. At the beginning, a convex body (or feasible set) K ⊆ R d is given. At each round t ∈ [T ] := {1, . . . , T }, the learner selects a decision x t ∈ K from the convex body K using information obtained up to round t -1. Then, the environment determines a convex loss function f t : K → R, and the learner suffers loss f t (x t ) and observes ∇f t (x t ) ∈ R d . The goal of the learner is to minimize the regret, which is the expectation of the difference between the cumulative loss of decisions (x t ) T t=1 and that of a single optimal decision x ⋆ fixed in hindsight, that is, R T = E T t=1 (f t (x t ) -f t (x ⋆ )) for x ⋆ = arg min x∈K E T t=1 f t (x) . OCO is called online linear optimization (OLO) when (f t ) t are linear functions, i.e., f t (•) = g t , • for some g t ∈ R d .In OCO and OLO, the well-known online gradient descent (OGD) achieves an O( √ T ) regret upper bound for Lipschitz continuous f t [27] . In general, this upper bound cannot be improved and is known to match the Ω( √ T ) regret lower bound [8] . However, this lower bound can be circumvented under certain conditions. The most typical way is to exploit the curvature of loss functions. It is known Table 1 : Comparison of our regret upper bounds with existing bounds. All bounds assume that loss functions are G-Lipschitz (except Lines 1-3) and x⋆ is on the boundary of K. The upper bounds that contain the variable L > 0 assume ∥g1 + • • • + gt∥2 ≥ tL for all t ∈ [T ]. We use f • = E f ∼D [f ], C ≥ 0 is the corruption level, and the Ω notation ignores logarithmic factors. The (κ, 2)-uniformly convex set is κ-strongly convex. Theorem is abbreviated as as Thm, Corollary as Cor, and sphere-enclosed as sphere-enc. Note that regret bounds proven in this study can be simultaneously achieved by the same algorithm with identical parameters.Feasible set Loss functions Regret bound [9] , This work ( [11] (κ, q)uniformly convex adversarial, linearO G q q-1 (κL) 1 q-1 T q-2 q-1This work (Thm 15) stochastic, convexO G q q-1 (κ∥∇f • (x⋆)∥⋆) 1 q-1 T q-22(q-1) (ln T ) q 2(q-1)that OGD with a learning rate of Θ(1/t) and online Newton step (ONS) can achieve an O( 1 α ln T ) and O( d β ln T ) regret for α-strongly-convex and β-exp-concave loss functions, respectively [8] . Another way to circumvent the lower bound is to harness the curvature of the feasible set K. Existing studies proved that in OLO if the feasible set is curved and loss vectors g t are biased towards a specific direction, the follow-the-leader (FTL) algorithm can achieve a logarithmic regret. In particular, Huang et al. [9] first proved that under the growth condition that there exists L > 0 such that g 1 + • • • + g t 2 ≥ tL for any t ∈ [T ], FTL achieves an O( G 2 λL ln T ) regret for λ-strongly convex K and G-Lipschitz loss functions. This bound matches their lower bound of Ω( 1 λL ln T ). Molinaro [17] also proves that FTL can achieve a logarithmic regret under the different assumption on the loss vectors that g t ≤ 0 for all t ∈ [T ], providing an intuitive and simple proof.Their approach, however, has several remaining limitations. First, they only consider OLO. While the linearization 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 is a rather limited condition. Finally, some of their approach suffers an Ω(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 expert tracking algorithm in [9, Section 4] , in which FTL is combined with follow-the-regularized-leader, 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 functions [21, 22, 24] , also known as 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 functions, e.g., parameters of strong convexity or exp-concavity, without knowing them. The crux of their analysis is to derive a bound ofT t=1 ∇f t (x t ), x t -x ⋆ = O T t=1 x t -x ⋆ 22 ln T .We introduce a 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 withT t=1 ∇f t (x t ), x t - x ⋆ = O c sc T t=1 x t -x ⋆ 2 2 ln T for some c sc > 0 achieves R T = O c 2 sc ρ ∥∇f • (x⋆)∥2 ln T in stochastic environments, where f • = E ft [f t ]and ρ > 0 is the smallest radius of a sphere that includes x ⋆ and encloses K. The same algorithm achievesR T = O(ρ ln T + √ Cρ ln T ) in corrupted stochastic environments for corruption level C and R T = O( √ T ) 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) . (ii) Even in worst cases, where the specific conditions on loss vectors, such as the growth condition, are not satisfied, an O( √ T ) regret upper bound can be achieved. (iii) The local structure of K around optimal decision x ⋆ is sufficient for our approach to achieve the logarithmic regret. As a further advantage, our approach can achieve an O(ρ ln T + √ Cρ ln T ) regret bound for corrupted stochastic environments with corruption level C ≥ 0, which are intermediate environments between stochastic and adversarial environments (Theorem 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 ℓ p -balls for p ∈ [2, ∞). For q-uniformly convex K, Kerdreux et al. [11] proves an regret bound of O T q-2 q-1 , which is smaller than O( √ T ) only when q ∈ (2, 3). We improve this bound by proving the following upper bound, which matches the lower bound in [2] : Theorem 2 (informal version of Theorem 15) . In online convex optimization with q-uniformly convex feasible set K, the same algorithm as Theorem 1 achieves R T = O T q-2 2(q-1) (ln T ) q 2(q-1) . This becomes a fast rate for any q > 2 and is strictly better than the bound in [11] . Our bound interpolates between the O(ln T ) bound for strongly convex sets (when q = 2) and the O( √ T ) bound for non-curved feasible sets (when q → ∞). Table 1 summarizes the regret comparison.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, we claims that we consider online convex optimization and introduce a new approach and analysis for achieving fast rates over curved feasible sets. 
preliminaries: 
 Let e i ∈ {0, 1} d be the i-th standard basis of R d , and 1 be the all-one vector. For p ∈ [1, ∞] and vector x, let x p be ℓ p -norm. Let ξ > 0 be a constant satisfying x 2 ≤ ξ x for any x ∈ R d . For a norm • , we use x ⋆ = sup{ x, y : y ≤ 1} to denote its dual norm. Let B ∥•∥ (x, r) be a ball with radius r centered at x associated with • , i.e., B ∥•∥ (x, r) = {z : z -x ≤ r}. We use B(x, r) to denote the Euclidean ball with radius r centered at x and B ∥•∥ to denote the unit ball. Let bd(K) be the boundary ofK. A function f : R d → (-∞, ∞] is convex if for all x ∈ int dom f , f (y) ≥ f (x) + ∇f (x), y -x for all y ∈ R d . 1 For α > 0, f : K → (-∞, ∞] is α-strongly convex over K ⊆ dom f w.r.t. • if for all x, y ∈ K, f (y) ≥ f (x) + ∇f (x), y -x + α 2 x -y 2 . For β > 0, f : K → (-∞, ∞] is β-exp-concave if exp(-βf (x)) is concave.We consider online convex optimization (OCO). In OCO, a convex body (or feasible set) K ⊆ R d is given before the game starts. Let D = max x,y∈K x -y 2 be the diameter of K. At each round t ∈ [T ], the learner selects a decision x t ∈ K using information obtained up to round t -1, and a convex loss function f t : K → R is determined by the environment. The learner then suffers a loss f t (x t ) and observes ∇f t (x t ) ∈ R d . The goal of the learner is to minimize the regret, which is defined asR T = E T t=1 (f t (x t ) -f t (x ⋆ )) for the optimal decision x ⋆ = arg min x∈K E T t=1 f t (x) .When loss functions are restricted solely to linear functions, that is, when f t (•) = g t , • for some g t ∈ R d , OCO is referred to as online linear optimization (OLO).In this study, we assume that f t is G-Lipschitz, i.e., sup x∈K ∇f t (x) 2 ≤ G. In the following, we list three assumptions on how a sequence of f 1 , . . . , f T is generated. In stochastic environments, f t is sampled in an i.i.d. manner from a certain probability distribution D. The expectation of f t is denoted asf • = E f ∼D [f ].In adversarial environments, f t is arbitrarily determined depending on the past history, and f t may depend on x t . 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 t ∈ [T ], ft ∼ D is obtained according to a certain distribution D, where the expectation of ft is defined byf • = E f ∼ D [ f ].Then, possibly depending on ft and the past history, loss function f t is determined by the environment so thatE T t=1 f t -ft ∞ ≤ C, where E T t=1 f t -ft ∞ is the corruption level.In this paper, we consider these three environments.We start by introducing the definition of strongly and uniformly convex sets. We then define a new notion of convex bodies, sphere-enclosed set, for which we can also achieve the fast rates of O(ln T ). We finally discuss the existing lower bound when exploiting the curvature.One common way to describe the curvature of a convex body is with the following strong convexity.Definition 3. A convex body K is λ-strongly convex w.r.t. a norm • if for any x, y ∈ K and any θ ∈ [0, 1], it holds that θx + (1 -θ)y + θ(1 -θ) λ 2 x -y 2 • B ∥•∥ ⊆ K .For example, ℓ p -balls for p ∈ [1, 2] ∈ [0, 1], it holds that θx + (1 -θ)y + θ(1 -θ)κ x -y q • B ∥•∥ ⊆ K .For [11] and Appendix H for the connection between the uniform convexity of a normed space and the uniform convexity of sets.) Note that (κ, 2)-uniformly convex sets are κ-strongly convex. In this paper, we introduce a new, different characterization of convex bodies.Definition 5 (sphere-enclosed sets). Let K ⊆ R d be a convex body, u ∈ bd(K), and f : K → R. Then, K is (ρ, u, f )-sphere-enclosed (or simply sphereenclosed facing u) if there exists a sphere of radius ρ that has u on it, encloses K, and the gradient of f at point u is directed towards the center of the sphere. That is, there exists a ball B(c, ρ) with c ∈ R d and ρ > 0 satisfying (i) u ∈ bd(B(c, ρ)), (ii) K ⊆ B(c, ρ), and (iii) there exists r 0 > 0 such that u + r 0 ∇f (u) = c. 2One might think that the sphere-enclosed condition is complicated but Condition (iii) in Definition 5 is only for the case when x ⋆ 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 is sphere-enclosed facing x (the red dotted line is the minimum sphere facing x), but K is not sphere-enclosed facing y. In the right figure, we can see that K is sphere-enclosed facing z (the blue dotted line is the minimum sphere facing z for K). Note that the notion of sphere-enclosedness is a 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 is sphere-enclosed facing at optimal decision x ⋆ .Here, we discuss a lower bound when exploiting the curvature of feasible sets. For λ ∈ (0, 1), let W λ = {(x, y) ∈ R 2 : x 2 + y 2 /λ 2 ≤+ • • • + g t 2 ≥ tL for all t ∈ [T ] such that R T ≥ 1 84 √ 2 1 λL ln T -δ for δ = 1 λL 2 1-e λ 2 L 2 + π 2 108 .In their proof, they use the following sequence of linear functions f t (•) = h L t , • . Let P be a random variable following a Beta distribution, Beta(k, k), for some k > 0. For this P , let (X t ) T t=1 be i.i.d. random variables following a Bernoulli distribution with parameter P . Then for L ∈ (0, 1),let h L t = (2X t -1, -L), which indeed satisfies the growth condition h L 1 + • • • + h L t 2 ≥ tL for all t ∈ [T ]. This construction of loss functions will be exploited to prove lower bounds in Section 3, and we will provide a matching upper bound in Corollary 12.Our algorithm is based on 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 an (efficient) algorithm such that T t=1 ∇f t (x t ), x t -x ⋆ is bounded from above by the order ofEQUATION) where c sc , c ′ sc , c ec , c ′ ec , c g > 0 are algorithm dependent variables provided in the following. 3For example, upper bound (1) can be achieved by the MetaGrad algorithm with c sc = G √ d, c ′ sc = d, c ec = √ d, c ′ ec = d,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 in Table 1 in the introduction, after Theorems 10 and 15, and in Appendices C and I.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
regret lower bounds: 
 In this section, we construct lower bounds that align with the assumptions of our regret bounds. Considering a sequence of loss functions to construct the lower bound in Theorem 6, we can immediately obtain the following lower bound.Theorem 8. Consider online linear optimization. Let λ, L ∈ (0, 1) and K = W λ . Then, for any algorithm, there exists a stochastic sequence of loss functions f 1 , . . . , f T satisfyingf t (•) = g t , • , g 1 , . . . , g T ∈ {(1, -L), (-1, -L)}, and ∇f • (x ⋆ ) 2 = L such that R T ≥ 1 84 √ 2 1 λ∥∇f • (x⋆)∥ 2ln Tδ, where δ is defined in Theorem 6.Proof. Consider the sequence of loss vectors h L 1 , . . . , h L T after Theorem 6 and letf t (•) = h L t , • for all t ∈ [T ]. For this sequence of (f t ) T t=1 , it holds that ∇f • (x t ) 2 = E h L t 2 = (0, -L) 2 = L = 0, which completes the proof.With this lower bound, we have the following lower bound for corrupted stochastic environments. Theorem 9. Consider online linear optimization. Let λ, L ∈ (0, 1) and K = W λ . Suppose that T ≥ C/(λL) 2 and C ≥ 1/(λL). Then, for any algorithm, there exists a corrupted stochastic environment with corruption level at mostC ≥ 0 satisfying ∇f • (x ⋆ ) 2 = L such that R T ≥ 1 168 √ 2 1 λ ∇f • (x t ) 2 + C λ ∇f • (x t ) 2 ln C λ ∇f • (x t ) 2 -δ ,where δ is defined in Theorem 6.The assumption that T ≥ C/(λL) 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 (f t ) T t=1 in a corrupted stochastic environment, where (f t ) t are generated so that ft (•) = gt , • with g1 , . . . , gT following a distribution D and f t is a corrupted function of ft .We first note that we haveT ≥ C/(λL) ≥ 1/(λL) 2 . Define L > 0 such that λ L = λL/C. Note that since C ≥ 1/(λL), we have λ L ≤ λL, implying that L ∈ (0, 1). We also define τ := 1/(λ L) 2 = C/(λL) ≤ T , which follows from λ L = λL/C and T ≥ C/(λL).With these definitions, we then consider the following corrupted stochastic environments:• For t ∈ {1, . . . , τ }, define ft by ft (•) = gt , • for gt = h L t ,where h L t is defined after Theorem 8, and define loss functionf t by f t (•) = g t , • with g t = h L t . • For t ∈ {τ + 1, . . . , T }, let ft (•) = f t (•) = g t , • with g t = h L t ,where there is no corruption. In fact, the corruption level of this environment is bounded by C sinceT t=1 E f t -ft ∞ = τ t=1 E sup x∈K | g t -gt , x | ≤ τ |L -L|λ ≤ C/(λL) • |L -L|λ ≤ C,where in the first inequality we used the fact that the first elements of g t and gt are the same and that K = W λ and in the second inequality we used L ≥ L > 0. This implies that the sequence of (f t ) T t=1 is a corrupted stochastic environment with the corruption level at most C.Hence, from Theorem 8 with L ∈ (0, 1), λ L = λL/C, and the definition of τ , the regret is bounded from below asR T ≥ 1 84 √ 2 1 λ L ln τ -δ ≥ 1 84 √ 2 C λL ln C λL -δ ≥ 1 84 √ 2 1 λL ln C λL -δ.Taking the average of the last two inequalities completes the proof. Note that our lower bounds are not for general sphere-enclosed feasible sets, and establishing a new lower bound is important future work.x ⋆ ∇f • (x⋆) x⋆ + 1 2γ⋆ ∇f • (x⋆) B K γ⋆ K Figure 2:The region enclosed by the black solid line is feasible set K and the red dotted line B K γ⋆ is the smallest sphere enclosing K and facing x⋆.We provide logarithmic regret for stochastic environments. Define the ball B K γ ⊆ R d for γ > 0 byB K γ = B x ⋆ + 1 2γ ∇f • (x ⋆ ) , 1 2γ ∇f • (x ⋆ ) 2 . (2)By the definition, we have x ⋆ ∈ bd(B K γ ). See Figure 2 . Remark 1. The ball B K γ is determined in the following manner. We will see in the following proof that the inequality ∇f• (x ⋆ ), x -x ⋆ ≥ γ x -x ⋆ 22 that holds for some γ > 0 and any action x plays a key role in proving a logarithmic regret. This inequality is equivalent tox -x ⋆ + 1 2γ ∇f • (x ⋆ ) 2 ≤ 1 2γ ∇f • (x ⋆ ) 2 and we define B K γ as the set of all x ∈ R d satisfying this inequality. Using this B K γ , we let γ ⋆ = sup{γ ≥ 0 : K ⊆ B K γ }.Then, we can prove the following theorem. Theorem 10. Consider online convex optimization in stochastic environments, where the optimal decision isx ⋆ = arg min x∈K f • (x). Suppose that K is (ρ, x ⋆ , f • )-sphere-enclosed and that ∇f • (x ⋆ ) = 0.Then, any algorithm with the bound (1) achieves The assumption that K is sphere-enclosed around x ⋆ is satisfied for many typical feasible sets. It holds if the feasible set K is a ball, or a polytope with a mild condition on ∇f • (x ⋆ ). Specifically, the condition ∇fR T = O c 2 sc γ ⋆ ln T + c ′ sc ln T = O c 2 sc ρ ∇f • (x ⋆ ) 2 ln T + c ′ sc ln T . int(-NK (x⋆)) x ⋆ K undesirable direction of ∇f • (x⋆)• (x ⋆ ) ∈ int(-N K (x ⋆ )) is sufficient to ensure that the feasible K is sphere-enclosed around x ⋆ , where -N K (x ⋆ ) = {g ∈ R d : g, x -x ⋆ ≥ 0 ∀x ∈ K} is the negative normal cone.This condition is mild since, from the optimailty condition of x ⋆ , we have∇f • (x ⋆ ) ∈ -N K (x ⋆ ).Hence the undesirable case is restricted to ∇f • (x ⋆ ) ∈ bd(-N K (x ⋆ )) (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 are 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 8 in the environment used to construct the lower bound.Proof. The regret is bounded from below byR T = E T t=1 (f • (x t ) -f • (x ⋆ )) ≥ E T t=1 ∇f • (x ⋆ ), x t -x ⋆ ≥ E T t=1 γ ⋆ x t -x ⋆ 2 2, where the first inequality follows from the convexity of f • , and the last inequality follows from x t ∈ K ⊆ B K γ⋆ and the definition of γ ⋆ . By combining this inequality with inequality (1), the regret is bounded asR T ≤ E T t=1 ∇f t (x t ), x t -x ⋆ = O c sc R T γ⋆ ln T + c ′ sc ln T . Solving this inequation w.r.t. R T , we get R T = O c 2 sc γ⋆ ln T + c ′ sc ln T . Observing that 1 2γ⋆ ∇f • (x ⋆ ) 2 = ρ, which holds from the as- sumption that K is (ρ, x ⋆ , f • )-sphere-enclosed, 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 x ⋆ is on corners (see Figure 1 ), while the existing analysis requires strong convexity over the entire feasible set K. (ii) 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). (iii) Even if the growth assumptions on loss vectors g 1 , . . . , g T are not satisfied, the O( √ T ) regret upper bound can be achieved in adversarial environments, while the existing approach, FTL, can suffer Ω(T ) regret.A limitation of the proposed approach is that it assumes stochastic environments. However, our approach at least guarantees an O( √ T ) 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 in 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 g t : There exists L > 0 such thatg 1 +• • •+g t 2 ≥ tL for all t ∈ [T ], or g t ≤ 0 for all t ∈ [T ].These assumptions cannot be directly comparable with our assumption that ∇f • (x ⋆ ) = 0. Note that the assumption that inf x∈K ∇f • (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 sphereenclosed condition leverages the fact that the enclosing ball is a Euclidean ball. However, we will see in Section 4.4 that fast rates for uniformly convex sets can be achieved for general norms (Theorem 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 identifying a new 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 I for a detailed comparison between the sphere-enclosed condition and the Bernstein condition.In the remainder of this subsection, we investigate 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 λ ∈ (0, 1), let W λ be the ellipsoid defined in Section 2.3.2. Then, its minimum enclosing sphere S such that (0, -λ) ∈ S is S = {(x, y) ∈ R 2 : x 2 + [y -(1 -λ 2 )/λ] 2 = 1/λ 2 } .The proof of Proposition 11 is deferred to Appendix B. This result immediately implies the following: Corollary 12. Let K be W λ 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 in [24] achievesR T = O 1 λL ln T + GD ln T .This upper bound matches the lower bound in Theorem 8 up to the additive GD ln T factor.Proof. From Proposition 11 and the fact that Euclidean ball with radius r is 1/r strongly convex w.r.t. • 2 , we have ρ = 1/λ. This proposition with Theorem 10 gives the desired bound.The upper bound in Theorem 10 is applicable when K is a polytope. We will see that our approach work also in the corrupted stochastic environment in Section 4.2, and to our knowledge, this is the first upper bound that achieves fast rates when the feasible set is a polytope in non-stochastic environments. A further discussion when K is a polytope can be found in Appendix C.Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 in appendix. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced.• 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 to provide a 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. 
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 γ > 0, we define ballB K γ ⊆ R d by B K γ = B x ⋆ + 1 2γ ∇ f • ( x ⋆ ) , 1 2γ ∇ f • ( x ⋆ ) 2, which is defined in the same manner as B K γ . For this BK γ , we letγ ⋆ = sup{γ ≥ 0 : K ⊆ B K γ }.Then, we can prove the following regret upper bound. Theorem 13. Consider online convex optimization in corrupted stochastic environments with corruption level at most C, wherex ⋆ = arg min x∈K f • (x). Suppose K is (ρ, x ⋆ , f • )-sphere enclosed and ∇ f • ( x ⋆ ) = 0.Then, any algorithm with the bound (1) achievesR T = O c 2 sc γ ⋆ ln T + Cc 2 sc γ ⋆ ln T + c ′ sc ln T = O c 2 sc ρ ∇ f • ( x ⋆ ) 2 ln T + Cc 2 sc ρ ∇ f • ( x ⋆ ) 2 ln T + c ′ sc ln T .The proof of Theorem 13 can be found in Appendix D. One can see that this upper bound matches the lower bound in Theorem 9 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.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. Iff 1 , . . . , f T are α-strongly convex w.r.t. a norm • , then R T = O c 2 sc γ⋆+α/ξ ln T + c ′ sc ln T . If f 1 , . . . , f T are β-exp-concave, then R T = O min c 2 sc γ⋆ , c 2 ec β ′ +γ⋆/G 2 ln T + max{c ′ sc , c ′ ec } ln T for β ′ ≤ 1 2 min 1 4GD , β .The proof can be found in Appendix E. Theorem 14 implies that one can simultaneously exploit the curvature of feasible sets and loss functions.Here, we prove that a regret bound smaller than O( √ T ) can be achieved when K is uniformly convex. This can be proven by a 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 min x∈K f • (x). Suppose that K is (κ, q)-uniformly convex w.r.t. a norm • for some q ≥ 2 and that ∇f • (x ⋆ ) = 0. Then, any algorithm with bound (1) achievesEQUATION)In particular, when K is λ-strongly convex w.r.t.• , R T = O ξcsc λ∥∇f • (x⋆)∥⋆ ln T + c ′ sc ln T .The dependence on T in this bound is O T q-2 2(q-1) (ln T )q 2(q-1), which becomes O(ln T ) when q = 2 and Õ( √ T ) when q → ∞, and thus interpolates between the bound over the strongly convex sets and non-curved feasible sets. This is strictly better than the O T q-2 q-1 bound in [11] ; their regret upper bound is better than O( √ T ) only when q ∈ (2, 3). Notably, our bound matches the existing lower bound of Ω T q-2 2(q-1)proven for a stochastic environment withd = 2 [2, Theorem C.1]. For example, when K is ℓ p -ball, by x 2 ≤ d 1 2 -1 p x p for any x ∈ R d and p > 2, the regret is bounded as R T = O (ξcsc) p p-1 d p-2 2(p-1) (∥∇f • (x⋆)∥⋆) 1 p-1 T p-2 2(p-1) (ln T ) p 2(p-1) + c ′ sc ln T .It is worth noting that the result of Theorem 15 corresponds to the result for sphere-enclosed sets when q = 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 ∇f• (x ⋆ ), x -x ⋆ ≥ κ 4 x -x ⋆ q • ∇f • (x ⋆ )⋆ for all x ∈ K, which describes the local curvature around the optimal solution x ⋆ .Before proving Theorem 15, we present the following lemma, which offers a characterization of uniformly convex sets. This directly follows from the definition in Definition 4: Lemma 16. Suppose that a convex body K is (κ, q)-uniformly convex w.r.t. a norm • for κ > 0 and q ≥ 2. Let y ∈ K, g ∈ R d , and y ⋆ ∈ arg min y ′ ∈K g, y ′ . Then, -g, y ⋆ -y ≥ κ 4 y -y ⋆ q • g ⋆ .The proof can be found in [12, Lemma 2.1], and we include the proof in Appendix F for completeness.Proof of Theorem 15. From x ⋆ = arg min x∈K f • (x) and the first-order optimality condition, ∇f • (x ⋆ ), x -x ⋆ ≥ 0 for all x ∈ K, which implies that x ⋆ = arg min x∈K ∇f • (x ⋆ ), x . Hence, by combining this with Lemma 16 and that K is (κ, q)-uniformly convex w.r.t. a norm • , we have ∇fEQUATION)where the first inequality follows from the convexity of f • , the second inequality by x 2 ≤ ξ x for any x ∈ R d , and the last inequality by Jensen's inequality and the fact that x → x q/2 is convex for q ≥ 2. Combining ( 1) and ( 4), we can bound the regret asEQUATION)where in the last line we used the inequality a √ x -bx q/2 ≤ a q q-1 (qb)1 q-1 that holds for a, b, x > 0 and q ≥ 2. This completes the proof.The above analysis can be extended to corrupted stochastic environments in a straightforward manner: Theorem 17. Consider online convex optimization in corrupted stochastic environments with corruption level C, where the optimal decision is x ⋆ = arg min x∈K f • (x). Suppose that K is (κ, q)uniformly convex w.r.t. a norm • for some q ≥ 2 and that ∇ f • ( x ⋆ ) = 0. Then, any algorithm with the bound (1) achievesR T = O R + C 1 q R q-1 q + c ′ sc ln T for R = (ξc sc ) q q-1 qκ ∇ f • ( x ⋆ ) ⋆ 1 q-1 T q-22(q-1) (ln T ) q 2(q-1) . ( 6)When K is λ-strongly convex w.r.t. • , R T = O ξcsc λ∥∇ f • ( x⋆)∥⋆ ln T + Cξcsc λ∥∇ f • ( x⋆)∥⋆ ln T +c ′ sc ln T .The proof can be found in Appendix G. When q = 2, the dependence on the corruption level C is same as that in Theorem 13.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? 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 be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 a 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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 be possible for other researchers to have some path to reproducing or verifying the results. • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
conclusion: 
 In this work, we introduce a new curvature condition for achieving fast rates in online convex optimization. Under this condition, we developed a new analysis to achieve fast rates by exploiting the curvature of feasible sets. In particular, by the algorithm adaptive to the curvature of loss functions, we proved an O(ρ ln T ) regret bound for (ρ, x ⋆ , f • )-sphere enclosed feasible sets. There are several advantages of our approach: it can exploit the curvature of loss functions, can achieve the O(ln 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 ℓ p -balls for p ∈ [2, ∞) as special cases. This regret bound interpolates the O(ln T ) regret over strongly convex sets and the O( √ T ) regret over non-curved sets. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The focus of this study is on theory and does not include experiments.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 
licenses for existing assets: 
 Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: The focus of this study is on theory and does not 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 a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.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 not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: The focus of this study is on theory and does not introduce new 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: This appendix discusses the additional related work.Fast rates on strongly or uniformly convex sets Exploiting the curvature of feasible sets has been considered in OLO. In addition to the previously discussed studies [9, 11, 17] , in online learning with a hint, where a context m t satisfying m ⊤ t x t ≥ c x t 2 2 is given every round, we can achieve an O( 1 c ln T ) regret [3] , which was further extended in [2] with the lower bound for uniformly convex sets. The curvature was also exploited for improving a regret upper bound and reducing the number of linear optimization oracle calls in constructing Frank-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 x∈K f (x) for a given smooth convex function f [4, 5, 6, 11, 14] .Fast rates on curved loss functions One classical and seminal work to exploit the curvature of loss functions is by Hazan et al. [8] . Our approach is based on the results of universal online learning, the motivation of which is to be adaptive to parameters of loss curvature without knowing them. This line of investigation was initiated by van Erven and Koolen [21] , van Erven et al. [22] , who establish an algorithm, MetaGrad, that achieves an O( d β ln T ) regret bound if loss functions are β-exp-concave and an O( √ T ln ln T ) bound otherwise, without knowing the curvature of loss functions. The underlying idea is to run several experts in parallel with different curvature parameters, and then another expert algorithm integrates their results to choose decisions. This algorithm was later extended to achieve an O( 1 α ln T ) regret bound when the loss functions are α-strongly convex [24] . Roughly speaking, this was made possible by considering MetaGrad with additional experts of OGD with a learning rate of Θ(1/t). They provided a bound ofT t=1 ∇f t (x t ), x t -x ⋆ = O(G T t=1 x t -x ⋆ 22 ln T +GD ln T ) for D = max x,y∈K x-y 2 . This universal online learning framework has been extended to a simpler form [26] and to a form with the path-length bound [25] . It is worth noting that these algorithms are efficient since the number of experts is at most O(ln T ).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 a more general environment, the stochastically extended adversary (SEA) model. It would be important future work to extend our results to the SEA model. Note that they do not consider the curvature of feasible sets.Proof. Since K is W λ and x ⋆ = (0, -λ), the optimization problem we need to solve is fomulated as follows:EQUATION)From geometric observations, we have c -r = -λ. Hence, the optimization problem (7) can be rewritten asEQUATION)In the following, to make the constraint in the optimization problem (8) simpler, we consider the following optimization problem:EQUATION)By the standard method of Lagrange multiplier, one can compute that the optimal value of this optimization problem is max -2λcEQUATIONonly holds when c = 1-λ 2 λ , the feasible set of the optimization problem ( 8) is singleton set 1-λ 2 λ . Combining this fact with c -r = -λ, we get the desired result.Here we discuss the pros/cons of our regret bound against an existing bound when feasible set K is a polytope. The results mentioned in Section 4 mainly focus on the case where the feasible set is curved. However, as one can see from the definition of the sphere-enclosedness, even if the feasible set is polytope or does not have the curvature, a 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, Corollary 11] . Theorem 18. Consider online online linear optimization in stochastic environments with g• = E[g t ].Assume that K is polytope and g t ∞ ≤ M . Further assume that there exsits r > 0 such thatΦ(•) = max x∈K x, • is differentiable for any ν such that ν -g • ≤ r. Then, the regret of FTL is bounded by R T = O M 3 D r 2 ln M 2 d r 2.The comparison of this bound with our regret upper bound is not straightforward. If ∇f • (x ⋆ ) is not toward the "unfavorable" direction in K, then it is trivial that polytope K is (ρ, x ⋆ , f • )-sphereenclosed for some ρ, and thus the regret bound in Theorem 10 can be achieved. When T is large enough, the bound in Theorem 18 is better since it does not depend on T . However, their regret upper bound depends on 1/r 2 and M 3 , and the relation between them and 1/ ∇f • (x t ) 2 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 not straightforward, we would like to emphasize that our regret upper 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 4. In particular, while their bound is valid only in stochastic environments, our regret guarantee is valid in stochastic, adversarial, and corrupted stochastic environments.Proof. Recalling that x ⋆ = arg min x∈K f • (x), we can bound the regret from below asEQUATION)The first term in the last inequality is further bounded from below asEQUATION)where the first inequality follows by the definition of x ⋆ and the last inequality follows by x t ∈ K ⊆ BK γ⋆ . Combining the above inequalities with (1), we have R T = O c sc R T +C γ⋆ ln T + c ′ sc ln T . Solving this inequation and following the similar analysis as the proof of Theorem 10 complete the proof.Proof. Following the same argument as in the proof of Theorem 10, we haveEQUATION)From the strong convexity of f t , we also haveEQUATION)Plugging ( 14) in ( 13) and from Lemma 7 and Jensen's inequality,EQUATION)which completes the proof for the strongly convex loss functions.Next, we consider the case where f t 's are exp-concave. By [8, Lemma 3] , the G-Lipschitzness and β-exp-concavity of f t impliesEQUATIONfor β ′ ≤ 1 2 min 1 4GD , β . Using this and Lemma 7 to follow a similar argument as the stronglyconvex case, we can bound the regret asEQUATION)where in the last inequality we usedx t -x ⋆ 2 2 ≥ 1 G 2 ∇f t (x t ) ⊤ (x t -x ⋆ )2 that holds by the Cauchy-Schwarz inequality.Proof. Since K is (κ, q)-uniformly convex w.r.t. norm • ,EQUATION)Hence, for any z ∈ B ∥•∥ , the definition of y ⋆ implies thatEQUATION)Rearranging the last inequality implies -g, y ⋆ -y ≥ κ 4 y-y ⋆ q -g, z . Choosing z = -g/ g ∈ B ∥•∥ completes the proof.Proof. The regret is bounded from below asEQUATION)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 as in (4) . Recall that R = (ξcsc)q q-1 (qκ∥∇ f • ( x⋆)∥⋆) 1 q-1 T q-22(q-1) (ln T ) q 2(q-1) . Then from ( 1) and ( 20), for any λ ∈ (0, 1] we haveEQUATION)where in the second inequality we used a √ x -bx q/2 ≤ a q q-1 (qb)1 q-1 that holds for a, b, x > 0 and q ≥ 2 and in the last inequality we used (1+λ)q q-1 ≤ 2 q q-1 ≤ 4. Choosing λ = R C+R q-1 q ∈ (0, 1] in (21) gives R T = O(R + C 1 q R q-1 q+ c ′ sc ln T ), which completes the proof.This appendix discusses the connection between the uniform convexity in Banach space and the uniformly convex sets. While the notion of uniformly convex set was employed in the context of achieving fast rates by exploiting the curvature of feasible sets [11] , some papers in the context of online learning with a 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.We start from the definition of the uniform conexity in Banach spaces [18, Definition 4.16] .EQUATION)The modulus of uniform convexity δ B (ε) is the best possible δ for that ε, that is,EQUATION)Further, we say that B is (C, q)-uniformly convex if δ B (ε) = Cε q .We say that a Banach space B is uniformly convex if δ B (ε) > 0 for any ε ∈ (0, 2]. The modulus of convexity captures the strength of convexity, and intuitively, if the convexity of the space is large, then any two arbitrarily chosen points on the unit sphere will have their midpoints located deep inside the unit sphere. From this intuition, one can imagine that ℓ ∞ space is not uniformly convex.In fact, x = (1, 1, 1, . . . ), y = (-1, 1, 1, . . .) satisfies x ∞ = y ∞ = 1, x -y ∞ = 2 but 1 -(x + y)/2 ∞ = 0.Uniformly convex sets Here, we adopt a slightly generalized definition of uniformly convexity. Definition 20. A convex body K is γ K (•)-uniformly convex w.r.t. a norm • if for any x, y ∈ K and any θ ∈ [0, 1], it holds thatEQUATION)In particular, we say that a convex body K is (κ, q)-uniformly convex w.r.t. a norm • (or q-uniformly convex) if γ K (r) ≥ κr q .Connection between uniform convexity in Banach space and uniformly convex sets It is known that the unit ball on a uniformly convex space is a uniformly convex set and their uniform convexity matches up to a constant factor [11, Lemma 4.2] .Then the unit ball on the Banach space,B ∥•∥ , is 2δ(•)-uniformly convex set w.r.t. • . That is, for any x, y ∈ B ∥•∥ and any θ ∈ [0, 1], θx + (1 -θ)y + θ(1 -θ)2δ( x -y ) • B ∥•∥ ⊆ B ∥•∥ .In existing studies, there is no explicit discussion on whether the converse of Proposition 21 is 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. In the following, we show that the converse of Proposition 21 indeed holds for completeness: Proposition 22. If a ball K = B ∥•∥ is γ(•)-EQUATION)EQUATION)From this observation, we obtainEQUATIONwhere the last inequality follows from the assumption that K = B ∥•∥ . Hence, for any x, yEQUATIONwhich implies that Banach space with the norm • is uniformly convex with the modulus of convexity of δ(•) = 1 4 γ(•).This appendix discusses the relation between the sphere-enclsoed condition and the Bernstein condition. We use E t [ • ] to denote the expectation given f 1 , . . . , f t-1 .The seminal paper by Koolen et al. [13] provides the following Bernstein condition to obtain fast rates in OCO: Definition 23. In online convex optimization, a sequence of loss functions (f t ) T t=1 satisfies the (B, κ)-Bernstein condition if 10EQUATION)almost surely for all x ∈ K and t ∈ [T ].When κ = 1, this condition is also known as the Massart condition. They proved that if the (B, κ)-Bernstein conditions is satisfied, then the MetaGrad algorithm achieves a regret bound ofR T = O (d ln T ) 1 2-κ T 1-κ 2-κ.Sphere-enclosed condition Under the same assumption as in Theorem 10, the (ρ, x ⋆ , f • )-sphereenclosed condition implies thatEQUATIONfor any x ∈ K. Rearranging the last inequality gives thatx -x ⋆ 2 2 ≤ 2ρ ∇f • (x ⋆ ) 2 ∇f • (x ⋆ ), x -x ⋆ (31)holds for any x ∈ K. When loss functions are stochastic, the last inequality impliesEQUATION)where the first inequality follows from the Cauchy-Schwarz inequality and the second inequality follows from (31).Comparison between Bernstein condition and sphere-enclosed condition Comparing ( 29) and (32), we can see that they look similar but different and there is no direct connection the sphere-enclosed condition and Bernstein condition, since the RHS of (29) has x in ∇f t (x) while the RHS of (32) has x ⋆ in ∇f • (x ⋆ ). However, when loss functions are linear with g • = ∇f • (x) for all x ∈ K, Eq. ( 32) is equivalent toEQUATIONTherefore, when loss functions are stochastic and linear, the (ρ, x ⋆ , f • )-sphere-enclosed condition implies the (2G 2 ρ/ g • 2 , 1)-Bernstein condition for g • = ∇f • (x). 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 to OCO over uniformly convex sets, and has several advantages as detailed in Section 1.• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.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 (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).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 a straightforward manner.We will see that the third condition that the gradient of f at point u is directed towards the center of the sphere needs to be cared when optimal decision x⋆ is on corners of feasible sets.The subscripts sc and ec in csc and cec are the abbreviations of strongly-convex and exp-concave.Regret upper boundsIn 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 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: N.A.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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).
questions: 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: limitations: Yes, the paper points out that one limitation is that the main results hold under stochastic environment.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Second, although it seems that this paper has made many contributions, some results have already been achieved, and some results can be simply derived. 
1) 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.
2) 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.
3) 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.
4) 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.

Third, the writing and organization of this paper are not very sound.
1) The context of Section 2.1 is almost the same as the first paragraph in Section 1.
2) Many short proofs are interluded in the main text, which reduces the readability of this work.
3) In line 340, "a similar analysis ideas" seems to be a typo.

[*] Anderson and Leith. Online Lazy Gradient Descent is Universal on Strongly Convex Domains. In NeurIPS 2021.

----After Rebuttal----
After 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.
questions: questions: Besides the weaknesses discussed above, I also have the following questions.
1) Can the authors summarize the fully new contributions compared with existing studies?
2) 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: limitations: The authors have discussed some limitations of this work.
paper_summary: paper_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). 
- 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. 
- 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$.
strength_weakness: strength_weakness: - 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 ?
- 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.
- 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$?

Some sections are slightly unclear and a bit confusing:
- 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.
- 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).
- 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.
- 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.

Typos:
- Line 222 missing a “the” in front of inequality. 
- Line 219, missing a “the” in front of ball.
- Line 245: typo “$x_\star$ in on corners" ?
- 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$.
- line 147: missing "a" in front of "convex body K".
- Line 287: missing “the” in front of ball. 
- 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.
- 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).
questions: questions: Some questions are asked in the weaknesses above.
- 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 ?
- 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 ?
- 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: limitations: In general yes, though it is not necessarily apparent that in the fully adversarial setting, the results do not improve upon FTL.

Comments: title: Additional Replies
Additional Replies
comment: Thank you for your response. I will keep my score positive.
Thank the authors for additional comments on lower and upper bounds, which answer my questions. I would like to keep my score!
Thanks to the authors for their response, which clarify some of the points I had raised. I am happy to keep my score.
Thanks for the authors' response. I currently 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 will increase my score from 3 to 5.
Here, we will respond to the points that are considered to have a relatively small impact on the evaluation, which cannot be included in the above rebuttal due to space constraints.

> 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

Thank you for pointing this out. In the revised version, we will adjust the statement of the Theorem accordingly.

> Furthermore, it is not clear why if the assumption does not hold, the lower-bound becomes vacuous ?

We apologize for the inappropriate use of the term "vacuous". We will simply change the expression to "We assume that $T \geq C / (\lambda L)$".

> 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. It is unclear why this notation is used here (similarly for $\nabla f^{\circ}(x_t)$ in the statements of Theorem 8 and 9).

The use of $x_t$ here is because it will be used in Theorem 10, as stated in line 222, "We will see in the following proof that...".
However, as you pointed out, the description in Remark 1 can be improved, and we will improve this in the revised version.
Specifically, we will change it to " $x \in B_\gamma^K$ is equivalent to $\langle \nabla f^\circ(x_\star), x - x^* \rangle \geq \gamma \\| x - x^* \\|_2^2$".
We apologize for the typo in Theorems 8 and 9 where $\nabla f^{\circ}(x_t)$ should be $\nabla f^{\circ}(x^*)$. Thank you for pointing this out.

> - 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.
>- Line 251-254: am I correct in understanding that your approach guarantees a 
 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.

Thank you very much for your valuable comments. We will prepare the revised version according to your comments.

**Replies to Questions**

> 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 ?
> 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 ?

We are uncertain whether $GD$ can be eliminated from the regret upper bound or introduced into the regret lower bound.
Regarding the dependency on $d$ in Theorem 10, we believe that it does not depend on $d$ if the Maler algorithm is used.
This is because the constants $c_{\mathsf{sc}}$ and $c'_{\mathsf{sc}}$ in the Maler algorithm do not depend on $d$.

> 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. 

Thank you for your advice. In the revised version, we will also include results for the corrupted setting.
Here, we will respond to the points that are considered to have a relatively small impact on the evaluation, which cannot be included in the above rebuttal due to space constraints.

> Third, the writing and organization of this paper are not very sound.
> 1. The context of Section 2.1 is almost the same as the first paragraph in Section 1.
> 2. Many short proofs are interluded in the main text, which reduces the readability of this work.
> 3. In line 340, "a similar analysis ideas" seems to be a typo.

Regarding point 1, I believe it is quite common to restate the problem formulation in the preliminaries section following the introduction.

For point 2, if you have time, could you please specify which parts you found to have low readability if the reviewer has time? We will make an effort to reduce the number of inline equations in the revised version.

Regarding point 3, thank you for pointing this out. We will correct it in the revised version.