Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
This work provides an incremental improvement in theoretical analysis for online optimization, benefiting researchers in machine learning and optimization by offering a best-of-three-worlds guarantee for dynamic regret.
The paper tackles the problem of improving the dynamic regret bound for the Online Multiple Gradient Descent algorithm applied to strongly convex and smooth functions, achieving a tighter bound of O(min{P_T, S_T, V_T}) compared to the previous O(min{P_T, S_T}), where P_T, S_T, and V_T measure different aspects of environmental non-stationarity.
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.