Riemannian Online Optimistic Algorithms With Dynamic Regret

In this paper, we consider Riemannian online convex optimization with dynamic regret, which involves minimizing the cumulative loss difference between a learner's decisions and a sequence of adaptive decisions across dynamic environments over time on Riemannian manifolds. First, we propose Riemannian Online Optimistic Gradient Descent (R-OOGD), which extends the classical optimistic algorithms to Riemannian manifolds, requiring one gradient inquiry per round. We then propose Riemannian Adaptive Online Optimistic Gradient Descent (R-AOOGD) by incorporating the meta-expert framework into R-OOGD. We analyze the dynamic regret of R-OOGD and R-AOOGD in terms of the regularity of the sequence of cost functions and comparators. The dynamic regret bound matches the results in Euclidean space and with a scale adjustment of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(\frac{1+\kappa D^{2}}{\sqrt{1-KD^{2}}})$</tex-math></inline-formula> related to the sectional curvature lower bound <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\kappa$</tex-math></inline-formula>, sectional curvature upper bound <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> and feasible set diameter <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$D$</tex-math></inline-formula>. Finally, we provide numerical experiments to illustrate the performance of the proposed algorithms.