Optimistic Online Convex Optimization in Dynamic Environments

In this paper, we study the optimistic online convex optimization problem in dynamic environments. Existing works have shown that Ader enjoys an Oleft(√left(1+PTright)Tright) dynamic regret upper bound, where T is the number of rounds, and PT is the path length of the reference strategy sequence. However, Ader is not environment-adaptive. Based on the fact that optimism provides a framework for implementing environment-adaptive, we replace Greedy Projection (GP) and Normalized Exponentiated Subgradient (NES) in Ader with Optimistic-GP and Optimistic-NES respectively, and name the corresponding algorithm ONES-OGP. We also extend the doubling trick to the adaptive trick, and introduce three characteristic terms naturally arise from optimism, namely MT, widetildeMT and VT+1L2ρleft(ρ+2 PTright)leqslantvarrho2 VTDT, to replace the dependence of the dynamic regret upper bound on T. We elaborate ONES-OGP with adaptive trick and its subgradient variation version, all of which are environment-adaptive.