Decentralized Riemannian Conjugate Gradient Method on the Stiefel Manifold
Authors: Jun Chen
Haishan Ye
Mengmeng Wang
Tianxin Huang
Guang Dai
Ivor Tsang
Yong Liu
Venue: ICLR 2024 poster (2024)
Keywords: Decentralized optimization
Stiefel manifold
Conjugate gradient method
Primary area: optimization

Abstract: The conjugate gradient method is a crucial first-order optimization method that generally converges faster than the steepest descent method, and its computational cost is much lower than that of second-order methods. However, while various types of conjugate gradient methods have been studied in Euclidean spaces and on Riemannian manifolds, there is little study for those in distributed scenarios. This paper proposes a decentralized Riemannian conjugate gradient descent (DRCGD) method that aims at minimizing a global function over the Stiefel manifold. The optimization problem is distributed among a network of agents, where each agent is associated with a local function, and the communication between agents occurs over an undirected connected graph. Since the Stiefel manifold is a non-convex set, a global function is represented as a finite sum of possibly non-convex (but smooth) local functions. The proposed method is free from expensive Riemannian geometric operations such as retractions, exponential maps, and vector transports, thereby reducing the computational complexity required by each agent. To the best of our knowledge, DRCGD is the first decentralized Riemannian conjugate gradient algorithm to achieve global convergence over the Stiefel manifold.

Published as a conference paper at ICLR 2024
DECENTRALIZED RIEMANNIAN CONJUGATE GRADI- ENT METHOD ON THE STIEFEL MANIFOLD
Jun Chen', Haishan Ye Mengmeng Wang', Tianxin Huang'
Guang Dai Ivor W. Tsang*., Yong Liu'
'Zhejiang University 2Xi'an an Jiaotong University SSIT AI Lab, State Grid Corporation of China *CFAR and IHPC, Agency for Science, Technology and Research SCCE, NTU (junc, mongmmmmmgegggggggg 21 2 bolangggdal ivor. ema com, yongliušiipe zju edu.c.
cn, yehaishan@xx edu.. edu. cn
ABSTRACT
The conjugate gradient method is a crucial first-order optimization method that generally converges faster than the steepest descent method, and its computational cost much lower than that of second-order methods. However, while various types of conjugate gradient methods have been studied in Euclidean spaces and on Riemannian manifolds, there is little study for those in distributed scenarios. This paper proposes decentralized Riemannian conjugate gradient descent (DRCGD) method that aims at minimizing a global function over the Stiefel manifold. The optimization problem is distributed among network of agents, where each agent is associated with a local function, and the communication between agents occurs over an undirected connected graph. Since the Stiefel manifold is a non-convex set, a global function is represented as finite sum of possibly non-convex (but smooth) local functions. The proposed method free from expensive Riemannian geometric operations such as retractions. exponential maps, and vector transports, thereby reducing the computational complexity required by each agent. To the best of our knowledge, DRCGD is the first decentralized Riemannian conjugate gradient algorithm to achieve global convergence over the Stiefel manifold.
INTRODUCTION
In large-scale systems such machine learning, control, and signal processing, data is often stored in a distributed manner across multiple nodes and it is also difficult for a single (centralized) server to meet the growing computing needs. Therefore, the decentralized optimization has gained significant attention in recent years because it can effectively address the above two potential challenges. In this paper, we consider the following distributed smooth optimization problem over the Stiefel manifold:
min
f (x:),
S.L.
Fn. 24 E M, Vi =i= 111,2,..... 1,,,
where n is the number of agents, fi is the local function at each agent, and M M St(d,)) Sttd far e
Rdxr [Ix Tu 1,) is the Stiefel manifold (r < d) (Zhu 2017 Sato 2022 Many important large- scale tasks can be written as the optimization problem (1, e.g., . the principle component analysis (Ye)
& Zhang 2021), eigenvalue estimation (Chen et al.] (021). ) dictionary learning (Raja & Bajwal
2015). and deep neural networks with orthogonal constraint (Voonntovv et al. 2017 Huang et al. 2018
Eryilmaz & Dundar 2022
The decentralized optimization has recently attracted increasing attention in Euclidean spaces. Among the methods explored, the decentralized (sub)-gradient method stands out as straightfor- ward way combining local gradient descent and consensus error reduction (Nedic & Ozdaglar 2009
Yuan et al. 2016). Further, in order to converge to stationary point (i.e., exact convergence) with
*Corresponding author

---

Published as a conference paper at ICLR 2024
fixed step size, various algorithms have considered the local historical information, e.g., gradient tracking algorithm (Qu & Li 2017] Yuan et al. 2018). primal-dual framework (Alghunaim et al.
2020), EXTRA (Shi al. 2015). and ADMM (Shi et al. 2014 Aybat et al. 2017). when each local
function is convex.
However, none of the above studies can solve the problem since the Stiefel manifold is convex set. Based on the viewpoint of [Cen et al. (021)) the Stiefel manifold is an embedded sub-manifold in Euclidean space. Thus, with the help of Riemannian optimization (i.e., optimiza- tion on Riemannian manifolds) (Absil et al. 2008 Bouual et al. 2019; Sato 202T), the problem (T) can be thought as a constrained problem Euclidean space. The Riemannian optimization nature brings more challenges for consensus construction design. For instance, straightforward way is to take the average -i=1 2t Fuclidean space. However, the arithmetic average does not apply to the Riemannian manifold because the arithmetic average of points can be outside of the manifold. To address this problem, Riemannian consensus method has been developed (Shah) 2017). but needs to use asymptotically infinite number of consensus steps for convergence. Subsequently, Wang & Liu 2022) combined the gradient tracking algorithm with an augmented Lagrangian function to achieve the single step of consensus. Recently, Chen et al. (2021) proposed a decentralized Rieman- nian gradient descent algorithm over the Stiefel manifold, which also requires only the finite step of consensus to achieve the convergence rate of O(1 (()/VK). Simultaneously. the corresponding gradi- tracking version was presented to reach a stationary point with the convergence rate of ((1/K) / On this basis, Deng & Hu (2023) replaced retractions with projection operators, thus establishing a decentralized projected Riemannian gradient descent algorithm over the compact submanifold to achieve the convergence rate of ((1/v Similarly, the corresponding gradient tracking version also achieved the convergence rate of OL1/K).
In this paper. we address the decentralized conjugate gradient method on Riemannian manifolds, which we refer to as the decentralized Riemannian conjugate gradient descent (DRCGD) method. In essence, the conjugate gradient method is an important first-order optimization method, which generally converges faster than the steepest descent method, and its computational cost is much lower than that of second-order methods. As well, conjugate gradient methods are highly attractive for solving large-scale optimization problems (Sato) 2022). Recently, Riemannian conjugate gradi- ent methods have been studied, however, expensive operations such as parallel translations, vector transports, exponential maps, and retractions are required. For instance. some studies
theoret-
ical approach, i.c., parallel translation along the geodesics (Smith) [995| Edelman & Smith 1996]
Edelman et al.) 1998), which hinders the practical applicability. More generally, other studies utilize a vector transport (Ring & Wirth 2012) Sato & Iwai 2015) Zhu [017]] Sakai & liduka] [020 (02T)
or inverse retraction (Zhu & Sato 2020) to simplify the execution of each iteration of Riemannian conjugate gradient methods. Nonetheless, there is still room for computational improvements.
This paper focuses designing an efficient Riemannian conjugate gradient algorithm solve the problem (I) over any undirected connected graph. Our contributions are summarized as follows:
1. We propose a novel decentralized Riemannian conjugate gradient descent (DRCGD) method whose global convergence is established under an extended assumption. It is the first Riemannian conjugate gradient algorithm for distributed optimization.
2. We further develop the projection operator for search directions such that the expensive retraction and vector transport completely replaced. Therefore, the proposed method is retraction-free free and vector transport-fres, and achieves the consensus of search directions, giving rise to appealing algorithm with low computational cost.
3. Numerical experiments are implemented to demonstrate the effectiveness of the theoretical results. The experimental results are used to compare the performance of otate-of-the-art ones eigenvalue problems.
2 PRELIMINARIES
2.1 NOTATION
The undirected connected graph G = (V,E), where == (1,2.-.. .n. is the set of agents and is the set of edges. When W is the adjacency matrix of G, we have Wy Wy; and Wi; > 0 if an
2

---

Published as a conference paper at ICLR 2024
edge (2.5) & and otherwise Way O. We use to denote the collection of all local variables x; by stacking them, i..,, x (x] ,22 .2..... 2, Then define f(x) := 1 Li=1 f((z).. We denote the n-fold Cartesian product MM with itself as M = M x x M, and use [ng] == (1,2,-.. .n.. For any E M, denote the tangent space and normal space of M respectively. We mark || || as the Euclidean norm. The Euclidean gradient of f is V fz) and the Riemannian gradient of is grad fxx). Let la and In R" be the d x d identity matrix and a vector of all entries one, respectively. Let W = W @ la. where / is a positive integer and & denotes the Kronecker product.
T.M and N.M,
2.2 RIEMANNIAN MANIFOLD
We define the distance of point z E Rdxr onto .M by
dist(r, M) == inf |ll [ x||. yEM
then, for any radius > O, the R-tube around M can be defined as the set: (M(R) fa (2, S R).
Furthermore, we define the rearest-point projection of point Rdxr onto M by
(M := arg min |1y - 3EM
xI|.
Based on Definition 1 it should be noted that closed set is Rt-roximally smooth if the projec- tion P (x) singleton whenever dist(x,,M) < R. In particular, when M the Stiefel manifold, it is a 1-proximally smooth set (Balashov & Kamalov 2021). And these properties will be crucial for us to demonstrate the convergence.
Definition Clarke et al. (1995) An R-proximally smooth set M satisfies that for any real γ (0, R), the estimate holds:
(PM(2) - PM,y)l <
R || yll. UM(T).
(2)
To proceed the optimization on Riemannian manifolds, we introduce key concept called the re- traction operator in Definition Obviously, the exponential maps (Absil et al., 2008) also satisfies this definition, so that the retraction operator not unique.
Definition 2 Absil er al. 2208 A smooth map R TM + M is called a retraction on smooth manifold M if the retraction of R the tangent space T.M at any point x MM, denoted by R., satisfies the following conditions:
(i) R is continuously differentiable.
(ii) (0,,) (iii) DR, (0,) = idt_M, the identity mapping on T,M.
where O, is the zero element of T.
Furthermore, we can introduce well-known concept called vector transport, which as special case of parallel translation can be explicitly formulated on the Stiefel manifold. Compared to parallel translation, vector transport is easier and cheaper to compute (Sato) 2021 Using the Whitney sum TM + TM := (17, n, E T,M, x E M), we can define a vector transport as follows.
Definition 3 Absil et al. 2008) A map T TM + TM TM: (n,E) I,(E) is called vector transport on M if there exists retraction R on M and T satisftes the following conditions for any M:
(i) (E) E M, (ii) TT (E) = =. E T.M.
(ii) Ta(aE + bC) = (E) + bT,(C), a,bER, n.E.C T.M.
Example 1 Absil et al. (2008) On Riemannian manifold M with retraction R, we can construct a vector transport g.t TM e TM + TM: (n, + T2 defined by
x.,(()) := D n.E T.M, x M,
called the differentiated relraction.
3

---

Published as a conference paper at ICLR 2024
3 CONSENSUS PROBLEM ON STIEFEL MANIFOLD
Let 01," " In E M be the local variables of each agent, we denote the Euclidean average point of 01," 11. In by
Z2
(3)
In Euclidean space, one can use Σx= c 8/1 to measure the consensus error. Instead, on the
Stiefel manifold St,d, r), the induced arithmetic mean (Sarlette & Sepulchre 2009), defined as follows:
arg
by x.11 (s)
(d,r)
where Psc(-) is the orthogonal projection onto r). Considering the Riemannian optimization, the Riemannian gradient of fi(x) on St(d,r), endowed with the induced Riemannian metric from the Euclidean inner product (.--), is given by
grad fx(x) = (V)()))
(5)
where Pr. (1)) is the orthogonal projection onto T.M. More specifically (Edelman et al. Absil et al. 2008), for any y E Rd we have
1998
Pr.M(y)
z(x + y x).
(6)
Subsequently, the e-stationary point of problem [T] is given by Definition
Definition Chen et al. (2021) The set of points x (o) 2z ... Ih is called an e-stationary point of problem (7 if the following holds:
Σ
F|| Se
and grad f())11 sc
n
where f(x) = + (())..
To achieve the stationary point given in Definition 4 the consensus problem over St(d, r) needs to be considered to minimize the following quadratic loss function
min s' (x) = MΣ> wt || - x,,1²
(8)
1=1
S.L. F. M, Vi [n].
where the positive integer / used to indicate 1-th power of the doubly stochastic matrix W. Note that W7y is computed through performing / steps of communication on the tangent space, and satisfies the following assumption.
Assumption We assume that the undirected graph G is connected and W is doubly stochastic, ie., (i) W = W (üi) Wij 2 0 and O < Wa < for all i,j; (iii) Eigenvalues of W lie in (-1,1} The second largest singular value a2 of W lies in [0, 1).
Throughout the paper, we assume that the local function f((x) is Lipschitz smooth, which is standard assumption theoretical analysis of the optimization problem (Jorge Stephen 2006
Zeng & Yin 2018 Deng & Hu 2023).
Assumption Each local function f((x) has Lipishhit continuous gradient
[Vf(()) - I L||x - E [n]]
(9)
and let Lj max [f+(=)]] Therefore, (x) is also L-Lipschitz continuous in the Euclidean space and L, 2 max,ess(d.r) [[]]()]]
With the properties of projection operators, we can derive the similar Lipschitz inequality on the Stiefel manifold the Fuclidean-type one (Nesterov 2013) in the following lemma.
4

---

Published as a conference paper at ICLR 2024
Lemma (Lipschitz-type inequality) Under Assumption 2 for any z. St(d, if f(z) is L-
Lipschitz smooth in the Euclidean space, then there exists a constant Lg = L + 2 such that
grad fi(x) ((r)) grad f((w)l & م - vll. i [n].
(10)
Proof. The proofs can be found in Appendix
Furthermore, since the Stiefel manifold is 1-proximally smooth set (Balashov & Kamalov 202 the projection operator on St(d, r) has the following property based on Definition
[PM(2) - PMM - 1- -1- vll. Vz, Um(1), (0.
(11)
This inequality will be used to characterize the local convergence of the consensus problem.
4 DECENTRALIZED RIEMANNIAN CONJUGATE GRADIENT METHOD
In this section, we will present decentralized Riemannian conjugate gradient descent (DRCGD) method for solving the problem described in Algorithm [ and yield the convergence analysis.
4.1 THE ALGORITHM
We now introduce conjugate gradient methods on Riemannian manifold M. Our goal is to develop the decentralized version of Riemannian conjugate gradient methods on St,d, r). The generalized Riemannian conjugate gradient descent (Absil et al. 2008 Sato 2021) iterates
Tk+1
Res (a&T)s)
(12)
where 7kk is the search direction the tangent space T and og > 0 is the step size. Then an operation called retraction R2g is performed to ensure feasibility, whose definition is given in Definition 2 It follows from Definition 3 that we have Tamm (m)) M. Thus, the search
direction Sato 2021) can be iterated as
7
grad f(*++1) 3K41 (πk),
k=0,1,-.
(13)
where the scalar Bx+1 E R. Since grad f (x T and 3K+17l Tr they belong to different tangent spaces and cannot be added. Hence, the vector transport in Definition needs to be used to map a tangent vector in M to one in T M.
However, vector transports still computationally expensive, which significantly affects the ef- ficiency of our algorithm. To extend search directions in the decentralized scenario together with computationally cheap needs, perform the following update of decentralized search directions:
1k = - grad [((Lik+1) + Bi,ki PT Premet
Σ W! Wh Ti.k
i E [m]]
(14)
where grad (((,,,+1) E Ta., M and Ti, E M. Note that ΣØ= Wii clearly not on the tangent space Tr M and even not on the tangent space Tr, M. Therefore, it is important to define the projection Pr. M of Σÿ= Wijng T M so that we can compute the addition in the same tangent space T M to update the 71,++1- Simultancously, Σラ= W fii also achieves the consensus of search directions. On the other hand, similar to the decentralized projected Riemannian gradient descent (Deng Hu 2023), the DRCGD performs the following update the k-th iteration
TiA++ PM
W WoyTK + OLTTR
i E [n]]
(15)
The Riemanian gradient step with unit step size, i.c., PM EEi= Wif utilized in the above iteration for the consensus problem (8). So far, we have presented the efficient method by replacing both retractions and vector transports with projection operators.
5

---

Published as a conference paper at ICLR 2024
Regarding Sk+1, there are six standard types in the Euclidean space, which proposed by (2000), Polak & Ribiere (196 and Polyak Hestenes et al. [952), and Liu & Storey 1991), respectively. Furthermore, the Riemannian version of /k++1 was given in (Sato] 2022). Ring & Wirth (2012) analyzed the Riemannian conju-
Fletcher & Reeves ),64), Dai & Yuan
gate gradient with a specific scalar FR which a natural generalization of # in (Fletcher & K++
Reeves 1964). In this paper, we yield naive extension of [k+1 in terms of the decentralized type
RR-FR- (grad Si (11,,,44) grad (111,,4)))) BR-
l|grad fi(Ts,
(16)
(grad (I) grad f((2i,,))
I|grad f((Ts,))
where the "R R stands for "Riemannian" and "FR" stands for "Fletcher-Reeves" type (Fletcher & Reeves 1964). With the above preparations, we present the DRCGD method described Algo- rithm I The step first performs consensus step and then updates the local variable using search directions 4),k- The step 4 uses the decentralized version of - The step 5 is to project the
search direction onto the tangent space 1 M, which follows a projection update.
Algorithm Decentralized Riemannian Conjugate Gradient Descent (DRCGD) for solving Eq.(I).
Input: Initial point Xo E MM", an integer I, set 7/.0 = grad fi(1,,o). 1: for k 0.... do
> for each node E [n]. in parallel
2: Choose diminishing step size on O(IVV))
3: Update 24,4+1 PM Σラ= WijJA a.TTi.k
4: Compute B |l grad fi (1 grad (1
5: Update 71,++1 grad (II, 3 Premen M Eii= W2yTE.))
6:
end for
To analyze the convergence of the proposed algorithm, the following assumptions on the step size Oi are also needed (Sato 2022).
Assumption 3 The step size ag > 0 satisfies the following conditions: (i) og decreasing and bounded
a++1 1, 0 ag S 2(1-))
lim Ok 0, lim
(17)
Og
4C
(ii) For constant ej and 02 with ai 62 1, the Armijo condition on M is
f(( S (((,,,))) ci (grad fi(2i,)); ((,t,,)))), Na,k)
(18)
(iii) The strong Wolfe condition is
( (grad Ji (1i, F. Famm. (m.x))
c (grad fa (Fi,K) mikk
(19)
21.441
4.2 CONVERGENCE ANALYSIS
This subsection focuses the global convergence analysis of our DRCGD algorithm. Different from the bounded assumption of a vector transport in (Sato) 2022), we give an extended assump- tion about the projection operator in the decentralized scenario, where gi == grad (x Specifically, we assume, for each & 2 O, that the following inequality holds
(BLAHI,Pr SLA+I, Pr Prefe
Σ W Ti.k
<oAtt, gR aama (mBx)) senee
(20)
Zci+1
which will be used as a substitute to proceed the following demonstration. Next, we consider proving the convergence of the Beeccer-Reeees-typpe DRCGD method for each agent, i.c., we use $ in (16 See Al-Baali (1985) for its Euclidean version and Sato (2022) > for its Riemannian version.
At last, we establish the global convergence based on Theorem 2 and Theorem 3 which give the locally linear convergence of consensus and the convergence of each agent, respectively.

---

Published as a conference paper at ICLR 2024
Theorem (Global convergence). Let {xx} be the sequence generated by Algorithm Suppose
that Assumptions andd hold. If xu E N == (x || - øl| I 2/2} and ||3 I C fa constant C > 0), then lim inf grad [fx 0.
(21)
Proof. The proofs can be found in Appendix D.1
5 NUMERICAL EXPERIMENT
In this section, we compare our DRCGD method with DRDGD (Chen et al. 2021) and DPRGD (Deng & Huj 2023), which are first-order decentralized Riemannian optimization methods using retraction and projection respectively, on the following decentralized cigenvector problem:
Σ tr (a) A A,.:).
min xEM
s.t.
I1
Zn
(22)
2n
where M = St(d,r) x St(d, A₁ R is the local data matrix for agent and m;
n is the sample size. Note that A == [A] A ...... ANl is the global data matrix. For any solution x of (2). giving an orthogonal matrix Q IR**" xx Q is also a solution in essence. Then the distance between two points and x² can be defined
dg (z. (1,,"))
Q Q- QQ-QQQ =I. |xQ x x"1|-
min
We employ fixed step sizes for all comparisons, i.e., the step size is set to Ork VK with K being the maximal number of iterations. We examine various graph matrices used represent the topology across agents, i.e., the Erdos-Renyi (ER) network with probability and the Ring network. It follows from (Chen al. 202T) that W the Metroplis constant matrix (Shi al. 2015).
We measure algorithms by four metrics, i.e., the consensus error ||x; - x the gradient norm ( the objective function - and the distance to the global optimum d, (Tx, x²), respectively. The experiments are evaluated with the Intel(R) Core(TM) i7-12700 CPU. And the codes are implemented in Python with mpi4py.
5.1 SYNTHETIC DATA
We fix mi = = ... = m, = 1000. d = 10, and r == 5. Then we generate m, X n independent and identically distributed samples obtain by following standard multi-variate Gaussian distri- bution. Specifically, let A UVVT be the truncated SVD, where U E R 1000n and V E ddd are orthogonal matrices, and Raxd be Σ,, Eg,0 A 1/2 where E [d] and eigengap A 10. We also fix the maximum iteration epoch to 200 and early terminate if d, (Tx, x²) < 10-5
x is diagonal matrix. Then we set the singular values of A
The comparison results are shown in Figures I 2 and It can be seen from Figure I that our DRCGD converges faster than DPRGD under different numbers of agents (n 16 and 32).
When n becomes larger, these two algorithms both converge slower. In Figure 2 DRDGD gives very similar performance under different numbers of consensus steps, i.e., & {1. 10, oo). which means that the numbers of consensus steps do not affect the performance of DRDGD much. A similar phenomenon can be observed in DPRGD. In contrast, as the communication rounds increase, our DRCGD consistently achieves better performance. Note that one can achieve the case of t - co through a complete graph with the equally weighted matrix. For Figure we see DPRGD has very close trajectories under different graphs on the four metrics. In fact, this also occurs for DRDGD, However, the connected graph ER helps our DRCGD obtain a better final solution than the connected graph Ring because ER network with the probability of each edge is a better graph connection than Ring network. Moreover, our DRCGD with ER = 0.6 performs better than that with ER p 0.3. In conclusion, DRCGD always converges faster and performs better than both DRDGD and DPRGD under different network graphs because the search direction conjugate gradient method we designed in Eq. (14) is not only vector transport-free, but also achieves the consensus.

---

Published as a conference paper at ICLR 2024
24RG0 m012
0611
20
15
10 20
100 10
Figure 1: Numerical results synthetic data with different numbers of agents, eigengap A 0.8, Graph: Ring, f = 1, = 0.01. y-axis: log-scale.
15a9
16
10a4
DACGD,
DACGD,
DRCGD, ta
10
DRDGD.
1.09
DRDGD. t=10
DRCGD, tw1
10
DRDGD, t-x
DRCGO,
10
DRDGO.
10th
DRDGD, tm10
DRDGD to
25
75
100
125
150
175
200
25
50
100 Epoch
125
150
175
200
Epoch
16
10-4
400.4"1
t-1
DRCGD, t=10
10-2
DRCGD, t=10
DRCGID, t=s
DRCGD, 1-o
DRDGD. t=10
DRDGD. t=10
twx
10-1
DRDGD,
25
75
125
175
50
100
150
200
Epach
Epach
Figure 2: Numerical results on synthetic data with different numbers of consensus steps, eigengap
A 0.8, Graph: Ring, 16, à 0.01. y-axis: log-scale.
5.2 REAL-WORLD DATA
For MNIST, the samples consist of 60000 hand-written images where the dimension of each image is given by d = 784. And these samples make up the data matrix of 60000 x 784, which is randomly and evenly partitioned into agents. We normalize the data matrix by dividing 255. Then each agent holds local data matrix A; of 60000 784. For brevity, we fix / = 1, = 5, and 784, respectively. W the Metroplis constant matrix and the graph is the Ring network. The step size of our DRCGD, We set the maximum iteration epoch to 1000 and carly
We also present some numerical results on the MNIST dataset (LeCun 1998
DRDGD, and DPRGD is ag 60000 terminate it if d, (Zk, x ))= S 10-5
The results for MNIST data with 20 are shown in Figure 4 DRDGD and DPRGD are almost the same. When á becomes larger, all algorithms converge faster. And our DRCGD converges much faster than both DRDGD and DPRGD.
We that the performance of
8

---

Published as a conference paper at ICLR 2024
DROGO, ER pm0.3
DRCGD, ER p-0.6
Ring
DRRGD, ER p-0.3
DPRGD, ER p=008
1549
DIRGD, Ring
DRCGD, ER p-0.6
DACGD, Ring
10-3
p-0.3
DPRCD ER p-0.6
DFRGD, Aing
10a9
25
75
125
150
175
50
1.00
150
Epach
Epach
DRCGD,ED ER p-0.3 DACGD,
DRCGD, ER p-3033
10-
DRCGD, p-0.6
DRCGD, Ring
DRCGD, Ring
10--
DPRGD ER
DARGD,
DFRGD, p-0.6
DPRGO, Ring
DPRGD, Ring
13-3
100
200
Figure 3: Numerical results on synthetic data with different network graphs, eigengap A = 008, 1 10, = 16, = 0.05. y-axis: log-scale.
10a2
13-1
DRCGD, t= 6=
23-4
DROGD, t= 6=0.02
DACGD, t=1, 8=0.05
DRCGO, t=1, 6-0.05
DPRGD, t-1, 6-0.05
DPRCD, 1=1, 6-0.05
DROGD, 1-), 6-0.02
DRDGO, 1-1, 8-0.00
DRDGD, t=1,
Epsch
Figure 4: Numerical results on MNIST data with single-step consensus, Graph: Ring, n 20.
CONCLUSION
We proposed the decentralized Riemannian conjugate gradient method for solving decentralized op- timization over the Stiefel manifold. In particular, it is the first decentralized version of the Rieman- nian conjugate gradient. By replacing retractions the global convergence was established under an extended assumption (20) on the basis of (Sato) 2021). thereby reducing the computational complexity required by each agent. Numerical results demonstrated the effectiveness of our proposed algorithm. In the future, will further extend our algorithm to compact sub-manifold. On the other hand, it will be interesting to develop the decentralized version of online optimization over Riemannian manifolds.
vector transports with projection operators,

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported by NSFC 62088101 Autonomous Intelligent Unmanned Systems.
REFERENCES
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms matrix manifolds. Princeton University Press, 2008.
Mchiddin Al-Baali. Descent property and global convergence of the fletcher-reever method with inexact line search. IMA Journal of Numerical Analysis, 5(1):121-124, 1985.
Sulaiman A Alghunaim, Ernest K Ryu, Kun Yuan, and Ali H Sayed. Decentralized proximal gra- dient algorithms with linear convergence rates. IEEE Transactions on Automatic Control, 66(6); 2787-2794, 2020.
Needet Serhat Aybat, Wang, Tianyi Lin, and Shiqian Ma. Distributed linearized alternating direction method of multipliers for composite convex consensus optimization. IEEE Transactions on Automatic Control, 63(1):5-20, 2017.
MV Balashov and RA Kamalov. The gradient projection method with armijo's 's step size on mani- folds. Computational Mathematics and Mathematical Physics, 61:1776-1786, 2021.
Nicolas Boumal, Pierre-Antoine Absil, and Coralia Cartis. Global rates of convergence for noncon- vex optimization on manifolds. IMA Journal of Numerical Analysis, 39(1):1-33 2019.
Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on a graph. SIAM review, 46(4):667-688 2004.
Shixiang Chen, Alfredo Garcia, Mingyi Hong, and Shahin Shahrampour. Decentralized riemannian gradient descent on the stiefel manifold. In International Conference on Machine Learning, pp. 1594-1605. PMLR, 2021.
Francis H Clarke, Ronald J Stern, and Peter R Wolenski. Proximal smoothness and the lower-c2 property. J. Convex Anal, 2(1-2):117-144, 1995.
Yu-Hong Dai and Yaxiang Yuan. A nonlinear conjugate gradient method with strong global con- vergence property. SIAM Journal on optimization, 10(1):177-182, 1999.
Kangkang Deng and Jiang Hu. Decentralized projected riemannian gradient method for smooth optimization on compact submanifolds. arXiv preprint arXiv:2304.08241, 2023.
Persi Diaconis and Daniel Stroock. Geometric bounds for eigenvalues of markov chains. The annals of applied probability, pp. 36-61, 1991.
Alan Edelman and Steven T Smith. On conjugate gradient-like methods for eigen-like problems. BIT Numerical Mathematics, 36(3):494-508, 1996.
Alan Edelman, Tomás A Arias, and Steven T Smith. The geometry of algorithms with orthogonality constraints. SIAM journal on Matrix Analysis and Applications, 20(2):303-333, 1998.
Sukru Bure Eryilmaz and Aysegul Dundar. Understanding how orthogonality of parameters im- proves quantization of neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Reeves Fletcher and Colin M Reeves. Function minimization by conjugate gradients. The computer journal, 1(2):149-154, 1964.
Roger Fletcher. Practical methods of optimization. John Wiley & Sons, 2000.
Magnus Hestenes, Eduard Stiefel, et al. Methods of conjugate gradients for solving linear systems. Journal of research of the National Bureau of Standards, (9(6):4094434 1952.
10

---

Published as a conference paper at ICLR 2024
Lei Huang, Xianglong Liu, Bo Lang, Adams Yu, Yongliang Wang, and Bo Li. Orthogonal weight normalization: Solution to optimization over multiple dependent stiefel manifolds in deep neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Nocedal Jorge and Wright Stephen. Numerical optimization. Spinger, 2006.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist/, 1998.
Y Liu and C Storey. Efficient generalized conjugate gradient algorithms, part 1: theory. Journal of optimization theory and applications, 69: 11911199777 1991.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1):48-61. 2009.
Angelia Nedic, Asuman Ozdaglar, and Pablo Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE Transactions Automatic Control, 55(4))922-938, 2010.
Angelia Nedić, Alex Olshevsky, and Michael Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5)9533-97, 2018.
Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87, Springer Science & Business Media, 2013.
Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
Elijah Polak and Gerard Ribiere. Note sur la convergence de méthodes de directions conjuguées. Revue française d' inforrattqque et de recherche opérationnelle. Série rouge, 3(16):35 43, 1969.
Boris Teodorovich Polyak. The conjugate gradient method in extremal problems. USSR Computa- tional Mathematics and Mathematical Physics, 94):94-112, 1969.
Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization. IEEE Trans- actions Control of Network Systems, 5(3):1245-1260, 2017..
Haroon Raja and Waheed U Bajwa. Cloud k-svd: collaborative dictionary learning algorithm for big, distributed data. IEEE Transactions on Signal Processing, 64(1):173-188, 2015.
Wolfgang Ring and Benedikt Wirth. Optimization methods riemannian manifolds and their ap- plication to shape space. SIAM Journal on Optimization, 22(2):596-627, 2012.
Hiroyuki Sakai and Hideaki liduka. Hybrid riemannian conjugate gradient methods with global convergence properties. Computational Optimization and Applications, 77:811 1-830, 2020.
Hiroyuki Sakai and Hideaki liduka. Sufficient descent riemannian conjugate gradient methods.
Journal of Optimization Theory and Applications, 190(1):130-155)) 2021.
Alain Sarlette and Rodolphe Sepulchre. Consensus optimization on manifolds. SIAM journal on Control and Optimization, 48(1):56-76, 2009.
Hiroyuki Sato. Riemannian optimization and its applications, volume 670. Springer, 2021.
Hiroyuki Sato. Riemannian conjugate gradient methods: General framework and specific algorithms with convergence analyses. SIAM Journal Optimization, 32(4):2690-271) 2022.
Hiroyuki Sato and Toshihiro Iwai. A new, globally convergent riemannian conjugate gradient method. Optimization, 64(4): 100031,,,1 2015.
Suhail M Shah. Distributed optimization on riemannian manifolds for multi-agent networks, arXiv preprint arXiv: 11t.:1111.1116666 2017.
Wei Shi. Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin. On the linear convergence of the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(7):1750- 1761, 2014.
11

---

Published as a conference paper at ICLR 2024
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: An exact first-order algorithm for decentral- ized consensus optimization. SIAM Journal on Optimization, 25(2):944-966) 2015.
Steven Smith. Optimization techniques on riemannian manifolds. Hamiltonian and Gradient Flows, Algorithms and Control, pp. 113-136, 1995.
Eugene Vorontsov, Chiheb Trabelsi, Samuel Kadoury, and Chris Pal. On orthogonality and learn- ing recurrent networks with long term dependencies. In International Conference Machine Learning. pp. 3570-3578. PMLR, 2017.
Lei Wang and Xin Liu. Decentralized optimization over the stiefel manifold by an approximate augmented lagrangian function. IEEE Transactions Signal Processing, 70:3029-304| 2022.
Haishan Ye and Tong Zhang. Deepea: Decentralized exact pea with linear convergence rate. The
Journal of Machine Learning Research, 220):10777-1100000 2021.
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1854, 2016.
Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H Sayed. Exact diffusion for distributed opti- mization and learning -tarttattt i: Algorithm development. IEEE Transactions Signal Processing, 67(3):708-723, 2018.
Jinshan Zeng and Wotao Yin. On nonconvex decentralized gradient descent. IEEE Transactions on signal processing, (6284)22844 2018.
Xiaojing Zhu. A riemannian conjugate gradient method for optimization on the stiefel manifold. Computational optimization and Applications, 67:73-110, 2017.
Xiaojing Zhu and Hiroyuki Sato. Riemannian conjugate gradient methods with inverse retraction. Computational Optimization and Applications, 77:779-810, 810, 2020.
12

---

Published as a conference paper at ICLR 2024
A
PROOFS FOR LEMMA 1
Proof. Since grad f((x) = Pr.M((Vi(z)) we have
Igrad f((x) grad f((1))l = -VA))
- PPMM
|POM (Vf((z)) PI.M (VS+()) + (PIM Pr,M (VS(V))
IPT.M (Vf(()) [P.
- (VA()))
(23)
< (z) V/((V++++ (Pr.M - PP,M (VA(U))
[V) - Vf((i) + +2,
< 11++2, 2L/)|== v/l,
where, by 6). the third inequality uses
Pr.M fi())) PI,M (Vi())))
1 (x Vf((y) + V 2) V V
2 (1 ((x v) V + (x- (x- -) + (1 3) (v vv) Vf() 1) (24)
52 (2||=1| || y|1 | + 2||x-~111 - - -V Illll)
$2/ - Ul [(al( s
max yESt(d.r)
V - yl = 2-, - y/l
The proof is completed.
B LINEAR CONVERGENCE OF CONSENSUS ERROR
Let us first present the linear convergence of consensus error. For the iteration scheme 21,4+1 PM (E Wijzza + ass)i.) where ag 0 and Thik E M, the following lemma yields that, for X2 in the neighborhood N, the iterates X also remain in this neighborhood N.
Lemma 2 Let Fi,4+1 = PPM [E== W1yaza owTL)) On the basis of Assumption I if xx
N (x: ||0 x||| 7/2), ||m, S C. 0 <a S 1(1-2), and 1 > [1080
(1112)
with
AvnC
Ç = max,, ||. 1/1. then
W WO + oxal E UM(()), 1= 1, n,
(25)
|10411- - -x+tll S 2/
(26)
Proof. Since X E N, we have
1
| Fzt1ll < ||
Fzll 5
|
Fall
i=1
PM
W Wo + axeTiik
- PM (ite)
1
Wh TyJ + a..Ti 2x
<
2 7
7
13

---

Published as a conference paper at ICLR 2024
where the third inequality uses (q. and the fourth inequality yields
11
W 1.. + o. - 8k
Σ
W
Fi 2x
+ +llammlll
1=1
Wi 1
(f (xx)
+axC
/=1
W
|| $x + asc
1 n
an S Viois azC S 7(1-7)
max
W
2
where the fourth inequality uses that |æ sx S トー || and the fifth inequality follows from the bound the total variation distance between any row of
xi,x S (Dng & Hu 2023
W and 1 I (Dicconis & Stroock 1991 Boyd et al. 2004). For any i E [n], since Fg E M and R. Y E (0, 1), we have
Σ Wig + ouTli. Is
S
W Wajaa + 0u77i, In + 11 Tz
7(1 7)
1 2 3-
The proof is completed.
In Lemma 2 the search direction 77, is required to be bounded. Let 1) = 0, then consider the convergence of consensus error.
Theorem (Linear convergence of consensus error). Let Ji = PM (E W W On the basis of Assumption max { {1ogo,(11 (1 (1-7)) r)],
Xx N (x 1 5 7/2) and 2
logoz
T( A
). then the following linear convergence with rate
d1/(1 7) 1 holds
a2 -1x0 1- ||x: - xx
|xx+1 - xx+1ll 1
||ā0 - Roll s & and x E N for all & 2 0 holds, then it holds that Proof. According to Lemma
W Um(()) i= n.
Let Px) = [PM((1)T ... Pm((x) then with the iteration scheme 21,4+
PM EE=n WiJaz,)) we have
|x - 8++1ll S |x] - 8 = PM (W'xx) - PMr (8x))1
1
| Xx
E41 =
|I @ (1)) xx - xx
[(w- |
1 1,
T
ld
(xx
(27)
1
o2 |x *+11 ll
o 1x - xxll.
where the second inequality uses Eq.
11]. The proof is completed.
14

---

Published as a conference paper at ICLR 2024
On the Stiefel manifold, by utilizing the 1-proximally smooth property of projection operators, establish the locally linear convergence of consensus error with a rate / -11--1 y). where can be any positive integer, which is consistent with the cases in the Euclidean space (Nedic et al. 2010 Nedić et al. 2018
C CONVERGENCE OF EACH AGENT
Lemma In Algorithm with 81,441 13 the strong Wolfe conditions in Eq. (8) and 19. with < < C2 < 1/2, for each 2 0. If
FR in Eq. 16 and Eq. 22 assume that on satisfies
grad fz( + for each O, then Ti,k as descent direction satisfies
(grad (.( Mikklaa Iggrad f((11,,))
1 202
(28)
02
Proof. For ease of notation, we denote gi,k := grad fi (Ii,k)) When 1: 0, 78.0 = 99,0 the initial condition and have
(gr, 11,0)
(9 9:0)
119,,0 22.0
119,0
Hence, Eq. (28 holds. Supposing that n4 is a descent direction satisfying Eq. (28) for some
with will prove that 7,,4+1 is also a descent and satisfies Eq. (28) in which is replaced with k 1, Based on Eq.444) and Eq. we yield
(BINTI, IlA+1 Ba 1441PM PT PIEMIIM
Ei= W WigTin))
(0i,++1, (16+11,7,4++// 71.+1))
199 1l
119 1122,111
(29)
gi,tt,, P Presa M EE=n Wig
F1,+11
11 11
Similar to (Sato 2022). the assumption in Eq. 20 and the strong Wolfe condition in Eq
yield
gi,++1, Pr Preceti M
Wiy
(gi, (1. = cc2 (li,ks (i.k) (30)
11,k-1
follows from Eq.22 and Eq. (30 that
-1 C2 (g Th.k)a
(g.,t11 Mot1)aeer
(gr,kr 1h.
-1 C2
11 112.
From the induction hypothesis in Eq. 28 i.e., (gi.k) mikk) / 11g. 2 -(1 - c2)= and the assumption C2 > 0, we finally obtain the following inequality
(gi,+1, Th,4+)
222 202
02
11 1
1 C2
which also implies (gr,k-1, 71..1),... <
0. The proof is completed.
Subsequently, we proceed the convergence property each agent. The proof below is based on the Riemannian version given in Sato 2022).
Theorem 3 In Algorithm with 3 -t-FF FR 1iki1
Eq. 16 and Eq. (20), assume that or satisfies
the strong Wolfe conditions Eq. 78) and Eq. 19
with Ci c2 < <T/2, for each 2 0. If f is
15

---

Published as a conference paper at ICLR 2024
bounded below and is of class C¹, and the Riemannian version (Ring & Wirth 2012 Sato & Iwai 2015) of Zoutendijk's Theorem (Noceaal & Wright 1999) holds, then we yield
lim inf
|| grad
fe(2a)))lz., ft = O, i= i=1.-. 1. n.
(31)
1-0000
Proof. We denote Pi.k grad ( again. If gi holds for some kn, then we have Br E4.,
and ko 0 from Eq. 16) and Eq. (1), which implies I1,to+1 PM (Σ)=) W1f Based
on Theorem 2 the consemsus error converges such that 21,8o+1 - Tio holds. Thus, we obtain gi.k for all Ko so that Eq. 31 31 holds.
We next consider the case in which gi.k # 0 for all & 2 O. Let fi, be the angle between -i. and k i.e.
kg (h.k) oi.
cos 0z,2
(32)
|| Fi.k lxck I
1195 (.s.lla,, Na. 11 1la
It follows from Eq. (2 and Eq. 28 that
cos 01, Z 1 1-202 1199,
(33)
C2 |1
Since the search directions are descent directions from Lemma with Eq. (33)
Zoutendijk's Theorem together
yields
1 Zick
< 00.
(34)
Combined Eq. (28) and Eq. (0) we have
n
gi Prey..M
W Winnia--
02 1)
C2
11
11
02
(35)
Using 16. Eq. 20 and Eq. 35), we obtain the recurrence inequality for ||
2
-9t.k | + Bi..Prrn Proma M Σ
W WiyTgik-1
2
< 11
+ 2,i,0
giiks PT Pre
Wt Mi
+ Br
Pre
Σ Wij Mj.k
202
< $119a1122,
+
3i
|1gi.k
1122 11,,,-.,
+ S3. |1 1122.211
1- C2
202
101.
BB Ilaaa-
62
|11); 112,0-1
(36)
where
(1+ 02) 02) > 1. Note that assume in the second inequality, for each A
1.
that
Σソ=1 Wip73,--1
1 holds, which is similar to Formula (4.28) in Sato
16

---

Published as a conference paper at ICLR 2024
2021I.
We can successively use Eq. (3) with Eq. as
Imallee
(lonalleen S. 119sx=11 11la,-11- +.. 87, 1 ...6p.2 11 (0n112,,1) P ... f611 Il
=c =ellgialles. (I19aal 11a 12 ..... 11,., (1.11 + 119..el1 1
<ellgix
Σ 11ghs 1=0
(37)
We can prove Eq. (31) by contradiction. We first assume that Eq. 31) does not hold. Then there exists a constant C 0 such that ll,,,ll... 2 C. > 0 for all &: 2 0 because we also assume Ii.k # 0 for all 2 at the same time. Consequently, we have Σø=o 1l9..112.. S C + 1). Hence, based on Eq. 37.. the left hand side of Eq. is evaluated as
|
1
ckkll
k=0
which contradicts Eq. (34). The proof is completed.
Global convergence
Linear convergence of consensus error
Convergence of each agent
Lemma
Lemma 2
Lemma
Lemma
Theorem 2
Theorem
Theorem
Figure 5: An overview of the proofs.
D GLOBAL CONVERGENCE
overview of this paper shown the Figure We now investigate the uniform boundedness of ||m|] in the following lemma.
Lemma 4 Let {xx} be the sequence generated by Algorithm
7 Suppose that Assumptions
and
hold. If xy E N. ||B I C. 0 < ak < min 1-7 7(1-2)
"L," 40 }. and 2
loga. (2)xx) [ogo. (Bvie) [Iog., (2(1-))
}}.
max
it follows that for all k, X E N
and
|m $ 2Lg
Vi E [n]]
(38)
Proof. We prove it by induction on both [| ll and || - #xll- Based on Assumption 2 we have grad fe (xx,) < Ve ( Lj < Lg due Lg L + 2L, Lj. Then have
[ooll = grad fe (xx0) < by for all [n] and | Foll 1.. Suppose for some k 2
17

---

Published as a conference paper at ICLR 2024
that ||7 I g and || Exll $ 22. Since || I 2Lg and an 2(1-2) it follows from
Lemma that
1 Whyya + OnTER Um(1), i= 1= ,,, || Txt1ll S 2.
Then, we have
MM, grad fi (2i,a)ll
B PI PreINet M
Wi Wim
(grad fo (IL,K1)) grad fi (ILR))
Bitt+
W 1b.k
+ +lggrad So (I11,441) grad Si (I11,))
C
W
+ Lg || FiAll
(39)
j=1
Co. / max | + Lg 1| - I.AAll
Co max || + Lg 7
Σ Wij - !
n 24,4 + cusTi
Colvn n ap Lg
Lg
max ||m,, + 1 1-
max m + 2 L S 2 Lg + 2 Ly Lg. 4
where the second inequality uses Lemma and the fourth inequality utilizes Eq. [|r, & [1,.+1 + grad fs (II, + l|grad fs (Ir,))) < 2Lg. The proof is completed.
Hence,
With the above lemma, we can elaborate the relationship between the consensus error and step size.
Lemma 5 Let {xx} be the sequence generated by Algorithm| ! Suppose that Assumptions 7 and
hold. If X Ns [| S 2Lo 1 |logo (1 [ and 0 Ork 81,
2(1-2), follows that for all
k. X2 E N and
1
X xol12 S C (1 y1- a.
(40)
n
Proof. Since ll grad fo (21,x) || s Lg and |1:0 - Toll S 2/,, it follows from Lemma that for any k O, have
"
Σ
w Wfz + ootha Um(7), i 1=
Let PM (x)T (PM(21) T (xM( By the definition of xx+1 and Theorem 2 then yield
[x x1+1/| S | -Xxll
PM (W'x,, Xx + aanss -PMr (Xxx
<
W''x + 0..7 -xall
(41)
02 |
xx1l
VnaxLo.
where the first inequality follows from the optimality of Re+1, the second inequality uses Eq. and the third inequality utilizes the fact that [ma]] < /
18

---

Published as a conference paper at ICLR 2024
Let Pt of where 0 Pe < 1, it follows from Eq.
(2 that
2
| X S Pr. || - -xxll
1 1-9 Vnean
(42)
S Pi k+1 ||x0 xoll + 2//iL
Σ
a
Pi
7
1=0
Let 1/k
-x Vnaa
For a positive integer K < k. follows from Eq. that
k
Tig aR yk+1 S PElh + 1- 0x++1
S Pt
k+1-K
yK + 1-9 1=0
Lg Σ
a
01+1
has that yo 22//au O Since limg-to 0c+1 1, there exists sufficiently large K such that as/ORt1
Since ag (g)Lg) and ||00 xull I 1/2 Vnn,,
4k K. For 0 s
ak
& K, there exists some C' > 0 such that v I C' (i- Lg where C' is independent of Lg and n. For k K, one has that v S C (( Lg where C 2C" + (1 (1-m)) Hence, we get Kt &
C TT= l for all l 2 0, where C 0 ([-p.))) The proof is completed.
D.1 PROOFS FOR THEOREM
Proof. We have the following inequality:
grad f (*x)11
1 Σ
grad fe(vi,)) + grad f(īx)
grad fe(
i=1
2
grad (I(
+2
grad f(xx)
grad fo (xi,K)
n
x2
(43)
<
grad f((,kk))
Igrad f((Tx) grad (I
7
1
2L
<
grad fz(,,.))
g
|| Fssk
n
i=1
i=1
2L
2
grad (1(21,,)
||X - xx112
2=1
where the third inequality uses Lemma
Since lim inf grad f((,,,)) 0 based on The-
1 orem 2 and | xx|1² < nC' { L a based on Lemma it follows from lim Og. = that
2
lim grad f(xx)11 2
1 n Σ
grad f((t;,))
+2C
71 Lg 0.
1
The proof is completed.
19


Reviews:
[{"review_id": "bPyzhnKKkp", "reviewer": "Reviewer_hbTT", "summary": "This paper presents a decentralized Riemannian conjugate gradient descent (DRCGD) algorithm for distributed optimization, and proves the global convergence of the algorithm. Compared with existing state-of-the-art algorithms, DRCGD uses a projection operator that searches the direction instead of retraction and vector transport, thus reducing computational costs. Through the simulation of eigenvalue problem, the paper shows that DRCGD has better performance than state-of-the-art algorithms.", "questions": "1. What is the definition of $x_{x}$ in Definition 3 (ii)?\n\n2. It seems like there are many assumptions of the parameters such as $\\alpha_{k}$. Are these assumptions easy to satisfy?\n\n3. In this paper, the decreasing step size is used in the convergence proof, while the fixed step size is used in the simulation. Does this difference affect convergence?\n\n4. What is the significance of the eigenvalue problem used in the simulation in real life?\n\n5. In general, since the problems solved are the same, the convergence result of the distributed algorithm should be independent of the structure of the graph if the assumptions about the graph are satisfied. In Figure 3 of the simulation, the same algorithm seems to converge to different solutions under different graphs. Why did this happen?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "originality and significance: This paper has good originality and significance since it presents the first decentralized Riemannian conjugate gradient descent (DRCGD) algorithm for distributed optimization and proves the global convergence of the algorithm.\n\nquality: The proposed algorithm is supported by solid theory and verified by simulation.\n\nclarity: The overall narrative logic of the article is clear.", "weaknesses": "1. There is still room for improvement in the clarity of the proof. Some symbols that appear in the convergence analysis section of the text, such as $g_{i,k+1}$, $\\mathcal{N}$, and $C$, are not defined in the text.\n\n2. It seems that there are some assumptions about the step size $\\alpha_{k}$ that are not mentioned in Assumption 3 about $\\alpha_{k}$ in the body of the proof, such as the assumption about $\\alpha_{k}$ in Lemma 2. This leads to unclear assumptions about $\\alpha_{k}$.\n\n3. The measures mentioned in the simulation should converge towards 0, which is not well demonstrated in the experimental results. For example, the measures in Figure 3 tend to be constant after it drops to a certain level. This does not support the theoretical results very well.\n\n4. The definition of doubly stochastic matrix seems to be $\\sum_{i} x_{ij}=\\sum_{i} x_{ij}=1$, which is different from the definition in Assumption 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "reK3O6pmRk", "reviewer": "Reviewer_86eb", "summary": "This paper suggests an extension of conjugate gradient on Stiefel manifold for distributed setting and provides convergence guarantees for this algorithms. The approach is based mainly on the Xiaojing Zhu's original papers", "questions": "1. Typo in \"Lemma 3 In Alogrithm\"\n2. What about time-varying case? Conidering the case of time-varying graph would be important for all-around extending CG for decentralised setting.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The setting of decentralized optimisation is crucial in applied optimisation, and extending one of the most practically efficient algorthms to it is topical. Riemannian generality here requires carefull trheoretical justifications and proper choice of tools to prevent big computational complexity. Paper indeed propose a good solution for solving optimisation problems on Stiefel manifold.", "weaknesses": "Empirical study is not comprehensive: there was not presented a comparison of the proposed approach with alternatives. Besides, form of convergence guarantees is not exhaustive, because the rate of the convergence is not established. Theoretical framework is mostly inherited from Zhu's original papers, but that analysis does not allow providing guarantees on convergence rate, so does not this paper, which means that there were no significant extending of that framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "RpMaS19mBD", "reviewer": "Reviewer_yaab", "summary": "The conjugate gradient method, a critical first-order optimization technique, typically exhibits faster convergence compared to the steepest descent method and demands significantly lower computational resources than second-order methods. Nevertheless, despite extensive research on various forms of conjugate gradient methods in Euclidean spaces and Riemannian manifolds, there has been limited exploration of such methods in distributed scenarios. This paper introduces a novel approach called the Decentralized Riemannian Conjugate Gradient Descent (DRCGD) method, designed to minimize a global objective function defined on the Stiefel manifold. This optimization problem is distributed among a network of agents, each associated with a local function, with communication occurring over a connected, undirected graph. Global convergence of DRCGD over the Stiefel manifold is proved. Numerical experiments demonstrate the advantages and efficacy of the DRCGD approach.", "questions": "- Assumption 1: usually a doubly stochastic matrix is defined with positive elements and row and columns that sum to 1. Can you comment how does it relate to your definition?\n- Section 4.1: \"The Riemanian gradient step with a unit step size, i.e., ...\" is it a unit step size or a null/zero step size?\n- Assumption 3 (iii): what is $T_{alpha_k\\eta_{i,k}^R$ ?\n\nProofs:\n- Lemma 1, eq (24): how do you get second and third inequalities. For me, there is something wrong here.\n- Theorem 2 is independent from the conjugate gradient. Is it new or is it a known result from a different paper?\n- Theorem 2 assumes that $\\eta_{i,k}=0$. In the proposed algorithm, you jointly do a gradient descent and average the iterates of the different nodes, hence $\\eta_{i,k}\\neq 0$. Can you comment this?\n- After eq (31), you mention that $x_{i,k_0+1} \\to x_{i,k_0}$. I don't understand at all this limit. Is it a mistake?\n- Second inequality in eq (36), can you explain how do you get it?\n\nTypos:\n- Definition 3: (ii) $x_x$ is $0_x$.\n\nNotations:\n- $P_{St}$ and $P_M$ are the same.\n- Section 4.2: $g_{i,k+1}$ is not introduced.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well written: basic definitions of optimization on Riemannian manifolds are recalled and the proposed algorithm is well explained. Furthermore, the latter is quite simple and hence has a great practical interest. Classical conjugate gradients on Riemannian manifolds have much faster convergence compared to the plain Riemannian gradient descent. Hence, proposing a decentralised Riemannian conjugate gradient descent can be well received by the community. Moreover, the global convergence of the proposed algorithm is proved whereas it is far from being trivial. Finally, numerical experiments show a practical interest to the proposed method.\n\nThe paper is overall of great quality.", "weaknesses": "The claim 2 in the introduction as well as the section 4.1 are misleading. Indeed, the authors mention they don't use retraction or vector transport to reduce the computation. However, they use the orthogonal projection onto the Stiefel manifold, which is a retraction, and the othogonal projection onto the tangent space, which is a vector transport (see \"Optimization on matrix manifolds\" from Absil et al. 2008). This claim should be removed.\n\nIn section 4.2, the equation (20) is not clear since $T_{alpha_k\\eta_{i,k}^R$ is not defined. Hence, it is hard to appreciate if this hypothesis is reasonable or not. Same thing for assumption 3 (iii).\n\nThe paper lacks an overview of the poof to get the global convergence. The different proofs are long and technical and an overview would help the reader.\n\nThe numerical experiments section lacks the presentation of DRDGD and DPRGD. It would be interesting to better understand the differences with the proposed method.\n\nSeveral passages in the proofs are unclear. See the questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (poster)