Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions
Authors: Lijun Zhang
Guanghui Wang
Wei-Wei Tu
Wei Jiang
Zhi-hua Zhou
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online Convex Optimization
Adaptive Regret
Convex Functions
Strongly Convex Functions
Exponentially Concave Functions

Abstract: To deal with changing environments, a new performance measure—adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existing algorithms lack universality in the sense that they can only handle one type of convex functions and need apriori knowledge of parameters. By contrast, there exist universal algorithms, such as MetaGrad, that attain optimal static regret for multiple types of convex functions simultaneously. Along this line of research, this paper presents the first universal algorithm for minimizing the adaptive regret of convex functions. Specifically, we borrow the idea of maintaining multiple learning rates in MetaGrad to handle the uncertainty of functions, and utilize the technique of sleeping experts to capture changing environments. In this way, our algorithm automatically adapts to the property of functions (convex, exponentially concave, or strongly convex), as well as the nature of environments (stationary or changing). As a by product, it also allows the type of functions to switch between rounds.


Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions
Lijun Zhang', Guanghui Wang", Wei-Wei Tut, Wei Jiang", Zhi-Hua Zhou"
"National Key Laboratory for Novel Software Technology. Nanjing University, Nanjing, China
14Paradigm Inc., Beijing 100000, China
{zhanglj, wanggh, jiangu, zhouzh} nju- edu.cn, tuwwcn@gmail.cm com
Abstract
To deal with changing environments, new performance measure adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existing algorithms lack universality in the sense that they only handle one type of convex functions and need apriori knowledge parameters. By contrast, there exist universal algorithms, such MetaGrad, that attain optimal static regret for multiple types of convex functions simultaneously. Along this line of research, this paper presents the firs! universal algorithm for minimizing the adaptive regret of convex functions. Specifically, we borrow the idea maintaining multiple learning rates in MetaGrad to handle the uncertainty of functions, and utilize the technique of sleeping experts to capture changing environments. In this way, our algorithm automatically adapts the property of functions (convex, exponentially concave, or strongly convex), as well as the nature of environments (stationary or changing). As a by product, it also allows the type of functions switch between rounds.
Introduction
Online learning aims to make a sequence of accurate decisions given knowledge of answers to previous tasks and possibly additional information SShalev-Swwrtz/ 2011]. sequence of consecutive rounds, where at round the learner is asked to select a decision w, from a domain Ω. After submitting the answer, loss function ft Ω R is revealed and the learner suffers a loss fe(w)). The standard performance measure the regret (Cesa-Bianchi and Lugosi 2006
performed in
Regret (T)
Σ fs(w.) min wEn
E((w)
defined the difference between the cumulative loss of the online learner and that of the best decision chosen in hindsight. When both the domain 52 and the loss fe(.) are convex, becomes online convex optimization (OCO) [Zinkevich] 2003
In the literature, there exist plenty algorithms to minimize the regret under the setting of OCO Hazan 2016). However, when the environment undergoes many changes, regret may not be the best measure performance. That is because regret chooses fixed comparator, and for the same reason, is also referred to static regret. To address this limitation, Hazan and Seshadhri [2077] introduce the concept of adaptive regret, which measures the performance with respect to a changing comparator. Following the terminology of Daniely et al. (2055), we define the strongly adaptive
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

regret as the maximum static regret over intervals of length T, i.e.,
p+t-1
p+r-1
SA- (A-
max
Σ fe(we)
min wesl
Σ fi(w)) t=p
(I)
bapt [[(
Since the seminal work of Hazan and Seshadhri [2007] several algorithms have been successfully developed to minimize the adaptive regret of convex functions, including general convex, exponenti- ally concave (abbr. exp-concave) and strongly convex functions [Hazan and Seshadhri 2009. Jun
ict al., 2017a| Zhang et al. 2018b]. However, existing methods can only handle one type of convex functions. Furthermore, when facing exp-concave and strongly convex functions, they need to know the moduli of exp-concavity and strong convexity. The lack of universality hinders their applications to real-world problems.
On the other hand, there do exist universal algorithms, such as MetaGrad [van Erven and Koolen 2016], that attain optimal static regret for multiple types of convex functions simul tamuuuanl This observation motivates us to ask whether is possible to design a single algorithm to minimize the adaptive regret of multiple types of functions. This is very challenging because the algorithm needs to enjoy dual adaptivity, adaptive to the function type and adaptive to the environment. In this paper, we provide an affirmative answer by developing Universal algorithm for Minimizing the Adaptive regret (UMA), First, inspired by MetaGrad, UMA maintains multiple learning rates to handle the uncertainty of functions. In this way, it supports multiple types of functions simultaneously and identifies the best learning rate automatically. Second, following existing studies on adaptive regret, UMA deploys sleeping experts [Freund al. 1997] to minimize the regret over any interval, and thus achieves a small adaptive regret and captures the changing environment.
The main advantage of UMA is that it attains second-order regret bounds over any interval. As result, it can minimize the adaptive regret of general convex functions, and automatically take advantage of easier functions whenever possible. Specifically, UMA attains O(vT T") O log log 7') and O log r log 7) strongly adaptive regrets for general convex, c-exp-concave and X-strongly convex functions respectively, where d is the dimensionality. All of these bounds match the state-of-the- results on adaptive regret [Jun et al., 2017a] Zhang et al., 2018b) exactly. Furthermore, UMA can also handle the case that the type of functions changes between rounds. For example, suppose the online functions are general convex during interval Z1, then become a-exp-concave in 12, and finally switch to >-strongly convex in Iz. When facing this function sequence, UMA achieves O( ((v[I1 TogT). a log log 7) and O log [T] log 7) regrets over intervals J1, 12 and J3, respectively.
O d
2 Related work
We briefly review related work on static regret and adaptive regret, under the setting of OCO.
2.1 Static regret
To minimize the static regret of general convex functions, online gradient descent (OGD) with step size n7 = O(1/vt) achieves an O(vT) bound [Zinkevich] 2003]. If all the online functions are A-strongly convex, OGD with step size ne- = O(1/ | attains an O 3 log 2`) bound Shalev-Shwarte et al. 2007 When the functions are a-exp-concave, online Newton step (ONS). with knowledge of a. enjoys an O( log 2') bound, where dl is the dimensionality [Hazan et al. 2007). These regret bounds are minimax optimal for the corresponding type of functions (Abernethy et al.) 2008 but choosing the optimal algorithm for a specific problem requires domain knowledge.
The study of universal algorithms for OCO stems from the adaptive online gradient descent (AOGD)
[Brrlettt et al.] 2008) and its proximal extension [Do et al. 2209]. The key idea of AOGD is to add quadratic regularization term to the loss. Bartlett et al. 2008 demonstrate that AOGD is able
to interpolate between the O(VT) bound of general convex functions and the Olog T) bound of strongly convex functions. Furthermore, it allows the online function to switch between general convex and strongly convex. However, AOGD has two restrictions:
It needs to calculate the modulus of strong convexity on the fly, which is a nontrivial task; It does not support exp-concave functions explicitly, and thus can only achieve a suboptimal O(VT) regret for this type of functions.
2

---

Another milestone is the multiple eta gradient algorithm (MetaGrad) [van Erven and Koolen 2016 Mhammedi et al.) 2019, van Erven al. 202T], which adapts to a much broader class of functions, including convex and exp-concave functions. MetaGrad's s main feature is that it simultaneously considers multiple learning rates and does not need to know the modulus of exp-concavity. MetaGGra achieves O( D(VTlog log log and O ((4 log 7') regret bounds for general convex and a-exp-concave functions, respectively. However, it suffers the following two limitations:
MetaGrad treats strongly convex functions exp-concave, and thus only gives suboptimal
( log 7) regret for X-strongly convex functions; It assumes the type of online functions, as well as the associated parameter, does not change
between rounds.
The first limitation of MetaGrad has been addressed by Wang al. (019), who develop a universal algorithm named as multiple sub-algorithms and learning rates (Maler). It attains O(VT). O a log T) and O( J log T) regret bounds for general convex, a-exp-coneave, and X-strongly convex functions, respectively. Furthermore, Wang et al. [2020] extend Maler to make use of smoothness. However, the second limitation remains there.
2.2 Adaptive regret
Adaptive regret has been studied in the setting of prediction with expert advice Littlestone and
Warmuth 1994 Freund et al., 1997 |Adamskiy al., 2012 György et al.] 2012 Luo and Schapire 2013] and OCO [Hazan and Seshadhri [2007] Daniely et al. 2015 Jun et al. [011 7a In this section, we focus on the related work the latter one.
Adaptive regret is introduced by Hazan and Seshadhri 2007]. and later refined by Daniely et al. (2015). To distinguish between them, we refer to the definition of Hazan and Seshadhri as weakly adaptive regret:
q Σ f((w)) [ 1=p
WA- (T) =
max
min WEit
Σ f((w) t=p
For a-exp-concave functions, Hazan and Seshadhri [007]] propose an adaptive algorithm named as Follow-the-Lcading Histtry (FLH). FLH restarts a copy of ONS in each round as an expert, and chooses the best one using expert-tracking algorithms. The meta-algorithm used to track the best expert is inspired by the Fixed-Share algorithm [Herbster and Warmuth 1998]. While FLH is equipped with an O d log T) weakly adaptive regret, it is computationally expensive since needs to maintain / experts in the 1-th iteration. To reduce the computational cost, Hazan and Seshadhri 2007] further prune the number of experts based on a data streaming algorithm. In this way, FLH only keeps Ollg t) experts, at the price of an O (dd log" T) weakly adaptive regret. Notice that the efficient version of FLH essentially creates and removes experts dynamically. As pointed out by Adamskiy et al. [2012], this behavior can be modeled by the sleeping expert setting [Freund et al.. 1997], in which the expert can be "asleep" for certain rounds and does not make any advice.
For general convex functions, we can use OGD as the expert-algorithm in FLH. Hazan and Seshadhri (007)] prove that FLH and its efficient variant attain O OVyTlog and O(VTlog" T) weakly adaptive regrets, respectively. This result reveals a limitation of weakly adaptive regret-ir it does not respect short intervals well. For example, the O(yTlogT) regret bound is meaningless for intervals of length O(VT). To address this limitation, Daniely et al. (2015) introduce the strongly adaptive regret which takes the interval length as a parameter, as shown in (T). They propose a novel meea-algorithm, named as Strongly Adaptive Online Learner (SAOL). SAOL carefully constructs a
set of intervals, then runs an instance of low-regret algorithm in each interval as an expert, and finally combines active experts' outputs by variant of multiplicative weights method [Arora et al. [0022]
SAOL also maintains Olog t) experts in the t-th round, and achieves an O log T') strongly adaptive regret for convex functions. Later, Jun et al. [2017a] develop new meta-algorithm named as sleeping coin betting (SCB), and improve the strongly adaptive regret bound to ( T).
Very recently, Cutkosky (2020) proposes a novel strongly adaptive method, which can guarantee the ((vT log T') bound in the worst case, while achieving tighter results when the square norms of gradients are small.
3

---

For A-strongly convex functions, Zhang et al. 2018b] point out that we can replace ONS with OGD, and obtain an O( log weakly adaptive regret. They also demonstrate that the number of active experts can be reduced from / to Oloog (), at cost of an additional log 7 factor in the regret. All the aforementioned adaptive algorithms need to query the gradient of the loss function at least O times in the 1-th iteration. Based on surrogate losses, Wang et al. [2018) show that the number of gradient evaluations per round can be reduced to without affecting the performance. When we have prior knowledge about the change of environments, it is also possible to improve the logarithmic factor in the adaptive regret [Wan et al. 2021]
2.3 Dynamic regret
Another metric for dealing with changing environments is dynamic regret, which compares the cumulative loss of the online learner against a sequence of decisions (Zinkevich] 2003 Jadbabaie et al. 2015 Besbes et al. 20155 Yang et al. 2016 Zhang et al. 2017 2018a]. Although we can upper bound dynamic regret by adaptive regret, the results are usually suboptimal (Zhang et 2018b Cutkosky 2020 Baby and Wang 2021]. For more discussions, please refer to Zhang 2020
2020
3 Main results
We first present necessary preliminaries, including assumptions, definitions and the technical chal- lenge, then provide our universal algorithm and its theoretical guarantee.
3.1
Preliminaries
We introduce two common assumptions used in the study of OCO Hazan 2016].
Assumption
The diameter of the domain Qt is bounded by D, i.e.,
max | yll D.
(2)
x.yE
Assumption The gradients of all the online functions are bounded by G, i.e.,
max
[V[[()]] s G, E
(3)
WER2
Next, state definitions of strong convexity and exp-concavity (Boyd and Vandenberghe Cesa-Bianchi and Lugosi 2006).
2004
Definition A function f Ω R is X-strongly convex if
f(y) 2 f(x) + (Vf(x). x) fly x112 Vx,y E Q.
Definition A function f : + is a-exp-concave if
is concave over Ω
The following property of exp-concave functions will used later (Hazan al. 2007 Lemma 3].
Lemma For a function f Q + R, where Ω has diameter D. such that Vw e Ω IIV < G and (x))-af(() is concave, the the following holds for min dainaad:oo at):
3
f(y) 2 f(x) (Vf(x).) x) (Vf(x), x)2, Vx,y
3.1.1 Technical challenge
Before introducing the proposed algorithm, we discuss the technical challenge of minimizing the
adaptive regret of multiple types of convex functions simultaneously. Existing adaptive algorithms [aaaan and Seshadhri 2007 Daniely et al.) 2013 Jun et al., 2017a Zhang et al. 2018b] share the
same framework and contain 3 components:
An expert-algorithm, which is able to minimize the static regret of specific type of functions;

---

A set of intervals, each of which is associated with an alpert-agoorihm that minimizes the regret of that interval:
A meta-algorithm, which combines the predictions of active experts in each round.
To design universal algorithm, straightforward way is to universal method for static regret, such as MetaGrad [yan Erven and Koolen 2016], as the expert-algorithm. In this way, the expert- algorithm is able to handle the uncertainty of functions. However, the challenge lies in the design of the meta-algorithm, because the mneta-aggorithms used by previous studies also lack universality. For example, the meta-algorithm Hazan and Seshadhri [007] able to deliver a tight meta-regret for exp-concave functions, but loose one for general convex functions. Similarly, meta- meta-algorithms of Daniely al. (2015) and Jun et al. [017a]] incur at least ((vF) meta-regret for intervals of length т, which is tolerable for convex functions but suboptimal for exp-concave functions.
To address the above challenge, we have found two different solutions.
1. In the first approach, we dig into MetaGrad and modify it to minimize the adaptive regret directly. MetaGrad itself is two-layer algorithm, which runs multiple expert-algorithms. each with a different learning rate, and combines them with a meta-algorithm named as Tilted Exponentially Weighted Average (TEWA). To address the aforementioned challenge, we extend TEWA to support sleeping experts so that it can minimize the adaptive regret. The advantage of TEWA is that its meta- meta-regret only depends the number of experts instead of the length of the interval, e.g., Lemma 4 of van Erven and Koolen (2016). and thus does not affect the optimality of the regret.
2. In the second approach, we use an existing universal method (e.g., MetaGira or Maler) as the expert-algorithm, and change the meta-algorithm. Inspired by recent universal strategy for OCO [Zhang et al., 2021). we choose
aoea--aggriitm that enjoys second-order bounds with excess losses [Gaillard al., 2014 Koolen and Erven 2015 Wintenberger 2017 Mhammedi et al. 2019). and use the linearized loss to measure the performance of experts. In this way, the meta-algorithm can exploit strong convexity and exponential concavity, and suffers small meta-regret. While the first approach remains a two-layer algorithm, the second one is three-layer.
Due to the limitation of space, we only present the first approach in this conference paper, and will elaborate the second one in extended version.
3.2 A prrameter-free and adaptive algorithm for exp-concave functions
Recall that our goal is to design a universal algorithm for minimizing the adaptive regret of general convex, exp-concave, and strongly convex functions simultaneously. However, to facilitate under- standing, we start with simpler question: How to minimize the adaptive regret of exp-concave functions, without knowing the modulus of exp-concavity? By proposing a novel algorithm answer the above question, we present the main techniques used our paper. Then, we extend that algorithm to support other types of functions in the next section. Since our algorithm is built upon MetaGradd, we first review its key steps below.
3.2.1 Review of MetaGrad
The reason that MetaGrad can minimize the regret of a-exp-concave functions without knowing the value of because it enjoys a second-order regret bound:
T
T
T
Σ ((w))
Σ f((w) & fe..). w. w) w0 (Vrrdlog + dlog T)
(4)
1=1
where V/ = Et (V(()))) We w Besides, Lemma iimplies
3 Σ (V[((w:)) w. w)?
E.(w) ((w)= (V..(.:), w.
(5)
Combining with 5 and applying the AM-GM inequality, we immediately obtain
T T
fe(w.) Σ fi(w) = o ( log logT) =o =0(") ca log )
[=1
5

---

t
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
I[
I[
I[
][
][
I[
][
][
1[
][
][
][
][
1[
10
1
I[
1[
][
1[
1[
][
1
[
][
][
I
][
I
Figure Geometric covering (GC) intervals of Daniely et al. 2015
From the above discussion, it becomes clear that we can establish a second-order regret bound for any interval [p. _ [T], able minimize the adaptive regret even when is unknown.
The way that MetaGrad attains the regret bound in 4 is to run set of experts, each of which minimizes surrogate loss parameterized by learning rate
(w) (V w, w) ry (W(e). W. w)?
(6)
and then combine the outputs of experts by meta-algorithm named as Tilted Exponentially Weighted Average (TEWA). Specifically, it creates expert E" for each y in
{ 2-
S(T)
=
logz [T
5DG
and thus maintains 1+12 log2 7| = (log experts during the learning process. By simultaneously considering multiple learning rates, MetaGrad able to deal with the uncertainty of Vr. Since the surrogate loss e7 (-) is exp-concave variant of ONS is used as the expert-algorithm. Let w be the output of expert E in the 1-th round. MetaGrad calculates the final output W, according TEWA:
Σn T' W.
En 7.
where nạ x exp(- -1= (w?)).
3.2.2 Our approach
In this section, we discuss how to minimize the adaptive regret by extending MetaGrad. Following the idea of sleeping experts [Freund et al. 1997). the most straightforward way is create - [ lg + 1)] experts for each interval p.. q E [T']. and combine them with a meta-algorithm that supports sleeping experts. However, this simple approach is inefficient because the total number of experts is on the order of O log T). To control the number of experts, we make use of the geometric covering (GC) intervals (Daniely al. 2015) defined as
I=
U It
kENUYO)
where
Is (i-
..eeNN.NNNN Nu
A graphical illustration of GC intervals is given in Fig. 1 We observe that each Z, is partition of [1,..., ,2 - (1)m fly, so we do not need to fix the horizon T. We note that similar intervals have been proposed by
1} to consecutive intervals of length 2 The GC intervals can be generated on the
Veness et al. (2013).
Then, we only focus on intervals in Z. For each interval = [r, s] E I, we will create 1+ [+[ logg r + 1)] experts, each of which minimizes one surrogate loss in { (w)ly E S(s + 1)} during I, where (-) and S(-) are defined in (6) and (7). respectively. These experts become active round and will be removed forever after round s. It is easy to verify that in each round t, the number of intervals that contain is [log, t| + [Daniely et al. 2015). and thus the number of active experts
at most
[1
logz 1)
(logz t| + 1)
O(log t).
2
So, the number of active experts larger than that of MetaGGrd by a logarithmic factor, which the price paid in computations for the adaptivity to every interval.

---

Algorithm 1 A Parameter-free and Adaptive algorithm for Exp-concave functions (PAE)
1: Ao 0
2: for t = 1 to do
3: for all I E II that starts from do
4:
for all 17 E S((Z) do
5:
Create an expert E7 by running the slave algorithm of MetaGrad minimize (?) during
I, and set 1- = 0
6:
Add Ey to the set of active experts: A A U {E}}
7: end for
8:
end for
9:
Receive output wh,, from each expert E E At
10:
Submit w, in 4
11:
Observe the loss f-(.) and evaluate the gradient V (w())
12:
for all Ey E A: do
13:
Update -", - f7 (w(2))
14: Pass the surrogate loss (.) expert Fy
15:
end for
Remove experts whose ending times are from A
17: end for
Finally, need to specify how to combine the outputs of active experts. From the construction of the surrogate loss in (6). we observe that each expert uses its own loss, which is very different from the traditional setting of prediction with expert advice in which all experts use the same loss. As result, existing meta-algorithms for adaptive regret [Daniely et al. 2015 Jun et al.) 2017a], which assume a fixed loss function, cannot be directly applied. In the literature, the setting that each expert uses a loss function that may be different from the loss functions used by the other experts has been studied by Cherno and Vovk [2009), who name it as prediction with expert evaluators' advice. Furthermore, they have proposed a general conversion to the sleeping expert case by only considering active rounds in the calculation of the cumulative losses. Following this idea, we extend TEWA to sleeping experts.
Our Parameter-fiee free and Adaptive algorithm for Exp-concave functions (PAE) is summarized in Algorithm [ In the t-th round, we first create an expert E7 for each interval I E I that starts from I and each 17 E S(Zl).. where S(.) is defined in (7). and introduce a variable Lİ-1, to record the cumulative loss of Ey (Step 5). The expert F.T is the slave algorithm of MetaGrad [van Erven and We also maintain set A, consisting of all the active experts (Step 6). Denote the prediction of expert EJ at round t w In Step 9, PAE collects the predictions of all the active experts, and then submits the following solution in Step 10:
Koolen 2016) that minimizes (-) during interval
1
Σ EJEA,
exp(-Li-1,,)1"",
Wr Σ LEJEA exp( L 1,))
Compared with TEWA in (8) we observe that P focuses on active experts and ignores inactive ones. Although the extension is inspired by Chernoy and Vovk 2009), our analysis is different because the surrogate losses take special form of (6) Specifically, and apply a simple inequality [Cesa- Bianchi et al. 2005 Lemma 1]. In this way, we do not need to introduce advanced concepts such the mixability of Chernov and Vovk 2009 The analysis is still challenging because of the dynamic change of active experts. In Step 11, PAE observes the loss fe(-) and evaluates the gradient cumulative loss of each active expert, and in Step 14 passes the surrogate loss to each expert such that it can make predictions for the next round. In Step 16, PAE removes experts whose ending times are / from Ar.
exploit the special structure of losses
to construet the surrogate loss. In Step 13, it updates the
Due to limitations of space, provide the expert-algorithm, well all the proofs, in the supplementary. The theoretical guarantce of PAE is given below.
Theorem Under Assumptions and for any interval [p, gl S [T] and any w E Ω, PAE satisfies
(f(WW), w; - w) -w)
(ODGa(p..)b(pp... 4) +
fe::), w. - -w)
7

---

where
1
d
2 25d
p 10-D+1)) -+1)).
alp.9) 9) -2 2og (24)
+ 2
In
1
(g
(10)
2
b(p.) 9) - (1 p 2)].
(11)
Furthermore, if all the online functions are a-exp-concave over interval (p. q). we have
Σ f(w)) f((w) (DDDG+ 9
alp, (..(p)b))))) =0 (dlogg log(g p)
23
where B = min( ..)
Remark Theorem | Indicaaes that PAE enjoys second-order regret bound for any interval, which in uurn implies a small regret for exp-concave functions. Specifically, for a-exp-concave functions, PAE satisfies SA-Regret(T. 7) O a log Tog which matches the regret of efficient FLH [Hazan and Seshadhri 2007]. This is remarkable result given the fact that PAE is agnostic to a.
3.3
A universal algorithm for minimizing the adaptive regret
In this section, we extend PAE to support strongly convex functions and general convex functions. Inspired by Wang et al. 2020], we introduce new surrogate loss to handle strong convexity:
(w) = 7 ((eee, w. w) + I V (w. w|
(12)
which is also parameterized by r) > Our goal attain another second-order type of regret bound
9 E.(w ((w)= Σ Vel(w))) w. w) Ö
Σ
w. w/12
(13)
for any interval (p, v) T. Combining 13 with Definition 1 we can establish tight regret bound for Å-strongly convex functions over any interval without knowing the value of Furthermore, we can also derive regret bound for general convex functions from 13 and there is need add additional surrogate losses.
Our Universal algorithm for Minimizing the Adaptive regret (UMA) is summarized in Algorithm 2 UMA is natural extension of PAE by incorporating the new surrogate loss (.). The overall procedure of UMA very similar to PAE, except that the number of experts doubles and the weighting formula is modified accordingly. Specifically, in each round f, we further create expert I that starts from and each 1) E S([[)). E7 is an instance of AOGD Bartlett et al. 2008] that able to minimize ?7 during interval 1. We use LV-1,1 to represent the cumulative loss of Fy till round 1, and Ar to store all the active F.y's. Denote the prediction of expert Ey at round t as w",,. In Step 11, UMA receives predictions from experts in A, and AG, and submits the following solution in Step 12:
En for each interval
ΣEJEA, exp(- 1.-,,) Σ Bzed, LV Dmw exp(-Li-.,))VV
W. ΣEJEA, exp( Lxp(-L"1,,)' E E7 exp( ap(-i"_1,j)n
(14)
which is an extension of (9) to accommodate more experts.
Our analysis shows that UMA inherits the theoretical guarantee of PAE, and meanwhile able to minimize the adaptive regret of general convex and strongly convex functions.
Theorem Under Assumptions 7 andd for any interval [p. q) S [T] and any w Ω UMA enjoys the theoretical guarantee of PAE in Theorem 7
Besides, it also satisfies
(e w: -w) <10DGá(p.g)e g)b(p.g) + 3G 3G ((ppg)b(p.g))
Σ w: w/
(15)
Σ (V..(w:),, w: w: S10DGā(p..)) +21DG - 1
(16)

---

Algorithm 2 A Universal algorithm for Minimizing the Adaptive regret (UMA)
1:
Ao =0=-pp Ao =
2: for = 1 to T do
3:
for all I I that starts from do
4:
for all 17 E S(11) do
5:
Create an expert Eq by running the slave algorithm of MetaGrad minimize (-) during I, and set -
6:
Add E7 to the set of active experts: A, = A ({E)}
7:
Create an expert E7 by running an instance of AOGD minimize ()()) during and
---1.- =
Add E to the set of active experts: A. = - end for
8:
9:
10:
end for
11:
Receive output w from each expert E E A and w from each expert E Å.
12:
Submit w, in (4
Observe the loss Je(.) and evaluate the gradient ((e))
14:
for all E AA do
15:
Update L" = L. + (ww",)
16:
Pass the surrogate loss (-) to expert E3
end for
18:
for all E E A; do
Update Σ",,, - (w?,)) 20: Pass the surrogate loss e7 to expert Ey
21: end for
22: Remove experts whose ending times are from A, and A,
23:
end for
where )) is given in 11 and
a(p. 4) = 1 2 (2g) + log(y p 2).
(17)
Furthermore, if all the online functions are X-strongly convex over interval ip, q). we have
9 f((w)) Σ f((w) (IODG+
9G2
a(p.g)b(p.9)= = (00001 (oggloga 1o0gg -p)
2A
X
Remark First, (15) shows that UMA is equipped with another second-order regret bound for any interval, leading small regret for strongly convex functions. Specifically, for X-strongly convex functions, UMA achieves SA-Regret(T,, = O log log 7"), which matches the regret of the efficient algorithm of Zhang et al. (01 8b) Second, (16) manifests that UMA attains O(vr log T) strongly adaptive regret for general convex functions, which again matches the state-of-the-arr result of Jun et al. [2017a] exactly. Finally, because of the dual adaptivity, UMA can handle the tough case that the type functions switches or the parameter functions changes.
Experiments
We present empirical results evaluate the proposed UMA, and the full details can be found in the supplementary.
First, we focus on exp-concave functions, and perform online classification on the ijenn1 dataset [Chang and Lin [011]] Prokhorov] [200T], where the logistic loss is used. In each round, we sample mini-batch of examples to construct the loss, and flip the labels per 200 rounds to simulate changing environments. We compare UMA with FLH for exp-concave functions (abbr. FLHHep) Hazan and Seshadhrij 2007]. ONS Hazan et al. 2007]. SCB Jun et al.) 2017a]. and MetaGrad [van Erven and Koolen 2016). Notice that (i) both FL.Hssp and ONS need to know the modulus of exp-concavity beforchand; and (ii) SCB can be applied because exp-concave functions also convex. Second,

---

300
Cumulative loss
300
ONS
Cumulative loss
OGD
Cumulaatve loss
293
OGI
FLllaa MetaCimd
130
Fillarr MesuCradd
200
Meaaind
200
103
100
(a) Exp-concave functions
(b) Strongly convex functions
(c) Convex Functions
Figure 2: Cumulative losses of different methods versus the number of iterations.
Instantaneour loss
UMA ONS
Instantaneous loss
UMA OGD
Instantaneous loss
UMA OGD 0.6
2.-
2.-
8.
FLlllaes MataCrad
FL MetaGrodd
Meta
1.5
1.6-
0.5
(a) Exp-concave functions
(b) Strongly convex functions
(c) Convex Functions
Figure 3: Instantaneous losses of different methods versus the number of iterations.
consider strongly convex functions, and follow the above setting but choose the regularized hinge loss. We compare UMA with FLH for strongly convex functions (abbr. FLHar) [Zhang et al.) 2018b], et al. 2007]. SCB, and MetaGrad. Similarly, both FLH,, and OGD require the
OGD [Shalev-Shwand modulus of strong convexity as their input. Finally, we investigate convex functions, and implement online linear regression synthetic data, where the absolute loss is chosen. We generate the data in a way such that the underlying parameter changes every 200 rounds, and compare UMA with SCB, OGD [inkevich] 2003) and MetaGrad.
We conduct all the experiments on personal laptop equipped with Intel 17-10750H CPU and 16G memory. We report the cumulative losses of different methods in Fig. 2 As can be seen, UMA performs nearly the best in all cases. Specifically, UMA better than FL in Fig. 2(a) and close to FLHar in Fig. 2(b which indicates that UMA can estimate the moduli of exp-concavity and strong convexity automatically. We also observe that the cumulative losses ONS, OGD, and MetaGrad, which are designed to minimize the static regret, increase rapidly over time, especially when the optimal model changes. We also show the average instantaneous losses different methods Fig. and have similar observations.
Conclusion and future work
In this paper, develop universal algorithm that is able minimize the adaptive regret of general convex, exp-concave and strongly convex functions simultancously. For each type functions, our theoretical guarantee matches the performance of existing algorithms specifically designed for this type of functions under apriori knowledge of parameters.
In the literature, it is well-known that smoothness can be exploited to improve the static regret for different types of loss functions (Srebro et al. [2010] Orabona et al., 2012 Wang et al. 2020). Recent studies Jun et al. 2017b] Zhang et al.) 2019 have demonstrated that smoothness can also be exploited improve the adaptive regret. In the future, we will investigate whether our universal algorithm for minimizing the adaptive regret can be extended to support smoothness.
10

---

Acknowledgments and Disclosure of Funding
We are grateful for the valuable comments from anonymous reviewers and the area chair, especially regarding the second approach in Section 3.1.1 Funding in direct support of this work: NSFC grant 62122037 and 619761 12, JiangsuSF grant BK20200064, Open Research Projects of Zhejiang Lab (NO. 2021KBOABO2)
References
J. Abernethy, P. L. Bartlett, A. Rakhlin, and A. Tewari. Optimal stragies and minimax lower bounds for online convex games. In Proceedings of the 21 Annual Conference on Learning Theory, pages 415-423, 2008.
D. Adamskiy, W. M. Koolen, A. Chernov, and Vovk. closer look at adaptive regret. In Proceedings of the 23rd International Conference Algorithmic Learning Theory, pages 290-304, 2012.
S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of Computing, 8(6):121-164, 2012.
D. Baby and Y.-.. Wang- Optimal dynamic regret in exp-concave online learning. In Proceedings of the 34th Conference on Learning Theory, pages 359-409, 2021.
P. L. Bartlett, E. Hazan, and A. Rakhlin. Adaptive online gradient descent. In Advances in Neural Information Processing Systems 20, pages 65-72, 2008.
O. Besbes, Y. Gur, and A. Zeevi. Non-stationary stochastic optimization. Operations Research, 63 (5):1227-1244, 2015.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
N. Cesa-Bianchi, Y. Mansour, and G. Stoltz. Improved second-order bounds for prediction with expert advice. In Proceedings of the 18th Annual Conference on Learning Theory, pages 217-232, 2005.
C.-.. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):77:1-2::211 2011.
A. Chernov and V. Vovk. Prediction with expert evaluators' advice. In Proceedings of the 20th International Conference on Algorithmic Learning Theory, pages 8-22, 2009.
A. Cutkosky. Parameter-free, dynamic, and strongly online learning. In Proceedings of the 37th International Conference on Machine Learning, pages 2250-2259, 2020.
A. Damiely, A. Gonen, and Shalev-Shwartz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning, pages 1405-1411, 2015.
C. Do. Q. Le, and C.-S. Foo. Proximal regularization for online and batch learning. In Proceedings of the 26th International Conference on Machine Learning, pages 257-264, 2009.
Y. Freund, R. E. Schapire, Y. Singer, and M. K. Warmuth. Using and combining predictors that specialize. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 334 1997.
Gaillard, G. Stoltz, and T. van Erven. A second-order bound with excess losses. In Proceedings of the 27th Conference on Learning Theory, pages 176-196, 2014.
A. György, Linder, and G. Lugosi. Efficient tracking of large classes of experts. IEEE Tronsactions Information Theory, 58(11):679--675,, 2012.

---

E. Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2 (3-4):157-325, 2016.
E. Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. Electronic Colloquium on Computational Complexity, 88, 2007.
E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 393-400, 2009.
E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-192 2007.
M. Herbster and M. K. Warmuth. Tracking the best expert. Machine Learning, 32(2):151-178, 1998.
A. Jadbabaie, A. Rakhlin, Shahrampour, and K. Sridharan. Online optimization: Competing with dynamic comparators. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, pages 398 406, 2015.
K.-S. Jun, F. Orabona, S. Wright, and R. Willett. Improved strongly adaptive online learning using coin betting. In Proceedings of the 20th International Conference Artificial Intelligence and Statistics, pages 943-951, 2017a.
K.-S. Jun, F. Orabona, S. Wright, and R. Willett, Online learning for changing environments using coin betting. Electronic Journal of Statistics, 11(2):222253110, 2017b.
W. M. Koolen and T. V. Erven. Second-order quantile methods for experts and combinatorial games. In Proceedings of the 28th Conference on Learning Theory, pages 1155-1175, 2015.
N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212-22 2611, 1994.
H. Luo and R. E. Schapire. Achieving all with no parameters: Adanormalhedge. In Proceedings of the 28th Conference on Learning Theory, pages 1286-1304 2015.
Z. Mhammedi, W. M. Koolen, and T. Van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Proceedings of the 32nd Conference on Learning Theory, pages 2490-2511, 2019.
F. Orabona, N. Desa-Bianchi. and C. Gentile. Beyond logarithmic bounds in online learning. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, pages 823 133-831,22 2012.
D. Prokhorov. IJCNN 2001 neural network competition. Technical report, Ford Research Laboratory, 2001.
S. Shalev-Shwart. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
Shalev-Shwartz, Singer, and N. Srebro. Pegasos: primal estimated sub- aub-gradient solver for SVM. In Proceedings of the 24th International Conference on Machine Learning, pages 807-814, 2007.
N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low-noise and fast rates. In Advances in Neural Information Processing Systems 23, pages 2199-2207, 2010. 2010.
T. van Erven and W. M. Koolen. MetaGrad: Multiple learning rates in online learning, In Advances in Neural Information Processing Systems 29, pages 3666-3674, 2016.
van Erven, W. M. Koolen, and D. van der Hoeven. MetaGrad: Adaptation using multiple learning rates in online learning. Journal of Machine Learning Research, 22(161):1-61, 2021.
J. Veness, M. White, M. Bowling, and A. György. Partition tree weighting. In Proceedings of the 2013 Data Compression Conference, pages 321-330, 2013.
Y. Wan, W.-W Tu, and I.. Zhang. Strongly adaptive online learning over partial intervals. Science China Information Sciences, page in press, 2021.
12

---

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, pages 2762-2768, 2018.
G. Wang. S. Lu, and L. Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Proceedings of the 35th Conference on Uncertainty Artificial Intelligence, 2019.
G. Wang. S. Lu, Y. Hu, and L. Zhang. Adapting smoothness: A more universal algorithm for online convex optimization. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 6162-6169, 2020.
O. Wintenberger. Optimal learning with bernstein online aggregation. Machine Learning, 106: 119- 149--41,220 2017.
T. Yang. L.. Zhang, R. Jin, and J. Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In Proceedings of the 33rd International Conference Machine Learning, pages 449-457, 2016.
L. Zhang. Online learning in changing environments. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pages 5178-5182, 2020. Early Career.
L. Zhang, T. Yang. J. Yi, R. Jin, and Z.-H. Zhou. Improved dynamic regret for non-degenerate functions. In Advances Neural Information Processing Systems 30, pages 732-741, 2017.
Zhang, S. Lu, and Z. Zhou, Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31, pages 1333, 201 8a.
L. Zhang, T. Yang, R. Jin, and Z.-H. Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning, pages 5882-5891, 2018b.
L. Zhang. T.-Y. Liu, and Z.-H. Zhou. Adaptive regret of convex and smooth functions. In Proceedings of the 36th International Conference on Machine Learning, pages 7414-7423, 2019.
L. Zhang, S. Lu, and T. Yang. Minimizing dynamic regret and adaptive regret simultaneously. In P Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 309-319, 2020.
L. Zhang, G. Wang. J. Yi, and T. Yang. A simple yet universal strategy for online convex optimization. ArXiv e-prints, (iXii::10050068) 2021.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-936, 2003.
13


Reviews:
[{"review_id": "n1B4II0cQ0", "reviewer": "Reviewer_Mr6y", "summary": "This paper studies online convex optimization in the strongly-adaptive regret setting. Essentially, this paper generalizes MetaGrad, an OCO algorithm which was able to adapt to the type of convexity of the losses, to the strongly adaptive regret setting.\n\nThis algorithm is build using the metagrad meta-regret structure, geometric covering, a new surrogate loss function, and a generalization of the sleeping experts analysis. By deriving second-order regret bounds on the sub-intervals, the authors are able to show strongly-adaptive regret guarantees. The proposed algorithms were also shown to have favorable performance in experiments. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this is a good paper. It solves a natural problem -- the extension of universal OCO algorithms to strongly-adaptive regret -- and presents the new ideas in a clear manner. Generally, the explanations and writing are clear. The results are believable, and the analysis is sufficiently clear.\n\nA few questions and suggestions for improvement:\n1) Can you provide some intuition why the alternative surrogate function is needed?\n2) Why spend so much time on PAE, as it is a special case of your main algorithm? Some important discussion, like the role and regret guarantees of the slave algorithms, could be a better use of the space in the main body.\n3) Can you say anything about lower bounds?\n\npost-rebuttal: Thanks for the clarification, and nice work! I remain positive about the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "O-lRM9oX4g", "reviewer": "Reviewer_x3iJ", "summary": "In this papers, the authors tackle the problem of online optimization with unknown (or even changing) convex function types, which can be plain convex, exp-concave, or strongly convex. Their main goal is to design an algorithm that suffers asymptotically optimal regret on any time interval. \n\nTo this end they extend the MetaGrad algorithm, a method that guarantees low static regret against plain convex or exp-concave functions, to also handle strongly convex functions and in a way that guarantees low adaptive regret, not only static regret. Their main technical contribution is showing that this can be done by incorporating sleeping experts in the meta algorithm of MetaGrad.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths and Weaknesses\n\n## Strengths\n- The main paper is well written and clearly poses the question and the challenges involved, what can be a bit hard in this case since there are so many moving pieces;\n- Introducing the simpler version first that handles only exp-concave functions does help in the readability;\n- Although no technique in isolation is novel, the clever combination of many different techniques to create a truly \"universal algorithm\" is a solid contribution.\n\n## Weakenesses\n- The proofs in the supplementary material are not very well organized and written.\n- The experiments are not very well explained (more details later);\n\n# Details and Questions for the Authors\n\nThe paper was a nice read and is a solid contribution. As I mentioned, no single piece in isolation is novel, but this is a good combination of many different techniques to devise an interesting \"universal\" algorithm. Two points I'd like the authors' thoughts are on the supplementary material writing and on the experiments.\n\nThe supplementary material has all the proofs, but while I tried to read it (skipping some parts since our time for review is limited), I often got lost. The problem is that the authors start by giving a brief overview of the proof of the main theorems, deferring the proof of a couple of lemmas for later. Yet, they never explicitly say they are going to do that, what makes the reader wonder if they simply omitted the proof or if the proofs are \"well-known\". Also, each subsection usually consists of one proof, but they often state the lemmas they will need before actually starting the proof. In the end, it is hard to figure out exactly where the statement of lemmas and discussion ends, and where the proofs actually begin.\n\nAbout the experiments, there are some aspects of them that do not seem fair (or at least not well explained):\n- The classical static algorithms (OGD and ONS) should have their parameters chosen by some kind of grid search. It is not clear from the text if the parameters were chosen to be the \"theoretically optimal\" or if the authors did pick the best parameters for OGD and ONS;\n- Why is the interval set at 200? Changing the interval size changes the results by a lot? If not, discussing this (even if in the appendix) would be interesting;\n- Different datasets change the results by a lot? You should at least give some reason for using only one single dataset;\n- Since you are comparing with ONS and OGD, would it also make sense to compare with one of the adaptive algorithms for static regret (Metagrad or Maler)? Why none of these algorithms were used?\n- It would be interesting to provide timing data and the laptop specs, if possible;\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Mostly yes, I've only raised some concerns related to the experiments.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "H-zcudZ5iWA", "reviewer": "Reviewer_jKJC", "summary": "This paper considers the problem of minimizing the adaptive regret together with being adaptive to the regularity of the loss function (exp-concavity, strong convexity, convexity,...). On one hand, algorithms and techniques to minimize the adaptive regret already exist but existing results are specific to the curvature of the losses. On the other hand, there exist universal algorithms that are adaptive to broad classes of loss functions (Metagrad and extensions). This paper combines both techniques and provides two algorithms (PAE and UMA) that get both guarantees simultaneously. In particular, it is adaptive to changes in the regularity of the losses. Finally, the authors provide some experiments to illustrate their results.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On one hand, the paper is generally well-written, and having a generic algorithm that automatically adapts to the regularity of the losses to enjoy the best possible guarantees and can deal with non-stationary environment is surely interesting for the community and can be very useful for applications. In particular, I like the result to be adaptive to changes in the regularity of the loss sequences.\n\nYet, on the other hand, the results did not surprise me and the contribution is somewhat incremental in my opinion. The technique of sleeping experts is widely used and known to transform any static algorithm into an adaptive regret algorithm (see among many others, Daniely et al. 15, Orabona et al. 2017, Zhang et al. 2018). The Metagrad algorithm and its variants are based on combining experts. Combining their analysis with the sleeping expert procedure seems fairly straightforward and does not provide any technical novelty. In case I missed a new technical difficulty in the analysis, I encourage the authors to highlight it. \n\nMoreover, I suspect that the results can be also obtained as follows. Second-order bounding algorithms that adapt to loss regularity already exist for the expert framework (see, for example, [1,2,3]). Using such algorithms as the meta-procedure for FLH (Zhang et al. 2018) with MetaGrad as subroutines should achieve this, doesn't it?\n\n\nAnother comment:\nAnother natural measure to deal with a non-stationary environment in online learning is dynamic regret. I do think that dynamic regret should be discussed in the introduction. As shown by Zhang et al 2018, there exists a reduction from adaptive regret to dynamic regret. Yet, it was shown that the rate obtained by Zhang et al. 2018 was suboptimal for exp-concave loss functions [4]. I would be surprised, but it would be interesting to see if the optimal rate of [4] could be recovered by your method for dynamic regret.\n\n\n[1] A second-order bound with excess losses. Gaillard, Stoltz, Van Erven, 2014.  \n[2] Second-order quantile methods for experts and combinatorial games. Koolen, Van Erven, 2015.  \n[3] Optimal learning with Bernstein online aggregation. Wintenberger, 2017.  \n[4] Optimal Dynamic Regret in Exp-Concave Online Learning. D Baby, YX Wang, 2021.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "DlAj13S1lHt", "reviewer": "Reviewer_jQzg", "summary": "In this paper, the authors develop a universal algorithm, namely UMA, that is able to minimize the adaptive regret of general convex, exp-concave and strongly convex functions simultaneously. The key idea is to modify MetaGrad to support sleeping experts and introduce additional surrogate losses for strongly convex functions and general convex functions. In this way, UMA can minimize the adaptive regret of multiple types of convex functions automatically, and thus is universal. Some experiments are done to evaluate the effectiveness of UMA.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "From the technical viewpoint, UMA is a nice extension of MetaGrad to minimize the adaptive regret. Because MetaGrad has a small meta-regret, the authors are able to maintain the optimality of UMA for different types of functions. This result actually demonstrates that the meta-algorithm of MetaGrad can be used to replace existing meta-algorithms designed for adaptive regret [Hazan and Seshadhri, 2007, Daniely et al., 2015, Jun et al., 2017a].\n\nStrengths:\n1. To the best of my knowledge, UMA is the first universal algorithm for minimizing the adaptive regret. Due to the property of universality, UMA can be applied with less manual intervention.\n2. For each type of functions, UMA achieves state-of-the-art adaptive regret, and can also handle the case that the type of functions may change.\n3. The paper is well-written and the proofs are easy to follow.\n\nWeaknesses:\n1. As pointed out by the authors, the main limitation of UMA is that the number of experts is $O(\\log^2 t)$, which is larger than previous method by a logarithmic factor.\n2. UMA is built upon MetaGrad, and somehow incremental.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Questions:\n1. All the adaptive regret bounds have a logarithmic dependence on $T$, which means that the regret over fixed-length intervals keeps increasing as $T$ increases. The logarithmic dependence is usually acceptable, but when $T$ becomes very large, this could be an issue. Is there any way to avoid the dependence on $T$?\n\n2. In Line 50, the authors claim that UMA attains *second-order* regret bounds over any interval. On the other hand, Cutkosky [2020] also establishes a *second-order* bound for adaptive regret. Can the authors discuss the difference between them?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In agreement with the reviewers, I am happy to recommend acceptance of the paper. During the review process the authors promised several improvements to the paper (such as discussing and experimenting with the suggested simple black-box algorithm or clarifying that their references to sleeping experts are meant only in a restricted manner), which they must include in the final version of the paper.
Decision: Accept (Poster)