The projection operation is a critical component in a wide range of
optimization algorithms, such as online gradient descent (OGD), for enforcing
constraints and achieving optimal regret bounds. However, it suffers from
computational complexity limitations in high-dimensional settings or when
dealing with ill-conditioned constraint sets. Projection-free algorithms
address this issue by replacing the projection oracle with more efficient
optimization subroutines. But to date, these methods have been developed
primarily in the Euclidean setting, and while there has been growing interest
in optimization on Riemannian manifolds, there has been essentially no work in
trying to utilize projection-free tools here. An apparent issue is that
non-trivial affine functions are generally non-convex in such domains. In this
paper, we present methods for obtaining sub-linear regret guarantees in online
geodesically convex optimization on curved spaces for two scenarios: when we
have access to (a) a separation oracle or (b) a linear optimization oracle. For
geodesically convex losses, and when a separation oracle is available, our
algorithms achieve $O(T^{1/2}\:)$ and $O(T^{3/4}\;)$ adaptive regret guarantees
in the full information setting and the bandit setting, respectively. When a
linear optimization oracle is available, we obtain regret rates of
$O(T^{3/4}\;)$ for geodesically convex losses and $O(T^{2/3}\; log T )$ for
strongly geodesically convex losses

本文介绍了在曲面上进行在线几何凸优化时如何通过投影自由算法，在有分离预言机或线性优化预言机的情况下实现亚线性后悔保证。