Decentralized Online Riemannian Optimization with Dynamic Environments
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916425394814976 |
|---|---|
| author | Chen, Hengchao Sun, Qiang |
| author_facet | Chen, Hengchao Sun, Qiang |
| contents | This paper develops the first decentralized online Riemannian optimization algorithm on Hadamard manifolds. Our algorithm, the decentralized projected Riemannian gradient descent, iteratively performs local updates using projected Riemannian gradient descent and a consensus step via weighted Frechet mean. Theoretically, we establish linear variance reduction for the consensus step. Building on this, we prove a dynamic regret bound of order ${\cal O}(\sqrt{T(1+P_T)}/\sqrt{(1-σ_2(W))})$, where $T$ is the time horizon, $P_T$ represents the path variation measuring nonstationarity, and $σ_2(W)$ measures the network connectivity. The weighted Frechet mean in our algorithm incurs a minimization problem, which can be computationally expensive. To further alleviate this cost, we propose a simplified consensus step with a closed-form, replacing the weighted Frechet mean. We then establish linear variance reduction for this alternative and prove that the decentralized algorithm, even with this simple consensus step, achieves the same dynamic regret bound. Finally, we validate our approach with experiments on nonstationary decentralized Frechet mean computation over hyperbolic spaces and the space of symmetric positive definite matrices, demonstrating the effectiveness of our methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05128 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Decentralized Online Riemannian Optimization with Dynamic Environments Chen, Hengchao Sun, Qiang Optimization and Control Differential Geometry This paper develops the first decentralized online Riemannian optimization algorithm on Hadamard manifolds. Our algorithm, the decentralized projected Riemannian gradient descent, iteratively performs local updates using projected Riemannian gradient descent and a consensus step via weighted Frechet mean. Theoretically, we establish linear variance reduction for the consensus step. Building on this, we prove a dynamic regret bound of order ${\cal O}(\sqrt{T(1+P_T)}/\sqrt{(1-σ_2(W))})$, where $T$ is the time horizon, $P_T$ represents the path variation measuring nonstationarity, and $σ_2(W)$ measures the network connectivity. The weighted Frechet mean in our algorithm incurs a minimization problem, which can be computationally expensive. To further alleviate this cost, we propose a simplified consensus step with a closed-form, replacing the weighted Frechet mean. We then establish linear variance reduction for this alternative and prove that the decentralized algorithm, even with this simple consensus step, achieves the same dynamic regret bound. Finally, we validate our approach with experiments on nonstationary decentralized Frechet mean computation over hyperbolic spaces and the space of symmetric positive definite matrices, demonstrating the effectiveness of our methods. |
| title | Decentralized Online Riemannian Optimization with Dynamic Environments |
| topic | Optimization and Control Differential Geometry |
| url | https://arxiv.org/abs/2410.05128 |