Online Composite Optimization Between Stochastic and Adversarial Environments

Abstract

We study online composite optimization under the Stochastically Extended Ad-versarial (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 be-tween 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 ( (cid:112) σ 21: T + (cid:112) Σ 21: T ) regret bound, where σ 21: T and Σ 21: 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 (( σ 2max + Σ 2max ) log( σ 21: T + Σ 21: T )) regret bound, where σ 2max and Σ 2max 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( σ 21: T + Σ 21: T )) bound where d denotes the dimensionality. Moreover, to deal with the unknown function type in practical problems, we propose a multi-level 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