--- title: "Online Learning in Changing Environments" authors: - "Lijun Zhang" doi: "10.24963/ijcai.2020/731" url: "https://ijcai.org/proceedings/2020/731" pdf: "https://ijcai.org/proceedings/2020/0731.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "5178-5182" track: "Early Career" keywords: - "Machine Learning: Big data; Scalability" - "Machine Learning: Online Learning" - "Machine Learning: Time-series;Data Streams" --- # Online Learning in Changing Environments Lijun Zhang *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 5178-5182. DOI: [10.24963/ijcai.2020/731](https://doi.org/10.24963/ijcai.2020/731) ## Abstract The usual goal of online learning is to minimize the regret, which measures the performance of online learner against a fixed comparator. However, it is not suitable for changing environments in which the best decision may change over time. To address this limitation, new performance measures, including dynamic regret and adaptive regret have been proposed to guide the design of online algorithms. In dynamic regret, the learner is compared with a sequence of comparators, and in adaptive regret, the learner is required to minimize the regret over every interval. In this paper, we will review the recent developments in this area, and highlight our contributions. Specifically, we have proposed novel algorithms to minimize the dynamic regret and adaptive regret, and investigated the relationship between them. ## Full text ## 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. ## References 1. [Besbes et al., 2015] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227-1244, 2015. 2. [Cesa-Bianchi and Lugosi, 2006] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cam- bridge University Press, 2006. 3. [Daniely et al., 2015] Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In Pro- ceedings of the 32nd International Conference on Machine Learning, pages 1405-1411, 2015. 4. [Freund et al., 1997] Yoav Freund, Robert E. Schapire, Yo- ram Singer, and Manfred K. Warmuth. Using and combi- ning predictors that specialize. In Proceedings of the 29h Annual ACM Symposium on Theory of Computing, pages 334-343, 1997. 5. [György et al., 2012] András György, Tamás Linder, and Gábor Lugosi. Efficient tracking of large classes of experts. IEEE Transactions on Information Theory, 58(11):6709-6725, 2012. 6. [Hall and Willett, 2013] Eric C. Hall and Rebecca M. Wil- lett. Dynamical models and tracking regret in online con- vex programming. In Proceedings of the 30th Internati- onal Conference on Machine Learning, pages 579-587, 2013. 7. [Hazan and Seshadhri, 2007] Elad Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. Elec- tronic Colloquium on Computational Complexity, 88, 2007. 8. [Hazan and Seshadhri, 2009] Elad Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th Annual International Confe- rence on Machine Learning, pages 393-400, 2009. 9. [Hazan et al., 2007] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex op- timization. Machine Learning, 69(2-3):169-192, 2007. 10. [Hazan, 2016] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325, 2016. 11. [Jadbabaie et al., 2015] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online opti- mization: Competing with dynamic comparators. In Pro- ceedings of the 18th International Conference on Artificial Intelligence and Statistics, 2015. 12. [Jun et al., 2017a] Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Proceedings of the 20th International Conference on Artificial Intelli- gence and Statistics, pages 943-951, 2017. 13. [Jun et al., 2017b] Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Online learning for changing environments using coin betting. Electronic Journal of Statistics, 11(2):5282-5310, 2017. 14. [Littlestone and Warmuth, 1994] Nick Littlestone and Man- fred K. Warmuth. The weighted majority algorithm. In- formation and Computation, 108(2):212-261, 1994. 15. [Mokhtari et al., 2016] Aryan Mokhtari, Shahin Shahram- pour, Ali Jadbabaie, and Alejandro Ribeiro. Online opti- mization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on Decision and Control, pages 7195- 7201, 2016. 16. [Shalev-Shwartz, 2011] Shai Shalev-Shwartz. Online lear- ning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011. 17. [van Erven and Koolen, 2016] Tim van Erven and Wouter M Koolen. MetaGrad: Multiple learning rates in online lear- ning. In Advances in Neural Information Processing Sys- tems 29, pages 3666-3674, 2016. 18. [Wang et al., 2018] Guanghui Wang, Dakuan Zhao, and Li- jun Zhang. Minimizing adaptive regret with one gradient per iteration. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 2762- 2768, 2018. 19. [Yang et al., 2016] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Op- timal dynamic regret of online learning with true and noisy gradient. In Proceedings of the 33rd International Confe- rence on Machine Learning, pages 449-457, 2016. 20. [Zhang et al., 2017] Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. In Advances in Neural In- formation Processing Systems 30, pages 732-741, 2017. 21. [Zhang et al., 2018a] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31, pages 1323-1333, 2018. 22. [Zhang et al., 2018b] Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Confe- rence on Machine Learning, 2018. 23. [Zhang et al., 2019a] Lijun Zhang, Tie-Yan Liu, and Zhi- Hua Zhou. Adaptive regret of convex and smooth functi- ons. In Proceedings of the 36th International Conference on Machine Learning, pages 7414-7423, 2019. 24. [Zhang et al., 2019b] Lijun Zhang, Guanghui Wang, Wei- Wei Tu, and Zhi-Hua Zhou. Dual adaptivity: A univer- sal algorithm for minimizing the adaptive regret of convex functions. ArXiv e-prints, arXiv:1906.10851, 2019. 25. [Zhang et al., 2020] Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret si- multaneously. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020. 26. [Zinkevich, 2003] Martin Zinkevich. Online convex pro- gramming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Ma- chine Learning, pages 928-936, 2003.