Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915607541186560 |
|---|---|
| author | Cai, Yang Jordan, Michael I. Lin, Tianyi Oikonomou, Argyris Vlatakis-Gkaragkounis, Emmanouil-Vasileios |
| author_facet | Cai, Yang Jordan, Michael I. Lin, Tianyi Oikonomou, Argyris Vlatakis-Gkaragkounis, Emmanouil-Vasileios |
| contents | Equilibrium computation on Riemannian manifolds provides a unifying framework for numerous problems in machine learning and data analytics. One of the simplest yet most fundamental methods is Riemannian gradient descent (RGD). While its Euclidean counterpart has been extensively studied, it remains unclear how the manifold curvature affects RGD in game-theoretic settings. This paper addresses this gap by establishing new convergence results for \textit{geodesic strongly monotone} games. Our key result shows that RGD attains last-iterate linear convergence in a \textit{geometry-agnostic} fashion, a key property for applications in machine learning. We extend this guarantee to stochastic and adaptive variants -- SRGD and FARGD -- and establish that: (i) the sample complexity of SRGD is geometry-agnostic and optimal with respect to noise; (ii) FARGD matches the convergence rate of its non-adaptive counterpart up to constant factors, while avoiding reliance on the condition number. Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings, underscoring the surprising power of RGD -- despite its simplicity -- in solving a wide spectrum of machine learning problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_16617 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation Cai, Yang Jordan, Michael I. Lin, Tianyi Oikonomou, Argyris Vlatakis-Gkaragkounis, Emmanouil-Vasileios Optimization and Control Computer Science and Game Theory Machine Learning Equilibrium computation on Riemannian manifolds provides a unifying framework for numerous problems in machine learning and data analytics. One of the simplest yet most fundamental methods is Riemannian gradient descent (RGD). While its Euclidean counterpart has been extensively studied, it remains unclear how the manifold curvature affects RGD in game-theoretic settings. This paper addresses this gap by establishing new convergence results for \textit{geodesic strongly monotone} games. Our key result shows that RGD attains last-iterate linear convergence in a \textit{geometry-agnostic} fashion, a key property for applications in machine learning. We extend this guarantee to stochastic and adaptive variants -- SRGD and FARGD -- and establish that: (i) the sample complexity of SRGD is geometry-agnostic and optimal with respect to noise; (ii) FARGD matches the convergence rate of its non-adaptive counterpart up to constant factors, while avoiding reliance on the condition number. Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings, underscoring the surprising power of RGD -- despite its simplicity -- in solving a wide spectrum of machine learning problems. |
| title | Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation |
| topic | Optimization and Control Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2306.16617 |