Online Composite Optimization Between Stochastic and Adversarial Environments

We study online composite optimization under the Stochastically Extended Adversarial (SEA) model. Specifically, each loss function consists of two parts: a fixed non-smooth and convex regularizer, and a time-varying function which can be chosen either stochastically, adversarially, or in a manner that interpolates between the two extremes. In this setting, we show that for smooth and convex time-varying functions, optimistic composite mirror descent (OptCMD) can obtain an O( σ 2 1:T + Σ 2 1:T ) regret bound, where σ 2 1:T and Σ 2 1:T denote the cumulative stochastic variance and the cumulative adversarial variation of time-varying functions, respectively. For smooth and strongly convex time-varying functions, we establish an O((σ 2 max + Σ 2 max ) log(σ 2 1:T + Σ 2 1:T )) regret bound, where σ 2 max and Σ 2 max denote the maximal stochastic variance and the maximal adversarial variation, respectively. For smooth and exp-concave time-varying functions, we achieve an O(d log(σ 2 1:T + Σ 2 1:T )) bound where d denotes the dimensionality. Moreover, to deal with the unknown function type in practical problems, we propose a multilevel universal algorithm that is able to achieve the desirable bounds for three types of time-varying functions simultaneously. It should be noticed that all our findings match existing bounds for the SEA model without the regularizer, which implies that there is no price in regret bounds for the benefits gained from the regularizer.