Proximal Online Gradient is Optimum for Dynamic Regret

By Yawei Zhao, Shuang Qiu, Ji Liu. 2018

7 citations recorded by the source corpus.

In online learning, the dynamic regret metric chooses the reference (optimal) solution 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 method has been shown to be optimal for the static regret metric, the optimal algorithm for the dynamic regret remains unknown. In this paper, we show that proximal online gradient (a general version of online gradient) is optimum to the dynamic regret by showing that the proved lower bound matches the upper bound that slightly improves existing upper bound.

Subfields: Artificial Intelligence, Computational Mechanics, 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

In Computational Mechanics

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): “…learning algorithms has been widely studied for decades [Zinkevich, 2003, Hall and Willett, 2015, 2013, Jadbabaie et al., 2015, Yang et al., 2016, Bedi et al., 2018, Zhang et al., 2017a, Mokhtari et al., 2016, Zhang et al., 2018b, Gy¨orgy and Szepesv´ari, 2016, Wei et al., 2016, Zhao et al., 2018].”