Minimizing Dynamic Regret on Geodesic Metric Spaces
This work addresses a gap in online optimization for geodesic metric spaces, offering new algorithms for sequential decision-making in non-Euclidean domains.
The paper tackles the problem of minimizing dynamic regret in online learning on Riemannian manifolds, achieving optimistic regret bounds for manifolds with non-positive curvature and proposing adaptive no-regret algorithms.
In this paper, we consider the sequential decision problem where the goal is to minimize the general dynamic regret on a complete Riemannian manifold. The task of offline optimization on such a domain, also known as a geodesic metric space, has recently received significant attention. The online setting has received significantly less attention, and it has remained an open question whether the body of results that hold in the Euclidean setting can be transplanted into the land of Riemannian manifolds where new challenges (e.g., curvature) come into play. In this paper, we show how to get optimistic regret bound on manifolds with non-positive curvature whenever improper learning is allowed and propose an array of adaptive no-regret algorithms. To the best of our knowledge, this is the first work that considers general dynamic regret and develops "optimistic" online learning algorithms which can be employed on geodesic metric spaces.