Adaptive Online Learning in Dynamic Environments

By Lijun Zhang, Shiyin Lu, Zhi-Hua Zhou. 2018

246 citations recorded by the source corpus.

In this paper, we study online convex optimization in dynamic environments, and aim to bound the dynamic regret with respect to any sequence of comparators. Existing work have shown that online gradient descent enjoys an $O(\sqrt{T}(1+P_T))$ dynamic regret, where $T$ is the number of iterations and $P_T$ is the path-length of the comparator sequence. However, this result is unsatisfactory, as there exists a large gap from the $\Omega(\sqrt{T(1+P_T)})$ lower bound established in our paper. To address this limitation, we develop a novel online method, namely adaptive learning for dynamic environment (Ader), which achieves an optimal $O(\sqrt{T(1+P_T)})$ dynamic regret. The basic idea is to maintain a set of experts, each attaining an optimal dynamic regret for a specific path-length, and combines them with an expert-tracking algorithm. Furthermore, we propose an improved Ader based on the surrogate loss, and in this way the number of gradient evaluations per round is reduced from $O(\log T)$ to $1$. Finally, we extend Ader to the setting that a sequence of dynamical models is available to characterize the comparators.

Subfields: Artificial Intelligence, Computer Science Applications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Ching-An Cheng
2. Byron Boots
3. En Zhu
4. Nolan Wagener
5. Shuang Qiu
6. Xinwang Liu
7. Peilin Zhao
8. Jianping Yin

In Computer Science Applications

1. Peilin Zhao
2. Yawei Zhao
3. Shuang Qiu
4. Ji Liu

In Management Science and Operations Research

1. Ching-An Cheng
2. En Zhu
3. Peilin Zhao
4. Jianping Yin
5. Jacob Sacks
6. Kunlun He
7. Chenkai Yu
8. Zongren Li

Citations in the corpus

• Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “The implied static regret O (√TM ) is consistent with the dynamic regret result in References [42, 46], which is proven to be optimum.”
• Understand Dynamic Regret with Switching Cost for Online Decision Making (2019, methodology): “But, [45] works in the expert seŠing, not a general seŠing of online convex optimization.”
• An Online Learning Approach to Model Predictive Control (2019, background): “For problems in non-stationary setups, a normalized way to describe the accumulated costs in the online learning literature is through the concept of dynamic regret [14, 34], which is defined as”
• Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “) Our lower bound holds for any 0 ≤ β < 1, but the result in [39] only holds for the case of β = 0.”
• Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “When β > 0, our upper bound is O (√ T Dβ + √ T ) , which extends the known result for β = 0 [38], [39].”
• Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees (2022, unknown): “Techniques based on online learning and regret minimization provide performance guarantees for accumulated mistakes in terms of dynamic regret bounds (Kivinen et al., 2004; Cavallanti et al., 2007; Zhang et al., 2018; Cutkosky, 2020).”