In this paper, we propose an online convex optimization method with two
different levels of adaptivity. On a higher level, our method is agnostic to
the specific type and curvature of the loss functions, while at a lower level,
it can exploit the niceness of the environments and attain problem-dependent
guarantees. To be specific, we obtain $\mathcal{O}(\ln V_T)$, $\mathcal{O}(d
\ln 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
$\hat{\mathcal{O}}(\cdot)$-notation omits logarithmic factors on $V_T$. Our
result finds broad implications and applications. It not only safeguards the
worst-case guarantees, but also implies the small-loss bounds in analysis
directly. Besides, it draws deep connections with adversarial/stochastic convex
optimization and game theory, further validating its practical potential. Our
method is based on a multi-layer online ensemble incorporating novel
ingredients, including carefully-designed optimism for unifying diverse
function types and cascaded corrections for algorithmic stability. Remarkably,
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 customized surrogate losses.

本文提出了基于多层在线集成的在线凸优化方法，具有两种不同的适应性水平，并针对强凸、指数 - 凹和凸损失函数分别获得了收敛等效性和遗憾上界。