Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions
Year: 2021

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.

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

heading: 1 Introduction
text: Online learning aims to make a sequence of accurate decisions given knowledge of answers to previous tasks and possibly additional information [Shalev-Shwartz, 2011]. It is performed in a sequence of consecutive rounds, where at round t the learner is asked to select a decision wt from a domain Ω. After submitting the answer, a loss function ft : Ω 7→ R is revealed and the learner suffers a loss ft(wt). The standard performance measure is the regret [Cesa-Bianchi and Lugosi, 2006]:
Regret(T ) = T∑ t=1 ft(wt)− min w∈Ω T∑ t=1 ft(w)
defined as the difference between the cumulative loss of the online learner and that of the best decision chosen in hindsight. When both the domain Ω and the loss ft(·) are convex, it becomes online convex optimization (OCO) [Zinkevich, 2003].
In the literature, there exist plenty of 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 of performance. That is because regret chooses a fixed comparator, and for the same reason, it is also referred to as static regret. To address this limitation, Hazan and Seshadhri [2007] introduce the concept of adaptive regret, which measures the performance with respect to a changing comparator. Following the terminology of Daniely et al. [2015], we define the strongly adaptive
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
regret as the maximum static regret over intervals of length τ , i.e.,
SA-Regret(T, τ) = max [p,p+τ−1]⊆[T ] ( p+τ−1∑ t=p ft(wt)− min w∈Ω p+τ−1∑ t=p ft(w) ) . (1)
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, exponentially concave (abbr. exp-concave) and strongly convex functions [Hazan and Seshadhri, 2009, Jun et 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 simultaneously. This observation motivates us to ask whether it 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 a 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 et 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 a result, it can minimize the adaptive regret of general convex functions, and automatically take advantage of easier functions whenever possible. Specifically, UMA attains O( √ τ log T ), O( dα log τ log T ) and O( 1λ log τ log T ) strongly adaptive regrets for general convex, α-exp-concave and λ-strongly convex functions respectively, where d is the dimensionality. All of these bounds match the state-of-the-art 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 I1, then become α-exp-concave in I2, and finally switch to λ-strongly convex in I3. When facing this function sequence, UMA achieves O( √ |I1| log T ), O( dα log |I2| log T ) and O( 1 λ log |I3| log T ) regrets over intervals I1, I2 and I3, respectively.

heading: 2 Related work
text: We briefly review related work on static regret and adaptive regret, under the setting of OCO.

heading: 2.1 Static regret
text: To minimize the static regret of general convex functions, online gradient descent (OGD) with step size ηt = O(1/ √ t) achieves an O( √ T ) bound [Zinkevich, 2003]. If all the online functions are λ-strongly convex, OGD with step size ηt = O(1/[λt]) attains anO( 1λ log T ) bound [Shalev-Shwartz et al., 2007]. When the functions are α-exp-concave, online Newton step (ONS), with knowledge of α, enjoys an O( dα log T ) bound, where d 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) [Bartlett et al., 2008] and its proximal extension [Do et al., 2009]. The key idea of AOGD is to add a quadratic regularization term to the loss. Bartlett et al. [2008] demonstrate that AOGD is able to interpolate between the O( √ T ) bound of general convex functions and the O(log 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( √ T ) regret for this type of functions.
Another milestone is the multiple eta gradient algorithm (MetaGrad) [van Erven and Koolen, 2016, Mhammedi et al., 2019, van Erven et al., 2021], which adapts to a much broader class of functions, including convex and exp-concave functions. MetaGrad’s main feature is that it simultaneously considers multiple learning rates and does not need to know the modulus of exp-concavity. MetaGrad achieves O( √ T log log T ) and O( dα log T ) regret bounds for general convex and α-exp-concave functions, respectively. However, it suffers the following two limitations:
• MetaGrad treats strongly convex functions as exp-concave, and thus only gives a suboptimal O( dλ log T ) regret for λ-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 et al. [2019], who develop a universal algorithm named as multiple sub-algorithms and learning rates (Maler). It attainsO( √ T ),O( dα log T ) and O( 1λ log T ) regret bounds for general convex, α-exp-concave, and λ-strongly convex functions, respectively. Furthermore, Wang et al. [2020] extend Maler to make use of smoothness. However, the second limitation remains there.

heading: 2.2 Adaptive regret
text: Adaptive regret has been studied in the setting of prediction with expert advice [Littlestone and Warmuth, 1994, Freund et al., 1997, Adamskiy et al., 2012, György et al., 2012, Luo and Schapire, 2015] and OCO [Hazan and Seshadhri, 2007, Daniely et al., 2015, Jun et al., 2017a]. In this section, we focus on the related work in 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:
WA-Regret(T ) = max [p,q]⊆[T ] ( q∑ t=p ft(wt)− min w∈Ω q∑ t=p ft(w) ) .
For α-exp-concave functions, Hazan and Seshadhri [2007] propose an adaptive algorithm named as Follow-the-Leading-History (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 it needs to maintain t experts in the t-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 O(log t) experts, at the price of an O( dα log
2 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 [2007] prove that FLH and its efficient variant attain O( √ T log T ) and O( √ T log3 T ) weakly adaptive regrets, respectively. This result reveals a limitation of weakly adaptive regret—it does not respect short intervals well. For example, the O( √ T log T ) regret bound is meaningless for intervals of length O( √ T ). To address this limitation, Daniely et al. [2015] introduce the strongly adaptive regret which takes the interval length as a parameter, as shown in (1). They propose a novel meta-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 a variant of multiplicative weights method [Arora et al., 2012]. SAOL also maintains O(log 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 a new meta-algorithm named as sleeping coin betting (SCB), and improve the strongly adaptive regret bound to O( √ τ log T ). Very recently, Cutkosky [2020] proposes a novel strongly adaptive method, which can guarantee the O( √ τ log T ) bound in the worst case, while achieving tighter results when the square norms of gradients are small.
For λ-strongly convex functions, Zhang et al. [2018b] point out that we can replace ONS with OGD, and obtain an O( 1λ log T ) weakly adaptive regret. They also demonstrate that the number of active experts can be reduced from t to O(log t), at a cost of an additional log T factor in the regret. All the aforementioned adaptive algorithms need to query the gradient of the loss function at least Θ(log t) times in the t-th iteration. Based on surrogate losses, Wang et al. [2018] show that the number of gradient evaluations per round can be reduced to 1 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].

heading: 2.3 Dynamic regret
text: 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., 2015, 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 al., 2018b, 2020, Cutkosky, 2020, Baby and Wang, 2021]. For more discussions, please refer to Zhang [2020].

heading: 3 Main results
text: We first present necessary preliminaries, including assumptions, definitions and the technical challenge, then provide our universal algorithm and its theoretical guarantee.

heading: 3.1 Preliminaries
text: We introduce two common assumptions used in the study of OCO [Hazan, 2016].
Assumption 1 The diameter of the domain Ω is bounded by D, i.e.,
max x,y∈Ω
‖x− y‖ ≤ D. (2)
Assumption 2 The gradients of all the online functions are bounded by G, i.e.,
max w∈Ω ‖∇ft(w)‖ ≤ G, ∀t ∈ [T ]. (3)
Next, we state definitions of strong convexity and exp-concavity [Boyd and Vandenberghe, 2004, Cesa-Bianchi and Lugosi, 2006].
Definition 1 A function f : Ω 7→ R is λ-strongly convex if
f(y) ≥ f(x) + 〈∇f(x),y − x〉+ λ 2 ‖y − x‖2, ∀x,y ∈ Ω.
Definition 2 A function f : Ω 7→ R is α-exp-concave if exp(−αf(·)) is concave over Ω.
The following property of exp-concave functions will be used later [Hazan et al., 2007, Lemma 3].
Lemma 1 For a function f : Ω 7→ R, where Ω has diameter D, such that ∀w ∈ Ω, ‖∇f(w)‖ ≤ G and exp(−αf(·)) is concave, the following holds for β = 12 min{ 1 4GD , α}:
f(y) ≥ f(x) + 〈∇f(x),y − x〉+ β 2 〈∇f(x),y − x〉2, ∀x,y ∈ Ω.

heading: 3.1.1 Technical challenge
text: 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 [Hazan and Seshadhri, 2007, Daniely et al., 2015, 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 a specific type of functions;
• A set of intervals, each of which is associated with an expert-algorithm that minimizes the regret of that interval;
• A meta-algorithm, which combines the predictions of active experts in each round. To design a universal algorithm, a straightforward way is to use a universal method for static regret, such as MetaGrad [van Erven and Koolen, 2016], as the expert-algorithm. In this way, the expertalgorithm is able to handle the uncertainty of functions. However, the challenge lies in the design of the meta-algorithm, because the meta-algorithms used by previous studies also lack universality. For example, the meta-algorithm of Hazan and Seshadhri [2007] is able to deliver a tight meta-regret for exp-concave functions, but a loose one for general convex functions. Similarly, meta-algorithms of Daniely et al. [2015] and Jun et al. [2017a] incur at least Θ( √ τ) 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 a 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-regret only depends on 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., MetaGrad or Maler) as the expert-algorithm, and change the meta-algorithm. Inspired by a recent universal strategy for OCO [Zhang et al., 2021], we choose a meta-algorithm that enjoys second-order bounds with excess losses [Gaillard et 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 a 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 an extended version.

heading: 3.2 A parameter-free and adaptive algorithm for exp-concave functions
text: 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 understanding, we start with a simpler question: How to minimize the adaptive regret of exp-concave functions, without knowing the modulus of exp-concavity? By proposing a novel algorithm to answer the above question, we present the main techniques used in our paper. Then, we extend that algorithm to support other types of functions in the next section. Since our algorithm is built upon MetaGrad, we first review its key steps below.

heading: 3.2.1 Review of MetaGrad
text: The reason that MetaGrad can minimize the regret of α-exp-concave functions without knowing the value of α is because it enjoys a second-order regret bound:
T∑ t=1 ft(wt)− T∑ t=1 ft(w) ≤ T∑ t=1 〈∇ft(wt),wt −w〉 = O (√ VT d log T + d log T )
(4)
where VT = ∑T t=1〈∇ft(wt),wt −w〉2. Besides, Lemma 1 implies
T∑ t=1 ft(wt)− T∑ t=1 ft(w) ≤ T∑ t=1 〈∇ft(wt),wt −w〉 − β 2 T∑ t=1 〈∇ft(wt),wt −w〉2. (5)
Combining (4) with (5) and applying the AM-GM inequality, we immediately obtain T∑ t=1 ft(wt)− T∑ t=1 ft(w) = O ( d β log T ) = O ( d α log T ) .
From the above discussion, it becomes clear that if we can establish a second-order regret bound for any interval [p, q] ⊆ [T ], we are able to minimize the adaptive regret even when α is unknown. The way that MetaGrad attains the regret bound in (4) is to run a set of experts, each of which minimizes a surrogate loss parameterized by a learning rate η
`ηt (w) = −η〈∇ft(wt),wt −w〉+ η2〈∇ft(wt),wt −w〉2 (6) and then combine the outputs of experts by a meta-algorithm named as Tilted Exponentially Weighted Average (TEWA). Specifically, it creates an expert Eη for each η in
S(T ) = { 2−i
5DG ∣∣∣∣ i = 0, 1, . . . ,⌈12 log2 T ⌉}
(7)
and thus maintains 1+d 12 log2 T e = O(log T ) experts during the learning process. By simultaneously considering multiple learning rates, MetaGrad is able to deal with the uncertainty of VT . Since the surrogate loss `ηt (·) is exp-concave, a variant of ONS is used as the expert-algorithm. Let w η t be the output of expert Eη in the t-th round. MetaGrad calculates the final output wt according to TEWA:
wt =
∑ η π η t ηw
η t∑
η π η t η
(8)
where πηt ∝ exp(− ∑t−1 i=1 ` η i (w η i )).

heading: 3.2.2 Our approach
text: 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 to create 1 + d 12 log2(q − p+ 1)e experts for each interval [p, q] ∈ [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(T 2 log T ). To control the number of experts, we make use of the geometric covering (GC) intervals [Daniely et al., 2015] defined as
I = ⋃
k∈N∪{0}
Ik,
where Ik = { [i · 2k, (i+ 1) · 2k − 1] : i ∈ N } , k ∈ N ∪ {0}.
A graphical illustration of GC intervals is given in Fig. 1. We observe that each Ik is a partition of N \ {1, · · · , 2k − 1} to consecutive intervals of length 2k. The GC intervals can be generated on the fly, so we do not need to fix the horizon T . We note that similar intervals have been proposed by Veness et al. [2013].
Then, we only focus on intervals in I . For each interval I = [r, s] ∈ I , we will create 1+d 12 log2(s− r + 1)e experts, each of which minimizes one surrogate loss in {`ηt (w)|η ∈ S(s− r + 1)} during I , where `ηt (·) and S(·) are defined in (6) and (7), respectively. These experts become active in round r and will be removed forever after round s. It is easy to verify that in each round t, the number of intervals that contain t is blog2 tc+ 1 [Daniely et al., 2015], and thus the number of active experts is at most
(blog2 tc+ 1) ( 1 + ⌈ 1
2 log2 t
⌉) = O(log2 t).
So, the number of active experts is larger than that of MetaGrad by a logarithmic factor, which is 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: A0 = ∅ 2: for t = 1 to T do 3: for all I ∈ I that starts from t do 4: for all η ∈ S(|I|) do 5: Create an expertEηI by running the slave algorithm of MetaGrad to minimize ` η t (·) during
I , and set Lηt−1,I = 0 6: Add EηI to the set of active experts: At = At−1 ∪ {E η I } 7: end for 8: end for 9: Receive output wηt,J from each expert E η J ∈ At
10: Submit wt in (9) 11: Observe the loss ft(·) and evaluate the gradient∇ft(wt) 12: for all EηJ ∈ At do 13: Update Lηt,J = L η t−1,J + ` η t (w η t,J) 14: Pass the surrogate loss `ηt (·) to expert E η J 15: end for 16: Remove experts whose ending times are t from At 17: end for
Finally, we 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 a 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 Chernov 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-free and Adaptive algorithm for Exp-concave functions (PAE) is summarized in Algorithm 1. In the t-th round, we first create an expert EηI for each interval I ∈ I that starts from t and each η ∈ S(|I|), where S(·) is defined in (7), and introduce a variable Lηt−1,I to record the cumulative loss of EηI (Step 5). The expert E η I is the slave algorithm of MetaGrad [van Erven and Koolen, 2016] that minimizes `ηt (·) during interval I . We also maintain a set At consisting of all the active experts (Step 6). Denote the prediction of expert EηJ at round t as w η t,J . In Step 9, PAE collects the predictions of all the active experts, and then submits the following solution in Step 10:
wt = 1∑
EηJ∈At exp(−Lηt−1,J)η ∑ EηJ∈At exp(−Lηt−1,J)ηw η t,J . (9)
Compared with TEWA in (8), we observe that (9) focuses on active experts and ignores inactive ones. Although the extension is inspired by Chernov and Vovk [2009], our analysis is different because the surrogate losses take a special form of (6). Specifically, we exploit the special structure of losses and apply a simple inequality [Cesa-Bianchi et al., 2005, Lemma 1]. In this way, we do not need to introduce advanced concepts such as 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 ft(·) and evaluates the gradient ∇ft(wt) to construct the surrogate loss. In Step 13, it updates the 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 t from At. Due to limitations of space, we provide the expert-algorithm, as well as all the proofs, in the supplementary. The theoretical guarantee of PAE is given below.
Theorem 1 Under Assumptions 1 and 2, for any interval [p, q] ⊆ [T ] and any w ∈ Ω, PAE satisfies q∑ t=p 〈∇ft(wt),wt −w〉 ≤ 10DGa(p, q)b(p, q) + 3 √ a(p, q)b(p, q) √√√√ q∑ t=p 〈∇ft(wt),wt −w〉2
where
a(p, q) =2 log2(2q) + 1 2 + d 2 ln
( 1 + 2
25d (q − p+ 1)
) , (10)
b(p, q) =2dlog2(q − p+ 2)e. (11) Furthermore, if all the online functions are α-exp-concave over interval [p, q], we have
q∑ t=p ft(wt)− q∑ t=p ft(w) ≤ ( 10DG+ 9 2β ) a(p, q)b(p, q) = O ( d log q log(q − p) α ) where β = 12 min{ 1 4GD , α}.
Remark Theorem 1 indicates that PAE enjoys a second-order regret bound for any interval, which in turn implies a small regret for exp-concave functions. Specifically, for α-exp-concave functions, PAE satisfies SA-Regret(T, τ) = O( dα log τ log T ), which matches the regret of efficient FLH [Hazan and Seshadhri, 2007]. This is a remarkable result given the fact that PAE is agnostic to α.

heading: 3.3 A universal algorithm for minimizing the adaptive regret
text: In this section, we extend PAE to support strongly convex functions and general convex functions. Inspired by Wang et al. [2020], we introduce a new surrogate loss to handle strong convexity:
ˆ̀η t (w) = −η〈∇ft(wt),wt −w〉+ η2‖∇ft(wt)‖2‖wt −w‖2 (12)
which is also parameterized by η > 0. Our goal is to attain another second-order type of regret bound q∑ t=p ft(wt)− q∑ t=p ft(w) ≤ q∑ t=p 〈∇ft(wt),wt −w〉 = Õ √√√√ q∑ t=p ‖wt −w‖2  (13) for any interval [p, q] ⊆ T . Combining (13) with Definition 1, we can establish a tight regret bound for λ-strongly convex functions over any interval without knowing the value of λ. Furthermore, we can also derive a regret bound for general convex functions from (13), and there is no need to add additional surrogate losses.
Our Universal algorithm for Minimizing the Adaptive regret (UMA) is summarized in Algorithm 2. UMA is a natural extension of PAE by incorporating the new surrogate loss ˆ̀ηt (·). The overall procedure of UMA is very similar to PAE, except that the number of experts doubles and the weighting formula is modified accordingly. Specifically, in each round t, we further create an expert ÊηI for each interval I ∈ I that starts from t and each η ∈ S(|I|). Ê η I is an instance of AOGD [Bartlett et al., 2008] that is able to minimize ˆ̀ηt during interval I . We use L̂ η t−1,I to represent the cumulative loss of ÊηI till round t− 1, and Ât to store all the active Ê η I ’s. Denote the prediction of expert ÊηJ at round t as ŵ η t,J . In Step 11, UMA receives predictions from experts in At and Ât, and submits the following solution in Step 12:
wt =
∑ EηJ∈At exp(−Lηt−1,J)ηw η t,J + ∑ ÊηJ∈Ât
exp(−L̂ηt−1,J)ηŵ η t,J∑
EηJ∈At exp(−Lηt−1,J)η + ∑ ÊηJ∈Ât exp(−L̂ηt−1,J)η (14)
which is an extension of (9) to accommodate more experts.
Our analysis shows that UMA inherits the theoretical guarantee of PAE, and meanwhile is able to minimize the adaptive regret of general convex and strongly convex functions.
Theorem 2 Under Assumptions 1 and 2, for any interval [p, q] ⊆ [T ] and any w ∈ Ω, UMA enjoys the theoretical guarantee of PAE in Theorem 1. Besides, it also satisfies
q∑ t=p 〈∇ft(wt),wt −w〉 ≤10DGâ(p, q)b(p, q) + 3G √ â(p, q)b(p, q) √√√√ q∑ t=p ‖wt −w‖2, (15) q∑ t=p 〈∇ft(wt),wt −w〉 ≤10DGâ(p, q)b(p, q) + 21DG √ â(p, q)(q − p+ 1) (16)
Algorithm 2 A Universal algorithm for Minimizing the Adaptive regret (UMA)
1: A0 = Â0 = ∅ 2: for t = 1 to T do 3: for all I ∈ I that starts from t do 4: for all η ∈ S(|I|) do 5: Create an expertEηI by running the slave algorithm of MetaGrad to minimize ` η t (·) during I , and set Lηt−1,I = 0 6: Add EηI to the set of active experts: At = At−1 ∪ {E η I } 7: Create an expert ÊηI by running an instance of AOGD to minimize ˆ̀ η t (·) during I , and set
L̂ηt−1,I = 0
8: Add ÊηI to the set of active experts: Ât = Ât−1 ∪ {Ê η I }
9: end for 10: end for 11: Receive output wηt,J from each expert E η J ∈ At and ŵ η t,J from each expert Ê η J ∈ Ât 12: Submit wt in (14) 13: Observe the loss ft(·) and evaluate the gradient∇ft(wt) 14: for all EηJ ∈ At do 15: Update Lηt,J = L η t−1,J + ` η t (w η t,J) 16: Pass the surrogate loss `ηt (·) to expert E η J 17: end for 18: for all ÊηJ ∈ Ât do 19: Update L̂ηt,J = L̂ η t−1,J + ˆ̀η t (w η t,J) 20: Pass the surrogate loss ˆ̀ηt (·) to expert Ê η J 21: end for 22: Remove experts whose ending times are t from At and Ât 23: end for
where b(·, ·) is given in (11), and â(p, q) = 1 + 2 log2(2q) + log(q − p+ 2). (17)
Furthermore, if all the online functions are λ-strongly convex over interval [p, q], we have q∑ t=p ft(wt)− q∑ t=p ft(w) ≤ ( 10DG+ 9G2 2λ ) â(p, q)b(p, q) = O ( log q log(q − p) λ ) .
Remark First, (15) shows that UMA is equipped with another second-order regret bound for any interval, leading to a small regret for strongly convex functions. Specifically, for λ-strongly convex functions, UMA achieves SA-Regret(T, τ) = O( 1λ log τ log T ), which matches the regret of the efficient algorithm of Zhang et al. [2018b]. Second, (16) manifests that UMA attains an O( √ τ log T ) strongly adaptive regret for general convex functions, which again matches the state-of-the-art result of Jun et al. [2017a] exactly. Finally, because of the dual adaptivity, UMA can handle the tough case that the type of functions switches or the parameter of functions changes.

heading: 4 Experiments
text: We present some empirical results to 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 ijcnn1 dataset [Chang and Lin, 2011, Prokhorov, 2001], where the logistic loss is used. In each round, we sample a 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. FLHexp) [Hazan and Seshadhri, 2007], ONS [Hazan et al., 2007], SCB [Jun et al., 2017a], and MetaGrad [van Erven and Koolen, 2016]. Notice that (i) both FLHexp and ONS need to know the modulus of exp-concavity beforehand; and (ii) SCB can be applied because exp-concave functions are also convex. Second, we
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. FLHstr) [Zhang et al., 2018b], OGD [Shalev-Shwartz et al., 2007], SCB, and MetaGrad. Similarly, both FLHstr and OGD require the modulus of strong convexity as their input. Finally, we investigate convex functions, and implement online linear regression on 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 [Zinkevich, 2003] and MetaGrad.
We conduct all the experiments on a personal laptop equipped with Intel i7-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 is better than FLHexp in Fig. 2(a) and close to FLHstr 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 of 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 of different methods in Fig. 3, and have similar observations.

heading: 5 Conclusion and future work
text: In this paper, we develop a universal algorithm that is able to minimize the adaptive regret of general convex, exp-concave and strongly convex functions simultaneously. For each type of 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 to 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.
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 61976112, JiangsuSF grant BK20200064, Open Research Projects of Zhejiang Lab (NO. 2021KB0AB02).

Review summaries:
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.  This 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.  

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.

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.

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