A Simple and Optimal Approach for Universal Online Learning with Gradient Variations

Authors: yu-hu  yan
peng  zhao
zhi-hua  zhou
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 13:44:06

Abstract: We investigate the problem of universal online learning with gradient-variation regret. Universal online learning aims to achieve regret guarantees without prior knowledge of the curvature of the online functions. Moreover, we study the problem-dependent gradient-variation regret as it plays a crucial role in bridging stochastic and adversarial optimization as well as game theory. In this work, we design a universal approach with the *optimal* gradient-variation regret simultaneously for strongly convex, exp-concave, and convex functions, thus addressing an open problem highlighted by [Yan et al. [2023]](https://openreview.net/forum?id=AA1xrgAP5z). Our approach is *simple* since it is algorithmically efficient-to-implement with a two-layer online ensemble structure and only $1$ gradient query per round, and theoretically easy-to-analyze with a novel and alternative analysis to the gradient-variation regret. Concretely, previous works on gradient variations require controlling the algorithmic stability, which is challenging and leads to sub-optimal regret and less efficient algorithm design. Our analysis overcomes this issue by using a Bregman divergence negative term from linearization and a useful smoothness property.

Main paper: 
 introduction: 
 Online convex optimization (OCO) models a sequential T -round game between an online learner and the environments [Hazan, 2016 , Orabona, 2019] . In each round t ∈ [T ], the learner selects a decision x t from a convex compact set X ⊆ R d . Simultaneously, the environments adversarially choose a convex loss function f t : X → R. Subsequently, the learner suffers a loss of f t (x t ), receives feedback on the function f t (•), and updates her decision to x t+1 . In OCO, the learner aims to optimize the game-theoretical performance measure known as regret [Cesa-Bianchi and Lugosi, 2006] , which is formally defined asREG T ≜ T t=1 f t (x t ) -min x∈X T t=1 f t (x).(1.1)It represents the learner's excess cumulative loss compared with the best fixed comparator in hindsight.In OCO, function curvatures play an important role in the best attainable regret bounds. Traditional studies examine three types of curvatures: convexity, exp-concavity, and strong convexity. Specifically, for convex functions, online gradient descent (OGD) achieves O( √ T ) regret [Zinkevich, 2003] ; for α-exp-concave functions, online Newton step assuming α is known obtains O( d α log T ) regret [Hazan et al., 2007] ; and for λ-strongly convex functions, OGD with known λ attains O( 1 λ log T ) [Hazan et al., 2007] . These results are shown to be minimax optimal [Ordentlich and Cover, 1998, Abernethy et al., 2008] . Recent studies further strengthen them by introducing two levels of adaptivity.Table 1 : Comparison with existing results. The second column shows the regret bounds for strongly convex, exp-concave, and convex functions, following the O(•)-notation. Note that we only list universal guarantees related to the gradient variation VT or the time horizon T . Each gradient-variation bound can directly apply a corresponding small-loss regret in analysis, which is formally stated in Theorem 2 and omitted here for clarity. We treat the log log T factor as a constant and omit it. "# Gradient" is the number of gradient queries in each round, where "1" represents exactly one gradient query. And "# Base" stands for the number of base learners.Regret Bounds Efficiency Strongly Convex Exp-concave Convex # Gradient # Base van Erven and Koolen [2016] d log T d log T √ T 1 log T Wang et al. [2019] logT d log T √ T 1 log T Zhang et al. [2022a] log V T d log V T √ T log T log T Yan et al. [2023] log V T d log V T √ V T log V T 1 (log T ) 2 Ours log V T d log V T √ V T 1 log THigh-level Adaptivity to Unknown Curvatures. Traditional studies require function curvature information in advance to select suitable algorithms for provable bounds. However, the information could be hard to access in real-world applications. To this end, a line of research aims to design a single universal algorithm that does not require the curvature information while achieving the same regret guarantees as if knowing it, achieving the adaptivity to unknown curvatures. The pioneering work of MetaGrad [van Erven and Koolen, 2016] proposed carefully designed surrogate functions and achieved O( d α log T ) for α-exp-concave functions and O( √ T ) for convex functions. Subsequently, Wang et al. [2019] obtained the optimal O( 1 λ log T ) regret for λ-strongly convex functions, while maintaining the optimal rates in the other cases. Another remarkable progress of Zhang et al. [2022a] proposed a flexible framework with simplified analyses and further enhanced the minimax results using smoothness. We provide a detailed introduction of this work in Section 2.2.Low-level Adaptivity to Gradient Variation. Although the regret guarantees based on the time horizon T are optimal in the minimax sense, in this work we are interested in achieving the gradientvariation regret [Chiang et al., 2012 , Yang et al., 2014] , which replaces the dependence of the time horizon T by the gradient variation quantity defined in the following:V T ≜ T t=2 sup x∈X ∥∇f t (x) -∇f t-1 (x)∥ 2 .(1.2)Under smoothness assumptions, the minimax regret can be improved to O( 1 λ log V T ), O( d α log V T ), and O( √ V T ) for λ-strongly convex, α-exp-concave, and convex functions, respectively. In this work, continuing previous gradient-variation online learning results [Zhao et al., 2020 , 2024 , Zhang et al., 2022b , Chen et al., 2023] , we focus on the gradient-variation regret for the following reasons: (i) gradient-variation bounds safeguard the minimax guarantees. Besides, as demonstrated by Zhao et al. [2024] , the gradient-variation regret is more fundamental than another well-known problemdependent quantity known as the small loss F T ≜ min x∈X t≤T f t (x) [Srebro et al., 2010 , Orabona et al., 2012] since gradient-variation regret can imply small-loss bounds directly in analysis; (ii) the gradient variation plays a crucial role in bridging adversarial and stochastic optimization [Sachs et al., 2022] ; and (iii) the gradient-variation regret can be used to achieve fast rates in multi-player games [Syrgkanis et al., 2015 , Zhang et al., 2022b] . More detailed explanations of the importance of achieving such adaptivity are provided at the end of this section.Motivated by the aforementioned two levels of adaptivity, we focus on the problem of achieving universal gradient-variation regret, i.e., designing a single universal approach with gradient-variation regret across different curvature types without the prior knowledge of them. For this problem, Zhang et al. [2022a] achieved partial results of O( 1 λ log V T ), O( d α log V T ), O( √ T ) for λ-strongly convex, α-exp-concave, and convex functions, respectively. Subsequently, Yan et al. [2023] proposed a carefully designed three-layer online ensemble approach to stabilize the algorithm and improved the convex result to O( √ V T log V T ), achieving the first universal gradient-variation guarantee. Although optimal for strongly convex and exp-concave functions, their results still exhibit a gap with the optimal O( √ V T ) regret in the convex case. Here "optimal" refers to matching the best known results with curvature information since problem-dependent lower bound cannot be easily obtained. The only lower bound we are aware of is Ω( √ V T ) for convex functions [Yang et al., 2014, Remark 5] .To handle the uncertainty, online ensemble is commonly employed and proven effective in enhancing the robustness [Zhou, 2012 , Zhao, 2021] , such as adaptive regret minimization [Hazan and Seshadhri, 2007 , Daniely et al., 2015 , Zhang et al., 2019] , dynamic regret minimization [Zhang et al., 2018 , Zhao et al., 2020 , 2024] , and universal online learning [van Erven and Koolen, 2016 , Zhang et al., 2022a , Yan et al., 2023] . Concretely, an online ensemble algorithm contains multiple base learners for exploring the environments and a meta learner for ensemble. In universal online learning, base learners make guesses on the curvature information, and the meta learner tracks the best base learner (i.e., with the most accurate guess) on the fly.Due to the deployment of the online ensemble framework, computational efficiency has become a point of concern, with two essential factors. The first is the number of base learners, because each independently runs an online learning algorithm that involves time-consuming gradient computations and projections. The second factor is the number of gradient queries, especially when the gradient evaluation is costly, e.g., in nuclear norm optimization [Ji and Ye, 2009] and mini-batch optimization [Li et al., 2014] . In universal online learning, an "efficient" algorithm is expected to adopt only O(log T ) base learners, which is inherent to the online ensemble design, and only 1 gradient query per round, matching the gradient query complexity of standard OGD. In terms of this metric, Zhang et al. [2022a] employed O(log T ) base learners, but required O(log T ) gradient queries per round. Yan et al. [2023] used only 1 gradient query per round but required O((log T ) 2 ) base learners (caused by their three-layer algorithm design), resulting in reduced efficiency.Results. Motivated by the above considerations of optimality and efficiency, in this work, we propose a simple universal approach that achieves the optimal O( 1 λ log V T ), O( d α log V T ), and O( √ V T ) regret simultaneously for λ-strongly convex, α-exp-concave, and convex functions, and is efficient with one gradient query per round and O(log T ) base learners, resolving a major open problem highlighted by Yan et al. [2023] . We summarize our theoretical results in Theorem 1, and compare our results with existing ones in Table 1 . Furthermore, we validate the effectiveness of our approach by: (i) showing that our universal gradient-variation regret directly implies the optimal universal small-loss regret in analysis without any algorithm modifications; and (ii) applying them to the stochastically extended adversarial (SEA) model [Sachs et al., 2022] , an intermediate framework between stochastic and adversarial optimization. We achieve the same state-of-the-art guarantees as Chen et al. [2024] , but without curvature information. The details are provided in Section 4.Techniques. Our technical contributions include two simple and novel analyses. First, the key to gradient-variation regret is to analyze its empirical version, formally, ∥∇f t (x t ) -∇f t-1 (x t-1 )∥ 2 2 . The previous approach to addressing this term involves controlling the algorithmic stability ∥x tx t-1 ∥ 2 2 , which is highly challenging in universal online learning, leading to sub-optimal results and less efficient algorithm design [Yan et al., 2023] . In this work, we overcome this issue via a novel analysis by a useful smoothness property and a Bregman divergence negative term from linearization, where the latter is inspired by the recent advance in stochastic optimization [Joulani et al., 2020] . Second, we adopt the surrogate functions proposed by Yan et al. [2023] to reduce the gradient query complexity, and provide a novel analysis for the empirical gradient variation based on the surrogates. A technical comparison with previous works is provided in Section 4.Organization. The rest of the paper is structured as follows. Section 2 introduces preliminaries and a general framework for universal online learning. Section 3 presents our efficient approach with the optimal universal gradient-variation regret. Section 4 presents the implication and application of our results. Finally Section 5 concludes the paper. All the proofs can be found in the appendices. 
preliminaries: 
 In this section, we introduce some preliminary knowledge, including notations, assumptions, definitions, and a general framework of universal online learning.For simplicity, we use ∥ • ∥ for ∥ • ∥ 2 by default and use a ≲ b or a = O(b) if there exists a constant C < ∞ such that a/b ≤ C. In the following, we introduce the assumptions used in this work.Assumption 1 (Boundedness). For any x, y ∈ X ⊆ R d , the domain diameter satisfies ∥x -y∥ ≤ D, and for t ∈ [T ], the gradient norm of the online functions is bounded as ∥∇f t (x)∥ ≤ G.Assumption 2 (Smoothness). For each t ∈ [T ], the online function f t (•) is L-smooth, i.e., ∥∇f t (x)-∇f t (y)∥ ≤ L∥x -y∥ holds for any x, y ∈ R d .Both assumptions are common in the literature. Specifically, the boundedness assumption is widely used in OCO [Hazan, 2016] . And the smoothness assumption is essential for first-order algorithms in achieving the gradient-variation regret [Chiang et al., 2012] . Note that here Assumption 2 requires smoothness on the whole R d space and can be relaxed to a slightly larger domain than X , formally,X + ≜ {x + b | x ∈ X , b ∈ G /L • B}, where B ≜ {x | ∥x∥ ≤ 1} is a unit ball.We defer the details of this relaxed smoothness requirement and its derivation to Appendix A. In the following, we provide formal definitions of strong convexity and exp-concavity. Definition 1. For any x, y ∈ X , a function f [Hazan, 2016, Lemma 4.3] . Therefore, we adopt Definition 1 as an alternative definition of exp-concavity for clarity.(•) is λ-strongly convex if f (x) -f (y) ≤ ⟨∇f (x), x - y⟩ -λ 2 • ∥x -y∥ 2 ; f (•) is α-exp-concave if f (x) -f (y) ≤ ⟨∇f (x), x -y⟩ -α 2 • ⟨∇f (x), x -y⟩ 2 . Note that the formal definition of β-exp-concavity is that exp(-βf (•)) is concave. Under As- sumption 1, β-exp-concavity implies Definition 1 with α = 1 2 • min{1/(4GD), β}In this part, we present a general framework of universal online learning [Zhang et al., 2022a , Yan et al., 2023] . Formally, we study the problem where the learner lacks the prior knowledge of curvature information, including (i) curvature type: convexity, exp-concavity, or strong convexity; and (ii) curvature coefficient: exp-concavity α or strong convexity λ. Without loss of generality, we focus on the case of α, λ ∈ [1/T, 1]. If α, λ < 1/T , even the optimal minimax results -O( d α log T ) for exp-concave functions and O( 1 λ log T ) for strongly convex functions [Hazan et al., 2007] -become linear in T , rendering the regret bounds vacuous. On the other hand, if α, λ > 1, we can simply treat them as α, λ = 1, only making the regret worsen by an ignorable constant factor. This simplification is also adopted by Zhang et al. [2022a] , Yan et al. [2023] .To handle the uncertainty of curvatures, an online ensemble structure is usually employed, with multiple base learners exploring the environments and a meta learner tracking the best base learner. More specifically, to deal with the unknown curvature coefficients α and λ, we discretize them into the following candidate pool [Zhang et al., 2022a] :H ≜ {1/T, 2/T, 4/T, . . . , 2 n-1 /T }, (2.1)whose size is n = ⌈log 2 T ⌉ + 1 = O(log T ). It can be proved that the discretized candidate pool H can approximate the continuous value of α or λ with negligible constant errors. By doing this, it is natural to design three distinct groups of base learners:(i) strongly convex base learners: n in total, each of which implements the algorithm for strongly convex functions with a guess λ i ∈ H of the strong convexity coefficient λ; (ii) exp-concave base learners: n in total, each of which implements the algorithm for expconcave functions with a guess α i ∈ H of the exp-concavity coefficient α; (iii) convex base learner: only one, it runs the algorithm for convex functions.In total, there are N ≜ (2n + 1) = O(log T ) base learners with a two-layer structure, which is for now necessary in this problem. The best base learner is the one with the right guess of the curvature type and the closest guess of the curvature coefficient. Taking λ-strongly convex functions as an example, the guessed coefficient of the best base learner (indexed by i ⋆ ) satisfiesλ i ⋆ ≤ λ ≤ 2λ i ⋆ .Denoting by x t,i the decision generated by the i-th base learner at the t-th round, p t,i the weight of the meta learner on the i-th base learner, an online ensemble method outputs the final decision as x t = i∈[N ] p t,i x t,i . This forms a general framework for universal online learning and it remains to select suitable algorithms and loss functions for the meta and base learners. We illuminate our algorithm design in Section 3.1. 
our approach: 
 In this section, we present our approach for universal online learning with gradient-variation regret. Section 3.1 presents the overall procedure of our proposed algorithm. Subsequently, we outline A updates to p t+1 = (p t+1,1 , . . . , p t+1,N ) with ℓ t,i = ⟨∇f t (x t ), x t,i ⟩, ε t,i given in (B.5), and m t,i = ⟨∇f t-1 (x t-1 ), x t -x t,i ⟩ for the convex base learner and m t,i = 0 otherwise # Base Update:5: Construct surrogates h sc t,i (•), h exp t,i (•), h c t,i (•) defined in (3.1) using only ∇f t (x t ) 6:Send the surrogate functions to B i for update and obtain x t+1,i for each i ∈ [N ] 7: end for our two key technical components: Section 3.2 presents a novel analysis to handle the empirical gradient variation, and Section 3.3 introduces surrogate functions to improve efficiency and provides a corresponding analysis for the empirical gradient variation defined on surrogates. We finally provide the optimal universal gradient-variation regret guarantees in Section 3.4.In this part, we present our simple approach for universal online learning with gradient variations, summarized in Algorithm 1. Basically, it follows a two-layer online ensemble structure. Base learners are implemented using the preliminary configurations given in Section 2.2 and on carefully designed surrogate functions. The meta learner runs OPTIMISTIC-ADAPT-ML-PROD [Wei et al., 2016] on linearized losses. We specify the algorithmic details below.In Line 3, the learner makes a weighted combination of the base learners' decisions {x t,i } i∈[N ] using the meta learner's weights p t = (p t,1 , . . . , p t,N ), submits the final decision x t , suffers a loss f t (x t ), and receives a single ∇f t (x t ) as the gradient feedback, using only 1 gradient query per round.Meta Algorithm. In Line 4, the meta learner uses OPTIMISTIC-ADAPT-ML-PROD [Wei et al., 2016] to update the weights by the following rule:p t+1,i ∝ ε t,i •exp(ε t,i m t+1,i )•W t,i , W t,i = W t-1,i • exp ε t-1,i r t,i -ε 2 t-1,i (r t,i -m t,i ) ε t,i ε t-1,i .Specifically, denoting by ℓ t,i ≜ ⟨∇f t (x t ), x t,i ⟩ the loss of the i-th dimension, the meta algorithm inputs: r t,i = ⟨ℓ t , p t ⟩ -ℓ t,i , the instantaneous regret; ε t,i , a time-varying learning rate; and m t,i , an estimation of the true loss of the t-th round (the choice of optimisms will be shown later Base Algorithm. In Line 5, we adopt carefully designed surrogate functions for different types of base learners to reduce the gradient query complexity [Yan et al., 2023] . Specifically, strongly convex, exp-concave, and the convex base learners run on the surrogate functions below respectively:h sc t,i (x) ≜ ⟨∇f t (x t ), x⟩ + λ i 4 ∥x -x t ∥ 2 , h exp t,i (x) ≜ ⟨∇f t (x t ), x⟩ + α i 4 ⟨∇f t (x t ), x -x t ⟩ 2 , (3.1)and h c t,i (x) ≜ ⟨∇f t (x t ), x⟩, where λ i , α i are selected from the candidate coefficient pool H in (2.1). We emphasize that the surrogate functions require only 1 gradient query ∇f t (x t ) per round. Finally, in Line 6, the i-th base learner B i updates the decision to x t+1,i using optimistic online mirror descent (OOMD) [Rakhlin and Sridharan, 2013] , which is general and covers many algorithms of interest, such as OGD and online Newton step. For each curvature type (convexity, exp-concavity, or strong convexity), we adopt a correspondingly configured OOMD as the base learner.As for previous works, Zhang et al. [2022a] adopted ADAPT-ML-PROD [Gaillard et al., 2014] as the meta learner, which does not incorporate optimisms and thus is impossible to achieve gradientvariation regret for convex functions, and operates on the original loss function f t (•) for base learners, which leads to a less efficient gradient query complexity of O(log T ) per round. Yan et al. [2023] used a two-layer meta algorithm MSMWC-MASTER [Chen et al., 2021] as the meta learner, resulting in a three-layer ensemble structure, which is also not efficient enough. Compared with approaches above, our Algorithm 1 is simpler and more efficient as it requires O(log T ) base learners and only 1 gradient query in each round. We emphasize that our contributions mainly lie in the technical aspects showing that although simple, our approach can achieve the optimal universal gradient-variation regret, which is accomplished via two novel analytical components.In this part, we provide a novel analysis of the gradient-variation regret. For clarity, we illustrate from the lowest level -as we only use one gradient ∇f t (x t ) in the t-th round, to obtain the gradient variation V T defined in (1.2), it is necessary to first attain its empirical version VT ≜ t≤T ∥∇f t (x t ) -∇f t-1 (x t-1 )∥ 2 . Previous studies decompose this term into two parts:∥∇f t (x t ) -∇f t-1 (x t-1 )∥ 2 ≲ ∥∇f t (x t ) -∇f t-1 (x t )∥ 2 + ∥∇f t-1 (x t ) -∇f t-1 (x t-1 )∥ 2 ≤ sup x∈X ∥∇f t (x) -∇f t-1 (x)∥ 2 + L 2 ∥x t -x t-1 ∥ 2 ,using smoothness (i.e., Assumption 2). Aggregating the first term over T rounds leads to the desired V T quantity and the remaining challenge is to control the algorithmic stability ∥x t -x t-1 ∥ 2 . Consequently, since each decision is a weighted combination of base learners' decisions (i.e., x t = i≤N p t,i x t,i ), the algorithmic stability is difficult to control. To this end, Yan et al. [2023] decomposed the stability term in the following way:∥x t -x t-1 ∥ 2 ≲ N i=1 p t,i ∥x t,i -x t-1,i ∥ 2 + ∥p t -p t-1 ∥ 2 1 . (3.2)Consequently, for the first term, the authors injected correction terms to the meta learner following Zhao et al. [2024] . To cancel the second term, the meta algorithm must include a corresponding negative stability term in its analysis, while achieving an optimistic second-order bound simultaneously. To the best of our knowledge, the only feasible algorithm satisfying both requirements is the two-layer meta algorithm MSMWC-MASTER [Chen et al., 2021] , which leads to a three-layer online ensemble structure and therefore affects the efficiency. Besides, it attains a second-order bound of the formO( Q T,i log Q T,i ), where Q T,i ≜ t (ℓ t,i -m t,i ) 2, which causes the sub-optimality of the regret guarantees with an additional logarithmic factor in the results of Yan et al. [2023] .In this work, we handle the empirical gradient variation alternatively via a novel and simple analysis with two key parts: (i) a negative term arising from linearization; and (ii) a useful smoothness property. First, we observe that the instantaneous regret can be transformed as:f t (x t ) -f t (x ⋆ ) = ⟨∇f t (x t ), x t -x ⋆ ⟩ -D ft (x ⋆ , x t ), (3.3) where x ⋆ ∈ arg min x∈X t f t (x) and D f (x, y) ≜ f (x) -f (y) -⟨∇f (y), x -y⟩ is the Bregman divergence associated with function f (•).The last term is a negative term from linearization, which can be seen as the compensation by treating a convex function as a linear one. Previous studies on the gradient-variation regret usually omit this term, while we show below that this negative term helps to achieve a much simpler analysis of the empirical gradient variation. Second, we introduce a useful property of smoothness, formally introduced below.Proposition 1 (Theorem 2.1.5 of Nesterov [2018]). f (•) is L-smooth over R d if and only if ∥∇f (x) -∇f (y)∥ 2 ≤ 2L • D f (y, x), for any x, y ∈ R d . (3.4)Compared with the commonly used ∥∇f (x) -∇f (y)∥ ≤ L∥x -y∥, Proposition 1 gives a tighter bound for the squared gradient changes since ∥∇f(x) -∇f (y)∥ 2 ≤ 2LD f (y, x) ≤ L 2 ∥x -y∥ 2 ,where the second step is due to D f (y, x) ≤ L 2 ∥x -y∥ 2 , for any x, y ∈ R d [Nesterov, 2018, Theorem 2.1.5], intuitively making the analysis easier. Combining the Bregman divergence negative term (3.3) and this useful property (3.4), we address the empirical gradient variation effectively asVT ≲ T t=2 ∥∇f t (x t ) -∇f t (x ⋆ )∥ 2 + ∥∇f t (x ⋆ ) -∇f t-1 (x ⋆ )∥ 2 + ∥∇f t-1 (x ⋆ ) -∇f t-1 (x t-1 )∥ 2 (3.4) ≲ L T t=2 D ft (x ⋆ , x t ) + V T + L T t=2 D ft-1 (x ⋆ , x t-1 ) ≤ 2L T t=1 D ft (x ⋆ , x t ) + V T , (3.5)where the first step introduces intermediate terms ∇f t (x ⋆ ) and ∇f t-1 (x ⋆ ), the second step uses Proposition 1, and the last step combines two summations into one by shifting the indexes of t. The Bregman divergence negative term in (3.3) can cancel the positive term in (3.5), leaving only the gradient variation quantity V T as desired.Here we only require ∥∇f (x)-∇f (y)∥ 2 ≤ 2LD f (y, x) on X rather than R d , which can be satisfied by requiring L-smoothness only on a slightly larger domain than X (a relaxation of Assumption 2).Interested readers can refer to Appendix A for details. Finally we end this part with several remarks. Remark 1. We emphasize that the Bregman divergence negative term comes from the linearization of convex functions, and is thus algorithm-independent. Therefore, we can eliminate the need to control the algorithmic stability, in contrast to previous works for gradient-variation regret [Chiang et al., 2012 , Yan et al., 2023] . To the best of our knowledge, this is the first alternative analysis of the gradient-variation regret since first proposed by Chiang et al. [2012] . ◁ Remark 2. Our idea of the negative term from linearization is inspired by the recent advance in stochastic optimization [Joulani et al., 2020] . Note that they focus on a different problem of achieving the O(1/T 2 ) rate as Nesterov's accelerated gradient [Nesterov, 2018] , while we investigate the gradient-variation regret in the universal online (adversarial) convex optimization setup. ◁ Remark 3. Our analysis does not strictly outperform those that directly handle the stability term as in (3.2), e.g., Yan et al. [2023] , since the latter can be used for fast rates in the multi-player game setup [Syrgkanis et al., 2015 , Zhang et al., 2022b] . A more detailed discussion of the advantages and disadvantages over previous approaches is provided in Section 4.3. ◁Section 3.2 already suffices to achieve the optimal universal gradient-variation regret if multiple gradient queries are permitted. In this part, we consider further improving the computational efficiency by using only 1 gradient query per round, achieving the same gradient query complexity as OGD.As stated in Section 3.1, we implement base algorithms on carefully designed surrogate functions following Yan et al. [2023] . In this part, we show that additional novel analysis is required to handle the empirical gradient variation defined on surrogates. To see this, we first provide the entire regret decomposition to give readers a clear roadmap. Specifically, taking λ-strong convexity as an example, the regret can be decomposed as follows:REG T ≤ T t=1 ⟨∇f t (x t ), x t -x ⋆ ⟩ - λ 4 T t=1 ∥x t -x ⋆ ∥ 2 - 1 2 T t=1 D ft (x ⋆ , x t ) ≤ T t=1 r t,i ⋆ - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 + T t=1 h sc t,i ⋆ (x t,i ⋆ ) -h sc t,i ⋆ (x ⋆ ) - 1 2 T t=1 D ft (x ⋆ , x t ),where the first step uses (3.3) and the fact thatD ft (x ⋆ , x t ) ≥ λ 2 ∥x t -x ⋆ ∥ 2 since f t (•) is λ-strongly convex.The second step uses the definition of the best base learner (indexed by i ⋆ ): λ i ⋆ ≤ λ ≤ 2λ i ⋆ and the definition of surrogate functions defined in (3.1). The first term above (meta regret) assesses how well the algorithm tracks the best base learner, and the second term (base regret) measures the best base learner's performance. The meta regret contains a linearized regret with a negative term from curvatures. This negative term is useful for exp-concave and strongly convex functions if the linearized regret enjoys a second-order bound:T t=1 r t,i ⋆ - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 ≲ T t=1 ⟨∇f t (x t ), x t -x t,i ⋆ ⟩ 2 - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 ≲ 1 λ ,where the 1/λ factor can be absorbed by the final regret O( 1 λ log V T ). The base regret is defined on the surrogates, which preserves the curvature properties, but using only 1 gradient ∇f t (x t ).Below we explain the reason for handling the empirical gradient variation defined on surrogates. Taking the i-th strongly convex base learner as an example, it updates asx t,i = Π X [ x t,i -η t m t ] and x t+1,i = Π X [ x t,i -η t ∇h sc t,i (x t,i )],an initialization of the OOMD algorithm, where η t represents the step size, Π X [x] = arg min y∈X ∥x -y∥ denotes the Euclidean projection onto X , and x t,i is an intermediate variable. With appropriately chosen step sizes, the base learner achieves an optimistic bound of O(log D T ), where D T = t≤T ∥∇h sc t,i (x t,i ) -m t ∥ 2 (e.g., please refer to Theorem 15 of Chiang et al. [2012] ). Therefore, choosing the optimism as m t = ∇h sc t-1,i (x t-1,i ) leads to an empirical gradient-variation bound O(log D T ) defined on surrogates,3 whereD T = T t=2 ∥∇h sc t,i (x t,i ) -∇h sc t-1,i (x t-1,i )∥ 2 = T t=2 ∇f t (x t ) -∇f t-1 (x t-1 ) + λ i 2 (x t,i -x t ) - λ i 2 (x t-1,i -x t-1 ) 2 .The empirical gradient variation defined on the original functions, i.e., ∥∇f t (x t ) -∇f t-1 (x t-1 )∥ 2 , can be handled via the analysis in Section 3.2. The main challenge is to deal with the rest terms caused by the surrogate functions. Yan et al. [2023] overcame this issue by controlling (x t -x t-1 ) and (x t,i -x t-1,i ) separately. Again, as we have explained in Section 3.2, since the decision x t is a weighted combination of base learners' decisions (i.e., x t = i≤N p t,i x t,i ), handling the algorithmic stability term ∥x t -x t-1 ∥ 2 directly using (3.2) would results in a less efficient three-layer online ensemble structure and the sub-optimality of the regret guarantees, as Yan et al. [2023] did.In this work, we propose a novel analysis -while controlling (x t,i -x t ) -(x t-1,i -x t-1 ) in each individual round is hard, it can be bounded when aggregated over the time horizon. Specifically, we bound it by combining two summations into one:T t=2 ∥(x t,i -x t )-(x t-1,i -x t-1 )∥ 2 ≲ T t=2 ∥x t,i -x t ∥ 2 + T t=2 ∥x t-1,i -x t-1 ∥ 2 ≤ 2 T t=1 ∥x t,i -x t ∥ 2 .The same idea is also used in the derivation of (3.5). Consequently, this term can be canceled out by the negative term from curvatures in the meta regret. For this cancellation to occur, appropriate coefficients are chosen, which are provided in the detailed proofs (e.g., the 'Regret Analysis' part in the proof of Theorem 1) and are omitted here for clarity.This simple and novel analysis eliminates the need to control the overall algorithmic stability term of ∥x t -x t-1 ∥ 2 required by previous works, and is essential for achieving the improved computational efficiency and the optimal regret guarantees, as shown in the next part.In this part, we present our main theoretical result -our simple and efficient Algorithm 1 (in Section 3.1) which adopts two novel analyses (in Section 3.2 and Section 3.3) achieves the optimal gradient-variation regret without requiring the curvature information in advance for universal online learning. The corresponding proof is provided in Appendix B. Theorem 1. Under Assumptions 1 and 2 (or the relaxed Assumption 3), Algorithm 1 achieves O(log V T ), O(d log V T ), and O( √ V T ) for strongly convex, exp-concave, and convex functions. Yan et al. [2023] and is optimal by matching the best known results when the curvature information is known. It performs well when the gradient variation is small, such asTheorem 1 improves the O( √ V T log V T ) bound off 1 = f 2 = • • • = f T (where V T = 0). Note that for α-exp-concave or λ-strongly convex functions, our guarantee is actually O(min{ d α log V T , √ V T }) or O(min{ 1 λ log V T , √ V T }), thus ensuring O( √ V T ) even when α = O( 1 /T ) or λ = O( 1 /T). This is because exp-concave and strongly convex functions are also convex and thus our convex bound is still applicable.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• 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). 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). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: This paper is a purely theoretical work, and we do not find specific societal impacts that should be highlighted here. 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). 
implication, application, and discussion: 
 In this section, we validate the effectiveness of our results by the implication of small-loss regret and the application in the SEA model. We also discuss the technical comparison with the previous correction-based approach [Yan et al., 2023] at the end of this section.In this part, we illustrate that our universal gradient-variation regret in Theorem 1 implies the universal small-loss regret measured by F T ≜ min x∈X t≤T f t (x) directly in analysis, i.e., without any algorithmic modification, and thus safeguards the case of F T ≤ V T , such as min x∈X f t (x) = 0 for any t ∈ [T ] (where F T = 0). The corresponding proof is provided in Appendix C.1. Theorem 2. Under Assumptions 1 and 2 (or the relaxed Assumption 3), if the online functions are non-negative, Algorithm 1 achieves O(log F T ), O(d log F T ), and O( √ F T ) for strongly convex, exp-concave, and convex functions, respectively.Theorem 2 achieves the same optimal small-loss bounds as Zhang et al. [2022a] . Combined with Theorem 1, our approach achieves the best known problem-dependent regret guarantees in the universal online learning problem. In the end, we emphasize again that our approach is efficient as it requires O(log T ) base learners and only 1 gradient query in each round.Stochastically extended adversarial (SEA) model [Sachs et al., 2022] interpolates between stochastic and adversarial online convex optimization. Formally, it assumes that the online function f t (•) is sampled stochastically from an adversarially chosen distribution F t . Denoting byF t (•) ≜ E ft∼Ft [f t (•)]the expected function, two quantities capture the essential characteristics of the SEA model: Sachs et al. [2022] initiated the study of the SEA model. For smooth expected functions {F t (•)} T t=1 , they achieved the optimal O( σ 2 1:T + Σ 2 1:T ) regret for convex expected functions, and O((σ 2 max + Σ 2 max ) log T ) in the strongly convex case, whereσ 2 1:T ≜ T t=1 max x∈X E ft∼Ft ∥∇f t (x) -∇F t (x)∥ 2 , Σ 2 1:T ≜ E T t=2 sup x∈X ∥∇F t (x) -∇F t-1 (x)∥ 2 , where σ 2 1:T is the variance in sampling f t (•) from F t (•) and Σ 2 1:T is the variation of {F t (•)} t∈[T ] .σ 2 max ≜ max t∈[T ] max x∈X E ft∼Ft [∥∇f t (x) - ∇F t (x)∥ 2 ] and Σ 2 max ≜ max t∈[T ] sup x∈X ∥∇F t (x) -∇F t-1 (x)∥ 2 . Subsequently, Chen et al. [2024] improved the strongly convex regret to O((σ 2 max +Σ 2 max ) log((σ 2 1:T +Σ 2 1:T )/(σ 2 max +Σ 2 max ))) and obtained O(d log(σ 2 1:T + Σ 2 1:T )) regret for exp-concave individual functions {f t (•)} T t=1. The gradient variation is essential in connecting the stochastic and adversarial optimization [Chen et al., 2023, Lemma 4] , which is also restated in (C.2). Therefore, universal gradient-variation regret can be applied to this problem, achieving the same best known bounds as Chen et al. [2024] , with a single algorithm. Table 2 compares our results with existing ones. The following theorem presents our results formally, with the corresponding proof provided in Appendix C.2. + Σ 2 max ) log T ) N/A O( σ 2 1:T + Σ 2 1:T ) ✗ Chen et al. [2024] O (σ 2 max + Σ 2 max ) log σ 2 1:T +Σ 2 1:T σ 2 max +Σ 2 max O(d log(σ 2 1:T + Σ 2 1:T )) O( σ 2 1:T + Σ 2 1:T ) ✗ Sachs et al. [2023] O((σ 2 max + Σ 2 max + D 2 L 2 ) log 2 T ) N/A O( √ T log T ) ✓ Yan et al. [2023] O((σ 2 max + Σ 2 max ) log(σ 2 1:T + Σ 2 1:T )) O(d log(σ 2 1:T + Σ 2 1:T )) O( (σ 2 1:T + Σ 2 1:T ) log(σ 2 1:T + Σ 2 1:T )) ✓ Ours O (σ 2 max + Σ 2 max ) log σ 2 1:T +Σ 2 1:T σ 2 max +Σ 2 max O(d log(σ 2 1:T + Σ 2 1:T )) O( σ 2 1:T + Σ 2 1:T ) ✓ Theorem 3. Under Assumption 1 and smoothness of F t (•) for any t ∈ [T ]: if F t (•) is convex, Algorithm 1 achieves O( σ 2 1:T + Σ 2 1:T ); if f t (•) is exp-concave, it achieves O(d log(σ 2 1:T + Σ 2 1:T )); and if F t (•) is strongly convex, it achieves O((σ 2 max + Σ 2 max ) log((σ 2 1:T + Σ 2 1:T )/(σ 2 max + Σ 2 max ))).Theorem 3 requires exp-concavity of the individual function f t (•) rather than the expected functionF t (•).This assumption is also used by Chen et al. [2023] and common in the studies of stochastic exp-concave optimization [Mahdavi et al., 2015, Koren and Levy, 2015] .In this part, we discuss the technical comparison with the previous correction-based approach [Yan et al., 2023] . Compared with their approach, ours is simpler and achieves the optimal universal problem-dependent regret (Theorem 1 and Theorem 2) and the best known guarantees in the SEA model (Theorem 3). Although not providing guarantees as favorable as ours, Yan et al. [2023] can control the overall algorithmic stability (i.e., ∥x t -x t-1 ∥ 2 ) using collaborative online ensemble [Zhao et al., 2024] , which is necessary in achieving fast rates in multi-player games [Syrgkanis et al., 2015] . For example, in a min-max game min x∈X max y∈Y x ⊤ Ay, where A is a game matrix, since A is unknown, the Nash equilibrium is typically computed through repeated play, i.e., player-x and player-y select {x t } T t=1 and {y t } T t=1 sequentially to approach the Nash equilibrium. For player-x, in the t-th round, it suffers a loss x ⊤ t Ay t and receives the gradient Ay t . Similarly, player-y suffers -x ⊤ t Ay t and receives -Ax t . For player-x, if it updates via OOMD, its gradient-variation regret contains ∥Ay t -Ay t-1 ∥ 2 , which includes the stability of player-y. In this case, to achieve fast rates, we indeed need to control the algorithm stability like ∥x t -x t-1 ∥ 2 and ∥y t -y t-1 ∥ 2 . This can be done by Yan et al. [2023] while this work cannot since we do not directly control the algorithmic stability. Interested readers can refer to Appendix A.2 in Yan et al. [2023] for more details. 
conclusion: 
 In this work, we investigate universal online learning with gradient-variation regret. We propose a simple two-layer online ensemble approach that not only achieves the optimal O( 1 λ log V T ), O( d α log V T ), and O( √ V T ) regret simultaneously for λ-strongly convex, α-exp-concave, and convex functions and is efficient with O(log T ) base learners and only 1 gradient query per round. This is done via the negative Bregman divergence term from linearization and the useful smoothness property of ∥∇f (x) -∇f (y)∥ 2 ≤ 2LD f (y, x). We further validate the effectiveness of our approach and results by implying the optimal universal small-loss regret directly in analysis and achieving the best known results in the stochastically extended adversarial model.Two future directions are worth investigating. The first is to reduce the number of projections to only 1 in each round [Mhammedi et al., 2019 , Zhao et al., 2022 , Yang et al., 2024] , thereby further improving the computational efficiency. The second direction involves extending our algorithm and results to the unconstrained setup [Orabona and Pál, 2016 , Cutkosky and Orabona, 2018 , Jacobsen and Cutkosky, 2022] , broadening its applicability across a wider range of scenarios. M. Li, T. Zhang, Y. Chen, and A. J. Smola. Efficient mini-batch training for stochastic optimization.In  
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: This paper does not include experiments (data or models), and thus poses no such risks.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.12. 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: This paper does not use 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. 
 
 Appendix: In this section, we propose a relaxation of the smoothness requirement to a slightly larger domain than the feasible domain X , in contrast to the whole R d space as in Assumption 2. The relaxed smoothness assumption is detailed in the following. Assumption 3 (Relaxed Smoothness). Under the condition of ∥∇f t (x)∥ ≤ G for any x ∈ X and t ∈ [T ], all online functions are L-smooth: ∥∇f t (x) -∇f t (y)∥ ≤ L∥x -y∥ for any t ∈ [T ] and x, y ∈ X + , whereX + ≜ {x + b | x ∈ X , b ∈ G /L • B} and B ≜ {x | ∥x∥ ≤ 1} is a unit ball.The domain of Assumption 3 is slightly larger than X -for any x + ∈ X + , we can always find anx ∈ X such that ∥x + -x∥ ≤ G /L. In this work, one of the key technical contributions is to handle the empirical gradient variation via a useful smoothness property (Proposition 1). We show in the following that this condition can be satisfied by requiring only Assumption 3. Lemma 1. Under Assumption 1, for any online function f (•) satisfying Assumption 3, it holds that ∥∇f (x) -∇f (y)∥ 2 ≤ 2LD f (y, x) for any x, y ∈ X .Proof. To begin with, we present the self-bounding property [Srebro et al., 2010] , which is useful in proving our result -if a function f : R d → R is L-smooth and bounded from below, then for anyx ∈ R d , it holds that ∥∇f (x)∥ 2 ≤ 2L f (x) -inf y∈R d f (y) . (A.1)Next, we aim to prove that if we only need (A.1) on a bounded domain X , we require smoothness only on a slightly larger domain than X . To see this, we delve into the proof of the self-bounding property. Specifically, for any x, v ∈ R d , it holds that⟨-∇f (x), v⟩ - L 2 ∥v∥ 2 ≤ f (x) -f (x + v) ≤ f (x) -inf y∈R d f (y),where the first step requires smoothness on x and x + v. Consequently, by taking maximization over v, it holds thatf (x) -inf y∈R d f (y) ≥ sup v∈R d ⟨-∇f (x), v⟩ - L 2 ∥v∥ 2 = 1 2L ∥∇f (x)∥ 2 ,which leads to the self-bounding property (A.1) by taking v = -1 L ∇f (x). The above proof is from Theorem 4.23 of Orabona [2019] . This means that for the self-bounding property, we only require the smoothness to hold for any x ∈ X and x -1 L ∇f (x). Under Assumption 1, this can be satisfied by requiring smoothness on a slightly larger domain than X , namely, X + ≜ {x+b|x ∈ X , b ∈ G /L•B}. Now we are ready to prove the final result. To begin with, we define a surrogate function of g(x) ≜ f (x) -⟨∇f (x 0 ), x⟩ for any x ∈ X , where x 0 ∈ X . Due to the above property we have just proved, by requiring smoothness on X + , we have∥∇g(x)∥ 2 ≤ 2L g(x) -inf y∈R d g(y) .Denoting by y ⋆ ∈ arg min y∈R d g(y), the above inequality equals to∥∇f (x) -∇f (x 0 )∥ 2 ≤ 2L (f (x) -⟨∇f (x 0 ), x⟩ -f (y ⋆ ) + ⟨∇f (x 0 ), y ⋆ ⟩) = 2L(f (x) -f (y ⋆ ) -⟨∇f (x 0 ), x -y ⋆ ⟩),due to the definition of g(•). The proof using the self-bounding property is from Theorem 2.1.5 of Nesterov [2018] . Finally, we note that g(•) is minimized at y ⋆ = x 0 , leading to ∥∇f (x) -∇f (x 0 )∥ 2 ≤ 2LD f (x 0 , x) for any x, x 0 ∈ X , which finishes the proof.In this section, we provide the proof of Theorem 1, our main theoretical result for the optimal universal gradient-variation regret.Proof. We first give different decompositions of the regret for different curvature types, then analyze the meta and base regret, and finally combine them to achieve the regret bound. For simplicity, we define g t ≜ ∇f t (x t ) andVT ≜ T t=2 ∥∇f t (x t ) -∇f t-1 (x t-1 )∥ 2for short. Using the analysis in Section 3.2, the empirical gradient variation can bounded asVT ≤ 3 T t=2 ∥∇f t (x t ) -∇f t (x ⋆ )∥ 2 + 3 T t=2 ∥∇f t (x ⋆ ) -∇f t-1 (x ⋆ )∥ 2 + 3 T t=2 ∥∇f t-1 (x ⋆ ) -∇f t-1 (x t-1 )∥ 2 ≤ 6L T t=2 D ft (x ⋆ , x t ) + 3V T + 6L T t=2 D ft-1 (x ⋆ , x t-1 ) ≤ 3V T + 12L T t=1 D ft (x ⋆ , x t ). (B.1)Regret Decomposition. Denoting by x ⋆ ∈ arg min x∈X t∈[T ] f t (x), for convex functions, we decompose the regret asREG T = T t=1 ⟨g t , x t -x ⋆ ⟩ - T t=1 D ft (x ⋆ , x t ) (by (3.3)) = T t=1 ⟨g t , x t -x t,i ⋆ ⟩ META-REG + T t=1 h c t,i ⋆ (x t,i ⋆ ) - T t=1 h c t,i ⋆ (x ⋆ ) BASE-REG - T t=1 D ft (x ⋆ , x t ), (B.2)where h c t,i (x) ≜ ⟨g t , x⟩. For α-exp-concave functions, we decompose the regret asREG T = T t=1 ⟨g t , x t -x ⋆ ⟩ - 1 2 T t=1 D ft (x ⋆ , x t ) - 1 2 T t=1 D ft (x ⋆ , x t ) (by (3.3)) ≤ T t=1 ⟨g t , x t -x ⋆ ⟩ - α 4 T t=1 ⟨g t , x t -x ⋆ ⟩ 2 - 1 2 T t=1 D ft (x ⋆ , x t ) ≤ T t=1 ⟨g t , x t -x t,i ⋆ ⟩ - α i ⋆ 4 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 META-REG (by α i ⋆ ≤ α ≤ 2α i ⋆ ) + T t=1 h exp t,i ⋆ (x t,i ⋆ ) - T t=1 h exp t,i ⋆ (x ⋆ ) BASE-REG - 1 2 T t=1 D ft (x ⋆ , x t ), (B.3)where the second step is due to the definitions of exp-concavity and Bregman divergence and the last step is due to the definition of the surrogate functionh exp t,i (x) ≜ ⟨g t , x⟩ + αi 4 ⟨∇f t (x t ), x -x t ⟩ 2, where α i ∈ H, defined in (2.1). For λ-strongly convex functions, following the similar decomposition in the exp-concavity case, we obtainREG T ≤ T t=1 ⟨g t , x t -x t,i ⋆ ⟩ - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 META-REG (by λ i ⋆ ≤ λ ≤ 2λ i ⋆ ) + T t=1 h sc t,i ⋆ (x t,i ⋆ ) - T t=1 h sc t,i ⋆ (x ⋆ ) BASE-REG - 1 2 T t=1 D ft (x ⋆ , x t ), (B.4)due to the definition of the surrogate h sc t,i (x) ≜ ⟨g t , x⟩ + λi 4 ∥x -x t ∥ 2 , where λ i ∈ H in (2.1).Meta Regret Analysis. We adopt OPTIMISTIC-ADAPT-ML-PROD [Wei et al., 2016] as the meta learner, and present its regret analysis below for self-containedness.Lemma 2 (Theorem 3.4 of Wei et al. [2016] ). Denoting by p t the weights of the algorithm, ℓ t the loss vector, and m t,i the optimism, by choosing the learning rate optimally asε t,i = min 1 8 , ln N s∈[t] (r s,i -m s,i ) 2 , (B.5)the regret of OPTIMISTIC-ADAPT-ML-PROD with respect to any expert i ∈[N ] satisfies T t=1 ⟨ℓ t , p t -e i ⟩ ≤ C 0 1 + T t=1 (r t,i -m t,i ) 2 + C 1 ,where r t,i = ⟨ℓ t , p t -e i ⟩, e i denotes the i-th standard basis vector, C 0 = √ ln N + ln(1 + N e (1 + ln(T + 1)))/ √ ln N , andC 1 = 1 4 (ln N + ln(1 + N e (1 + ln(T + 1)))) + 2 √ ln N + 16 ln N .Here we adopt ℓ t,i = ⟨g t , x t,i ⟩ such that ⟨ℓ t , p t -e i ⟩ = ⟨g t , x t -x t,i ⟩. Besides, since the number of base learners N = O(log T ) as explained in Section 2, the constants C 0 and C 1 are in the order of O(log log T ) and can be treated as ignorable constants, following previous convention [Luo and Schapire, 2015, Gaillard et al., 2014] .For convex functions, we choose the optimism as m t,i = ⟨g t-1 , x t -x t,i ⟩ for the index i indicating the convex base learner. As explained in Section 3.1, although x t is unknown for now, we only require the scalar value of ⟨g t-1 , x t ⟩. Denoting by z = ⟨g t-1 , x t ⟩, it actually forms a fixed-point problem of z = ⟨g t-1 , x t (z)⟩, where x t is a function of z since x t depends on p t,i , p t,i relies on m t,i , and m t,i depends on z. Such a one-dimensional fixed-point problem can be solved with an O(1/T ) approximation error through O(log T ) binary searches, and aggregating the approximate error over the whole time horizon will only incur an additive constant to the final regret. As a result, such an optimism setup is valid. Consequently, the meta regret in (B.2) can be bounded asMETA-REG ≤ C 0 1 + T t=1 ⟨g t -g t-1 , x t -x t,i ⋆ ⟩ 2 + C 1 (by Lemma 2) ≤ C 0 1 + D 2 VT + C 1 ≤ C 0 1 + 3D 2 V T + 12LD 2 T t=1 D ft (x ⋆ , x t ) + C 1 (by (B.1)) ≤ O( V T ) + C 0 12LD 2 T t=1 D ft (x ⋆ , x t ) ≤ O( V T ) + O(C 2 ) + C 0 2C 2 T t=1 D ft (x ⋆ , x t ),where the second step adopts Assumption 1, the fourth step uses √ a + b ≤ √ a + √ b for any a, b ≥ 0, the last step uses AM-GM inequality:√ ab ≤ ax 2 + b 2x for any a, b, x > 0.Note that C 2 is used to ensure the positive Bregman divergence term to be canceled and will be specified in the end.For exp-concave functions, we choose the optimism as m t,i = 0 for indexes i indicating exp-concave base learners. By Lemma 2, the meta regret in (B.3) can be bounded asMETA-REG ≤ C 0 1 + T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 - α i ⋆ 4 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 + C 1 ≤ O(C 3 ) + C 0 2C 3 - α i ⋆ 4 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 , (B.6)where the last step omits the ignorable additive C 0 or C 1 terms and is due to AM-GM inequality. C 2 is a constant to be specified.For strongly convex functions, we choose the optimism m t,i = 0 for indexes i indicating strongly convex base learners. By Lemma 2, the meta regret in (B.4) can be bounded asMETA-REG ≤C 0 1 + T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 + C 1 (by Lemma 2) ≤ C 0 1 + D 2 T t=1 ∥x t -x t,i ⋆ ∥ 2 - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 + C 1 (by Assumption 1) ≤ O(C 4 ) + C 0 D 2 2C 4 - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 , (B.7)where the last step omits the ignorable additive C 0 or C 1 terms and is due to AM-GM inequality. C 4 is a constant to be specified.Base Regret Analysis. For convex functions, we implement Optimistic OGD (OOGD) on the convex base learner (indexed by i):x t,i = Π X [ x t,i -η t m t ], x t+1,i = Π X [ x t,i -η t ∇h c t,i (x t,i )]. (B.8)By choosing the step size asη t = min{D/ 1 + t-1 s=2 ∥∇h c s,i (x s,i ) -∇h c s-1,i (x s-1,i )∥ 2 , 1}and the optimism as m t = ∇h c t-1,i (x t-1,i ), due to the standard analysis of OOGD for convex functions (e.g., Lemma 10 of Yan et al. [2023] ), the base regret can be bounded asBASE-REG ≤ 5D 1 + T t=2 ∥∇h c t,i ⋆ (x t,i ⋆ ) -∇h c t-1,i ⋆ (x t-1,i ⋆ )∥ 2 + O(1) = 5D 1 + VT + O(1) ≤ O( V T ) + 5D 12L T t=1 D ft (x ⋆ , x t ) (by (B.1)) ≤ O( V T ) + O(C 5 ) + 5D 2C 5 T t=1 D ft (x ⋆ , x t ),where the second step is due to the property of the surrogate function: ∇h c t,i (x t,i ) = g t , and the last step uses AM-GM inequality. C 5 is a constant to be specified.For exp-concave functions, we run OOMD on the exp-concave base learners (indexed by i):x t,i = arg min x∈X {⟨m t , x⟩ + D ψt (x, x t,i )} , x t+1,i = arg min x∈X ⟨∇h exp t,i (x t,i ), x⟩ + D ψt (x, x t,i ) . Choosing ψ t (x) = 1 2 x ⊤ U t x for any x, U t = (1 + αiG 2 2 )I + αi 2 t-1 s=1 ∇h exp s,i (x s,i )∇h exp s,i (x s,i ) ⊤ , and m t = ∇h exp t-1,i (x t-1,i), due to the standard analysis of OOMD for exp-concave functions (e.g., Lemma 11 of Yan et al. [2023] ), the base regret can be bounded asBASE-REG ≤ 16d α i ⋆ ln 1 + α i ⋆ 8d T t=2 ∇h exp t,i ⋆ (x t,i ⋆ ) -∇h exp t-1,i ⋆ (x t-1,i ⋆ ) 2 + O(1). (B.9)Next, we analyze the empirical gradient variation defined on the surrogate function h exp t,i (•): (by (B.1) and Assumption 1)T t=2 ∇h exp t,i ⋆ (x t,i ⋆ ) -∇h exp t-1,i ⋆ (x t-1,i ⋆ ) 2 = T t=2 g t + α i ⋆ 2 g t ⟨g t , x t -x t,i ⋆ ⟩ -g t-1 - α i ⋆ 2 g t-1 ⟨g t-1 , x t-1 -x t-1,i ⋆ ⟩ 2 ≤ 3 VT + 3 T t=2 α i ⋆ 2 g t ⟨g t , x t -x t,i ⋆ ⟩ 2 + 3 T t=2 α i ⋆ 2 g t-1 ⟨g t-1 , x t-1 -x t-1,i ⋆ ⟩ 2 ≤ 3 VT + 6 T t=1 α i ⋆ 2 g t ⟨g t , x t -x t,i ⋆ ⟩ 2 (B.10) ≤ 9V T + 36L T t=1 D ft (x ⋆ , x t ) + 2α 2 i ⋆ G 2 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 ,where the first step is due to the property of the surrogate function: ∇h exp t,i (x t,i ) = g t + αi 2 g t ⟨g t , x tx t,i ⟩, the second step is by the Cauchy-Schwarz inequality: (a + b + c) 2 ≤ 3(a 2 + b 2 + c 2 ) for any a, b, c ∈ R. Plugging the surrogate's empirical gradient variation back to the base regret, we obtainBASE-REG ≤ 16d α i ⋆ ln 1 + 9α i ⋆ 8d V T + 9α i ⋆ L 2d T t=1 D ft (x ⋆ , x t ) + α 3 i ⋆ G 2 4d T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 ≤ O d α ln(C 6 V T ) + 16d C 6 α i ⋆ 9α i ⋆ L 2d T t=1 D ft (x ⋆ , x t ) + α 3 i ⋆ G 2 4d T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 ≤ O d α ln V T + 72L C 6 T t=1 D ft (x ⋆ , x t ) + 4G 2 C 6 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 + O(ln C 6 ).The second step requires C 6 ≥ 1 by Lemma 5 and uses the property of the best base learner, i.e.,α i ⋆ ≤ α ≤ 2α i ⋆ . The last step is because of α i ≤ 1.For strongly convex functions, we run OOGD (B.8) on the strongly convex base learners (indexed by i). Specifically, by choosing the step size as η t = 2/(1+λ i t) and the optimism as m t = ∇h sc t-1,i (x t-1,i ), due to the analysis of OOGD for strongly convex functions (e.g., Lemma 12 of Yan et al. [2023] ), the base regret can be bounded asBASE-REG ≤ 16G 2 λ i ⋆ ln 1 + λ i ⋆ T t=2 ∇h sc t,i ⋆ (x t,i ⋆ ) -∇h sc t-1,i ⋆ (x t-1,i ⋆ ) 2 + O(1). (B.11)Next, we analyze the empirical gradient variation defined on the surrogate function h sc t,i (•):T t=2 ∇h sc t,i ⋆ (x t,i ⋆ ) -∇h sc t-1,i ⋆ (x t-1,i ⋆ ) 2 = T t=2 g t + λ i ⋆ 2 (x t,i ⋆ -x t ) -g t-1 - λ i ⋆ 2 (x t-1,i ⋆ -x t-1 ) 2 ≤ 3 VT + 3 T t=2 λ i ⋆ 2 (x t,i ⋆ -x t ) 2 + 3 T t=2 λ i ⋆ 2 (x t-1,i ⋆ -x t-1 ) 2 (B.12) ≤ 9V T + 36L T t=1 D ft (x ⋆ , x t ) + 2λ 2 i ⋆ T t=1 ∥x t,i ⋆ -x t ∥ 2 , (by (B.1))where the first step is due to the property of the surrogate:∇h sc t,i (x t,i ) = g t + λi 2 (x t,i -x t ), and the second step is due to the Cauchy-Schwarz inequality. Plugging the surrogate's empirical gradient variation back to the base regret, we obtainBASE-REG ≤ 16G 2 λ i ⋆ ln 1 + 9λ i ⋆ V T + 36Lλ i ⋆ T t=1 D ft (x ⋆ , x t ) + 2λ 3 i ⋆ T t=1 ∥x t,i ⋆ -x t ∥ 2 ≤ O 1 λ ln(C 7 V T ) + 16G 2 C 7 λ i ⋆ 36Lλ i ⋆ T t=1 D ft (x ⋆ , x t ) + 2λ 3 i ⋆ T t=1 ∥x t,i ⋆ -x t ∥ 2 ≤ O 1 λ ln V T + 576G 2 L C 7 T t=1 D ft (x ⋆ , x t ) + 32G 2 C 7 T t=1 ∥x t,i ⋆ -x t ∥ 2 + O(ln C 7 ),where the second step requires C 7 ≥ 1 by Lemma 5 and uses the property of the best base learner, i.e., λ i ⋆ ≤ λ ≤ 2λ i ⋆ . The last step is due to λ i ≤ 1.Regret Analysis. For convex functions, by combining the meta and base regret, it holds thatREG T ≤ O( V T ) + O(C 2 + C 5 ) + C 0 2C 2 + 5D 2C 5 -1 T t=1 D ft (x ⋆ , x t ) ≤ O( V T ),by choosing C 2 = C 0 and C 5 = 5D. For exp-concave functions, by combining the meta and base regret, it holds thatREG T ≤ O d α ln V T + O(C 3 + ln C 6 ) + C 0 2C 3 + 4G 2 C 6 - α i ⋆ 4 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 + 72L C 6 - 1 2 T t=1 D ft (x ⋆ , x t ) ≤ O d α ln V T , by choosing C 6 = max{1, 144L, 32G 2 α i ⋆ } and C 3 = 4C0 α i ⋆ .Note that such a parameter configuration will only add an O(1/α) factor to the final regret bound, which can be absorbed. For strongly convex functions, by combining the meta and base regret, it holds thatREG T ≤ O 1 λ ln V T + O(C 4 + ln C 7 ) + C 0 D 2 2C 4 + 32G 2 C 7 - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 + 576G 2 L C 7 - 1 2 T t=1 D ft (x ⋆ , x t ) ≤ O 1 λ ln V T , by choosing C 7 = max{1, 1152G 2 L, 256G 2 λ i ⋆ } and C 4 = 4C0D 2 λ i ⋆ .Note that such a parameter configuration will only add an O(1/λ) factor to the final regret bound, which can be absorbed.Note that the constants C 2 , C 3 , C 4 , C 5 , C 6 , C 7 only exist in analysis and thus can be chosen arbitrarily, finishing the proof.In this section, we provide proofs for Section 4, including Theorem 2 and Theorem 3.Proof. To begin with, we give a different decomposition for the empirical gradient variation VT :VT ≤ 2 T t=2 ∥g t ∥ 2 + 2 T t=2 ∥g t-1 ∥ 2 ≤ 4 T t=1 ∥g t ∥ 2 ≤ 16L T t=1 f t (x t ), (C.1)where the last step is by the self-bounding property (A.1) for non-negative functions. For simplicity, we denote by FT ≜ T t=1 f t (x t ). The regret decomposition is the same as that in the proof of Theorem 1 (i.e., (B.2), (B.3), and (B.4)), and thus omitted here. In the following, we analyze the meta and base regret, and combine them for the final regret bounds.Meta Regret Analysis. Our Algorithm 1 achieves the small-loss bounds without modifying the algorithm. As a result, the meta algorithm and the corresponding step size and optimism configurations are the same as that in the proof of Theorem 1.For convex functions, by choosing the optimism as m t,i = ⟨g t-1 , x t -x t,i ⟩ for the index i indicating the base learner for the convex case, the meta regret in (B.2) can be bounded asMETA-REG ≤ C 0 1 + T t=1 ⟨g t -g t-1 , x t -x t,i ⋆ ⟩ 2 + C 1 (by Lemma 2) ≤ C 0 1 + D 2 VT + C 1 ≤ C 0 1 + 16D 2 L FT + C 1 .(by Assumption 1 and (C.1))For exp-concave functions, we choose the optimism as m t,i = 0 for indexes i indicating the expconcave base learners. The meta regret is bounded in the same way as (B.6).For strongly convex functions, we choose the optimism as m t,i = 0 for indexes i indicating the strongly convex base learners. The meta regret is bounded in the same way as (B.7).Base Regret Analysis. For convex functions, using the same base algorithms as in the proof of Theorem 1, the base regret can be bounded asBASE-REG ≤ 5D 1 + VT + O(1) ≤ 5D 1 + 16L FT + O(1).For exp-concave functions, using the same base algorithms as in the proof of Theorem 1, the base regret can be bounded by (B.9). Following (B.10), the empirical gradient variation defined on the surrogate function h exp t,i (•) can be bounded asT t=2 ∇h exp t,i ⋆ (x t,i ⋆ ) -∇h exp t-1,i ⋆ (x t-1,i ⋆ ) 2 ≤ 3 VT + 6 T t=1 α i ⋆ 2 g t ⟨g t , x t -x t,i ⋆ ⟩ 2 ≤ 48L FT + 2α 2 i ⋆ G 2 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 .(by Assumption 1 and (C.1))Plugging the surrogate's empirical gradient variation back to the base regret, we obtainBASE-REG ≤ 16d α i ⋆ ln 1 + 6Lα i ⋆ d FT + α 3 i ⋆ G 2 4d T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 + O(1) ≤ 16d α i ⋆ ln C 8 1 + 6Lα i ⋆ d FT + 16d C 8 α i ⋆ α 3 i ⋆ G 2 4d T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 ≤ 32d α ln 1 + 6L d FT + 4G 2 C 8 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 + O(ln C 8 ),where the second step requires C 8 ≥ 1 by Lemma 5 and uses the property of the best base learner, i.e., α i ⋆ ≤ α ≤ 2α i ⋆ . The last step is due to α i ≤ 1.For strongly convex functions, using the same base algorithms as in the proof of Theorem 1, the base regret can be bounded by (B.11) . Following (B.12), the empirical gradient variation defined on the surrogate function h sc t,i (•) can be bounded asT t=2 ∇h sc t,i ⋆ (x t,i ⋆ ) -∇h sc t-1,i ⋆ (x t-1,i ⋆ ) 2 ≤ 3 VT + 6 T t=1 λ i ⋆ 2 (x t,i ⋆ -x t ) 2 ≤ 48L FT + 2λ 2 i ⋆ T t=1 ∥x t,i ⋆ -x t ∥ 2 .(by (C.1))Plugging the surrogate's empirical gradient variation back to the base regret, we obtainBASE-REG ≤ 16G 2 λ i ⋆ ln 1 + 48Lλ i ⋆ FT + 2λ 3 i ⋆ T t=1 ∥x t,i ⋆ -x t ∥ 2 + O(1) ≤ 16G 2 λ i ⋆ ln C 9 1 + 48Lλ i ⋆ FT + 16G 2 C 9 λ i ⋆ 2λ 3 i ⋆ T t=1 ∥x t,i ⋆ -x t ∥ 2 ≤ 32G 2 λ ln(1 + 48L FT ) + 32G 2 C 9 T t=1 ∥x t,i ⋆ -x t ∥ 2 + O(ln C 9 ),where the second step requires C 9 ≥ 1 by Lemma 5 and uses the property of the best base learner, i.e., λ i ⋆ ≤ λ ≤ 2λ i ⋆ . The last step is due to λ i ≤ 1.Regret Analysis. For convex functions, by combining the meta and base regret, it holds thatREG T ≤ C 0 1 + 16D 2 L FT + 5D 1 + 16L FT + C 1 ≤ O( F T ),where the last step is due to Lemma 9 of Zhao et al. [2024] , restated below for self-containedness.Lemma 3 (Lemma 9 of Zhao et al. [2024] ). For any x, y, a, b > 0 satisfying x -y ≤ √ ax + b, it holds that x -y ≤ √ ay + ab + a + b.For exp-concave functions, by combining the meta and base regret, it holds thatREG T ≤ C 0 2C 3 + 4G 2 C 8 - α i ⋆ 4 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 + 32d α ln 1 + 6L d FT + O(C 3 + ln C 8 ) ≤ 32d α ln 1 + 6L d FT + O(1) ≤ O d α ln F T , (by Lemma 6)where the second step choosesC 3 = 4C0 α i ⋆ and C 8 = max{1, 32G 2 α i ⋆ }.Note that such a parameter configuration will only add an O(1/α) factor to the final regret bound, which can be absorbed.For strongly convex functions, by combining the meta and base regret, it holds thatEQUATIONwhere the second step is by choosingC 4 = 4C0D 2 λ i ⋆and C 9 = max{1, 256G 2 λ i ⋆ }. Note that such a parameter configuration will only add an O(1/λ) factor to the final regret bound, which can be absorbed. Also note that the constants C 3 , C 4 , C 8 , C 9 only exist in analysis and thus can be chosen arbitrarily, finishing the proof.Proof. To begin with, we give a different analysis of the empirical gradient variation:E[ VT ] ≤ 5E T t=2 ∥∇f t (x t ) -∇F t (x t )∥ 2 + 5 T t=2 ∥∇F t (x t ) -∇F t (x ⋆ )∥ 2 +5E T t=2 ∥∇F t (x ⋆ ) -∇F t-1 (x ⋆ )∥ 2 + 5 T t=2 ∥∇F t-1 (x ⋆ ) -∇F t-1 (x t-1 )∥ 2 +5E T t=2 ∥∇F t-1 (x t-1 ) -∇f t-1 (x t-1 )∥ 2 ≤ 10σ 2 1:T + 5Σ 2 1:T + 20L T t=1 D Ft (x ⋆ , x t ), (C.2)where the first step is due to Cauchy-Schwarz inequality and the last step is because of the definitions of σ 2 1:T and Σ 2 1:T (given in Section 4) and the analysis proposed in Section 3.2. In the following, we first give regret decompositions for different curvature types, then we analyze the meta and base regret, and combine them for the final regret guarantees.Regret Decomposition. Denoting by x ⋆ ∈ arg min x∈X t∈[T ] f t (x), for convex functions, we decompose the regret asE[REG T ] = E T t=1 F t (x t ) - T t=1 F t (x ⋆ ) = E T t=1 ⟨∇F t (x t ), x t -x ⋆ ⟩ - T t=1 D Ft (x ⋆ , x t ) = E T t=1 ⟨∇f t (x t ), x t -x ⋆ ⟩ - T t=1 D Ft (x ⋆ , x t ) = E T t=1 ⟨g t , x t -x t,i ⋆ ⟩ META-REG + E T t=1 h c t,i ⋆ (x t,i ⋆ ) -h c t,i ⋆ (x ⋆ ) BASE-REG - T t=1 D Ft (x ⋆ , x t ),where the first and third step use F t (x) = E[f t (x)], the second step uses the definition of Bregman divergence, and the fourth step is due to h c t,i (x) ≜ ⟨g t , x⟩. For exp-concave functions, following the similar decomposition as in the proof of Theorem 1 in Appendix B, we decompose the regret asE[REG T ] = E T t=1 ⟨∇F t (x t ), x t -x ⋆ ⟩ - 1 2 T t=1 D Ft (x ⋆ , x t ) - 1 2 T t=1 D Ft (x ⋆ , x t ) = E T t=1 ⟨∇f t (x t ), x t -x ⋆ ⟩ - 1 2 T t=1 D ft (x ⋆ , x t ) - 1 2 T t=1 D Ft (x ⋆ , x t ) ≤ E T t=1 ⟨g t , x t -x ⋆ ⟩ - α 4 T t=1 ⟨g t , x t -x ⋆ ⟩ 2 - 1 2 T t=1 D Ft (x ⋆ , x t ) ≤ T t=1 ⟨g t , x t -x t,i ⋆ ⟩ - α i ⋆ 4 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 META-REG + E T t=1 h exp t,i ⋆ (x t,i ⋆ ) -h exp t,i ⋆ (x ⋆ ) BASE-REG - 1 2 T t=1 D Ft (x ⋆ , x t ),where the second step uses the definition of the expected function F t (•), the third step requires the exp-concavity of f t (•), and the fourth step is due to h exp t,i (x) ≜ ⟨g t , x⟩ + αi 4 ⟨∇f t (x t ), xx t ⟩ 2 , where α i ∈ H, defined in (2.1). For strongly convex functions, following the similar decomposition as in Appendix B, we decompose the regret asE[REG T ] = E T t=1 ⟨∇F t (x t ), x t -x ⋆ ⟩ - 1 2 T t=1 D Ft (x ⋆ , x t ) - 1 2 T t=1 D Ft (x ⋆ , x t ) ≤ E T t=1 ⟨g t , x t -x ⋆ ⟩ - λ 4 T t=1 ∥x t -x ⋆ ∥ 2 - 1 2 T t=1 D Ft (x ⋆ , x t ) ≤ T t=1 ⟨g t , x t -x t,i ⋆ ⟩ - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 META-REG + E T t=1 h sc t,i ⋆ (x t,i ⋆ ) -h sc t,i ⋆ (x ⋆ ) BASE-REG - 1 2 T t=1 D Ft (x ⋆ , x t ),where the second step, different from the exp-concave case, only requires the strong convexity of F t (•), and the third step is due to h sc t,i (x) ≜ ⟨g t , x⟩ + λi 4 ∥x -x t ∥ 2 , where λ i ∈ H, defined in (2.1).Meta Regret Analysis. Our Algorithm 1 can be applied to the SEA model without any algorithm modifications. As a result, we directly use the same parameter configurations as in the proof of Theorem 1 (i.e., in Appendix B).For convex functions, the meta regret can be bounded asMETA-REG ≤ E C 0 1 + D 2 VT + C 1 ≤ C 0 1 + D 2 E[ VT ] + C 1 ≤ C 0 1 + 5D 2 (2σ 2 1:T + Σ 2 1:T ) + 20D 2 L T t=1 D Ft (x ⋆ , x t ) + C 1 (by (C.2)) ≤ O σ 2 1:T + Σ 2 1:T + O(C 10 ) + C 0 2C 10 T t=1 D Ft (x ⋆ , x t ),where the second step is by Jensen's inequality and the last step is due to AM-GM inequality. C 10 is a constant to be specified.For exp-concave and strongly convex functions, the meta regret is bounded in the same way as (B.6) and (B.7), and thus omitted here.Base Regret Analysis. For convex functions, the base regret can be bounded asBASE-REG ≤ 5D 1 + E[ VT ] ≤ 5D 1 + 10σ 2 1:T + 5Σ 2 1:T + 20L T t=1 D Ft (x ⋆ , x t ) ≤ O σ 2 1:T + Σ 2 1:T + O(C 11 ) + 5D 2C 11 T t=1 D Ft (x ⋆ , x t ),where the first step is by Jensen's inequality, the second step is due to (C.2), and the last step is because of AM-GM inequality. C 11 is a constant to be specified.For exp-concave functions, the base regret is bounded by (B.9). Following (C.2), we control the empirical gradient variation defined on surrogates asE T t=2 ∇h exp t,i ⋆ (x t,i ⋆ ) -∇h exp t-1,i ⋆ (x t-1,i ⋆ ) 2 ≤ 3E[ VT ] + 6 T t=1 α i ⋆ 2 g t ⟨g t , x t -x t,i ⋆ ⟩ 2 ≤ 15(2σ 2 1:T + Σ 2 1:T ) + 60L T t=1 D Ft (x ⋆ , x t ) + 2α 2 i ⋆ G 2 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 .Plugging the surrogate's empirical gradient variation back to the base regret, we obtainBASE-REG ≤ 16d α i ⋆ ln 1 + 15α i ⋆ 8d (2σ 2 1:T + Σ 2 1:T ) + 15Lα i ⋆ 2d T t=1 D Ft (x ⋆ , x t ) + α 3 i ⋆ G 2 4d T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 ≤ O d α ln σ 2 1:T + Σ 2 1:T + O(ln C 12 ) + 120L C 12 T t=1 D Ft (x ⋆ , x t ) + 4G 2 C 12 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 ,where the second step requires C 12 ≥ 1 by Lemma 5.For strongly convex functions, we need to delve into the proof details of the base algorithm, i.e., OOGD (B.8) with step size η t = 2/(1 + λ i t) and optimism m t = ∇h sc t-1,i (x t-1,i ). For example, from Lemma 12 of Yan et al. [2023] , the base regret can be bounded asBASE-REG ≤ 4 T t=2 1 λ i ⋆ t E ∇h sc t,i ⋆ (x t,i ⋆ ) -∇h sc t-1,i ⋆ (x t-1,i ⋆ ) 2 + O(1).Subsequently, we analyze the empirical gradient variation defined on surrogates in each round, i.e.,∥∇h sc t,i ⋆ (x t,i ⋆ ) -∇h sc t-1,i ⋆ (x t-1,i ⋆ )∥ 2 . Denoting by σ 2 t ≜ max x∈X E ft∼Ft [∥∇f t (x) -∇F t (x)∥ 2 ] and Σ 2 t ≜ E[sup x∈X ∥∇F t (x) -∇F t-1 (x)∥ 2 ] for simplicity, E ∇h sc t,i ⋆ (x t,i ⋆ ) -∇h sc t-1,i ⋆ (x t-1,i ⋆ ) = E g t + λ i ⋆ 2 (x t,i ⋆ -x t ) -g t-1 - λ i ⋆ 2 (x t-1,i ⋆ -x t-1 ) 2 ≤ 3E ∥g t -g t-1 ∥ 2 + 3 λ i ⋆ 2 (x t,i ⋆ -x t ) 2 + 3 λ i ⋆ 2 (x t-1,i ⋆ -x t-1 ) 2 ≤ 15(σ 2 t + σ 2 t-1 + 2LD Ft (x ⋆ , x t ) + 2LD Ft-1 (x ⋆ , x t-1 ) + Σ 2 t ) (by (C.2)) + λ 2 i ⋆ ∥x t,i ⋆ -x t ∥ 2 + λ 2 i ⋆ ∥x t-1,i ⋆ -x t-1 ∥ 2, where the first step is due to the property of the surrogate: ∇h sc t,i (x t,i ) = g t + λi 2 (x t,i -x t ), and the second step is due to the Cauchy-Schwarz inequality. Plugging the above term back into the base regret and omitting the ignorable O(1) term, we achieveBASE-REG ≤ 60 λ i ⋆ T t=2 σ 2 t + σ 2 t-1 + Σ 2 t t + 120L T t=2 D Ft (x ⋆ , x t ) + D Ft-1 (x ⋆ , x t-1 ) λ i ⋆ t + 4 T t=2 λ 2 i ⋆ ∥x t,i ⋆ -x t ∥ 2 + λ 2 i ⋆ ∥x t-1,i ⋆ -x t-1 ∥ 2 λ i ⋆ t ,To handle the above term of T t=1 a t /t for some variable sequence {a t } T t=1 , we import a useful lemma from Yan et al. [2023] .Lemma 4 (Lemma 9 of Yan et al. [2023] ). For a sequence of {a t } T t=1 and b, where a t , b > 0 for any t ∈ [T ], denoting by a max ≜ max t a t and A ≜ ⌈b T t=1 a t ⌉, we haveT t=1 a t bt ≤ a max b (1 + ln A) + 1 b 2 .Using Lemma 4, we control the base regret asBASE-REG ≤ O 1 λ σ 2 max + Σ 2 max ln σ 2 1:T + Σ 2 1:T σ 2 max + Σ 2 max + 480LGD λ i ⋆ ln 1 + 2λ i ⋆ T t=1 D Ft (x ⋆ , x t ) + 8D 2 λ i ⋆ ln 1 + 2λ 3 i ⋆ T t=1 ∥x t,i ⋆ -x t ∥ 2 ≤ O 1 λ σ 2 max + Σ 2 max ln σ 2 1:T + Σ 2 1:T σ 2 max + Σ 2 max + O(ln C 13 + ln C 14 ) + 960LGD C 13 T t=1 D Ft (x ⋆ , x t ) + 16D 2 C 14 T t=2 ∥x t,i ⋆ -x t ∥ 2 ,where the first term initializes Lemma 4 as a t = σ 2 t + σ 2 t-1 + Σ 2 t (i.e., a max = O(σ 2 max + Σ 2 max )) and b = 1/(σ 2 max + Σ 2 max ), the second term initializes Lemma 4 as a t = D Ft (x ⋆ , x t ) + D Ft-1 (x ⋆ , x t-1 ) (i.e., a max = 4GD due to Assumption 1) and b = λ i ⋆ , the third term initializes Lemma 4 asa t = λ 2 i ⋆ ∥x t,i ⋆ -x t ∥ 2 + λ 2 i ⋆ ∥x t-1,i ⋆ -x t-1 ∥ 2 (i.e., a max = 2D 2 due to λ i ≤ 1 and Assumption 1) and b = λ i ⋆ . The O(1) term contains ignorable terms like O(1/λ). The second step requires C 13 , C 14 ≥ 1 by Lemma 5.Regret Analysis. For convex functions, by combining the meta and base regret, it holds thatREG T ≤ O σ 2 1:T + Σ 2 1:T + O(C 10 + C 11 ) + C 0 2C 10 + 5D 2C 11 -1 T t=1 D Ft (x ⋆ , x t ) ≤ O σ 2 1:T + Σ 2 1:T, by choosing C 10 = C 0 and C 11 = 5D. For exp-concave functions, by combining the meta and base regret, it holds thatREG T ≤ O d α ln σ 2 1:T + Σ 2 1:T + O(C 3 + ln C 12 ) + 120L C 12 - 1 2 T t=1 D Ft (x ⋆ , x t ) + C 0 2C 3 + 4G 2 C 12 - α i ⋆ 4 T t=1 ⟨g t , x t -x t,i ⋆ ⟩ 2 ≤ O d α ln σ 2 1:T + Σ 2 1:T , by choosing C 12 = max{1, 240L, 32G 2 α i ⋆ } and C 3 = 4C0 α i ⋆ .Note that such a parameter configuration will only add an O(1/α) factor to the final regret bound, which can be absorbed. For strongly convex functions, by combining the meta and base regret, it holds thatREG T ≤ O 1 λ σ 2 max + Σ 2 max ln σ 2 1:T + Σ 2 1:T σ 2 max + Σ 2 max + O(C 4 + ln C 13 + ln C 14 ) + C 0 D 2 2C 4 + 16D 2 C 14 - λ i ⋆ 4 T t=1 ∥x t -x t,i ⋆ ∥ 2 + 960LGD C 13 - 1 2 T t=1 D Ft (x ⋆ , x t ) ≤ O 1 λ σ 2 max + Σ 2 max ln σ 2 1:T + Σ 2 1:T σ 2 max + Σ 2 max , by choosing C 13 = max{1, 1920LGD}, C 14 = max{1, 128D 2 λ i ⋆ } and C 4 = 4C0D 2 λ i ⋆ .Note that such a parameter configuration will only add an O(1/λ) factor to the final bound, which can be absorbed.Note that the constants C 3 , C 4 , C 10 , C 11 , C 12 , C 13 , C 14 only exist in analysis and thus can be chosen arbitrarily, finishing the proof.Lemma 5. For any a > 1, b > 0, it holds that ln(a + b) ≤ ln(Ca) + b C for some C ≥ 1.Proof. The one-line proof is presented below:ln(a + b) ≤ ln(Ca + b) ≤ ln(Ca) + ln 1 + b Ca ≤ ln(Ca) + b C ,where the first step is due to C ≥ 1, and the last step adopts ln(1 + x) ≤ x for any x ≥ 0.Lemma 6 (Corollary 5 of Orabona et al. [2012] ). Justification: One limitation we could discover is that our approach is not applicable in multi-player games since it does not control the algorithmic stability, which is essential and necessary in achieving fast rates in games.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.Although xt is unknown when using mt,i, we only need the scalar value of ⟨∇ft-1(xt-1), xt⟩, which is bounded and can be efficiently solved via a one-dimensional fixed-point problem of ⟨∇ft-1(xt-1), xt(z)⟩ = z. xt is a function of z because xt relies on pt,i, pt,i relies on mt,i and mt,i relies on z. Interested readers can refer to Section3.3 ofWei et al. [2016] for more details.For strongly convex functions, it is possible to choose mt = ∇ft-1(xt-1) to avoid additional surrogateinduced terms, that will be discussed below. We choose the gradient of the last round as the optimism since this is the the only choice at present to achieve an optimistic regret for exp-concave functions[Chiang et al., 2012]. 


Decision: Overall all reviewers were positive about this work and I support their decision.

Reviews: review: paper_summary: paper_summary: The authors study the regret minimization problem in online convex optimization without access to curvature information. They tackle the task of achieving problem-dependent optimal regret while requiring no prior knowledge of the function class (convex, exp-concave, or strongly convex). They propose an efficient-to-implement two-layer online ensemble structure that requires only one gradient query within each round. Their main technical novelty lies in providing a novel approach for gradient-variation bounds.
strength_weakness: strength_weakness: The proposed approach seems reasonable to me. While I have not gone through the technical details very carefully, I seek one clarification on the proof of Theorem 1. In my opinion, the bottleneck of the proof is in showing the existence of an appropriate choice of $C_3$ and $C_4$ (page 17, line 594, 596). Can the authors comment if such a setting always exists? I would at least expect certain conditions like $\alpha_i^* > G^2/9L $ or $\lambda_i^* > 1/9L$ for results to hold.

Another small thing: I understand the authors ignore very small terms like $\log \log T$ from the order notation. It might be good to put a note in the introduction about it while presenting the result. I understand that it is there in Section 3.1 -- it might be good to move it earlier.
questions: questions: See above.
limitations: limitations: See above.
paper_summary: paper_summary: This paper investigates the problem of universal online convex optimization to achieve problem dependent regret guarantees for different classes of convex functions (strongly convex, exp-concave, and convex) simultaneously. Problem/function/data dependent regret guarantees have become popular in literature to bridge stochastic and adversarial guarantees.
strength_weakness: strength_weakness: W1) The contribution seems limited in that the improvement is only logarithmic for both efficiency and regret results.

W2) While the regret analysis is novel, algorithmic contribution is very limited, which leads me to believe this paper is more suitable to be a technical note.
questions: questions: Q1) Why is $\log^2 T$ computational complexity claimed to be inefficient throughtout the paper? In Table 1, the number of gradient queries and base learners are given as part of efficiency, however, a decrease on the number of queries seems much more significant to me.

Q2) Improvement over the results of Yan et al. [2023] seems incremental. Are there scenarios where this improvement becomes significant?

Q3) Is your approach the same as Zhang et al. [2022]  but using Optimistic ADAPT-ML-PROD [Wei et al., 2016] instead of  ADAPT-ML-PROD [Gaillard et al., 2014]?
limitations: limitations: No significant limitations. Necessary assumptions about the problem setting are properly addressed.
paper_summary: paper_summary: The paper studied the problem of regret minimization of a set of functions $\{f_t\}_{t=1}^{T}$ over a compact and convex constraint set $\mathcal{X}$, i.e.,
$\sum{t=1}^{T}f_{t}(x_t) - \text{min}{x\in\mathcal{X}}\sum{t=1}^{T}f_{t}(x),$
where $x_t$ is the output of the proposed algorithm at round $1\leq t\leq T$.
The set of functions ${f_t}_{t=1}^{T}$ potentially satisfy certain curvature assumptions, e.g., strong convexity, convexity, or exp-concavity. In the paper, it is unknown which curvature assumption the function satisfies. The main goals of the paper are the following:

1. To construct a universal algorithm that adaptively acts on the curvature property of the function and achieves a proper regret bound.
2. For the case where the function is $\lambda$-strongly convex or $\alpha$-exp-concave, the algorithm should be adapted with respect to the curvature parameter, $\lambda$ to $\alpha$.
3. The algorithm should achieve a good problem-dependent regret bound: The goal of the paper is to attain a regret bound that depends on the following quantities:
$V_T = \sum_{t=1}^{T}\text{sup}_{x\in \mathcal{X}} \| \nabla f_{t}(x) - \nabla_f{t-1} (x) \|^2, \quad \text{and}\quad F_T = \text{min}{x\in\mathcal{X}}\sum{t=1}^{T}f_t(x).$

The proposed algorithm of the paper is a modification of the algorithm proposed by [1]. Similar to the approach introduced by [1], in Algorithm 1 (page 5) of the paper, the authors proposed $\emph{base learners}$ that are aggregated by a meta-algorithm, which outputs the final output of the algorithm at round $t$, $x_t$. The contribution of the paper mainly concerns the technical aspects that outperform the performance of [1] from the following points of view:

1.The paper improves the number of required base learners from $\log(T)^2$ (in [1]) to $\log(T)$.

2.This improvement of the algorithm outperforms the algorithm proposed by [1] up to a logarithmic factor for the situation where the loss functions $f_t$ are convex.

[1] Y.-H. Yan, P. Zhao, and Z.-H. Zhou. Universal online learning with gradual variations: A multi-layer online ensemble approach. In Advances in Neural Information Processing Systems 36 (NeurIPS), 2023.
strength_weakness: strength_weakness: The main weakness of the paper lies in its presentation. The content is too dense, and the last section on dynamic regret could be moved to the appendix. Some key parts of the paper are not well explained. For instance, it is unclear how the authors managed to outperform the number of required base learners in [1] by a logarithmic factor. Was this achieved through the application of a Bregman divergence negative term?

The contribution of the paper is limited to a simple technical improvement that enhances the achieved regret up to a logarithmic factor for convex functions.

The optimality of the result with respect to $V_T$ and $F_T$ has not been discussed by the authors.


[1] Y.-H. Yan, P. Zhao, and Z.-H. Zhou. Universal online learning with gradual variations: A multi-layer online ensemble approach. In Advances in Neural Information Processing Systems 36 (NeurIPS), 2023.
questions: questions: 1. I do not understand the comment on the small $\alpha$ and $\lambda$ in lines 146-147. Can these cases be considered convex? For the convex case, the rate is of the order of $\sqrt{T}$. How do the optimal minimax results hold for this regime, which indicates that the regret is linear?

2. I would appreciate it if the authors could explain the question I raised in the weakness section and outline the main difference that helps them improve the number of base learners.

3. I do not understand the comment in line 305: "which can be easily canceled by the negative term from curvatures in the meta regret." For this cancellation to occur, the coefficient in the equation after line 304 really matters. Could the authors explain this further?

4. Could the authors explain if the final result is optimal with respect to $V_T$ and $F_T$?

Minor Points:

The terms $\sigma_{\text{\max}}$ and $\Sigma_{\text{\max}}$ are not defined in Theorem 3.
limitations: limitations: The authors adequately addressed the limitations.
paper_summary: paper_summary: This paper studies universal Online Convex Optimization (OCO) with gradient-variation-dependent regret bounds. That is, to design one single algorithm that is unaware of but is able to adapt to both two following groundtruth: 1) the type of curvatures: the loss functions could be convex, strongly convex, or exp-concave; 2) the curvature coefficient: exp-concavity $\alpha$ or strong convexity $\lambda$. As a result, the regret guarantee achieved by the algorithm scales with the cumulative gradient variation $V_T$ (which depends on the loss function sequence), rather than the time horizon $T$, as well as the corresponding curvature type of the underlying loss functions.

This paper proposes a new simple algorithm, that for the first time achieves optimal gradient-variation bounds for all three curvature types. Note that the gradient-variation bounds immediately imply small-loss (aka first-order) regret bounds as well as worst-case bounds. The #base learners is also improved from $(\log T)^2$ to $\log T$ due to the two-layer structure. The main result also finds broad applications including the SEA model and dynamic regret bounds.

Technique-side, the improvement comes from an alternative way to analyze the the empirical gradient variation w.r.t. surrogate losses and utilizing a negative Bregmen divergence term (due to linearization) to cancel other positive terms, which is often omitted in the analysis.
strength_weakness: strength_weakness: I didn’t spot any significant technical issues, and I'm just suggesting some minor “weakness”.

1. When the authors introduce the notion of $F_T$ and small-loss bound for the first time (around Eq. (1.2)), they may want to add that now the loss functions are non-negative (which I think should be necessary for all small-loss/first-order bounds?). Obviously, one can’t take squared root or logarithmic to a negative number.

2. In the application to dynamic regret, the problem setup is not clearly defined. What is the type of loss function? Is the strong-convexity/log-concavity known? It is particularly confusing since it’s right after the universal OCO setup.
questions: questions: 1. The idea of utilizing negative Bregmen divergence terms also appeared in other problems, such as high-probability regrets in adversarial bandits [1]. Could the authors comment on the connection (if any) between the use therein and this work?

2. Under the universal OCO setup, is it possible to handle time-varying curvatures, just like in [2]?

3. Seems that a universal OCO algorithm cannot be anytime? The reason is that the number of base learner (for discretization) depends on $T$.

References

[1] Lee, Chung-Wei, Haipeng Luo, Chen-Yu Wei, and Mengxiao Zhang. "Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps." Advances in neural information processing systems 33 (2020): 15522-15533. https://arxiv.org/abs/2006.08040

[2] Luo, Haipeng, Mengxiao Zhang, and Peng Zhao. "Adaptive bandit convex optimization with heterogeneous curvature." In Conference on Learning Theory, pp. 1576-1612. PMLR, 2022. https://proceedings.mlr.press/v178/luo22a/luo22a.pdf
limitations: limitations: yes

Comments: title: Response to the follow-up questions
Thanks for the feedback
Thanks for the feedback
Rebuttal acknowledgment
Response to other comments
comment: Thanks for your feedback and the follow-up questions. Below, we answer your questions about the unknown time horizon and the dynamic regret bound, hoping to help you gain a better understanding of our work.

---

**Q3.** The construction of the algorithm is dependent on knowing the time horizon $T$. Is it possible to extend this to scenarios when the time horizon is not known?

**A3.** Thanks for this insightful question. As shown in Eq. (2.1) on Page 4, setting the number of base learners requires knowing $T$ in advance. To remove this dependence, a possible solution that we could imagine is the ***doubling trick***. However, this would possibly import an additional $\log T$ factor to the final regret bound, which would ruin the desired $\log V_T$ rate for exp-concave and strongly convex functions. Indeed, as explained in the response **A5** for Reviewer #y66n, making our algorithm anytime is a challenging open problem worth exploring in future work. This challenge is also noted in previous studies of universal online learning like Zhang et al. [2022].

---

**Q4.** The extension to dynamic regret bound seems interesting to me. If I am correct, this part does not utilize any curvature information, likely due to $P_T$ and $V_T$ being the dominant terms in the final expression. Is that correct? Also, in Theorem 5, is there an $O(V_T)$ term missing from the final expression?

**A4.** Thank you for the great question. Below, we answer your two questions separately.

* **Curvature Information:** In this part, we aim to validate the effectiveness and generality of our technique in dynamic regret minimization for ***convex*** functions. It means that we do ***not*** consider curvature information such as exp-concavity or strong convexity in this part. We will make more clarifications about the problem setup of this part in the revised version.
* **Missing $O(V_T)$:** In Theorem 5, there is no missing $O(V_T)$ term, and our obtained $O(\sqrt{(1+V_T+P_T)(1+P_T)})$ dynamic regret has matched the state-of-the-art rate, see Theorem 4 in [1].

[1] Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization, JMLR 2024

---

We greatly appreciate your thorough review and helpful feedback. We will incorporate the above clarifications in the revised version. Please let us know if you have any more questions, and we are happy for further discussions.
We appreciate your feedback and acknowledgment of our work. We will emphasize more about the computational efficiency, the significance of our improvements over Yan et al. [2023], and the algorithm contributions in the revised version. Thanks again for your valuable and helpful review.
Thanks for the feedback. We will work on improving the presentation and incorporating the above clarifications in the revised version to ensure that readers gain a better understanding of our contributions. Please let us know if you have any more questions, and we are happy to provide further clarification.
Thank you for your response. The new settings of parameters seem to work well. Could you comment on a couple of more things :
1. The construction of the algorithm is dependent on knowing the time horizon $T$. Is it possible to extend this to scenarios when the time horizon is not known?
2. The extension to dynamic regret bound seems interesting to me. If I am correct this part does not utilize any curvature information, likely due to $P_T$ and $V_T$ being the dominant terms in the final expression. Is that correct?  Also, in Theorem 5, is there an $\mathcal{O}(V_T)$ term missing from the final expression?
I acknowledge the author's rebuttal. Thank you for a detailed response. I suggest you revise the manuscript with these explanations. I have no further questions.
I would like to acknowledge the author's rebuttal. For now, I will maintain my current score. I plan to discuss the paper with the other reviewers and look forward to the author's discussions with them as well. I will update my score accordingly.
In this reply, we respond to presentation/definition issues, hoping to help you better understand our work.

**Q6.** The content is too dense, and the last section on dynamic regret could be moved to the appendix. 

**A6.** Thank you for the advice. We use dynamic regret minimization as an example to validate the generality and significance of our technique and believe it is worth listing in the main part. Given that an extra page is allowed in the camera-ready version, we will provide more detailed explanations of our method and applications to help readers understand them better.

**Q7.** The terms $\sigma_{\max}$ and $\Sigma_{\max}$ are not defined in Theorem 3.

**A7.** Thank you for pointing it out. $\sigma_{\max}^2 \triangleq \max_{t \in [T]} \max_{\mathbf{x} \in \mathcal{X}} \mathbb{E}\_{f_t \sim \mathcal{D}\_t} [\\|\nabla f_t(\mathbf{x}) - \nabla F_t(\mathbf{x})\\|^2]$ and $\Sigma_{\max}^2 \triangleq \max_{t \in [T]} \sup_{\mathbf{x} \in \mathcal{X}} \\|\nabla F_t(\mathbf{x}) - \nabla F_{t-1}(\mathbf{x})\\|^2$. We will add their definitions in the revised version.
I thank the authors for the reply. Currently, I do not have any other concerns and I maintain my scores.