Understand Dynamic Regret with Switching Cost for Online Decision Making
By Yawei Zhao, Xingxing Zhang, En Zhu, Xinwang Liu, Jianping Yin. 2019
15 citations recorded by the source corpus.
As a metric to measure the performance of an online method, dynamic regret with switching cost has drawn much attention for online decision making problems. Although the sublinear regret has been provided in much previous research, we still have little knowledge about the relation between the dynamic regret and the switching cost. In the article, we investigate the relation for two classic online settings: Online Algorithms (OA) and Online Convex Optimization (OCO). We provide a new theoretical analysis framework that shows an interesting observation; that is, the relation between the switching cost and the dynamic regret is different for settings of OA and OCO. Specifically, the switching cost has significant impact on the dynamic regret in the setting of OA. But it does not have an impact on the dynamic regret in the setting of OCO. Furthermore, we provide a lower bound of regret for the setting of OCO, which is same with the lower bound in the case of no switching cost. It shows that the switching cost does not change the difficulty of online decision making problems in the setting of OCO.
Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, 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 Computer Networks and Communications
In Electrical and Electronic Engineering
In Management Science and Operations Research
Citations in the corpus
- Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “An online convex optimization method can achieve a static regret bound of order O (√ � ) and O (log� ) for convex and strongly convex loss functions, respectively [5, 13, 32, 48].”