Decentralized Riemannian Conjugate Gradient Method on the Stiefel Manifold

Thank you for your valuable suggestions, and we have corrected the typos and inappropriate notations in the modified version.

1. [This claim 2 should be removed] Indeed, we don't use retraction directly. However, we still need to bound the projection operator using retraction and vector transport based on Eq.19 and Eq.20. Thus, we must give the complete claim of retraction and vector transport.
2. [$T_{\alpha_k \eta_{i,k}}^R$ is not defined] Actually, we give its definition in Example 1, which is the vector transport constructed by retraction.
3. [The paper lacks an overview of the poof] Thanks for your suggestion. We have added an overview of the proofs in Figure 5 in the modified version.
4. [The experiments lacks the presentation of DRDGD and DPRGD] In fact, the presentation of DRDGD and DPRGD is shown in Figure 4. And their results are very close.
5. [Doubly stochastic matrix] For example, if we have 4 agents with ER $p=0.3$ graph, then the matrix satisfies $W=\begin{bmatrix} 1/3 & 1/3 & 0 & 1/3 \\\ 1/3 & 2/3 & 0 & 0 \\\ 0 & 0 & 2/3 & 1/3 \\\ 1/3 & 0 & 1/3 & 1/3 \end{bmatrix}$. If we have 4 agents with Ring graph, then the matrix satisfies $W=\begin{bmatrix} 1/3 & 1/3 & 0 & 1/3 \\\ 1/3 & 1/3 & 1/3 & 0 \\\ 0 & 1/3 & 1/3 & 1/3 \\\ 1/3 & 0 & 1/3 & 1/3 \end{bmatrix}$.
6. [Is it a unit step size] It follows from the setting of DRDGD and DPRGD that a unit step size means the coefficient before $\sum_{j=1}^n W_{i j}^t x_{j,k}$ is 1.
7. [Assumption 3 (iii): what is $T_{\alpha_k \eta_{i,k}}^R$] It is a vector transport constructed by retraction, which is defined in Example 1.
8. [Lemma 1, eq (24): how do you get second and third inequalities] We miss a parenthesis in the second inequality, which has been corrected in the modified version. And $0 \leq \Vert x \Vert, \Vert y \Vert \leq 1$ is implicit in this proof.
9. [Is Theorem 2 new or is it a known result from a different paper] In fact, similar results have been given in [1], which we extended from retraction to projection operator and made it compatible with the conjugate gradient.
10. [Theorem 2 assumes that $\eta_{i,k}=0$] It's fine. Theorem 2 discusses the consensus error $\sum_{j=1}^n W_{i j}^t x_{j,k}$, and $\eta_{i,k}$ does not belong to the consensus error, so we consider setting it to 0. In particular, we still consider the role of $\eta_{i,k}$ in the part of global convergence (Appendix D).
11. [$x_{i,k_0+1} \rightarrow x_{i,k_0}$] There is no problem. It means that $x_{i,k_0+1}$ will no longer be updated and will remain at the previous point $x_{i,k_0}$ as the consensus error converges and the gradient approaches 0. A similar statement can be found in Theorem 4.2 based on [2].
12. [Second inequality in eq (36)] First, the second part comes from Eq. 35. Then, the third part is $\Vert \mathcal{P}\_{T\_{x\_{i,k}}\mathcal{M}}\left(\sum\_{j=1}\^n W\_{i j}\^t \eta\_{j,k-1}\right) \Vert \_{x\_{i,k}}\^2 \leq \Vert \sum\_{j=1}\^n W\_{i j}\^t \eta\_{j,k-1} \Vert \_{x\_{i,k}}\^2 \leq \Vert \eta\_{i,k-1} \Vert \_{x\_{i,k-1}}\^2$, where $\Vert \sum\_{j=1}\^n W\_{i j}\^t \eta\_{j,k-1} \Vert \_{x\_{i,k}}\^2 \leq \Vert \eta\_{i,k-1} \Vert \_{x\_{i,k-1}}\^2$ is a similar assumption followed with formula (4.28) in [2].

[1] Chen, Shixiang, et al. "Decentralized riemannian gradient descent on the stiefel manifold." International Conference on Machine Learning. PMLR, 2021.

[2] Sato, Hiroyuki. Riemannian optimization and its applications. Berlin: Springer, 2021.

Thank you for your efforts in improving the quality of our paper. In fact, in the framework of conjugate gradient, the convergence rate has not been established so far. Naturally, the decentralized version we derive from this framework can not provide the convergence rate as well. We guess the view inherited from Zhu's original papers is caused by the framework of the Riemannian conjugate gradient. Different studies revolve around geometric tools without affecting the theoretical framework of conjugate gradient, e.g., inverse retraction [1] and vector transport [2]. Specifically, we present a quite simple geometric tool (projection operator), and extend it to decentralized scenarios, which obviously makes a significant extension to unify the framework of conjugate gradient and decentralized optimization.

1. We have modified the corresponding typo in the modified version.
2. This is a very meaningful and interesting idea for the time-varying graph in decentralized CG. We also notice that there have been some recent works focusing on time-varying graphs, e.g., [3], [4], [5]. By reviewing these works, we find that this paper can be extended to time-varying cases because we have no additional requirements for decentralized settings. Of course, there are a large number of proofs to be considered that would go well beyond the scope of this paper and would be sufficient to form a new paper. We will consider this exciting setting in future work.

[1] Zhu, Xiaojing, and Hiroyuki Sato. "Riemannian conjugate gradient methods with inverse retraction." Computational Optimization and Applications. 2020.

[2] Sato, Hiroyuki, and Toshihiro Iwai. "A new, globally convergent Riemannian conjugate gradient method." Optimization. 2015.

[3] Rogozin, Alexander, et al. "An accelerated method for decentralized distributed stochastic optimization over time-varying graphs." IEEE Conference on Decision and Control (CDC). 2021.

[4] Saadatniaki, Fakhteh, Ran Xin, and Usman A. Khan. "Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices." IEEE Transactions on Automatic Control. 2020.

[5] Kovalev, Dmitry, et al. "ADOM: Accelerated decentralized optimization method for time-varying networks." International Conference on Machine Learning. 2021.

1. [Some symbols are not defined] Thank you for your valuable suggestions, and we have added the definitions of the corresponding symbols in the modified version.
2. [Some assumptions about step size are not mentioned] Indeed, the step size $\alpha_k$ should be bounded as the description of Lemma 2, and we have added this part to Assumption 3.
3. [The measures tend to be constant] In theoretical analysis, we require the step size to be infinitely close to 0. However, for a fair comparison with different methods in the experiment, we employ fixed step sizes, i.e., $\alpha_k=\frac{\hat{\alpha}}{\sqrt{K}}$ with $K$ being the maximal number of iterations. Obviously, this causes the measures only drop to a certain level.
4. [Doubly stochastic matrix] In our opinion, the definition in Assumption 1 puts forward higher requirements for a doubly stochastic matrix, including symmetry and eigenvalues, but it still meets the properties of a doubly stochastic matrix. Actually, the completely consistent definition is also given in Assumption 1 based on [1].
5. [Definition of $x_x$ in Definition 3 (ii)] It should be $0_x$, and we have corrected it in the modified version.
6. [Are these assumptions easy to satisfy] Many assumptions are built into conjugate gradient, e.g., the Armijo condition and strong Wolfe condition, and their purpose is to theoretically prove the convergence of conjugate gradient. All assumptions only ensure that the algorithm converges in the worst case, and they can be satisfied from the view of practical convergence.
7. [Does this difference affect convergence] The fixed step size causes the measures approach to be constant (very close to 0) after it drops to a certain level, rather than continuously dropping as the decreasing step size.
8. [The eigenvalue problem in real life] The eigenvalue problem is a fundamental concept in linear algebra with widespread applications in various fields, including physics, engineering, computer science, and statistics. In the context of simulations and real-life applications, the eigenvalue problem is particularly significant for several reasons: (1) Eigenvalues are used in control theory to analyze the stability of control systems. (2) Eigenvalue decomposition is utilized in various algorithms for dimensionality reduction and feature extraction in machine learning. (3) Eigenvalue problems are foundational in spectral methods used in numerical simulations.
9. [The same algorithm seems to converge to different solutions] In practice, the proposed method indeed achieves convergence under different graphs, which shows that their convergence is indeed independent of the structure of the graph. However, different graph structures will cause different efficiency of information transmission, thus affecting the convergence trend.

[1] Chen, Shixiang, et al. "Decentralized riemannian gradient descent on the stiefel manifold." International Conference on Machine Learning. PMLR, 2021.