Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory
This work provides a more general and robust framework for online convex optimization, particularly for scenarios with varying movement costs, which is relevant for researchers and practitioners dealing with dynamic environments and resource constraints.
This paper addresses dynamic regret in unconstrained online convex optimization (OCO) with time-varying movement costs, where the cost coefficients $\lambda_t$ can change arbitrarily. The authors propose a new algorithm that achieves the first comparator-adaptive dynamic regret bound of $\widetilde{\mathcal{O}}(\sqrt{(1+P_T)(T+\sum_t \lambda_t)})$, which is optimal for static and dynamic regret in standard OCO when $\lambda_t=0$.
In this paper, we study dynamic regret in unconstrained online convex optimization (OCO) with movement costs. Specifically, we generalize the standard setting by allowing the movement cost coefficients $λ_t$ to vary arbitrarily over time. Our main contribution is a novel algorithm that establishes the first comparator-adaptive dynamic regret bound for this setting, guaranteeing $\widetilde{\mathcal{O}}(\sqrt{(1+P_T)(T+\sum_t λ_t)})$ regret, where $P_T$ is the path length of the comparator sequence over $T$ rounds. This recovers the optimal guarantees for both static and dynamic regret in standard OCO as a special case where $λ_t=0$ for all rounds. To demonstrate the versatility of our results, we consider two applications: OCO with delayed feedback and OCO with time-varying memory. We show that both problems can be translated into time-varying movement costs, establishing a novel reduction specifically for the delayed feedback setting that is of independent interest. A crucial observation is that the first-order dependence on movement costs in our regret bound plays a key role in enabling optimal comparator-adaptive dynamic regret guarantees in both settings.