  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.
