  In this paper, we propose an online convex optimization approach with two
different levels of adaptivity. On a higher level, our approach is agnostic to
the unknown types and curvatures of the online functions, while at a lower
level, it can exploit the unknown niceness of the environments and attain
problem-dependent guarantees. Specifically, we obtain $\mathcal{O}(\log V_T)$,
$\mathcal{O}(d \log V_T)$ and $\hat{\mathcal{O}}(\sqrt{V_T})$ regret bounds for
strongly convex, exp-concave and convex loss functions, respectively, where $d$
is the dimension, $V_T$ denotes problem-dependent gradient variations and the
$\hat{\mathcal{O}}(\cdot)$-notation omits $\log V_T$ factors. Our result not
only safeguards the worst-case guarantees but also directly implies the
small-loss bounds in analysis. Moreover, when applied to adversarial/stochastic
convex optimization and game theory problems, our result enhances the existing
universal guarantees. Our approach is based on a multi-layer online ensemble
framework incorporating novel ingredients, including a carefully designed
optimism for unifying diverse function types and cascaded corrections for
algorithmic stability. Notably, despite its multi-layer structure, our
algorithm necessitates only one gradient query per round, making it favorable
when the gradient evaluation is time-consuming. This is facilitated by a novel
regret decomposition equipped with carefully designed surrogate losses.
