# Improved Dynamic Regret for Non-degenerate Functions

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2016.

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

- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Adapting to Online Label Shift with Provable Guarantees](https://mlsanity.com/paper/2207.02121/) (2022)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (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)
- [Towards Fair Disentangled Online Learning for Changing Environments](https://mlsanity.com/paper/2306.01007/) (2023)
- [Online Federated Learning via Non-Stationary Detection and Adaptation amidst Concept Drift](https://mlsanity.com/paper/2211.12578/) (2022)
- [An Equivalence Between Static and Dynamic Regret Minimization](https://mlsanity.com/paper/2406.01577/) (2024)
- [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)
- [Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States](https://mlsanity.com/paper/2210.00997/) (2022)
- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [Minimizing Dynamic Regret on Geodesic Metric Spaces](https://mlsanity.com/paper/2302.08652/) (2023)
- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems](https://mlsanity.com/paper/2209.01608/) (2022)
- [On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization](https://mlsanity.com/paper/2301.09808/) (2023)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)
- [Dynamic Regret Convergence Analysis and an Adaptive Regularization Algorithm for On-Policy Robot Imitation Learning](https://mlsanity.com/paper/1811.02184/) (2018)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [Distributionally Time-Varying Online Stochastic Optimization under Polyak-Lojasiewicz Condition with Application in Conditional Value-at-Risk Statistical Learning](https://mlsanity.com/paper/2309.09411/) (2023)
- [Online Convex Optimization with Switching Cost and Delayed Gradients](https://mlsanity.com/paper/2310.11880/) (2023)
- [Continuous Online Learning and New Insights to Online Imitation Learning](https://mlsanity.com/paper/1912.01261/) (2019)

## Abstract (arXiv)

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.