To address the uncertainty in function types, recent progress in online
convex optimization (OCO) has spurred the development of universal algorithms
that simultaneously attain minimax rates for multiple types of convex
functions. However, for a $T$-round online problem, state-of-the-art methods
typically conduct $O(\log T)$ projections onto the domain in each round, a
process potentially time-consuming with complicated feasible sets. In this
paper, inspired by the black-box reduction of Cutkosky and Orabona (2018), we
employ a surrogate loss defined over simpler domains to develop universal OCO
algorithms that only require $1$ projection. Embracing the framework of
prediction with expert advice, we maintain a set of experts for each type of
functions and aggregate their predictions via a meta-algorithm. The crux of our
approach lies in a uniquely designed expert-loss for strongly convex functions,
stemming from an innovative decomposition of the regret into the meta-regret
and the expert-regret. Our analysis sheds new light on the surrogate loss,
facilitating a rigorous examination of the discrepancy between the regret of
the original loss and that of the surrogate loss, and carefully controlling
meta-regret under the strong convexity condition. In this way, with only $1$
projection per round, we establish optimal regret bounds for general convex,
exponentially concave, and strongly convex functions simultaneously.
Furthermore, we enhance the expert-loss to exploit the smoothness property, and
demonstrate that our algorithm can attain small-loss regret for multiple types
of convex and smooth functions.

通过黑匣子减少，我们使用简化域上定义的替代损失函数，构建了一种只需要进行一次投影的通用 OCO 算法，对于一轮在线问题，我们维护每种类型函数的一组专家，并通过元算法聚合他们的预测。我们的方法的关键在于针对强凸函数设计的专家损失函数，并通过创新地将遗憾分解为元遗憾和专家遗憾，从而对替代损失函数的遗憾和原损失函数的遗憾之间的差异进行了严格的研究，并在强凸性条件下仔细控制了元遗憾。通过这种方式，我们建立了一轮中的通用凸函数、指数凹函数和强凸函数的最优遗憾上界，并通过增强专家损失函数来利用光滑性质，从而证明了我们的算法可以达到多种类型的凸函数和光滑函数的小损失遗憾。