From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, existing methods to attain optimal dynamic regret bounds for strongly convex losses and exp-concave losses remain analytically intricate or computationally demanding. In this paper, we present a simple framework that reduces dynamic regret minimization to switching regret minimization. The key idea is to construct, for any comparator sequence, an auxiliary random sequence that is unbiased at each round, with controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we decompose dynamic regret into the expected switching regret against the infrequently-changing random sequence and a variance-controlled approximation error. Consequently, any algorithm with a switching regret guarantee can be plugged into our framework to obtain a corresponding dynamic regret bound. In particular, by instantiating the framework with existing switching-regret algorithms, we can obtain an $\tilde{\mathcal{O}}(T^{1/3}{P}_T^{2/3})$ dynamic regret bound for strongly convex losses and $\tilde{\mathcal{O}}(d^{2/3}{T}^{1/3}{P}_T^{2/3})$ for exp-concave losses, where $P_T$ denotes the path-length and $d$ denotes the dimension. For general convex losses, the same reduction recovers the $\mathcal{O}(\sqrt{T(1+P_T)})$ dynamic regret bound. Notably, all our findings match the known minimax-optimal bounds, up to logarithmic factors, and the modularity of our framework makes it easy to understand and implement.