A Simple and Optimal Approach for Universal Online Learning with Gradient Variations
Authors: Yu-Hu Yan
Peng Zhao
Zhi-Hua Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: universal online learning
gradient-variation regret
Primary area: online_learning
TL;DR: This work proposes a simple universal approach with the optimal gradient-variation regret guarantees.

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.

A Simple and Optimal Approach for Universal Online Learning with Gradient Variations
Yu-Hu Yan, Peng Zhao, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology. Nanjing University, China School Artificial Intelligence, Nanjing University, China (yanyh, zhaop, zhouzh)@lae @lamda.
Abstract
We investigate the problem universal online learning with gradient-variation regret. Universal online learning aims to achieve regret guarantees without the prior knowledge of the curvature of the online functions. Morcover, we study the problem-dependent pradient-variation regret as it plays crucial role in bridging stochastic and adversarial optimization as well as game theory. In this work, we design a universal approach with the optimal pradient-variation regret simultane- ously for strongly convex, exp-concave, and convex functions, thus addressing an open problem highlighted by Yan al. [2023]. Our approach is simple since it is algorithnically efficient-to-implleent with a two-layer online ensemble structure and only gradient query per round, and theoretically easy-to-analyze with 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 Bregman divergence negative term from linearization and a useful smoothness property.
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 decision X₁ from a convex compact set X' C Rd Simultancously, the environments adversarially choose convex loss function fi X' + R. Subsequently, the learner suffers loss of fe (x:), receives feedback on the function fe(.), and updates her decision to X 1. In OCO, the learner aims optimize the game-theoretin performance measure known as regret [Cesa- Bianchi and Lugosi, 2006], which is formally defined as
REGT Σ f((x)) min Σ f((x). XEX
(1.1)
represents the learner's excess cumulative loss compared with the best fixed comparator in hindsight.
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(VT) regret [Zinkevich, 2003]; for a-exp-concave functions, online Newton step assuming is known obtains O log T') regret [Hazan al., 2007]; and for X-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 al., 2008]. Recent studies further strengthen them by introducing two levels of adaptivity.
In
"Correspondence: Peng Zhao <zhaop @ lamda.nj..cdu.cn>>
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison with existing results. The second column shows the regret bounds for strongly convex. exp-concave, and convex functions, following the ( -noottotooon. Note that we only list universal guarantees related to the gradient variation Vr 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 constant and omit "# Gradient" is the number gradient queries in each round, where "I" represents exactly one gradient query. And "# Base" stands for the number of base learners.
Regret Bounds
Efficiency
Works
Strongly Convex
Exp-concave d dlog T
Convex VT
# Gradient
Basc
van Erven and Koolen [2016]
d d'log T
1
log T
Wang et al. [2019]
log T
d dlog T
VT
1
log T
Zhang et al. [2022a]
log Vr
dlog Vr
VT
log T
log T
Yan et al. [2023]
log V4
dloog V1r
Vv, log Vi.
1
(log T)²
Ours
log Vy d'log Vi
V/r
1
log T
High-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 access in real-world applications. To this end, line of research aims design single universal algorithm that does not require the curvature information while achieving the same regret guarantees as if knowing it, achieving the adaptivity work of MetaGrad [van Erven and Koolen, 2016] proposed carefully designed surrogate functions and achieved ( d log T") for a-exp-concave functions and ((VT) for convex functions. Subsequently, Wang et al. [2019] obtained the optimal O log 7') regret for X-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.
unknown curvatures. The pioneering
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 gradient- variation 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:
T
V1 A
Σ sup [IV x=X XEX
(x)1
(1.2)
Under smoothness assumptions, the minimax regret can be improved to O log VT), O log VT), and ((VVT) for X-strongly convex, n-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 problem- dependent quantity known as the small loss F7 A minxex Eisr f((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 gradient variation plays crucial role in bridging adversarial and stochastic optimization [Sachs et al., 2022]; and (iā) the variaatn 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.c., designing single universal approach with gradient-variation regret across different curvature types without the prior knowledge of them. For this problem, Zhang al. [2022a] achieved partial results of O( log Vrr), O o-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 ( Vr log Vr), achieving the first universal mandient-variation guarantee. Although optimal for strongly convex and exp-concave functions, their results still exhibit a gap with the optimal O(vVT) 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 aware of is 2( VT) for convex functions [Yang et al., 2014, Remark 5].
or log Vr), ((TT) for A-strongly convex,

---

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., 2015 88, 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 optimiza- tion [Li et al., 2014]. universal online learning, an "efficient" algorithm expected to adopt only (log 7') 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 Ollog 7') base learners, but required Olog T') gradient queries per round. Yan et al. [2023] used only gradient query per round but required O(log ?)? 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 simple universal approach that achieves the optimal O log Vr), O _ log Vr), and (VVTT) regret simultaneously for X-strongly convex, d-exp-coneave, and convex functions, and is efficient with one gradient query per round and Ollog 7') 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-varinn 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-ar guarantees as Chen et al. [2024], but without curvature information. The details are provided in Section 4.
a
Our technical contributions include two simple and novel analyses. First, the key to gradient-variation regret is to analyze its empirical version, formally, [x,) I Il. The previous approach to addressing this term involves controlling the algorithmic stability ||x, x,-111ž. 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 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 al., 2020]. Second, we adopt the surrogate functions proposed by Yan et al. [2023] to reduce the gradient query complexity, and provide novel analysis for the empirical gradient variation based on the surrogates. A technical comparison with previous works is provided in Section 4.
Techniques.
(x,-))
Organization. The rest of the paper is structured as follows. Section 2 introduces preliminaries and a general framework for universal online learning. Section presents our efficient approach with the optimal universal pradient-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, defini- tions, and general framework of universal online learning.
2.1 Notations, Assumptions, and Definitions
For simplicity, we use || for || ||2 by default and use a S b a (b)) if there exists a constant C' < xo such that a/b S C. In the following, we introduce the assumptions used in this work.
=
Assumption 1 (Boundedness). For any x,y E X' C Rdd the domain diameter satisfies ||x 1xxxx yll S D,
and for é [T), the gradient norm of the online functions is bounded as [x())) < G.
3

---

Assumption 2 (Smoothness), For each & (7), the online function f((-) is L-smooth, i.e., (( Vs((y)l & T||x- - -yll holds for any y E Rd
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 Fd space and can be relaxed
slightly larger domain than X,, formally, X4 - (x + b| X, b C/L-BJ, where IB _ {x || S 1} is 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- exp-concavity.
For any x, y. E X. a function f()) is X-strongly convex if (xx) - f(y) S (VI(x), x- y) |x x yl?; f() is a-exp-concave if f(x) - f(y) S (VS(x), x y) - - (VI(x),x-y) y)
Definition 1.
Note that the formal definition of 3-exp-concavity is that exp(-3/() is concave. Under As- sumption 1, 3-exp-concavity implies Definition I with = 3 min(1/(4GD), 33 [Hazan, 2016,
Lemma 4.3). Therefore, we adopt Definition as an alternative definition of exp-concavity for clarity.
2.2 A General Framework for Universal Online Learning
In this part, we present 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 a or strong convexity A. Without loss of generality, we focus on the case of a, À E 1I. If a, À < 1/T, even the optimal minimax results - O log T) for exp-concave functions and ( log T') for strongly convex functions [Hazan et al., 2007] become linear in T, rendering the regret bounds vacuous. On the other hand, if a, À > we can simply treat them as À = 1, only making the regret worsen by an ignorable constant factor. This simplification 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 meta learner tracking the best base learner. More specifically, to deal with the unknown curvature coefficients a and X, we discretize them into the following candidate pool [Zhang al., 2022a]:
H A 2//T,2/T,4/T,. .,, 2"..,,,,//TT,,
(2.1)
whose size is n [log, 7 (log 7'). It can be proved that the discretized candidate pool H can approximate the continuous value of a or with negligible constant errors. By doing this, 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 X; E H of the strong convexity coefficient A; (ii) exp-concave hase learners: n in total, each of which implements the algorithm for exp- concave functions with a guess ag E H of the exp-concavity coefficient o:; (iii) convex base learner: only one, it runs the algorithm for convex functions.
In total, there are N (2n + 1) Olog 7) 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 A-strongly convex functions as an example, the guessed coefficient of the best base learner (indexed by i*)) satisfics Xç- S A < 2
Denoting by xt, the decision generated by the i-th base learner at the f-th round, pt.; the weight of the meta learner on the i-th base learner, an online ensemble method outputs the final decision as x; = ΣieiN] Xt.:Xt.i. This forms general framework for universal online learning and it remains to select suitable algorithms and loss functions for the meta and base learners. We will illuminate our concrete algorithm design Section 3.1 and present a more detailed description of our meta/base learners configurations in Appendix B.

---

Algorithm A Simple Approach for Universal Online Learning with Gradient Variations
Input: Meta learner A, base learners {Bi HE[N]
1: Initialize: P1,: 1/N and X1,5 to be an arbitrary decision inside X' for all i e [N]
2: for tort= 1 to 7" do
3: Submit X4 = LEENN] Pt, suffer fx(x)), and observe the gradient (x,,))
# Meta Update:
4: updates to p++1 E An using the rule (B.5) with learning rate (B.6)
# Base Update:
5: Construct surrogates hg,(() (.) (, defined in (3.1) using only fx((x))
6: B₁ updates to X4+1,; using surrogates functions (3.1) and update rules (B.1)-(B.3) for E [M]
7: end for
3 Our Approach
In this section, we present our approach for universal online learning with gradient-variatinn regret. Section 3.1 presents the overall procedure of our proposed algorithm. Subsequently, we outline two key technical components: Section 3.2 presents novel analysis to handle the empirical gradient variation, and Section 3.3 introduces surrogate functions to improve efficiency and provides corresponding analysis for the empirical gradient variation defined on surrogates. We finally provide the optimal universal gradient-varian variation regret guarantees in Section 3.4.
3.1 Overall Algorithm
In this part, present simple approach for universal online learning with gradient variations, summarized in Algorithm Basically, it is a two-layer online ensemble. Base learners are imple- mented using the preliminary configurations given in Section 2.2 and on carefully designed surrogate functions. The meta learner runs OPTIMISTIC- MAMMIISIC-AAAT-MMOE ADAPT-ML-PROOT [Wei et al., 2016] on linearized losses. We specify the algorithmic details below, and a more detailed procedure in Appendix B.
In Line 3, the learner makes a weighted combination of the base learners' decisions { beeN) using the meta learner's weights pt = (Pr.,,....,Po Pt.v). submits the final decision x,, suffers loss fxx),, and receives single V fxx)) as the gradient feedback, using only gradient query per round.
Meta Algorithm. In Line 4, the meta learner uses 2016] to update the weights by the following rule:
[Wei al.,
Pe+1a X Ex explee, We We, (We-1. exp (E1-,,,,7 - m,,, m,
Specifically, denoting by 4,, A (x.), xt,i) the loss of the i-th dimension, the meta algorithm inputs: Ft, (L,, Pt) l.s. the instantaneous regret; Ct,i, time-varying learning rate; and m4,i. an estimation of the true loss of the 1-th round (the choice of optimisms will be shown later). The meta algorithm then outputs the weights P++1 (p(+1,). ....,. .P+ IN) of the next round.
With appropriate learning rates (B.6), OPTMIITII-ADDAT-ML-PPP order bound of rt, S VioTo N (ri, m² + log N), where the log N factor is negligible since the base learner number N equals (log and we can treat O (log log T) as constant [Luo and Schapire, 2015]. The formal guarantee of
achieves an optimistic second-
is deferred to Lemma 2 in the appendix. In our problem, the instantaneous regret Ft.; = (Le, P:) L,, = (x))();)
xt.:). Thus we choose m = (V /V (x x; xx,i) for the convex base learner and m = 0 otherwise (i.e., for exp-concave and strongly convex base learners). 2 By doing this, we can upper-bount Σ, (V (x,,, the convex base learner and by O( O(VE, (v)( X, x otherwise. Later in Section 3.3, we illuminate how such results could benefit the final regret guarantees.
x.,) by O OOVI, (x), V V
xx,)) for
2 AAthooghh x; is unknown when using m.,,, we only need the scalar value (x xi), which bounded and can be efficiently solved via a one-dimensional tixed-poin problem of (V ( xx)) = 2. x, is function of because relies on Pt. Pt. relies on my, and my. relies on Interested readers can refer to Section 3.3 of Wei et al. [2016] for more details.
5

---

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:
A ||x | x
(x)
fe((x)),
(x)
(V x)
f[(())), x-ls,,,xxxx..) xx)) (3.1)
and (x) (x,). x), where A₁ a are selected from the candidate coefficient pool H. in (2.1). We emphasize that the surrogate functions require only gradient query V fx(x) per round. Finally, in Line 6, the i-th base learner B; updates the decision to Xt+1,; 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. For detailed update rules of differently configured OOMD, we refer readers to (B. (B.3) in Appendix B.
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 gradient- variation regret for convex functions, and operates on the original loss function f+(-) for base learners, which leads to a less efficient gradient query complexity of ( 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 three-layer ensemble structure, which is also not efficient enough. Compared with approaches above, our Algorithm is simpler and more efficient as it requires Olog 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.
3.2 Novel Analysis on Empirical Gradient Variations
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 V (x,) in the t-th round, to obtain the gradient variation Vr defined in (1.2), it is necessary to first attain its empirical version V7 A Previous studies decompose this term into two parts:
Eisr (x,) - (
[V,)),,) - (x || < [V/x(x)) - I + VV (x.) - V 1x- I suPxex | fi() - v - x11111
using smoothness (i.e., Assumption 2). Aggregating the first term over T rounds leads the de- sired V/ quantity and the remaining challenge is to control the algorithmic stability ||x; -x,-xx,17 Consequently, since each decision is weighted combination of base learners decisions (i.e.,
x 1|2
Xx = EisN Xt,) the algorithmic stability is difficult to control. To this end, Yan et al. [2023] decomposed the stability term in the following way:
N
{ X x 2 Σ Pr. X1-1,a11 +|pp: 11-
(3.2)
Consequently, for the first term, the authors injected correction terms to the meta learner follow- ing Zhao et al. [2024]. To cancel the second term, the meta algorithm must include corresponding negative stability term in its analysis, while achieving an optimistic second-order bound simultane- ously. To the best of our knowledge, the only feasible algorithm satisfying both requirements the two-layer meta algorithm ensemble structure and therefore affects the efficiency. Besides, attains a second-order bound of the form O / /Qr, log Qr.)). where Qr, & E, m,,1) which causes the optimaaly of the regret guarantees with an additional logarithmic factor in the results of Yan et al. [2023].
[Chen et al., 2021]. which leads to three-layer online
In this work, handle the empirical gradient variation alternatively via novel and simple analysis with two key parts: (i) negative term arising from linearization; and (ii) useful smoothness property. First, we observe that the instantaneous regret can be transformed
fe(x;) - fx(x*) =
((fo=))=(VV((()) (Vfi(x)), - xx) - Dj, (x*, xt):
(3.3)
where x E arg min ((xx and (x y) e f(x) ((xx)-(yy-- (V](y), - 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 linear one. Previous studies on 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.
the gradient-variation
Proposition 1 (Theorem 2.1.5 of Nesterov [2018]. f()) is L-smooth over R if and only if ffy) - 2L Dy(y, x), for any x,y E Rd.
||
(3.4)
Compared with the commonly used | [V() [f(y))l - x yll Proposition gives tighter bound for the squared gradient changes since [V - Vf(()) - 22DD, S - y yl?
where the second step is due to Dy(y. x) & 1 yl?. for any x.y E Rd [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 as
VT S (I)))(x))) Vx((')II + [V]((x)
Vi--i 1)133
Am 2
(3.4) L Σ Dj. (x*,x,) VT + L Σ D fb- (x" x, s 2L Σ Dj. ,xxxxxx, xx) V/,
(3.5)
where the first step introduces intermediate terms (xx)) and V (x'), the second step uses Proposition I, 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 as desired.
Here we only require [V [sy)]l < (y, x) on X' rather than Rd, which be satisfied by requiring L-smoothness only on 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-independee independent. Therefore, we can eliminate the need to control the algorithmic stability, in contrast to previous works for crudient-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²) 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.
3.3 Novel Analysis on Empirical Gradient Variations of Surrogates
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 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 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 X-strong convexity as an example, the regret can be decomposed as follows:
T
REGT S
V f((x)) X1 xx)
X x" 112
1
Σ
(xx,x)
2
T
Tt.s
Ap.
T
-x,-- 11?
+
Σ
T
(1 (Xx, - (x*))
-
2
1 T
Σ
Dj (xxxxxx) x(),
1=1
[=1
7

---

where the first step uses (3.3) and the fact that (x", ,x) 2 2 Ixx x21 since f((-) is A-strongly convex. The second step uses the definition of the best base learner (indexed by i*): X, S X - 2 and the definition of surrogate functions defined in 13.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 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 Σ 1=1
I Σ (VI((x)),x x1,,)²² X
T Σ
X 4
1
x
X
Xt. 11
where the 1/A factor can be absorbed by the final regret 0 the surrogates, which preserves the curvature properties, but using only 1 gradient (x(x).).
{ log Vr.) The base regret is defined on
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 as X = xIx [R mm) and X4+1,1 Ixx [x.; Ti Vhr, (x,,), an initialization of the OOMD algorithm, where ?7 represents the step size, |xx[x] arg min ||x ex-yl yll denotes the Euclidean projection onto X, and & an intermediate variable. With appropriately chosen step sizes, the base learner achieves an optimistic bound of (log Dr), where Dy Eisr |/V (Xt,s) m (e.g.. please refer to Theorem 15 of Chiang et al. [2012]). Therefore, choosing the optimism as m, 1x;=-1,(x;11., leads to an empirical cuddient-variation bound Oloog Dz) defined on surrogates, where
Dr (x,.)) V/ (x
(x111
d > (x,, - x1) Vx(((x)) V + Σ
T
2 (x (x--1,x-x,-)) xx--1
2
The empirical gradient variation defined on the original functions, i.e. fx,,) - V f (x1=
can be handled via the analysis in Section 3.2. The main challenge to deal with the rest terms caused by the surrogate functions. Yan et al. [2023] overcame this issue by controlling (x: x,-1) and (Xe.; - xx,1,;) separately. Again, as we have explained in Section 3.2, since the decision x; is weighted combination of base learners' decisions (i.e., X, EiSn N (t,)), handling the algorithmic stability term |x,- x,-1 2l directly using (3.2) would results in 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 novel analysis - while controlling (Xe,i -xx) (x Xt-1) in each individual round hard, can be bounded when aggregated over the time horizon. Specifically, we bound it by combining two summations into one:
T
Σ -x)x -x-- 111 S Σ
X
X 1I
Σ
| X
S
X xel12.
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, - x required by previous works, and is essential for achieving the improved computational efficiency and the optimal regret guarantees, shown in the next part.
3.4 Optimal Universal Gradient- Gradient-Variation Regret Guarantees
In this part, we present our main theoretical result our simple and efficient Algorithm 1 (in Section 3) which adopts two novel analyses (in Section 3.2 and Section 3.3) achieves the optimal
*For strongly convex functions, it is possible to choose m, V (x;-1) to avoid additional surrogate- induced terms, that will be discussed below. We choose the gradient of the last round as the optimism since this the the only choice at present achieve optimistic regret for concccecvve functions [Chiang et al., 2012).
8

---

vrrdiint-variatin regret without requiring the curvature information in advance for universal online learning. The corresponding proof is provided in Appendix C.
Theorem 1. Under Assumptions 1 and (or the relaxed Assumption 3), Algorithm I achieves (log Vr). Oo Vr), and O /Vr) for strongly convex, exp-concave, and convex functions.
Theorem improves the (VVVr
r log Vr) bound of 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 varia- tion is small, such as fi = f2 =
fr (where Vr = 0). Note that for d-exp-concave or A-strongly convex functions, our guarantee is actually (minn { a log Vr, vVr or O(mnn x log Vr, vVr thus ensuring O (() even when a = ((/r) or À = O(/r). This is because exp-concave and strongly convex functions are also convex and thus our convex bound is still applicable.
4 Implication, Application, and Discussion
In this section, we validate the effectiveness of 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- baaeed approach [Yan al., 2023] the end of this section.
4.1 Implication to Universal Small-Loss Regret
In this part, we illustrate that our universal gradient-variation regret in Theorem I implies the universal small-loss regret measured by Fr minxex EisT (x) directly in analysis, i.e., without any algorithmic modification, and thus safeguards the case of Fr S VT, such as minxex fx(x) = 0 for any E [T] (where FT = 0). The corresponding proof is provided in Appendix D.I.
Theorem 2. Under Assumptions and 2 (or the relaxed Assumption 3), if the online functions are non-tega Algorithm achieves Olog Fr), O(dlog Fr), and O ((FF)) for strongly convex, exp-concave, and convex functions, respectively.
Theorem 2 achieves the same optimal small-loss bounds as Zhang al. [2022a]. Combined with Theorem 1, our approach achieves the best known problem-depedda regret guarantees in the universal online learning problem. In the end, emphasize again that our approach is efficient requires (log 7') base learners and only I gradient query in each round.
4.2 Application to Stochastically Extended Adversarial (SEA) Model
Stochastically extended adversarial (SEA) model [Sachs et al., 2022] interpolates between stochastic and adversarial online convex optimization. Formally, it assumes that the online function fr(-) is sampled stochastically from adversarially chosen distribution Dr. Denoting by Fc(-) A
Ef,,D,f(() [f(-)] the expected function, two terms capture the essential characteristics of SEA model:
o.. Σ max max E,DD. (x)) (x)) EP. XEX
E
Σ
sup (v. (x)] XEX
where o.r is the variance in sampling fe(.) from De(-) and Ei.r is the variation of (Fe(-))em
Sachs et al. [2022] initiated the study of the SEA model. For smooth expected functions {F((-))
they achieved the optimal O O(vorrr + Eirr) regret for convex expected functions, and O max
52 Xxxx) ) log T) in the strongly convex case, where o A max maxxex FED, [xx))
[x) and Ea - max supxex [[V - (x)-1xx) Subsequently. Chen et al.
[2024] improved the strongly convex regret to ((o + - ( //.r)/(/
( max D
))))))
and obtained Od E(.r)) regret for exp-concave individual functions {f(())]
The gradient variation is essential in connecting the stochastic and adversarial optimization [Chen et al., 2023, Lemma 4], which also restated in (D.2). Therefore, universal gradient- variation regret can be applied to this problem, achieving the same best known bounds as Chen et al. [2024], with single algorithm. Table compares our results with existing ones. The following theorem presents results formally, with the corresponding proof provided in Appendix D.2.

---

Table Comparisons of our results with existing ones. The second column presents regret bounds, where oं. and Eir represent the stochastic and adversarial statistics of the SEA problem. The last column indicates whether the results can be achieved by single algorithm (i.c., suitable in the universal setup). We achieve the same state-of oatte-of-th-aatt art guarantees Chen et al. [2024] using one single algorithm.
Regret Bounds
Single A Algorithm?
Works
Strongly Convex
Exp-concave
Conve
Sachs al. [2022]
(f(o + Mance log2))
NIA
Olvotr + Mir)
X
Chen et al. [2024]
0 (Iriaxx Minael log cfrrt
Oldlogiri Mir)
Oiv | xin)
X
Suchs et al. [2023]
Ol(ohaxx Maaa 12 log"
NIA
O(vTlogTT)
/
Yan et al. [2023]
Ollo + Emase) log(o + E(y))
Oddoogoo Earl) Olyioia Mi,y) loglor Kinl)
/
Ours
o ((rlun Y log Plase Pi
O(dlog(o]7 M77))
Oivel, 1 x9
/
Theorem 3. Under Assumption 1 and smoothness of F((-) for any E [T]: F((-) is convex,
Algorithm I achieves O( O(vor=+ >i if fe()) is exp-concave, it achieves O(dlog(o + Ei:r)); and if F((.) is strongly convex, it achieves O( maxx max E log((o) + // ( taax + Σ2 max ma))))
Theorem 3 requires exp-concavity of the individual function fz(-) rather than the expected function F.(.). 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].
4.3 Discussion on Comparison with Correction-based Approach
In this part, we discuss the technical comparison with the previous correction-based approach [Yann et al., 2023]. Compared with their approach, ours is simpler and achieves the optimal universal problem-dependen 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,- x 112) 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 min-max game minxex ma x Ay, where A is game matrix, since A is unknown, the Nash equilibrium is typically computed through repeated play, i.e., player-x and {yo) V sequentially to approach the Nash equilibrium. For player-x, in the t-th round, it suffers a loss x, Ay: and receives the gradient Ay Similarly, player-y suffers -x, Ay; and receives - Ax,. For player-x, if it updates via OOMD, its gradient-variation regret contains ||Ay; - A 12 we indeed need to control the algorithm stability like ||x x1 and [|y, ----r- -r-1ll 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.
player-y select {x=)²= and {y,
which includes the stability of player-y. In this case, to achieve fast rates,
5 Conclusion
In this work, we investigate universal online learning with gradient-variation regret. We propose simple two-layer online ensemble approach that not only achieves the optimal ( log Vr), Ol log Vr), and (VVVT) regret sinultaneously for X-strongly convex, a-exp-concave, and convex functions and is efficient with Ollog T) base learners and only 1 gradient query per round. This is done via the negative Bregman divergence term from lincarization and the useful smoothness property of [[V f2 < (yD 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 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 domain using recent advances in parameter-free online learning [Orabona and Pál, 2016, Cutkosky and Orabona, 2018, Jacobsen and Cutkosky, 2022], to broaden its applicability across a wider range of scenarios.
10

---

Acknowledgements
This research was supported by National Science and Technology Major Project (2022ZD01 14802), NSFC (62176117) and JiangsuSF (BK20220776). Peng Zhao was supported in part by the Xiaomi Foundation.
References
Abernethy, P. L. Bartlett, A. Rakhlin, and A. Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings the 21st Annual Conference Learning Theory (COLT), pages 414 424, 2008.
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
L. Chen, H. Luo, and C. Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Proceedings of the 34th Annual Conference on Learning Theory (COLT), pages 1216-12555 2021.
Chen, W.-W. Tu, Zhao, and L. Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 5002-5035, 2023.
S. Chen, Y.-J. Zhang, W.-W. Tu, P. Zhao, and L. Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, 25 (178):1 - 62, 2024.
C. Chiang, T. Yang. Lee, M. Mahdavi, Lu, R. Jin, and S. Zhu. Online optimization with gradual variations. In Proceedings of the 25th Anmual Conference on Learning Theory (COLT), pages 6.1-6.20, 2012.
A. Cutkosky and F. Orabona. Black-box reductions for paramcter-free online learning in Banach spaces. In Proceedings of the 31st Annual Conference on Learning Theory (COLT), pages 1493- 1529, 2018.
A. Daniely, A. Gonen, and S. Shalev-Shwartz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 1405-1411, 2015.
P. Gaillard, G. Stoltz, and T. van Erven. A second-order bound with excess losses. In Proceedings of the 27th Annual Conference on Learning Theory (COLT), pages 176-196, 2014.
E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization, 15555:55 2016.
E. Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. Electronic Colloquium Computational Complexity (ECCC), 14(088), 2007.
E. Hazan, Agarwal, and Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-19)) 2007.
A. Jacobsen and Cutkosky. Parameter-free mirror descent. Proceedings of the 35th Annual Conference on Learning Theory (COLT), pages 4 4160-4211, 2022.
S. Ji and J. Ye. An accelerated gradient method for trace minimization. In Proceedings the 26th International Conference on Machine Learning (ICML., pages 457-464, 2009.
P. Joulani, A. Raj, A. Gyorgy, and C. Szepesvári. A simpler approach to accelerated optimization: Iterative averaging meets optimism. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 4984-4999 2020.
Koren and K. Y. Levy. Fast rates for exp-concave empirical risk minimization. In Advances in Neural Information Processing Systems 28 (NIPS), pages 1477-1485, 2015.

---

M. Li, T. Zhang, Y. Chen, and A. J. Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th ACM SICKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 661-670, 2014.
H. Luo and R. E. Schapire. Achieving all with parameters: AdaNormalHedge. In Proceedings of the 28th Annual Conference on Learning Theory (COLT), pages 2286-1304, 2015.
M. Mahdavi, L. Zhang, and R. Jin. Lower and upper bounds on the generalization of stochastic exponentially concave optimization. In Proceedings of the 28th Annual Conference on Learning Theory (COLT), pages 1305-1320, 2015.
Z. Mhammedi, W. M. Koolen, and T. Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT), pages 2490-2511, 2019.
Y. Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018.
Orabona. A modern introduction to online learning. ArXiv preprint, arXiv: 2019.
F. Orabona and D. Pál. Coin betting and parameter-free online learning. In Advances in Neural Information Processing Systems 29 (NIPS), pages 577-585, 2016.
Orabona, Cesa-Bianchi and C. Gentile. Beyond logarithmic bounds in online learning. In Proceedings of the 15th International Conference Artificial Intelligence and Statistics (AISTATS), pages 823 831, 2012.
E. Ordentlich and T. M. Cover. The cost of achieving the best portfolio in hindsight. Mathematics of Operations Research, 23(4):960 982, 1998.
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference Learning Theory (COLT), pages 993-1019, 2013.
S. Sachs, H. Hadiji, T. van Erven, and C. Guzmán. Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 691-702, 2022.
S. Sachs, H. Hadiji, T. van Erven, and C. Guzmán. Accelerated rates between stochastic and adversarial online convex optimization. ArXiv preprint, arXiv:2303.03277 2023.
N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. Advances in Neural Information Processing Systems 23 (NIPS), pages 2199-2207, 2010.
V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems 28 (NIPS), pages 1989-2997, 2015.
T. van Erven and W. M. Koolen. MetaGrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29 (NIPS), pages 3666-3674, 2016.
G. Wang, S. Lu, and L. Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI), pages 659-668, 2019.
C. Wei, Y. Hong, and C. Lu. Tracking the best expert in non-stationary stochastic environments, In Advances in Neural Information Processing Systems 29 (NIPS), pages 3972-3980, 2016.
Y.-H. Yan, Zhao, and Z. Zhou. Universal online learning with gradient variations: multi-layer online ensemble approach. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 37682-37715, 2023.
T. Yang, M. Mahdavi, R. Jin, and S. Zhu. Regret bounded by gradual variation for online convex optimization. Machine Learning, 95(2):183-223, 2014.
W. Yang, Wang, P. Zhao, and I.. Zhang. Universal online convex optimization with projection per round. ArXiv preprint, 1977 2024.
12

---

L. Zhang, S. Lu, and Z.-H. Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 1330-1340, 2018.
L. Zhang, T.-Y. Liu, and Z.-H. Zhou, Adaptive regret of convex and smooth functions. Proceedings of the 36th International Conference on Machine Learning (ICML), pages 7414-7423, 2019.
L. Zhang, G. Wang, J. Yi, and T. Yang. A simple yet universal strategy for online convex optimization. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26605-
26623, 2022a.
M. Zhang, P. Zhao. H. Luo, and Z.-H. Zhou, No-regret learning in time-varying zero-sum games. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26772- 26808, 2022b.
Zhao. Online Ensemble Theories and Methods for Robust Online Learning. PhD thesis, Nanjing University, Nanjing, China, 2021. Advisor: Zhi-Hua Zhou.
P. Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 12510-12520, 2020.
Zhao, Y.-F. Xie, L. Zhang, and Z.-H. Zhou. Efficient methods for non-stationary online learning. In Advances Neural Information Processing Systems 35 (NeurIPS), pages 11573-11585, 2022.
Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.
Z. Zhou. Ensemble Methods: Foundations and Algorithms. Chapman & Hall/CRC Press, 2012.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928-936. 2003.
13

---

A On Smoothness Assumption
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 space as in Assumption 2. The relaxed smoothness assumption is detailed in the following.
Assumption 3 (Relaxed Smoothness). Under the condition of [ - G for any x E and t E [T]. all online functions are L-smooth: | (x) - V ( <
L x y for any & E [2'] and
y E R4, where X4 _ {x b x X, b E C/2 ] and B [ X S 11 is unit ball.
The domain of Assumption
slightly larger than X' - for any X+ E X4,, we can always find an E X' such that ||+ - x|| I G/T. 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 I. for any online function f(-) satisfying Assumption 3, it holds that [V fly)l s 2LD,(3 (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 ʃ IRd + R is L-smooth and bounded from below, then for any E R2 it holds that
[x)( S 2T [(x))
(((x) - inf inf f(x) f(x)
(A.1)
yERu
Next, we aim to prove that if we only need (A.1) on 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-boundee property. Specifically, for any x, V E Id,, it holds that
L | < f(x) 2
(- (-Vf(x).
f(x) inf f(y),
yERR
where the first step requires smoothness on and x + Consequently, by taking maximization over v, it holds that
f(x) inf f(y)= 2 sup (f))) 1|v|2= YERu
2L |V
VERd
which leads to the self-bounding property (A.1) by taking v - 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 E and x 1. fx).. Under Assumption 1, this can satisfied by requiring smoothness
slightly larger domain than X' namely, X4 A {x+ b/x E X, b E G/L-
Now we are ready to prove the final result. To begin with, we define a surrogate function of g(x) ê f(x) (xx)) x) for any x e X, where xo X. Due to the above property we have just proved, by requiring smoothness on X4. we have
( < 2L [((x)
inf yERa a(x))
Denoting by y* E arg min g(v), the above inequality equals to
[V/(() - V 2 < 2L (f(x) (V/(())) ((y') (V)))))))))))))))(((((())))))))) ( (V/(x)))))
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 Xo. leading to [V v f2x)))l < 22DD((Xo. x) for any x, Xg E X. which finishes the proof.
B Omitted Details of Algorithm! 1
In this section, we provide some omitted details of our Algorithm 1, including the losses and update rules of the base and meta learners.
14

---

Base Learners. To begin with, we duplicate the candidate coefficient pool (2.1) for both the exp- concave coefficient and the strongly convex coefficient X, denoted by Huu _ H. and 7 _ H. Consequently, denoting by Nesp = Nac H the size of candidate pool, for each O; E Hux and A₃ E 7t", where [N and j [, we define corresponding groups of base learners for optimizing exp-concave and strongly convex functions. Specifically, for o-exp-concave functions, we define a group of base learners {b, ie (Nee)) where the i-th base learner runs the algorithm below:
X,, arg xEX
arg min { (x.- x) Der, (x, &(,))
(B.1)
Xt+1; arg min (Vii (xt.) .) x) + Der.. (x, 8t,1)
where (x) f U,, Ul = (1+ _ Σ Vhghg (x., ( (x..)) og is the i-th element in HeP,, and (.) is surrogate loss function for _, defined as
(V
x x
Similarly, for A-strongly convex functions, we define group of base learners (B,5 )etNNy. where the i-th base learner runs the algorithm below:
x 1x Th V (x
R 1xx Thi (x,,))))
(B.2)
where 7/. = 2/(1 + A,t), x is the i-th element in Ht and (.) is a surrogate loss function for B defined as
[x, (x) (Vfe(x,), + X; ||x x1l??
4
For convex functions, we only have to define one base learner B3, which updates as
X1, Hxx Rr, ne Vi & 1 mi. (x:)).
(B.3)
where T/, = min! (D/ - (VX(()) - V/:-i(X
Finally, we conclude the con-
figurations of base learners. Specifically, we deploy
[B.JEIN] A " U (B; JEEN the total set of base learners.
U (B {B), where N & Nop + N + 1, (B.4)
Meta Learner. The meta learner simply runs OPTIMISTIC-ADAAPPMM-PPPPM (Wei et al., 2016), which updates as follows:
P441a x Ex, exp(er, Wei:
9. We,1 = (Wr exp (Et-1.TT,, -E (ri, me,))) fe-1.
(B.5)
where 4, xx,) is the loss of the i-th dimension, instantaneous regret, my (V (x;-(xx,,,, xx.i) for the index indicating 8 and m for indexes indicating 13x and t The learning rate ε,, is chosen as
= (Le. l,s represents the
In
E. min
(B.6)
8 V
(Ta.i m,
C Proof for Section 3
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 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 A (x,,x) and
T
VT
V [z (x.) - (x--
1=2
15

---

for short. Using the analysis in Section 3.2, the empirical gradient variation can bounded as
T
T
VT
[x(( - [|] +3 Vf((x*) - ff-11xx)11
1=2
T
T
+3
Σ
fi-1 (x') - v 56 6L Σ
D), + 3V + 6L
Σ
D/-
xx-1)
1=2
1=2
1=2
< 3V + 12L
xx),xxx)).
(C.1)
Regret Decomposition. decompose the regret as
Denoting by x* E arg minxex Erem fe(x), for convex functions, we
REGT Σ gi, X x²) Σ Dj,((xx xx)
(by (3.3))
T Σ
Σ gr, X x(,,) +
Ni (x1,i)
New (x*)
Σ Dx x1);
(C.2)
META-REG
BASE-REG
where (x) x).
For a-exp-concave functions, we decompose the regret as
T
1
REGT
Xr - -x) x')-
Dr. (x)
Σ
Dj. (x' x1)
(by (3.3))
t=
t=1
1
gr, X x²)
ge Xx xx²)²
Dj. (x" xt)
2
(=1
t=1
T
gg X1 - x
0+
1g X - x2,5,)
(by ar Sa S 200))
MEG
L (Xt,1))
hap (x*)
Dj. (x* xt),
(C.3)
BASE:REs REG
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 function h (x) (g. + (x),
x x,
where E H. defined in (2.1).
For X-strongly convex functions, following the similar decomposition in the exp-concavity case,
T
T
Age
REGT S
Σ
gge Xx - x
X
Xx, 1|
(by A/+ S AY 2
4
1=1
t=1
META-REG
T h (Xt,i-) Σ
T
hig (x*x(()))
Σ
(x'(",, Xt),
(C.4)
2
BasE ReG
due to the definition of the surrogate h
gge x) + X ||x
xel2. where X, in (2.1).
Meta Regret Analysis. We adopt PPTIMISTIC-ADPTT-ML-E (Wei et al., 2016] as the meta
learner, and present its regret analysis below for self-containedness.
16

---

Lemma 2 (Theorem 3.4 of Wei et al. [2016]). Denoting by Pt the weights of the algorithm, & the loss vector, and my,4 the optimism, by choosing the learning rate optimally as (B.6), the regret of OPTMISTIC-ADDPT--IL-S
(B.5) with respect to any expert i E [N) satisfies
T
Σ ee P: - e.) S CON 1+ E(ros - m,,)2 Ci,
(rrs-maa
where Tt,i = Per, - ez), e; denotes the i-th standard basis vector, Co = VIn N + In(1 +11+5 (1 In(T + 1)))/// and Ci 2In + In(1 N + In( 1)))) + 2 N N6
0z) = (gr, X - x(,))- Besides, since the number of base learners N = (log 7) as explained in Section 2, the constants Co and C1 are in the order of Oloo log T) and can be treated as ignorable constants, following previous convention [Luo and Schapire, 2015, Gaillard et al., 2014].
Here we adopt l, (g. xt,i) such that (Lc. -
For convex functions, choose the optimism as my,i 1, xx,i) for the index indicating the convex base learner. As explained in Section 3.1, although X, is unknown for now, we only require the scalar value of (g)) Denoting by 2 Xe), it actually forms fixed-point problem of 2 = 1g me,s and my,i depends on z. Such a one-dimensional fixed-point problem can be solved with an O(/TT) approximation error through O Olog T) binary searches, and aggregating the approximate error over the whole time horizon will only incur an additive constant the final regret. As result, such an optimism setup is valid. Consequently, the meta regret in (C.2) can be bounded as
X2 (z)). where x; is function of since x; depends on pt,s, Pt. relies on
T
META-REG S Con
1+
g
g--1, 22
(by Lemma 2)
S <ovI+ D2V G S Cop
1 1+3D²V + 12LD2 Σ Dr. (xt(xxxx:)+ +
(by (C.1))
T
Co
s <o(Vv)) Co
12LD Σ
Σ 2C₂
Dj. (xx,xx))
where the second step adopts Assumption 1, the fourth step uses V va+bb S v Vb for any a, 2 0. the last step uses AM-GG inequality: vab < azr + 2x for any a, b, x >> 0. Note that C2 is used to ensure the positive Bregman divergence term be canceled and will be specified in the end.
2
For exp-concave functions, we choose the optimism as m,, = 0 for indexes indicating exp-concave base learners. By Lemma 2, the meta regret in (C.3) can be bounded
T
T
META-REG S Co
1+
gr, Xt Xt,5
g Xt - xx,
1=1
1=1
< <0(Cs))
Cu
Cr.z
Be X
x
(C.5)
2C3
where the last step omits the ignorable additive Co or Ci terms and is due AM-GM inequality, C₂ is a constant to be specified.
For strongly convex functions, we choose the optimism m4,i 0 for indexes i indicating strongly convex base learners. By Lemma 2, the meta regret in (C.4) can be bounded as
Age
META-REG SCO,
1+
gr, X
)2
xx xt, +
(by Lemma 2)
t=1
t=1
\ T
SCom
1
2
[x
X1, | 1
Xx X1,
12 C1 (by Assumption 1)
1=1
17

---

CoD2
X,
T X Xt.s- 11?
- O((C)) +
(C.6)
2C
where the last step omits the ignorable additive Co or C1 terms and is due AM-GM inequality. C4 is a constant to be specified.
Base Regret Analysis. For conver functions, when using the update rule (B.3), due to the standard analysis of OOMD for convex functions (e.g.. Lemma 10 of Yan et al. [2023]), holds that
T
BASE-REa S 5D
1+
Vh (X4,)
Vh (x--1,))1
T
= -DD + VT + 0(1) S ((VVT) + 5D,
12T Σ
Dj, (x*,x)
(by (C.1))
5D T
< + +
Σ (x*,,,,),, 2C3 [=1
where the second step is due to the property the surrogate function: (x,,, = gg. and the last step uses AM-GM inequality. Cs is constant to be specified.
For exp-concave functions, when using the update rule (B.1), 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 as
BASE- S
16d 0:+-
In
1
Olia 8d
T
cxp (xt,)) - Vi (xx-1,5)) )12 0(1.
(C.7)
1=2
Next, we analyze the empirical gradient variation defined on the surrogate function 4 (-):
Vh W (x1,5-)
Vh, (x4-1,;-) )|(
Oht
0g5*
11-1, xx-1,-) 2
+
ge (gr x1,1.)
8i-1
2
2
t=2
T
3v +3)
>
0₂+
gi (gi, x1,1 ||
+3
gt 1 1g
(8--1, -x--1,1)
2
1=2
1=2
<3V, +6 Σ
2 gi (gr, X1 x1,,)
(C.8)
T
9V + 36L
Σ Dj, (x'xxxx) x.) + 20 G²
Σ gg X - x1,5 (by (C.1) and Assumption 1)
where the first step is due to the property of the surrogate function: V (x = Co
7 (gt, X
Xt,i), the second step is by the Muuchy-Schwarz inequality: (a + b + c)² < 3(a² + 6² c²) for any
a, b, e E R. Plugging the surrogate's 's empirical gradient variation back to the base regret, we obtain
BASE-REG
<
16d a+-
In
1
9cGs
VT
+
9a,, L
Dr (x*, xx) +
0 G2
Σ
T
gr Xx - xx,
8d
2d
4d
- In(CoVT))
+ CRar.
16d
99,, L
Σ
T
Dí, (x* Xx) +
a G
Σ
T
(gr, Xs - xe.o)?
2d
4d
t=1
t=1
d
72L
T
402
<
+
Σ
D (x* xx)
+
Bi X; - OlnCo)
Co
Co
t=l
t=1
18

---

The second step requires C. 2 1 by Lemma 5 and uses the property of the best base learner, i.e., O+-- I a 2a... The last step because of a; S
For strongly convex functions, when using the update rule (B.2), due to the analysis of OOMD for strongly convex functions (e.g., Lemma 12 of Yan et al. [2023]), the base regret can be bounded as
16G In (1 1 A. Σ Vig (xx,,)
- 1. (x= + 0(1) (C.9)
BASE-RRG S Ap-
Next, we analyze the empirical gradient variation defined on the surrogate function h2 (-):
Vhi. (x1,,)) V 1,,- (xx-1.
T
2
Σ
g1
[x,ii" - -x() - ----1
(x--1,5* - x(-1)
2
2
1=2
$ T +3
Σ
T
A
(x,,i- - -xi
1/2
+3
Σ
T
Xi+
(x -x-11)
2
(C.10)
2
2
1=2
1=2
T
T
S 9V 36L
Σ
(x,,x"xxi + +2
Σ
X
-xl1?
(by (C.1))
where the first step is due to the property of the surrogate: Vh (x,.) (x..) = g + second step is due the Cauchy-Schyee inequality. Plugging the surrogate' 's empirical gradient variation back to the base regret, we obtain
2 (xt, xt). and the
16G2 In (1 [1 Vr + 36LA,
T Σ
T
BASE-REE SSEERRE- & dv-
x1) + 22
X - xell
1=1
1=1
0 (^ (n((cvr)) +
1602
36LAG Σ D),(x'x' (x), + +2
Σ
||x,,t xell?
Cydin
1=1
so (0( ln
L7
32G² T
(x, xx)
x + OIn C7),
O7
where the second step requires O7 2 by Lemma and uses the property of the best base learner, ie., di. SAS 2). The last step is due to X; < 1.
Regret Analysis. For conver functions, by combining the meta and base regret, it holds that
REGT S0
Vr) + O(22 Cs)
Co
20s -
5D
1) Σ Dj. (x* x1) S O(V
2C₂
by choosing C2 Co and C3= 5D.
For exp-concave functions, by combining the meta and base regret, holds that
REGT 0o
d In Vr
+ OCC + In) +
Co
+
4G2
a+.
gt X4 x1,1
20's
Co
4
72L
T Σ Dr (x" x1) <
+
In V/7
Co
2
1=1
by choosing Co = max(1, 11, 1441, 32G and C3 4Co Note that such a parameter configuration will only add an (11aa) factor to the final regret bound, which can be absorbed.
a..
a..
For strongly convex functions, by combining the meta and base regret, holds that
REGT S O (H + O(C Cl
Co
32G²
A/.
T
l|xe
Xt,i- 1|2
2C4
C7
4
19

---

Cn -2
-
1
Σ
T
n (x), S S0 (
by choosing C7 max (1, 1152G 250G² and C₁ 1Ca Note that such parameter configu- A."
Aia
ration will only add an ((1/A) factor to the final regret bound, which can be absorbed.
Note that the constants C22 C3 Ca, Cs,, Co. C7 only exist in analysis and thus can be chosen arbitrarily. finishing the proof.
D Proofs for Section
In this section, we provide proofs for Section 4, including Theorem 2 and Theorem 3.
D.1 Proof of Theorem 2
Proof. To begin with, we give different decomposition for the empirical gradient variation Vy:
Vr 2
gc 2 +
g
g
16L
Σ f((x))
(D.1)
where the last step is by the self-bounding property (A.1) for non-negative functions. For simplicity, we denote by F7 Di= fx(x)).
The regret decomposiiion is the same as that in the proof of Theorem 1 (i.e., (C.2), (C.3), and (C.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 I achieves the small-loss bounds without modifying the algorithm. As result, the meta algorithm and the corresponding step size and optimism configurations are the same as that in the proof of Theorem 1.
For conver functions, by choosing the optimism M4,1 (g xx,,) for the index indicating the base learner for the convex case, the meta regret in (C.2) can be bounded as
T
META-REG S Co
1+
Σ
81-1.X; - - + C1
(by Lemma 2)
1=1
DOVI+DDV C1 S 16 C1.
(by Assumption and (D.1))
For exp-concave functions, we choose the optimism as my, = 0 for indexes indicating the exp- concave base learners. The meta regret is bounded in the same way as (C.5).
For strongly convex functions, we choose the optimism as m,, = for indexes indicating the strongly convex base learners. The meta regret is bounded in the same way as (C.6).
Base Regret Analysis. For conver functions, using the same base algorithms as the proof of Theorem 1, the base regret can be bounded as
BASE-REG S 5DV1 + VT + 0(1) S 5D 16LF + 0(1).
For exp-concave functions, using the same base algorithms as in the proof of Theorem 1, the base regret can be bounded by (C.7). Following (C.8), the empirical gradient variation defined on the surrogate function hexp (-) can be bounded
T
T
V h (X,,5) - Chi (X-- (x1-1,1))1 I11 < 3v + Σ
ai+ 2 gr (ge,
Xt -x.5.>
< 48LF + 20 G2 Σ
gg. x2.
(by Assumption and (D.1))
20

---

Plugging the surrogate's empirical gradient variation back to the base regret, we obtain
16d ai*
( 6Lar
a.. G2
BASE-REG
In
1
Fr
X, -x,,0)² + O(1)
d
4d
16d
In
Cs
1+ 6Lau Fi)) F.))
16d
( aa
Σ
gt, X
x1,11?
d
Czas+
4d
32d
61 Fr.
4G T
In
+
+ Cs
Σ
gt, x1, + Css)s),
d
1=1
where the second step requires Cs 2 1 by Lemma and uses the property of the best base learner, Le., Oij. S a S 20;.. The last step is due to 0; S 1.
For strongly conver functions, using the same base algorithms as in the proof of Theorem 1, the base regret can be bounded by (C.9). Following (C.10), the empirical gradient variation defined on the surrogate function hy, (.) can be bounded as
T
VhE (xL,e) 1
)l( 3V,
\i- 2
X1,, - x1)
T 11
< 48LF + 2X
Σ
x
(by (D.1))
t=1
Plugging the surrogate's 's empirical gradient variation back to the base regret, we obtain
16G²
In (1 1 + 48L Fr. + 21,
T
BASE-REG S
|
x,11
+ 0(1)
Ax-
t=1
16G
160²
In (Co (1 48TA;; Codss
21
|x,00
xx11?
Ap
32G²
32G
T
In(1 + 4TLFT) +
Σ
| x:|1² O Co),
C9
where the second step requires Cg 2 1 by Lemma and uses the property of the best base learner, i.e. di. SAS 2),.. The last step is due to X; 1.
Regret Analysis. For conver functions, by combining the meta and base regret, it holds that
REG, Cov1+ 16D + 5D 16LF, C1 S O(VFr), where the last step is due to Lemma 9 of Zhao et al. [2024], restated below for self-containedness. Lemma 3 (Lemma of Zhao et al. [2024]). For any x, a, satisfying - y S vax + holds that x y S / ay + ab + b.
For exp-concave functions. by combining the meta and base regret, holds that
REGT <
Co
+
4G²
a4-
gg X2 xx,
32d
In
1+
6L +OCCs+ + Cx)
d Fr
2C
Cs
4
a
32d In
61
+ 0(11) 0 ( d inFF)
1+
FT
(by Lemma 6)
where the second step chooses C3 = 4C. and Cs = max (1, 32G }. Note that such parameter configuration will only add an ((1/a) factor to the final regret bound, which can be absorbed.
For strongly conver functions, by combining the meta and base regret, holds that
D2
32G²
d
T
320² In(1 48LFT) + O(C+ + Cn)
REGT 5
Σ
Xx
X1.5 1|
2C4
C
4
21

---

32G 1n(1 + 48LFT) s
( In Fr)
S
(by Lemma 6)
where the second step is by choosing C1= 4CoD2 and Cg max(1, 256G² }. Note that such A,
A.
parameter configuration will only add an (1/A)) factor the final regret bound, which can be
absorbed. Also note that the constants C3, Ca, Cs. Cg only exist in analysis and thus can be chosen arbitrarily, finishing the proof.
D.2
Proof of Theorem 3
Proof. To begin with, we give a different analysis of the empirical gradient variation:
T
B[VT] S 5E
- (V)(xx)))V(((x)))) 5
(x, - VVF(x']]
t=2
T
+5E
IVF - v
+5
|VFF-1(x*) - (x--1(x
1=2
T
+5E
IV - Vi
< 100 + 55 + 201. Σ Dr. xx), (D.2)
where the first step is due to Caacch-Schwand inequality and the last step because of the definitions of of.r and Eir (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 ExEmy fe(x), for conver functions,
decompose the regret as
T (((x))
T
E E[REGT] = E
Σ Fx(x*)
=E E
Σ (F.(
Σ Dr, xx)
1=1
E
V (x X1 xx))
Σ Dr. (x" xt)
T Σ
= E
(gr, X x1,10)
+E
n (x1,1) ) - hi (x*)
(x x:),
(x"
(=1
REG
BASP-REG
where the first and third step use (x = ([ff(x))) the second step uses the definition of Bregman divergence, and the fourth step is due to (x) 2 (gr. x).
For exp-concave functions, following the similar decomposition as in the proof of Theorem I in Appendix C, we decompose the regret as
1
1
E REGT]
E
V (x::. X1 x")
Dr. (x", xx)
Σ
Dr. (x" x1)
2
T
T
T
E
Vf((())
Xt -x')
Σ
Dj. (x" xxi
1
D (x" x1)
2 t=1
2 1=1
T
T
T
<
E
gg -x')
0 4
(g X2 -x-)²
Σ
Dr. x1)
2
1=1
1=1
T
[gr X2
x1,1)
(g, X )2
4
META-REO
22

---

1 T
E
F (xt, ) - n (xx)
Σ
Dr (x),
2
BASE.REa
where the second step uses the definition of the expected function Fe(-), the third step requires the exp-concavity of f((-), and the fourth step is due to (x,(() _ (gr. x) + 4 ( fxx)),, - x,)²
where E H. defined in (2.1).
For strongly convex functions, following the similar decomposition as in Appendix C, we have
T
E REGT
E
(x.(xx); Xx
x*)
Dr. F. (x xx)
Dr, Dr,(x'
2
A T
S
Σ 1=1
gr Xt 10-x x*)
Σ
Xx - x 1|
2 Σ
Dr. ,x*xxi)
4
t=1
T
T
A
<
gr.
x
X
xx,,-11
4
t=1
(=1
META-RFG
1 T
E
(xx,r)
N9. (x*)
Σ
DR (x*, (x*x,,))
2
BASE
where the second step, different from the exp-concave case, only requires the strong convexity of Fc(:), and the third step is due to (x) & (g.,)) + A ||x x, 11 where X E H. defined in (2.1).
Meta Regret Analysis. Our Algorithm I 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 (i.e., in Appendix C).
For convex functions, the meta regret can be bounded as
META-REG E E Co C ai s CoV D'E(V) Ci
T
<
Copp 1 522 + +1.)) 2
Dr. (xt( +C1
(by (D.2)
so 50(1
oo. vo(Voia
Co
EEar + O(Cio) +
Σ Dn x)),
2C10
t=1
where the second step is by Jensen's 's inequality and the last step is due to AM-GM inequality. C1o is a constant be specified."
For exp-concave and strongly convex functions, the meta regret is bounded in the same way as (C.5)
and (C.6), and thus omitted here.
Base Regret Analysis.
For conver functions, the base regret can be bounded as
BASE-REG S 5D 1+ E[V]] S 5D,
1 10 + +5E7. + 20L Σ Dr, (x+,
tml
5o Co + Eg. + O(CI)) +
20 Σ Dr. xx),
5D
T
where the first step is by Jensen's inequality, the second step due to (D.2), and the last step because of AM-GM incquality. C1 is a constant to be specified.
23

---

For exp-concave functions, the base regret is bounded by (C.7). Following (D.2), we control the empirical gradient variation defined on surrogates
E
Vh sap (x,,))
V (xt (xc- 33 +6 Σ
aie Br ge, Xr Xc,t-)
T
< 15(2 + )
+ 60L
Σ
Dr. (xx (x xx) + 2a C2
Σ
(g), X - x²
Plugging the surrogate's empirical gradient variation back to the base regret, obtain
1 (1+
BASE-REG I
16d
In
15ar 8d
(20 -1
15Lay
Dp x1)
ax+
2d
1=1
OZ C
(0 d
gt X x2,101 5
In (oΩ. + (
+ O(In C12)
4d
a
120L
C12 Dr. (x* xi) + 4G T
T
Σ
C12 gr, X - x1,;,)²
where the second step requires C12 2 1 by Lemma 5.
For strongly conver functions, need to delve into the proof details of the base algorithm, i.e., OOMD (B.2) for strongly convex functions with step size = 2/(1 + A²t). For example, from Lemma 12 of Yan al. [2023], the base regret can be bounded
BASE-REG 4
1 Aget
E
(xL,.)) (x- 1, |||] +011.
t=2
Subsequently, we analyze the empirical gradient variation defined on surrogates in each round, i.e., || (x,,+) - V4 (xx- )1² Denoting by of - maxxex (VVx)) - (x)(1
and 2 A E[supxex [VF(xx 1 for simplicity,
E
T (xe,))) Vii-1, (xc-1. }|?
Apa (X,,* xx) -:-
d (x1-1, xx-1)
E
g: +
2
2
< 3E
[|g gi-1 [13] +3
Air
(Xt,3- - -xx)
2
+3
As
(x1-1,5- - -x--))
2
2
< <15(0
+o 2LD
F. (x*, xx) + 2L.D
Fi ,x*,x + 23)
(by (D.2))
+ * |x,=
12 + X | 11.
where the first step is due the property of the surrogate: Vhţ, = ge + 2 (xt,) x)), and the second step is due to the Mauchy-Sehware inequality. Plugging the above term back into the base regret and omitting the ignorable (1) term, we achieve
2
60
T
of
of + Ei + -10LL
DF. (x*,xx) + 1F,,,x"' (x*,x,,
BASE-REG
S
Σ
Ap-
t
Axtt
T
X2. |x, - x 2 + X2. 11,-11111----- 11 11.
\xtt
1=2
To handle the above term of Σ lemma from Yan et al. [2023].
1 a// for some variable sequence (ar import useful
Lemma 4 (Lemma 9 of Yan al. [2023]). For sequence of (at IT and b, where at, b 0 for any T
t [T), denoting by amax _ max, a, and A A [b
TT arl, we have
T
Omax (1 + In A) B
1
bl
24

---

Using Lemma 4, we control the base regret as
(1 (o (x(0
i. + Σ9.T
BASE-REG O
In
o max + +maxx
480LGD
8D2
2 Σ (x'(x", (x))
In
1
1+ 21
Xt,5 xt|1?
dv-
50
In P. + 21.r
(o max
+
2 max)
+ +
T + >
960LGD
T
16 T
Dx, xx) +
Σ
X - -xel?
C13
C14
1=2
where the first term initializes Lemma as d2 of + Eng (i.e., amax 0 + En max))
)) and
b 1/(o + 5 max)) the second term initializes Lemma a, Dr (x* xx) + Dr, (x*, xt-1)
(i.c.. 4max = 4GD due to Assumption 1) and 6 = A the third term initializes Lemma 4 as a; X | -xel 12 + XT. Xt-L.;* x (i.c., dmax 21 due to X S 1 and Assumption
and b = A The (1) term contains ignorable terms like ((1A)) The second step requires
C13, C14 2 1 by Lemma
Regret Analysis.
For convex functions, by combining the meta and base regret, it holds that
REG 00
oo. (Vviir + 21.T
+ +0 + Cn1)+ +
Co 20
+
5D
1)
Σ 1=1
Dr. (x", x,)
2011
00 Voiar + 11:T)
by choosing C10 Co and Cn1 5D.
For exp-concave functions, by combining the meta and base regret, holds that
REGT S 0 (02 (oî. + + + + + 112)) +
120L 1
T
Dr.
(x*,
C12
2
1=1
(Co
Co
+
4G
ar.
Σ
gt X xx,)) 50
d
In
( 21r)
2C3
C12
4
by choosing C12 max(1, m1,x(1,2400) 240L, 32G² } and C3 4C., Note that such parameter configuration will only add an (1/aa) factor to the final regret bound, which can be absorbed.
o..
For strongly convex functions, by combining the meta and base regret, it holds that
REGT s so
(+((
o.. + MTT + 2mxx) In Tmax + Σ2 E
+ OOCC + In C13 + +In
CoD2
16D2
1600GD
1
Σ
1xxe Xe,1 112
Σ
Dr, (x""x"xxxx (x*,
2C4
C14
4
C1a
2
t=1
t=1
<0 (1
c.. Σ2
In
o2
+ Σ
A, by choosing Cia = max(1, 1920LGD). C14 = max 128D* and C4 = 4C.D², Note that such a parameter configuration will only add an ((1/A) factor to the final bound, which can be absorbed.
Note that the constants C3, C4, C1o, Cn, C12, C13, C14 only exist in analysis and thus can be chosen arbitrarily, finishing the proof.
E
Technical Lemmas
Lemma 5. For any 1,b > 0, it holds that In(a + b) I In(Ca) + & for some C C2. 1.
25

---

Proof. The one-line proof is presented below:
In(a + 6) < In(Ca + 6) S In(Ca) + In (1 Ca) = In(Ca) + C
Ca
where the first step is due to C 2 1, and the last step adopts In(1 + x) S x for any 2 0.
Lemma 6 (Corollary 5 of Orabona et al. [2012]). If a, b, c, d. > 0 satisfy I - d S a an + c).
then it holds that
2bd + 20) 2ab
d S aln
2abln
6
26

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have claimed the paper's contribution both the abstract and the introduc- tion part.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: One limitation we could discover is that our approach is not applicable in multi-player games since 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 limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "LLimitations" 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
27

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: crijps.ccpuubli//uut
/Coee/uumdaaaaii iosomisssion ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, 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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips: http://sss.ccpllccccccccccllleel
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is 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.
30

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
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, scraped datasets)?
Question:
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 such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 require this, but we encourage authors to take this into account and make 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 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 dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thoode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

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


Reviews:
[{"review_id": "j01V6h0eLO", "reviewer": "Reviewer_KThz", "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.", "questions": "See above.", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors tackle a very interesting problem in online convex optimization. The paper is well-written and the presentation makes it easy to follow. The main novelty lies in Sections 3.2 and 3.3, where they provide a new way of tackling gradient variations by utilizing the Bregman divergence term. They also make clever use of Proposition 1 in their analysis. The overall method utilizes techniques from several existing works and cleverly combines them to achieve an impressive bound on the regret.", "weaknesses": "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.\n\nAnother 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback and appreciation of our work! In the following, we answer your questions about feasible analytical parameters and the statements of the $\\log \\log T$ term.\n\n---\n\n**Q1.** 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.\n\n**A1.** Thank you for the great question! We checked the proof carefully again and realized that the current choices of these parameters may not be favorable enough. To fix this, we provide another choice below.\n\nFor simplicity, we omit unimportant constants (we omit $C_0$ also since $C_0 \\approx \\log \\log T$) and consider satisfying the following two conditions simultaneously: $\\frac{1}{C_3} + \\frac{1}{C_6} - \\alpha_i^* \\le 0$ and $\\frac{1}{C_6} - 1 \\le 0$. The new choice of parameters is $C_6 = \\max\\{1, \\frac{2}{\\alpha_i^*}\\}$ and $C_3 = \\frac{2}{\\alpha_i^*}$ such that $\\frac{1}{C_6} \\le \\frac{\\alpha_i^*}{2}$, $\\frac{1}{C_6} \\le 1$, and $\\frac{1}{C_3} = \\frac{\\alpha_i^*}{2}$. Note that these constants only exist in analysis and thus can be chosen arbitrarily. As a cost, we need to analyze the positive terms depending on $C_3$ and $C_6$, i.e., $O(C_3 + \\ln C_6)$, as shown in the equation above Line 594. Fortunately, the positive terms are also acceptable since $C_3 = \\frac{2}{\\alpha_i^*} \\approx \\frac{1}{\\alpha}$ and $\\ln C_6 \\approx \\ln (1+\\frac{1}{\\alpha}) \\le \\frac{1}{\\alpha}$. And $\\frac{1}{\\alpha}$ is a constant independent of time horizon $T$ and can be absorbed into the final bound of $\\frac{d}{\\alpha}\\log V_T$. We will use this new choice of analytical parameters in the revised version. Thanks for highlighting this point for improvement.\n\n---\n\n**Q2.** 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.\n\n**A2.** Thank you for the advice. We will add a statement about the $\\log \\log T$ term in the caption of Table 1 in the revised version. Thanks for highlighting this point for improvement.\n\n---\n\nWe believe that our work offers valuable contributions to the community. We hope our response addresses your concerns and we are happy to provide further clarifications if needed during the following author-reviewer discussions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FcUUJhYeVP", "reviewer": "Reviewer_S4Zf", "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.", "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.\n\nQ2) Improvement over the results of Yan et al. [2023] seems incremental. Are there scenarios where this improvement becomes significant?\n\nQ3) 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": "No significant limitations. Necessary assumptions about the problem setting are properly addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1) The paper is well written and easy to understand.\n\nS2) The literature review is comprehensive and up to date.\n\nS3) Simplicity of the incorporation of Bregman divergence is a plus.", "weaknesses": "W1) The contribution seems limited in that the improvement is only logarithmic for both efficiency and regret results.\n\nW2) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your feedback. Below, we aim to address your concerns about the number of base learners, the significance of our contributions, and the algorithmic improvements.\n\n---\n\n**Q1-a.** Why is $\\log^2 T$ computational complexity claimed to be inefficient throughout the paper?\n\n**A1-a.** Thank you for the question. We clarify that the $\\log^2 T$ complexity is ***less efficient*** compared with methods with only $\\log T$ base learners. We will revise the statements of \"inefficient\" in the next version.\n\n**Q1-b.** 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.\n\n**A1-b.** Thank you for the comment. Online ensemble runs a meta learner over multiple base learners and each base learner runs an online learning algo. separately. Consider a simple case: each base learner runs OGD $x_{t+1} = \\Pi_{D}[x_t - \\eta \\nabla f_t(x_t)]$, where $\\nabla f_t(x_t)$ is the gradient and $\\Pi_D[\\cdot]$ is the projection onto the domain. Since computing gradients and projections is usually time-consuming, and each base learner has to conduct such operations in their own update, it is essential to reduce the number of them. In this work, we reduce the gradient query number to one per round by using surrogate functions and reduce the projection number by reducing the number of base learners. We will revise the paper to make this clearer to readers.\n\n---\n\n**Q2.** The contribution seems limited in that the improvement is only logarithmic for both efficiency and regret results. Are there scenarios where the improvement over the results of Yan et al. [2023] becomes significant? (response to W1 and Q2)\n\n**A2.** Thank you for the question. We clarify the significance of our paper from the aspects of the problem, applications, and techniques below.\n\n* **Problem:** OCO is fundamental in online learning due to its generality. Curvatures are important to the best attainable results in OCO. However, traditional methods require knowing them in advance to select suitable algorithms, which is cumbersome in practice. ***Universal*** methods do not require such prior knowledge and can achieve the same optimal rates as if the curvatures were known. Furthermore, the ***gradient variation*** is essential in modern online learning due to its profound connections with stochastic/adversarial optimization, game theory, etc. Therefore, studying how to achieve gradient-variation regret in universal online learning is an essential problem. We contribute to ***achieving the optimal rates in this fundamental problem***, thereby solving the ***major open problem in [3]*** (please kindly refer to their conclusion). \n* **Applications:** We validate the significance of our results in the ***stochastically extended adversarial (SEA) model*** and ***dynamic regret minimization*** and achieve ***SOTA*** rates therein. Note that [3] only achieved suboptimal bounds in the SEA model (Table 3 therein) and cannot be used in the dynamic regret minimization problem.\n* **Techniques:** We have provided a novel technical perspective to gradient-variation regret. Instead of controlling the algorithm stability of $\\|x_t - x_{t-1}\\|^2$, which is the reason for the suboptimality and inefficiency of [3]'s method, we propose leveraging the Bregman divergence-related negative terms. This is ***the first alternative solution to gradient-variation regret since it was first proposed in [1]***. We believe this technical insight is useful for broader applications and take ***dynamic regret minimization*** as an example, where a much simpler method using our technique obtains the same SOTA dynamic regret as [2]. It cannot be done via the techniques of [3].\n\nAt last, we clarify that our improvement in efficiency is not just reducing previous ones by a log factor, but ***simplifying the previous complicated three-layer algorithm of [3] to a simpler two-layer one***, as explained in Lines 223-237.\n\n---\n\n**Q3.** While the regret analysis is novel, algorithmic contribution is very limited. 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]? (response to W2 and Q3)\n\n**A3.** Thank you for the question. Below, we clarify the differences between our method and that of Zhang et al. [2022].\n\n* **Meta Algorithm:** We use Optimistic ADAPT-ML-PROD while they used ADAPT-ML-PROD. We clarify that simply using Optimistic ADAPT-ML-PROD in previous methods (e.g., in [3]) will ***not*** lead to the same optimal rates as we did. The simplicity of our meta algorithm is owing to our novel analysis to bypass the stability cancelation in [3].\n* **Base Algorithm:** We use ***surrogate functions***, defined in eq. (3.1), for the base learner update in Algorithm 1 (they directly optimized $f_t(\\cdot)$). This is also the key to ensuring our method requires only one gradient query per round. \n\nBesides, as shown in our title, one of our contributions is proposing a *simple and optimal* algorithm. In our humble opinion, designing a simple and optimal algorithm is also an unignorable contribution, because ***simple algorithms are usually more efficient and reflect the essence of the problem***, which is also acknowledged by Reviewer #y66n as one of our contributions.\n\n---\n\nWe will carefully revise the paper to ensure our contributions are clear to readers. If our responses have properly addressed your concerns, we would appreciate it so much if you could re-evaluate our work. Thank you!\n\n**References:**\n\n[1] Online Optimization with Gradual Variations, COLT 2012 (Best Student Paper)\n\n[2] Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization, JMLR 2024\n\n[3] Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach, NeurIPS 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7iQvSgUhrj", "reviewer": "Reviewer_THmn", "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.,\n$\\sum{t=1}^{T}f_{t}(x_t) - \\text{min}{x\\in\\mathcal{X}}\\sum{t=1}^{T}f_{t}(x),$\nwhere $x_t$ is the output of the proposed algorithm at round $1\\leq t\\leq T$.\nThe 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:\n\n1. To construct a universal algorithm that adaptively acts on the curvature property of the function and achieves a proper regret bound.\n2. 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$.\n3. 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:\n$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).$\n\nThe 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:\n\n1.The paper improves the number of required base learners from $\\log(T)^2$ (in [1]) to $\\log(T)$.\n\n2.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.\n\n[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": "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?\n\n2. 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.\n\n3. 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?\n\n4. Could the authors explain if the final result is optimal with respect to $V_T$ and $F_T$?\n\nMinor Points:\n\nThe terms $\\sigma_{\\text{\\max}}$ and $\\Sigma_{\\text{\\max}}$ are not defined in Theorem 3.", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper uses simple but interesting technique that contributes in tigher bounds for the case of convex losses. Inspired by [2] the authors used that exploit the imposed smoothness assumption of the loss function and Bregman divergence negative term from linearization of loss function, explained in Section 3.2.\n\n\n\n[2] P. Joulani, A. Raj, A. Gyorgy, and C. Szepesvari. A simpler approach to accelerated optimization: iterative averaging meets optimism. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.", "weaknesses": "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?\n\nThe contribution of the paper is limited to a simple technical improvement that enhances the achieved regret up to a logarithmic factor for convex functions.\n\nThe optimality of the result with respect to $V_T$ and $F_T$ has not been discussed by the authors.\n\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback and appreciation of our work! Due to the 6,000-character limit of the rebuttal, we address your major questions below and respond to other minor issues in the next reply after the discussion period starts.\n\n---\n\n**Q1.** 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?\n\n**A1.** Thank you for the question. We take $\\alpha$-exp-concavity as an example for illustration. Since **exp-concave functions are also convex**, universal methods actually guarantee the final rate as $\\min\\\\{\\frac{d}{\\alpha} \\log V_T, \\sqrt{V_T}\\\\}$, thus safeguarding $\\sqrt{V_T}$ even when $\\alpha = 1/T$. Similarly, a bound of $\\min\\\\{\\frac{d}{\\alpha} \\log T, \\sqrt{T}\\\\}$ holds for minimax regret for exp-concave functions. We will discuss this issue in the next version. Thank you for highlighting it for improvement.\n\n---\n\n**Q2.** 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?\n\n**A2.** Thank you for the question. We clarify that the ***base learner number is only determined by the algorithm design***. Previous $\\log^2 T$ base learners come from their *multi-layer (three-layer)* algo. with a *two-layer meta learner*, as explained in Line 90 and Lines 233-237. By contrast, we have only $\\log T$ base learners by using ***the single Optimistic ADAPT-ML-PROD as the meta learner***, resulting in *two layers (not three)*. We clarify that simply using Optimistic ADAPT-ML-PROD in previous methods (e.g., in [3]) cannot achieve the optimal rates. The simplicity of our meta algo. is owing to our novel analysis to bypass the stability cancelation in [3].\n\n---\n\n**Q3.** 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?\n\n**A3.** Thank you for the insightful observation. We have chosen appropriate coefficients in the detailed proofs in the appendices and we omitted them from the main paper only for clarity. For more details, please kindly refer to the proof of Theorem 1. For example, in the 'Regret Analysis' part on Page 17, the coefficients from $C_2$ to $C_7$ are used to carefully balance the positive and negative terms such that they can be canceled. And we clarify that these coefficients only exist in analysis and thus can be chosen arbitrarily.\n\n---\n\n**Q4.** Could the authors explain if the final result is optimal with respect to $V_T$ and $F_T$?\n\n**A4.** Thank you for the great question. We take $V_T$-bounds as an example for clarification. \n\n* For known curvatures (strongly convex/exp-concave/convex), the SOTA rates are $\\log V_T$, $d \\log V_T$ and $\\sqrt{V_T}$ , and can recover minimax optimal $\\log T$, $d \\log T$ and $\\sqrt{T}$. For convex functions, an $\\Omega(\\sqrt{V_T})$ lower bound is known in [Regret Bounded by Gradual Variation for Online Convex Optimization, Remark 5]. Nevertheless, for the other two cases, though the current rates are believed to be optimal, the precise problem-dependent lower bounds are still unclear. \n* In our paper, for \"optimality\", we mean that our universal bounds match the same best-known rates as if the curvature information were known. We will revise the paper to make this point clearer to readers.\n\n---\n\n**Q5.** 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.\n\n**A5.** We would like to take this opportunity to further highlight our contributions, including the problem, techniques, and applications. We will improve the presentation in the revised version.\n\n* **Problem:** Due to the importance of universal online learning due to its robustness and gradient variation due to its profound connections with stochastic/adversarial optimization, game theory, etc. Studying how to achieve gradient-variation regret in universal online learning is essential. We contribute to ***achieving the optimal rates in this fundamental problem***, thereby solving the ***major open problem in [3]*** (please kindly refer to their conclusion). \n* **Techniques:** ***Our technique's simplicity is advantageous for its generality***. It succeeds in avoiding controlling the algorithm stability of $\\|x_t - x_{t-1}\\|^2$, the reason for the suboptimality and inefficiency of [3]. It is ***the first alternative solution to gradient-variation regret since it was first proposed in [1]***. We believe this technical insight is useful for broader applications and take ***dynamic regret minimization*** as an example, where a much simpler method using our technique obtains the same SOTA dynamic regret as [2].\n* **Applications:** We validate the significance of our results in the ***stochastically extended adversarial (SEA) model*** and ***dynamic regret minimization*** and achieve ***SOTA*** rates therein. Note that [3] only achieved suboptimal bounds in the SEA model (Table 3 in [3]) and cannot be used in dynamic regret minimization.\n\n---\n\nWe will carefully revise the paper according to your suggestions and questions. If our responses have satisfactorily addressed your concerns, we would appreciate it so much if you could re-evaluate our work. Thank you!\n\n**References:**\n\n[1] Online Optimization with Gradual Variations, COLT 2012 (Best Student Paper)\n\n[2] Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization, JMLR 2024\n\n[3] Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach, NeurIPS 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C1uUQ9dTKF", "reviewer": "Reviewer_y66n", "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.\n\nThis 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.\n\nTechnique-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.", "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?\n\n2. Under the universal OCO setup, is it possible to handle time-varying curvatures, just like in [2]?\n\n3. Seems that a universal OCO algorithm cannot be anytime? The reason is that the number of base learner (for discretization) depends on $T$.\n\nReferences\n\n[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\n\n[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": "yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "I overall like such results. The authors present their observations and insights (from the regret analysis) in detail, leading to improved (and indeed optimal) regret bounds and even (conceptually) simpler algorithm design.", "weaknesses": "I didn’t spot any significant technical issues, and I'm just suggesting some minor “weakness”.\n\n1. 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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback and appreciation of our work! We answer your questions in the following.\n\n**Q1.** 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.\n\n**A1.** Thank you for the advice. Actually, the non-negative assumption is not necessary. Specifically, the non-negativity is only used in the self-bounding property, i.e., $\\|\\nabla f(x)\\|^2 \\le 2L f(x)$ to achieve small-loss bounds. Without non-negativity, the self-bounding property still holds as $\\|\\nabla f(x)\\|^2 \\le 2L (f(x) - \\inf_x f(x))$ [A Modern Introduction to Online Learning, Theorem 4.23]. In this case, we can correspondingly define a slightly complicated notion of small loss. We will emphasize that the non-negativity assumption is only adopted here for simplicity in the revised version.\n\n---\n\n**Q2.** 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.\n\n**A2.** Thank you for the advice. Our results for dynamic regret minimization hold for ***convex*** functions, and we aim to validate the generality of our proposed technique in this application. We will clarify the problem setup more clearly in the revised version. \n\n---\n\n**Q3.**  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?\n\n**A3.** Thank you for the reference. Lemma B.13 in [1] lower-bounds a quantity of $D_{\\Psi}(u,x_t)$, where $u$ is the comparator and $x_t$ is the learner's decision. Their similarity to ours is that both work uses a negative Bregman divergence term for cancellation purposes. However, the difference is that their Bregman divergence is defined on a normal barrier $\\Psi(\\cdot)$, a special self-concordant barrier, which is a widely used concept in bandit convex optimization problems. In contrast, our Bregman divergence is defined on the online function $f_t(\\cdot)$ and focuses on the full information setup.\n\n---\n\n**Q4.** Under the universal OCO setup, is it possible to handle time-varying curvatures, just like in [2]?\n\n**A4.** Thank you for the insightful question. Our work and [2] investigate two orthogonal problems regarding function curvatures. Concretely, we study the case where the curvatures are ***unknown and homogeneous***, while [2] focuses on ***known but heterogeneous*** curvatures ('known' means that the learner can access the curvature coefficients after submitting her decisions). Handling time-varying curvatures in universal problems (i.e., ***both unknown and heterogeneous*** curvature) is extremely hard and it seems impossible to deal with such a challenging problem at the moment.\n\n---\n\n**Q5.** Seems that a universal OCO algorithm cannot be anytime? The reason is that the number of base learner (for discretization) depends on $T$.\n\n**A5.** Thank you for the question. As the reviewer said, achieving anytime algorithms is hard since the number of base learners relies on the time horizon $T$. To handle unknown $T$ (an easier case), a possible solution that we could imagine may be using the doubling trick. However, it may import additional logarithmic factors in the final regret bound, which are unacceptable for exp-concave and strongly convex functions since $\\log T$ factors would ruin the desired $\\log V_T$ regret. This is also one of the open problems raised in the previous work of Zhang et al. [2022].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Overall all reviewers were positive about this work and I support their decision.
Decision: Accept (poster)