Improved Dynamic Regret for Non-degenerate Functions

By Lijun Zhang, Tianbao Yang, Jinfeng Yi, Jing Rong, Zhi-Hua Zhou. 2016

139 citations recorded by the source corpus.

Recently, there has been a growing research interest in the analysis of dynamic regret, which measures the performance of an online learner against a sequence of local minimizers. By exploiting the strong convexity, previous studies have shown that the dynamic regret can be upper bounded by the path-length of the comparator sequence. In this paper, we illustrate that the dynamic regret can be further improved by allowing the learner to query the gradient of the function multiple times, and meanwhile the strong convexity can be weakened to other non-degenerate conditions. Specifically, we introduce the squared path-length, which could be much smaller than the path-length, as a new regularity of the comparator sequence. When multiple gradients are accessible to the learner, we first demonstrate that the dynamic regret of strongly convex functions can be upper bounded by the minimum of the path-length and the squared path-length. We then extend our theoretical guarantee to functions that are semi-strongly convex or self-concordant. To the best of our knowledge, this is the first time that semi-strong convexity and self-concordance are utilized to tighten the dynamic regret.

How researchers see this paper

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

Citations in the corpus

Adaptive Gradient-Based Meta-Learning Methods (2019, background): “The generality of ARUBA also allows for the incorporation of other dynamic regret bounds [25, 52] and other non-static notions of regret [27].”
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].”
Tracking Moving Agents via Inexact Online Gradient Descent Algorithm (2017, methodology): “Next, we briefly remark on the path length definitions used in [12], [40].”
Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, unknown): “When querying O (κ) with κ := β α gradients for every iteration, [26] improves the dynamic regret to be O (min{D∗, S∗}).”
Dynamic Regret of Strongly Adaptive Methods (2017, background): “Thus, D-Regret(w∗1, . . . ,w ∗ T ) can be treated as the worst case of the dynamic regret, and there are many works that were devoted to minimizing D-Regret(w∗1, . . . ,w ∗ T ) (Jadbabaie et al., 2015; Mokhtari et al., 2016; Yang et al., 2016; Zhang et al., 2017).”
Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “…assume f t is α strongly convex and β smooth, and the dynamic constraint is deﬁned by When querying O ( κ ) with κ := gradients for every iteration, Zhang et al. [2017a] improves the dynamic regret to be O (min { D ∗ ( T ) , S ∗ ( T ) ). deﬁnition } Comparing with the previous work, we obtain a…”
Adaptive Online Learning in Dynamic Environments (2018, background): “Zhang et al. [2017] propose online multiple gradient descent, and establish an O (min( P ∗ T , S ∗ T )) regret bound for (semi-)strongly convex and smooth functions.”