  In the field of online convex optimization, some efficient algorithms have
been designed for each of the individual classes of objective functions, e.g.,
convex, strongly convex, and exp-concave. However, existing regret analyses,
including those of universal algorithms, are limited to cases in which the
objective functions in all rounds belong to the same class, and cannot be
applied to cases in which the property of objective functions may change in
each time step. To address such cases, this paper proposes a new regime which
we refer to as \textit{contaminated} online convex optimization. In the
contaminated case, regret is bounded by $O(\log T+\sqrt{k\log T})$ when some
universal algorithms are used, and bounded by $O(\log T+\sqrt{k})$ when our
proposed algorithms are used, where $k$ represents how contaminated objective
functions are. We also present a matching lower bound of $\Omega(\log T +
\sqrt{k})$. These are intermediate bounds between a convex case and a strongly
convex or exp-concave case.
