Online Learning in Changing Environments

1 Introduction

Online learning is a well established learning paradigm which has both theoretical and practical appeals [Shalev-Shwartz, 2011]. It is performed in a sequence of consecutive rounds, where at iteration t the learner chooses a decision wt from a set W. After committing to this choice, a cost function ft : W ↦→ R is revealed and the learner suffers a loss ft(wt). The goal of online learning is to minimize the cumulative loss ∑Tt=1 ft(wt), and the traditional performance measure is regret:

defined as the difference between the cumulative loss of the online learner and that of the best decision chosen in hindsight. When both the set W and the function ft(·) are convex, it becomes online convex optimization (OCO) [Zinkevich, 2003].

In the literature, there exist plenty of algorithms and theories for minimizing the regret [Cesa-Bianchi and Lugosi, 2006; Hazan, 2016]. However, when the environment is changing, regret is not a suitable measure, since it compares the learner against a fixed decision. And for the same reason, the definition in (1) is also referred to as static regret. To address this limitation, recent studies have introduced new performance measures, including dynamic regret and adaptive regret, to measure the performance of online learner.

In dynamic regret, the learner is compared against a sequence of comparators u1, . . . , uT ∈ W [Zinkevich, 2003], i.e.,

It is well-known that in the worst case, a sublinear dynamic regret is impossible. The dynamic regret is usually bounded in terms of some regularities on the comparator sequence or the function sequence [Besbes et al., 2015; Jadbabaie et al., 2015]. As shown in (2), dynamic regret deals with changing environments from a global prospective, as it measures the performance over the whole interval [1, T] but allows the comparator to change over time.

On the other hand, adaptive regret takes a local perspective, and aims to minimize the static regret over every interval. Given a parameter τ, the strong version of adaptive regret is defined as the maximum static regret over intervals of length τ [Daniely et al., 2015], i.e.,

Note that the optimal decision for different intervals could be different. By minimizing the adaptive regret, we essentially enforce the learner to compete with a changing comparator.

In this paper, we will review the recent developments on dynamic regret and adaptive regret under the setting of OCO, including our contributions. Specifically, we contribute to this area in the following aspects.

• We have considered the worst-case of dynamic regret in (2), and exploited the curvature of the functions, such as smoothness and strong convexity, to improve the regret bound [Yang et al., 2016; Zhang et al., 2017].
• For the general definition of dynamic regret, we propose a novel algorithm named Ader, which attains an O(√T (1 + PT )) dynamic regret, where PT is the pathlength of the comparator sequence [Zhang et al., 2018a].

We also prove an Ω(√T(1+PT )) lower bound, showing that our upper bound is optimal.

• For adaptive regret, we reduce the number of gradient evaluations in the t-th round from O(log t) to 1 without affecting the performance [Wang et al., 2018], and make use of smoothness to establish problem-dependent bounds [Zhang et al., 2019a]. We also develop a universal algorithm that is able to minimize the adaptive regret of multiple types of convex functions simultaneously [Zhang et al., 2019b].
• To investigate the relationship between dynamic regret and adaptive regret, we demonstrate that the worst-case dynamic regret can be upper bounded in terms of the adaptive regret and the functional variation [Zhang et al., 2018b]. Furthermore, we develop novel algorithms that are able to minimize the general dynamic regret and adaptive regret simultaneously [Zhang et al., 2020].

2 Dynamic Regret

We first discuss the worst-case dynamic regret, and then move to the general one.

2.1 Worst-case Dynamic Regret

Under the setting of OCO, most of previous studies about dynamic regret focus on the worst-case of (2), in which the sequence of comparators consists of minimizers of online functions [Jadbabaie et al., 2015], i.e.,

where w∗ t ∈ argminw∈W ft(w) is a minimizer of ft(·) over W.

Let P ∗ T be the path-length of the minimizer sequence, i.e.,

When the loss functions are strongly convex and smooth, Mokhtari et al. [2016] show that online gradient descent (OGD) ensures D-Regret(w∗ 1 , . . . , w∗T ) = O(P ∗ T ). We have demonstrated that this rate is also attainable for convex and smooth functions under the condition that the minimizers lie in the interior of W [Yang et al., 2016]. Furthermore, when the minimizer of each function is unique, a simple baseline which plays the minimizer of the previous round, i.e.,

attains an O(P ∗ T ) worst-case dynamic regret.

Besides the path-length, we have introduced the squared path-length [Zhang et al., 2017]:

as a new regularity of the comparator sequence. The advantage of S∗T is that it could be much smaller than P ∗ T if the minimizer moves slowly. When all the functions are strongly convex and smooth, we propose to apply gradient descent multiple times in each round, and demonstrate that the dynamic regret could be reduced from O(P ∗ T ) to O(min(P ∗ T , S∗T )). We then extend our theoretical guarantee to semi-strongly convex or self-concordant functions.

Instead of measuring the complexity of the comparator sequence, Besbes et al. [2015] propose to evaluate the movement of the loss functions as follows:

Besbes et al. show that a restarted OGD algorithm equipped with a prior knowledge of an upper bound VT ≥ FT achieves O(V 1/3 T T 2/3 ) and O(logT √VTT) dynamic regret for convex functions and strongly convex functions, respectively. However, these bounds depend on the predetermined VT rather than the actual FT .

2.2 General Dynamic Regret

Although one can show that D-Regret(w∗ 1 , . . . ,w∗T ) ≥ D-Regret(u1, . . . , uT ) for any u1, . . . , uT ∈ W, it does not imply the former one is stronger since an upper bound for D-Regret(w∗ 1 , . . . ,w∗T ) could be very loose for D-Regret(u1, . . . , uT ). In fact, the definition in (2) is more general since it holds for any sequence of comparators, and thus includes the static regret and the worst-case dynamic regret as special cases.

In his seminal work, Zinkevich [2003] shows that OGD with a constant step size attains a dynamic regret of O(√T (1 + PT )) for any sequence u1, . . . , uT , where

This upper bound is adaptive in the sense that it automatically becomes tighter when the comparators change slowly. Hall and Willett [2013] have investigated the general dynamic regret when a dynamic model is available to predict the comparator sequence.

For the general dynamic regret, we have established an Ω(√T(1+PT )) lower bound, which indicates that results of Zinkevich [2003] and Hall and Willett [2013] are far away from the optimum. To address this limitation, we develop an optimal algorithm, namely adaptive learning for dynamic environment (Ader), which attains an O(√T (1 + PT )) dynamic regret. In the following, we give a brief description of Ader.

2.3 Ader

Ader follows the framework of prediction with expert advice (PAE) [Cesa-Bianchi and Lugosi, 2006], and is inspired by the strategy of maintaining multiple learning rates in MetaGrad [van Erven and Koolen, 2016]. The basic idea is to run multiple OGD algorithms in parallel, each with a different step size that is optimal for a specific path-length, and combine them with an expert-tracking algorithm.

Algorithm 1 Ader: Meta-algorithm

Require: A step size α, and a set H containing step sizes for experts

• 1: Activate a set of experts {Eη |η ∈ H} by invoking Algorithm 2 for each step size η ∈ H
• 2: Sort step sizes in ascending order η1 ≤ η2 ≤ · · · ≤ ηN, and set ωηi 1 = C i(i+1)
• 3: for t = 1, . . . , T do
• 4: Receive wη t from each expert Eη
• 5: Output

• 6: Observe the loss function ft(·)
• 7: Update the weight of each expert by

• 8: Send gradient ∇ft(wη t ) to each expert Eη
• 9: end for

Meta-algorithm Our meta-algorithm, summarized in Algorithm 1, is built upon the exponentially weighted average forecaster [Cesa-Bianchi and Lugosi, 2006]. The inputs of the meta-algorithm are its own step size α, and a set H of step sizes for experts. In Step 1, we active a set of experts {Eη |η ∈ H} by invoking the expert-algorithm for each η ∈ H. In Step 2, we set the initial weight of each expert. Let ηi be the i-th smallest step size in H. The weight of Eηi is chosen as

In each round, the meta-algorithm receives a set of predictions {wη t |η ∈ H} from all experts (Step 4), and outputs the weighted average (Step 5):

where ωη t is the weight assigned to expert Eη . After observing the loss function, the weights of experts are updated according to the exponential weighting scheme (Step 7). In the last step, we send the gradient ∇ft(wη t ) to each expert Eη so that they can update their own predictions.

Expert-algorithm As shown in Algorithm 2, we use OGD as the expert-algorithm, which takes the step size η as its input. In Step 3 of Algorithm 2, each expert submits its prediction wη t to the meta-algorithm, and receives the gradient ∇ft(wη t ) in Step 4. Then, in Step 5 it performs gradient descent

to get the prediction for the next round.

Next, we specify the parameter setting and our dynamic regret. The set H is constructed in the way such that for any possible sequence of comparators, there exists a step size that

Algorithm 2 Ader: Expert-algorithm

Require: The step size η

• 1: Let wη 1 be any point inW
• 2: for t = 1, . . . , T do
• 3: Submit wη t to the meta-algorithm
• 4: Receive gradient ∇ft(wη t ) from the meta-algorithm

5:

• 6: end for

is nearly optimal. To control the size of H, we use a geometric series with ratio 2:

where G is the upper bound of the norm of gradients, D is the upper bound of the diameter of W, and N = ⌈ 1 2 log2(1+ 4T/7)⌉ + 1. Then, with an appropriate choice of α, we can show that Ader is equipped with an optimal dynamic regret:

With the help of surrogate losses, we have proposed an improved Ader and reduced the number of gradient evaluations per round from N = O(logT) to 1. Furthermore, we have extended Ader to the setting that a sequence of dynamical models is available to characterize the comparators.

3 Adaptive Regret

Adaptive regret has been studied under the settings of PAE [Littlestone and Warmuth, 1994; Gy¨orgy et al., 2012] and OCO. In this paper, we focus on the later one.

The concept of adaptive regret is formally introduced by Hazan and Seshadhri [2007] to OCO, 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:

which is the maximum regret over any contiguous interval. They develop a novel algorithm named as follow the leading history (FLH), which runs an instance of low-regret algorithm in each round as an expert, and then combines them with an expert-tracking method. To improve the efficiency, Hazan and Seshadhri deploy a data-streaming technique to prune the set of experts, and as a result only O(log t) experts are stored at round t. The efficient version of FLH attains O(d log2 T) and O(√T log3 T) adaptive regrets for exponentially concave (abbr. exp-concave) functions and convex functions, respectively [Hazan and Seshadhri, 2009]. For strongly convex functions, we have designed an efficient algorithm with an O(log2 T) adaptive regret [Zhang et al., 2018b].

However, the weakly adaptive regret does not respect short intervals well. To avoid this limitation, Daniely et al. [2015]

propose the strongly adaptive regret in (3), which emphasizes the dependence on the interval length. For convex functions, Daniely et al. [2015] establish an O(√τ logT) strongly adaptive regret. In a subsequent work, Jun et al. [2017a] improve the strongly adaptive regret to O(√τ logT). Jun et al. [2017b] have investigated how to exploit smoothness to further improve the adaptive regret, and we go one step further by making the bound fully problem-dependent [Zhang et al., 2019a]. All the previous algorithms designed for adaptive regret require to query the gradient at least O(log t) times in the t-th round. To address this limitation, we propose to use surrogate losses to reduce the number of gradient evaluations per round to 1 [Wang et al., 2018].

Existing algorithms for adaptive regret 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 [van Erven and Koolen, 2016], that attain optimal static regret for multiple types of convex functions simultaneously. Along this line of research, we have proposed the first universal algorithm for minimizing the adaptive regret of convex functions [Zhang et al., 2019b]. Due to limitations of space, we take exp-concave functions as an example to illustrate the key idea in the next section.

3.1 AUniversal Algorithm for Adaptive Regret

Inspired by MetaGrad, we constructs surrogate losses parameterized by a learning rate η:

By considering different values of η, we can handle the uncertainty of the modulus of exp-concavity. To minimize the adaptive regret, we adopt the the idea of sleeping experts [Freund et al., 1997]. Specifically, we make use of the geometric covering (GC) intervals [Daniely et al., 2015] defined as I = ⋃k∈N∪{0} Ik, where

Then, we only focus on intervals in I. For each interval I = [r, s] ∈ I, we will create 1+⌈ 12 log2(s-r+1)⌉ experts, each of which minimizes one surrogate loss in {ℓηt (w)|η ∈ S(s - r + 1)} during I, where

These experts become active in round r and will be removed forever after round s. It is easy to verify that the surrogate loss ℓηt (·) is exp-concave. So, we can apply online Newton step (ONS) [Hazan et al., 2007] as the expert-algorithm to minimize ℓηt (·) during interval I.

To combine the solutions of active experts, we extend the meta-algorithm of MetaGrad, i.e., Tilted Exponentially Weighted Average (TEWA), to sleeping experts. Let At be the set consisting of all the active experts, and Eη I be the expert for an interval I ∈ I with learning rate η. Denote the prediction of expert Eη I at round t as wη t,I . Specifically, we submit the following decision in the t-th round

where Lηt-1,I is the cumulative loss of Eη I .

Our theoretical analysis shows that the above algorithm attains an O( dα log τ logT) strongly adaptive regret for αexp-concave functions. By introducing an additional surrogate loss for strongly convex functions, we obtain an O( 1λ log τ log T) strongly adaptive regret for λ-strongly convex functions. Meanwhile, the algorithm also ensures an O(√τ log T) bound for convex functions.

4 Relationship between Dynamic Regret and Adaptive Regret

While both the dynamic and adaptive regrets aim at coping with changing environments, little is known about their relationship. We make two contributions in this direction.

First, we show that the strongly adaptive regret in (3), together with the functional variation, can be used to upper bound the worst-case dynamic regret [Zhang et al., 2018b]. Let I1 = [r1, s1], . . . , Ik = [rk, sk] be a partition of [1, T ] and for each interval Ii, and define the local variation of functions as

We have proved that

D-Regret(w∗ 1 , . . . , w∗T )

Thus, an algorithm with a small strongly adaptive regret is automatically equipped with a tight dynamic regret. As a result, we obtain a series of algorithms for minimizing the dynamic regret that do not need any prior knowledge of the functional variation.

Second, we have proposed novel algorithms that are able to minimize the general dynamic regret and adaptive regret simultaneously [Zhang et al., 2020]. In fact, our theoretical guarantee is even stronger in the sense that one algorithm is able to minimize the dynamic regret over any interval.

5 Open Problems

Although significant progress has been made in dynamic regret and adaptive regret, there still remain many open problems in this area.

• In the analysis of the worst-case dynamic regret, we can exploit the curvature of functions, such as strong convexity and smoothness, to improve the bound. However, whether these conditions can be used to tighten the general dynamic regret remains open.
• Although we have shown that the worst-case dynamic regret can be upper bounded by the adaptive regret, the relationship between the general dynamic regret and the adaptive regret is unclear.

Acknowledgments

This work was partially supported by NSFC (61921006), and the Collaborative Innovation Center of Novel Software Technology and Industrialization.