Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach
Authors: Yu-Hu Yan
Peng Zhao
Zhi-Hua Zhou
Venue: NeurIPS 2023 spotlight (2023)
Keywords: online learning

Abstract: In this paper, we propose an online convex optimization approach with two different levels of adaptivity. On a higher level, our approach is agnostic to the unknown types and curvatures of the online functions, while at a lower level, it can exploit the unknown niceness of the environments and attain problem-dependent guarantees. Specifically, we obtain $\mathcal{O}(\log V_T)$, $\mathcal{O}(d \log V_T)$ and $\hat{\mathcal{O}}(\sqrt{V_T})$ regret bounds for strongly convex, exp-concave and convex loss functions, respectively, where $d$ is the dimension, $V_T$ denotes problem-dependent gradient variations and the $\hat{\mathcal{O}}(\cdot)$-notation omits $\log V_T$ factors. Our result not only safeguards the worst-case guarantees but also directly implies the small-loss bounds in analysis. Moreover, when applied to adversarial/stochastic convex optimization and game theory problems, our result enhances the existing universal guarantees. Our approach is based on a multi-layer online ensemble framework incorporating novel ingredients, including a carefully designed optimism for unifying diverse function types and cascaded corrections for algorithmic stability. Notably, despite its multi-layer structure, our algorithm necessitates only one gradient query per round, making it favorable when the gradient evaluation is time-consuming. This is facilitated by a novel regret decomposition equipped with carefully designed surrogate losses.

Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach
Yu-Hu Yan, Peng Zhao, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China (yanyh, zhaop, zhouzh) @lamda. nww.njj.u..... edu.
Abstract
In this paper, we propose an online convex optimization approach with two dif- ferent levels of adaptivity. On higher level, our approach is agnostic to the un- known types and curvatures of the online functions, while at a lower level, can exploit the unknown niceness of the environments and attain problem-dependent guarantees. Specifically,
obtain Ollog VT), Oolo Vr) and ((VVT) regret bounds for strongly convex, exp-concave and convex loss functions, respectively, where d is the dimension, Vr denotes problem-dependen gradient variations and the Ö(-) (-))-notation omits log Vr factors. Our result not only safeguards the worst- case guarantees but also directly implies the small-loss bounds in analysis. More- over, when applied to adversarial//toccaasti convex optimization and game theory problems, our result enhances the existing universal guarantees. Our approach is based on multi-layer online ensemble framework incorporating novel ingredi- ents, including carefully designed optimism for unifying diverse function types and cascaded corrections for algorithmic stability. Notably, despite its multi-layer structure, our algorithm necessitates only one gradient query per round, making it favorable when the gradient evaluation is time-consuming. This is facilitated by a novel regret decomposition equipped with carefully designed surrogate losses.
Introduction
Online convex optimization (OCO) is a versatile model that depicts the interaction between a learner and the environments over time [Hazan, 2016, Orabona, 2019]. In each round [T], the leamer selects decision X, from convex compact set X C ı and simultancously the environments choose a convex loss function :' + Subsequently, the learner incurs loss fe(x;), obtains information about the online function, and updates the decision to X aiming to optimize the game-theoretical performance measure known as regret [Cesa- BianchiBacchii and Lugosi, 2006]:
T
T
REGT A Σ f((x))
min f((x), xEX
(1.1)
1=11
1=1
which represents the learner's s excess loss compared to the best fixed comparator in hindsight.
In OCO, the type and curvature of online functions significantly impact the minimax regret bounds. Specifically, for convex functions, online gradient descent (OGD) can achieve O(vT) regret guarantee [Zinkevich, 2003]. For n-exp-ccncave functions, online Newton step (ONS), with prior knowledge of the curvature coefficient a, attains Od 7') regret [Hazan et al., 2007]. For X-strongly convex functions, OGD with prior knowledge of the curvature coefficient and a dif- ferent parameter configuration enjoys Ollog T") regret [Hazan al., 2007]. Note that the above
"Correspondence: Peng Zhao <zhaop @ lamdanjj..ddu.cn>>
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison with existing results. The second column presents the regret bounds various kinds of functions, where Vr and Fr are problem-dependent quantities that are at most (TT) and can be much smaller nice environments. The ((-) (nn)noottioon omits logarithmic factors on Vr and Pr. The third column shows the gradient query complexity. All problem-dependent bounds require the smoothness of online functions.
Regret Bounds
Gradient Query
Works
Strongly Coavex
Exp-concave
Convex
van Erven and Koolen [2016]
Old I')
O(dlog T')
O(VT)
1
Wang et al. [2019]
Ollog T')
Oodlog T')
O(VT)
1
Zhang et ul. [2022a]
O(min (log Vy, log Pr))
Oldmmn Vr. log Fr))
OlvTFT)
Olog T)
Ours
O(min(log V4, log Pr)))
Old Vy, log Fr Olmin[y VVr, vTr)
1
algorithms require the function type and curvature beforehand and does not consider the niceness of environments. Recent studies further strengthen the algorithms and results with two levels of adap- rivity. The higher-level adaptivity requires an algorithm to be agnostic to the unknown types and curvatures of the online functions. And the lower-level adaptivity requires an algorithm to exploit the unknown niceness of the environments within a specific function family. In the following, we delve into an extensive discussion on these two levels of adaptivity.
1.1 High Level: Adaptive to Unknown Curvature of Online Functions
Traditionally, the learner needs to know the function type and curvature in advance to select suitable algorithms (and parameter configurations), which can be burdensome in practice. Universal online learning [van Erven and Koolen, 2016, Wang et al., 2019, Zhang et al., 2022a] aims to develop single algorithm agnostic to the specific funetion type and curvature while achieving the same regret guarantees as if they were known. The pioneering work of van Erven and Koolen [2016] proposed single algorithm called MetaGrad that achieves an ((VT) regret for convex functions and an Ol log T) regret for exp-coneave functions. Later, Wang et al. [2019] further obtained the optimal Olog 7') regret for strongly convex functions. Notably, these approaches are efficient regarding the gradient query complexity, by using only one gradient within each round.
However, the above approaches are not flexible enough since they have to optimize a group of heterogeneous and carefully-designed surrogate loss functions, which can be cumbersome and chal- lenging. To this end, Zhang et al. [2022a] introduced a simple framework that operates on the original online functions with the same optimal results at the expense of Olog T) gradient queries.
1.2 Low Level: Adaptive to Unknown Niceness of Online Environments
Within a specific function family, the algorithm's 's performance is also substantially influenced by the niceness of environments. This concept usually captured through problem-dependent quantities in the literature. Therefore, it becomes essential to develope adaptive algorithms with problem- dependent regret guarantees. Specifically, we consider the following problem-dependent quantities:
T
T
Fr min
Σ [((),, and VT A XEX
Σ sup [V 1=2 XEX
(x)
where the small loss Fr represents the cumulative loss of the best comparator [Srebro et al., 2010, Orabona et al., 2012] and the gradient variation Vy characterizes the variation of the function gradi- ents [Chiang et al., 2012]. In particular, the gradient variiatoo bound demonstrates its fundamental importance in modern online learning from the following three aspects: (i) it safeguards the worst- case guarantees in terms of and implies the small-loss bounds in analysis directly; (ii) draws a profound connection between adversarial and stochastic convex optimization; and (ii)) it is crucial for fast convergence rates in game theory. We will explain the three aspects detail in the next part.
1.3 Our Contributions and Techniques
In this paper, we consider the two levels of adaptivity simultancously and propose novel univer- sal approach that achieves Olog Vr), Od Vr) and ((VVT) regret bounds for strongly convex,

---

exp-coneave and convex loss functions, respectively, using only one gradient query per round, where (-))-ottation omits factors on log VT. Table I compares results with existing ones. In summary, relying on the basic idea of online ensemble [Zhao et al., 2021], our approach primarily admits a multi-layer online ensemble structure with several important novel ingredients. Specifically, we pro- pose a carefully designed optimism, a parammer encoding historical information, to handle different kinds of functions universally, particularly exp-concave functions. Nevertheless, it necessi- tates careful management of the stability of final decisions, which is complicated in the multi-layer structure. To this end, we analyze the negative stability terms in the algorithm and propose cascaded correction terms to realize effective collaboration among layers, thus enhancing the algorithmic stability. Moreover, we facilitate a novel regret decomposition equipped with carefully designed surrogate losses to achieve only one gradient query per round, making our algorithm as efficient as van Erven and Koolen [2016] regarding the gradient complexity. Our result resolves an open problem proposed by Zhang et al. [2022a], who have obtained partial results for exp-concave and strongly convex functions and asked whether
possible to design designing single algorithm with universal gradient-variation variation bounds. Among them, the convex case is particularly important because the improvement from T VT is polynomial, whereas logarithmic in the other cases.
Next, we shed light on some applications of our approach. First, it safeguards the worst-case guar- antees [van Erven and Koolen, 2016, Wang al., 2019] and directly implies the small-loss bounds of Zhang et al. [2022a] in analysis. Second, gradient variation is shown to play an essential role in the stochastically extended adversarial (SEA) model [Sachs al., 2022, Chen al., 2023b], an interpolation between stochastic and adversarial OCO. Our approach resolves a major open problem left in Chen et al. [2023b] on whether it is possible develop a single algorithm with universal guar- antees for strongly convex, exp-concave, and convex functions in the SEA model. Third, in game theory, gradient variation encodes the changes in other players' actions and can thus lead to fast convergence rates [Rakhlin and Sridharan, 2013b, Syrgkanis et al., 2015, Zhang et al., 2022b]. We demonstrate the universality of our approach by taking two-player zero-sum games as an example.
Technical Contributions. Our first contribution is proposing a multi-layer online ensemble ap- proach with effective collaboration among layers, which is achieved by carefully-designel op- timism to unify different kinds of functions and cascaded correction terms to improve the algo- rithmic stability within the multi-layer structure. The second contribution arises from efficiency. Although there are multiple layers, our algorithm only requires one gradient query per round, which achieved by a novel regret decomposition equipped with carefully designed surrogate losses. Two interesting byproducts rises in our approach. The first one is the negative stability term in the analysis of MsMwC [Chen et al., 2021], which serves as an important building block of our algorithm. And the second byproduct contains simple approach and analysis for the optimal worst-case universal guarantees, using one gradient query within each round.
The rest of the paper is structured as follows. Section 2 provides preliminaries. Sec- tion 3 proposes our multi-layer online ensemble approach for universal gradient-variation bounds. Section 4 further improves the gradient query complexity. Due to page limits, the applications of our proposed algorithm are deferred to Appendix A. All the proofs can be found in the appendices.
Organization.
2 Preliminaries
In this section, we introduce some preliminary knowledge, including our assumptions, the defini- tions, the formal problem setup, and review of the latest progress of Zhang et al. [2022a].
To begin with, we list some notations. Specifically, we use ||- for || Ila in default and use E., Σx- Σ; as abbreviations for Everyy ΣxE[K] and Eie[Ny- a S b represents S Ob). (-)-notation omits logarithmic factors on leading terms. For example, Ö(VV) omits the dependence of log V.
Assumption 1 (Boundedness). For any x, E X' and E [T). the domain diameter satisfies ||x yll < D, and the gradient norm of the online functions is bounded by [x)][ & G.
Assumption 2 (Smoothness). All online functions are L-smooth: [x(x)) Vi(yi) & L||x- yll for any x E X' and E [T].
Both assumptions are common in the literature. Specifically, the boundedness assumption is com- mon in OCO [Hazan, 2016]. The smoothness assumption is essential for first-order algorithms to
3

---

achieve gradient-variatee bounds [Chiang et al., 2012]. Strong convexity and exp- exp-concavity are de- fined as follows. For any x,y E X, a function f is A-strongly convex if f(x) - f(y) - (V (x)), (V)(x)xx-y)
y) 2 ||x yll and is o-exp-coneave f(x) - f() I that the formal definition of /-exp-concavitg states that exp(==ffe
Note is concave. Under Assump- tion 1. ---exp-concavity leads our definition with a = 1 min 1GD (8) [Hazan, 2016, Lemma 4.3].
(Vf(x), x x-y)
2 For simplicity, we use it as an alternative definition for exp-concavity.
In the following, formally describe the problem setup and briefly review the key insight of Zhang et al. [2022a]. Concretely, we consider the problem where the learner has no prior knowledge about the function type (strongly convex, exp-coneave, or convex) or the curvature coefficient (a or A). Without loss of generality. we study the case where the curvature coefficients a, À E [/rr, 1]. This requirement is natural because if a (or X) < 1/r, even the optimal regret is 52(2") [Hazan et al., 2007], which is vacuous. Conversely, functions with a (or X) > 1 are also 1-exp-concave (or 1- strongly convex). Thus using a (or À)
will only worsen the regret by a constant factor, which can be omitted. This condition is also used in previous works [Zhang et al., 2022a].
A Brief Review of Zhang et al. [2022a]. A general solution handle the uncertainty is leverage a two-layer framework, which consists of a group of base learners exploring the environments and a meta learner tracking the best base learner the fly. To handle the unknown curvature coefficients a and X, the authors discretize them into the following candidate pool:
H. {1/r, 4/rr,4/....... 1},
(2.1)
where [H| A log T. Consequently, they design three groups of base learners:
(i) about log T base learners, each of which runs the algorithm for strongly convex functions with guess X; E H of the strong convexity coefficient X;
(ii) about log I' base learners, each of which runs the algorithm for exp-concave functions with guess a; H of the exp-concavity coefficient o;;
(iii) 1 base learner that runs the algorithm for convex functions.
Overall, they maintain N = log T + log T + base learners. Denoting by P. - (Pr.1..... Pt,N)) the meta learner's 's weights and x1,, the i-th base learner's 's decision, the learner submits x, E, (X,,
In the two-layer framework, the regret (1.1) can be decomposed into two terms:
T
T [1(x)
REGT Σ (x(x)) Σ (xx.))))))
Σ (xxx)))) min XEX
(2.2)
where the meta regret (first term) assesses how well the algorithm tracks the best base learner, and the base regret (second term) measures the performance of The best base learner is the one which runs the algorithm matching the ground-truth function type with the most accurate guess of the curvature- - taking a-exp-concave functions as an example, there must exist a base learner indexed by i*, whose coefficient a;,, H satisfies ag. < 20;..
A direct benefit of the above dccomposition is that the meta regret can be bounded by a constant (L)) for exp-concave and strongly convex functions, allowing the algorithm to perfectly inherit the gradient-variatie bound from the base learner. Taking a-exp-concave functions as an exam- ple, by definition, the meta regret can be bounded by E,re,
2 E, r.... where the first term FE,S fe)x),,), X2 - X4,3) denotes the linearized regret, and the second one is a negative term from exp-concavity. Choosing ADAPT-ML-PROD [Gaillard et al., 2014] the meta algorithm bounds the first term E, Te.s- by O O(VE, )z), which can be canceled by the negative term, leading to an O()) meta regret. Due to the meta algorithm's benefits, their approach can inherit the gradient gradient-variation guarantees from the base learner. Similar derivation also applies to strongly convex functions. However, their approach is not favorable enough in the convex case and is not efficient enough in terms of the gradient query complexity. We will give more discussions about the above issues in Section 3.1 and Section 4.
3 Our Approach
This section presents our multi-layer online ensemble approach with universal gradient- cradient-variation bounds. Specifically, in Section 3.1, we provide novel optimism to unify different kinds of func- tions. In Section 3.2, we exploit two types of negative terms to cancel the positive term caused by
variation

---

the optimism design. We summarize the overall algorithm in Section 3.3. Finally, in Section 3.4, we present the main results and list several applications of our approach.
3.1 Universal Optimism Design
In this part, we propose novel optimism that simultaneously unifies various kinds of functions. We start by observing that Zhang et al. [2022a] does not enjoy gradient-variation bounds for convex functions, where the main challenge lies in obtaining while simultancously maintaining an (1) regret for exp-concave and strongly convex functions. In the following, focus on the meta regret because the base regret optimization is straightforward by employing the optimistic online learning technique [Rakhlin and Sridharan, 2013a.b] in a black- box fashion. Optimistic online learning is essential in our problem since it can utilize the historical information, e.g., V--((()) for our purpose due to the definition of the gradient variation.
(VVVT) meta regret for convex functions
Shifting our focus to the meta regret, we consider upper-bounding it by a second-order bound of O(V) O(VE,lre. -,,,))), where rt, (V fx()),,, X x1,)) and the optimism ma.s* can encode historical information. Such second-order bound can be easily obtained using existing prediction with expert advice algorithms, e.g.. ADAPT-ML--PROS
[Wei et al., 2016]. Nevertheless, we will demonstrate the following, designing an optimism m4, that effectively unifies various function types is not straightforward, thereby requiring novel ideas in the optimism design.
To begin with, a natural impulse is choose the optimism as mi, which yields the following second-order bound:
1), x.).
T Σ (rr.
Σ, | - X1,5-
(strongly convex)
Σ. [V(()))) V
(convex)
where the inequality is due to the boundedness assumption (Assumption 1). This optimism design handles the strongly convex functions well since the bound can be canceled by the negative term imported by strong convexity (i.e., -||x; - Xx,:- [|²). Moreover, it is quite promising for convex functions because the bound essentially consists of the desired gradient variation and positive term of ||x; - -x-1 (we will deal with it later). However, it fails for exp-concave functions because the negative term imported by exp-concavity (i.e.. f( cancellation due to the mismatch of the formulation.
xx,i )3) cannot be used for
To unify various kinds of functions,
propose a novel optimism design defined by m4,i 7t-1, This design aims secure second-order bound of O (,,
rt-1,:- )2), which sufficient to achieve an O(1) meta regret for exp-concave functions (with strong convexity being subcat- egory thereof) while maintaining an (vVrr) meta regret for convex functions. The high-level intuition behind this approach is follows: although the bound cannot be canceled exactly by the negative term imported by exp-concavity (i.e., -r(,z-) within each round, it becomes manageable when aggregated across the whole time horizon as (rr,, rt-1.5- )2 S 5. r,.,,, because rr,av and 1- differs by merely single time step. the following, we propose the key lemma of the universal optimism design and defer the proof to Appendix B.1.
Lemma (Key Lemma). Under Assumptions and 2, if the optimism is chosen as ma 1t-1,1 (V XI-1 Xt-1,;), it holds that
T
(X)((x),,,, - )2,
(exp-concave)
T
Σ (re. - ?
T [
Vr
|x X1-1.* 1|2
1111112.
(convex)
Moreover, the second part of Lemma shows that the bound for convex functions also controllable by being further decomposed into three terms. The first term is the desired gradient variation. The
2 "Although X; is unknown when using M.... we only need the scalar value of 1 x:). which can be efficiently solved via a fixed-point problem of (x (x)) = X; relies on since ma. relies on and relies m.,.. Interested readers refer to Section 3.3 of Wei et al. [2016] for details.
5

---

second one measures the base learner stability, which can be canceled by optimistic algorithms [Rakhlin and Sridharan, 2013a]. We provide a self-contained analysis of the stability of optimistic online mirror descent (OMD) in Appendix E.2. At last, if the stability term of the final decisions (i.e., ||x; - x,-1 can be canceled, an O( ((VVT) meta regret for convex functions is achievable.
To this end, we give the positive term ||x xz-1|1² a more detailed decomposition, due to the fact that the final decision is the weighted combination of base learners' decisions (i.e., X; E; i). A detailed proof is deferred to Lemma 6. Specifically, it holds that
N
xx 111 < Ip: Pt-
Pr.llxe, -x--,,,l?
(3.1)
where the first part represents the meta learner's stability while the second one is a weighted version of the base learners' stability. In Section 3.2, we cancel the two parts respectively.
3.2 Negative Terms for Cancellation
In this part, we propose negative terms to cancel the two parts of (3.1). Specifically, Section 3.2.1 analyzes the endogenous negative stability terms of the meta learner to handle the first part, and Sec- tion 3.2.2 proposes artificially-ineeteed cascaded corrections to cancel the second part exogenously.
3.2.1 Endogenous Negativity: Stability Analysis of Meta Algorithms
In this part, we aim to control the meta learner's stability, measured by ||p, - PP-i l.. To this end, we leverage the two-layer meta algorithm proposed by Chen et al. [2021], where each layer runs the MsMWC algorithm [Chen et al., 2021] but with different parameter configurations. Specifically, single MsMWC updates via the following rule:
Pt = arg min (/m;, p) + Do, p()) P+t1 = arg min {le + at, at.p) + D's, p.), (3.2)
PEAx
pEdr
where Aa denotes d-dimensional simplex, (p) = Ei 1/ -1 Inp; is the weighted negative entropy regularizer with mame-coordinatevaryyinn step size ne Dv, (p.q) (p) (q) (V)(()). q) is the induced Bregman divergence for any p.q q E Ad. m, is the optimism, & the loss vector and a, is a bias term.
It is worth noting that MsMwC based on OMD, which is well-studied and proved to enjoy nega- tive stability terms in analysis. However, the authors omitted them, which turns out to be crucial for our purpose. In Lemma below, we extend Lemma I of Chen et al. [2021] by explicitly exhibiting the negative terms in MsMwC. The proof is deferred to Appendix B.2.
Lemma 2. If max,a([] fle,. mm S 1, then MsMwC (3.2) with time-invariant step sizes (i.e., ne,s = 7) for any t E [T] enjoys the following guarantee if n $ 1/32
T
T
Σ (..) - Σ [=1
S
1
In
1
8
MPPi,lkes - m,,))
P1
1=1
i=1
(=1
+1613
(4.s m4
Pt - Ph--Pi-lli 111
The two-layer meta algorithm is constructed by MsMwC in the following way. Briefly, both layers run MsMWC, but with different parameter configurations. Specifically, the top MsMWC (indicated by MsMwC- (OP) connects with K O(log 7') MsMWCs (indicated by MsMWC-MID), and each MsMWC-MID' is further connected with N base learners (as specified in Section 2). The spe- cific parameter configurations will be illuminated later. The two-layer meta algorithm is provable to enjoy a regret guarantee of (VVV, In V.) (Theorem 5 of Chen et al. [2021]), where V, is analogous to Ee m ) but within multi- layer context (a formal definition will be shown later). By choosing the optimism as m4, (Ls, p.).", it can recover the guarantee of ADAPT-ML-PROD,
We only focus the proof with fixed learning rate, since it is sufficient for analysis. 4 "Although p. is unknown when using my, due to (3.2), m,, = (Lr.p.) remains the same for all dimension i E id] and can thus omitted in the algorithm, i.e., it only suffices to update as p: arg p a, Da, (p. P.). Interested readers refer to Section 2.1 of Chen al. [2021] for more details.

---

Table Notations of three-layer structure. The first column presents index of layers. The rest columns illuminate the notations for the algorithms, losses, optimisms, decisions and outputs of each layer.
Layer
Algorithm
Loss
Optimism
Decision
Output
Top (Meta)
MsMwC
&,
4: E
AK
E ALANKL
Middle (Meta)
MsMwC
4
m
Pik E AN
N
Σ Pr...
Bottom (Base)
Optimistic OMD
fa())
Vi--(()
Nt.b3
although up to an (In V.) factor (leading to an ((VVT) meta regret), but with additional negative terms in analysis. Note that single MsMwC enjoys an O( In T') bound, where the extra In T factor would ruin the desired (log Vr) bound for exp-concave and strongly convex functions. This is the reason for choosing second-layer meta algorithm, overall resulting in three-layer structure.
For clarity, we summarize the notations of the three-layer structure in Table Besides, previous notions need to be extended analogously. Specifically, instead of (2.2), regret is now decomposed as
T
REGT Σ si()))
Σ (x(x)ao..)) 1=1
Σ Se (x(
min XEA
f((x)
The quantity V, is defined as V. & Mi,Ki (Vf((x,),,)
-T, )2, where be, - (V (xx),, Xt, and ( - follows the same sprit as Lemma 1.
At the end of this part, we explain why we choose MsMwC as the meta algorithm. Apparently, direct try is to keep using ADAPT-ML-PRON following Zhang et al. [2022a]. However, it is still an open problem to determine whether ADAPT-MI- PROD contains negative stability terms in the analysis, which is essential to realize effective cancellation in our problem. Another try is to explore the titled exponentially weighted average (TEWA) as the meta algorithm, following another line of research [van Erven and Koolen, 2016], introduced in Section 1.I. Unfortunately, its stability property is also unclear. Investigating the negative stability terms in these algorithms is an important open problem, but beyond the scope of this work.
3.2.2 Exogenous Negativity: Caseaded Correction Terms
In this part, we aim to deal with the second term in (3.1) (i.e., >, Ptoll xx-1, 13). Inspired by the work of Zhao et al. [2021] on the vradient-variation dynamic regret in non-stationary online learning. 5 we incorporate exogenous correction terms for cancellation. Concretely, we inject cas- caded correction terms to both top and middle layers. Specifically, the loss e, and the optimism m. of MsMMC- M-MM TOP are chosen as
ke A (xx), xx,N) + AiI|x X, m A (mi,k k Pr.A) + A A 1.-1. (3.3)
The loss Le and optimism mI,E of MSMWC-MID are chosen similarly
lek (X)) x(.k,) A 1.. ? me,k, A mi.k. d Xell XX 11 (3.4)
x,) x,) denotes optimism, which uses the same idea Lemma in Section 3.1.
where Mi,k (M..k.1...... M.,..N) and m = f.,x)
-x, x,-1 X1 11
To see how the correction term works, consider a simpler problem with regret Σn (Ct, zt) -E, le. If we instead optimize the corrected loss l, + b. and obtain a regret bound of lr, then moving the correction terms to the right-hand side, the original regret is at most R E; Ex be. be, algorithm is required to handle an extra term of E, bt, which only relies on the -- dimension. In the next part, we will discuss about how cascaded corrections and negative stability terms of meta algorithms realize effective collaboration for cancellation in the multi-layer online ensemble.
where the negative term of Σ. Ex br, & can be leveraged for cancellation. Meanwhile, the
It is noteworthy that our work is the first to introduce correction mechanisms to universal online learning, whereas prior works use it for different purposes, such as non-stationary online learn-
*This work proposes an improved dynamic regret minimization algorithm compared to its conference ver- sion [Zhao et al., 2020), which introduces the correction terms to the meta-base online ensemble structure and thus improves the gradient query complexity from Olog 7') I within each round.
7

---

Algorithm Universal OCO with Gradient-variation Guarantees
Input: Curvature coefficient pool H. MSMWC-MID number K, base learner number N
1: Initialize: Top layer: A - MMM with 77 = (Co 2 and i1 = n Σ k=1 1/2
Middle layer: {-ARid [RE[K] MSMWC-MID with step size 21/je and PI,A. = I/N
Bottom layer:
base learners as specified in Section 2
2: for /. 1 to 7 do
3: Receive X from B obtain X E; Kr, and submit x, = >x At,AK
4: Suffer (x{) and observe the gradient information fc(-)
5: Construct m,;) (3.3) for A and (L,,, m,,x) (3.4) for A
6: AeoP updates to 4r+11 and A updates to Pt+1.k
7:
Multi-gradient feedback model:
8: Send gradient V (-)
(+) to BR.5 ; for update
Ollog gradient queries
9:
One-gradient feedback model:
Construct surrogates (-),()), (,,"()), (x) using only fx(x))
11: Send the surrogate functions to BR for update
D Only one gradient query
12:
end for
ing [Zhao et al., 2021] and the multi-scale expert problem [Chen et al., 2021]. Distinctively, dif- ferent from the conventional two-layer algorithmic frameworks seen in prior studies, deploying this technique to a three-layer structure necessitates a comprehensive use and extensive adaptation of it.
3.3 Overall Algorithm: A Multi-layer Online Ensemble Structure
In this part, we conclude our three-layer online ensemble approach in Algorithm 1. In Line 3, the decisions are aggregated from bottom to top for the final output. In Line 4, the learner suffers the loss of the decision, and the environments return the gradient information of the loss function. In Line 5, the algorithm constructs the surrogate losses and optimisms for the two-layer meta learner. In Line 6- 11, the update is conducted from top to bottom. Note that in Line 8, our algorithm requires multiple, concretely (log" T), gradient queries per round since it needs to query V (x(,,, for each base leamner, making it inefficient when the gradient evaluation is costly. To this end, in Section 4, we improve the algorithm's 's gradient query complexity to per round, corresponding to Line 10-11, via novel regret decomposition and carefully designed surrogate loss functions.
In Figure 1, we illustrate the detailed procedure of the collaboration in our multi-layes online en- semble approach. Specifically. we aim to deal with the positive term of ||x, xx-1ll which stems from the universal optimism design proposed in Section 3.1. Since x; = Σx (t. the posi- tive term can be further decomposed into two parts: l/q. q:- ll and Σx gr || 1, which can be canceled by the negative and correction terms in MsMwC-TOP respectively. Note that the correction comes the expense of an extra term of || X1-1,6-11 11?, which can be decomposed similarly into two parts: ||pt... 1, |l and Σ, ,|xx,= x, be- cause of Xr,A = E, P...k.. The negative term and corrections in the middle layer (specifi- cally, the k-- -th MsMWC-MID can be leveraged for cancellation. This correction finally generate ||x 1-2-1.-.:4 112, which can be handled by choosing optimistic OMD as base algorithms.
As final remark, although it is possible to treat the two-layer meta algorithm as single layer, its analysis will become much more complicated than that in one layer and is unsuitable for extending to more layers. In contrast, our syyer-by-laye analytical approach paves systematic and principled way for analyzing the dynamics of the online ensemble framework with even more layers.
3.4 Universal Regret Guarantees
In this part, we conclude our main theoretical result and provide several implications and appli- cations to validate its importance and practical potential. Theorem 1 summarizes the main result, universal regret guarantees terms of the gradient variation. The proof is deferred to Appendix B.4.
Theorem 1. Under Assumptions and 2, Algorithm I obtains Ollog VT), Old Vr) and (VVT)) regret bounds for strongly convex, exp-concave and convex functions, respectively.
8

---

Positive Term:
||x, x1-
Yt.k |x4, xx-1,x1 + +d1l
Xx-1.6
Top Layer
canoeled by MsMWC-TOP
canceled by- -E ge,00e.
PL.k- P IR
Pa xll.xlll x ael?
Middle Layer
cunceled by M.IWC.MID
canceled by 2 Pe.c Bee
+ A2 1x
Bottom Layer
Decomposition of the positive term |xx, ensemble via endogenous negativity from meta algorithm exogenous negativity from cascaded corrections.
Figure 1:
x and how it handled by the multi-layer online
Theorem improves the results of Zhang et al. [2022a] by not only maintaining the optimal rates for strongly convex and exp- cop-cce functions but also taking advantage of the small gradient variation for convex functions when VT < Fr. For example, if fi = ... = fr f and min f(x 1, our bound is much better since Vr O while Fr T. Moreover, Algorithm 1 also provably achieves universal small-loss guarantees without any algorithmic modification and thus safeguards the case when Fr Vr. We conclude the result below and provide the proof in Appendix B.5.
Corollary 1. Under Assumptions I and 2, if fe(-) Algorithm obtains Olog Fr), Old Fr) and Ō ((FF)) regret bounds for strongly convex, exp- cep-concave and convex functions.
Due to the connection of the gradient-variation with stochastic and adversarial OCO [Sachs et al., 2022] and game theory [Syrgkanis et al., 2015], our results can be immediately applied and achieve best known universal guarantees therein. Due to page limits, we defer applications to Appendix A.
4 Improved Gradient Query Complexity
Though achieving favorable theoretical guarantees in Section 3, one caveat is that our algorithm requires (log T)) gradient queries per round since it needs to query fi for all & e [K], i making it commputatioallinnfffiiii optimization [Ji and Ye, 2009] and mini-batch optimization [Li et al., 2014]. The same concern also appears in the approach of Zhang et al. [2022a], who provided small-loss and worst-case regret guarantees for universal online learning. By contrast, traditional algorithms such as OGD typically work under the one one-grate rre-grddient feedback setup, namely, they only require one gradient V fx for the update. light of this, natural ask whether there universal algorithm that can maintain the desired regret guarantees while using only one gradient query per round.
when the gradient evaluation is costly. e.g., in nuclear norm
We answer the question affirmatively by reducing the gradient query complexity 1 per round. To describe the high-level idea, we first consider the case of known X-strong convexity within two-layer structure, c.g., adaptive regret minimization for strongly convex functions [Wang et al., 2018]. The regret can be upper-bounded as REGT S IE, h (x())) - E, (x( i E, hr (x(x Σ, (x*)),, where x" E arg min E. fx() and (x) & (x)( A|x x2113/2 /2 is second-order surrogate of the original function ft. This yields a homogeneous surrogate for both meta and base algorithms the meta algorithm uses the same evaluation function across all the base learners, who in turn use this function to update their base-level decisions.
In the universal online learning (i.e., wnknown A), a natural adaptation would be a heterogeneous surrogate hx,(()) ( + A; x X2 //2 for the i-th base learner, where A; is a guess of the true curvature À from the candidate pool H (2.1). Consequently, the regret decomposition with respect to this surrogate becomes REGT < |E, (x,x E, /r.5 (x,, )] + [Σ, hr, (x+..))
E, he (xx.s((x))) (x*)), where denotes the index of the best base learner whose strong convexity coefficient satisfies X₁- 5 À < 2A This admits heterogeneous surrogates for both meta and base regret, which

---

necessitates designing expert- expert-tracking tracking algorithms with heterogeneous inputs for different experts as required in MetaGrad [van Erven and Koolen, 2016], which is not flexible enough.
To this end, we propose a novel regret decomposition that admits homogeneous surrogates for the meta regret, making our algorithm as flexible as Zhang et al. [2022a], and heterogeneous surrogate for the base regret, making it as efficient as van Erven and Koolen [2016]. Specifically, we remain the heterogeneous surrogates he,a(x) defined above for the base regret. For the meta regret, we define a homogeneous linear surrogate & (x) - [1 (x(x))), x) such that the meta regret is bounded by (xx,) - Σ, (xx,.x) - A Σ: X xt, /2. As long as we can obtain a second-order bound for the regret defined on this surrogate loss, i.c., Ee f((x;) - -E, ((xx,x)) ). can be canceled by the negative term from strong convexity. Overall, we decompose the regret in the following way:
T
REGT & Σ (xxx)) - Σ (xx,,))
A
X1
xx,x
+ Σ ha (x1.2)
-Eh (x,tx(x*)) (xe))
2
1=1
1=1
t=1
For clarity, we denote this surrogate for strongly convex functions by (x). Similarly, we define the surrogates (x) & (V.((xx)), x) + a. (xxxx x,)²/2 and (x) & (V)((x)). x))
for a-exp-concave and convex functions, respectively. These surrogates require only one gradient
(x,) within each round. thus successfully reducing the gradient query complexity.
Note that the base regret optimization requires controlling the algorithmic stability, because the em- pirical gradient variation Vhū,, (xx,s) V ( (x,) = [x, + +A, -x,
(x, x)-1) not only contains the desired gradient variation, but also includes the positive sta- bility terms of base and final decisions. Fortunately, as discussed earlier, these stability terms can be effectively addressed through our cancellation mechanism within the multi-layer online ensemble. This stands in contrast to previous two-layer algorithms with worst-case regret bounds [Zhang al., 2018, Wang et al., 201 8), where the algorithmic stability is not examined.
The efficient version is concluded in Algorithm 1 with Line 10-11, 11, which uses only gradient (x()). The only algorithmic modification is that base learners update on the carefully designed surrogate functions, not the original one. We provide the regret guarantee below, which achieves the same guarantees as Theorem with only one gradient per round. The proof is in Appendix C.2.
Theorem 2. Under Assumptions I and 2, efficient Algorithm I enjoys Olog Vr), O(d Vr) and Ö(VV)) for strongly convex, exp-concave and convex functions, using only one gradient per round.
As a byproduct, we show that this idea can be used recover the optimal worst-case universal guarantees using one gradient with a simpler approach and analysis, with proof in Appendix C.I. Proposition 1. Under Assumption I, using the above surrogate loss functions for base learners, and running
as the meta learner guarantees Olog T), Od T) and O regret bounds for strongly convex, exp-concave and convex functions, using one gradient per round.
Conclusion
In this paper, we obtain universal variiant-vaiationn guarantees via a multi-layer online ensemble approach. We first propose novel optimism design to unify various kinds of functions. Then we analyze the negative terms of the meta algorithm MsMWC and inject cascaded correction terms to improve the algorithmic stability to realize effective cancellations in the multi-layer structure. Furthermore, we provide novel regret decomposition combined with carefully designed surrogate functions to achieve one gradient query per round. Finally, we deploy the our approach into two applications, including the stochastically extended adversarial (SEA) model and two-player zero- sum games, to validate its effectiveness, and obtain best known universal guarantees therein. Due to page limits, the applications are deferred to Appendix A. Two byproducts rise in work. The first one is negative stability terms in the analysis of MsMwC. And the second one contains a simple approach and analysis for the optimal worst-case universal guarantees, using one gradient per round.
An important open problem lies in optimality and efficiency. In the convex case, our results still exhibit an (log Vr) gap from the optimal (( result. Moreover, our algorithm necessitates Olog² 2 ') base learners, as opposed to (log T') base learners in two-layer structures. Whether it possible to achieve the optimal results for all kinds of functions (strongly convex, exp-concave, convex) using a two-layer algorithm remains as an important problem for future investigation.
10

---

Acknowledgements
This research was supported by National Key R&D Program of China 00022200144000 NSFC (62206125, 61921006), and JiangsuSF (BK20220776). The authors would thank Reviewer #ZhYs of OpenReview for the thorough review and insightful suggestions.
References
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. 2006.
Cambridge University Press,
L. Chen, Luo, and C. Wei. Impossible tuning made possible: new expert algorithm and its applications. In Proceedings of the 34th Annual Conference Computational Learning Theory (COLT), pages 1216-1259, 2021.
S. Chen, W.-W. Tu, P. 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, 2023a.
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. ArXiv preprint, arXiv:2302.04552, 2023b.
C. Chiang, T. Yang, C. Lee, M. Mahdavi, C. Lu, R. Jin, and S. Zhu. Online optimization with grad- ual variations. In Proceedings of the 25th Annual Conference Computational Learning Theory (COLT), pages 6. 6.126. 2012.
Gaillard, G. Stoltz, and T. Erven. second-order bound with excess losses. In Proceedings of the 27th Annual Conference Computational Learning Theory (COLT), pages 176-196, 2014.
E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
E. Hazan, Agarwal, and Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-192 2007.
S. Ji and J. Yc. An accelerated gradient method for trace norm minimization. In Proceedings of the 26th International Conference on Machine Learning (ICML), pages 457-464, 2009.
M. Li, T. Zhang, Y. Chen, and A. Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 661-670, 2014.
Orabona, A modern introduction to online learning. ArXiv preprint, arXiv: 2019.
Orabona, N. Cesa-Bianchi, and Gentile, Beyond logarithmic bounds in online learning. Pro- ceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 823 831, 2012.
M. S. Pinsker. Information and information stability of random variables and processes. Holden- Day, 1964.
R. Pogodin and T. Lattimore. On first-order bounds, variance and gap-dependent bounds for adver- sarial bandits. In Proceedings of the 35th Conference on Uncertainty in Artifificial Intelligence (UAI), pages 894-904, 2019.
2019.
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference Computational Learning Theory (COLT), pages 993-1019, 2013a.
A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems 26 (NIPS), pages 3066-3074, 2013b.
S. Sachs, H. Hadiji, T. van Erven, and C. Guzmán. Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness. Advances 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 adver- sarial online convex optimization. ArXiv preprint, arXiv:2303.03272, 2023.
N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems 23 (NIPS), pages 2199-2207, 2010.
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 2989-2997, 2015.
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. D. Zhao, and L. Zhang. Minimizing adaptive regret with one gradient per iteration. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) pages 176622768,, 2018.
G. Wang, S. Lu, and L. Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI), pages 659-668, 2019. 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.
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.
Zhang, G. Wang, J. Yi, and T. Yang. A simple yet universal strategy for online convex optimiza- tion. 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, 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.-J. Zhang, Zhang, and Z.-H. Zhou. Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. ArXiv preprint, arXiv:2112.14368, 2021.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Pro- ceedings of the 20th International Conference Machine Learning (ICML), pages 928-936. 2003.
12

---

A Applications
In this section, validate the importance and the practical potential of our approach by applying it in two problems, including stochastically extended adversarial (SEA) model in Appendix A.I and two-player zero-sum games in Appendix A.2.
A.1 Application I: Stochastically Extended Adversarial Model
Stochastically extended adversarial (SEA) model [Sachs et al., 2022] serves as an interpolation between stochastic and adversarial online convex optimization, where the environments choose the loss function ft from a distribution Dr (i.c., ft ~ Dz). They proposed cumulative stochastic variance T... the gap between ft and its expected version F+(-) - ES,-D, [fe(-)] and cumulative adversarial variation Li.r. the gap between F.(.) and Fr-1 to bound the expected regret. Formally,
T
2 J:T
max D. [lV - - Ei. XEX
E
Σ
sup [V((xx [=2 XEX
By specializing different ar. and Eg.T. the SEA model can recover the adversarial and stochastic OCO setup, respectively. Specifically, setting o..r recovers the adversarial setup, where Σ equals to the gradient variation Vr. Besides, choosing 21.r 0 recovers the stochastic setup, where d.r stands for the variance in stochastic optimization.
For smooth expected function F+(.), Sachs et al. [2022] obtained an optimal @(V + Eirr) _ expected regret for convex functions and O( max + Σ ) log T) regret for strongly vex functions, where max - max maxxex H [IIV
(x) [2]] and X A [ supxex [//((x) VF-- Later, the results are improved by Chen al. [2023b], where the authors achieved better O((o max Σ2 max) log(of-r Eirr) regret for strongly convex functions and new O log(of:r + Ei.r) regret for exp-concave functions, while maintaining the optimal guarantee for convex functions. Their key observation is that the gradient variation in opti- mistic algorithms encodes the information of the cumulative stochastic variance o.r and cumulative adversarial variation Di.,. restated Lemma 5.
A major open problem remains in the work of Chen et al. [2023b] that whether it is possible to get rid of different parameter configurations and obtain universal guarantees in the problem. In the following, we show that our approach can be directly applied and achieves almost the same guarantees as those Chen al. [2023b], up to a logarithmic factor in leading term. Notably, our algorithm does not require different parameter setups, thus resolving the open problem proposed by the authors. We conclude our results Theorem and the proof can be found in Appendix D.I.
Theorem 3. Under the same assumptions as Chen et al. [2023b], the efficient version of Algorithm I obtuins O( + Emaxx log(oī.r + r) regret for strongly convex functions, (ld log(o"rr + Ei,r) regret for exp-concave functions and Ö(VoT.r + Ei.r) regret for convex functions, where the (-))nnotaioon omits logarithmic factors in leading terms.
Note that Sachs et al. [2023] also considered the problem of universal learning and obtained an O (ogg) regret for convex functions and an O + >d + strongly convex functions simultancously. We conclude the existing results in Table 3. Our results are better than theirs in two aspects: (i) for strongly convex and convex functions, our guarantees adaptive with the problem-dependent quantities 01:7 and ΣrE while theirs depends the time horizon T; and (ii) our algorithm achieves an additional guarantee for exp-concave functions.
L²) log T) regret for
A.2 Application II: Two-player Zero-sum Games
Multi player online games [Cesa-Binne Bianchi and Lugosi, 2006] is a versatile model that depicts the interaction of multiple players over time. Since each player facing similar players like herself, the theoretical guarantees, e.g., the summation of all players' regret, can be better than the minimax optimal VT bound in adversarial environments, thus achieving fast rates.
'This bound improves the result of O(min log(oî.r + Mi.r), (o + ) log (') in their confer- ence version [Chen al., 2023a].
13

---

Table 3: Comparisons of our results with existing ones. The second column presents the regret bounds for various kinds of loss functions, where oं. and rf are the cumulative stochastic variance and adversarial variation, which are at most (I)) and can be much smaller in benign environments. The Ö nnottttnn omits logarithmic factors on leading terms. The third column indicates whether the results for different kinds of functions are achieved by single algorithm.
Regret Bounds
Single
Works
Algorithm?
Strongly Convex
Exp-con Exp-concave
Convex
Sachs et al. [2022]
((( + ( log T)
X
Olvo,, + (ir))
No
Chen et al. [2023b]
O((o moxe E loglo T Mir)
Oldlog(oir E Olvotr + Eirr)
No
Sachs et al. [2023]
(( + E D2 log"
x
Õ(VT)
Yes
Ours
Offomuce + Ea log(os r Mirr) Oldlog(ofr Mir) Ōlvo9, 22,
Yes
Table 4: Comparisons of our results with existing ones. In the honest case, the results are measured by the summation all players' regret and the dishonest case, the results are terms of the individual regret of each player. Bilinear and strongly convex-concave games are considered inside each case. denotes the best result in each case (row).
Games
Syrgkamis et al. [2015]
Zhang al. [2022a]
Ours
bilinear
O(1)
O(VT)
O(1)
Honest
strongly conex-concave
0(1) *
O(logT)
0(1)
bilinear
((vT) *
((VT)
Ø(vT) *
Dishonest
strongly convex-concave
O(vT)
O(logT)
Oloo T')
The pioneering works of Rakhlin and Sridharan [2013b], Syrgkanis et al. [2015] investigated op- timistic algorithms in multi-player online games and illuminated the importance of the gradient variation. Specifically, Syrgkanis et al. [2015] proved that when each player runs an optimistic al- gorithm (optimistic OMD or optimistic follow the regularized leader), the summation of the regret, which serves as an upper bound for some performance measures in games, can be bounded by O(). The above results assume that the players are honest, i.c., they agree to run the same algorithm dis- tributedly. In the dishonest case, where there exist players who do not follow the agreed protocol, the guarantees will degenerate to the minimax result of (VTT).
In this part, we consider the simple two-player zero-sum games as example to validate the ef- fectiveness of our proposed algorithm. The game can be formulated as min-max optimization problem of minxex maxyey y). We consider the case that the game is either bilinear (i.e., yx. x Ay), or strongly convex-concave (i.e., f(x,y) is X-strongly convex in x and X- strongly concave in y). Our algorithm can guarantee the regret summation in the honest case and the individual regret of each player in the dishonest case, without knowing the type of games in advance. We conclude our results in Theorem 4, and the proof can be found in Appendix D.2.
Theorem 4. Under Assumptions I and 2, for bilinear and strongly comvex-concvee games, the effi- cient version of Algorithm enjoys (1) regret summation in the honest case, ((VT) and Oloo T) bounds in the dishonest case, where the O())-ootation omits logarithmic factors in leading terms.
Table 4 compares our approach with Syrgkanis et al. [2015], Zhang et al. [2022a]. Specifically, ours better than Syrgkamis al. [2015] the strongly convex-concane games in the dishonest case due to its universality, and better than Zhang et al. [2022a] in the honest case since our approach enjoys gradient-variation bounds that are essential in achieving fast rates for regret summation.
B Proofs for Section 3
In this section, we provide proofs for Section 3, including Lemma 1, Lemma 2 and Lemma 3. For simplicity, we introduce the following notations denoting the stability of the final and intermediate decisions of the algorithm. Specifically, for any ie E [K], i E [NV. we define
T
T
T Σ
SX
Xt Xx -1 113, ST
Xxt - Xx- 1.-1 ST.K
||x,,,s - Xt- X.
t=2
14

---

T S
T
_
|1 q:-1lli and SP &
Σ
pr, - 11
(B.1)
t=2
B.1 Proof of Lemma!
Proof. For simplicity, define g:
- (x(xx)). For exp-concave functions, have
mr me,;-)² Σ
(g, X x1,i,)
(g--1. Xt-1 x(-1,5-))
T
T
gi; X -x,,5-) +
1, xt-1 xx-1,10)²
t=1
Br. X1 - -xx,,)3
For convex function, it holds that
T
Σ (ra - m4
E(8
(8), - -x,,0) - 11- xx-1,;)))²
-
1=1
T
S 2
(g 1, x +2
1 Xx-1 X1,3" x(-1,
t=1
t=1
< 2D
|gr 11-1 +
|x X +x,, x 1
(by Assumption 1)
T
< 4D'V++ G2)
Σ | - xt-
112 -
4G²
Σ
Xt. - X,-
where the last step is due to the definition of the gradient variation, finishing the proof.
B.2 Proof of Lemma
In this part, we analyze the negative stability terms in the MsMwC algorithm [Chen et al., 2021]. For cofffcontannedsess, we restate the update rule of MsMWC in the following:
Pt arg min {(m,. p) + De (p, p.)) P++1
mrg ((le + a,, p) + (p.
PEAr
PEAx
where the bias term a, = 16,, m Below, we give detailed proof of Lemma 2, fol- lowing a similar logic flow Lemma of Chen al. [2021], while illustrating the negative stability terms. Moreover, for generality. we investigate more general setting of an arbitrary comparator E A, and changing step sizes Vt... This was done hoping that the negative stability term analysis would be comprehensive enough for readers interested solely in the MsMwC algorithm.
Proof of Lemma 2. To begin with, the regret with correction can be analyzed as follows:
T
T
T
(2. a., P: - e,,) < 1=1
(Dos. u/ (u. p.) -aas (u, Pc+1)) +
Σ
(ee + m.. - p.+1)
t=1
(Do,
(p141, (p.
p.) + Des (P))
1
<
DD, u. Pi) Duv (u, Pr41))
(ee + a: m-.m Pt p.1) 2
Dys (Per1.P))
TERM (A)
TERM (B)
15

---

T
(Do (Pet1, Pe) + (pr, P.)),
TERM (C)
where the first step follows the standard analysis of optimistic OMD, e.g., Theorem of Zhao et al. [2021]. One difference of our analysis from the previous one lies in the second step, where previous work dropped the Dv. (P:: Pr) term while we keep it to generate the desired negative terms.
To begin with, we require upper bound of ne, S 1/32 for the step sizes. To give lower bound for TERM (C), we notice that for any a. b Ad.
(a, =
1
ai In
a; bi
aj + bi
=
T
bi
ai
b;
In
b;
aj
ai b
+
i=1
d
min
0;
In
a; + bi 2 (2 b),
(by Me, S 1/32)
n
bj
where the first incquality is due to z lnx
0 for all x > 0, leading to
32
TERM (c) 2 32
KL (f Po) + KL(P,,
(1p--1 ppeli + ||p. -pelli)
2
T
2 16
Σ 1=2
(1 - P-- +1p: - p.1l3)
Pr - PP--P--11 1111
1=2
where the first step is from the above derivation, the second step due to the Pinsker's inequal- ity [Pinsker, 1964]: KL b) 2 21n2 aa - bll for any a, b E Ad and the last step is true because of 2x + 2y²² 2 (z + y)² for any x, y E and ||a + bll |al + ||b]] for any a, Rdd
For TERM (B). the proof similar to the previous work, where only some constants are modified. For celf-containedness, we give the analysis below. Treating p:+1 as a free variable and defining
pd arg max (ee + a, m. Pt: - p) Dv. (p.Pr).
p
by the optimality of p", we have
l, a m (Vei(p)) - (p)((")).
1
Since [Vba(p)) =
1 (In p: + 1), it holds that
1
Pesi
4,--m4 me, at,i
In
pt Pc.: exp((22).. - me + ac,)))
21/,
pt
Therefore we have
1
1 2 Do. (p', ,.)
(e, a. m.. -p+1)
- Dr, (p.11, S (ee + a: -mm (t.pp--)) p²)
2
= 1 Dvs (pt.p")
(Vee(p))
Vih( - -p") D Dw,(p' (p',p.))
,P:)= 2
(by definition)
2
1
Pt,s In Pt.i
Pt, p.
p.¹
Pt.i 127,,,lss - m4,5 + ar,s) - 1 +
- m,,i + a,))))
2
ne.i
Pt. An2, (Re,s - M4,5 + + = Σ
M.P... m4,i + ar,))²
ne.i
1
i=1
16

---

where the first and second steps use the optimality of p", the last inequality uses e 1 x S x²
for all x 2 -1, requiring [20), m4,; + ar,i)l S 1. It can be satisfied by Te - 1/32 and 11,, me, + or,il - 16, where the latter requirement can be satisfied by setting ae 16 m,,
14,; - ,,, + anil 2
32 (2 + +mm s 4 16.
As result, we have
(4,, ma,i + ax,5)² 22 (le, mass + 16m,, - m),s))²² & 4(le,t m².)² where the last step holds because (k,, |ma,s I and Th, S 1/32. Finally, holds that
TERM (B) 2 N..Pi, may aq,)) ? $
MrPP,,lles m,,))
As for TERM (A), following the same argument as Lemma of Chen et al. [2021], we have
d
T
d
TERM (A) S
Σ
Jka. (us, PI.s) +
fKL. (us. Pe,),
11.1
Tt. 77-1,5
i=1
where fai 6) 2 a al((a//) - a + b. Combining all three terms, we have
d
T d
Σ (1 + a.. - -) 5
71,1
11is5
1=2 i=1
T
T
+
8
nt.P,, m,,;)
1
1111
t=1
1=1
1=2
Moving the correction term
Σ
(at, Pt
u) to the right-hand side gives:
d Σ ll. Pt u))
Σ
(1;
fkc Pe.))
n.
==1
1=2 i=1
d
Σ M.sPi, - mr,)) 2 Σ
2e (le,i- - (4,))
Pp: Pr- 11:
Finally, choosing ex and ne, = for all t E [T] finishes the proof.
B.3 Proof of Lemma 3
In this part, give self-contained analysis of the two-layer meta learner, which mainly follows the Theorem 4 and Theorem 5 of Chen et al. [2021], but with additional negative stability terms. Lemma 3. If 1e, (m, Keaaal |ma S 1 and (le, - m2,x) (Le, my,ks P., for any k E [K] and i E [N), then the two-layer MsMWC algorithm satisfies
T
T
N
Co
Co
Σ (le q: - -ex)) + (le, Cl. PL.k - e,,) S
1)k
3
2
32 V.
2
S
4
sp
T.k.
where V, & Eolle P. & -
11q. q and T. DT Ilr 1.
measure the stability of MsMwC-TOP and MSMWC-MID.
Note that leverage a condition of (Le, )2, (Le, myA P.. in Lemma 3 only to ensure a self-contained result. When using Lemma (more specifically, in Theorem 2), we will verify that this condition is inherently satisfied by our algorithm.
Proof. Using Lemma 2, the regret of MsMWC-TOP can be bounded as
(ee q: cx+) 5 (
K
In
91.k
+ 0
1677
Σ mz,x) min
sq
7k
-1.k
77s
kE[K] 47p.
k=
17

---

where the first step comes from fKL(a, b) = a 1/6 a a b I a %/6 + b for a, > 0. The second term above (corresponding to the second term in Lemma is zero since the step size is time-invariant. The first term above can be further bounded as
K
T1.k 7
k= TI
ΣK kk=1 Uk S D 1/
1
In
In
In
+ +
17k-
91.k
Th
T]k
30
k=
where the first step due to the initialization of T1 = mhl 7 = 1/(Cu )²,, the second step holds since
Ex=l
The
Plugging in the setting of
K²
K
K
K
Σ
Th S
2 S
40%
C
4k
30
Co
Co
k=1
k=1
Since 1/1R = Co - 2h 2 2C,, the regret of MsMwC-TOP can be bounded by
T
C. S7
Σ 1=1
(44, q: -ex-) In
+ 167j-
--
?kk
30
1=1
Next, using Lemma again, the regret of the k* MsMWC-MID, whose step size is 27 can be bounded as
1
Co
Σ Le, Pt,k -ei.) S
In N + 32T
(le m4 x-)
SP
27k-
T,k'
(=1
T
1677
Pe,k (le,k, k me,k,))
1/N. Based on the observation of where the first step is due the initialization of Pi,k.
(Lr,a- m )2 (Le,k- Pr,k.)
Σ Etpe m),,..)
where the last step use Gauchy-Schwary inequality, combining the regret of MsMwC-TOP and the k--th MSMWC-MID finishes the proof.
B.4 Proof of Theorem
In Appendix C.2, we provide the proof of Theorem 2, the gradient-variation guarantees of the effi- cient version of Algorithm 1. Therefore, the proof of Theorem be directly extracted from that of Theorem 2. In the following, we give proof sketch.
Proof Sketch. The proof of the meta regret the same Theorem since the meta learners (top and middle layer) are both optimizing the linearized regret of Σir (V fe (x;,,x, X,, . The only difference lies in the base regret. In Theorem 1, since the base regret is defined on the original function Jt. the gradient-variatio
bound of the base learner can directly obtained via black- box analysis of the optimistic OMD algorithm, e.g., Theorem B. of Zhang et al. [2022a] (strongly convex), Theorem 15 (exp-come (cxp-concave) and Theorem 11 (convex) of Chiang et al. [2012]. The only re- quirement on the base learners is that they need to cancel the positive term of X . -x-1,,," I|2 caused by the universal optimism design (Lemma 1) and cascaded correction terms (Figure 1). The above base algorithms satisfy the requirement. The negative stability term in the optimistic OMD analysis is provided in Appendix E.2.
B.5 Proof of Corollary
In Appendix C.3, we provide Corollary 2, the small-loss guarantees of the efficient version of Al- gorithm 1. The proof of Corollary 1 can be directly extracted from that of Corollary 2. We give proof sketch below.
18

---

Proof Sketch. The proof sketch is similar to that of Theorem in Appendix B.4. Specifically, the meta regret can be bounded in the same way. Since cradient-variation bounds naturally implies small-loss ones due to (F.3), the small-loss bound of the base learner can be directly obtained via black-box analysis of the base algorithms mentioned in Appendix B.4, for different kinds of func- tions. The requirement of being capable of handling | 1, , ||? can be still satisfied, which finishes the proof sketch.
C Proofs for Section 4
In this section, we give the proofs for Section 4, including Proposition 1, Theorem 2 and Corollary 2.
C.1 Proof of Proposition
Proof. To handle the meta regret, ADAPT-ML-PROD [Gaillard et al., 2014] to optimize the linear loss & (f.. v), where le (xx)),,, xr,),, and obtain the following second- order bound by Corollary 4 of Gaillard al. [2014].
T
E (V)())); - -x,,)
In T xx xx..-)2
For a-exp-concave functions, it holds that
T In T
META-REG S
(x
V f(,,) X X1.10)
t=1
In T In I
(by ar. S a S 20c+)
20g
α
2a for any x, y. a 0 with agg.. To handle the base regret, by optimizing the surrogate loss function cxp using online Newton step [Hazan et al., 2007], holds that
where the second step uses AM-GM inequality: Vay S az
dDGexp
2dD(G + GD)
BASE-REG S
log T &
log T,
04
where Geep A maxxxxX.r((TT.eel (X)] S G GD represents the maximum gradient norm the last step is because a S 20,.. Combining the meta and base regret, the regret can be bounded by Od T). For X-strongly convex functions, since it is also al., 2007, Section 2.2], the above meta regret analysis is still applicable.
X/G² exp-concave under
Assumption 1 [Hazan To optimize the base regret, by optimizing the surrogate loss function N,,, using online gradient descent [Hazan et al., 2007], it holds that
G2
DD2 (1+log]), + (1 T) < A
BASE-REG I Apr
where Gy max [[ (x) S G D represents the maximum gradient norm and the last step is because À S 2A, Thus the overall regret can be bounded by Oloog For convex functions, the meta regret can be bounded by O In T), where the In In T factor can be omitted in the O(-) and the base regret can be bounded by O(VT) using OGD, resulting in an O VT) regret overall, which completes the proof.
C.2 Proof of Theorem
Proof. We first give different decompositions for the regret, then analyze the meta regret, and finally provide the proofs for different kinds of loss functions. Some abbreviations of the stability terms are defined in 1).
19

---

Regret Decomposition. Denoting by x" min Et=1 f((x), for exp-concave functions,
T
T (x(( X - x²)
Σ f((x)) - Σ
f((x*)
a
2 (V((())) x2)²
1=1
1=1
(x(()))) xx-)
V
(by Or S a S 20x+))
2
t=1
Σ (Vi((x),; x 2
[V(((x)), x.,,,,))
(xt,k* ;t )
Ni (x*)
META-REG
BASE-REG
where the second step uses the strong exp-concavity and the last step holds by defining surrogate loss functions ( (x) & (V/((x),, x) + % (V - x1)². Similarly, for strongly convex functions, the regret can be upper-bounded by
T
Air ||xe x 1|2
T
Vi(())), x
+
h (x),)).)))
Σ h (x*),
META-REG
BASE-ReG
by defining surrogate loss functions (x) & (VI((x:),,) + 2 ||x x, 112 For convex functions, the regret can be decomposed as:
T
REGT
- x -
()((()); X1,
META-REG
BASE-REG
Meta Regret Analysis. For the meta regret, we focus on the linearized term since the negative term by exp-concavity or strong convexity only exists analysis. Specifically,
T
T
V(((x)), xx
Vf((x)) X - xL Ve Xt,k x(,)),)))
K
Σ
(e,, 9: -ex-) ((eun - -er) - t=1
t=1
(=1
T
N
A2
Pr.ke s X1, - 1,-1, + + A2
(by definition of le l,,s)
t=1 1=1
T
T
T K
<
Le, q: -ex-)
Σ
(le,",,t, - -e,)- A1
qt
11-1, + 12
1=1
1=1
(=1 k=1
+ (2d1 A22) Σ
Σ
Pr Pr,t,, X2 11 - 111 +2,
D2SP
(by Lemma 6)
:=1==
K
(e, q: -0---- -ex-) + Σ - -e:)- - A1 Σ
<
+ 2\, DP + A25
(requiring X2 2 2X1)
Next, we investigate the regret of the two-layer meta algorithm (i.e., the first two terms above). To begin with, we validate the conditions of Lemma 3. First, since
R < GD + A2 |ma < 2GD + >₂D2 e < GD |maal & 2GD + (A1 + D²)
20

---

rescaling the ranges of losses and optimisms to [-1, 1] only add a constant multiplicative factors on the final result (A, and A2 only consist of constants). Second, by the definition of the losses and the optimisms, it holds that
(le me )2 = (() - PP.N.
(Pr,k* mi,k*
Pt,k+)² , (le,,* - mi.k* ,
where Ee,K, (V)((x:), x. Using Lemma 3, holds that
N
fi(x))), x1,b
In + 32 V. + A2ST
(requiring Co 1)
TTk
l
1=1
Co 5
X1
K
Ye |
x1-1, +
22,
Co
ST.
4
(=2
Co cq
T K
32m V, + A2 k- 2 T
ΣΣ
R - 1x-1,
The
2=
where the last step holds by requiring Co D2,
Exp-concave Functions.
Using Lemma 1, it holds that
1 T]k*
N
In 2 T/ +
32mp V. S
In
+ 128
(e(())) -- -x,) 0(1).
T)k
T
As result, the meta regret can be bounded by
META-REG
In
N
+
(1281TK-
Oc+
(xxx)) - x1)² + A
1]K
T
2
Co
T K Σ
cq
A
1t [ 1,11
2
t=2 t=2 k=1
512
22 N
Co
< (2Col1(4C
In
a²
+ X2
2 ST
(by Lemma 8 with
256
1
| 11
(C.1)
where the last step holds by a. S a S 20g.. For the base regret, according to Lemma 11, the i"-th base learner guarantees
Σ M (X
Σ 1 (x*) S
16d
In
1+
ai+
Vr,
7 + 72 7 5T (C.2)
8nd
O+
where Vr,,,, Σt= V (xt,ar.-)) 1 (X1- 1, ;- )12 denotes the empirical gradient
variation of the i" base learner. For simplicity, denote by g, Vf(xx), and this term can be further decomposed and bounded as:
V s
(gg a. g:g. (x - xx)) (g.-1 + a. (x, 1,6'
x1)11
t=2
T
<
Ig:: gt-1 2 Σ
+2
gg (x - xx) - 18-18__110 (x - - x111)
T
< 4V7 + 4L'SX + 2
Σ
lggg
8:-18 11-181111
(by (E.2))
21

---

T
+
4G*
(x - xt) - -xt--1,b - xx-1)]l
(by a E [/T, 1)
I C. VT. + C2S7 + 8G Sx
T
where the first step uses the definition of (x) = + aggig (x Xx) and the last step holds by setting C
4 G2D and C2 = 4L + 32D 8G Then we obtain
In
1 +
ar VTA
- In
1
a3 C1
VT +
a, C2 ST
as. G
yd 57.
8yd
8yd
8yd
In
+
ag Ci
V/r
+ In
1
C 8nd
pp
+ 0.
7d
ST (
8yd
1+
a.
8rd
ag. 8yd
ar+ C1
a+ C2
G
S In
[+
V/r
+
8yd
3p
ex
+
y
Sx
(In(1 + S x for 2 0)
Plugging the above result and due to ax+
S 20tt, the base regret can be bounded by
BASE-REC RESE-REG&S S
32d In
aC1
VT
+
2C2 Sx +
16G*
3
k + 2 2
8yy
Combining the meta regret and base regret, the overall regret can be bounded by
512 In
2
+ 32d
aCi
REGT S
+
In
1
Vr
a²
8yd
4C2D²
Co
44C2
St
A1
qt ||,,
7
2= R=1
160
-7)
1 + y>De
\/ +
8x
2
?
S o
Vir
(requiring Co 2 8C2DD// /7 A1 2 4C2/7,7 2 8G2 + X2)
Strongly Convex Functions. Since A-strongly convex function is also X/G² exp-concave under Assumption 1 [Hazan et al., 2007, Section 2.2], plugging a = x/G2 into the above analysis, the meta regret can be bounded by
512G² X
220
META-REG <
In
+
2C In(4 + 1257
X²
(C.3)
Co
$
A
q1,1 - x
t=2
For the base regret, according to Lemma 12, the i' base learner guarantees
Σ N (x+,
Σ Nr (x*) S Xy.
16G2
In (1+ Apr VT. + 4-
(C.4)
where V = Ei=2 Vhe (x) Vh (XI-1A ; >| is the empirical gradient vari- ation and Gue maxxex, (x)]], S + D represents the maximum gradient norm.
For simplicity, denote by g: A f((x))) and the empirical gradient variation VT, can be further decomposed as
Vr.
(ge + App (X x1)) (g:-1 + Ay (X1-1A x111))112
T
T
||g: g:-1 - 112 + 227.
Σ
[X - -x) (Xx- 11
(=2
1=2
22

---

$ 4Vr + +4+ + +47,,",
(by A E [/r,, 1)
where the first step the definition of (x* ge 7x(x x,). Consequently,
In (1 + A . & In(1 + 4A,, V/r + (4 ) S7 + 47,+ ST,K"
= =In + 4 VT) + In 1+ (4 4L )1, S7 + 47i= --1:-S7 TT
1 44,.11 VT
S In(1 + 4 Vi- + (4 + 4T. ) ST + 4x2- ST ,
(In(1 + x)) S x for x 2 0)
Plugging the above result and due to A;. S S 27,-, the base regret can be bounded by
32G se In(1 + 4 + 16Ca57 + (04G 3)
1 ST - + 4 DD?
BASE-REG I
where C3 = (4 + AL2 OL Combining the meta regret and base regret, the overall regret satisfies
REGT S 512G
N
32(G + D)
+ +C 2C0ol(( +
In(1 + 4XVT)
X²
X
Co
T
K
+
32D 03
S7 + (3203 - A1)
Σ
4t.k Xt, 1,x1,
2
1=2 km
+ (22 + 64G
7
1 5x k 5 +
7 7212
8
{ 1V Vr
$ o
+ +5100?) (requiring Co 2 64D2C3, 2 320, +
Convex Functions.
Using Lemma 1, it holds that
1 N ?lk
1 In
N
In
+ 32m V. s 17k-
128 + G*) + Sx K
The
n
S 2Co In(4CO,) + 32D 222D22112 2V In(112N + +2 + G + 2G ST ,
where the first step is due to 7/2 = 1/(Co ) S 1/(2Cn) and requiring Co 2 1 and the last step by Lemma 7 and requiring Co 2 8D. Thus the meta regret can be bounded by
META-REG S 2C, In(C + O( Vn - 2(D2 +
G
Co S
T
K
+ (A2 + 2G
) k
X Σ
1,
k=
For the base regret, according to Lemma 10, the convex base learner guarantees
T
BASE-REG
(V)(()))
N x*) < 5D 1 Viaa + +>D
I Isx (C.5)
4 3
t=1
where VT. =
[V)x (x denotes the empirical gradient variation of the base learner. Via (F.2), the base regret can be bounded by
BASE-REG < 2V, 10D1 SX + 7DD2
-sx S
Combining the meta regret and base regret, the overall regret can be bounded by
REGT S (
+ 5DV1++2/
Co
2DC
St + (2Cg- A1)
20 |x,, x,
2
+ +(12 + 26 2)
Sx k + 722
23

---

$ In
(requiring Co 2 4DC,, 2 20 22 412 + 8G2)
where C2 = 2 + 10DD?.
Overall. At last, we determine the specific values of Co, A1 and A2. These parameters need to satisfy the following requirements:
8C2D²
Co 2 1, Co D2, Co 2 128, Co 2
Co 2 64D' Co 2 8D, Co 2 4DC4,
802 + X2
2C X 2 32C3, A 2C4, A2 2 2X1
A
8G A2
As result, we set Co, A1, X2 to be the minimum constants satisfying the above conditions., which completes the proof.
C.3 Proof of Corollary
In this part, we provide Corollary 2, which obtains the same small-loss bounds as Corollary 1, but only requires one gradient query within each round.
Corollary 2. Under Assumptions I and 2, if fe(.) for all [T), the efficient version of Algorithm I obtains (log FT), Old log FT) and ((VFT) regret bounds for strongly convex, exp- concave and convex functions, using only one gradient per round.
Proof. For simplicity, define 177 2 D (xx).. Some abbreviations are given in (B.1).
Exp-concave Functions. The meta regret can be bounded the same as Theorem (espe- cially (C.1)), and thus we directly move to the base regret. For simplicity, we denote by g: fx(x)) and give different decomposition for VT,,+, Σi= Wh (x,,
1 (x-11 II? the empirical gradient variation of the base learner.
T
Vi
(gr + ag. g.g, (X x:)) (g--1 + ar 11-1-1181111 (x x1-1))112
T
< 2
+ 20 |g: 11-
(XI- - T lggg (x1,*,.- - xx)) xx) g.-18i
x112)
1=2
1=2
T
2
|g: g 11- +4D2
ggg.
-:-1 + 8G' + 8
1=2
< <2 52++16D G2) Σ g: 8
&G 8G SX ST.
CC +G ST SG* SG*SS ST
(by (E.3)
where the first step by using the definition of Vh (x) = + agg.g (x xt), the third step uses the assumption that a E [1/T, 1] without loss of generality, and the last step sets Css = 16T + G2) Consequently, it holds that
Oli 8yd
V.. ) s (1+
a2 Cs
Oi G
G ag-
1
Fx
+
SX
+
ST
8yd
y
dd
Plugging the above result and due to ax S S 20,,, the base regret can be bounded by
BASE-RESS REG < a
32d 1+
aCs
Fx
16G4
Sx
(16
?
S + 2 nDD
8yd
Combining the meta regret (C.1) and base regret, the overall regret can be bounded by
512 In REGT < a a² 2C, In +
22
32d
aCa 8yd
1
Fxx
a
24

---

32D2
Co
3224
T K
+
St +
\1
gr
1,
2
2= k=1
16G
2
+
A2 +
0
In F+
(requiring Co 2 64D4 /// A 2 32G ///2//2 2 8G2 + x2)
d
0
In FT
where the last uses the following lemma.
Lemma 4 (Corollary 5 of Orabona et al. [2012]). If b, c, d, x > 0 satisfy d S a annnbb + c).
2ab + 2bd + 2c
x - d S aln
2ab In
Strongly Convex Functions. The meta regret can be bounded the same as Theorem (es- pecially (C.3)), and thus we directly move on to the base regret. For simplicity, we denote by Br A (x(()) and give different decomposition for Vr, = Ei=2|VVig (x,,),))))
Vh 1-12 (x ).? the empirical gradient variation of the base learner.
Vr Σ [gr + Ap -x x1)) - (g:-1 +x- x(-1))112
T
T
2
Σ
l|g: g 11-1 + 227.
Σ
[1x,,,,t - -x,) (x4-1.45 - x2-1))12
1=2
t=2
S 32LF + 4S} + T.
(by (E.3) and [2/T, 1))
where the first step uses the definition of Vhf,,()) = g: > x.). Consequently,
16G2 dj-
16G.
In (1 + A vT < A;-
In(1 + 32 LF}) + 64G (S7 + S
Plugging the above result and due to );- X - 2 the base regret can be bounded by
32G2 In(1 32ALF)) + 64G2 + (61G2
2 S K + z D
BASE-REG &
Combining the meta regret (C.3) and base regret, the overall regret can be bounded by
512G2
2
NG
32G2
REGT S
In
+2cg
+
In + 32ALF
X²
A
Co
T K
+ 128D G2
St + (128G2 - X1)
Xt,k x
1.
2
A2 + 6102
?
xx K*
8
0
In Fxx
(requiring C. 2 256D a > 128G2 7 8Ag + 512G
0
In FT
(by Lemma 4)
Convex Functions. We first give a different analysis for V. 4 EL El - m,,...)) From
Lemma 1, it holds that
T
V. < 2D
[x(()) - (x
2G
| Xt- + Xt-1 - xx11
25

---

S + +
ST + SG
(by (E.3))
Plugging the above analysis back to the meta regret, we obtain
N
META-RES
I
In
+
1024mM.
D2 LF
2G2 ST + (A2 222²) )
7k
Th
T
K
Co
2 T
X
x1, -
(=2
k=1
For the base regret, using Lemma 10 and (E.3), it holds that
BASE-REG I 20D LF7 - 7
S x O1).
4
Combining the meta regret and base regret, the overall regret can be bounded by
REGT 1
1
In
N
1024MK
DALF + 20D /LFK
(>e + 2G - -2) S ,
17--
T/.
Co
T
+
4DD2
5 + (4G² -11) 2
ΣΣ
Σgn
(0,11]xe, - -xt- 1,12
t= k=1
N
Ne
In
1024m D2 + 20D LF
In
+ 1044m 1044m=DD2Ln DF7
2
2
1/ks
k/
?
T
2
Ne
<
In
_
+ 2088 DFL
7lk*
The
S 4Cp In(4C o
(v Fr In In FT)
(by Lemma 7)
where the second step holds by requiring Co 2 DD λ 2 4G and 7 2 4A2 + 8G2, and the third step uses AM-GM inequality: vry < + & for any I, V, 0 with 1/(2Di ). The fourth step is by requiring - 10444- L 2 1/2, ie., 17 < 1/(2088 for any A E [K]. which can be satisfied by requiring Co 2 1
Overall. At last, we determine the specific values of Co, A1 and d2. These parameters need to satisfy the following requirements:
64
Co 2 1, Co 2 4h1 Co 2 128, C. 2
C. 2 G5 Co 2 8D*G2,
80 + X
32G4
Co M 104AD2L, AZ
\ 128G2 set \ 2 4G2 A 2 2d1
8G
X2
As a result, we set Co, A1. A2 to be the minimum constants satisfying the above conditions. Be- sides, since the absolute values of the surrogate losses and the optimisms are bounded by problem- independent constants, as shown in the proof of Theorem 1, rescaling them to [-1, only add constant multiplicative factors on the final result.
D Proofs for Appendix A
This section provides the proof' for Appendix A, including Theorem 3 and Theorem 4.
D.1 Proof of Theorem 3
key result in the work of Chen et al. [2023b] is the following decomposition for the empirical gradient variation Vy e E (xx,) - If--1(x--)]1' restated as follows.
Lemma (Lemma 4 of Chen al. [2023b]). Under the same assumptions as Chen al. [2023b).
T
T
E
[xxx))
V (x
<
4L
||xe x.-
11 + 80 + 4 + 0())
1=2
26

---

Proof of Theorem 3. The analysis is almost the same as the proof of Theorem 2. Some abbreviations of the stability terms are defined in (B.I).
Exp-concave Functions. The meta regret remains the same as (C.1) and the only difference is a slightly different decomposition of the empirical gradient variation of the base learner, i.e., Vr, in (C.2). Specifically, it holds that
V
(g: 0g gig (XL, xx)) (gi-1 a.. 18 I xx-1))11?
T
$ (2+ (2+ Σ Igg: - g-111 + 8G 8G*57 + 8G ST T
- 2030 + C + C&S + S7
where C3- 8(L+8D&G9) C.- L6 and the last step is by taking expectation on both sides and Lemma 5, leading to the following upper bound of the base algorithm:
E E[BASE-REG] s O (~
d In (o + kir))
2Co S7 +
(16G* 2)
S + 2 DD..
1
7
Combining the meta regret and base regret, the overall regret can be bounded by
512 In
2
E|REGT] <
+
20
+0
In (o + +xxx))
a
40,
Co
[40
K
St +
A1
2 | Xt,k 1,
?
2
t= k=1
12+ + 7
160
-
ST.K + 1 2 <0
Sx
In(oi:z + +E(g))
where the last step holds by requiring Co 2 8C,D2/T,>1 2 40o/ and y 2 X2 + 8G2.
Strongly Convex Functions. The meta regret remains the same (C.3) and the only difference is a slightly different decomposition of the empirical gradient variation of the base learner:
[| Vh, (x))),;)) - Vhg 1,a- (x,- 1,,,, )1
= E (g + d: (Xt, - x:)) - (g:-1 + di+ (Xt (xt- 1 xt- 13
< 2E [|lg: gi-1 11-] + 22 [xxt,,t',' x1) 1, 1112
< 160 + + (4 + | X xx-1 11 , X1-1,8- 113
where of A maxxex EY.-D, || [x())) VF Σラ A E Sup x
(
and the last step is by taking expectation on both sides and Lemma 5. Plugging the above empirical gradient variation decomposition into Lemma 12, we aim control the following term:
T
E
s0 (x.M).))) Vi (x 11?
Axat
20 +
(1+213)][x, - 11 + Xe. Xx- 1
8
+4
djol
diol
2=2
1=2
1omaxx + E In Xi.r) 8L2 +1) Im(1 + As- (1 (1+)S AŞ+ .+.
0
The last step due to Lemma which is a generalization of Lemma 5 of Chen et al. [2023b]. Combining the meta regret and base regret, the overall regret can be bounded by
512G²
220
N
(1 E In Ei,T)
E REGT
In
+ +C +2Co In(4CG +
X²
Co)
T K
20,D2_
Sy. + (2C,
A1)
ge.k 11,,
x1-1,
2
27

---

+ A2 + +32 + +1) -1)--8)
2) ST The + 7D2
0 (0 max + > In(o 22:7)
where O 64D (L? + 1)² and the last step holds by requiring Co 4C,D², x 2 2C7 and Y 2 842 + 2 (L2 + +1..
Convex Functions. We first give a slightly different decomposition for V. & Exlles Me s=)² Starting from Lemma 5, holds that
T [V((())) - V(--1(x(-1)) + Σ V. I 2D
| X1-1 + X1-1 - x+|1
S SDD (20 + 48 4G (1),
where the last step by taking expectation on both sides. Following the same proof as in Theorem 2, taking expectation both sides, the expected meta regret can be bounded by
N
E MEEEAA-REE
In
+
128D I]c (20 + Eir) + 128 G
1/K-
T
Co
T
K
+ + + 128G )S 1
c
1
x1-111?
2
1=
(Viožy + Eg
$ 22Coln(4GEN)+ +0
In(of:r + Ejer)
Co
T
+ 128 G (A2 + 128G2) ) TT
A1 ST
qt x.
11
where the last step is due to Lemma 7 by requiring Co 2 8D.
For the base regret, the only difference is a slightly different decomposition of the empirical gradient variation of the base learner, i.c., VT, . in (C.5). Specifically, using Lemma 5, it holds that
[[BASE-REG] I 10D (207 + 21.7) 10DLST 7D2 2 sx T O().
Combining the meta regret and base regret, the overall regret can be bounded by
E[REGy| 0
(oं. + E In(or.r + +biTT) + (C
K
2D'C Co
+
S9 +(20g -11)
2 x
x1-1,
1=
(M2
+18862
-2)
5x ; + +7D2²
0
( (of.r + In(o + Ex
where C = 122(222 +10DL and the last step holds by requiring Co 2 4D'Co, A 2 20g
and 7 2 + 512G
Overall. At last, we determine the specific values of Co, A1 and d2. These parameters need to satisfy the following requirements:
Co 1, Co 2 D2, Co 2 128, Co 2 SC,D2
Co 2 4C,D3, Co 2 4D2Cs
Co 2 8D,
8G2 + A22
16 + X
4C
20s
C. CD A 8G + A2
A > 2C,, X
x > 2C,, x 4G2 Xa 2 2X1.
16 16
As a result, we set Co A1 d2 to be the minimum constants satisfying the above conditions. Be- sides, since the absolute values of the surrogate losses and the optimisms are bounded by problem- independent constants, as shown the proof of Theorem rescaling them to [-1, 1] only add constant multiplicative factors on the final result.
D
28

---

D.2 Proof of Theorem 4
Proof. The proof of the dishonest case straightforward by directly applying Theorem 2. In the following, we mainly focus on the honest case. Consider a bilinear game of f(x.y) - x" Ay and denote by gi Ayt, gi & Ax, the gradients received by the x-player and y-player. The only difference from the proof of Theorem 2 is that the gradient variation can be now decomposed
lg 1--1
|| Ay:- I1 s ||y+ yr-1ll
where the step holds under the mild assumption of |||]| s The gradient variation of the x- player is associated with the stability term of the y-player. When summing the regret of the players, the negative terms the x-player's algorithm can be leveraged to cancel the gradient variation of the y-player and vise versa. As result, all gradient variations can be canceled and the summation of regret bounded by O(1). As for strongly convex-concave games, since it is a special case of the bilinear games, the above derivations still hold, which completes the proof.
E Supporting Lemmas
In this section, we present several supporting lemmas used in proving our theoretical results. In Appendix 1. provide useful lemmas for the decomposition of two combined decisions and the parameter tuning. And in Appendix E.2, we analyze the stability of the base algorithms for different kinds of loss functions.
E.1
Useful Lemmas
In this part, we conclude some useful lemmas for bounding the gap between two combined decisions (Lemma 6), tuning the parameter (Lemma 7 and Lemma 8), and useful summation (Lemma 9),
Lemma 6. Under Assumption 1, if En P.X., Ein 4.y where p, q AN, X,,y; X for any i E [N], then it holds that
||x - y1 S _
- ql1--
i=1
Lemma 7. For a step size pool of Hn = (nokeejк] where 7 20% 2 ... 2 AK 20,T if
Co 2 X 2T there exists E Hy such that
1 Y nx 2Co + 4V
In
" 7
Lemma 8. Denoting by n, the optimal step size, for a step size pool of Hy = tns where
2C 2... 1K 2C.
Co 2 24. there exists ij E Hy such that
1 Y
2 4Y
ln 1/2
< 2C In Cb)
"
1/+
Lemma 9. For a sequence of {ar VT and b, where at b > for any t E (T), denoting by amax max, 0₁ and A & [b a have
Omax
b (1 1 (m 1
1
bt
Proof of Lemma 6. The tenm of |xx
2
can be decomposed as follows:
N
N
N
N
N
N
||x - 2
P.X:
Σ
y:Y:
=
Σ
P:X:
P.y. +
p.y
Σ
y:yi
i=1
i=1
i=1
< 2
Σ pr(x; - y:)
2
Σ
(pr - q:)y
i=1
29

---

2 Σ pi X yill
S 2
+2 Σ Pi q: ||yss|
2 2
Σ Pt pilxx +
where the first inequality is due to (a + +)² < 2a + 2b² for any a, b E R, and the last step is due to Cauchy-Schward inequality, Assumption and the definition of & 1nnorm, finishing the proof.
Proof of Lemma 7. Denoting the optimal step size by 7)+
- v In /m(4XX)/X, if the optimal step size
satisfies 17 S 7) 2n, where 7) S 7) can be guaranteed if Co XX then it holds that
1 Y 7
2 hn 4Y 7/-
In 7 + n
n.
3v XXIXXXX)
T/2
Otherwise, if the optimal step size is greater than the maximum step size in the parameter pool, i.e., 7/ 2 (1) = 7/1
20,), then we have
Y
Y
xX
In +n.x
20g VIIn(XXY).
11
1 n
Overall, holds that
Y
In
2C In()) 4
which completes the proof.
Proof of Lemma 8. The proof follows the same flow as Lemma 7.
Proof of Lemma 9. This result is inspired by Lemma of Chen et al. [2023b]. and we generalize it arbitrary variables for our purpose. Specifically, we consider two cases: < T and A T. For the first case, if A < T, it holds that
A
T
A
T
G bt
a
Gmax
+ 6(A 1)
Σ A+1
a
S
Qmax
1 (1 +1+In In + 62
bt
bt
b
A+1
1=1
where the last step is due to Σ at similarly, which finishes the proof.
Σt ar I 1/b. The case of A < T can be proved
E.2 Stability Analysis of Base Algorithms
In this part, we analyze the negative stability terms in optimism OMD analysis, for convex, exp- concave and strongly convex functions. For simplicity, we define the empirical gradient variation:
VT A
g: - g.-1/? where g: A fx(.).
(E.1)
In the following, we provide two kinds of decompositions that are used in the analysis of gradient- variation and small-loss guarantees, respectively. First, using smoothness (Assumption 2), we have
lig. (x.) Vf-- g:- 2 2V + 21
Σ ||x x,-1|
(E.2)
2
< 4Lf(x) holds for Second, for an L-smooth and non-negative function f : X + R4, | [xx any X [Srebro et al., 2010, Lemma 3.1]. It holds that
1 Σ lg. 1--1 <
Σ
g 2 + Σ
gg 1 < 16L Σ f((x)). (E.3)
g
Next we provide the regret analysis in terms of the empirical gradient-variation Vr, for convex (Lemma 10), exp-concave (Lemma 11), and strongly convex (Lemmaa 12) functions.
30

---

Under Assumptions and 2, if the loss functions are convex, optimistic OGD with the following update rule:
Lemma 10.
X 1xx m.m,,, R+11 1xx 1/ [xx))(
(E.4)
where xx - arg arg yex |x-x/i yll, m ( and = min V 1/1),
enjoys the following empirical pradient-variation bound:
T
- -xx-x=11+++0
REGT & <5DV1 Vr + DD²
Lemma 11. Under Assumptions and 2, if the loss functions are a-exp-concave, optimistic OMD with the following update rule:
arg min (mm, x) + (x, xEX
R
arg arg ((Vf((x)) + Du. {x)),
XEX
where vhe(-) Ill IR U. -1+ 9 V((x and m, V (x;-1x))));
enjoys the following empirical gradient-variation bound:
REGT S
16d In (1 8yd
a Vr
2
22D2
T
t=2
Lemma 12. Under Assumptions 1 and 2, if the loss functions are X-strongly corver, optimistic
OGD (E.4) with 7,- = 2/(7+ X6) and m. V f5-1 (xt-1), 1), enjoys the following empirical gradient-
variation bound:
REGT S In (1
16G
+ D² 7
D
T X 112
X
4
8
1=
Proof of Lemma 10. The proof mainly follows Theorem 11 of Chiang et al. [2012]. Following the standard analysis of optimistic OMD, e.g., Theorem 1 of Zhao et al. [2021], it holds that
T m [VS((x) m 12
Σ (xx) E(())
s
(Do 2.) (x* &e+1))
ADAPHIVTTY
OFT-GAP
(De(Rrt1,))) + De, (xx,
(E.5)
STABILITY
where arg migginxez Σ (x( and v0.) 1lll 11 The adaptivity term satisfies
(x(( V (x+- 1)11
ADAPTIVITY
Σ Me V[((xx)) m0/1 3 Σ
1+ s=1 (x,)))) V (x
4D 1+ ((((x))-V(-ixx--)) 4D0
where the last step uses Lattimore, 2019, Lemma 4.8). Next, we move on to the optimality gap.
Σ 4t/ 1 < 1
at + max 4 [Pogodin and
1 1
1
OPT-GAP Σ (Dx Dx &441))
Sell2 - ||x 8x42 (22) (||x*
21
[xllu & Vx Uix refers the matrix norm.
31

---

x
111
T
+
||x &
2m
21/²
21/(-1
1=2
(1 + +D) + +
Σ
T
1
$
(1 (1
+D)+ +
D
2
21
21
2
21T
1=2
= =DD² + D V + (1).
2
Finally, we analyze the stability term,
T
1
STABILITY =
Σ
(1|2+11
x+112 + 1|x: - 2..1
2
(1|x, x1-1
+1++llx 1|xx 8x.13)
21pt
21/F
t=1
t=2
[
X
11
X X
41/t
t=2
Combining the above incqualities completes the proof.
Proof of Lemma 11. The proof mainly follows Theorem 15 of Chiang et al. [2012]. Denoting by
x* E arg min xEX Et= f((x), it holds that
T
T
Σ f(())) Σ fi(x)) S
[v(((x)) - mille, +
Σ
DD. (x",
Dev, (x", &c+1))
t=1
ADAPTIVITY
OPT-GAP
(Der (R++1, + Dr (x+, 2x))
I VAM
STABILITY
NEGATIVITY
where the last term is imported by the definition of exp-concavity. First, the optimality gap satisfies
1 T
1
OPT-GAP
X
R
Σ
xx 2111112.
2
2
t=1
t=1
$ 1 -
-11x
-
+ Σ
[||x* R24111e - -1|x* 8441112,
DG
T
Σ
||x
Re+ 1 (())
4
7
We handle the last term by leveraging the negative term imported by exp-concavity:
OPT-GAP NEGATIVITY
T
T
< 22
1
a +
x -
a
X
x
( + 0(1)
2
2
4
2
1=1
<
1
2
+
a
[ + O(1).
|x
2
where the local norm of the second term above can be transformed into Uz:
T
X S.l < a
T
|x
x
1
Σ
|xx
1=1
t=1
Using the stability of optimistic OMD [Chiang et al., 2012, Proposition 7]. the above term can be further bounded by
xx
8 12:,
S
[V((x)) - m01122-- 1m.
32

---

By choosing the optimism as m, Vxi-((x(-1). the above term can be consequently bounded due Lemma 19 of Chiang et al. [2012]]
T Σ
[Vx())) v (
Sd
In
1+
a
Vr)
8yd
The last step is to analyze the negative stability term:
1 T
1
STABILITY
Σ
DD. (Re+1, Xx) + Dai (x,, 8,))
Re+1 - xcllē,
+
Σ
||x
8x 12
2
2
t=
t=1
T
2 Rx+1 xel +
Xxt
xel1
Σ
||x, x1-1
1=2
Combining existing results, have
REGT S
16d In
1
8yd
a VI
+
2
4
7
T Σ
|
x x1-
X,
t=2
which completes the proof.
Proof of Lemma 12. The proof mainly follows Theorem 3 of Chen et al. [2023b]. Following the almost the same regret decomposition in Lemma 10, it holds that
E (xx)s (F.5)
A Σ x
1
2
NEGATIVITY
First, we analyze the optimality gap,
1 OPT-GAP S [x
1
1
Σ
Dx(x", (2411)
11141
t=1
A
S (1 + xXD²
+
|x*
R2+1112
1=1
We handle the last term by leveraging the negative term imported by strong convexity:
T
T
1 (
A
OPT-GAP NEGATIVITY <
N)D2
+
xx
21+1112
Xx
x
2
1=1
t=1
T
< D2
A
Σ
xx:
R411l1 12+1 O(1).
2
t=1
The second term above can be bounded by the stability of optimistic OMD:
T
A
x 11
Th
ll m
11 ne f((x)) -m,1
Finally, we lower-bound the stability term
T
STABILITY = Σ
+
A
(1| - x1112 + ||xx - -x,113)
(by m: 2 4ttt
4
1=1
T
2
(115,,
x 11 + ||x, 8x.12) >
xx x, 11.
4
8 1=2 2
2
33

---

Choosing the optimism
V -x we have
REGT 2 N ()) ( 1 DD²
2 t=
x x1- O(1)
To analyze the first term above, we follow the similar argument of Chen et al. [2023b]. By Lemma with a, - [(x))
(x--1(x--1)11 Umax 4G" A [AVT]. and b = X, holds that
T
4G lg. B-1ll & X (1 AVT)
4G
Xl
X
1=1
Since = 2/ + Xt) S (At), combining existing results, we have
REGr
16G
In (1 AVr) 4
7 8 1=
x, x1 0((),
which completes the proof.
34


Reviews:
[{"review_id": "r49lyEDrmD", "reviewer": "Reviewer_FwDP", "summary": "Addressing to the drawback of Zhang et al. [2022], which does not enjoy gradient-variation bounds for convex functions, using an optimistic version of ADAPT-ML-PROD with a second-order bound of  [Wei et al.,  2016],three-layer online ensemble structure with two-layer meta learner running  MSMWC [Chen et al., 2021] with different parameter configurations, and each MSMWC-MID is further connected with N base learners to explore the unknown function information, is developed.$\\mathcal{O}(\\ln V_T)$, $\\mathcal{O}(d \\ln V_T)$ and $\\hat{\\mathcal{O}}(\\sqrt{V_T})$ regret bounds for strongly convex, exp-concave and convex loss functions is obtained. two different levels of adaptivity with problem-dependent gradient variations, e.g., adaptive to unknown function information and benign Environments are fulfilled.", "questions": "I believe that exists other gradient-variation bounds, which is similar to [Wei et al., 2016], Can better results be obtained by means of it?", "limitations": "the authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "In Zhang et al. [2022], the convex case has not been addressed. a two-layer framework In Zhang et al. [2022] is generalized to three-layer online ensemble structure. a single algorithm with gradient-variation bounds for all kinds of functions is designed.", "weaknesses": "1 the derived results substantially depend on Zhang et al. [2022], [Chen et al., 2021], Zhao et al. [2021] and [Wei et al., 2016].\n2 The results of the algorithm still belong to the class of MSMWC [Chen et al., 2021]. the decomposed regret and injecting cascaded correction terms to both the top and middle layer make the work replicate published findings without adding substantial knowledge, leading to lack of novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful feedback. Below we clarify our unique contributions and differentiate our approach from existing ones, hoping to address your concerns.\n\n---\n\n**Q1**. The derived results substantially depend on [Zhang et al., 2022], [Chen et al., 2021], [Zhao et al., 2021], and [Wei et al., 2016].\n\n**A1**. We acknowledge that some algorithm components of our approach are based on existing works, and thus the new ones might appear as \"simple modifications\" (depending on one's familiarity with online learning). However, effectively integrating them to obtain our results necessitates *non-trivial innovations*. We will include more elaborations on technical contributions in A2. Below, we emphasize the importance of the problem and our results.\n\n* **Importance of problem:** obtaining universal gradient-variation bounds is highly important but challenging, left as an *open problem* by [Zhang et al., 2022] and now resolved by us. The importance of the problem comes from two aspects:\n  * The convex case, where the method of [Zhang et al., 2022] fails, is far more important than the other two cases (exp-concave and strongly convex) since the improvement from $T$ to $V_T$ is *polynomial* in the convex case, whereas *logarithmic* in the other two cases (as stated in Line 69).\n  * The gradient variation is a *fundamental* problem-dependent quantity in modern online learning due to its implications for worst-case and small-loss guarantees, and profound connections with adversarial/stochastic convex optimization and games.\n\n* **Importance of our results:** our results can be applied to various learning problems. In particular, applying them to the *stochastically extended adversarial (SEA)* model gives a *single* algorithm with *nearly optimal* regret bounds for different kinds of functions, thus resolving the *major open problem* left by [Chen et al., 2023] (see their conclusion for the open problem).  Furthermore, our results can also be applied to *games*, providing universal guarantees therein. The applications are deferred to *Appendix A* due to page constraints. Please refer to Table 3 and Table 4 on Page 13 for an overview of our results in the aforementioned applications.\n\nTo summarize, while some algorithm components of our method are based on existing works, we have made non-trivial usages and effectively resolved *two open problems* raised in the literature. We believe that our work has solid contributions and holds significant interest to the community.\n\n---\n\n**Q2**. The results of the algorithm still belong to the class of MSMWC [Chen et al., 2021]. the decomposed regret and injecting cascaded correction terms to both the top and middle layer make the work replicate published findings without adding substantial knowledge, leading to a lack of novelty.\n\n**A2**. We respectfully disagree with this comment. While inspired by existing works, effectively unifying them to solve our problem requires comprehensive uses of them. Besides, there are also unique challenges in our problem, which necessitate novel technical contributions for solving them.\n\nBelow we discuss the mentioned techniques (MsMwC, regret decomposition, and cascaded correction terms), hoping to address your concerns.\n\n* **MsMwC:** our meta algorithm resides within MsMwC but incorporates novel techniques, including a *novel optimism design* (detailed in Section 3.1) and *negative stability terms in the analysis* (Section 3.2.1), which may be of independent interest to the community.\n* **Regret decomposition:** our regret decomposition in Section 4 is novel, allowing the algorithm to use only one gradient query in each round. Note that such a regret decomposition is *inapplicable* to [Zhang et al., 2022] because their method cannot deal with the positive stability terms as we do.\n* **Cascaded correction terms:** although our use of cascaded correction terms is not entirely new, the application to a three-layer structure necessitated *an extensive adaptation* of the technique. Importantly, our research focus deviates significantly from the existing literature --- our work is the *first* to introduce corrections for universal online learning, whereas prior works use it for different purposes, such as non-stationary online learning [Zhao et al., 2021] and the multi-scale expert problem [Chen et al., 2021].\n\n---\n\n**Q3**. I believe that exists other gradient-variation bounds which are similar to [Wei et al., 2016]. Can better results be obtained by means of it?\n\n**A3**. We are not sure if we get this question accurately. As far as we know, simply modifying [Wei et al., 2016] does not suffice to obtain gradient-variation universal regret bounds (as explained in Line 164-176). This is due to the lack of negative terms in their regret analysis, which makes it hard to perform cancellations as we did in our work.\n\n---\n\nWe will revise the paper to ensure the readers understand our key contributions better. If our responses have properly addressed your concerns, please consider updating your score. Thanks!"}, {"review_id": "mrRJXpJBpq", "reviewer": "Reviewer_x4hL", "summary": "This paper proposes an online convex optimization algorithm that is adaptive in two ways to the environment.\nSpecifically, it can achieve logarithmic regrets for problems with good properties such as strong convexity and exp-concavity,\nas well as $\\sqrt{T}$ regret in the worst-case.\nFurther,\nit achieves improved regret bounds for problems with small variation of the function gradients.\nIn addition, it works with only one gradient call per round.", "questions": "Can you address the concerns described in Weaknesses above?", "limitations": "I have no concerns about the limitations and potential negative societal impact are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper is well structured and easy to follow.\n- Existing studies are adequately reviewed and the paper is informative for the reader.\n- The paper clearly explains the structure of the proposed method, the idea of the proof, and its implication in great detail.", "weaknesses": "Compared to the study by Zhang et al. [2022], the magnitude of the contribution of this paper appears somewhat limited.\nAlthough the design of the algorithm is quite sophisticated, the main component is a combination of already known techniques.\nIt would be better to have a more detailed description of the challenges in algorithm design and analysis, as well as the new techniques proposed in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable feedback. We believe that our work has solid contributions and holds significant interest to the community. The submitted version may not have effectively conveyed our findings clearly, leading to the reviewer's perception. We will carefully revise the paper to clarify the unique contributions of our work. Herein, we elaborate on our work's results and techniques to highlight its unique significance.\n\n---\n\n**Results:** our research offers more than an enhanced gradient-variation bound for convex functions over [Zhang et al., 2022]. Below we emphasize the importance of the problem and our results.\n\n* **Importance of problem:** obtaining universal gradient-variation bounds is highly important but challenging, left as an *open problem* by [Zhang et al., 2022] and now resolved by us. The importance comes from two aspects:\n  * The convex case, where the method of [Zhang et al., 2022] fails, is far more important than the other two cases (exp-concave and strongly convex) since the improvement from $T$ to $V_T$ is *polynomial* in the convex case, whereas *logarithmic* in the other two cases (as stated in Line 69).\n  * The gradient variation is a *fundamental* problem-dependent quantity in modern online learning due to its implications for worst-case and small-loss guarantees, and profound connections with adversarial/stochastic convex optimization and games. \n* **Importance of our results:** our results can be applied to various learning problems. In particular, applying them to the *stochastically extended adversarial (SEA)* model gives a *single* algorithm with *nearly optimal* regret bounds with different kinds of functions, thus resolving the *major open problem* left by [Chen et al., 2023] (see their conclusion for the open problem). Furthermore, our results can also be applied to *games*, providing universal guarantees therein. The applications are deferred to *Appendix A* due to page constraints. Please refer to Table 3 and Table 4 on Page 13 for an overview of our results in the aforementioned applications.\n\n---\n\n**Techniques:** our method is not a combination of already known techniques but with some important innovations, as outlined in Lines 90-99. As far as we know, these techniques did not appear in previous works, which distinctly differentiate our method from that of [Zhang et al., 2022].\n\n* The first innovation is a *novel optimism design* (elaborated in Section 3.1), demonstrating that a straightforward modification of existing methods is insufficient to tackle this problem. \n* The second innovation involves a *novel meta-base regret decomposition* with customized surrogate losses for base learners (detailed in Section 4), reducing gradient complexity to one per round. Note that such a regret decomposition is *inapplicable* to [Zhang et al., 2022] because their method cannot deal with the positive stability terms as we do.\n* The third innovation is incorporating *cascaded correction terms* within a three-layer structure (Section 3.2.2). Although the idea of correction terms is not new to other problems, such as non-stationary online learning [Zhao et al., 2021] and the multi-scale expert problem [Chen et al., 2021], our work is the *first* to introduce it to universal online learning, and the application to a three-layer structure necessitated *an extensive adaptation* of the technique.\n* Two interesting novel byproducts arise in our techniques. \n  * The first one is the *negative terms in MsMwC* (Section 3.2.1), which may be of independent interest to the community. \n  * The second one is a simple method and analysis for the worst-case universal guarantees (detailed in Proposition 1 in Section 4) and a general regret decomposition in the online ensemble structure for exp-concave and strongly convex functions.\n\n\n---\n\n\nIf our responses have properly addressed your concerns, please consider updating your score. Thanks!"}, {"review_id": "PfsyyN1bhu", "reviewer": "Reviewer_ZhYs", "summary": "A new algorithm for online learning is provided, together with improved regret bounds compared to the state-of-the-art: \n\nThe new regret guarantees are summarised in table 1 on page 2: in the case of a strongly convex function, the regret guarantee is of $O(min(\\log(V_T),\\log (F_T)))$ where $V_T$ and $F_T$ are the gradient variation and cumulative loss of the best comparator respectively (cf. equation on lines 53 to 54). In the case of exp-concave functions, the rate is the same, whereas in the case of a convex function, the rate is $\\widetilde{O}(\\min(\\sqrt{V_t},\\sqrt{F_T})$ instead. In terms of the regret bound, only the convex case is an improvement over the existing results ([3], $O(\\sqrt{F_T})$). An additional claimed advantage is that the gradient query is reduced to $O(1)$ instead of $O(\\log(T))$: this is valid for an improved algorithm (separate from the main algorithm presented in the paper) with additional surrogate losses, which is only presented in the appendix on page 18 (Algorithm 2)\n\nThe main algorithm itself is a combination of several existing techniques: at each iteration, a set of $KN$ experts $(k,i)\\in [K]\\times [N]$ each consisting of different gradient descent methods is maintained. Each expert computes the gradient update as per Optimistic OMD [3]. Then, for each fixed $k$, the experts $(k,i')$ for $i'\\leq N$ are aggregated exactly as in MsMwC (cf. [1] and equation (2.3)), then the resulting experts are aggregated again via another use of MsMwC, with different parameters. The proof is a very long list of re-expressions of the regret via various existing results and additional calculations, drawing a lot of inspiration from [1], which itself improves on  techniques in [2].\n\n\n\n\n=================Post-Rebuttal=============\n\nAfter discussing with the authors, I am convinced that the presentation issues are theoretically fixable, and I still think the amount of work is adequate. Thus, I will keep my score and hope the authors fix all the minor errors as promised and try hard to make the paper more accessible to a broader audience. \n\n==============\n\n\n\n\n**References**\n\n[1]  Sijia Chen, Wei-Wei Tu, Peng Zhao and  Lijun Zhang. Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization. ICML 2023.\n\n[2] Pierre Gaillard,  Gilles Stoltz and Tim Van Erven. A Second-order Bound with Excess Losses. COLT 2014. \n\n[3]  Lijun Zhang, Guanghui Wang, Jinfeng Yi and Tianbao Yang.  A Simple yet Universal Strategy for Online Convex Optimization. ICML 2022.", "questions": "**1** Can you describe the base learner from [3] concisely?  Perhaps rewrite the main paper in a more careful way? \n\n**2** I am a bit confused about what you mean by the $O$ notation sometimes: which constants are considered to be \"$O(1)$ exactly? In page 31, it seems like $\\gamma$ is treated as a variable (not $O(1)$), but it is less clear in the case of $D$ and $G$: at the end of the proof of Lemma 10, **the $O(1)$ notation hides a term of $4DG^2$**. If you can absorb this into the $O(1)$ notation, why do you still need to write $\\gamma D^2$? I can sort of see that the reason is that there is a $\\gamma$ in there, but providing a bit of context might help. \n\n**3** Do you really mean an equal sign at the second equality (first line) describing the Adaptivity term in page 30? it seems like if $1/\\gamma<\\frac{D}{\\sqrt{1+\\bar{V_T}}}$, **the equality wouldn't hold**. More worrying still, the inequality would be in the wrong direction. \n\n**4** In lemma 3, you make the assumption that $(\\ell_{t,k -m_{t,k}})^2 =\\langle l_{t,k}-m_{t,k},p_{t,k}\\rangle^2$. Could you provide more context there? \n\n**5** Could you summarize the difference between your work and [1] more concisely? Why was the base learner [3] not used directly in [1]? What would happen if we used the correct base learner but did not use the hierarchical approach from your method? \n\n\n\n**Minor mathematical errors:** \n\n**1** I think the term  $-8\\sum_{t=2}^T \\|p_t-p_{t-1}\\|$ should be $-4\\sum_{t=2}^T \\|p_t-p_{t-1}\\|$ in Lemma 2. Indeed, the definition of \"term C\" excludes the factor of $1/2$ at the bottom of page 14 (as evidenced not just by the curly bracket but also by the use of Pinsker's inequality in line 498 as there would need to be a factor of 16 instead of 32 if the 1/2 were included): this factor of $1/2$ needs to be reintroduced in line 513 on page 16.  It would also be nice to quote Pinsker's inequality and perhaps add a citation at line 499 (page 15). \n\n**2** In the calculations on page 15, lines 497-498, at the third equality on the first line, the $b_i$ should be at the numerator instead of the denominator.  \n\n\n\n**3** In the second line of the series of equations for the optimality gap in the proof of Lemma 10 on page 30, I think it should be $\\leq$ instead of $=$ because there is a term of $-\\|x^*-\\hat{x}_{T+1}\\|^2\\frac{1}{2\\eta_T}$ which is dropped out. \n\n\n**4** In the statement of Lemma 5, it should be $\\|p-q\\|_1^2$ instead of  $\\|p-p\\|_1^2$ \n\n\n**5** In the proof of Lemma 1 on page 14, at the second line of equalities after line 482, I think it should be $\\leq $ and not $=$ because of a missing $\\langle g_T-g_{T+1},x_T-x_{T,i*}\\rangle$ term which is added to make the sum look simpler. \n\n**6** In the definitions of the iterations of $p_t$ and $q_t$ from [1] in line 486 page 14 and also in line 211 page 6, the last term should be $D(p,q_{t-1})$ instead of $D(p,q_{t})$, consistent with equation 6 in [1].  **NB**: I have used q instead of \\hat{p} due to issues with markdown.\n\n\n\n\n**Typos**\n\n\n\n\nline 7: \"the O notation\" (missing \"the\")\n\nline 146: constants=> constant\n\nline 161, same thing\n\nline 205 \"it is still open that whether..>\" ==> \"it is still an open problem to determine whether\" \n\nline 217 \"same of\" ==> \"same as\"\n\nline 252 \"same of\" ==> \"same as\"\n\nline 488: \"follows the similar logic of\" ==> \"follows a similar logic as\" \n\nline 506 \"which equals to\" ==> \"which is equivalent to\" (this somewhat changes the meaning and makes the line more understandable. Also, one might want to consider turning some of these inline equations into {align} blocks).\n\nline 739 \"it the optimal step size\" ==> \"if the optimal step size\"", "limitations": "The improvement compared to [3] is somewhat disappointing compared to the much larger complexity of the algorithm: it seems that eh main improvement is to use a single algorithm for all types of functions and to reach similar rates, with a better rate in the case of convex functions. This is interesting theoretically but the algorithm seems too unwieldy to be used in either practice or future work. \n\nI cannot fully vouch for the correctness as I often had to read the supplementary line by line without fully grasping the bigger picture. It is also hard to vouch for the originality compared to [3] as I am not familiar enough with it. Nevertheless, this seems like solid work, assuming the presentation was improved.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "This is a highly technical and long paper and it is clear the authors know what they are doing. The parts of the proofs I managed to check are generally correct with only minor typos (though they are not reader friendly).", "weaknesses": "In my opinion, the main paper is poorly written. I understand that the authors are trying to explain the intuition for why they construct their algorithm in this way, but there isn't enough context or revision of existing methods to make the paper readable. \nThe paper reads like a soliloquy of a researcher trying to solve the problem at hand: for instance, in lines 140 to 148, the authors are saying \"if we used Adapt-ML [2], bad things ill happen, what can be done about this?\" then later in Section 3, their solution is proposed, which consists in using [3] instead, with a purportedly novel choice of optimism.   \n\nSee also how the authors are using expressions like \"Another try is to\" on line 206. This is an issue not just in terms of grammar but also because it occurs in the context of a vague exposition that follows the stream of consciousness of the author rather than trying to present a cogent story.\n\n\nHere are examples of more concrete **issues with the presentation**: \n\n\n**1** There is a lot of talk in the main paper of \"how to cancel out terms\" which comes a long time before the part where the authors introduce their main algorithm. When they finally decide to do so on page 7, it is only the basic version of the algorithm (not the one with the $O(1)$ gradient calls) and it still vaguely refers to \"the base learners described in Section 2\", which I can only imagine refers to what is introduced in line 168 (section 3.1), but is still presented as new in line 177 \"to unify all kinds of functions, we propose....\"\n\n\n**2** The concept of \"optimism\" isn't properly introduced either in the main or in the supplementary; the only definition is on line 72 in the intro: \"a hyperparameter encoding historical information\", which I am given to understand means slightly different things in different algorithms. A few more words of explanation here would be nice. Definitely, the base learners should be defined properly in the main text. In the current form, not even the reference to [3] is especially clear outside of Table 1. The same goes for the section names, terms such as \"exogeneous negativity\" are not very informative. In footnote 2, the authors even speak of \"implementing $m_t$\", which is definitely very informal and should be explained more clearly. \n\n\n**3** Note also that the Bregman Divergence is note defined in lines 486 to 487 or 211-212 (page 6), despite the fact that it would make the description more complete and that it is indeed defined in the reference [1] when the same equation is introduced. \n\n**4** In the proof of Lemma 2, the first equation is hard to understand without background in the field. the only explanation is \"by standard analysis of optimistic OMD\". It would be nice to say that this refers specifically to Theorem 1 of [4], which is explained better later in the appendix when the argument arises again (line 767 page 30). Since it is natural for the reader to read the proof of Lemma 2 first, the more detailed explanation should be present there as well. \n\n**5** Similarly, the proof of Lemma 1 on page 14 uses equation E.1 from page 29, which is completely unnecessary as E.1. is derived from first principles. \n\n**6** The proof of Lemma 2 is done for \"an arbitrary comparator $u\\in\\Delta$, but the concept of comparator isn't really defined there, though it becomes clear from context after some effort. This also seems to run counter to the fact that in the main paper the authors write elsewhere in the paper that they \"focus on the proof for fixed learning rate\", which seems not to be the case in the case of the proof of Lemma 2. \n\n**7** What does the notation $\\|.\\|_{U_t}$ mean on line 761? Is it explained somewhere? \n\n\n\n\nI understand that I am not an expert in the field and my difficulties understanding the bigger picture is mostly due to this, but I do feel like in the case of well written papers, I am often able to make better progress, in less time, towards understanding more complex papers than this one in equally distant areas. However, I am not sure, it may be that the prerequisites are intrinsically larger.\n\n\n\n**References**\n\n[1]  Sijia Chen, Wei-Wei Tu, Peng Zhao and  Lijun Zhang. Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization. ICML 2023.\n\n[2] Pierre Gaillard,  Gilles Stoltz and Tim Van Erven. A Second-order Bound with Excess Losses. COLT 2014. \n\n[3]  Lijun Zhang, Guanghui Wang, Jinfeng Yi and Tianbao Yang.  A Simple yet Universal Strategy for Online Convex Optimization. ICML 2022. \n\n[4]   Zhao, Peng ; Zhang, Yu-Jie ; Zhang, Lijun ; Zhou, Zhi-Hua.  Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization. ArXiv. May 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable feedback and very careful check of our paper! We will carefully revise it according to the mentioned points. Due to the 6,000-character limit of this year's rebuttal, we first answer your questions about [Chen et al., 2023] and [Zhang et al., 2022] and then respond to presentation/typo issues and other questions in the next reply after the reviewer-author discussion begins.\n\n---\n\n**Q1**. Can you describe the base learner from [Zhang et al., 2022] concisely? Perhaps rewrite the main paper in a more careful way?\n\n**A1**. We appreciate your question, and thanks for the suggestion. We will give a more detailed formalization in the revised version. Below we provide a comprehensive explanation for it.\n\nSpecifically, we consider the problem where the kind (strongly convex, exp-concave, or convex) and curvature coefficient (value of $\\alpha$ or $\\lambda$) of the functions are unknown. Ideally, the best base learner is the one that runs the algorithm for the right function type and the accurate guess of the curvature coefficient. Since both of them are unknown in our problem, we employ multiple base learners to hedge the uncertainty. The key to the problem is designing a meta algorithm to effectively track the best base learner. \n\nSpecifically, we set *one* base learner to run an algorithm for convex functions (only one is needed since there is no curvature coefficient here). For the rest two cases, e.g., for exp-concave functions, since the value of $\\alpha$ is unclear, we discretize its potential range $[1/T,1]$ into $O(\\log T)$ values ($\\mathcal{H}$ in Line 128) and select one of them as a guess. In total, we require $O(\\log T)$ base learners for the exp-concave case, all of which execute an algorithm for exp-concave functions but with *varying guesses* of the value of curvature coefficient $\\alpha$. A similar arrangement also applies to strongly convex functions.\n\n---\n\n**Q2**. Could you summarize the difference between your work and [Chen et al., 2023] more concisely? Why was the base learner [Zhang et al., 2022] not used directly in [Chen et al., 2023]? What would happen if we used the correct base learner but did not use the hierarchical approach from your method?\n\n**A2**. Thanks for the question. We compare with [Chen et al., 2023] from the following aspects:\n\n* **Difference:** the two works focus on *different problems*. Specifically, ours considers obtaining gradient-variation bounds in the universal problem. While theirs studied the *stochastically extended adversarial (SEA)* model, an interpolation between stochastic and adversarial OCO. Since the base learners in [Zhang et al., 2022] are employed to deal with the universal problem, they cannot be used directly in [Chen et al., 2023].\n* **Similarity:** one similarity is that both works consider three kinds of functions (strongly convex, exp-concave, and convex). Thus, our analysis of *base learners' negative terms* has some parallels with theirs, which are also *standard* in optimistic online learning.\n* **Application:** our method can be applied to their problem with nearly optimal universal results due to the profound connection between the gradient variation and the SEA model, resolving a *major open problem* therein (see their conclusion for the open problem).\n\n---\n\n**Q3**. The improvement compared to [Zhang et al., 2022] is somewhat disappointing compared to the much larger complexity of the algorithm... This is interesting theoretically, but the algorithm seems too unwieldy to be used in either practice or future work.\n\n**A3**. Thanks for the feedback. While our algorithm might appear complex, it stands as the *first* to achieve gradient-variation bounds for the universal problem --- an *open problem* identified by [Zhang et al. 2022]. The improvement over [Zhang et al. 2022] is significant, not only due to the importance of the gradient-variation quantity itself but also because the improvement from $T$ to $V_T$ is *polynomial* for convex functions, whereas *logarithmic* in the rest cases (as stated in Line 69). Furthermore, our results can be applied to various learning problems, encompassing the *stochastically extended adversarial (SEA)* model and *games* (Appendix A). In doing so, we tackle a *major open question* posited by [Chen et al., 2023]. Please refer to Table 3 and Table 4 on Page 13 for an overview of our results in the aforementioned applications.\n\nThe complexity of our three-layer method arises primarily because, to our knowledge, *only MsMwC* can yield the desired negative terms for cancellations (also one of our technical contributions) while securing a second-order regret bound. In the future, we will focus on obtaining the same rates with a two-level structure. A possible solution is to explore the negative stability terms in other meta algorithms (e.g., Adapt-ML-Prod). We will include a discussion on these future directions, especially concerning computational efficiency, in the updated version.\n\n---\n\nWe believe that our work offers valuable contributions to the community. We hope the above replies will address your concerns and would appreciate a reevaluation of our paper's score. And we are happy to provide further clarifications if needed in the following author-reviewer discussions.\n\nWe also take this opportunity to sincerely thank you for the careful review, including the thorough examination of the proofs! Your suggestions are very insightful and important for further improving the paper."}, {"review_id": "B8AGjPkkOr", "reviewer": "Reviewer_wYJC", "summary": "This paper proposes algorithms that have data-dependent regrets and adaptive to the loss function classes. The algorithm improves on Zhang et al., 2022 in the sense that 1) it also achieves a gradient variation bound for convex Lipschitz losses and 2) it requires only one gradient evaluation at each round. The first is achieved by the introduction of optimism. The second is achieved by appropriately designed surrogate functions for the base learners. \n\n---\n\nThe authors have addressed my questions. I keep the original rating.", "questions": "Please address the first two weaknesses and the possible typo in Ln. 125.", "limitations": "This is a theory paper. All assumptions are explicitly written. The potential issue regarding the computational complexity has been raised in the weakness block above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The algorithm is new and improves on Zhang et al., 2022 (see the summary). \n2. The paper clearly addresses the ideas behind algorithm design and analysis.", "weaknesses": "1. **Comparison of complexity.** Please also compare the number of the instances of the base learners required for each algorithm in Table 1. This information helps evaluate the computational complexity. \n2. **Algorithm 1.** It is said that the base learners are set \"as specified in Section 2,\" but Section 2 (preliminaries) does not give any algorithm. \n1. **Presentation.**\n    - Section 4 is presented in a hasty way. The reader may not be able to understand the ideas without reading Appendix C. \n    - Table 1: The Lipschitzness and smoothness assumptions are missing. The assumptions may not hold in, e.g., online portfolio selection. \n    - Ln. 35: That \"the learner requires to know the function information (type and curvature) in advance to select suitable algorithms\" only holds for textbook OCO algorithms and not general OCO. \n    - The three aspects in Ln. 57--60 can be skipped as that will be addressed in detail in Ln. 79--89. \n    - Ln. 58: The term \"small-loss bound\" has not been explained before. It is better to explain it as the term is not common sense to general machine learning researchers. \n    - Ln. 125: That $N \\approx 1 + \\log T + \\log T$ looks weird. Perhaps there is some typo. \n2. **Typos.**\n    - Ln. 57: aspect*s*\n    - Ln. 219: *for* our purpose", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable feedback and appreciation of our work! Given that all three questions (computational complexity, base learners setup, and number $N$) relate to the base learner configuration, we provide a comprehensive explanation for it first, followed by the answers to your questions.\n\n---\n\n**Base learner setup:** we are addressing a problem where both the type (strongly convex, exp-concave, or convex) and curvature coefficient (value of $\\alpha$ or $\\lambda$) of the functions are unknown. Ideally, the best base learner is the one that runs the algorithm for the right function type and the accurate guess of the curvature coefficient. Since both of them are unknown in our problem, we employ multiple base learners to hedge the uncertainty. The key to the problem is designing a meta algorithm to effectively track the best base learner.\n\nSpecifically, we make *one base learner run an algorithm for convex functions* (only one is needed since there is no curvature coefficient here). For exp-concave and strongly convex functions, where the curvature coefficient's value is unknown, we employ multiple (the number will be illuminated later) base learners for each case. They all run an algorithm for the corresponding function type but with different guessed values for the curvature coefficient. Concretely, we discretize the possible range $[1/T,1]$ of $\\alpha$ and $\\lambda$ into $\\lceil \\log_2 T \\rceil$ values ($\\mathcal{H}$ in Line 128) and choose one of them as a guess. Overall, we need *$\\lceil \\log_2 T \\rceil$ base learners for exp-concave and strongly convex functions*. Therefore, we use $N = 1 + \\lceil \\log_2 T \\rceil + \\lceil \\log_2 T \\rceil = O(\\log T)$ base learners.\n\n---\n\n**Q1**. Please also compare the number of instances of the base learners required for each algorithm in Table 1.\n\n**A1**. Thanks for the suggestion. Previous works employ a *two-layer* structure, necessitating $O(\\log T)$ base learners. Our method leverages a *three-layer* structure and thus requires $O(\\log^2 T)$ base learners. We will include this information in the revised version.\n\n**Q2**. It is said that the base learners are set \"as specified in Section 2,\" but Section 2 (preliminaries) does not give any algorithm.\n\n**A2**. Thanks for the question. The base learner setup is provided in Lines 125-129 and please refer to the description above Q1 for more details. We will give a more detailed formalization in the revised version.\n\n**Q3**. Ln. 125: That $N \\approx 1 + \\log T + \\log T$ looks weird. Perhaps there is some typo.\n\n**A3**. We appreciate your observation. It is not a typo. We represent $N$ as the *sum of three components* to denote the number of base learners needed for different kinds of functions. Specifically, one for convex functions (which don't have a curvature coefficient), and $O(\\log T)$ for both exp-concave and strongly convex functions due to their unknown curvature coefficient.\n\n---\n\nWe are grateful for your meticulous review and will carefully revise the mentioned presentation issues and typos to enhance the paper's readability."}, {"review_id": "DkxRujUpNA", "reviewer": "Reviewer_osvq", "summary": "This paper put together and designed new techniques to reach a high level of adaptivity in online convex optimization. It is a timely contribution that is useful to put together various algorithms optimal for different problem setups and to better adapt to the characteristic of each setup.", "questions": "No question.", "limitations": "None.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is an excellent paper in presenting the results and the qualitative explanation of the techniques or proofs. The adaptivity contribution of the paper is also very satisfying in terms of general knowledge of machine learning.\n", "weaknesses": "I do not see any weakness in this paper. However, I have not checked the proofs in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable feedback and appreciation of our work! We believe that our research occupies a nonnegligible position in universal online learning, especially given the significance of the gradient-variation quantity coupled with the novel techniques we've introduced.\n\nThe gradient variation is a fundamental problem-dependent quantity in modern online learning, largely due to its profound connections with both stochastic/adversarial OCO and games. As a result, our work finds broad application scope in these fields by obtaining universal algorithms with nearly optimal guarantees therein.\n\nMoreover, the techniques we've developed, such as the cascaded correction terms, the negative terms in MsMwC, and the meta-base regret decomposition with customized surrogate functions, are poised to capture the interest of the broader community and potentially spark further innovations."}, {"review_id": "H2YkLQkkrQ", "reviewer": "Reviewer_rs9j", "summary": "   In this work, the authors aim to develop an algorithm for online convex optimization that can adapt to the specific curvature of the loss function without knowing it in advance. The goal is to develop an algorithm that can adapt to strongly convex, exp-concave and convex loss functions dynamically, while also deriving some problem-dependent guarantees. They also ensure that their method is computationally efficient as it only requires one gradient query per round.\n\nTo do so, they present a three layer algorithm that estimates both the type of loss functions and its parameters. Crucially, this kind of multi-layer approach generally comes at the cost of logarithmic factors. These three algorithms follow pre existing structures (MSMWC (Chen et al. 2021) for the meta algorithms and an optimistic Online Mirror Descent for the base algorithm) but the authors rely on several tricks and refinements of the analysis to exploit negative terms in the regret analysis and obtain competitive regret bounds. \n\nFinally, they also provide a novel decomposition of the regret which allows to reduce the number of gradients queries from $O(\\log^2 T)$ to $O(1)$ at each round. This result is of independent interest, as they show that it can be used with different meta algorithms, such as Adapt-ML-Prod (van Erven and  Koolen 2016) to recover worst-case guarantees (whereas the main results of the paper are stated in terms of problem dependent terms). ", "questions": "Could you discuss if and how you think these results could be further improved? ", "limitations": "NA", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper provides significant contributions to the field of OCO. Achieving optimal results simultaneously across several environments has been an important topic in learning theory in the past few years, and, by providing universal guarantees, this paper fits in this line of work. The presented algorithm builds upon existing results and provides non-trivial improvements to their analysis. These technical contributions are interesting and likely to be build upon in the future. \n\nIt is worth noting that this paper is particularly well written. The body of the paper focuses on providing detailed explanations for the choice of methods, and the authors take a particular care in higlighting the connections and differences with the rest of the litterature. Discussionss such as in Section 3.2.1 which highlight the different approaches that could have been considered and were discarded are not that common and should be encouraged. The proofs, deferred to the appendix, are clear and detailed. Appendix A provides several applications for the results, showing that the method can be used to bridge the gap between stochastic and adversarial online convex optimization and for two-player zero-sum games. In both cases, the proposed algorithm obtains regret bounds that are at least matching up to log-factors and sometimes improving upon the state of the art while considering a broader setting.", "weaknesses": "While many comparisons with other results in the litterature have been provided, it would be interesting to get comparisons with lower bounds, in particular for the small loss bounds that depend in F and V. \nAs the results achieved by the current method are matching these of Zhang et al. (2022), though with a better runtime complexity, it could also be interesting to get experimental results to compare them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the constructive feedback and appreciation of our work! Below we answer your questions on the lower bounds and the possibility of further improvements.\n\n**Q1**. It would be interesting to get comparisons with lower bounds, in particular for the small loss bounds that depend in F and V.\n\n**A1**. Thanks for the insightful suggestion. The optimal bounds for convex functions are $O(\\sqrt{V_T})$ and $O(\\sqrt{F_T})$. For exp-concave and strongly convex functions, the optimal results are $O(\\ln V_T)$ and $O(\\ln F_T)$, with an additional dimension dependence for exp-concave functions. For more details,  please refer to Lemma 9 of [1] and Corollary 3 of [2]. We will add a corresponding discussion in the next version.\n\n**References:**\n\n[1] Online Optimization with Gradual Variations, COLT 2012\n\n[2] Beyond Logarithmic Bounds in Online Learning, AISTATS 2012\n\n---\n\n**Q2**. Could you discuss if and how you think these results could be further improved?\n\n**A2**. Thanks for the question. An open problem left in our work is to *achieve the optimal regret bound for convex functions* (by removing the extra $\\ln V_T$ factor) *while attaining the current optimal rates for exp-concave and strongly convex ones.* In the future, we will investigate whether this term can be removed either by novel modifications and analysis of the MsMwC algorithm or by exploring the negative stability terms in other meta algorithms (e.g., Adapt-ML-Prod). We will include this discussion on future directions in the next version.\n\n---\n\nWe believe that our research occupies a nonnegligible position in universal online learning, especially given the significance of the gradient-variation quantity coupled with the novel techniques we've introduced. In the end, thanks again for recognizing the importance and contributions of our work."}]

Author rebuttal:

Meta-review: Strengths:
The primary strength of this paper lies in its contribution to the field of online learning. The novel algorithm presented in this work has the potential to advance the state-of-the-art by significantly improving regret bounds. This innovation is a commendable achievement and undoubtedly contributes to the academic community's knowledge in this area.

Weaknesses:
Despite the remarkable contribution, it is evident that there are several areas in the paper's presentation that require attention in order to enhance its overall readability and accessibility. Both Reviewer ZhYs and Reviewer wYJC have aptly pointed out various presentation-related aspects that could be improved to make the paper more reader-friendly and comprehensible. These issues include clarity in explanations, organization of content, and the need for more detailed examples or illustrations to aid in understanding.

Recommendation:
Considering the strengths and weaknesses outlined above, I am inclined to recommend the acceptance of this paper. The condition for acceptance is that the authors should diligently address the feedback provided by Reviewer ZhYs and Reviewer wYJC. This includes improving the clarity of explanations, reorganizing the content for better flow, and incorporating additional examples or illustrations where necessary. By addressing these concerns, the paper's overall quality can be significantly enhanced.
Decision: Accept (spotlight)