Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization

Abstract

Stochastically Extended Adversarial (SEA) model is introduced by Sachs et al. [2022] as an interpolation between stochastic and adversarial online convex optimization. Under the smoothness condition, they demonstrate that the expected regret of optimistic follow-the-regularized-leader (FTRL) depends on the cumulative stochastic variance ${\sigma }_{1:T}^2$ and the cumulative adversarial variation ${\Sigma }_{1:T}^2$ for convex functions. They also provide a slightly weaker bound based on the maximal stochastic variance ${\sigma }_{\max }^2$ and the maximal adversarial variation ${\Sigma }_{\max }^2$ for strongly convex functions. Inspired by their work, we investigate the theoretical guarantees of optimistic online mirror descent (OMD) for the SEA model. For convex and smooth functions, we obtain the same $\mathcal{O}(\sqrt{{\sigma }_{1:T}^2}+\sqrt{{\Sigma }_{1:T}^2})$ regret bound, without the convexity requirement of individual functions. For strongly convex and smooth functions, we establish an $\mathcal{O}(({\sigma }_{\max }^2+{\Sigma }_{\max }^2)\log ({\sigma }_{1:T}^2+{\Sigma }_{1:T}^2))$ bound, better than their $\mathcal{O}(({\sigma }_{\max }^2+{\Sigma }_{\max }^2)\log T)$ result. For exp-concave and smooth functions, we achieve a new $\mathcal{O}(d\log ({\sigma }_{1:T}^2+{\Sigma }_{1:T}^2))$ bound. Owing to the OMD framework, we broaden our work to study dynamic regret minimization and scenarios where the online functions are non-smooth. We establish the first dynamic regret guarantee for the SEA model with convex and smooth functions, which is more favorable than static regret bounds in non-stationary scenarios. Furthermore, to deal with non-smooth and convex functions in the SEA model, we propose novel algorithms building on optimistic OMD with an implicit update, which provably attain static regret and dynamic regret guarantees without smoothness conditions.

v3 substantially improves the presentation and has a few improvements, including the regret bound for strongly convex functions; v2 is an extended version that enriches the content with improved regret bounds for strongly convex functions, discussions on the optimism design for dynamic regret minimization, and extensions to non-smooth scenarios; v1 is the ICML 2023 conference version

Cited by in corpus (1)

• Universal Online Convex Optimization Meets Second-order Bounds