Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound

By Yawei Zhao, Shuang Qiu, Ji Liu. 2021

13 citations recorded by the source corpus.

In online learning, the dynamic regret metric chooses the reference oracle that may change over time, while the typical (static) regret metric assumes the reference solution to be constant over the whole time horizon. The dynamic regret metric is particularly interesting for applications, such as online recommendation (since the customers’ preference always evolves over time). While the online gradient (OG) method has been shown to be optimal for the static regret metric, the optimal algorithm for the dynamic regret remains unknown. In this article, we show that proximal OG (a general version of OG) is optimum to the dynamic regret by showing that the proved lower bound matches the upper bound. It is highlighted that we provide a new and general lower bound of dynamic regret. It provides new understanding about the difficulty to follow the dynamics in the online setting.

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

1. En Zhu
2. Peilin Zhao
3. Jianping Yin
4. Kunlun He
5. Chenkai Yu
6. Zongren Li
7. Xinwang Liu
8. Yawei Zhao

In Electrical and Electronic Engineering

1. Yawei Zhao
2. Xingxing Zhang
3. Ji Liu

In Management Science and Operations Research

1. En Zhu
2. Peilin Zhao
3. Jianping Yin
4. Kunlun He
5. Chenkai Yu
6. Zongren Li
7. Xinwang Liu
8. Yawei Zhao

Citations in the corpus

• Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “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): “Since the lower bound is still same with the case of no switching cost [50], it implies that the switching cost does not change the diculty of the online decision making problem for the OCO 2Generally, the dynamic environment means the distribution of the data stream may change over time.”