  Stochastic and adversarial data are two widely studied settings in online
learning. But many optimization tasks are neither i.i.d. nor fully adversarial,
which makes it of fundamental interest to get a better theoretical
understanding of the world between these extremes. In this work we establish
novel regret bounds for online convex optimization in a setting that
interpolates between stochastic i.i.d. and fully adversarial losses. By
exploiting smoothness of the expected losses, these bounds replace a dependence
on the maximum gradient length by the variance of the gradients, which was
previously known only for linear losses. In addition, they weaken the i.i.d.
assumption by allowing, for example, adversarially poisoned rounds, which were
previously considered in the related expert and bandit settings. In the fully
i.i.d. case, our regret bounds match the rates one would expect from results in
stochastic acceleration, and we also recover the optimal stochastically
accelerated rates via online-to-batch conversion. In the fully adversarial case
our bounds gracefully deteriorate to match the minimax regret. We further
provide lower bounds showing that our regret upper bounds are tight for all
intermediate regimes in terms of the stochastic variance and the adversarial
variation of the loss gradients.
