Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization

arXiv:2112.14368v3 Announce Type: replace
Abstract: We investigate online convex optimization in non-stationary environments and choose dynamic regret as the performance measure, defined as the difference between cumulative loss incurred by the online algorithm and that of any feasible comparator sequence. Let $T$ be the time horizon and $P_T$ be the path length that essentially reflects the non-stationarity of environments, the state-of-the-art dynamic regret is $\mathcal{O}(\sqrt{T(1+P_T)})$. Although this bound is proved to be minimax optimal for convex functions, in this paper, …

abstract algorithm arxiv cs.lg difference dynamic environments horizon loss optimization performance type