# Riemannian Projection-free Online Learning

arXiv: https://arxiv.org/abs/2305.19349 · HTML: https://mlsanity.com/paper/2305.19349/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 30 May 2023.

## Builds on (most cited first, 23 of 23)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Riemannian Adaptive Optimization Methods](https://mlsanity.com/paper/1810.00760/) (2018)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization](https://mlsanity.com/paper/1910.10782/) (2019)
- [From Nesterov's Estimate Sequence to Riemannian Acceleration](https://mlsanity.com/paper/2001.08876/) (2020)
- [Riemannian Optimization via Frank-Wolfe Methods](https://mlsanity.com/paper/1710.10770/) (2017)
- [Revisiting Projection-free Online Learning: the Strongly Convex Case](https://mlsanity.com/paper/2010.07572/) (2020)
- [Projection-free Online Learning over Strongly Convex Sets](https://mlsanity.com/paper/2010.08177/) (2020)
- [Efficient and Near-Optimal Online Portfolio Selection](https://mlsanity.com/paper/2209.13932/) (2022)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles](https://mlsanity.com/paper/2111.13263/) (2021)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Improved Dynamic Regret for Online Frank-Wolfe](https://mlsanity.com/paper/2302.05620/) (2023)
- [Minimizing Dynamic Regret on Geodesic Metric Spaces](https://mlsanity.com/paper/2302.08652/) (2023)
- [Competitive Online Optimization under Inventory Constraints](https://mlsanity.com/paper/1901.09161/) (2019)
- [A Riemannian Corollary of Helly's Theorem](https://mlsanity.com/paper/1804.10738/) (2018)
- [Online and Random-order Load Balancing Simultaneously](https://mlsanity.com/paper/1610.07639/) (2016)
- [Fenchel Duality and a Separation Theorem on Hadamard Manifolds](https://mlsanity.com/paper/2102.11155/) (2021)
- [Interior-point methods on manifolds: theory and applications](https://mlsanity.com/paper/2303.04771/) (2023)

## Built on by (most cited first, 4 of 4)

- [Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds](https://mlsanity.com/paper/2509.07779/) (2025)
- [Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives](https://mlsanity.com/paper/2509.11236/) (2025)
- [Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions](https://mlsanity.com/paper/2607.20316/) (2026)
- [Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds](https://mlsanity.com/paper/2609.13646/) (2026)

## Abstract (arXiv)

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(T1/2:) and O(T3/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(T3/4;) for geodesically convex losses and O(T2/3; log T ) for strongly geodesically convex losses.