Riemannian Diffusion Adaptation for Distributed Optimization on Manifolds
Authors: Xiuheng Wang
Ricardo Augusto Borsoi
Cédric Richard
Ali H. Sayed
Venue: ICML 2025 poster (2025)
Keywords: Riemannian optimization
decentralized optimization
intrinsic method
diffusion adaptation
stochastic gradient descent
network agreement
non-asymptotic convergence
principle component analysis
Gaussian mixture model
Primary area: optimization->large_scale_parallel_and_distributed

Abstract: Online distributed optimization is particularly useful for solving optimization problems with streaming data collected by multiple agents over a network. When the solutions lie on a Riemannian manifold, such problems become challenging to solve, particularly when efficiency and continuous adaptation are required. This work tackles these challenges and devises a diffusion adaptation strategy for decentralized optimization over general manifolds. A theoretical analysis shows that the proposed algorithm is able to approach network agreement after sufficient iterations, which allows a non-asymptotic convergence result to be derived. We apply the algorithm to the online decentralized principal component analysis problem and Gaussian mixture model inference. Experimental results with both synthetic and real data illustrate its performance.

Riemannian Diffusion Adaptation for Distributed Optimization on Manifolds
Xiuheng Wang' Ricardo Borsoi'
Cédric Richard Ali H. Sayed
Abstract
of applications in machine learning. signal processing, and control can be written in the form of (1), including principal component analysis (PCA) (Cunningham & Ghahramani, 2015; Zhang et al., 2016), parameter estimation for Gaus- sian mixture models (GMM) (Hosseini & Sra, 2015; Collas et al., 2023), low-rank matrix completion (Boumal & Absil, 2011; Vandereycken, 2013), and deep neural networks with orthogonal constraints (Vorontsov et al., 2017).
Online distributed optimization is particularly use- ful for solving optimization problems with stream- ing data collected by multiple agents over a net- work. When the solutions lie on a Riemannian manifold, such problems become challenging to solve, particularly when efficiency and continuous adaptation required. This work tackles these challenges and devises diffusion adaptation strat- egy for decentralized optimization over general manifolds. A theoretical analysis shows that the proposed algorithm is able to approach network agreement after sufficient iterations, which allows non-asymptotic convergence result be derived. We apply the algorithm the online decentral- ized principal component analysis problem and Gaussian mixture model inference. Experimental results with both synthetic and real data illustrate its performance.
Decentralized optimization in Euclidean spaces has been extensively studied. As such, one may consider convert- ing the constraint w E .M into a cost function in the Eu- clidean space and solve (1) in a composite setting. Then, a distributed proximal gradient-type algorithm can be ap- plied if the projection onto the manifold available. How- ever, previous studies, e.g., (Bianchi & Jakubowiez, 2012; Di Lorenzo & Scutari, 2016; Zeng & Yin, 2018), require convex regularizer or at least the convexity of its domain. In addition, for certain manifolds, the dimension of an em- bedded Euclidean space can be relatively high according to the Whitney Embedding Theorem (Lee, 2013). Due to the non-convexity and non-linearity of certain M, these decen- tralized algorithms may fail when dealing with problem (I),
1. Introduction
In the decentralized setting, this work deals with the multi- agent optimization problem seeking consensus on a Rieman- nian manifold M:
In response to these challenges, this paper aims to intro- duce general framework to solve (1) by developing fully decentralized optimization on manifolds, which directly op- erates on M by exploiting its inherent geometry. Our main contributions are as follows:
K (w),,
min WEM K
(1)
1. Riemannian diffusion adaptation: We devise a Rie- mannian diffusion adaptation strategy, which is fully intrinsic and thus can be applied to general manifolds' It comprises a sequence of efficient adaptation and combination steps. the adaptation step, a Rieman- nian stochastic gradient descent (R-SGD) method is used to estimate the local solution at each agent. In the combination step, the local estimates of the neighbor- ing agents are combined on the tangent space of the manifold.
where J4 : : + IR is local risk function defined for each agent by J& (w) = Es, { (Qw:; } in terms of the expec- tation of some loss function Qu ax)). The computation of (w) is over the unknown distribution of the data 2t. which makes it necessary to use stochastic approximation for the gradient vector based on a set of independent realiza- tions tt, observed sequentially over time. A wide range
Part of this work was done while Xiuheng Wang was a PhD student at Université Côte d' AzAu.. Uniiersiiéé de Lorraine, CNRS, CRAN, France UUniversité Côte d' Azur, CNRS, OCA, France "École Polytechnique Fédérale de Lausanne, Switzerland. Corre- spondence to: Xiuheng Wang <drxiuheng wang @ gomi..com>
2. Theoretical analysis: ysis for the performance of the proposed Riemannian diffusion adaptation strategy with a constant step size.
We provide a theoretical anal-
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'This strategy not designed for specific manifold as it does not require an embedding A into Euclidean space.

---

Riemannian Diffusion Adaptation
We establish that all agents will approximately con- Verge network agreement (Theorem 5.12) in the sense of a decreasing geodesic distance between their estimates over the iterations. Additionally, we estab- lish a curvature-dependentt and non-asymptotic con- vergence result with a proper design of a Lyapunov function (Theorem 5.1.).
stochastic Riemannian Frank-Wolfe methods were intro- duced in (Weher & Sra, 2022). More recently, the behavior of various stochastic optimization algorithms around saddle points in geodesically non-convex functions was studied in (Hsieh et al., 2024). In (Wang et al., 2024a), the non- asymptotic convergence of R-SGD with constant step sizes was studied and applied to the change point detection on manifolds.
3. Application to various manifolds: We tailor our algo- rithm to suit two instances of Riemannian manifolds, i... the Grassmann manifold and a product manifold involving the manifold of symmetric positive definite (SPD) matrices. We apply our algorithm to the online distributed PCA and parameter estimation of GMMs through numerical experiments on synthetic and real- world datasets. Experimental results show its perfor- mance compared to non con-cooper,,ive, consensus, and centralized solutions.
Decentralized optimization on manifolds: The literature on decentralized optimization on Riemannian manifolds can be roughly divided into extrinsic and intrinsic methods.
The extrinsic methods are based on induced arithmetic mean (Sarlette& & Sepulchre, 2009), and rely on the specific embedding of the manifolds in Euclidean spaces (where traditional Euclidean consensus can be employed), which is often studied for specific manifolds. For stochastic op- timization, the incremental and consensus strategies have been extended to decentralized R-SGD-type on the unit sphere (Wang et al., 2023) and Stiefel manifolds (Chen et al., 2021), respectively. For the deterministic case, an augmented Lagrangian method (Wang & Liu, 2022) and type of conjugate gradient method (Chen et al., 2024) were also designed for decentralized optimization on the Stiefel manifold. In addition, a consensus strategy has also been extended to compact submanifolds (Deng & Hu, 2023).
2. Related work
In this section, we review related works on decentralized optimization in Euclidean spaces and the recent advances in (decentralized) optimization on Riemannian manifolds.
Decentralized optimization in Euclidean spaces: Dis- tributed optimization in Euclidean spaces has been exten- sively studied, including incremental (Blatt et al., 2007), consensus (Nedic et al., 2010) and diffusion (Chen & Sayed, 2012; Sayed et al., 2013) strategies. In particular, diffusion strategies have been demonstrated in (Sayed, 2014; Chen & Sayed, 2015) to offer improved performance and stability guarantees under constant step-size learning and adaptive scenarios. Recently, decentralized optimization has been extensively studied in non-convex environments (Bianchi & Jakubowicz, 2012; Di Lorenzo & Scutari, 2016; Lian al., 2017; Tatarenko & Touri, 2017; Zeng & Yin, 2018; Wang et al., 2019; Vlaski & Sayed, 2021).
The intrinsic methods are based on Fréchet mean (Tron et al., 2012) (or center of mass) and developed with the inherent geometry of manifolds, such as geodesic distance, Rieman- nian gradient, and exponential mapping. These methods can be studied on more general manifolds including, but not limited to, the unit sphere, Stiefel manifolds, Grassmann manifolds, and the manifold of SPD matrices. Different dis- tributed strategies (Tron et al., 2012; Kraisler et al., 2023a;b) were studied to achieve network agreement on manifolds. Another distributed strategy (Shah, 2017) was considered to solve (1) with a diminishing step size and two rounds of communication in each iteration. However, few meth- ods have investigated the diffusion strategy on manifolds, though it has been proven to have superior properties in Euclidean spaces, especially continuous learning and adaptive scenarios. A work extending the diffusion strategy to manifolds was introduced in (Wang et al., 2024b), but the algorithm is inefficient due to inner-loop optimization and does not have any theoretical analyses.
Riemannian optimization has gameered significant interest it considers the geometry of manifolds, recently presented in detail in the books (Ab- sil et al.. 2009) and (Boumal, 2023). Of particular interest are stochastic optimization methods due to their efficiency and scalability. The first asymptotic convergence analysis of R-SGD was provided in (Bonnabel, 2013), highlighting diverse applications such as PCA. The first global conver- gence results for first-order Riemannian optimization with geodesic convexity were obtained in (Zhang& & Sra, 2016). The finite-sum, stochastic setting has been further investi- gated in (Zhang et al., 2016; Sato et al., 2019) for variance reduction. The work (Tripuraneni et al., 2018) constructed and analyzed a variant of R-SGD that generalizes the clas- sical Ruppert averrina scheme. Several
Optimization on manifolds:
Recently, another branch of distributed optimization on man- ifolds considering a central server was also investigated, with settings of communication efficiency (Huang & Pan, 2020) and federated learning (Li & Ma, 2023; Huang et al., 2024a;b).
We further support this claim with numerical evaluation in Appendix D.
2

---

Riemannian Diffusion Adaptation
3. Background
Algorithm 1 Riemannian Diffusion Adaptation
Input: Step sizes Ja, at graph adjacency matrix C. Initialize {wr.o} J for all ls with a random point on M. for / = 2, do
This section introduces some basic concepts of Riemannian geometry, focusing on the essential tools for optimization on manifolds. Detailed presentations can be found in (Absil et al., 2009) and (Boumal, 2023).
for each agent A: do
Φx,t exPu ( H
A Riemannian manifold (M.g) is a constrained set M en- dowed with Riemannian metric (-(---) -): Mx x T + R. defined for every point x E .,, with T the so-called tangent space of M at x. geodesic 7v [0, 1] + M is the curve of minimal length linking two points x. y E M such that x = (0) and y = (1), with v T.M the velocity of You 0 denoted by (0). The geodesic dis- tance d(., :) : M x M - RR is defined as the length of the geodesic linking two points x, y E M. It satisfies all the conditions to be a metric.
wk. exP (ax Di=1 ON exp
K
(dE,))) Pbtt
end for end for
the risk J(w) and subsequently descend along the penalty P(w). Using node-level quantities have
Øxt =eXPmn Popi c-1
pV V.J.(ww.--))
(3)
Wk.t = expo. ( (- a VV.(()))))
(4)
The exponential map w = expx (v) is defined as the point w E .M located on the unique geodesic (t) with endpoints = (0), w = (1) and velocity v = (0). Consider smooth function f MM- + R. The Riemannian gradient of f ttxx E .M is defined as the unique tangent vector V (x) E T..M satisfying & #1 (lv)) = (V (x), o)2,, for all u E T.M. The Riemannian Hessian of f at is an operator [exp, (tv))) =
where and a are step sizes, VJ& is stochastic approxi- mation of the Riemannian gradient of Jk. and Ps can be computed in an explicit form (Afsari et al., 2013), given by
k
1 (
VPL(OK,))
cek Vdl
V2 f such that d (VexVV
t=1
2(V f (z). ()).
K
= Σ E=1
Cek exp exp $2, (de.)
(5)
4. Algorithm development
The Riemannian diffusion adaptation strategy, summarized in Algorithm 1, contains two steps: an adaptation step (3) where agent h uses its own data 2k,t-1 to update its solu- tion Φx.t and a combination step (4) where the intermediate estimates { } are combined, on the tangent space of Φ according to the weighting coefficients {cus in (5) to ob- tain the estimate Wk.t. Note that in the special case that M is a Fuclidean space, can take expx (v) as vector addition of + v, and our algorithm reduces to the diffusion adaptation algorithm in the Euclidean space (Chen & Sayed, 2012; Sayed et al., 2013). Here we emphasize that the local update of each agent in (3) is performed by stochastic Rie- mannian optimization with constant step size, which plays an important role in tasks in need of continuous learning and adaptation (Sayed et al., 2013; Sayed, 2014).
Let us define the product manifold KK A X x M, which is the K-fold Cartesian product of M with itself. We also define w & fol ... wx} } to indicate point on M The decentralized optimization problem (1) contains an implicit consensus: the individual models are required to be common the manifolds, i.e., wA = w, Vk. One can encourage consensus on manifolds by penalizing pairwise differences between connected agents. Let us represent the K agents as the nodes of a graph G. With a natural gener- alization of the Euclidean case, we consider the geodesic distance-based consensus problem (Tron et al., 2012), i.e., minimization of the penalty P(w) A Ek Pa((w)) where E cead we) and Cεk. _ [C]e,. with C' a weighted adjacency matrix of the graph G. representing the strength of link between each pair of agents. For a con- nected graph, P(w)= = 0 if and only if {w are equal for all k. This results in the following optimization problem with constraint:
P&
) A (wx))
5. Theoretical analysis
In this section, we analyze the convergence of Algorithm 1 in the constant step size setting.
min J(w) WEMM
s.f.
P(w)= 0,
(2)
In analyzing the dynamics of the distributed algorithm (3) and (4), it is useful introduce the following stacked vector notation by collecting variables from across the network:
where J(w) EK J.( To minimize the global cost function in (2), we follow the diffusion adaptation strat- egy in Euclidean spaces (Sayed et al., 2014; Yuan et al., 2018; Vlaski et al., 2023), and appeal to an incremental gradient descent argument. We first apply an R-SGD to
we - col( ... wx,) E EMK
VJ (1n.) e col ( ([((k)))))))))))) E MW
3

---

Riemannian Diffusion Adaptation
& = colf .Ket E EM
Assumption 5.2 (Regularization on graph). (Chen & Sayed, 2012; Sayed et al., 2013; Afsari et al., 2013) Assume that the undirected ς is connected and its adjacency matrix C is left-stochastic, i.e., Cck 2 0, E Cek = 1 for each agent k; denote lower and upper bounds on the eigenvalues of the Hessian of P in B as hmiin and hman. and suppose that Imiin 2 O.
K
VP(6,) _ =col - Σ
en expo, (de.))....
t=1
Σ
CEK expox. (dww) MK
where col(.) is obtained by stacking the arguments colum- nwise and T MaM K is the tangent space of .M* at æ, see Proposition 3.20 in (Boumal, 2023). We can then write (3) and (4) compactly as
Note this assumption implics that P is geodesically (strong) convex and smooth on B. Under Assumption 5.2, the global minimum exists and is unique if all { are contained in B, i... P: B A is well-defined (Tron et al.. 2012).
Φ. = -xPw.-1 (- (w--))) W, = expo, ( (VVV)())))
(6)
Recall the following trigonometric distance bound essential in the Riemannian optimization analysis.
(7)
Lemma 5.3. (Bonnabel, 2013; Zhang & Sra, 2016) If a, b, e are the side lengths of a geodesic triangle in Riemannian manifold with sectional curvature lower bounded by Runin- and A is the angle between sides and e (defined through the inverse exponential map and inner product in tangent space), then
Step (7) can be regarded one-step Riemannian gradient descent with step size to approximate global mini- mum of P(ő). belonging to the consensus submanifold A, defined as
A ( Φ. 3, vi.j..
(8)
Mimmin le
a² S
12 + c² - 2bc (A).
(9)
We start by introducing some technical assumptions and existing auxiliary results before presenting new results.
tanh( [Kmiule) (c)
We define the following key geometric constant that captures the impact of manifold curvature:
5.1. Assumptions and auxiliary results
Let us denote the convexity submanifold (Tron et al., 2012) of product manifolds M as B S .MK. We introduce the following standard assumptions in the literature on Rieman- nian optimization:
/IRmin|
if Kimin < 0,
tanb(y / /imin D)
(10)
1.
if Kmin 2 0,
Assumption 5.1 (Regularization on manifold). (Bonnabel, 2013; Zhang et al., 2016; Tripuraneni et al., 2018; Afsari, 2011) (a) The sequences (0)) and (w2 gener- ated by the algorithm stay continuously in B, and J at- tains its optimum w" in B; (b) the sectional curvature in B is upper bounded by Kmaxi (c) the sectional curva- ture in B is lower bounded by Kmini and (d) B is com- pact, and the diameter of B is bounded by D. that is, yex d(x, y) S D; (c) D < D", where D* is de- fined as D & min(inj(MM,, ( with iM) is the injectivity radius of M, which implies that the exponential map is invertible within B.
Note that most (if not all) practical manifold optimization problems can satisfy these assumptions.
Leveraging Assumption 5.1 and Lemma 5.3, we can readily establish the following corollary.
Corollary 5.4. (Zhang & Sra, 2016) For any Riemannian manifold M where the sectional curvature is lower bounded by Kmiin and for any points x, E M, the update 2(+1 = exp2, 22 (-+V (xx))
satisfies the inequalit::
(- (-VF())), cxp (x)) S (d(2)) d (0)4112))
2p
|VF(2))2
(11)
Also, it is necessary to assume some properties of the weighted adjacency matrix C' according to which the agents interact over the graph topology G. In addiction to the di- rect assumptions on G (c.g., left-stochastic) in Euclidean space (Chen& & Sayed, 2012: Sayed et al., 2013), for dis- tributed optimization on manifolds, we also make the fol- lowing assumptions on the cigenvalues of the Riemannian Hessian of P. whose computation involves C, see Subsec- tion 2.1.3 in (Afsari et al., 2013) and Proposition 8 in (Tron et al., 2012) for examples.
This corollary unveils significant relationship between two consecutive updates within an iterative optimization algo- rithm on a manifold with curvature bounded from below.
Part of our analysis will be performed under the following assumption of geodesically convex risk functions.
Assumption 5.5 (Geodesical convexity). A function J4 M -> IR is geodesically convex (g-convex) if for any x. E
4

---

Riemannian Diffusion Adaptation
M. a geodesic 7 such that 7(0) x and 7(1) yy, and [0, 1], have:
Proof. Appendix A.I.
Under Assumption 5.5, we can establish the following prop- erty for the risk function J.
Ja(T(a)) <L- aV)(
(12)
or equivalently, we have
Lemma 5.9. Under Assumption 5.5, define w col( (. (mm with wm being the Fréchet mean (burycenter) of w1...., W.. we have
J&(U) 2 (x) + exp,
(13)
J(w) S J(w).
(20)
Meanwhile, we require the risk function Jj at each agent to be geodesically smooth.
Proof. Appendix A.2.
Assumption 5.6 (Geodesic smoothness). A differentiable function JR is geodesically T-smooth (I-g-smooth) if its
This proof follows similarly to Proposition 10 in (Yokota, 2016) and Theorem 1.1 in (Paris, 2020).
gradient is L-Lipschitz, i.e., for any x, y E M, satisfies:
The following lemma builds on assumptions 5.1 and 5.6, and establishes an upper bound on [[:)(l
July) +
(v)) + expx (v)
(14)
Lemma 5.10. Under assumptions 5.1 and 5.6, we have:
where the gradient of function Js : M - R is said to be
T--Lipschitz if, for any y E .M in the domain of Jk. it satisfies:
VJJ(w:]l S G
(21)
for non-negative constant G < oc.
( < exp (v)ll,
(15)
where D denotes the parallel transport operator from y to x.
Proof. Appendix A.3.
In addition, make assumptions about the average and second moment of the gradient noise process.
This upper bound is similar to the one used in (Shah, 2017; Deng & Hu, 2023) under diminishing step size.
Assumption 5.7 (Gradient noise process). Denote F, the filtration generated by the random process Wk,s for all k and for < t, that is,
5.3. Network agreement
To begin with, we first show that the Riemannian diffu- sion adaptation algorithm approximately converges toward network agreement. In other words, w, converges to the consensus submanifold A with high probability. The fol- lowing lemma builds on Lemma 5. under the additional conditions set forth in assumption 5.7 and 5.2.
F. (Wo, Wi," ,",
(16)
where w, col(w,,,, wx,) contains the iterates across the network at time s. Define (w:) A
VJ(,))) - (ww,) as the gradient noise process at the time instant f. is assumed that
Lemma 5.11. Under assumptions 5.1, 5.2, 5.6 and 5.7, suppose a E (0, hmaal. The sequence (P(),) satisfies the following relation:
E(S ( = 0, 1 M1 < 2
(17)
(18)
2
E
- P(O.))
- VP(
G2
for non-negative constant aT.
a
2
(22)
With these assumptions, we can build some preliminary lemmas that will be used in the proof of our main results.
Proof. Appendix A.4.
5.2. Preliminary lemmas
This lemma reveals the evolution of the difference E E(P(Or+1) P(Φ,)) in the optimization process. The first term on the right-hand side of (22) is strictly negative and suggests a decrease in the expectation of penalty by a magnitude proportional to E P()))( However, the second and third terms on the right-hand side of (22) could be large enough allow the objective value increase. In
We first establish Jemma that bounds the gradient of the penalty function P in terms of the penalty itself.
Lemma 5.8. Under Assumption 5.2, for the gradient of the penalty, it holds that
[VP())]| 2P)(D))
(19)
5

---

Riemannian Diffusion Adaptation
the following, with an additional assumption that the cost J is geodesically convex (Assumption 5.5), we prove that the expectation of penalty decreases strictly and can be upper bounded with small value after sufficient iterations.
Lemma 5.14. Under assumptions 5.1, 5.2, 5.6 and 5.7, suppose ja E (0, 4. The sequence (J(ws) satisfies the following relation:
M E [B]JJ(W()))
[ [E((w(+11) -(w:)))))(ww))>>>>
Theorem 5.12. Under assumptions 5.1, 5.2, 5.5, 5.6, and 5.7, suppose a E (0, hmazl. The sequence (P(6 satisfies the following relation:
4
5a
V (28)
E
E(P(O.)) S 11,2
G² G²+ 3p²
0².
(23)
Proof. Appendix A.5.
2aT
at
after sufficient iterations s.- given by
This lemma shows the evolution of the term (JJ(w [w:)] } in the optimization process. The strictly negative term on the right-hand side of (28) suggests a decrease in the expectation of the risk function by magnitude pro- portional to E| (w.)) while the positive one could be large enough to allow the objective value to increase.
2 llg((u) So log(1 7) + =
(24)
where r = min
22: ahmin), (1) denotes a constant term,
and 1) denotes term that is equal or higher in order than μ the last equality holds for sufficiently small
In the following, we consider (and study the convergence of) a streaming average of iterates {wa,+1,'" we), given by (w ... ur/} with w'sot1 = u Wsotl, w'st1
Proof. Appendix B.I.
The result in Theorem 1212 establishes that after sufficient iterations &, = 0(r we have:
exPw:, (5- exp (Wa+1) for so + S 8 S t 2,
and
((P()))) 0(13)
(25)
2( 2 + 1
w/ exP
exp w
(w:)
(29)
or, from Markov's inequality:
Pr(P(())) 2 n] S 0()),
(26)
This provides a natural way of averaging along a trajectory restricted a manifold (Tripuraneni et al., 2018). For ex- ample, when M is a Euclidean space, we can write exp, (v) as + v, and the streaming average reduces to w' +1
which means the local estimates in &, coalesce around o E A (where P(),)= = 0) with high probability. These results are consistent with Theorem 1 in (Vlaski & Sayed, 2021) where the Euclidean diffusion adaptation algorithm analyzed for non-convex environments.
Wa,+1, w = w', + s-,.+1 (w', w.+1) for so + 1 S s S t Inspired by (Zhang & Sra, 2016), we design Lyapunov function of w; as
25 and w/ = w/-1 + 2(+1- 1---5--1 (wi_1 - wt).
Combined with Lemma 5.8, Theorem 5.12 leads the following corollary.
Corollary 5.13. With the assumptions in Theorem 12. The sequence (IV satisfies the following relation:
A A J(w() - J(w"),
(30)
with auxiliary variables wo defined in (29) and wt denoted as the optimal solution to (2). Under an additional assump- tion of geodesic convexity (Assumption 5.5), we can estab- lish the following result that EA, decreases strictly and can be bounded above.
(P()))) 11p2
6²²
G²
0²
(27)
at
at
after sufficient iterations s, = (4
Hence, according VP())) 0 and the update in (7), we conclude that w, approximately approaches Φb and achieves network agreement, or equivalently w. A with high probability after sufficient iterations.
Theorem 5.15. Under assumptions 5.1, 5.2, 5.5, 5.6 and 5.7, suppose E (0, hindel and E (0, T. The sequence satisfies the following relation:
CLD2 + (1-88)
231Cam G2 2r
63Cap o²
5.4. Non-asymptotic convergence
EA <
26 +
-1
Next, examine the convergence of Algorithm 1 after sufficient iterations 8.. For this purpose, we make use of the upper bound on P given in Corollary 5.13. Before this, we introduce the following lemma that builds on the same assumptions as in Lemma 5.11 and can be regarded as a symmetric result of the relation (22).
(31)
Proof. Appendix B.2.
Theorem 5.15 establishes that non-asymptotic convergence of Algorithm can be guaranteed after sufficient iterations
6

---

Riemannian Diffusion Adaptation
for sufficiently small step sizes je and a, if J is geodesically convex and smooth.
manifolds to be applied (Alimisis & Vandereycken, 2024). The Riemannian stochastic gradient of the loss function in (32) on Si is computed using the Euclidean gradient of (32) at Uk,t and (90) given in Appendix C.I, leading to:
Compared to the Euclidean counterpart (Chen & Sayed, 2012; Sayed et al., 2013; Vlaski & Sayed, 2021), key dif- ferences in our analysis include the impact of manifold curvature k (captured in the parameter () and the non-linear nature of the combination step (4). This makes traditional techniques like adjacency matrix decomposition unfeasible, since the network centroid cannot be computed using simple linear expressions. We address these challenges through novel framework that studies network agreement via the evolution of the penalty term P( and establish non- asymptotic convergence results using the carefully designed Lyapunov function in (30).
h h(UR,,, 2x...) 2(I - U U. h.s ) UKC.
The retraction used is defined in (91). In order to evaluate the accuracy of the solutions, we consider the geodesic distance (89) between the estimates at each time instant t k,t) and the optimal solution x x(U", ) and we define the mean square deviation (MSD) accordingly as
1 MSD
ox (UR,t, ksd U*)
K
6. Examples and applications
In this section, we tailor Algorithm 1 to two common in- stances of Riemannian manifolds. The first one is the Grass- mann manifold, a set of k-dimensional linear subspaces of IR, denoted by Gh. The second is the manifold of p x p SPD matrices, denoted by S We consider applying our algorithms on Go and product manifold involving S to online distributed PCA and GMM inference, respectively. While the exponential map is convenient for theoretical analysis, the retractions often lead to more practical and efficient computations. Thus, for computational simplicity, we replace the exponential maps in the updates (3) and (4) with approximate retractions as in (Bonnabel, 2013). We provide definitions of the geodesic distance, Riemannian gradient, and retraction of GK and + in Appendix C. The computational complexity of our algorithm is discussed in Appendix E.
6.2. Distributed GMM inference
Another challenging application of our algorithm is dis- tributed parameter estimation for GMMs with 2 E R" being data samples observed by each agent k. The decen- tralized inference of mixtures of M Gaussians with coef- ficients p 2 {pI.-... ,Prr), whose probability density is p(x=) - ΣN Ps P.r(a: m,; Σ,) with PN a multivariate
Gaussian with mean m, and covariance Σ, > 0, can be reformulated in (Hosseini & Sra, 2015):
M
e
min (8.) (1)
Exg
log
2 UN (.))
e
i==
(33)
where yu = [ar n) 1],n;=logg = Pi for i = 1, M M-11 and PM JM O. which makes the problem unconstrained (Jordan & Jacobs, 1994), and
= V2Tee (N 0, S,). The problem (33) reformulated on the product manifold M. S x R has the same optimum as that of the original loglliiel of p(x)) (Hosseini & Sra, 2015), i.e.,
6.1. Distributed PCA
We consider applying our algorithm GR to the online distributed PCA problem with 24 E R" being data samples observed by each agent k. In the decentralized setting, we consider the following problem:
S 5 Σ + mim? TT m
m
min - Em, (Tr(U[ (EUR)
(32)
The log-likelihood has been shown to be geodesically con- vex for the case of a single Gaussian (Hosseini & Sra, 2015), but not necessarily for multiple Gaussians. From this ex- ample, we can find the proposed algorithm itself can work even in some situations when not all these assumptions are satisfied. The Riemannian gradient of the loss func- tion in (33) on the product manifold is composed of the (Riemannian) gradients w.r.t. {..).M on II,"1 S and (m (T:)a. AM in M Specifically, the Riemannian gradient w.r.t. S. was computed via the Euclidean gradient of (33) at S.k. and (93) given in Appendix C.2. The retraction used is defined in (94). In this task, it is not very meaningful to compute the MSD values according to (92), because GMM
where π (Ux) represents the local estimate at agent k. The expectation in the loss function (32) is approximated by realizations WR. at each time instant t. Note that although various works formulate PCA on the Stiefel manifold (Chen al., 2021; Wang& & Liu, 2022: Wang et al., 2023), the loss function in (32) is invariant to orthonormal transformations. Thus, we formulate the problem on the Grassmannian man- ifold since it makes the solution unique (Cunningham & Ghahramani, 2015). This formulation has also been found to have a similar mathematical structure of strong geodesic convexity, allowing arguments from convex optimization on
7

---

Riemannian Diffusion Adaptation
Remanniin non-cooperative
DRSGD
Riemannian diffusionn
Riemannian centralized
NSD (dB)
-5
-10
-15
-20
200
400
600
1000
1200
1400
Figure 1. Graph topology.
Iteratioo
Figure 2. Illustration of MSD performance of the algorithms for distributed PCA on synthetic data.
not inherently identifiable, which means that the parame- ters of the model may not be uniquely determined. Thus, to evaluate the performance of the solutions, we consider the average log- log-likelihood (ALL)) as in (Hosseini & Sra, 2015; Collas et al., 2023).
10
Rieannnian non-cooperative
DRSGD
Riemannian diffusion
Remannian centralized
MSD (dB)
7. Numerical experiments
In this section, we present numerical experiments on distributed PCA and parameter estimation of GMMs, which are formulated on manifolds as explained in Sec- tion 6. Our method is implemented in Python with the Pymanopt toolbox (Townsend et al., 2016). Open- source code to reproduce the results is publicly avail- able on https: / //ttt/ggtttt/t//e// com/ xi whang- di f fffuuiionnn fffuiionnmani fold_rioooldeeedeeee ogy of the multi-agent system used for the experiments is illustrated in Figure 1. The weights in matrix C' were ran- domly generated by the Metropolis rule (Xiao et al., 2006) with K = 20 agents². For simulation on synthetic data, the MSD results are averaged over 100 times independent Monte Carlo experiments. Hereafter, we briefly describe the baselines.
-15
500
1000
1500
2000
2500
3000
3500
Iteratio
Figure 3. Illustration of MSD performance of the algorithms for distributed PCA on real data.
The graph topol-
7.1. Experiments on PCA
We first present results on PCA formulated on Go with both synthetic and real data.
Synthetic data:
We generate synthetic data as in (Chen
et al., 2021). First, set n. 10, p 5, and indepen- dently sample 1500K data points according to multivari- ate Gaussian model to obtain a matrix S E g=x1500k Let S = UAVT be its truncated SVD. We modify the distribution of A as A' = diag(X') with À = 0.8 and 0, 72 1 to reset S S' UA.V. We randomly shuffle and split the columns of S' E g=x1500K into 1500 subsets obtain X, for all time instants t = 1,.... 1500.
Baselines: We compare our algorithm against the Rieman- nian non-cooperative and centralized strategies for both PCA and GMM inference. The non-cooperative algo- rithm independently applies R-SGD on each agent using its local data TR,t, while the centralized works on data X, = { collected from all agents. We also pro- vide comparisons with an extrinsic consensus algorithm on the Stiefel manifold: Decentralized Riemannian Stochastic Gradient Descent (DRSGD) (Chen et al., 2021) for PCA. For GMM inference, to the best of our knowledge there are no approaches that are both online and decentralized. Thus, for comparison, we extend the decentralized consen- sus SGD (Nedic et al., 2010; Lian et al., 2017) to the product manifold presented in Section 6.2 using a projection oper- ator to ensure the constraints are satisfied. This Extrinsic Consensus strategy for GMM inference is named ECGMM.
The simulations used fixed step sizes μ = 0.05 and a = 0.8. For our algorithm, the step sizes control the tradeoff be- tween convergence speed and steady-state performance; this is illustrated with experimental results in Appendix D.3.
Real data: We also obtain numerical results on the MNIST dataset (LeCun, 1998). The dataset contains 70000 hrndtwritten images with n 784 pixels. The data ma- trix is normalized such that the elements are in the range [0, 1] and then centered. To compute MSD, we perform PCA on the full data matrix and regard its result as the opti- mum. We randomly shuffle the images, partition them into K = 20 subsets, and then run the algorithms to compute the first p = 5 principal components with the fixed step sizes p = 0.002 and a 0.005.
TTo illustrate the applicability to more networks, we include additional experimental results in Appendix D.2.
8

---

Riemannian Diffusion Adaptation
Riemannian ron-onoperalive
10.0
Riemannian ron-cooperative
ECGMM
ECGMM
Riemannian difussio
7.5
Riemannian diffusion
Riemannian centralized
Riemannian centralized
ALL" ALL (08)
ALL (08)
5.0
-5-
2.5
-10
-15
2.5
20
-5.0
400
800
1000
1200
1400
500
1000
1500
2500
3000
3500
Iteration
Iteration
Figure 4. Illustration of ALL differences of the algorithms for dis- tributed GMM inference on synthetic data.
Figure 5. Illustratioon of ALL differences of the algorithms for dis- tributed GMM inference on real data.
Discussion: Figure 2 shows the MSD learning curves for the compared algorithms on synthetic data. It can be seen that the Riemannian diffusion adaptation strategy achieves a significant improvement in MSD performance compared to the non-cooperative case, which indicates the benefit of information exchange. Moreover, our method also outper- forms DRSGD. The centralized solution achieves the lowest MSD, as it can access information over the whole graph. The proposed algorithm is fully decentralized, where each agent uses only locally observed data to update its local estimate and exchange information only among neighbor- ing agents. Although the proposed algorithm has lower performance compared the centralized method, it can be computed in parallel on multiple agents. The MSD of the different methods on real data, shown in Figure 3, be- haves similarly to that in the experiment with synthetic data, showing the same comparative performances between the different approaches.
data points are randomly shuffled and split into 1500 subsets to obtain X, for all time instants ....., 1500. The simulations used fixed step sizes 0.04 and a = 0.05.
Real data: Again, we perform the same data processing for the MNIST dataset (LeCun, 1998) as in Section 7.1. Then, we apply PCA to reduce the dimensionality = 20. We compute the Expectation Maximization (EM) solution on the full dataset and regard its result as an optimum. To evaluate the performance, we compare the difference be- tween the ALL values of the optimum and estimated solu- tions, denoted as ALL. ALL. We implement the com- pared algorithms to infer mixtures of Gaussian models with M and fixed step sizes l = 0.08 and a 0.08.
Figure 4 and Figure 5 illustrate the ALL dif- ference values for the compared methods on synthetic and real data, respectively. The results demonstrate that our method outperforms both the non-cooperative algorithm and ECGMM, further highlighting its effectiveness. As expected, the centralized case achieves the lowest ALL dif- ference.
Discussion:
7.2. Experiments on GMM inference
Now we show results on a more challenging task: GMM inference formulated on IMM + x M with synthetic and real data. As in (Hosseini & Sra, 2015), we initialize the mixture parameters for all the methods using k-means++.
8. Conclusions
In this paper, the Riemannian diffusion adaptation algorithm is proposed. The strategy consists of two efficient steps: an adaptation step, where R-SGD is used at each agent to up- date the estimate of the local solution on the manifold, and a combination step, where the estimates of neighboring agents are combined on the tangent space. A theoretical analysis is provided under constant step size, showing that network agreement achieved with high probability and the algo- rithm converges non-asymptotically to a neighborhood of the optimal solution. The proposed method is applied to line decentralized PCA and GMM inference. Experimental results on both synthetic and real-world data illustrate the efficacy of the proposed strategy. One main limitation of this work is that the theoretical results rely on the use of the exponential map, which can be computationally heavy. This is discussed in more detail in Appendix F.
Synthetic data: To generate synthetic data, we choose the parameters m, Σ and p of the Gaussian mixture similarly to (Collas et al., 2023). First, Σ is generated using its eigen- decomposition Σ- UAUT. U is drawn from the uniform distribution on the orthogonal group, and all the elements of A are drawn from a chi-squared distribution with a degree of freedom 3. Second, the elements of p are drawn from a Gamma distribution with a shape parameter 10, and then normalized. Third, m is sampled from multivariate Gaus- sian distribution (0, 3T), where sampling is repeated until the following inequality is satisfied (Hosseini & Sra, 2015):
j. Im m,Il || 2 max(1r (e))( IEE,)
We set n = and M- = 3 and independently sample 1500K data points according to the Gaussian mixture above. These

---

Riemannian Diffusion Adaptation
Impact Statement
Boumal, N. and Absil, P.-a. Rtrme: A Riemannian trust- region method for low-rank matrix completion. Advances in Neural Information Processing Systems, 24, 2011.
This paper presents work that aims to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Chen, J. and Sayed, A. H. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 60(8):4289- 4305, 2012.
Acknowledgements
Chen, J. and Sayed, A. H. On the learning behavior of adap- tive networks part I: Transient analysis. IEEE Transac- tions on Information Theory, (6)34873333 2015.
The authors would like to thank the reviewers for their con- structive feedback. The work of Cédric Richard was sup- ported in part by the French Government through the 31A Côte d' Azur Investments in the Future Project under grant ANR-19- 111--1----002222 and in part by grant ANR- 19-CE48- 0002. The work of Ricardo Borsoi was supported in part by the French National Research Agency, under grants ANR- 23-CE23-0024, ANR-23-CE94-0001, and by the National Science Foundation, under grant NSF 2316420. Xiuheng Wang would like to thank Dr. Mengfei Zhang for the benefi- cal diseussion in the early exploratory stage of this work.
Chen, J., Ye, H., Wang, M., Huang, T., Dai, G., Tsang, I., and Liu, Y. Decentralized Riemannian conjugate gra- dient method on the stiefel manifold. In The Twelfth International Conference on Learning Representations, 2024.
Chen, S., Garcia, A., Hong, M., and Shahrampour, De- centralized Riemannian gradient descent on the Stiefel manifold. In International Conference Machine Learn- ing, pp. 1594-1605, PMLR, 2021.
References
Collas, A., Breloy, A., Ren, C.,, Ginolhac, G., and Ovarlez, J.-P. Riemannian optimization for non-centered mixture of scaled gaussian distributions. IEEE Transactions on Signal Processing, 2023.
Absil, P.-A., Mahony, R., and Sepulchre, R. Optimization Algorithmss Matrix Manifolds. Princeton University Press, 2009.
Afsari, B. Riemannian E center of mass: existence, unique- ness, and convexity. Proceedings of the American Mathe- matical Society, 139(2):655-673, 2011.
Cunningham, J. P. and Ghahramani, Z. Linear dimensional- ity reduction: Survey, insights, and generalizations. The Journal of Machine Learning Research, 16(1):2859-2900, 2015.
Afsari, B., Tron, R., and Vidal, R. On the convergence of gradient descent for finding the Riemannian center of mass. SIAM Journal on Control and Optimization, 51(3): 2230-2260, 2013.
Deng. K. and Hu, J. Decentralized projected Riemannian gradient method for smooth optimization on compact submanifolds. arXiv:2304.00 082411, 2023.
Di Lorenzo, P. and Scutari, G. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Informa- tion Processing over Networks, 2(2): 2016.
Alimisis, F. and Vandereycken, B. Geodesic convexity of the symmetric eigenvalue problem and convergence of steepest descent. Journal of Optimization Theory and Applications, pp- 1 1-40, 2024.
Edelman, A., Arias, T. A., and Smith, S. T. The geometry of algorithms with orthogonality constraints. SIAM jour- nal on Matrix Analysis and Applications, 20(2):303-353, 1998.
Bianchi, P. and Jakubowicz, J. Convergence of multi-agent projected stochastic gradient algorithm for non-convex optimization. IEEE Transactions on Automatic Control, 58(2):391-40S, 2012.
Hosseini, R. and Sra, S. Matrix manifold optimization for gaussian mixtures. Advances in Neural Information Processing Systems, 28, 2015.
Blatt, D., Hero, A. O., and Gauchman, H. A convergent incremental gradient method with constant step size. SIAM Journal on Optimization, 18(1):29-51) 2007.
Hsieh, Y.P.., Karimi Jaghargh, M. R., Krause, A., and Mer- tikopoulos, P. Riemannian stochastic optimization meth- ods avoid strict saddle points. Advances in Neural Infor- mation Processing Systems, 36, 2024.
Bonnabel, S. Stochastic gradient descent on Riemannian manifolds. IEEE Transactions on Automatic Control, 58 (9):2217-2229, 2013.
Huang, L.-K. and Pan, S. Communication tributed PCA by Riemannian optimization. In Interna- tional Conference on Machine Learning, pp. 4474. PMLR, 2020.
dis-
Boumal, N. An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, 2023.
10

---

Riemannian Diffusion Adaptation
Huang, Z., Huang, W., Jawanpuria, P., and Mishra, B. Feder- ated learning Riemannian manifolds with differential privacy, arXiv preprint arXiv:2404. 10.4404.0000 10029, 2024a.
Sayed, A. H. Adaptive networks. Proceedings the IEEE,
102(4):460 2014.
Sayed, A. H., Tu, S.-Y., Chen, J., Zhao, X., and Towfic, Z. J. Diffusion strategies for adaptation and learning over networks: an examination of distributed strategies and network behavior. IEEE Signal Processing Magazine, 30 (3):155-171, 2013.
Huang, Z., Huang, W., Jawanpuria,, P., and Mishra, B. Rie- mannian federated learning via averaging gradient stream. arXiv preprint arXiv:2409.07225 2024b.
Jordan, M. and Jacobs, R. A. Hierarchical mixtures of experts and the EM algorithm. Neurul Computation, (2):181-214, 1994.
Sayed, A. H. al. Adaptation, learning, and optimization over networks. Foundations and Trends@) in Machine Learning, 7(4-5):11-801,, 2014.
Kraisler, S., Talebi, S., and Mesbahi. M. Consensus on lie groups for the Riemannian center of mass. In 2023 62nd IEEE Conference Decision and Control (CDC), pp. 4461-4466. IEEE, 2023a.
Shah, S. M. Distributed optimization on Riemannian mani- folds for multi- networks. arXiv: 2017.
Tatarenko, T. and Touri, B. Non-convex distributed opti- mization. IEEE Transactions on Automatic Control, 62 (8):7744 2017.
Kraisler, S., Talebi, S., and Mesbahi, M. Distributed consen- sus on manifolds using the Riemannian center of mass. In 2023 IEEE Conference on Control Techologg and Applications (CCTA), pp. 130-135. IEEE, 2023b.
Townsend, J., Koep, N., and Weichwald, S. Pymanopt: A python toolbox for optimization manifolds using automatic differentiation. Journal of Machine Learning Research, 17(137):1-5, 2016.
LeCun, Y. The MNIST database of handwritten digits. htlp://yann, lecun, com/exdb/mnist// 1998.
Lee, J. M. Introduction to Smooth Manifoods. Springer, 2nd edition, 2013.
Tripuraneni, N., Flammarion, N., Bach, F,, and Jordan, M. I. Averaging stochastic gradient descent on Riemannian manifolds. In Conference on Learning Theory, pp. 650- 687. PMLR, 2018.
Li, J. and Ma, S. Federated learning on Riemannian mani- folds. Applied Set-Valued Analysis and Optimization, 5 (2), 2023.
Tron, R., Afsari, B., and Vidal, R. Riemannian consensus for manifolds with bounded curvature. IEEE Transactions on Automatic Control, 58()):921 -934, 2012.
Lian, X., Zhang, C., Zhang, H., Hsich, C.-J,, Zhang, W., and Liu, J. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Vandereycken, B. Low-rank matrix completion by Rieman- nian optimization. SIAM Journal on Oplimization, 23(2): 1214-1236, 2013.
Nedic, A., Ozdaglar, A., and Parrilo, P. A. Constrained con-
Vlaski, and Sayed, A. Distributed learning non- convex environments Part I: Agreement a linear rate, IEEE Transactions Signal Processing, 69:1242- 1256. 2021.
sensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4):922-936, 2010.
Paris, Q. Jensen's inequality in geodesic spaces with lower bounded curvature, arXiv:2011.0859/ 2020.
Vlaski, S., Kar, S., Sayed, A. H., and Moura, J. M. Net- worked signal and information processing: Learning by multiagent systems. IEEE Signal Processing Magazine, 40(5):92-105,, 2023.
Pennec, X., Fillard, P., and Ayache, N. A Riemannian framework for tensor computing. International Journal of Computer Vision, 66(1):41-66 2006.
Vorontsov, E., Trabelsi, C., Kadoury, S., and Pal, C. On orthogonality and learning recurrent networks with long term dependencies. In International Conference on Ma- chine Learning, pp. 3570-3578. PMLR, 2017.
Sarlette, A. and Sepulchre, R. Consensus optimization manifolds. SIAM journal Control and Optimization, 48(1):56-76. 2009.
Sato, H., Kasai, H., and Mishra, B. Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport. SIAM Journal on Optimization, 29(2): 1444-1472, 2019.
Wang. L. and Liu, X. Decentralized optimization over the Stiefel manifold by an approximate augmented La- grangian function. IEEE Transactions on Signal Process- ing, 70:3029-3044 2022.

---

Riemannian Diffusion Adaptation
Wang, X., Jiao, Y., Wai, H.-T., and Gu, Y. Incremental aggre- gated Riemannian gradient method for distributed PCA. In International Conference Artificial Intelligence and Statistics, pp. 7492-7510. PMLR, 2023.
Wang, X., Borsoi, R. A., and Richard, C. Non-parametric online change point detection Riemannian manifolds. In International Conference Machine Learning, pp. 50143-50162. PMLR, 2024a.
Wang, X., Borsoi, R. A., and Richard, C. Riemannian dif- fusion adaptation over graphs with application to online distributed PCA. In IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 9736-9740, 2024b.
Wang, Y. Yin, W., and Zeng, Global convergence of ADMM in nonconvex nonsmooth optimization. Journal of Scientific Computing, 78:29 63, 2019.
Weber, M. and Sra, S. Projection-free free nonconvex stochastic optimization Riemannian manifolds. IMA Journal of Numerical Analysis, 32(4):3241-3271) 2022.
Xiao, L., Boyd, S., and Lall, S. A space-time diffusion scheme for peer-to-peer squares estimation. In Pro- ceedings of the 5th International Conference on Informa- fion Processing in Sensor Networks, pp. 168-176, 2006.
Yokota, T.
Convex functions and barycenter on cat (1)- spaces of small radii Journal of the Mathematical Society of Japan, 68(3):1277-1323, 2016.
Yuan, K., Ying. B., Zhao, X., and Sayed, A. H. Exact diffusion for distributed optimization and learning part Algorithm development. IEEE Transactions on Signal Processing, 67(3):708-723, 2018.
Zeng, J. and Yin, W. On nonconvex decentralized gradient descent. JEEE Transactions on Signal Processing, (11):2834-2848, 2018.
Zhang, H. and Sra, S. First-order methods for geodesically convex optimization. In Conference on Learning Theory, pp. 1617-1638, 2016.
Zhang, H., Reddi, S. J., and Sra, S. Riemannian SVRG: Fast stochastic optimization on Riemannian manifolds. In Advances in Neural Information Processing Systems, pp. 4592-4600, 2016
12

---

Riemannian Diffusion Adaptation
A. Proofs of the lemmas
A.1. Lemma 5.8
From the definition P().), we have
K
K
K
IVP(
Σ
Σ
cik expo or (0r.)
ctt
|xp (or+)
2P((.)
(34)
k=l
where the inequality follows from Jensen's 's inequality and the fact that C' is left-stochastic, as stated Assumption 5.2.
A.2. Lemma 5.9
Due to the g-convexity of Js under Assumption 5.5, we have
Ju (ww) - (wwx) S (W))(um) exp mm (wx))
(35)
Multiply the above by K and sum over ki we get
1 Σ (wm) 1 Eeww))) S Σ ((-)) (wx))
(36)
K
Using Ex Je(ww)) = J(w) and rearranging the terms, this can be rewritten as
j(
Σ Je(WE)) S (- (w))) K
K Σ exp (wx))
(37)
Note that K Es exp (wx) R V V (w =m=w is the gradient of the cost function & Es (( evaluated the Fréchet mean Wm. which is its minimizer, therefore, the first order optimality condition implies K Σn exp wm (wx) = O. Combining this with the previous results leads to (ww) S Σx Je(wk) = J(w).
A.3. Lemma 5.10
Since B is compact (Assumption 5.1), from the geodesic smoothness of J3 (Assumption 5.6), we have:
J (w;))l = G,
(38)
for a non-negative constant < 0o. Observe that (38) implies similar condition on the deviation from the centralized
gradient via Jensen's inequality:
[]J(())]] =
K Σ V.l(ww))
$ K &
Σ
(39)
A.4. Lemma 5.11
Let us start with the update u, = exp&, (-o ((P))) from (7), define 7 (a) A geodesic from o, w,, and use the second-order Taylor expansion of a P(n(a)) around a under assumptions 5.1 and 5.2, then have (Tron et al. 2012)
exp&, (~aVP(())) as the minimal
P(w.) < (VP())) + Aman (V) - - -
2
(40)
where è a alimaz 0 since
(0, h 1 Also, we use the first-order Taylor expansion of a + (P()(())
around a = 0 to obtain the following bound:
[[V M. 4,
P S h Amma A o
(41)
13

---

Riemannian Diffusion Adaptation
Similarly, for the update 01+1 expw, (- (~,VJ(w,) from (6), define 72(u1) 2 expw. (- (V as the minimal geodesic from w, Φi+1: use the second-order Taylor expansion of μ - P(12(11)) around and 5.2, then we have
0, under assumptions 5.1
P(0++1) & P(w:) + -u hmaz E (w,)ll
(42)
2
Take the expectation on (42) w.r.t. (a.)=-o and consider (17) and (18) in Assumption 5.7, we have
Aman El
(w:)l2
[P(0.+1) & [P((w, - +
2
1maal1
EE((w. (B(
EE|
VJ
-EP(w.) (1)) -1BP)))))16(((77)))))77777111111 + hmoo 22²
E VJ].),,'''
< (E((w:) + 5 E V..w,) )12
+ 2 J
m
E (J..) +.(wo,)))+(((
2
f E V (w.)
(1
<P((w) +
+
+ hmma
E VEW,)l + he
2
2
EP(ww) + E (P(
+
+
hmmr
p / + hmaatH
(43)
2
where we use the facts (a, b) s aa² respectively. Next, we take the expectation on (40) w.r.t. {xx)<=o- and combine the result with (43) to obtain
+
1 b2 for & > 0 and {a + b)2 < a² + 12 the second and third inequalities,
25
EP(O:4)) S EP())) - -B ( BBI))())))
+ 1maa
1 (( + kmaatt o² (44)
2
Now need upper bound B|| P(w;) Consider
E (P 21 (P)))))))))))))))))))))))))))) -
2
6.
< <E - -
112 mam 1)
(45)
where the first inequality uses the fact } (a + 6)2 < a² + b² the second inequality uses (41). Plugging the upper bound of PEW,))( as provided in (45), into (44) and reordering, we have
E(a21> + I) + ( + +lmax B + hmazel"
EP(0.41) < -
- <EI
25
(22122
= =EP(O,, 2 {EI(P((0))1++++
+ +hmax
| V.J(w:)) 1|2 1iaaz112""
a h2 +1
EP(Ø)) - (
hmax 1²6² + hmmz 200
(46)
where in the equality we select & = 2(n211 mar +1) for simplicity, and in the second inequality we use (21) from Lemma 5.10. Since (0, hm we have hmoo I and ş. and thus we can further simplify (46)
EP(().1) S <P(() - =
5p
G
4 0a
(47)
Re-arranging the terms in (47) gives the desired result.
14

---

Riemannian Diffusion Adaptation
A.5. Lemma 5.14
Consider the smoothness property of J in Assumption 5.6 with expw: - (w;)
from (6), we can write:
L L U||exp,.) (0t+1)ll
I( S J(w) + (xx)
2
L WV w )|?
= J(w) + (VJ(w:), -V
(48)
2
Also, we can obtain the following bound:
[V 0 V.w;) - Lp [p,))(
(49)
Take expectation on (48) w.t.. { [z. ) and consider (17) in Assumption 5.7, we have:
LE J (wx))l?
EJ((+++) S (.((w) + ((())(())) -+
Lp²²
EJ(ww) + E[ -A
+ 2
B| B(,))(
EJ(ww) - (w:)))
(50)
> 0 since E (0, L- Again, consider the smoothness property of in Assumption 5.6 with where e - 1 (1 m4 2
exp0441 0141
(W++1)= = -a CVV (V from (7), we obtain:
L L exp -1 044
(W++1)ll2
1(1+11) s J(0 + (VJ( exp (wx+1)) +
L -VV((
=((0411) + (V -aVi( -OVP(0+1)) +
2
S I(0+1) + [J( 111=+
+ a² @
(51)
25
where the second inequality uses the fact (a, b) < Sa² + D.. Next, we take the expectation on (51) w.r.t {a.))_ and combine the result with (50) to obtain
( + a²E V'
(x( & (w;,) <EE| (.,))l +
(52)
2
Now we need to upper bound B||
VJ Consider
[
= - [
1 ((w;)) + 0 V](w)))1
2
2
$ E VJ
D ([(w, 22 V J(w,))
$ 112112 1) (
(53)
where the first inequality uses the fact +a a² + b², the second inequality uses (49) and the fact ( E| (w:))l Plugging the upper bound of [ JJ ( 2| as provided in (53), into (52) and reordering, we have
|2 <
BJ(w))1 < EJ(w.) - (e E(₁2 1.2 + 1)) E [iJ +
25 + L
a E V
= =EJ(w:: $ E (.:(w:))1 + 11,1,2 +1 + I a a²
VP
(54)
2
where in the equality we select ç = 2(1 for simplicity. Since μ E (0, L - we have L S p: and 2 5. and thus we can further simplify (54) as
- E VJ (wx)) 5a
EJ EJ(w++) & E.(ww)
\P(
(55)
4
1
Re-arranging the terms in (55) gives the desired result.
15

---

Riemannian Diffusion Adaptation
B. Proofs of the theorems
B.1. Theorem 5.12
Define 6 = colf@m. & mm,) with &m,t being the Fréchet mean of Φ i.c. &m,t _ arg Σ & 6). Further, define (3) & expø, ex Φ,) as the minimal geodesic from Φ, to o.. use the second-order Taylor expansion of 3 (8) around B then we have (Afsari al., 2013):
(VP())) exp,, (o.) + hminn expx. (6:)1 exp,,
2 S P(Ø,) -(()))
(56)
Considering P().) O, we can further write
Amin expx,
xx,)((0))1 (1,))1
P( = P().) P(),) s (-VP())), exp:
2
almmi 8 x.))
d(wi Φ1) + Ça
P()))))
20
2a
2
admmnn (Ø, Ø.)
1
d (uww. wi) + Ça
(57)
2a
2a
2
where the second inequality is from Corollary 5.4, for the update wi expo, (- aVP()))) from (7) and the third inequality uses the fact (wr, w.) Σ (W worr) I Ex= df (WkKer Pm,,) df dww,, Φ,) where
w colf " [mm,.} with wm,t being the Fréchet mean of wt.
From Corollary 5.4, for the update Φ = =xpw (- (-MVJ(w:)) (6), we have
1 dww,, w.)
1 ( w. + SH (.(w111
[J(w), (w,)) I
(58)
24
2p
2
Take the expectation the previous result w.r.t. 1a=o and consider (17) in Assumption 5.7, obtain
E (xx) (w,))) = ((<E(VVJ(,,)) cxp. (w.))
E (- (EV(())(w,)) expm. (w:))}
(59)
Combining (58) and (59), we can write
(x.)) B((-VJ(w)) exp) (w:)) S Edd (w,, w.)
1
Edd (0++1) w.) ( ((w,)
(60)
2μ
2μ
2
Consider J to be geodesically convex function under Assumption 5.5. Using (13), taking its expectation w.r.t (x,)._0 and combining the result with (60), we further write
B(J(w:) ((w))} E((-VJ(w)) exp exp. (w.))
1
Edd w.
1
Ed (o411, w[)+ CHr E (
(61)
2μ
24
2
Using (w;) S J (w:) in Lemma 5.9, from (61), have
- -Ed (wi, w.)
-Ed ( C2
< -Ed
- (ww)))l
S 14tro//nnkkkknnn11//2///01111110 (w.))
-Ed (0 -24
(62)
where we use the fact {a + 6)2 < a² + 6² in the second equality, and (18) from Assumption 5,7 in the third inequality. Take expectation of (57) w.r.t. (x,) and combine the result with (62), we obtain
EP(Ø)) - 1 ahmin Edd Ed Φ.)
1 Edf Ee 2 + Sa B[VP(())) 2
2₁2
(63)
2a
2a
16

---

Riemannian Diffusion Adaptation
Multiplying (22) in Lemma 5.11 by 2Ç and summing the result to (63), and considering the upper bound of given in Lemma 5.10, we have
|| [V)
2(EP()+11) - (2)_1)))( S 1 - almmm Ed (d( Φ.)
1
11cx² G²+
3rr²
(o 01+1)
0²
(64)
2a
2a
a
a
Multiplying (64) by (1 - we have:
1 )2CEP(0) S (1 (1-7) almmn
(1- -
Ed (0 Φ1)
2ç
2a
-(1 -(1-7 - --)--= Edd ( 1
2x
+ (1 7) 11cH²
G² (1 -1 (1- 3616 0²
(65)
a
Now we sum (65) from t = 0 - s s-1 we can get simpler upper bound in the latter case. Consider the case = 0, which is simple. From (64) we have:
1. To simplify the summation, we consider the case = 0 and t 2 separately as
2(EP().) - (2ς - 1))P((o) < 1 - almmm Ed (do Ø0)
1 (o, Φ2) + 116 G2 + 301² 0².
(66)
2a
20
For the case 2 1, inspired by (Zhang & Sra, 2016), let T min -ेे almin), this implies S 2
and S almin
Consider S h hmaz hmmin we have E (0, For t 1, from (65) we can obtain:
(1 (1-7) (1-7))2((P(().))) -1 & (1 (1-7) (t-1) (1)-)-((-1)
Edd (1- Edd (01+1,
2x
2a
+ (1 - -) 11c
G² + (1 (1 o².
(67)
Finally, summing (65) over t from & = 0 to t 1, and using the previous results, we have:
1 ahnmin Edd
(1 -1-r) (1-7))(0"22(P((( -22 - -
1) v
(0) - -01 -1-7)
-(1-7)-(--1
(2,, 5.)
2a
2a
1
11G - G² +
Σ
7)
7)
1=0
D2
11 G²
3C
Σ
(1
7)
(1-
0²
(68)
2a
a
1=0
t=
where the second inequality drops the negative terms and plugs in d( g0) S D (Assumption 5.1). Define (3) A expo, exexp
d. (1))) the minimal geodesic from Φo Φ0 Using the second-order Taylor expansion of 3 + (()) around B = 1. considering P(),) = 0, vP(Ø.) = O, we have (Afsari et al., 2013):
p( S P(o + (VP())). exp (ō.)) + Amaz || expx (0)0(( (2)))12
2
hmaz & (c) Φ0).
(69)
2
This ensures P( < hanx 2 <
D2 2a
since d( Φ0) S D and a E (0, hmlsl. one can thus obtain from (68) that
2
(1 - D2
11
3p
EP( <
7)
6²
Σ
(1
7)
o²
2
2a
2
1=0
t=0
(1 - (1-1) D2
11
3p2 20
<
Σ
6
+
Σ
(1
7)
0²
20
2a
t=0
t=0
17

---

Riemannian Diffusion Adaptation
(1
12-
1142
3p²
G +
o²
2a
20T
2at
1 2
34²
G²
0²,
(70)
2aT
at
where the last inequality holds whenever:
(1-r)(6-1)))
-
D2
3p²²
3/2²
0²
- (1 - --- = TD) o²
2a
207
- (s 1) log((1 7) - 2 + 011
2 210g(1) -
+ 0(1)
(71)
log(1 - -7)
We conclude that
11x²2 2xt
G² 3p²² d²
B[P(d.)) S
(72)
at
with sufficiently small step sizes μ after sufficient iterations 8,. where
2log(p) + 0(1) = 0(1
8o = log(1 - T)
(73)
where the second equality follows since li / log(p) 0, which means that the magnitude of log(и) can be bounded above by constant multiple of μ for μ +
B.2. Theorem 5.15
Denote A, I(we) (ww",, from Lemma 5.14, we have:
+ 5a
Ed++1 EA, I
"E (w:)))
Ell
(74)
4
μ
From Corollary 5.4, for the update Φ1+1 exPw,
(w:)) in (6), we have
1
1 d d0 w²) + CH (w,))1
(w.), "ww" S (we,, w²)
(75)
2/
24
2
Take the expectation on the previous result w.r.t. faxz and consider (17) in Assumption 5.7, we obtain
B B((-VJ((o:), exp=! = ((E-EVV((..))1:)) (xxp
(E((-VJ()) (Jw,), exp (w*)))
(76)
Combining (75) and (76), we have
1 Ed ( w") + S 1 [
B[( B((-VJ(w;), exp=, (w")) < 24
(w,, w²)
(77)
2/
Consider that J is a geodesically convex function under Assumption 5.5, from (77) one can obtain
EA.- = [[](w.))) - J(w")} s ( (W)(--V)(..).)))) exp,
1 Edd (w,, w²) 2μ
1 Edl (+14111))))
SH S (.:
+
(78)
2μ
2
Now we need to upper bound - (2 w*) From Corollary 5.4, for the update w++1 cxp (7), we have
(-QVP()...).
d d( & l(0 w²) S ( 2a ( (w²)
18

---

Riemannian Diffusion Adaptation
< 2a (a(P(W") P(d++1))
s <<a2IVP(@=.>))1
(79)
where the second inequality uses the convexity property P with (13), and the third inequality uses the fact P(w*)
and P( 2 0.
Take the expectation on the previous result w.r.t. {ar,)a=0- and combine the result with (78), we have
1
SH4 B V
Ça² E
E.. S 2μ
(wr, w²) Ed (wL1,,
(80)
24
2μ
Multiplying (74) by 2Ç and adding to (80), we have:
1
21(a²
2 (2C - 1)EA, < Edl Ber,, w²) -
Edf (wi+1, w²) + 2/
E
EIVP((
(81)
2/
2p
From Corollary 5.13, we know E|
(l converges to a small value after sufficient iterations s., now we tend study the convergence of our algorithm after so iterations. For 2 so where so defined in (24), from (27) one can rewrite (81) as
1 Ed (w,, w") Ed (ed[ww11.". w²) + 231Çau G² + 63çap o². 2p
2(EA++1 - -25 - 195-1)EA, &
(82)
2p
2r
Summing (82) from 8o tot and plugging in d(w,,; w*) s D, obtain
(231çau G² +
63çap 02
2CEA, +
Σ 8
EA 5 1 (2(-)1) 1)EA,, + (ww,, w²) Edd Bdl( w²) + (8 -8)
2/1
2/4
2T
1
221çaa G² +
63ςaạ 0²
$ (2 1)EA,, + d (w.,, w²)+ + so)
2/
2T
T
D
(231çau
63çap 0²)
$ (2( - 1)EA,,
+ so)
G2
+
(83)
24
2r
T
Recall the geodesic L-smoothness of J in Assumption 5.6 and plugging into d( (W,,, w*) D and VJ(w") have:
A.. = J(w,,) - J(w") 1 (VJ(w"), expm= (w..)) ) + exp (w,
dL (W.,, w²) 5 LD²
(84)
This ensures A., <
LD3 2
< 2μ
since μ S -11 so that from (83) one can obtain
63Çap (33 G2 02)
Σ t=8+1
EA. CLD2 (s so)
(85)
2T
Here the term As does not cancel nicely due the presence of the curvature term S, which necessities the use of Lyapunov function as in (Zhang & Sra, 2016). Introduce auxiliary variables w whe+1 Ws.+1 and w/t: = expw (--. exp (w.+1) for 8o + 1 < S 2, w'41 +1 expw 2c+s-8.-1 exp (w.)). repeatedly consider (12) in Assumption 5.5 (geodesic convexity of J), for 2 8. + 1, we have
20
J(W
<
8 - 8, -
J [w + 1
J(W--1)
80
3o / (s- So
Jww ))
J (W +
8 8, -
8 80 2
80
80
s-1
< .... <
Σ
J(w:).
(86)
1=
19

---

Riemannian Diffusion Adaptation
Denote A - J(w,)) [ww), we have EA S 8-5,-1 Ei=eot1 EA, in (12) of Assumption 5.5, and further write
Again, consider the geodesic convexity of J
EA = [(J(ww,) - J(w))}
8 - 80
J(('(-1) +
2(
J(w.) - J (w=)
25 + 8 8, -
2 + 8
2 + (8 - 80 - 1)
25+ + 8 80
2(EE, + -t= s. EA:
(87)
2Ç + 8 - 80
Plug the upper bound of 2(EA, +
Σi-1 Di=e,t1 EA, (83) into the above result, for 8 2 80 + 1, we have
EA, S 2 -1
CT.D2
8 80
G² + 7
63çaz 02)
(88)
25+ + 80 -1
2T
C. Examples of Riemannian manifolds
C.1. Grassmann manifold
The Grassmann manifold Gh a set of p-dimensional linear subspaces of R", can be regarded as a smooth quotient
manifold of the Stiefel manifold S = -U E R=*P, : - = Ip}. i.c. Gh = / = (T(U) U E S where
Op- = IU E RPXP: : U = } is the orthogonal group and π St + G is the map T(U) (UO 0 E Op}. The geodesic distance between two subspaces (U,) and (UU)) of gh. spanned by orthonormal matrices U₁ and U2, is defined as follows (Edelman et al., 1998):
U2) = || cos (0)122.
(89)
where 0 E IR contains the singular values of U. U2, namely, it related its singular value decomposition (SVD) as UHU, U2 V Via Define ʃ Sh + R. we have (T((U) - f(U) for all xUU Gh. The Riemannian gradient Vf at π (U) 9h is given by:
= = (G).
(90)
with P (G) UU"), where G R2xP is the Euclidean gradient of f at U. Let & E Ta and let XΣY = U be the thin SVD of U & Raxp, A numerically stable retraction RA(U) Ta + 9 on g is given by (Boumal, 2023):
(E) = (XY").
(91)
C.2. The manifold of SPD matrices
The geodesic distance of S between two SPD matrices Σ; and Eg E S can be computed in closed form (Pennec et al., 2006) as:
d Σ2) = | ΣS Σ₁ Σ })|l }||m>
(92)
where ||-|| denotes the Frobenius norm. The Riemannian gradient V at Σ E + is given by:
VS(E) = {Gym
(93)
with G E RPxP the Euclidean gradient of function f at Σ and sym (G) = 1 (T + G). In practice, the Euclidean gradient
can be easily computed using automatic differentiation tools. Let & E TESt+. A retraction Ry,st+ T + S is
defined
- R R (E) = Σ + + 3Σ E
(94)
This retraction is a sedond-order approximation of the exponential mapping.
20

---

Riemannian Diffusion Adaptation
D. Additional experimental results
D.I. Inefficieney of the method (Wang et al., 2024b)
In Section 2, we argue that the algorithm in (Wang et al., 2024b) is inefficient due to the inner-loop optimization when minimizing the penalty term P(é,). To support this claim, we compare the MSD performance and runtime between the work in (Wang et al., 2024b) (denoted "Inefficient Riemannian diffusion") and the proposed algorithm. We examine these two algorithms for distributed PCA on synthetic data in the same setting as in Subsection 7.1, and produce the results as in Figure 6. From these results, we can see that while the performance of these two algorithms is nearly identical, the proposed algorithm achieves significantly reduced runtime. These experiments were performed on a computer with an Apple M4 Pro processor and 24GB of RAM.
Inefficient Rlemannian diffusion (15.88s) Riemannian diffusion 10.60s)
(d8)
MSD
-10
-15
-20
200
400
600
8:0
1000
1200
1400
Iteration
Figure 6. Illustration of MSD performance and runtime per Monte Carlo run of the (inefficient) Riemannian diffusion adaptation algorithms for distributed PCA on synthetic data.
D.2. Applicability to more networks
To illustrate the applicability of the proposed algorithm to more networks, we randomly generate another graph topology as shown Figure 7 (left) and select weights with an uniform rule. We test all compared algorithms for both distributed PCA and GMM inference on synthetic data in the same setting in Section 7 and produce experimental results in Figure 7 (middle and right). From these results, find the performance of the compared algorithms remains similar to that shown in Figure 2 and Figure 4, which are obtained with the network illustrated in Figure 1.
5
Riemannian nan-cooperative
Riemannnnnn non-caoperaative
DRSGD
ECGMM
0
Riemannian diffusion
0-
Riemannian diffusion
Remmanian contralized
nnin contralized
ALL ALL (dB)
MS0 (68)
-5
-10
-10
-15
-15
-20
-20-
-25
400
800 1200
200
600
1000
1400
iteration
Iteration
Figure 7. Performance illustration of the compared methods on another network with uniformly distributed weights: graph topology (left); MSD performance for distributed PCA (middle); ALL differences for GMM inference (right) on synthetic data.
D.3. Impact of step sizes
For the proposed algorithm, the choice of step sizes is critical to control the tradeoff between convergence speed and steady-state performance. We examine the behavior of the proposed algorithm for distributed PCA on synthetic data in the same setting as in Subsection 7.1, and produce the results with different choices of step sizes as shown in Figure 8. It can be observed that larger step sizes tend to accelerate convergence but result in worse performance at steady state.
21

---

Riemannian Diffusion Adaptation
=
== 0.07
J.
NSO (40)
-5-
-20
1000
1200
1400
Iteration
Figure 8. Illustration of MSD performance of the proposed method with different step sizes for distributed PCA on synthetic data.
E. Computational complexity
The computational complexity of the proposed algorithm on each agent involves two contributing terms. The first is the cost of a local adaptation step (3) (i.e., Riemannian SGD on Jz), which denoted by TJ. The second is the cost of the combination step (4), which involves gradient step the loss function Pa that scales linearly with the number N neigh, of neighbors connected node in the graph (that is, with the number of nonzero elements in the coefficients C&c). which we represent as Nneigh,k: Tp, where T is the cost of computing the inverse of the exponential mapping. Neeighh, is also known as the degree of the vertex & in the graph G. Thus, for each agent k, we obtain complexity of T Nueigh. Tp. Compared to a non-cooperative setting, we have an overhead cost of Nueigh,. Ty, which is a function of both on Tp (which depends on the manifold) and on the number of neighbors connected to node k (which depends on the graph topology).
This allows us understand how the complexity scales with the number of agents K. In the case where the number of neighbors each node (i.e., their degree in the graph) is constant, the complexity does not increase with K. On the other hand, in the worst case scenario of fully connected graph (where each vertex has degree K 1, being connected to all other vertices), then the complexity scales linearly with K, with coefficient equal to Tp.
F. Discussion on the limitations
Our work has two main limitations, which are discussed in the following.
The theoretical analysis is based on the exponential mapping expx as in many works in Riemannian optimization, e.g., (Zhang & Sra, 2016), while in practice, a retraction Rg used for more efficient computations. A key result in (Bonnabel, 2013) states that (f= v), exp, (p v)) = 0(+²), meaning that for small 14, a retraction closely approximates the exponential map. The main approach to proving convergence with retractions involves showing that the iterates of the algorithm remain close those of an equivalent version using the exponential map, which holds as μ 0 (Bonnabel, 2013). This argument typically relies on diminishing step sizes, whereas our analysis is designed for constant step sizes, which are crucial for continuous adaptation and learning. Some works also employ the pullback operator fo Rg i.e., the composition of the cost function f and retraction Rt. to establish convergence. However, these approaches require assumptions that may be less natural, such as the convexity and smoothness of the pullback operator, see Chapter of (Boumal, 2023). Thus, we believe that extending the proposed thcoretical analysis based on retraction is an exciting, though non-trivial, research direction.
Manifolds without closed-form expressions for retractions, or for the Riemannian gradient, pose challenges to the implementation of the proposed algorithm, as such operations have to be approximated numerically in some way. However, we highlight that this limitation also applics to most existing Riemannian optimization algorithms and not specific to our work.
22


Reviews:
[{"review_id": "nkotgr3HTo", "reviewer": "Reviewer_qfKq", "summary": "This paper presents a novel Riemannian generalization of a diffusion adaptation strategy for distributed optimization. The distributed optimization aims at finding an optimal solution with consensus among different agents. The proposed algorithm utilizes the Riemannian exponential map on manifolds and obtains a non-symptotic convergence under appropriate assumptions. In particular, a network agreement among the agents is guaranteed after sufficient iterations, which minimizes the (locally) convex risk function. The experimental results demonstrate the convergence when the Riemannian exponential map is replaced with an appropriate retraction map.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our work (especially in checking the proofs) and offering constructive suggestions. In the following, we provide clarifications and answers to your comments and questions.\n\n### **Replies to Weakness:**\n\n***Support the claim that the method in (Wang et al., 2024b) is not efficient:***\n\nThank you for this insightful comment. To support this claim, we compare the performance and runtime between the work in (Wang et al., 2024b) (denoted as \"Inefficient Riemannian diffusion\") and the proposed algorithm in the same setting as in Section 7.1 of the manuscript. We examine these two algorithms and produce the results as in https://ibb.co/nsDtry65. From these results, we can claim that while the performance of these two algorithms is nearly identical, the proposed algorithm achieves a significantly reduced runtime. We will add this supporting experiment to the revised manuscript. \n\n***Discuss more Riemannian federated learning works:***\n\nThank you for mentioning related work on Riemannian federated learning, which is an important rising topic and a counterpart of our research goal. We will add the suggested references to the revised manuscript.\n\n### **Replies to Questions:**\n\n***Why is the exponential mapping replaced by a retraction in the experiment? Does the analysis still apply?***\n\nWe suggest replacing the exponential map with a retraction for computational reasons, as a retraction can be more efficient than the exponential map for certain manifolds (Boumal, 2023). While the exponential map is convenient for theoretical analysis, the retractions often lead to more practical and efficient computations. We will further clarify the motivation for this choice in the revised manuscript.\n\nOur theoretical analysis, like many works in Riemannian optimization, e.g., (Zhang & Sra, 2016), is based on the exponential map.\nA key result in (Bonnabel, 2013) states that $d(R_x(\\mu\\cdot v),\\exp_x(\\mu\\cdot v))=O(\\mu^2)$,  meaning that for small $\\mu$, a retraction closely approximates the exponential map. The main approach to proving convergence with retractions involves showing that the iterates of the algorithm remain close to those of an equivalent version using the exponential map, which holds as $\\mu \\to 0$ (Bonnabel, 2013). This argument typically relies on diminishing step sizes, whereas our analysis is designed for constant step sizes, which are crucial for continuous adaptation and learning. Some works also employ the _pullback_ operator $f\\circ R_x$, i.e., the composition of the cost function $f$ and a retraction, to establish convergence. However, these approaches requires assumptions that may be less natural, such as the convexity and smoothness of the pullback operator, see Chapter 4 of (Boumal, 2023). Thus, we believe that extending the proposed theoretical analysis based on a retraction is an exciting, though non-trivial research direction. We will discuss this limitation of the theoretical analysis in the revised manuscript.\n\n***Whether the retraction is employed in all algorithms?***\n\nAll the algorithms use the same retraction for a fair comparison.  The experimental results are reported in terms of _time_, representing the time index of receiving streaming data $\\boldsymbol{x}_t$, which can also be regarded as the iteration index of the algorithm in the stochastic algorithms. To avoid possible ambiguity, we will replace \"time\" with \"iteration\" and update all the related figures in the revised manuscript.\n\n***What is the performance in parallel computing?***\n\nThe proposed method, like most decentralized algorithms, can benefit from parallelization. Given the response to the last question, all reported performance results (replacing \"time\" with \"iteration\") can be regarded as computations performed across agents in a parallel computing setting.\n\nThis can also be seen when we analyze how the computational complexity scales with the number of agents $K$ in the network, keeping in mind that all operations (i.e., both the adaptation and combination steps) are fully parallelizable over the agents. For a detailed discussion on the computational complexity of the proposed algorithm, please refer to *[the response to Reviewer xKFw](https://openreview.net/forum?id=5tyvHfhRFZ&noteId=Lgg3fpLQRg)*.", "claims_and_evidence": "The claims made in this submission are accurately stated and supported by convincing evidence and discussions. Except for the following statement\n\n``A work extending the diffusion strategy to manifolds was introduced in (Wang et al., 2024b), but the algorithm is inefficient due to inner-loop optimization ...'',\nwhich is not supported by any experimental evidence.\n\n>> REVIEW UPDATE: Authors have responded to this concern and included supporting experimental result.", "methods_and_evaluation_criteria": "The proposed methods and the evaluation criteria make sense for the problems of interest in this paper.", "theoretical_claims": "Yes, I checked and confirmed the correctness of the proofs. In particular, the proofs of Lemma 5.11, Theorem 5.12 and Theorem 5.15 are carefully examined.", "experimental_designs_or_analyses": "I checked the experimental designs and analyses. I find them organized well overall but I have some concerns that are not clearly addressed in:\n\n``For computational simplicity, we replace the exponential maps in the updates (3) and (4) with approximate retractions.''\n\nIn addition to the concerns on the approximate retractions, I also believe that the potential of the proposed algorithm is not fully demonstrated in the analyses. While the Riemannian centralized method obtains the superior performances in terms of elapsed comput time, one of the most important advantages of decentralized optimization is the parallel computations over the agents. Accumulating the elapsed comput time blur the parallel computing advantages of the proposed algorithm.\n\nPlease refer to the ``Questions For Authors'' section that explain my concerns.\n\n>> REVIEW UPDATE: Authors have clarified the concerns and confusions addressed above.", "relation_to_broader_scientific_literature": "This paper proposes the first Riemannian diffusion adaptation strategy with guaranteed convergence for general manifolds. The proposed algorithm outperforms the existing Riemannian diffusion adaptation strategy [CGHS'21] specifically designed for PCA problem and generalized extrinsic consensus strategy from [NOP'10,LZZHZL'17] for GMM. This paper also claims bad performance of the Riemannian diffusion adaptation strategy introduced in [WBR'24b], but the claim is not supported by numerical evidence.", "essential_references_not_discussed": "This paper focuses on the diffusion adaptation strategy that utilizes the full gradient information and there is also a stochastic diffusion adaptation strategy proposed in \n\nNonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data by Jiaojiao Zhang, Jiang Hu , Anthony Man-Cho So, Mikael Johansso, published in  Proceedings of the AAAI Conference on Artificial Intelligence.\n\nIt is worth mentioning the recent developments in Riemannian federated learning as a counterpart of decentralized algorithms for distributed optimization on manifolds. In particular, there are recent arXiv preprints:\n\nRiemannian Federated Learning via Averaging Gradient Stream by Zhenwei Huang, Wen Huang, Pratik Jawanpuria, Bamdev Mishra.\n\nFederated Learning on Riemannian Manifolds with Differential Privacy by Zhenwei Huang, Wen Huang, Pratik Jawanpuria, Bamdev Mishra.", "other_strengths_and_weaknesses": "Overall, the algorithmic design and theoretical analysis of the novel Riemannian diffusion adaptation strategy proposed in this paper is significant. In particular, the guaranteed convergence result for the Riemannian diffusion adaptation strategy as well as the techniques used to prove it are essential for this rising topics of distributed optimization.", "other_comments_or_suggestions": "I do not have comments other than those that have been addressed in other sections.", "questions_for_authors": "The following questions/concerns stand out in my opinion.\n\n\n1. The algorithmic design and theoretical analysis of the Riemannian diffusion adaptation strategy proposed in this paper are entirely based on the Riemannian exponential mapping. Why is this mapping replaced by the approximate retraction mapping in the numerical experiment? Does the theoretical analysis still apply to the approximated version of the diffusion strategy?\n1. A much more important follow-on question: please be specific whether the approximate retraction mapping is employed in all algorithms that are being tested in the experiments. This is important because the experimental results are reported in terms of the elapsed compute time, which is significantly affected by the choice of update computation on manifolds.\n1. What are the performance of the proposed method and other decentralized algorithms if the computations over agents are considered in parallel computing?\n\n\nAs stated above, the algorithmic design and theoretical analysis of the novel Riemannian diffusion adaptation strategy proposed in this paper is significant and my opinions on this submission leaning towards accept. While it is a common practice to relax the Riemannian exponential mapping with retraction mapping, this submission did not address the implications of the approximate retraction mapping used in the numerical experiment properly, which hurts the soundness of the numerical experiments as raised in the first two questions. Since the convergence results are actually obtained for the ``weaker'' retraction mapping, this paper is certainly recommended for ICML in my opinion if the first two questions are clearly addressed. The third question is more of a favourable question that exploits more potentials in the proposed algorithm. It would not damage my evaluation of this paper if it is not responded.\n\n>> REVIEW UPDATE: Authors have clarified the concerns and confusions addressed above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JHDS7lvTTd", "reviewer": "Reviewer_bCcG", "summary": "The paper studies online distributed optimization on manifolds, and proposes Riemannian diffusion adaptation in which each agent keeps running two steps until convergence: 1) execute R-SGD; 2) combine outputs of neighboring agents by running one step of RGD over the associated penalty function which characterizes the network agreement. The proposed algorithm is shown to converge to a consensus with high probability provided that a sufficiently small step-size is used. Similar results are established on the convergence of objective function. Experiments are conducted on two instances, i.e., distributed PCA and distributed GMM inference, showing better performance of the proposed algorithm compared to baselines.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our work and offering constructive suggestions. We provide clarifications to your comments as below.\n\n***Lack of evidence that the replacement performs better:***\n\nThank you for this comment. We argue that the algorithm in (Wang et al., 2024b) is inefficient due to the inner-loop optimization when minimizing the penalty $P(\\boldsymbol{\\phi}_t)$. We support this claim with a numerical evaluation reported in *[the response to Reviewer qfKq](https://openreview.net/forum?id=5tyvHfhRFZ&noteId=wtPNBvN9LG)*. From this result, we see that the penality minimization in (Wang et al., 2024b) does not require less iterations than our proposed approach, they actually require nearly identical numbers of iterations to achieve convergence. We also present the result in https://ibb.co/nsDtry65 for your convenience.\n\n***Comparison of the theoretical results with the Euclidean counterpart:***\n\nThank you for this insightful comment. Compared to the Euclidean counterpart (Chen & Sayed, 2012; Sayed et al., 2013; Vlaski & Sayed, 2021), one essential difference of our results is the impact of the manifold curvature $\\kappa$ (captured in the parameter $\\zeta$). For example, our convergence rates can be slower for some highly curved manifolds with $\\kappa<0$. Besides, for the network agreement, our results focus on the evolution of the penalty term $P(\\boldsymbol{\\phi}_t)$, while the work in (Vlaski & Sayed, 2021) can directly study the evolution of the network centroid due to the problem being linear in the Euclidean case (the reason can be found in *[the response to Reviewer tsm9](https://openreview.net/forum?id=5tyvHfhRFZ&noteId=FQqPRWKwJt)*). For convergence, our results focus on the non-asymptotic evolution of the cost function, while the Euclidean counterpart (Chen & Sayed, 2012; Sayed et al., 2013) only studies the bound of MSD performance at the steady state. Also, their results can benefit from the ease of the linear space. We will add more detailed comparisons in the revised manuscript.\n\n***Highlight the design of the Lyapunov function:***\n\nThank you for pointing out this vague definition. The Lyapunov function in our case is defined by $\\Delta_s'=\\mathbb{E}[J(\\boldsymbol{w}_t')-J(\\boldsymbol{w}^*)]$. The design of the Lyapunov function is special in this context due to the manifold curvature. While in the Euclidean case one can use a Lyapunov function $\\Delta_s=\\mathbb{E}[J(\\boldsymbol{w}_t)-J(\\boldsymbol{w}^*)]$, in the Riemannian case when \"telescoping\" the decrease in $\\Delta_s$ in the analysis, the curvature-related term $\\zeta$ prevents the cancellation of intermediate terms and makes this approach unfeasible. Thus, we use a specially designed \"curvature aware\" Lyapunov function $\\Delta_s'=\\mathbb{E}[J(\\boldsymbol{w}_t')-J(\\boldsymbol{w}^*)]$ inspired by (Zhang & Sra, 2016), which is a function of the \"streaming average\" of the iterates denoted by $\\boldsymbol{w}_t'$, as defined in (29). The idea consists of averaging the iterates carefully using the curvature-related parameter $\\zeta$ to obtain the desired cancellation of terms in (84) when telescoping the decrease of $\\Delta_s'$ in the convergence analysis (please see details in Appendix B.2 of the manuscript).\n\nWe will revise the manuscript to clarify the definition of this Lyapunov function and the reason behind its choice.\n\n***Report the experimental results on the step size choices:***\n\nThank you for this suggestion. For our algorithm, the step sizes are indeed critical to the tradeoff between convergence speed and steady-state performance. We provide an illustrative experimental result as in https://ibb.co/Q7L00mzj, and will report more results in the revised manuscript. \n\n***Fix the typo of zero denominators:***\n\nThanks for pointing out this typo, the denominator should be $s-s_0+1$ as in Appendix B.2 of the manuscript.\n\n***Fix mistakes in the proof of Lemma 5.1:***\n\nThanks a lot for pointing out this mistake. The correct proof uses Jensen's inequality and include the missing condition that the adjacency matrix of the graph $C$ is left-stochastic, that is, $c_{\\ell k}\\geq 0, \\sum_{\\ell=1}^K  c_{\\ell k} = 1$ for each agent $k$ in the assumption of \"Regularization on graph\".  This condition is fairly standard (Chen & Sayed, 2012; Sayed et al., 2013; Vlaski & Sayed, 2021) and can be assumed without loss of generality. \nThe correct proof is produced below, and these modifications do not influence any other proofs of the manuscript, whose correctness has also been checked by us and other reviewers.\n\n_Proof_: From the definition of $\\nabla P(\\phi_t)$ and $P(\\phi_t)$, we have\n\n$$\n\\lVert\\nabla P(\\phi_t)\\rVert^2 =  \\sum_{k=1}^K\\left\\lVert- \\sum_{\\ell=1}^K  c_{\\ell k} \\exp_{\\phi_{k,t}}^{-1}(\\phi_{\\ell,t})\\right\\rVert^2 \\leq \\sum_{k=1}^K\\sum_{\\ell=1}^K  c_{\\ell k} \\left\\lVert\\exp_{\\phi_{k,t}}^{-1}(\\phi_{\\ell,t})\\right\\rVert^2 = 2P(\\phi_t),\n$$\n\nwhere the inequality follows from Jensen's inequality and the assumption that $C$ is left-stochastic.", "claims_and_evidence": "The paper seems to extend the Riemannian diffusion adaptation algorithm proposed in Wang et al., 2024b. The difference is that the minimization of the penalty function there is replaced by a gradient descent step here. But it remains unknown why this replacement performs better. Although the minimization of the penalty is time-consuming, it is possible to require a lot less iterations than the version here with one-gradient step.\n\nThe main contribution seems to be theoretical analysis of this algorithm. It could be compared with the results in the Euclidean setting.\n\nAlso, it was mentioned that a Lyapunov function is designed. But I didn't see it in the main text.\n\nThe step size seems critical to the tradeoff between convergence and accuracy. It would be better if experimental results on it can be reported.\n\nOther minor issues: 1) denominators in Lines 275 and 282 are 0 when s=s0+1", "methods_and_evaluation_criteria": "see above", "theoretical_claims": "In the proof of Lemma 5.1, it said the inequality in Eq. (33) holds by Cauchy-Schwarz inequality. This seems wrong.", "experimental_designs_or_analyses": "Experimental designs follows Wang at el. 2024.", "relation_to_broader_scientific_literature": "This paper provides a theoretical analysis of a modified Riemannian diffusion adaptation algorithm.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "see above", "other_comments_or_suggestions": "see above", "questions_for_authors": "see above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "080rqGbFuz", "reviewer": "Reviewer_xKFw", "summary": "This paper proposes a decentralized optimization algorithm on manifolds that is termed Riemannian diffusion adaptation algorithm. The proposed algorithm follows two steps. First, in the adaptation step, each agent updates its local solution estimate on the manifold using Riemannian stochastic gradient descent (R-SGD). Second, in the combination step, agents share and combine their estimates in the tangent space. A theoretical analysis under a constant step size shows that the algorithm achieves network agreement with high probability and converges to a neighborhood of the optimal solution. The method is demonstrated on online decentralized PCA and GMM inference, with experiments on both synthetic and real-world data showing its effectiveness.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our work (especially in checking the proofs) and offering constructive suggestions. In the following, we provide clarifications and answers to your comments and questions.\n\n### **Replies to weakness:**\n\n***Improve the introduction and technical section:***\n\nThank you very much for the suggested improvements to the introduction and technical sections. We will provide sharper definitions on Page 1 and add subsections in Section 5 to clearly separate existing results from previous works and our technical results in the revised manuscript. \n\n***Discussion for the computational complexity:***\n\nThank you for this insightful comment. The computational complexity of the proposed algorithm involves two contributing terms. The first is the cost of a local adaptation step at each agent $k$ (i.e., Riemannian SGD on $J_k$), which is denoted by $T_J$. The second is the cost of the combination step, which involves a gradient step over the loss function $P_k$ that scales linearly with the number $N_{{\\rm neigh},k}$ of neighbors connected to node $k$ in the graph (that is, with the number of nonzero elements in the coefficients $c_{k\\ell}$), which we represent as $N_{{\\rm neigh},k}\\cdot T_{P}$, where $T_P$ is the cost of computing the Riemannian logarithm operator. $N_{{\\rm neigh},k}$ is also known as the *degree* of the vertex $k$ in the graph $\\mathcal{G}$.\nThus, for each agent $k$, we obtain a complexity of $T_{J} + N_{{\\rm neigh},k}\\cdot T_{P}$.\nCompared to a noncooperative setting, we have an overhead cost of $N_{{\\rm neigh},k}\\cdot T_{P}$, which is a function of both on $T_P$ (depending on the manifold) and on the number of neighbors connected to node $k$ (which depends on the network topology). \n\nThis allows us to understand how the complexity scales with the number of agents $K$. In the case where the number of neighbors to each node (i.e., their degree in the graph) is constant, the complexity does not increase with the number of agents. On the other hand, in the worst case scenario of a fully connected network (where each vertex has degree $K-1$, being connected to all other vertices), the complexity scales linearly with $K$, with a coefficient equal to $T_P$. \n\nWe will include this discussion on the computational complexity of the algorithm in the revised manuscript. In addition, we will calculate the complexity values of $T_J$ and $T_P$ (in terms of the required number of operations) for the PCA and GMM problems discussed in Section 6 of the paper and include them in the revised manuscript.\n\n***Discussion for the limitations:***\n\nThank you for this insightful suggestion. We summarize such a discussion in the following, and will include it in the revised manuscript: \n\n- Scaling with the number of agents: the discussion on the computational complexity (explained in more detail just above) shows how the complexity scales with the number of agents $K$. In particular, the computation complexity of the combination step of the algorithm scales according to the *degree* (number of neighbors) of the vertices of the graph. In the worst case of a fully connected network, this contribution scales linearly with the number of agents $K$.\n\n- Manifolds without closed form expressions: manifolds without closed form expressions for retractions, or for the Riemannian gradient, pose challenges to the implementation of the proposed algorithm, as such operations have to be approximated numerically in some way. However, we highlight that this limitation also holds for most existing Riemannian optimization algorithms, and is not specific to our work. \n\n- Theoretical analysis: one limitation of the theoretical analysis is that it relies on the use of the exponential mapping $\\exp_x$, while in practice, the use of a retraction $R_x$, which is more computationally efficient. For more details, please see *[the response to Reviewer qfKq](https://openreview.net/forum?id=5tyvHfhRFZ&noteId=wtPNBvN9LG)*.\n\n### **Replies to questions:**\n\n***Why is only one network considered?***\n\nTo illustrate the applicability to more networks, we randomly generate a different graph topology with uniformly distributed weights, and test all algorithms in the same setting as in Section 7 of the manuscript. The graph topology and experimental results can be seen in https://ibb.co/cKdYKdZ6, and remain similar to those obtained with the original network. We will include more experiments in the revised manuscript.\n\n***How does the algorithm scale with the number of agents $K$?***\n\nThe computational complexity is related to $K$. The proposed algorithm is parallelizable, with an adaptation cost that is constant per agent and an overhead cost of the combination step. The latter depends on the number of neighbors connected to each node in the graph, and in the worst-case scenario, it can increase linearly with $K$. For more details, please see the discussion on the computational complexity in the previous response.", "claims_and_evidence": "The claims are adequately supported by theoretical and experimental results.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are adequate.", "theoretical_claims": "I checked the derivations and proofs, and they seem correct.", "experimental_designs_or_analyses": "The experimental design and analyses are sound and valid.", "relation_to_broader_scientific_literature": "The paper addresses an important and central problem.", "essential_references_not_discussed": "The references are adequate.", "other_strengths_and_weaknesses": "Strengths: \n- The addressed problem is important and central.\n- To the best of my knowledge, although simple and straightforward, the proposed algorithm is new\n- The theoretical analysis presents important properties of the algorithm\n- The experiments nicely demonstrate the benefits of the algorithm compared to baselines in two classical applications.\n\nWeaknesses:\n- The introduction could be improved (see below)\n- A discussion on the computational complexity of the algorithm is missing.\n- A discussion on the limitations is missing. For example, how well does the algorithm scale with the number of agents? How is the exp map (or retraction) computed on manifolds without a closed-form expression?", "other_comments_or_suggestions": "- Page 1, right column, lines 011-025: The discussion is vague and should be more concrete. Many terms are mentioned (e.g., embedding and Whitney embedding) without any introduction. To clarify and strengthen the motivation, this paragraph should be re-written.\n\n- Page 1, right column, description of contributions 1: the paragraph contains many terms whose meaning is not completely clear at this stage (adaptation strategy, fully intrinsic, general manifolds, a sequence of efficient adaptation and combination steps).\n\n- Page 1, right column, description of contributions 2: same as in contribution 1, the paragraph contains many unclear terms (network agreement, decreasing geodesic distance, curvature-dependent, non-asymptotic convergence, proper design of Lyapunov function.\n\n- Sec. 5 contains many existing results (up to Cor. 5.5) - consider separating the old results from the new results.\n\n- In Sec. 6.1 - consider putting the definition of MSD in a non-inline equation for better emphasis.", "questions_for_authors": "- In Sec. 7 - only one network is considered. Why only one? How does the algorithm scale with the number of agents K?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N9uGDZyjqM", "reviewer": "Reviewer_8uHb", "summary": "This paper aims to solve the online decentralized optimization problem on the general Riemannian manifold for multi-agents. The proposed Riemannian diffusion adaptation method contains two stages: an adaptation step and a combination step. It theoretically proves that all agents will approximately converge to a network agreement with non-asymptotic convergence after sufficient iterations. The experiments on two typical manifolds for PCA and GMM show that the proposed method significantly outperforms the non-cooperative, DRSGD and ECGMM methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our work (especially in checking the proofs) and offering constructive suggestions. In the following, we provide clarifications and answers to your comments and questions.\n\n### **Replies to weakness:**\n\n***Conduct more experiments for wider application aspects:***\n\nThank you for this comment. We highlight that while PCA and GMM inference are key problems in machine learning, the proposed method is fairly general and applicable to a wide set of problems (the revised manuscript will be modified to better showcase this). Moreover, one of the main contributions of our paper is the theoretical analysis, and we find that the experimental validation in our paper is still in line with those performed in related work (see, e.g., Bonnabel, 2013; Zhang & Sra, 2016; Chen et al., 2021; Vlaski & Sayed, 2021; Li & Ma, 2023). While additional experiments with complex real-world benchmarks would definitely improve the paper, unfortunately, we were not able to perform such experiments in the comparatively short time available during the rebuttal period.\n\n***Claim the fitness of the assumptions in real applications:***\n\nThank you for this insightful comment. These main assumptions made in the paper are indeed standard in Riemannian and decentralized optimization algorithms, particularly in what concerns their theoretical analysis, see e.g.,  (Bonnabel,\n2013; Zhang et al., 2016; Tripuraneni et al., 2018; Afsari, 2011; Chen & Sayed, 2012; Sayed et al., 2013; Afsari et al., 2013). A necessary assumption for the derivation of the algorithm is the smoothness of the risk functions, since the proposed algorithm relies on gradients, while the remaining assumptions are used in the theoretical study. Moreover, an assumption that is less frequently satisfied is geodesic convexity.\nConsidering the practical examples studied in the paper (PCA and GMM inference), the cost function of PCA formulated on the Grassmannian manifold has been recently shown to be geodesically convex [R1]. On the other hand, for GMM inference, the log-likelihood has been shown to be geodesically convex for the case of a single Gaussian (Hosseini & Sra, 2015), but not necessarily when multiple Gaussians are considered. From the example of GMM inference, we find the proposed algorithm itself can work even in some situations when not all these assumptions are satisfied. \nWe will update the revised manuscript to discuss the applicability of the assumptions in our work to practical problems.\n\n[R1] Alimisis, F., and Vandereycken, B. Geodesic convexity of the symmetric eigenvalue problem and convergence of steepest descent. Journal of Optimization Theory and Applications, 203(1), 920-959, 2024. \n\n***Discussion for the computational complexity:***\n\nThank you for this useful comment. While the computation complexity will scale with the dimension of the manifold, the proposed approach is a first-order gradient-based method, and its complexity remains as low as in other first-order optimization approaches such as (Bonnabel, 2013; Zhang & Sra, 2016; Tripuraneni et al., 2018). For a detailed discussion on the computational complexity of the proposed algorithm, please refer to *[the response to Reviewer xKFw](https://openreview.net/forum?id=5tyvHfhRFZ&noteId=Lgg3fpLQRg)*.\n\n### **Replies to questions:**\n\n***Why does the Riemannian centralized method perform so much better? What are the advantages of the proposed method?***\n\nThe centralized solution achieved the best performance, as it can access all the data over the whole network at every iteration.\nThe proposed algorithm is fully decentralized, where each agent uses only locally observed data to update its local estimate and exchange information only among neighboring agents. Although the proposed algorithm has lower performance compared to the centralized method, it can be computed in parallel on multiple agents. We will add more details in the revised manuscript to better explain the differences and advantages.\n\n***How does the proposed method work on a manifold defined through an implicit function?***\n\nThe proposed algorithm is designed for general Riemannian manifolds, but it requires the computation of retractions and Riemannian gradients, as in other Riemannian optimization works (see, e.g., (Boumal, 2023; Zhang & Sra, 2016; Bonnabel, 2013), to name a few). When mentioning \"general manifolds\", we aimed to differentiate our approach from extrinsic works that focus on specific examples, such as Stiefel manifolds (Chen et al., 2021; Wang & Liu, 2022). For a manifold defined through an implicit function, such a Riemannian structure and the required operations would have to be derived to make those strategies applicable. We will clarify the \"general manifolds\" statement in the revised manuscript.", "claims_and_evidence": "Yes. The authors provide detailed and complete proofs of the theorems.", "methods_and_evaluation_criteria": "The proposed method is evaluated on synthetic data and real data in application of distributed PCA and GMM inference. However, more complex situations and applications are lacking discussion.", "theoretical_claims": "Yes, I have checked most proofs for lemmas and theories, especially for Lemma 5.11 and Theorem 5.15.", "experimental_designs_or_analyses": "If for an intuitive demonstration, the example in distributed PCA and GMM inference on synthetic and real data is great. But for wide application aspects, the experiments need to conduct more complex situations in real word benchmarks.", "relation_to_broader_scientific_literature": "The previous works on decentralized optimization are in Euclidean space. When extending to Riemannian manifolds, some previous works construct functions that map the points from the manifold to Euclidean space. But this paper proposes a more direct method, avoiding transformation between manifold and Euclidean space, and it can be proved theoretically that the algorithm will be non-asymptotic convergence.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Pros:\n1. The proposed methods are concise and clear. The two stages: for the adaptation step, the idea is to compute a local solution for each agent. In the combination step, the idea is making agreements with all agents. \n\n2. The whole idea is very simple, and the theoretical analysis is rich.\n\n3. Compared to previous works, the proposed method avoids transforming points to Euclidean space and back to manifold repeatedly.\n\nCons:\n1. The two examples and applications are all simple cases, it is hard for readers to accept that the proposed method will have wide application.\n\n2. Here are 4 assumptions in this paper, I think it lacks claims that these assumptions will fit most common situations in real applications?\n\n3. The computational complexity of the proposed method is not discussed, in the high-dimensional case, will the computational cost be very high?", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "1. In experimental results, why do the Riemannian centralized methods outperform the proposed methods so much? What are the advantages of the proposed method compared to Riemannian centralized method?\n2. The authors said that the proposed method is a strategy over general manifolds. However, in the general manifold case, e.g., the manifold embedded in $\\mathbb{R}^{m+n}$ defined by implicit function $p=(u, v) \\in \\mathbb{R}^{m+n}$ where $v=f(u)$ with $f:\\mathbb{R}^m\\rightarrow \\mathbb{R}^n$, how does the proposed Riemannian diffusion Adaptation process?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VsW6lKm60u", "reviewer": "Reviewer_tsm9", "summary": "The paper concerns online distributed optimization for data on Riemannian manifolds. The authors propose an algorithm for distributed optimization between a number of agents with combination steps in the tangent spaces of the current values at the agents. The paper contains a theoretical analysis of the algorithm, and experimental validation on synthetic and real data.\n\n## update after rebuttal\nI have maintained my initial score as it still adequately reflects my evaluation of the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our work and pointing out the strengths and weaknesses. In the following, we provide replies to weaknesses:\n\nWe would like to emphasize that the proposed work is not a trivial generalization, even though there is an Euclidean counterpart to the Riemannian diffusion adaptation algorithm. For example, when combining the local estimates lying on manifolds, it is no longer possible to use a simple linear combination of the local estimates as in the Euclidean counterpart, as we do not assume a vector space structure in the manifold. We tackled this issue by proposing a one-step Riemannian gradient descent over a network agreement loss function to achieve information exchange during the learning and adaptation process.\n\nAs you also mentioned, the theoretical analysis (both in terms of the network agreement and non-asymptotic convergence) involves fundamentally new ideas since our analysis is fully geometric. For example, in the network agreement analysis, we cannot use adjacency matrix decomposition as in the Euclidean counterpart due to the combination step in our case being *non-linear*.  Thus, the analysis is rendered significantly more difficult since the network centroid cannot be computed using a simple/linear expression as in the Euclidean case. Therefore, we propose a novel framework to study the network agreement through the evolution of the penalty term $P(\\boldsymbol{\\phi}_t)$. In the non-asymptotic convergence analysis, curvature-related terms also make traditional techniques used in Euclidean spaces unfeasible, requiring careful design of a Lyapunov function (please see more details in *[the response to reviewer bCcG](https://openreview.net/forum?id=5tyvHfhRFZ&noteId=IqmTIhR1dX)*).", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I did not check the proofs for correctness. My overall impression from reading the main paper is that the exposition is correct", "experimental_designs_or_analyses": "I did not find any issues", "relation_to_broader_scientific_literature": "while I am not specifically aware of the literature on e.g. decentralized optimization, I believe the literature is adequately surveyed", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\n- well-written paper. Clear explanation of the chosen methodology\n- well-chosen methodology to solve the problem\n- thorough theoretical analysis of the proposed algorithm\n\nWeaknesses:\n- I believe the algorithm is a fairly straight-forward generalization of its Euclidean counterpart. This is not necessarily a bad thing, it just mean that the algorithm itself does contribute significant new ideas. This is partly balanced by the theoretical analysis that has to account for the geometry", "other_comments_or_suggestions": "no other comment", "questions_for_authors": "no questions", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper has received positive reviews and all the reviewers are of the view of accepting the paper. In the final version, please take care of the comments and address the minor issues. Also include the explanations missing.
Decision: Accept (poster)