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

arXiv: https://arxiv.org/abs/1605.04638 · HTML: https://mlsanity.com/paper/1605.04638/

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2016.

## Built on by (most cited first, 30 of 66)

- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Adapting to Online Label Shift with Provable Guarantees](https://mlsanity.com/paper/2207.02121/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [Adapting to Continuous Covariate Shift via Online Density Ratio Estimation](https://mlsanity.com/paper/2302.02552/) (2023)
- [A closer look at temporal variability in dynamic online learning](https://mlsanity.com/paper/2102.07666/) (2021)
- [Dynamic Regret of Online Markov Decision Processes](https://mlsanity.com/paper/2208.12483/) (2022)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Towards Fair Disentangled Online Learning for Changing Environments](https://mlsanity.com/paper/2306.01007/) (2023)
- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [An Equivalence Between Static and Dynamic Regret Minimization](https://mlsanity.com/paper/2406.01577/) (2024)
- [Online Continual Adaptation with Active Self-Training](https://mlsanity.com/paper/2106.06526/) (2021)
- [Improved Dynamic Regret for Online Frank-Wolfe](https://mlsanity.com/paper/2302.05620/) (2023)
- [Non-Convex Bilevel Optimization with Time-Varying Objective Functions](https://mlsanity.com/paper/2308.03811/) (2023)
- [Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback](https://mlsanity.com/paper/2112.14332/) (2021)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Particle-based Online Bayesian Sampling](https://mlsanity.com/paper/2302.14796/) (2023)
- [Learning Rate Schedules in the Presence of Distribution Shift](https://mlsanity.com/paper/2303.15634/) (2023)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [Optimal Dynamic Regret in LQR Control](https://mlsanity.com/paper/2206.09257/) (2022)

## Abstract (arXiv)

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.