Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient

By Tianbao Yang, Lijun Zhang, Rong Jin, Jinfeng Yi. 2016

180 citations recorded by the source corpus.

This work focuses on dynamic regret of online convex optimization that compares the performance of online learning to a clairvoyant who knows the sequence of loss functions in advance and hence selects the minimizer of the loss function at each step. By assuming that the clairvoyant moves slowly (i.e., the minimizers change slowly), we present several improved variation-based upper bounds of the dynamic regret under the true and noisy gradient feedback, which are {\it optimal} in light of the presented lower bounds. The key to our analysis is to explore a regularity metric that measures the temporal changes in the clairvoyant's minimizers, to which we refer as {\it path variation}. Firstly, we present a general lower bound in terms of the path variation, and then show that under full information or gradient feedback we are able to achieve an optimal dynamic regret. Secondly, we present a lower bound with noisy gradient feedback and then show that we can achieve optimal dynamic regrets under a stochastic gradient feedback and two-point bandit feedback. Moreover, for a sequence of smooth loss functions that admit a small variation in the gradients, our dynamic regret under the two-point bandit feedback matches what is achieved with full information.

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

Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “References [3, 15, 25, 38, 43, 44] chooses the reference points {y∗ t }t=1 with y∗ t = argminz∈X ft (z), where ft is the loss function at the t th iteration.”
Online Meta-Learning (2019, neutral): “In the dynamic regret setting (Herbster & Warmuth, 1995; Yang et al., 2016; Besbes et al., 2015), the performance of the online learner’s model sequence is compared against the sequence of optimal solutions corresponding to each loss function in the sequence.”
Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “[25], [31] extend it for nonstrongly convex and non-convex functions, respectively.”
Improved Dynamic Regret for Non-degenerate Functions (2016, background): “…in analyzing a more stringent metric— dynamic regret (Besbes et al., 2015; Hall and Willett, 2013; Jadbabaie et al., 2015; Mokhtari et al., 2016; Yang et al., 2016), in which the cumulative loss of the learner is compared against a sequence of local minimizers, i.e., where x ∗ t ∈ argmin ∈X f t…”
Tracking Moving Agents via Inexact Online Gradient Descent Algorithm (2017, methodology): “Next, we briefly remark on the path length definitions used in [12], [40].”
Dynamic Regret of Strongly Adaptive Methods (2017, background): “When a prior knowledge of P(w∗1, . . . ,w∗T ) is available, D-Regret(w∗1, . . . ,w ∗ T ) can be upper bounded by O( √ TP(w∗1, . . . ,w∗T )) (Yang et al., 2016).”
Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “[25, 31] extend it for non-strongly convex and non-convex functions, respectively.”
Distributed Online Optimization in Dynamic Environments Using Mirror Descent (2016, background): “[31] provide optimal bounds for when the minimizer belongs to the feasible set.”
Understand Dynamic Regret with Switching Cost for Online Decision Making (2019, background): “Many other previous researches investigate the regret under dierent denitions of dynamics such as parameter variation [19, 34, 44, 47], functional variation [7, 25, 46], gradient variation [17], and the mixed regularity [16, 24].”
Adaptive Online Learning in Dynamic Environments (2018, background): “Although there exist lower bounds for the restricted dynamic regret [Besbes et al., 2015, Yang et al., 2016], to the best of our knowledge, this is the ﬁrst lower bound for the general dynamic regret.”