Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions

Abstract

In this paper, we present an improved analysis for dynamic regret of strongly convex and smooth functions. Specifically, we investigate the Online Multiple Gradient Descent (OMGD) algorithm proposed by Zhang et al. (2017). The original analysis shows that the dynamic regret of OMGD is at most $\mathcal{O}(\min \{{\mathcal{P}}_T,{\mathcal{S}}_T\})$, where ${\mathcal{P}}_T$ and ${\mathcal{S}}_T$ are path-length and squared path-length that measures the cumulative movement of minimizers of the online functions. We demonstrate that by an improved analysis, the dynamic regret of OMGD can be improved to $\mathcal{O}(\min \{{\mathcal{P}}_T,{\mathcal{S}}_T,{\mathcal{V}}_T\})$, where ${\mathcal{V}}_T$ is the function variation of the online functions. Note that the quantities of ${\mathcal{P}}_T,{\mathcal{S}}_T,{\mathcal{V}}_T$ essentially reflect different aspects of environmental non-stationarity -- they are not comparable in general and are favored in different scenarios. Therefore, the dynamic regret presented in this paper actually achieves a \emph{best-of-three-worlds} guarantee and is strictly tighter than previous results.

arXiv commentTo appear at L4DC 2021

References in corpus (12)

• Adaptive Online Learning in Dynamic Environments
• Improved Dynamic Regret for Non-degenerate Functions
• Online Control with Adversarial Disturbances
• Dynamic Regret of Strongly Adaptive Methods
• Tracking the Best Expert in Non-stationary Stochastic Environments
• Online Optimization with Memory and Competitive Control
• Non-stationary Online Learning with Memory and Non-stochastic Control
• Minimizing Dynamic Regret and Adaptive Regret Simultaneously
• Dynamic Regret of Convex and Smooth Functions
• Online Forecasting of Total-Variation-bounded Sequences
• Bandit Convex Optimization in Non-stationary Environments
• Equipping Experts/Bandits with Long-term Memory

Cited by in corpus (2)

• Dynamic Regret of Convex and Smooth Functions
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints