Minimizing Dynamic Regret on Geodesic Metric Spaces

Zihao Hu, Guanghui Wang, Jacob D. Abernethy
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4336-4383, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-hu23a, title = {Minimizing Dynamic Regret on Geodesic Metric Spaces}, author = {Hu, Zihao and Wang, Guanghui and Abernethy, Jacob D.}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {4336--4383}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/hu23a/hu23a.pdf}, url = {https://proceedings.mlr.press/v195/hu23a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Minimizing Dynamic Regret on Geodesic Metric Spaces %A Zihao Hu %A Guanghui Wang %A Jacob D. Abernethy %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-hu23a %I PMLR %P 4336--4383 %U https://proceedings.mlr.press/v195/hu23a.html %V 195 %X 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.
APA
Hu, Z., Wang, G. & Abernethy, J.D.. (2023). Minimizing Dynamic Regret on Geodesic Metric Spaces. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:4336-4383 Available from https://proceedings.mlr.press/v195/hu23a.html.

Related Material