Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold
Authors: Yilong Song
Peijin Li
Bin Gao
Kun Yuan
Venue: ICML 2025 poster (2025)
Keywords: Stiefel manifold
distributed optimization
error feedback
retraction-free
Primary area: optimization->large_scale_parallel_and_distributed

Abstract: Optimization problems on the Stiefel manifold, ranging from principal component analysis to enhancing neural network robustness, are ubiquitous in machine learning. The Landing algorithm avoids computationally expensive retraction operations on manifolds, making it highly competitive for large-scale problems. This paper extends this method to distributed settings, introducing *EF-Landing*, the first retraction-free and communication-efficient algorithm for distributed stochastic optimization on the Stiefel manifold. By incorporating communication compression and error feedback, EF-Landing ensures convergence and constraint feasibility while significantly reducing communication overhead. We provide sharp convergence guarantees, demonstrating that EF-Landing achieves the same asymptotic linear speedup convergence rate as existing methods without communication compression. Furthermore, our analysis is highly versatile, applying to both deterministic and stochastic settings and encompassing algorithms based on gradient descent or momentum-based gradient descent. We also generalize EF-Landing to operate on block-wise Stiefel manifolds, enabling greater flexibility for structured constraints. Extensive numerical experiments validate our theoretical results.

Distributed Retraction-Free and Communication-Effccent Optimization on the Stiefel Manifold
Yilong Song'
Peijin Li
Bin Gao
Kun Yuan
Abstract
(PCA) (Hotelling, 1933) and Canonical Correlation Analy- sis (CCA) (Hotelling, 1936). Furthermore, recent research has demonstrated that incorporating additional orthogonal constraints in deep learning problems often improves the robustness neural networks (Arjovsky et al., 2016; Wang et al., 2020; Bansal et al., 2018). These insights underscore the importance of optimization on the Stiefel manifold in machine learning applications. Traditional methods typi- cally involve single computing node. However, state-of- the-art performance in modern tasks is often achieved using extremely large training datasets, necessitating efficient dis- tributed algorithms for stochastic optimization on the Stiefel manifold across multiple computing nodes.
Optimization problems on the Stiefel manifold, ranging from principal component analysis to en- ubiqui-
hancing neural network robustness, tous in machine learning. The Landing algorithm avoids computationally expensive retraction oper- ations on manifolds, making it highly compet- itive for large-scale problems. This paper ex- tends this method to distributed settings, introduc- ing EF-Landing, the first ctractioo-free and communication-effiiie algorithm for distributed stochastic optimization on the Stiefel manifold. By incorporating communication compression and error feedback, EF-I Landing ensures conver- gence and constraint feasibility while significantly reducing communication overhead. We provide sharp convergence guarantees, demonstrating that EF-Landing achieves the same asymptotic linear speedup convergence rate as existing methods without communication compression. Further- more, our analysis is highly versatile, applying to both deterministic and stochastic settings and encompassing algorithms based on gradient de- scent or momentum-bice based gradient descent. We also generalize EF-Landing to operate on block- wise Stiefel manifolds, enabling greater flexibility for structured constraints. Extensive numerical experiments validate our theoretical results.
This paper considers the following optimization problem across N collaborative nodes:
1 N min f(X)= XEReIp N
- BAAD) F(X:E.) (1a)
s.t. X
(1b)
where n 2 f((X) represents the objective function for each node i, and the random variable & corresponds the local data maintained by node i, following a local distri- bution D.. The constraint (Ib) can also be expressed as X E St(p, n)) in which St(p, n) == {X E Raxp X X Ip] is referred to as the Stiefel manifold. It is straightfor- ward to verify that the Stiefel manifold constraint (1b) is non-convex.
Numerous approaches can be directly extended to solve the distributed problem (1). One line of research employs Rie- mannian methods to iteratively move towards the desired solution, incorporating retraction operations to ensure feasi- bility on the Stiefel manifold (Edelman et al., 1998; Absil et al., 2009; Absil & Malick, 2012). However, retraction operations are computationally expensive, often requiring matrix inversion, matrix exponential calculations, or QR factorization. To address this bottleneck, another line of re- search introduced the retraction-fres Landing method (Ablin & Peyré, 2022), which relies solely matrix multiplica- tion and is particularly efficient on GPUs. In the Landing algorithm, iterates do not remain on the Stiefel manifold but gradually "land" (i.e., converge) onto it. This retraction -fee property makes the method highly practical for large-scale
1. Introduction
The Stiefel manifold, defined as the set of matrices with orthonormal columns, plays a crucial role in enhancing the dissimilarity between learned features in machine learn- ing. Many classical problems inherently require orthog- onal constraints, such as Principal Component Analysis
Peeking University "Academy of Mathematics and Systems Scienee, Chinese Academy of Sciences. Correspondence to: Kun Yuan <kunyuan pku.edu.en>>
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Distributed Retraction-Fies and Communication--Pfiieen Optimization on the Stiefel Manifold
optimization problems. For these reasons, this paper focuses on developing and analyzing distributed Landing algorithms to solve problem (I).
merit function bound, which serves as a foundational tool for algorithms utilizing lossy gradient estimates and may be of independent interest.
In distributed optimization on the Stiefel manifold, each worker transmits gradient matrices to a central server to update the model parameters. Given the substantial size of these gradient matrices, communicating them at every itera- tion incurs significant overhead. which hinders algorithmic efficiency and scalability. To address this issue, this paper explores communication compression techniques (Alistarh et al., 2017; Richtarik et al., 2021: Stich et al., 2018; Huang et al., 2022) to reduce overhead. Instead of transmitting full gradient or model matrices, these strategies communicate compressed matrices with significantly smaller sizes at each iteration. While communication compression has demon- strated both theoretical guarantees and empirical successes in unconstrained distributed optimization, no existing algo- rithms, to the best of our knowledge, have been developed for distributed stochastic optimization on Stiefel manifolds. Several key questions arise when developing algorithms:
Generalization to block-wise Stiefel manifolds. We extend our framework to a generalized setting where ma- trix variables are partitioned into blocks with wise orthogonal constraints. This enables greater flexibility for large-scale optimization with structured constraints. We develop cummunication-efficcee algorithms for this setting and provide convergence analysis, showing that the proposed methods retain the same theoretical guar- antees their non-block counterparts.
2. Related Work
Optimization on manifolds. Riemannian methods are clas- sical approaches for solving optimization problems on man- ifolds. The foundational principles of Riemannian gradient descent with retraction were established in (Edelman et al., 1998; Absil et al., 2009; Absil & Malick, 2012). Build- ing on gradient- based techniques, various algorithms and convergence results have been developed, including first- order methods (Zhang & Sra, 2016; Boumal et al., 2019), second-order methods (Absil et al., 2007; Qi et al., 2010), and accelerated methods (Liu et al., 2017; Ahn & Sra, 2020; Alimisis al., 2021). Stochastic optimization on manifolds has also been explored (Bonnabel, 2013; Tripuranení et al., 201 8), with further refinements presented in (Zhang et al., 2016; Zhou et al., 2019). On the other hand, retraction- free approaches primarily include methods based on penalty functions and augmented Lagrangian formulations (Xiao et al., 2021; 2022; Gao et al., 2019), as well as techniques that reformulate manifold constraints Lezcano-Casadee & Martinez-
Q1. Which components of the algorithm can be compressed to ensure convergence? Specifically, should we com- press the Euclidean gradient, Riemannian gradient, or gradient coupled with constraint penalty?
Q2. Is the error compensation strategy necessary for op- timization on the Stiefel manifold to maintain both optimality and feasibility?
This paper addresses these questions and introduces the first algorithm for
retraction-free and communication-effice distributed stochastic optimization on the Stiefel manifold. Specifically, we make the following contributions:
EF-Landing algorithm. We identify that compressing the Fuclidean gradient of each ((()) ensures both op- timality and feasibility. Furthermore, we demonstrate that error feedback mechanisms are essential for con- vergence, even in single-node settings. Building on these insights, we propose the EF-Landing algorithm for distributed stochastic optimization problem (1) on the Stiefel manifold with communication compression.
2019; Liu et al., 2024). Additionally, the Landing method, designed specifically for the Stiefel man- ifold, has been proposed and analyzed in (Ablin & Peyré, 2022; Ablin et al., 2024; Vary et al., 2024).
Distributed optimization. Distributed optimization has been extensively studied, with Distributed Gradient Descent (Tsitsiklis al., 1986) serving the representative method. To address the communication bottleneck of central param- eter servers, three main improvement strategies have been explored: decentralized communication (Lopes & Sayed, 2008; Shi et al., 2015; Nedić et al., 2017), lazy communi- cation (McMahan et al., 2017; Stich, 2019a), and commu- nication compression (Alistarh et al., 2017: Richtarik et al., 2021). Research on distributed optimization on manifolds remains relatively limited (Chen et al., 2021; Wang & Liu, 2022; Sun et al., 2024; Hu & Deng, 2024; Qu et al., 2024; Zhao et al., 2025; Zhang et al., 2024), including work such as (Sun et al., 2024) which incorporated the Landing algo- rithm with gradient tracking techniques, (Hu & Deng, 2024), which applied communication compression, and (Zhang
Sharp convergence guarantees. We provide conver- gence guarantees and establish convergence rates for EF-Landing. Our algorithm achieves the same asymp- totic linear speedup convergence rate as the vanilla Land- ing algorithm without any communication compression. Furthermore, our results are highly versatile. By select- our analysis applies
ing appropriate to both deterministic and stochastic settings, encom- passing wide range of algorithms based on gradient descent or momentum- based gradient descent. Notably, our established convergence rates also recover results for communication compression in unconstrained dis- tributed optimization. Our analysis is built upon a novel
2

---

Distributed Retraction-Fiee Frrec and Communication--Pfiiii Optimization on the Stiefel Manifold
al., 2024) which considered federated learning with local updates.
Definition 3.1 (Safe Region). Given some E (0,3/4) we define the safe region of Stiefel manifold as
Communication compression. Communication compres- sion significantly reduces the amount of information ex- changed during distributed optimization. These techniques mainly fall into two categories: sparsification methods, such as Rand-K and Top-K (Stich, 2019b; Wangni al., 2018) (0.8, and quantization methods, like QSGD and TurnGrad (Al- istarh et al., 2017; Wen et al., 2017). To further mitigate information distortion, error feedback techniques have been widely adopted (Richtarik et al., 2021; Seide et al., 2014; Karimireddy et al., 2019; Stich & Karimireddy, 2021), with (Fatkhullin et al., 2023) showing that incorporating momen- tum enhances the effectiveness of error feedback. Optimal compelxity with communicaiton compression has been ex- amined in (Huang et al., 2022; He et al., 2024).
St(p, n) = X Ruxp |X - 1 [
The intuition behind the Landing algorithm is that (XX) drives the iteration towards the optimal solution on the Stiefel manifold, while V.V(X) steers the iteration towards the Stiefel manifold constraint. The orthogonal- ity between these two terms ensures both optimality and feasibility as long as the algorithm converges.
3.2. Compressor and Error Feedback
Contractive compressor. This paper examines commu- nication compression using contractive compressors, with Top-K and Random-K K being commonly used examples (Wangni et al., 2018; Stich, 2019b).
3. Preliminary
Definition 3.2 (Contractive Compressor). A compressor C' is defined as contractive compressor it satisfies
Notations. Given a matrix X E Rmxx,, let || de- note the Frobenius norm, with the corresponding inner product defined as (X,Y) == Tr(X TY). For square matrix M Rax, the symmetric and skew-symmetric components given by sym(M) := [M + M) and skew(M) == (M - M), respectively.
The [I((() -x1)) S S - x AX R"XP,
x112]
where (0, 1] is the contractive factor. The expectation is taken over the randomness of the compression operator C.
Error feedback. Consider the unconstrained problem:
3.1. Landing Method
Descent direction. The Landing method (Ablin & Peyré, 2022; Ablin et al., 2024) utilizes both the Riemannian gradi- ent and a penalty term to enforce constraints while eliminat- ing the need for retraction operation. The descent direction of Landing method is
min XER
f(X).
(4)
The error feedback method (Richtarik et al., 2021) to solve the above unconstrained optimization problem
X X y-kk y y = + CC(F
(5a)
A(X) (X) (X)+ AVA(X), where gX)df(X) = skew (Vf(X)xTTx X,
(2)
(5b)
where y the compressed approximation of the gradient V)((*), and C(-) satisfies Definition 3.2. The intuition behind error feedback is straightforward:
(W(X)=X(xx) x()
Eclly k+1 ()(x++))]1
The first term, (X), represents the Riemannian gra- dient the Stiefel manifold St(p, n) with respect to the canonical metric (Gao et al., 2022), when X satisfies the manifold constraints. The second term, V.N(X), denotes the gradient the penalty term A(X)= == I| 1 where the penalty parameter > controls its weight.
(5b) FcllI vs(x*+1) "Oy*-VS(X**I)))
$1 -
Suppose Vf(x*) + Vf(X*) as l + co, where X* is a stationary solution to problem (4). The above inequality implies that y* converges (X*)) Combined with (5a), this guarantees that X X under compression, thereby validating the effectiveness of the error feedback method.
Landing. With descent direction (2), Landing method is:
x++ x >A(X*),
(3)
where is the step size. Rather than enforcing an exact constraint at each step, the Landing method only requires the iterations to remain within the neighborhood of St(p, n). i.e. the safe region defined as follows (Ablin et al., 2024):
4. EF EF-Landing Algorithm
In this section, we introduce EF-Landing, the first dis- tributed Landing method incorporating Error Feedback.
3

---

Distributed Retraction- Free and Communication--fiiceenl Optimization on the Stiefel Manifold
ertor feedback VX(X)
VX(X). ). The most straightforward approach is directly compress VX()), i.e., 9 C(V where C(-) is the contractive compressor satisfying Definition 3.2. However, we observe that such vanilla compression may lead to non- convergence, even in the case of the single-node Landing (2)-(), The main intuition is that the tangent space of the Stiefel manifold and the compressed gradient may be- come orthogonal, causing the iteration to stagnate. Figure I provides schematic diagram of this phenomenon, while Proposition 4.2 provides the corresponding rigorous formu- lation.
c(V)(x))
gradf(X) (X)
(after céfor feodback)
St(p,n) n)"
Stíp. n)
Figure 1: The necessity of eπror feedback
Proposition 4.2. There exists an L-smooth objective func- fion f Rxx + R, a contractive compressor satisfying Definition 3.2, and an initial point X E R== such that the following update scheme:
4.1. Compression on Euclidean Gradient
In the error feedback method for solving the unconstrained optimization problem (4), compressing the gradient (X) is sufficient ensure convergence. Given that the Landing method can be expressed in a descent form (3), natural question arises: should we mimic recursion (5) and com- press (X) for EF-Landing?
g -= CC((((()).
x(X:g) = grad(g) AV)()))
X ~A(:g)
We find that compressing A(X) does not necessarily guar- antee convergence. Note that the key factor ensuring the effectiveness of the Landing method (2)-(3) the orthogo- nality property between the Riemannian gradient grad and the penalty gradient V.((X), given by
results in the algorithm getting stagnant and and failing to con- verge to the stationary solution. (See proof in Appendix A.2.) Remark 4.3, Proposition 4.2 suggests that vanilla gradient compression results in con-convereence for optimization the Stiefel manifold, even in deterministic and single- node setting. In contrast, for unconstrained deterministic optimization, vanilla gradient compression is guaranteed to converge under the same conditions (see proof in Ap- pendix A.3). This highlights the additional challenges in- troduced by the Stiefel manifold constraint in algorithm design.
(g)adf(X), (V)(X)) = =0,-
E
(6)
This orthogonality ensures that if [|A(X) 1/-- - 0, then both [lgrad (X)]l - O and [X))(()) - 0 hold, guaran- teeing optimality while preserving feasibility on the Stiefel manifold. However, it remains unclear whether orthogonal- ity (6) is preserved after compressing A A(X).
Remark 4.4. Error feedback technique can be motivated by diverse considerations. similar work (Karimireddy et al., 2019) discussed the necessity of error feedback in the context of signSGD compressor (Bernstein et al., 2018). However, this analysis remains orthogonal to scenario, as signSGI represents specific type of compressor, and it can be proved that signSGD does not satisfy contractive compressor Definition 3.2. Consequently, the rationale for employing error feedback varies across different settings. Our theoretical analysis demonstrates that in our framework, it is precisely the orthogonal constraint that necessitates the use of error feedback.
To address this issue, we propose to compress the Euclidean gradient V f(() in EF-Landing. Let g be the compressed approximation of the Euclidean gradient V (X.,, we let
Á(X; g) grad(g) + (X),
(7)
where grad(g) := skew gXX X,
VN(X) x x x1))
The proposition below ensures the orthogonality between grad(g) and (X) to hold after compressing (XX: Proposition 4.1. For any gradient estimate g E BRxx,, the orthogonality between grad(g) and (X) preserves (see proof in Appendix A.1):
Error feedback corrects non-convergence. Error feedback can correct the con-conveegence encountered with vanilla gradient compression (more details in Appendix A.2). In- spired by momentum error feedback (Fatkhullin et al., 2023), we employ the following updates within each node i:
(grad(g), VN(X)) =, VX E R"XP, Vg E Rxp,
n =1 n)) + +/ ck+1)
(8a)
4.2. Error Feedback
c = =C(uttt h+1 - g.))
(8b)
Vanilla compression may lead to non-convergence. Vari- ous approaches exist for compressing the Fuclidean gradient
g k+1 o + c
(8c)
4

---

Distributed Retraction-Fres and Communication--fiicaee Optimization on the Stiefel Manifold
Algorithm 1 EF-Landinn
the momentum rate is set to 1/ = 1, representing algorithms without momentum. Notably, when all three conditions hold simultaneously, EF-Landing simplifies to the basic Landing algorithm with gradient clipping, with exact convergence results as established in (Ablin et al., 2024). Table shows several scenarios to which EF-Landing is applicable.
Require: starting point X E R= gradient bound L':
step size y > 0; compressor C; momentum 1j E (0, 1];
1: Each node initializes vf - (.)) -.- C(n , 2: for = 0. -
for i = 1, ,,.., N; Master initializes go - 2i=1 g.
do 3: Master clips the gradient via (10);
Table I: EF-Landing for diverse scenarios
4: Master computes A(X*; (²) using (7);
5: Master computes X x = x* >A(x*:")) and
Stochastic
broadcasts X to all nodes.
Scenarios
Deterministic
(with momentum)
6: for all nodes i = , N in parallel do
7:
Compute momentum #+1 via (8a);
With compression
EF-Landing
EF-Landing
(Det.F) (1/KK
(Sto.")
8: Compress of via (8b) and send it to the master;
O(1/VNK)
9: Update local state g, via (8c).
10: end for
Vanilla Landing
Stochastic
11: Master updates gh1 via (9).
Without
Landing
compression
12:
end for
(1/KK)
O(1/VN))
Deterministic scenario. > Stochastic scenario.
where 17 is the momentum rate. Each node sends ef to the master, and the master updates the Euclidean gradient:
In the EF-Landing method (Algorithm 1), each node trans- mits the compressed variable c; to the master node, while the master broadcasts the uncompressed variable X to all workers. This unidirectional compression scheme is well- established in the literature (e.g., (Fatkhullin et al., 2023; Stich et al., 2018; Stich & Karimireddy, 2021; Alistarh et al.. 2017)), as upload costs typically dominate download costs in distributed settings. Notably, the communication of X can be removed in certain cases through system-level techniques such as the All-Reduce protocol (Patarasuk & Yuan, 2009), which eliminates the need for maater-to-woorke broadcasts.
N
b+1
g
The compressed gradient g* provides better approxima- tion than vanilla compressed gradient (X+t(x)))) dis- cussed in Section 4.2. Once g is obtained through the eгrоr feedback process (8)-()) the master node will compute the descent direction g( as outlined in (7).
4.3. La-dddni Algorithm
5. EF- Landing Convergence Analysis
EF-Landing comprises two key components: Euclidean gra- dient compression and error feedback, as outlined in the previous subsections. Additionally, before the master node computes the Landing descent direction (7), we apply clip- ping operation to g to ensure that the integrated gradient estimate does not push the iterations beyond the safe region (t,p, n)) (see Definition 3.1). Given gradient bound L' (specified later in Section 5.1), clip g" follows:
This section begins by presenting the necessary conditions, and then proceeds to derive the convergence guarantees and establish the convergence rates for EF-Landing.
5.1. Assumptions
The following assumptions are standard for optimization on the Stiefel manifold (Ablin et al., 2024) and distributed stochastic optimization.
g" = min {
L'
g..
(10)
Assumption 5.1 (Global Gradient Bound), There exists constant T,' such that the following inequality holds
|
Once clipped, g is ready for the computation of the Land- ing descent direction (7) and the iteration (3). The complete EF-Landing algorithm is presented Algorithm
[VF(X;))] S L', VX E St(p, n)", VG, ~ D,
Remark 5.2. The assumption of gradient bound L' mild, as the search domain St n) is bounded, and we assume that no highly anomalous data will cause gradient explosion. Assumption 5.3 (Lipschitz Smoothness). For each node i, fi(X) X + R is differentiable and there exists a smooth constant L, such that for any X, Y St(p, n
The EF-Landing algorithm is highly versatile. When the gra- dient oracle satisfies V VF(:;5) & = (X((X), the problem reduces to deterministic optimization. The algorithm also applies when the compressor C(-) is the identity mapping, corresponding to distributed optimization without commu- nication compression. Furthermore, it remains valid when
[VA(X) V.(() S I Yl
5

---

Distributed Retraction-Free Free and Communication--fiiiiie Optimization on the Stiefel Manifold
Remark 5.4. It is straightforward to show that the smooth- ness constant I. of the global function f(X) satisfies
(V((X),((Xg)) This bound plays critical role in analyzing the impact of compression error, it explicitly isolates the difference term llg lll)
L S Ia. { (L.). Additionally, we define L :=
E L as the averaged smoothness constant.
Lemma 5.8 (Merit Function Bound), For all X E St(p, n and g E R the inner product between the descent direc- tion (7) and the gradient of the merit function (11) satisfies the lower bound (see proof in Appendix B.2)
Assumption 5.5 (Lower Bounded Objective Function).
The objective function f(X) is lower bounded by f = inf inf f(X)= > -20.
1
Assumption 5.6 (Unbiasedness and Bounded Variance). There exists a 2 0 such that for each node i, for any X E St(p,n) it holds that
g), 2 |Igad f(x) + (xN(X)
4
+ + I|skew (gX ) 1/ - -11g Vf(x))
4
BG (F(:;)) - Vx(()] = 0, BE,ND. (I) [I so²
provided that μ 2 3-4e ( 222 2+)) where L. and I'' are defined in Assumptions 5.3 and 5.1, respectively, -= 1==maa max L'}. and e < 3/4.
5.2. Supporting Lemmas
5.3. Main Convergence Theorem
This section establishes supporting lemmas for the conver- gence analysis of the EF-Landing algorithm.
Given an arbitrary momentum coefficient 1) >> 0, we define Lyapunov function as follows:
Safe step size. The main objective of the Landing algorithm is to select an appropriate step size that ensures the iterations remain within St,p, ra).. In our analysis, we require only two assumptions Assumptions 5.1 and 5.3-to to determine uniform, non- von-vanishing step size that is valid throughout the entire iteration process.
C m - m + C17 Th. 20171B p++ C27 ph (12)
0
17
where Ghe = N i=1 1 -f
pk
N Σ
1
Lemma 5.7 (Uniform Safe Step Size). Consider the update X = X ->>((X;g) where ;(X;g) y is step size. For any X E nt(p,n) 9 E RR if |gg|r < T!' and we choose
pk = 1 \f(*>)
3) is defined in (7) and
where 0² : N Ex1 a.f and m denotes the infimum of the merit function (11). Constants 0, B, C1, O2 will be determined later. With the above Lyapunov function, we derive the main convergence theorem as follows.
X(1 - E)E ()/(2 + 22 + +)
7 Yo == min
1
Theorem 5.9 (Main Convergence Theorem). Letting As- sumptions 5. 5.3, 5.5 and 5.6 hold, if compressor C satis- fies Definition 3.2, for arbitrary momentun coefficient 1 E (0. 1], by running Algorithm I for K iterations, with proper learning rate y (see Appendix B.3), we have
2(1 + ()
2
then the next iteration X remains in St Su(p,)) (see proof in Appendix B.
Merit function.
We introduce a merit function to facilitate
K-1
Ellgrad
A
K-1
Σ
EEW(X*)
convergence analysis of La-Ldnning:
4K
2K
k==0
k=0
m(X) = ((x) - x(X)+ + (X()),
(11)
L
cn
-1-2)02
2011
302
c2702
0 + 0
1
K
N
where Mxx) = 2 (V(M)) x Ip)-
In the inequality, k is defined in (12), and 33 are two scalars defined as 0 := 1 vI- a and / == V-Vi-a C1 are two constants differently specified in three cases:
1-a
The constant μ is a hyperparameter, and its value will specified in Lemma 5.8. The merit function m(X) is Lm- smooth when restricted to the bounded safe region St(p, n)s, with an upper bound for Lm provided by (Ablin et al., 2024).
When the momentum coefficient 1 and the variance of gradients x² 0, the momentum and stochastic error is 0, and c1, C2 are specified as 1, 12 O.
Furthermore, under Assumption 5.5, since both (XX) and (XX) are bounded for X E St(p,n)) the merit func- tion mXX is also boundee with its infimum de- noted as m² In this work, we derive a lower bound for
When the contractive factor a 1, the compression error is O and c1, C2 are specified as 6 0, C2 1. Otherwise, we specify = 2
6

---

Distributed Retraction-Free and Communication- Optimization on the Stiefel Manifold
Remark 5.10. The convergence theorem above is highly versatile. By appropriately selecting hyper-parameters such as the momentum coefficient 7/. gradient variance a, and compressor factor a, our analysis applies to both determin- istic and stochastic settings, covering algorithms based on gradient descent and momentum-basee gradient descent, with or without communication compression.
5.5. Convergence Rate in Stochastic Scenario
In this section, we consider the case where the variance o² > 0 (Assumption 5.6). Notably, assumption differs from that of (Ablin et al., 2024), which directly assumes bounded variance for A g²). The momentum technique plays a crucial role in stochastic settings.
We consider the case with communication compression, i.c., a < 1, and analyze the most general version of the EF- Landing algorithm. In this setting, the constants in Theorem 5.9 are specified as c 02 = 2. The following theorem presents the convergence result of EF-Landing in stochastic scenarios, demonstrating linear speedup.
5.4. Convergence Rate in Deterministic Scenario
In this subsection, we set x² 0 in Assumption 5.6. We further set = to completely eliminate both momentum and stochastic error. Under these conditions, the constants in Theorem 5.9 simplify to e 1 and c = 0, allowing the theorem to naturally recover various convergence results in deterministic scenarios.
Theorem 5.14 (EF-Landing in Stochastic Scenarios). Let- ting Assumptions 5.1, 5.3, 5.5 and 5.6 hold, if compressor C satisfies Definition 3.2, and we choose step size 7 as in Lemma B.6, by running Algorithm I for K iterations, with proper learning rale ? and momentum coefficient nj (see Appendix B.6), we have
Theorem 5.11 (EF-Landing in Deterministic Scenarios). Letting Assumptions 5.1. 5.3, 5.5 and 5.6 hold, if compressor satisfies Definition 3.2, o² 0, and rj = 1, by running Algorithm I for K iterations, with proper constant learning rate y (see Appendix B.4), we have
K-1
Σ
(llgrads((*))
< 40
K
12.1 4(m((x) -m²)
GEE
K
VNK
B Illgradd
K=
Kr
K0
K=
B[N(X*)
2 o
1
((m(X)= -m²)
2F
K
AP
VNK
BIN(X
km
K
Kydp K0Aμ²
K=
where the O VNK
term is specified as
where 0 and B are defined in Theorem 5.9.
c
22 202C2L9) )
By additionally setting a = 1 and _ = O, meaning no compression is applied to the I Landing method, the theorem simplifies to the standard Landing convergence thcorem:
VNK 20 a) ( (CIL))
= K
+
NK
3
43022 1/
$C K
!
K
Corollary 5.12 (Vanilla Landing in Deterministic Scenar- ios). Letting Assumptions 5.1, 5.3, 5.5 and 5.6 hold, if compressor C satisfies Definition 3.2, o² = 0, n and
The constant L is defined in (12), while @ and B3 are spec- ified in Theorem 5.9. The constants C² and C2 are in- dependent of N and K, with their definitions provided in Appendix B.6.
= 1, by running Algorithm for K iterations, with proper constant learning rate (see Appendix B.4), we have
Remark 5.15. This theorem establishes that LF-Landing achieves an asymptotic linear speedup convergence rate. The impact of the communication compressor appears only in higher-order terms and does not affect the dominant linear speedup rate. Notably, this rate aligns with the momentum error feedback method (Fatkhullin al., 2023), which is designed for unconstrained minimization problems. This suggests that, with careful algorithmic design, the Stiefel manifold constraint does not pose fundamental challenges to communication compression.
ggradf(X < 4(m((x)- -m))
K
Ky
K=
2(m(X*)- -m))
Σ N(X*)
K
Kydu1
k=
Remark 5.13. Our established rate for vanilla Landing with- out compression is O(1KK), matching the state-of-the-art result in (Ablin et al., 2024; Vary et al., 2024) with exact constants, confirming the sharpness of our analysis. More- over, by comparing Theorem 5.1 and Corollary 5.12, we observe that Landing, with or without communication com- pression, achieves the same O(1/K) rate, indicating that compression does not degrade the convergence order. How- ever, more aggressive compression (i.c., + 0) leads to slower convergence for EF-Landing.
To illustrate the versatility of our convergence analysis, we now examine the stochastic Landing algorithm without com- pression. In this case, the constants in Theorem 5.9 are specified as c1 = and C2 = 1, leading to the result:
Theorem 5.16 (Stochastic Landing Convergence). Letting Assumptions, 5.1, 5.3, 5.5 and 5.6 hold, if compressor
7

---

Distributed Retraction-Fres and Communication- Optimization on the Stiefel Manifold
satisfies Definition 3.2, a with proper learning rale Y and momentum coefficient by (see Appendix B.7), by running Algorithm 1 for K iterations, we have
free variable block, the descent direction of the block-wise
constrained problem (13) be expressed
A(X; g) = (skew(1x[])X + +XI 1p)):
40
Cj C2C00 C NK
40
K
K
k=0
K Σ N(x*) K=
20 L
20
C2 L
skew (g. xxx))xx XX, Ipy):
- KAp
K
dy
NK
90) n.
(14)
where L is defined in (12), 0 and 3 are defined in Theorem 5.9, CR. C2 are two constants defined in Appendix B.7.
where 91 91..... 9.. Do can be - 05/0X,, o /0x or their compressed approximations, as indicated by (8) Using (14), the main update step follows:
Remark 5.17. Our analysis demonstrates that the vanilla Landing method achieves a convergence rate of O(I/VNK) in stochastic scenarios without compres- sion. Furthermore, by comparing Theorem 5.14 and The- orem 5.16, we note that the Landing method attains the same O(1/VNK) rate regardless of whether communica-
x = x 7
(15)
Therefore, is straightforward to extend the EF-Landing Algorithm 1 to solve the optimization problem (13) on the tion compression is applied. This indicates that the use of compression does not adversely affect the convergence order.
block-wise Stiefel manifolds. The implementation details are provided in Appendix C.1. Moreover, Appendix C.2 presents the convergence results of EF-Landing in stochastic scenario with block-wise constraints.
6. Optimization on Block-wise Manifolds
7. Numerical Experiments
Practical problems typically require variables to satisfy or- thogonal constraints in a block-wise manner, while the re- maining variables remain unconstrained, e.g., orthogonal CNN with orthogonally regularized convolutional layers and unconstrained MI.P layers (Wang et al., 2020). The optimization problem can thus be formulated follows:
To validate the performance of EF-Landing, provide experiments two groups of problems: the distributed online PCA for deterministic scenario and deep learning us- ing ResNet-18 (He et al., 2016) neural network architecture with orthogonal constraints applied to the convolutional lay- ers for stochastic scenario. We compared EF-I EF-Landding with other algorithms for optimization on the Stiefel manifold, including vanilla Landing, QR retraction and the Euclidean gradient descent with added la squared penalty norm. In ad- dition, to ensure the sufficiency and rigor of the experiments, we compared our approach with several other distributed algorithms on manifolds, including decentralized training frameworks (Chen et al., 2021) and centralized frameworks with multiple local updates before aggregation (Zhang et al., 2024). In all experiments, the gradient clipping bound T.' was set to sufficiently large value, as overestimating it does not incur any loss. All the experiments were implemented in Py Torch and performed using single GPU. Further ex- periments can be found in Appendix D.
min Xii
(13)
s.t.
x,|x, = 1p j= 1, J,
where Xj E XP) represents a constrained variable block on nz), and x E R contains the remaining un- constrained variables. We define X == (X1,..., x); composite data type, whose domain is given by R :- (R"1xp1,.. ..... Ra.xps R.)). Consequently, ʃ is well- defined as a mapping from R to R, with its gradient as
05
0s 0s
VS(x) = 0x1
E ER. ax," dz
The inner product on R is computed as
7.1. Distributed Online PCA
(E, = Σ (X Mg) (2,8), x E St.
The distributed online PCA problem can be expressed as
N Σ |AXX, 1=1
The norm on R is defined as |||||| == /x, X). allowing Definition 3.2, Assumptions 5.1, 5.3, 5.5, and 5.6 to be properly formulated for problem (13).
min XESt(p.n)
f(X) = 2N
where A E Bixn is the synthetically generated local data matrix for node i, with being the number of samples for each node. We set = 5000, 5000, N = and
By applying the Landing descent direction to each orthogo- nally constrained block and vanilla gradient descent to the
8

---

Distributed Retraction-Fres and Communication-Ffiicee Optimization on the Stiefel Manifold
(a) Training Loss
(b) Violation
(c) Riemannian gradient norm
101
EF-Landing-Top-K
EF-Landing-Topp
Rlemannlan gradlent norm
EF-Landing-Top
-Landing-Randoma
EF-Landing- Random-K
EF-Landing-QSGE
EF-Landing-QSGD
10"
EF-Landing-
Training Loss
Landing
10'
Landing
Landing
Retraction
Violation
Retraction
Retraction
Penalty method
Penalty method
Penalty method
10:2
104
10
10-
16-1
10-1
10a
10
1K
2K
3K
PK
8K
1K
3K
4K
9K
64
1K
2K
3K
4K
7K
ak
Communication(MB)
Communication(MB)
Communication(MB)
Figure 2: Performance comparison of EF-Landing and other algorithms on distributed online PCA with p = 1000.
10-4
3.0
EF- EF-Landing-Top--
3.0
EF LF-Lanning-Top-
EF EF-Landing-Top-x EF-Landing-Randomk Retraction
90
-LLanding-Rando-KK
-Laandin-Raaddom-
2.0
2.5
Retraction
Landing
2.5
2.0
Retraction
Landing
Violation
10
Landing
Accuraci
Training
1.5
1.5
10
50
EF-Landing-Top-K EF-Landing-Randome -aandlng--Rndo--K Landing
40
0.5
0.5
30
Retraction
0.0
4K 6K 10K12K14K16K
500
1000 1500 2000 2500
500 1000 1500 2000 2500
1000 1500 2000 2500
Iterations
Communication
Communication
Communication
Figure 3: Performance comparison on deep learning with ResNet- 18 on CIFAR-10.
p = 1000. For EF-Landing algorthm, the penalty parameter was set to 1, and we used three compressors: Top-K, Rand-K with compression retention ratio 0.1 and QSGD with quantization level 16. Using different algorithms mentioned above, we get the results in Figure 2.
et al., 2024). In case that the reshaped matrix becomes wide instead of tall, we enforce orthogonality on its transpose. Problem formulation (13) is suitable for our settings.
We tested the performance of EF-Landing on the CIFAR-10 dataset, using Top- K and Random-K compressors with compression retention ratio of 0.2. We compared the re- sults of EF-Landing with vanilla Landing and QR retraction methods in Figure 3. For each algorithm, the network is trained for 150 epochs, and the learning rate is reduced to 0.1 of its original value after the 100th epoch.
In the experiments, the training loss was computed by f(Xx) f(X.), where X, is the matrix composed by p right singular vectors of A (AT, ..., AT)" T, and the violation of constraint was computed by (XX) The result shows that EF-Landing reaches the same training loss as the vanilla Landing algorithm and other algorithms. Furthermore, due to communication com- pression technique, EF-Landing significantly reduces the communication overhead. For penalty method, the penalty parameter was set as À = 8. We observe that the penalty method performs poorly on this problem, which could not enforce the orthogonal constraint during the optimization process (its negative part of training loss was omitted). We provide further discussion on the choice of penalty parame- ters in Appendix D.3.
| X 12
As shown in Figure 3, EF-Landing and other algorithms reach similar accuracy in terms of iterations, while EF- Landing significantly reduces the communication overhead. Additional experimental details, including the choice of hyper-pane parameters such as momentum and step size, can be found Appendix
8. Conclusion
In this paper, we propose EF-Landing algorithm for solv- ing distributed optimization problems on Stiefel manifolds, which is both computationally and communicationally ef- ficient. EF-Landing encompasses various scenarios with sharp convergence guarantees and linear speedup rate. The good compatibility with block-wise problems extends the practicality of EF-Landing even further. Extensive numeri- cal experiments validate our theoretical results.
7.2. Neural Network with Orthogonal Constraints
Another group of experiments were conducted on Resnet1 88 We apply orthogonal constraints to the convolutional lay- ers by reshaping the convolutional kernels to size nout x Tin Ryy. where 7in and Nour are the numbers of input and output channels, and flg, ny are the filter dimensions (Ablin

---

Distributed Retraction- Freet and Communication--fficiee Optimization on the Stiefel Manifold
Acknowledgements
Arjovsky, M., Shah, A., and Bengio, Y. Unitary Evolution Recurrent Neural Networks. In Proceedings of The 33rd International Conference on Machine Learning, pp. 1120- 1128. PMLR, June 2016.
This work was supported by the National Natural Sci- ence Foundation of China under Grants 92370121, 12301392, and W2441021, and by the National Key Re- search and Development Program of China under Grant 101999... We also thank the anonymous reviewers for their valuable feedback.
Bansal, N., Chen, X., and Wang, 7. Can We Gain More from Orthogonality Regularizations in Training Deep Net- works? In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Impact Statement
Bernstein, J., Wang, Y.-.., Arizzadeneshelii K., and Anand- kumar, A. SignSGD: Compressed Optimisation for Non- Convex Problems. In Proceedings of the 35th Interna- tional Conference Machine Learning, pp. 560-569. PMLR, July 2018.
This paper centers on the theoretical analysis of machine learning algorithm convergence. We do not foresee any significant societal consequences arising from work, none of which we believe need to be explicitly emphasized.
Boissin, T., Mamalet, F., Fel, T., Picard, A. M., Massena, T.. and Serrurier, M. An adaptive orthogonal convolution scheme for efficient and flexible enn architectures. arXiv preprint arXiv:2501.07955 2025.
References
Ablin, P. and Peyré, G. Fast and accurate optimization on the orthogonal manifold without retraction. In Proceed- ings of The 25th International Conference on Artificial Intelligence and Statistics, pp. 5636-5657. PMLR, May 2022.
Bonnabel, S. Stochastic Gradient Descent on Riemannian Manifolds. IEEE Transactions on Automatic Control, 58(9)221772229, September 2013. Conference Name: IEEE Transactions on Automatic Control.
Ablin, P., Vary, S., Gao, B., and Absil, P.-A. Infeasible Deterministic, Stochastic, and Cariance-Reduction Algo- rithms for Optimization under Orthogonality Constraints. Journal of Machine Learning Research, 25(389):1-38, 2024.
Boumal, N., Absil, P.-A., and Cartis, C. Global rates of
convergence for nonconvex optimization on manifolds. IMA Journal of Numerical Analysis, 39(1):1-33, January 2019.
Absil, P.-A. and Malick, J. Projection-like Retractions on Matrix Manifolds. SIAM Journal on Optimization, 22(1): 135-158, January 2012.
Chen, S.,, Garcia, A., Hong, M., and Shahrampour, S. De- centralized Riemannian Gradient Descent the Stiefel Manifold. In Proceedings of the 38th International Con- ference on Machine Learning, pp. 1594-1605. PMLR, July 2021.
Absil, P.-A,, Baker, C., and Gallivan, K. Trust-Region
Methods on Riemannian Manifolds. Foundations of Com- putational Mathematics, 7(3):303-330, July 2007.
Absil, P-A., Mahony, R., and Sepulchre, R. Optimization Algorithms Matrix Manifolds. Princeton University Press, April 2009.
Edelman, A., Arias, T. A., and Smith, S. T. The Geometry of Algorithms with Orthogonality Constraints. SIAM Journal on Matrix Analysis and Applications, 20(2):303- 353, June 1998.
Ahn, K. and Sra, S. From Nesterov's Estimate Sequence to Riemannian Acceleration. In Proceedings of Thirty Third Conference on Learning Theory. pp. 84118. PMLR, July 2020.
Fatkhullin, I., Tyurin, A., and Richtarik, P. Momentum Provably Improves Error Feedback! Advances in Neu- ral Information Processing Systems, 36.76444-76645. December 2023.
Alimisis, F., Orvieto, A., Beeigneul, G., and Lucchi, A. Momentum Improves Optimization on Riemannian Man- ifolds. In Proceedings of The 24th International Confer- ence Artificial Intelligence and Statistics, pp. 1351- 1359. PMLR, March 2021.
Gao, B., Liu, X., and Yuan, Y.x.. Parallelizable Algo- rithms for Optimization Problems with Orthogonality Constraints. SIAM Journal on Scientific Computing, June 2019.
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD: cammuuiicatio--fffiiiee SGD via Gradi- ent Quantization and Encoding. In Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017.
Gao, B. Vary, S., Ablin, P., and Absil, P. A. Opti- mization flows landing on the Stiefel manifold. IFAC- PapersOnLine, 25(30):25-30, January 2022. ISSN 2405- 8963.
10

---

Distributed Retraction-Fri Free and Communication- Optimization on the Stiefel Manifold
Golub, G. H. and Zha, H. The canonical correlations of matrix pairs and their numerical computation. Springer, 1995.
Optimization on Riemannian Manifolds. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Lopes, C. G. and Sayed, A. H. Diffusion Least-Mean Squares Over Adaptive Networks: Formulation and Per- formance Analysis. IEEE Transactions on Signal Pro- cessing, 56(7):3122-3158) July 2008. Conference Name: IEEE Transactions on Signal Processing.
He, Y. Huang, X., and Yuan, K. Unbiased compression saves communication in distributed optimization: when and how much? Advances in Neural Information Pro- cessing Systems, 36, 2024.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and Arcas, B. A. y. Communication- Efficceen Learning of Deep Networks from Decentralized Data. In Proceed- ings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1273 1782. PMLR, April 2017.
Hotelling, H. Analysis of a complex of statistical variables into principal components. Journal of Educational Psy- chology, 24(6):417-444 441, 1933.
Hotelling, H. Relations between two sets of variates. Biometrika, 28:321-377, 1936.
Nedié, A., Olshevsky, A., and Shi, W. Achieving Geo- metric Convergence for Distributed Optimization Over Time- Varying Graphs. SIAM Journal on Optimization, December 2017.
Hu, J. and Deng, K. Improving the communication in decen- tralized manifold optimization through single-step con- sensus and compression, July 2024. arXiv:2407.08904 [math].
Patarasuk, P. and Yuan, X. Bandwidth optimal all-reduce al- gorithms for clusters workstations. Journal of Parallel and Distributed Computing, 69(2):117-124, 2009.
Huang, X., Chen, Y., Yin, W., and Yuan, K. Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression. Advances in Neu- ral Information Processing Systems, 35:18955-1896, December 2022.
Qi, C., Gallivan, K. A., and Absil, P.-A. Riemannian BFGS Algorithm with Applications. Jarlebring, E., and Michiels, W. (eds.), Recent Advances in Optimization and its Applications in Engincering, pp. 183-192, Berlin, Heidelberg, 2010. Springer.
Diehl, M., Glineur, F.,
Karimireddy, S. P., Rebjock, Q. Stich, S., and Jaggi, M. Error Feedback Fixes SignSGD and other Gradient Com- pression Schemes. In Proceedings of the 36th Interna- lional Conference on Machine Learning, pp. 3252-3261. PMLR, May 2019.
Qu, W., Chen, H., Xiu, X., and Liu, W. Distributed spar- sity constrained optimization over the Stiefel manifold. Neurocomputing, 602: 128267, October 2024.
Richtarik, P., Sokolov, I., and Fatkhullin, I. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. In Advances in Neural Information Processing Systems, volume 34, pp. 4384-4396. Curran Associates, Inc., 2021.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny i2ages.(2009). 2009.
LeCun, Y., Cortes, C., and Burges, C. Mnist hand- written digit database. ATT Labs [Online]. Available: 2, 2010.
Saxe, A., McClelland, J., and Ganguli, Exact solutions to the nonlinear dynamics learning in deep linear neural networks. In Proceedings of the International Confer- ence Learning Represenatations 2014. International Conference on Learning Represenatations 2014, 2014.
Gezcano-Casado, M. and Martínez- D. Cheap Or- thogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group. In Proceedings of the 36th International Conference Machine Learning, pp. 3794-3803. PMLR, May 2019.
Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. 1-bit stochas- tic gradient descent and its application to data- mata-parallel distributed training of speech DNNs. In Interspeech 2014, pp. 1058-1062. ISCA, September 2014.
Liu, X., Xiao, N., and Yuan, Y.xx. A Penalty-Free Free Infea- sible Approach for Class of Nonsmooth Optimization Problems Over the Stiefel Manifold. Journal of Scientific Computing, 9902):3, March 2024.
Shi, W., Ling, Q., Wu, G., and Yin, W. EXTRA: An Ex- act First-Order Algorithm for Decentralized Consensus Optimization, SIAM Journal on Optimization, May 2015.
Liu, Y., Shang, F., Cheng, J., Cheng, H., and Jiao, L. Ac- celerated First-order Methods for Geodesically Convex

---

Distributed Retraction-Fres and Communication-EPfiieen Optimization on the Stiefel Manifold
Singla, S. and Feizi, S. Skew orthogonal convolutions. In International Conference Machine Learning, pp. 9756- 9766. PMLR, 2021.
Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. TernGrad: Ternary Gradients to Reduce Com- munication in Distributed Deep Learning, In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Stich, S. U. Local sgd converges fast and communicates lit- tle. In ICLR 2019-nnteraatonal Conference on Learning Representations, 2019a.
Xiao, N., Liu, X., and Yuan, Y.-x. Exact Penalty Function for l2,1 Norm Minimization over the Stiefel Manifold. SIAM Journal on Optimization, December 2021.
Stich, S. U. Local SGD Converges Fast and Communi- cates Little. In ICLR 2019 International Conference on Learning Representations, May 2019b.
Xiao, N., Liu, X., and Yuan, Y--X. A class of smooth exact penalty function methods for optimization problems with orthogonality constraints. Optimization Methods and Software, 37(4): 1205-1222512211 July 2022.
Stich, S. U. and Karimireddy, S. P. The Error-Feedback Framework: Better Rates for SGD with Delayed Gra- dients and Compressed Communication, June 2021. 1XXiv:190.003355 [es].
Yu, T., Li, J., Cai, Y., and Li, P. Constructing orthogo- nal convolutions in an explicit manner. In International Conference on Learning Representattonss 2022.
Stich, S. U.. Cordonnier, J.-B., and Jaggi, M. Sparsified SGD with Memory. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Zhang, H. and Sra, S. First-order Methods for Geodesically Convex Optimization. In Conference on Learning Theory, pp. 1617-1638. PMLR, June 2016.
Sun, Y., Chen, S., Garcia, A., and Shahrampour, S. Retraction-Frea Decentralized Non-convex Optimiza- tion with Orthogonal Constraints, December 2024. arXiv:2405. [es].
Zhang, H., J. Reddi, S., and Sra, S. Riemannian SVRG:
Fast Stochastic Optimization on Riemannian Manifolds. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Tripuraneni, N., Flammarion, N., Bach, F., and Jordan, M. I. Averaging Stochastic Gradient Descent on Riemannian Manifolds. In Proceedings of the 31st Conference On Learning Theory, pp. 650-687, PMLR, July 2018
Zhang, J., Hu, J., So, A. M.-C., and Johansson, M. Non- convex Federated Learning on Compact Smooth Sub- manifolds With Heterogeneous Data. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J., and Zhang, C. (eds.), Advances in Neural Informa- tion Processing Systems, volume 37, pp. 109817-109844, Curran Associates, Inc., 2024.
Tsitsiklis, J., Bertsekas, D., and Athans, M. Distributed asynchronous deterministic and stochastic gradient opti- mization algorithms. IEEE Transactions on Automatic Control, 3 (19)8803-81, September 1986. Conference Name: IEEE Transactions on Automatic Control.
Zhao, J., Wang, X., and Lei, J. Distributed Riemannian Stochastic Gradient Tracking Algorithm on the Stiefel Manifold, January 2025. arXiv:2405. 16900 [math].
Vary, S., Ablin, P., Gao, B., and Absil, P.-A. Optimization without Retraction on the Random Generalized Stiefel Manifold. In Proceedings of the 41st International Con- ference on Machine Learning, pp. 49248. PMLR, July 2024.
Zhou, P., Yuan, X.-T., and Feng. Faster First-Order Meth- ods for Stochastic Non-Convex Optimization on Rieman- nian Manifolds. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, pp. 138-147 PMLR, April 2019.
Wang, J., Chen, Y., Chakraborty, R., and Yu, S. X. Orthogo- nal Convolutional Neural Networks. pp. 11505-11515, 2020.
Wang, I.. and Liu, X. Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented La- grangian Function. IEEE Transactions on Signal Pro- cessing, 10:3029-3041, 2022. Conference Name: IEEE Transactions on Signal Processing.
Wangni, J., Wang, J., Liu, J., and Zhang, T. Gradient Spar- sification for Communication- Effficien Distributed Opti- mization. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
12

---

Distributed Retraction- Free and Communication--Pliccenn Optimization the Stiefel Manifold
Contents of the Appendices
A. Details of Realizing EF-Landing
13
A.1. Proof of Proposition 4.1
13
A.2. Example Showing the Necessity of Error Feedback
14
A.3. Unconstrained Deterministic Optimization with Vanilla Gradient Compression
14
B. Details of Convergence Analysis
15
B.1. Proof of Lemma 5.7
15
B.2. Proof of Lemma 5.8
16
B.3. Proof of Theorem 5.9
18
B.4. Details of Theorem 5.11 and Corollary 5.12
23
B.5. An adequate Selection of Step Size with momentum
23
B.6. Proof of Theorem 5.14
24
B.7. Proof of Theorem 5.16
25
C. Details of Optimization on Block-wise Manifolds
25
C.1. Algorithm for Block-wise Problems
25
C.2. Convergence Results of EF-Landing in Stochastic Scenarios for Block-wise Constraints
26
D. Further Numerical Experiments
28
D.I. Online PCA
28
D.1.1. Datasets
28
D.1.2. Hyperparameters
28
D.1.3. Experiment Results
29
D.2. Neural Networks with Orthogonality Constraints
30
D.2.1. Datasets
30
D.2.2. VGGI6 on MNIST
30
D.2.3. VGG16 and ResNet-18 on CIFAR-10
32
D.3. Comparison with the Penalty method
.33
D.3.1. PCA problem
33
D.3.2. Neural Network
35
D.4. Comparison with Decentralized Setting
37
D.S. Comparison with Centralized Multi-Local-Update Setting
.37
A. Details of Realizing EF-Landing
A.1. Proof of Proposition 4.1
Proof. For any R2x,, we have
(skew(gXX XX, x Tr(x skew skew (9X x
Tsskew((gX)) X X-1,xx (skow(gX) x x
where skew(gX is skew-symmetric matrix and AX 4 is symmetric one. For any skew-symmetric matrix X and symmetric matrix Y.
x,Y)= Y - -xx,y) 0.
which leads the conclusion.
13

---

Distributed Octraction-Free and Communication--fiiccenn Optimization on the Stiefel Manifold
A.2. Example Showing the Necessity of Error Feedback
Here is toy example illustrating the phenomenon of stagnation. Let X [ and the Stiefel manifold {X R X 1} is now unit circle. We only consider distributed learning single node with gradient (X)) (2, 1) Top-1 compressor will compress the gradient into f(V
(2, 0) T If the iteration point X happens to be (1,
the Riemannian gradient after compression grad(g) = skew (g.X ) will be 0 since C(V (X)) = (2, 0) happens to be orthogonal to the tangent space of Stiefel manifold at point X = (1, 0) i.e., span (0, }. The iteration point X is on St(1,2), so the gradient of penalty term (X) is also O. Therefore. the descent direction ((XX)(((())) is but the iteration does not reach a stationary point. Furthermore, greedy compressor Top-1 will permanently output the same compressed gradient (2. 0) T as long as the iteration point does not move. This causes the iteration to stagnate.
However, when using error feedback, for the same situation, we first make stagnant step to X' = X (1,0)* But since the error feedback technique compresses the difference of two consecutive gradients, the next gradient after compression will be C(Vf(x)) + (XV) - CCV = (2,0) + (0, 1) = (2, 1) which is no longer orthogonal to the tangent space of X' on the Stiefel manifold because the direction parallel with the tangent space comes into effect. Hence, the iteration escapes the stagnation point. Figure 4 illustrates the process.
-VV)(X)-C(V)(3))
Vf(X)
c(Vf(x))
2t(
Figure 4: Diagram for the toy example in Appendix A.2.
The heuristic reason explaining the phenomenon of stagnation is: Greedy compressors choose the directions with largest magnitude in unconstrained Euclidean space, but these directions are not necessarily directions with largest magnitude in feasible subspaces of the Stiefel manifold. In extreme cases, when the two sets of directions do not intersect at all and the greedy compressors cannot give other feasible directions for the current iteration point, the iteration falls into stagnation. Error feedback, however, tends to select directions that were discarded in the previous iteration, ensuring that the feasible directions of the Stiefel manifold could always be selected within a few steps. Hence, error feedback technique overcomes the phenomenon of stagnation. In fact, for any deterministic optimization problem on the Stiefel manifold, when using greedy compressors, stagnation occurs with high probability. Thus this is general problem that is eventually solved by enror feedback technique.
A.3. Unconstrained Deterministic Optimization with Vanilla Gradient Compression
The error feedback strategy introduced in (Richtarik al., 2021) mainly eliminate the instability caused by compression among more than one nodes at the stationary point. A straightforward idea is that when using contractive compressors, the same issue does not exist in the songle-node scenario without any extra constraint. In fact, we have the following algorithm and its convergence result.
Algorithm 2 Unconstrained Deterministic Optimization with Vanilla Gradient Compression (Single node)
1: Input: starting point 0 E IRd, learning rate 7 > 0 T do
2: for = 0, 1,
3: g*
C(V/CC/) f(
4: kk+1 k 7g*
5: end for
14

---

Distributed Retraction-Free and Communication- Optimization on the Stiefel Manifold
Theorem A.I. Suppose J TR IR is L-smooth and lower bounded by f", and the compressor C satisfies Desinition 3.2, we choose the step size 1/L, by running Algoritim 2 for K iterations, we have
K- 1
|| 2(1(2)-1 -5)
K
yar
Proof. Using L-smoothness of f, we have
L
f(a - f(x²) + (Vf(2*), xh41 - 2//++ +
11
b+ - xx112
2
-s(²)) (V ),9²) + L
$1laAt1 10--1x111 -11
2
- -((**) " - -
2 -
-1
I
x01
-((² |1 22
1
" || - =111 + 211o* (Vf(())
Noticing that Definition 3.2 of contractive compressor leads to
BlIlo* V/ (0-
we have
[[s(x*t1)] & B[((x*))) F [1 )|3} //2
L
[B[1 - 1B[loottt [²]
2 + Blll (
2
I <B[[(**)]
T )| - -(27
L
- - 2 (1 - -) )1
Blllattt1
2
=E(((>
T B ||| (/7
L
1 111
2
2
y S L/L, immediately have
ao E
-
2
After telescoping, we get the final result.
B. Details of Convergence Analysis
B.1. Proof of Lemma 5.7
It is important to note that points within St(p, nt) have bounded singular values. The proof is straightforward and can be referred to (Ablin et al., 2024).
Lemma B.1 (Singular Values). If X E (t,,,)), we have vI-Esos &I for any singular value a of X.
And the proof of Lemma 5.7 is also based on (Ablin et al., 2024).
Proof. (Ablin et al., 2024) proved that for any given X E St(p, n) and E Raxp, there exists an upper bound of step size 7" ()) step size ((;g) S (X: g), the next iteration remains in St(p, n).. Further, if [|skew (g ]X|| = a, the bouer of step size 7 (X: g) will not disappear but can be lowerebounded as
(xx:9) 2 min
X(1 e)e
E
1
x
(2 + 2) V
2a 2X
15

---

Distributed Retraction-Free and Communication--PPiieee Optimization the Stiefel Manifold
Let's take one step further, if ||g|| < L', have:
gskew g X (1 + [1++)]]sbae c)llskow(gX )|? (1 + 1)1gX |1 S (1 (1+ (1 (1+ (z)
(16)
where the first and the third equations are from Lemma B. and the second is due to the orthogonality between symmetric and skew-symmetric matrices. Therefore, if we choose uniform step size
X(1 c)c Y S % min { ((+c) + x² e)e2 V 2(1 2 2) 2X
1
then for any given g, the next iteration will remain in the safe region.
B.2. Proof of Lemma 5.8
Lemma B.2 (Gradient of merit function). m(X) is the merit function defined in (11), and its gradient be expressed as
Vm(X) = - -x x - -1]]
XsymmX VI(X)) + (V)(
(17)
where ((X) (:00=sym(VV))) sym(V[(X)) R - RRUX Ix (x(+) denotes its derivative at X, and Jx Jx (x) X denotes vx))) in X evaluated in the direction X X Ip- Further, let voc(.) m + mm denote the vectorization operation, and let Hx E R denote the matrix representation of the Hessian of at X, we have
the adjoint of the Jacobian in the sense of the Frobenius inner product of (x
(ec(Jx(@)' X 1p) = H xe x 4p)).
(18)
The main part of proof for this lemma can be found at (Ablin et al., 2024).
Now we are ready to prove lemma 5.8.
Proof. STEP 1. We will bound all the terms from the inner product (Á(X;g), Vm(X)) separately by considering the four terms in (17) respectively.
The inner product between the first term of (17) and the descent direction is
(A(X:g), Vf(X)) (skew (gX TT ) + AX(X x I,), V((X))
(skow x )) Vf(X)X + X(XTX Ipp, XV
= Askew(gX T), skew (Rxeee/V((XXXX)))) + + Ip,sym(X VV())))
(19)
The first inner product term can lower bounded as
(skew(g.X) skew (adew([[(())) (X(xxx))
|ssee(gg) I|?
(kkew(Vf((XX)) )| - ||skew(( Vf(X))x I
of llg vf(X)
|skew(g 1 |sskew( )1
(20)
where the last inequality is due to the orthogonality between symmetric and skew-symmetric parts of one matrix, and 01 is the maximum singular value of X.
For the inner product between the second term of (17) and the descent direction,
1 (A(X:)), - -xx 1))
2 X(H veXWXx) vec(V.V(X)))
(21)
2 (xVee(V.N(X)), veclskew ))))
(22)
(VI(X) T )X,, skew(gX")x,,X'x Ip)
(23)
(Xsm(XTT((X)), -1,)²).
(24)
16

---

Distributed Retraction-Free and Communication--Pfiiee Optimization on the Stiefel Manifold
In the third term of the inner product, the lossy gradient estimate g has no effect:
g)) XXsym(X (1yy(((Vv(x))) (skew( g ")X + AVX) (
(25)
X/sym(X Vf(X)), x xxxxxXxX
(26)
The last term is also not affected by the lossy gradient estimate:
(VN(x)) = >
(27)
Adding all the four terms and applying the lower bound in the first term gives
of
(A(X:g), Vm(X)) 2 2 skew (gx 1| +
1 Vf(x)
(28)
2
+ M(IInp 2 Hx vvo voo vo(V)))))
(29)
>((XTx x - Ip) sym((' ,ym)) syy((TVV[(x)) V/(()))
(30)
(Hxvec(VV((X)) voc(skow(g.X) )x))
(31)
2 (Vf(X) skew ( )x (
Tp)
(32)
where the first line (28) comes from the lower bound (20); the second line (29) is a combination of (21) and (27); the third
line (30) comes from the second term of (19), (24) and (26); the fourth and the fifth terms are the rest terms (22) and (23).
STEP we should separately bound the new five terms. Setting aside the first term, we first analyze the second term (29):
Mp - (xx)) (X)Xx))))(((>))))
1
21/
L 1
L 24N
2 1oPN(X).
(33)
where L is the Lipschitz constant of V (X) over St(p, n)) defined by Assumption 5.3, and on the minimum singular value of X; the first inequality comes from the smoothness of ((X) and the second by the property of singular values of X.
The third term (30) can be lower bounded using Cauchy- Cauchy-Schwarz inequality
3 2z2 x - 11)) sy,,,ssm("" sym((TT (S()))) 2 - (X VVV(X()
V/(X))
2 - LN,,L'
(34)
where the second inequality is again due to the orthogonality between symmetric and skew-symmetric matrices and L' is such that [[X](l S L' for all X E St(p, n) defined by 5.1.
We further use Cauchy-Setie Schwarz inequality bound the fourth and the fifth terms. The fourth term (31) lower bounded as
(UXvec(VVA(())) vec(skew(gX Vee (xx)
2 - 1 - 4p) |/ske///wwwwwwe (gX
L
2 - Lo Lo N(X)ss(X)ssss x X
(35)
The fifth term is lower bounded as
1
2 VV(()) skew(gX skew(g]])x,xXX
x -X1)) 1p) -- / Vf(x]]| - ||skew ) Ipll
- L' L-L'VV(X3J]skew/ (gX )
(36)
17

---

Distributed Retraction-FFis FreetionnFFeeeaaae and Communication-Ffiiieel Optimization on the Stiefel Manifold
Putting the fourth and the fifth terms together, we have
2 (VX())))VVV)),
veclseee (x)) (V
(ef((X)Tsken) skew skew(gx)) 1p)
2 (L' + Lo)) +LoI)////E/)///eevxxXX"""""
2 1 (L' + (oo)))(((X)++++)>>
(gX (
(37)
where in the last inequality use the average inequality vay (x++)) with x 6X(X) and y - b- "[|skeww (g for an arbitrary > 0 which will be specified later.
Now for the first term (28), by using the property of singular values X again, we have
||skow(g )re 2 of [|skew(g ] [sske((V(XXX Mlr 2 (
(38)
Adding all lower bounds (33), (34), (37) and (38) together, we have total lower bound expressed
1 + Lor)
()(:;g), Vm(()) 2 Igaad/ f ((X]] + [|ske((gx
2
20 2
of g - [| 442
2 10?
Gdσ - 2 ( + Loi)b)
(39)
2
Finally, we choose b so that the coefficient of [|skew )x 1/ equals to 1/4, namely b = 20fi1' + Lord 2 2-
and noticing
V1 - op on S vi+cs v2, we have
(A(X:g), Vm(X)) 2 1 [lerad/(x)11 + 1lskew )x - -11 VS(X)1I
L 109 - -6A0IL' - 2 + Lo +N(X)) (M (4
oo
(40)
2 2 of
Denoting = max (I', L). the last term of (40) can be simplified as
(4X) L 100 62σ L' of (L' + Lo1)
2-0द
N( )1 - e) 6AVI+ - -i²(1 +c) -) (1-
2 N(X)( )1 - () G\VT+ - -4.((1- (c))
(xN(X).
(41)
where in the last incquality, we choose μ as
[(1 -) + +3/++ + +2i 1
2 3 de
(42)
which leads to the conclusion.
B.3. Proof of Theorem 5.9
We introduce some notation for convenience.
Auxiliary variables: momentum vector of the m N Li=i of: random variable of the master &h
ΣN
(Et...., < stochastic gradient of the master (F( = N N vF(
Momentum and stochastic error: error of each node ph = aali (x(( ||?; averaged error ph : 1 N EN a Vf((*)) error of the master pk := || V ||?
18

---

Distributed Retraction-Free Freet and Communication--Pfiieen Optimization on the Stiefel Manifold
Compression error: error of each node G. := =Ilg of I averaged error := ト/4 E llot of I error of the master G* = l1g* w* 1
Filtrations: filtration for the conditional expectation of stochastic gradient J%. = (5" 5², ,.,,..,,
_5-- x
filtration for the conditional expectation of compressor Fb == (E" x E x² ,²,..., 5 ck-1 X 5²)
Next, for arbitrary momentum factor 17 The following two lemmas provide the iterative formats of two kinds of errors.
Lemma B.3. The iteration of momentum and stochastic error satisfies
B[ s (1-1) + (1 (1 1
L
|| 12] + + ||
(43)
1/
B[Pett] > (1 (1- + (1 2) +
1
1.
- [2:] + +
(44)
77
| + 1202
B[pkt]| 1 (1 - pp + (1 (1 1
(45)
N
Proof. For the first inequality (43),
B B[P = B[llo, [(((+++)) |
E B[I[(1 n) + 7/F (x+++t+ - )|
E [| -
(1)--()))) (0 Vs(( + (V ( - v)(
= E [|(1 - (0 - v((x*t)) + -
F ||
S [1 1 - /x((x+1))))))))) +700²
(1 (1 1) - v>((*)) >
+ - (1-1))(11 (1 | 11 - +1200
s (1 - -)- (1-)))) - |
(46)
where the second equation is by the update rule of n b+1 the first inequality due to Assumption 5.6, the second inequality the consequence of Young's 's inequality and the last by the smoothness of each local function.
By simply summing all inequalities in terms of node from 1 to N, we get the second inequality (44). Notic- ing that FF(** == N Ei' (x E and according to the independency of each entry of &, we have Ega+1 [| (ht))
1 S o²/N. Similarly, we can derive the third inequality (45).
Lemma B.4. The iteration of compression error satisfies
E < (1 -- B s (1 -1 -,
+ (1 -
xx1
a)n
(47)
2))?
(48)
where 9 and 3 are two scalars related the contractive factor a, i.e. 0: VI- and 3 1 Vi-a
19

---

Distributed Retraction-Fres Freee and Communication--Piiieent Optiiiiiiiitttiiiiiititiii on the Stiefel Manifold
Proof. For the first inequality (47).
E[G = Ellgg ++1 v
+ 112] = 18 | + - 112-1
F [1 +++ ) C( - gf)]l = -
11
< (1 a [
|1 + - -/ = (1 - a) [[[[
( 9. 12:1
(1 a E
b gt + + (VF. =
) [1
(1 a )
1 b o. n (VSi o + + ( ( [bt)|
$ (1 a |
||0 /6 + (Vf (1* of) [|:] + (1 - a))
S (1- a1 + 1|g क + (1- a) + | 1 V -
(1-aa)f
- 11 + (1-a))
(49)
where the first inequality is due the property of contractive compressors (Definition 3.2), the second inequality is by the bounded variance (Assumption 5.6) and the third is the consequence of Young's inequality with parameter p. We should choose a proper P satisfying (1 - a1 + p) < 1 and (1 a1 +1 < +o0. (Richtarik et al., 2021) provided a to some
degree optimal choice = 1 we have
v1-a 1. Denoting 1 - 0 = (1-a) p) = v1 a, and B = (1 - a1 + 1/p) 1-VI-a'
1-c
E 1 $ (1 - B)E |1 - +,
- 1 + - +11 a)
$ (1 B) | - -/
- vf((x*)] )
+ 2.3 - + +1-a))1)
$ (1 - 0] + L x || | 237 + a1-2)
(50)
The second inequality (48) follows the same process as lemma B.3. Lacking the unbiasedness assumption of the compressor, we have no similar inequality for master, which is fortunately unnecessary.
Another lemma helps us split || 1B term to two orthogonal component used for convergence analysis.
Lemma B.S.
| = (imx(x*x'))) S (1sxev(((((x) + +
(51)
Proof. This lemma can be easily proved by the orthogonality between two terms of A(X*": and the sigular values bound of X (Lemma B)
Now we are able to prove the main theorem.
Proof.
STEP 1. Dividing different Errors. Using smoothness of m(x²) mentioned in Section 3.1 and Lemma 5.8, we
have:
m(x++1) s mm(x") + (Vm(x*)) X x x² + Ly |x*+t| - -x113
2
=m(x²)- > (mm(X*) A(x*; g) + I 2
2
sm(x²)- Ileradd ((x ((xx) )1 2 skew
(g" (x*))T) 11 + >lla* \(
-7dud(Xt)) Lm ||Ā(X** *
(52)
20

---

Distributed Retraction-Fres Free and Communication--PPiicenn Optimization the Stiefel Manifold
Denote S = {X E ||* s LJ. then we have g projs(g"). and v)((*) projs (V Therefore, using the property of projections,
l|@e
VS(X*) S llg V
(53)
Next, we need to separete the momentum and stochastic error as well as compression error. We first introduce an inequality l|g )l( ci llg o² 11 + oz V ((**) where two undetermined constants are specified three cases:
When the momentum rate 17 1 and the variance of gradients o² 0, the momentum and stochastic error will be 0, so
C12 C2 are specified as 1, C2 0, which is trivial.
When the contractive factor a = 1, the compression error will be 0, so C1, are specified as = 0, C2 = 1, which is trivial too.
Otherwise, we specify C1 = c2 2, which the consequence of mean value inequality.
Therefore,
11g Vf(x*)]3
<allg** - -0 -
N
l
of + c2
vs(x*) = c² + c2
(54)
where the second inequality is due to Jensen's 's inequality.
For convenience, we denote S = ||ske (g* ( > whose influence will be climinated later by choosing a proper step size. Substituting (54) into (52) after using (53), we have:
1(x++1) I m(xx)
? 4 Ig
7 5 + n + tr2pp - >AxN((x*)) + Im ||A(x* (55)
4
STEP 2. Constructing Lyapunov Function. Adding ey G++1 to both sides of 55, taking expectation and using lemma B.4, we have:
El Emm(X ) + 22 [
< ()))x)) ) 7 Ellgrad ((x*
[|:]]
4
7 B
4
+ 41 [B + n L'B||
x + 28 + (1 a)n²o²2)
4m BIIĀ(* 1
+ Ppp - 7XEE(N(X*))
E[m(X*)] 01 + B
Ellgradd ) - 1 E (
201 11.82
bm?
E ElIA((** :g |
20 2 3
[Pk]+ + C1 217 a))
+
B[Pb] + [
(56)
0
0
Further adding
20 201y p1++1 ez ph++1 to both sides, subtracting lower bound m² by Assumption 5.5, and using lemma B.3,
21

---

Distributed Retraction-Fres and Communication--fiiccenn Optimization on the Stiefel Manifold
have the following collated inequality
E Blm( [+]] mmm + C17
2c1 20
18 1l + 22? Blptttl
0
s [[m(X**) m + c B + 0
20
E[Pk| + 227 BlPt
"
2 B
2 1 - ">nnB/N(X'
4
221 222 (1 17 1 )²)
122
1m (
+
2 + n)>
n
r (1 - 2))²
201 m/ B
02
0 + 0
(57)
N
which corresponds to the Lyapunov function we defined as (12).
STEP Choosing Step Size. Next, we split [|(* gg) li using lemma B.5, which splits [X]]A(X;;
into E[S*]
and )x To eliminate the influence of S and to make the coefficient before (XX*) negative enough, we are looking for sufficiently small step size to make the coefficients before B[S*] and ([(((**) [X] satisfy
2c1 3c (1 (1-n+ n + o2L? n12
+ +ny + Lm? (1 (1- 1) (1-1)²(1
+
2 00
(58)
4
and
2c, 9L2
C2L2
Lm?
-
7Ap
Au + 41 + e)
(1
-1-18 (1 )/3
(1 21 + n +
< -
(59)
0
112
2
It's reducible to a quadratic inequality problem. suppose a, b > 0, if we choose 0 S x S (vā + b)-1 the inequality ax² bor S 1 holds. So it's enough choose step size 7 as
min Yo, Y1, 72
where 7s is the uniform safe step size defined by Lemma 5.7, and 71, 7/ are defined as
71 = (2va 2m
21 + t)a
4x2 + L)
72 2
1
1
where
20, 322
C2L²
(1 17 11²)
(1 21) (1+ n).
0
n2
With a small enough step size 7, we have
B < B| 4 ((xx)add((**)) 7'1
a)o² 20
o2Yma
(60)
STEP Summing Up. Summing up all inequalities from 1: to K 1 and dividing by K, we have
A 2K
+ (1-(11)) 2e1 302
c2
Ellggadf
+
Σ BW
(61)
4K
N
22

---

Distributed Retraction-Free and Communicationn-Piiieeet Optimization the Stiefel Manifold
B.4. Details of Theorem 5.11 and Corollary 5.12
Theorem 5.11. When o 0, 7 y= 1, Ci and C2 0, the momentum and stochastic error p O, the Lyapunov function defined in (12) can be simplified as
C m(x+) -mn + G
(62)
According to the rule of choosing step size in Appendix B.3, the step size should be chosen as
7 min (iin77s (Tss 71, 72)
where is the uniform safe step size defined by Lemma 5.7, and are defined as = (2v0- 2Lm)
21 + t)aa 4x2 e) -1
72 = 21
1
11
where
2,82
2. Theorem 5.12. When a = 1. the compression enror Gh will be 0. so the Lyapunov function can be further simplified as mxx)) m And the choice of the step size can also be simplified as L
7 min (ss 2m 4x2 + Lm
B.5. An adequate Selection of Step Size with momentum
Before deriving conclusions about convergence with momentum, we give a lemma about the step size. This lemma gives an adequate but not necessary choice for step size, for the convenience of analyzing the influence of momentum.
Lemma B.6 (An adequate Selection of Step Size with momentum). For the step size defined in Theorem 5.9, fix momentum rate 1) E 1), If we further choose = min(7s: of V 20,3 GL/2e," 6lm 12L V (1+c))
12L (1te) 1ex=(1-e]L.m }. then the step size satisfies y S min 7, 72) defined in Theorem 5.9.
Proof. The rule of choosing step size Appendix B.3
7 min(Tes 71, 72
where ys is the uniform safe step size defined by Lemma 5.7, and 71, 72 are defined as
= (2vā + 2Lm)
2X2(1 + c)a 4X2 c)
72 2
where
20 Bī.
C2T2
(1 - 17 + 11²) =
(1 - 17) + 7))
a 0
We can bound v as
2c, 3i
22
201
2cgL2
2213
L
Va=
(1 - n +7)) +
(1 21
-2oz
(63)
0
0
112
0
11
23

---

Distributed Retraction-Free and Communication-Fficiaa Optimization on the Stiefel Manifold
where the last inequality is due v < V vD, 2, 0. Therefore,
71 = 12va+22.mp 2 2 2013
L
-
+ 2 V 21
(64)
"1
For (x + + +-)=,, 2, > 0, if we denote M = max (2, ys 2). then + = min + at +, 1 So (z + y + 2)-
M
3M
min( + : 1. Hence, if we choose 7 S min
20r3t GLV/2g' _ then it satisfies 7 71.
a
67 V
The same reasoning leads to
72 (2V
21 e)a
41 + L)
2 (1IA)
cI + +eB
L
c2 + 4X² + e) -1
1
1M
1)
1
(65)
Choosing y S min{
(1+))) T2t ( 12x
satisfies Y S 72. And the conclusion follows.
12L V
B.6. Proof of Theorem 5.14
Proof. When e1 C2 =2, the Lyapunov function is
k m(x*) =n= + 27 Gh
4ym ps
27 pk.
(66)
"1
Choosing step size y as Lemma B.6 and setting C1 = C2 = leads to
1
12A + em
B
21 + + + 12T. + 1
21 +c)
1
+ 6T
12f
+ 12
(67)
7
1s
1
0
7
We denote C
+6 6lm +
12x (1+6))m
+12i
+ +12
213(1+))8
and C3 12L 122++111 12L
(1++)
for convenience.
1
10
P
Using Theorem 5.9, we have
K- 4K
Ap K
C
21 a)o²
30
2no²
[[llgrad[(X*)]]]
+
B[N(X*))
+
+
+
(68)
2K
K
nn
0
0
N
We choose 17 min
C3NC 20
1/2
8C 211
1/3
80, LD Too
1/44,, that
GC nk
2no²
C
(1-(1
and
C
nk
4ny B0² and at least one inequality takes equal. Hence, (68) can be bounded as
0
El [[llgad](X*
A
Σ
[[N(X*))
C C2C' nn
4
2K
K
k=0
C
LD
2n0² + 21 +
4n2
+ 4
K
C
CD
C20
200 (1-
3/C, CC,
?
4302
1
/ C,
+ 4
+4
+
(69)
K
NK
0
K
8
K
which leads to the conclusion.
24

---

Distributed Retraction-FFis Free and Communication-EPiitaal Optimization on the Stiefel Manifold
B.7. Proof of Theorem 5.16
Proof. When ei 0, 02 1, the Lyapunov function can be simplified as
k m(xx) mn" + pk.
(70)
And Theorem 5.9 leads to
Au Σ B[N(X*))
L
110²
Bllgrad ((x*) [1
(71)
4K k=0
2K
7K
N
Choosing step size y Lemma B.6 and setting C1 0,
leads to
1
A2 + 6T + 12 + + + (6V2T+ 12T
+
(72)
988
We denote C7 = 1. + m4. + (1+c))m and C3 = 6V2L + 12L
AR(1+e)
for convenience, and (71) leads to
K
Ap
K
C
C
no²
Blllgadd f(
5
(73)
4K
2K
K
n
N
k=
C. 2o
Choosing
leads to the conclusion.
o²
C. Details of Optimization on Block-wise Manifolds
In this section, we provide block-wiss version of EF-Landing algorithm. And we further prove the convergence result for stochastic scenarios with compression. Other Scenarios can be deduced similarly.
C.1. Algorithm for Block-wise Problems
Algorithm Block-wise EF-Landing
Require: starting point X E R; gradient bound L'; step size 7 >> 0; compressor C; momentum // E (0, 1]:
1: Each node initializes of VF( { of C(v)) for i ,,..., N; Master initializes g" No2 > gf.
2: for & = 0, 1,.,.,,,4 K do
3: Master clips the gradient g min(1. I'/
4: Master computes A( g using (14);
5: Master computes k++1
x* ->x gh) and broadcasts 21+1 to all nodes.
6: for all nodes l,... .N in parallel
Compute momentum Di-1 (1-n)uf n) + 7VF : 8: Compress oi via o: C(o +1 o and send the master;
9: Update local state k+1 via ++1 g + c..
10: end for
11: Master updates gh+ via ghg = g N EM c..
12: end for
25

---

Distributed Retraction-Free and Communication-Eliiie Optimization on the Stiefel Manifold
C.2. Convergence Results of EF-Landing in Stochastic Scenarios for Block-wise Constraints
Theorem C.1 (Block-wise EF-Landing Convergence in Stochastic Scenarios). Consider the problem (13) with block-wise constraints (13). Letting Assumptions 5.1, 5.3, 5.5 and 5.6 hold, if compressor C satisfies Definitton 3.2 (all in the sense of composite data type in R) ), if we choose step size r as in Lemma B.6, by running Algorithm for K iterations, we have
K
ellgrad,J((3)
S 40
VNR
2 o
1
K
Ap
v VNK
F=1
K-
1
05
111
20
K 0=
Da
2
VNK
where 01 ((/RR) )
specified as
1
GC +4 +1(20 2200 (202000 LU L
NK
K
NK
20 20 -a)
$ $
$C22 LO
(880²)
C2 Co
+4 +4(
+ 4
0
K
K
when choosing = min
C. No 2
11/
80 co 2z--ooo
)1/3,
(BC 1
)//33
L is defined in (12), and B are defined in
(300K
Theorem 5.9, CT, C2 are two constants defined as C = 1 + 66m + (1 + 12t 3 + 12t 222(1++)
and
n0
C2 = 12L + / 21+(1+
Proof. We choose the merit function as:
m(x)= = f(x)- - Σ (x,) + Euxs()).
(74)
where hx,) = { sym x
0f ax,/
x3 X,- - -p,)) and μ is a
specified later.
Noticing that partial functions like hx,))) satisfies ak, axx
= 0, Vj a ki we have
(A(I; g), Vm(()) = skew (g) x,xx))x++ + XX, - 1)) of ax,
Of vhy(X,) VaNg(x)) go de
Noticing that for all j = 1,.... J, a5 is L-Lipschitz smooth as long as V is L-Lipschitz smooth, and 8f is L' b'-bounded as long as V f((x) is I/' -bounded, using Lemma 5.8 with the same choice of ju, we have
ax;
ax,
(A(3; g), Vm(()) 2
skcw 05 x, 0x,
X,
+
skow
[,,x,
x,
1|
Σ j=1
J
9,
0f ax,
4
F
4
1=1
+ Σ
)xN(Xx) + |1.u
1 211
0s
2
gu
0f 051² Ox 12
(75)
dr
2
j=1
where for (go: 8f)
0z we use (a, b) = |a111 + + - 1aa b1 2
|aa| +
I|a - b112- The inequality is for the
sake of ||g 22 Σ/=1 ||g
a1 13 + -1
2f 113. Hence, using smoothness of m m3*t) and the merit function
2x,
26

---

Distributed Retraction- Free and Communication--liccee Optimization on the Stiefel Manifold
bound (75), we have
Lm || 1 -x01=
S <m((*)) m(x
(m(x*), x x²)
2
7²
=m(x)h) - 7(Vm(("))) A(2"; : +
||( 012
J
||skew (x)) 1B - 7ip E
S <m(*)) 4 Σ lggrad f(x)
Σ
4
==1
j=1
+ 7 |IA( -²) -
0f
+
+
(76)
2
axc
Denote S = =E ||skew( (x,)) || following the same process as the proof of Theorem 5.9, we have
Emm }] m +
c17
2e1
201m
E[ + 227 B(pkt]]
θ
7
s [ mm* cI7
G
20mm3
E[
+ C27 B(pt)
0
0
r
2
B Bllgrad f
(X.
||
7
E[sh] App Σ
BLNG (X+)]
- B
0f
[
7 Bllgg lB))
2
0z
2
1=1
2c 3i.
c2
Lm
(1
+
- (1 n)/93
B (
112
2
(1 a0)
2arm Ba²
027ma
(77)
0
0
N
Noticing that f1 ||kko(( TX,31 + 4x N5,(3) -1 if we choose y S 7/1 defined in Theorem 5.9, the following inequality also holds, so that the influence of [1ōol can be climinated.
7 + 0
20, 3L2
(1 -1-n " + 02L² (1 -1-18 (1-n))(111)))))
+)>p +
Lm
S
(78)
2
n
2
Hence, we do not need any additional restriction for y apart from 7a: 71 in Theorem 5.9. With the step size above, we have
B|ck+1] < E[C
?
E Elggad ,
Σ
J
Abp
Σ
E[N,(X)))1 + 3
0f 12 2 0z 2
4
j=1
j=1
Ci c - a)o²
2c 2 30²
c27n0²
(79)
0
Summing up all inequalities from = to K 1 and dividing by K, we have
K-1
K
E [
+
Aμ
Σ [XA)
4K
2K
2K
k=
1=1
k=D
1=
k=0
a)a
20 20 30²
c2no
(80)
0
0
N
Follow the same process of proof of Theorem 5.14, we achieve the final result.
27

---

Distributed Retraction-Fres and Communication--fiicienn Optimization the Stiefel Manifold
D. Further Numerical Experiments
D.1. Online PCA
D.1.1. DATASETS
In the experiment, the matrix E R is synthetically generated, where N = 20, 000 represents the number of samples, each of dimension n 5000. The columns of A are independently sampled from the normal distribution M((,, UUT +oI,), with 0.1, and "R= is sampled from the Stiefel manifold using the uniform Haar distribution.
D.1.2. HYPERPARAMETHER
We conducted the experiment in deterministic scenarios and distributed the data across 4 nodes. The EF-Landing algorithm was tested for different values of (100. 200, 500, and 1000). The results were compared with the QR retraction method, Euclidean gradient descent with l regularization (referred to as the Penalty method), and the Landing algorithm. The compression methods used included Top-K, K, Random-K K and QSGD. For the Top-K and Random-K compression, the compression rate was set to 0.1, and for QSGD, the quantization level was set for = 100 and = 200, and for p 500 and p 1000. The experiment involved 600 iterations for all algorithms with fixed learning rate, except for the QSGD algorithm when p 1000, where learning rate decay was applied during the iterations.
Mcthod/Hyyerparameeer
Y
Clipping
compress rate
EF-LLandig--Ton Top-K - Random-K K
1.0
10a
0.5
0.1
1.0
10
0.5
0.1
FF-I andinn-- QSQQD Landing Retraction
1.0 after 100 steps)
10
1.0
10a
0.5
1.0
0.5
Penalty method
1.0
8.0
Table 2: Hyperparameters of 100
Method//typerparameetr
Clipping
compress rate /s
EF-Landing-Toon Top-K
1.0
10a
0.5
0.1
EF-Landing- Mandding-Rando---f
1.0
10a
0.5
0.1
EF-Landing-Q&S5 QSSGD Landing Retraction
1.0 (0.01 after 100 steps)
10a
0.5
8
1.0
10
0.5
1.0
0.5
Penalty method
1.0
Table 3: Hyperparameters of 200
Method/HHyperparameeer
Clipping
compress rate /s
OF-LLandigg-Tyy Top-K
1.0 (0.01 after 100 steps)
10
0.5
0.1
EF-Landing Random-K
IF--Landin-RRnndo---
1.0
10
0.5
0.1
EF-I andinannddnsSt G
1.0 (0.1 after 50 steps)
10a
0.5
16
Landing Retraction
1.0
10a
0.5
1.0
0.5
Penalty method
1.0
8.0
Table 4: Hyperparameters of 500
28

---

Distributed Retraction- Free and Communication--Piiccenn Optimization the Stiefel Manifold
Method//Hypemparmeetr
?
Clipping
compress rate /s
-an-Ladi Top-A
1.0
10a
0.5
0.1
EF-L Handing-Random-- K
1.0
10
0.5
0.1
EF-Ilanding-QSO
(0.1 after steps)
10
Landing
1.0
10a
0.5
Retraction
1.0
0.5
Penalty method
1.0
Table 5: Hyperparameters of 1000
D.1.3. EXPERIMENT RESULTS
(a) Training
(b) Violation
(c) Riemannian gradient norm
EF-Landing-Top-K
10a
EF-Landing-
Riemannian gradient norm
100
EF-Landing-Top-K
Halanding-RRndom- EF-LandIng-QSSC
EF-Landing-RRnddom
EF-Landing -aanddmm-
10-1
EF-Landing-QSeE
10-1
EF-Landing-OSGG
Landing
Landing
Training Loss
Landing
Retraction
Retraction
Violation
Retraction
Penalty method
Penalty method
Penalty method
10-
10-2
10
10-4
20-
10-3
10
10
100
200
300
400
500
600
700
160
200
300
400
500
600
700
100
200
300
400
500
600 700
Communication(MB)
Communication(MB)
Communication(MB)
Figure 5: Performance of EF-Landing and other algorithms on online PCA, with 100
The corresponding experimental results for parameter p taking values of 100, 200, and 500 are shown in Figures 5, and 7, respectively. We can observe that, regardless of the compression algorithm, EF-Landing consistently reduces the communication volume by at least half while still converging to the optimal value of the function and ensuring that the norm of Riemannian gradient approaches O. Additionally, compared to the Landing algorithm, the EF-Landing algorithm requires less communication to satisfy the constraints on the variable X, specifically ensuring that N(X) ) sufficiently small, as demonstrated in Figures and 7.
(a) Training Loss
(b) Violation
(c) Riemannian gradient norm
TF-Lan
10a
EF-Landing-
Riemannian gradient norm
EF-Landing-Top-K De-Landiig-RRnddon
100
GeLaanding-Randoll K
EF-Landing-
EF-Landing-QSGU
EF-Landing-QSGE
Landing
-0-1
Landing
Training Loss
Landing
10a
Retraction
Violation
Retraction
Retraction
Penalty method
Penalty method
10-2
Penalty method
10-3
10
10a
10-1
10-1
10
10-3
10
200
600
800
1K
1.2K
3.4K
200
400
600
800
1K
1.2K
200
400
600
800
1.2K 1.4K
Communication(MB:
Communication(MB.
Communication(MB.
Figure 6: Performance of EF-Landing and other algorithms on online PCA, with p 200
29

---

Distributed Retraction-Fres and Communication--iiiee Optimization on the Stiefel Manifold
(a) Training Loss
(b) Violation
1o(c)
Riemannian gradient norm
10
EF-Landing-Torp
EF-Landing-Top-k
Riemannian gradient norm
EF-Landing-Top-K
EF-Landing-Randn Random-K
10a
Random-K
10a
EF-Landing-
EF-Landing-
EF-Landing-QSCo
Landing
10-1
Landing
Training Loss
Landing
10-1
Retraction
Violation
Retraction
Retraction
Penalty method
Penalty method
Penalty method
10
10.
10->
10
10"4
10-4
10
10-3
500 1K
1.5K
2K
2.5K
3K
3.5K
500
IK
1.3K
2K
2.3K
3K
3.3K
4K
500
1K
1.5K
2K
2.5K
3K
3.5k 4K
Communication(MBB
Communication(MB)
Communication(MB)
Figure 7: Performance of EF-Landing and other algorithms on online PCA, with p 500
Compared to the QR retraction method, EF-Landing reduces a significant amount of computational effort by eliminating the need for QR decomposition, making the algorithm more efficient. On the other hand, the Penalty method is highly sensitive the choice of A. If À is too small, the parameters may fail satisfy the constraint, shown in Figures and 5 to 7. If À is too large, the Riemannian gradient may fail to converge to and can lead to numerical instability. Although the Landing method can more accurately satisfy the orthogonality constraints, it requires several times more communication. By contrast, the EF- Landingg algorithm remains highly efficient.
D.2. Neural Networks with Orthogonality Constraints
We also tested the performance of the EF-Landing algorithm on neural network models with orthogonal constraints applied to the convolutional layers. Orthogonal constraints are playing an increasingly important role in deep learning. For example, they can ensure the stability of gradient magnitudes during training (Arjovsky et al., 2016; Saxe et al., 2014), preventing issues like gradient explosion or vanishing. Furthermore, there has been growing attention on how to design orthogonal convolutions (Singla & Feizi, 2021; Boissin et al., 2025; Yu al., 2022).
D.2.1. DATASETS
The MNIST dataset only has citation requirement (LeCun et al., 2010). It includes 28 x 28 grayscale images of handwritten digits from 0 to 9, containing 60,000 training data samples and 10,000 test data samples.
The CIFAR-10 10 dataset, which consists of 32 x 32 color images depicting 10 distinct categories of real-world objects, is comprised of 50,000 training samples and 10,000 testing samples. requires citation (Krizhevsky et al., 2009) for usage.
We applied some basic data augmentation techniques to these datasets during the training stage. For CIFAR-10, we applied random cropping, random horizontal flipping and random gray scale.
We conducted experiments VGG16 and ResNet- 18, comparing the performance of the EF-Landing algorithm with the Landing and QR retraction algorithms. Specifically, we applied orthogonal constraints to the convolutional layers by reshaping the convolutional kernels to the size neut X Ru where Thp and Nour represent the number of input and output channels, respectively, and nt and ny are the filter dimensions (Ablin et al., 2024). In cases where the reshaped matrix becomes wide instead of tall, we enforce orthogonality on its transpose.It is worth noting that the Block-wisc Constraints formulation (13) better suits this problem, as we impose constraints on each individual convolutional layer rather than on the entire neural network parameters X.
D.2.2. VGG16 ON MNIST
In this experiment, we use the built-in VGG16 model from PyTorch and initialize the convolutional layers using QR decomposition to enforce orthogonal constraints. To match the model architecture, we added a convolutional layer to the VGG16 model. This convolutional layer has an output channel size and a padding of 3. Consequently, we adjusted the shape of the data to 32 x 32. The compression methods applied are Top- K and Rand-K. with a compression ratio of 0.2. The training data uniformly distributed across 4 nodes. The initial learning rate y is determined via grid search over the
30

---

Distributed Retraction-Free and Communication--Piiieett Optimization the Stiefel Manifold
Method//typerpprammeer
Clipping
compress rate
OF--Landing-Tps Top-K
0.1
0.1
10
1.0
0.2
Lalaandinn-Randdon-
0.1
0.5
10
1.0
0.2
Landing
0.1
1.0
Retraction
0.1
1.0
Table 6: Hyperparameters: VGG16 on MNIST
set (0.001,0.0) 0.01, 0.1, 1.0). and is decayed by factor of 1/10 every 10 epochs. Similarly, the step size 1) is selected from {0.1, 0.5, 0.7} via grid search. We use a batch size of 128 and train the model for total of 30 epochs.
(a) Training Loss Iterations
(b) Training Loss Communication
-F-LandinggTop-K
EF-Landing- IF-Landing-Randee
10a
EF-Landing-Randon
10a
Landing
Landing
Retraction
Retraction
Training Loss
10-1
Training Loss
10-1
10-2
10-2
10
10-3
10-4
10-4.
500 1000 1500 2000 2500 3000 3500
250
500
750
1K
1K
2K
Iterations
Communication (GB)
(c) Violation vs Communication
(d)
Test Accuracy vs Communication
10-2.
100
EF-Landing-Top-K EF-Landing-Rande Landing
Retraction
Test Accuracy
Violation
10-3
90
10-4 -4
EF-Landing-Top-K
80
EF-Landing EF-Landing-Random- K
Landing
Retraction
1K
500
2K
Communication (GB)
Communication (GB)
Figure 8: Performance EF-Landing and other algorithms on deep learning with VGG16 on MNIST.
Figure 8 demonstrates that the EF-Landing algorithm achieves convergence of the training loss function and test accuracy to a steady state with less communication volume, and the accuracy on the test set stabilizes around 99%. In addition, the EF-Landing algorithm outperforms the Landing algorithm satisfying the orthogonality constraint under this experiment, which also highlights the advantage of the EF-Lanndng algorithm to some extent.
31

---

Distributed Retraction-Free and Communicationn-Pfiieeet Optimization the Stiefel Manifold
Method//typerpprammeer
Clipping
compress rate
OF--Landing-Tps Top-K
0.1
0.5
10
1.0
0.2
Lalaaniinn-Rnnddo--
0.1
0.1
10
1.0
0.2
Landing
0.1
1.0
Retraction
0.1
1.0
Table 7: Hyperparameters: VGG16 on CIFAR-10
D.2.3. VGG16 AND RESNET-18 ON CIFAR-10
Additionally, we tested the performance of EF- Landingg on the CIFAR-I0 dataset in 4-node setting, using the Top-K and Rand-K K compressors with compression ratio of 0.2. We compared the results with the Landing and QR retraction methods. In the experiment, each algorithm was trained for 150 epochs, and after the 100th epoch, the learning rate was reduced to 10 of its original value, with set to 1.0.
(a) Training Loss vs Iterations (b) Training Loss vs Communication
2.5
EF-Landing- Braadding-Random
2.5
EF-Landing-Top-K EF-Landing-
Landing Retraction
Landing
2.0
2.0
Training Loss
Training Loss
Retraction
1.5
1.5
1.0
1.0
0.5
4K 6K 8K 12K 14K 16K
2K
4K 5K 6K 7K
Iterations
Communication (GB)
(c) Violation vs Communication (d)
Test Accuracy vs Communication
90
EF-Landing-Top-K Selandiin-Randomme
80
10-2
Landing Retraction
Test Accuracy
70
Violation
10-3
50
40
EF-LandinggTop-K -anddo----addm-KKK
10
30
Landing
Retraction
20
OK
1K
2K
3K
4K
5K
6K
7K
OK
1K
2K
3K
4K
SK
6K
7K
Communication (GB)
Communication (GB)
Figure 9: Performance of EF-Landing and other algorithms on deep learning with VGG16 on CIFAR-10.
As shown in Figures and 9, in terms of satisfying the constraint conditions, the EF-Landing algorithm not only reduces ((X) with less communication overhead compared to the Landing algorithm, but also satisfies the constraints more accurately. Furthermore, in terms of computational cost, the EF-Landing algorithm offers a clear advantage over the QR retraction method, being free of QR decomposition calculations.
32

---

Distributed Retraction-Free and Eommunicationn-Piiieeet Optimization the Stiefel Manifold
Method//typerppaaameer
Clipping
compress rate
EF-LLandig-Top Top-K
0.1
0.5
10
1.0
0.2
Balaanninn-RRnddom-
0.1
0.5
10
1.0
0.2
Landing
0.1
1.0
Retraction
0.1
1.0
Table 8: Hyperparameters: ResNet-18 on CIFAR-10
D.3. Comparison with the Penalty method
This section mainly compares the performance of the EF-Landing algorithm and the Penalty method.
1. PCA PROBLEM
The data generation process for the Online PCA problem follows the description provided Appendix D.1.1. The step size is selected via grid search over the set {0.001, 0.01, 0.1, 1.0). As shown in Figures 10 to 13, compared with the EF-L Si-LLanding--asee
algorithm, the Penalty method is highly sensitive to the choice the penalty parameter A. When too small, the orthogonality constraint cannot be effectively enforced. On the other hand, choosing larger may introduce numerical instability, necessitating a smaller step size and consequently slowing down convergence. In contrast, the EF-Landing- basedd algorithm satisfy the orthogonality constraint with relatively small X, leading to faster convergence, and consistently achieves smaller Riemannian gradient norm.
(a) Training Loss
(b) Violation
(c) Riemannian gradient norm
EF-LandInn-
Riemannian gradient norm
10*
IF-Landing-Rande K
EF-Landing-QSSE
Training Loss
101
EF-Landing-Top-
10-1
Penalty 10
EF-Landiing-op-k
EF-Landing -anddin--
Violation
Penalty ==10
10-2
EF-Landing-Randdom+ EF-LandIng-QSGG
10
EF-Landing-Op
Penalty x = 10
10-3
Penalty À = 10
10a
Penalty À = 10
Penalty À 10
10
10-1
10
10-1
600 Communication (MB)
200 200
500
200
200
500
600
200
300
600
Communication (MB)
Communication (MB)
Figure 10: Comparison with Penalty Method: p 100
Method/Hyyperprrameerr
7
Clipping
A
compress rate
1.0
10
0.5
0.1
Li--Landng-RRadom-ii
Random-K
1.0
10a
0.5
0.1
Penalty method
0.01
10.0
Penalty method
0.001
1000.0
Table 9: Hyperparameters: Comparison with Penalty Method p 100
33

---

Distributed Retraction-Fres Freet and Communication-Ffiice Optimization the Stiefel Manifold
(a) Training Loss
(b) Violation
(c) Riemannian gradient norm
10"-
EF-LandIng-
Riemannian gradient norm
10*
K
EF-Landing-QSSe
Training Loss
Penalty =01
10-
10r
EF-Landing-Top-
EF-Landing-Top-K LaLaanding-Raddome EF-Landing-QSGa
Kaadd
Violation
Penalty A 10
-F-Landing-QSGa
Penalty X = 10"
10
Penalty À = 10
Penalty A = 10
10
Penalty À = 10
10-1
10-1
10-1
10
200 400
600
1K
1.2K 1.4K
200
400
800
800
1.2K 1.4K
200
400
800
1.2K 1.4K
Communication (MB)
Communication (MB)
Communication (MB)
Figure 11: Comparison with Penalty Method: p 200
Method/tyyperparameeer
7
Clipping
X
compress rate /s
EF-Landing-Topy Top-
1,0
10a
0.5
0.1
UB-LLnndig-Randdnee Random-K
1.0
10a
0.5
Penalty method
0.01
10.0
Penalty method
0.001
1000.0
Table 10: Hyperparameters: Comparison with Penalty Method p = 200
(a) Training
(b) Violation
(c) Rlemannian gradient norm
10a
EF-LandinngTop-k
Rlemannian gradient norm
10a-
EF-Landing-
100
EF-Landing-QSGD
Training Loss
Penalty 1=
10
EF-Landing-Top-KK EF-Landing-Random: EF-Landing-QSGL
EF-Landing-Top-K Ff-Landing-Randeee
Violation
Penalty 10²
201
EF-Landing-QSGGl Penalty x Penalty x= 10
Penalty
Penalty == 1
10-1
10-4
10a
-0
10
10-1
500
3K
1.5k
2K
2.5K
3K
3.5K
4x
500
1.5K Communication (MB)
1k
2X
2.5K
3K
3.5K
4K
2.5K Communication (MB)
500
1K
1.5k
2K
3K 3.5K 4K
Communication (MB)
Figure 12: Comparison with Penalty Method: p 500
Method/Hyyperprrameerr
7
Clipping
A
compress rate
Laddinng-Too--K
1.0
10
0.5
0.1
EF-Landing-RRane Random-K
1.0
10a
0.5
0.1
Penalty method
0.01
10.0
Penalty method
0.001
1000.0
Table 11: Hyperparameterrs: Comparison with Penalty Method p 500
34

---

Distributed Retraction-Free and Communication-Ffiicei Optimization the Stiefel Manifold
(a) Training Loss
(b) Violation
(c) Riemannian gradient norm
10*
EF-Landing-Top-K
Riemannian gradient norm
SeLaanding-Raddee K
Training Loss
10a
+ EF-Landing-Top-4
EF-Landing- Randim-
Violation
10"1
EF-Landing-
Penalty A 10?
Penalty 10"
10-
EF-Landing-Top-4
F-LandiingRRaddom*
10-7
OF-Landing-QSoo
EF-Landing-QSGG
10-2
Penalty À = 10"
Penalty X = =1
10
Penalty À 10
10
Penalty À 10²
10-3
10-1
10a
2K
4K
2K
4K
2K
4K
6K
Communication (MB)
Communication (MB)
Communication (MB)
Figure 13: Comparison with Penalty Method: p 1000
Mcthod/Hyperparanneer
Clipping
À
compress rate /s
EF-Landinn-TTop Top-K
1.0
10a
0.5
0.1
OF-LLanding-Raddee
1.0
10a
0.5
0.1
Penalty method
0.01
10.0
Penalty method
0.001
1000.0
Table 12: Hyperparameters: Comparison with Penalty Method p 1000
D.3.2. NEURAL NETWORK
We compare the Penalty method and the Fi-LLanding-based algorithm on the CIFAR-10 dataset using VGG16 and ResNet-18 neural network architectures. A grid search was conducted over y E {0.001, 0.01, 0.1, 1.0) and 17 E f0.1, 0.7] to determine the optimal hyperparameters. Each algorithm was trained for 150 epochs, and after the 100th epoch, was of its original value. A batch size of 128 was used throughout the training process.
reduced to To
From the experimental results (Figures 14,15), we observe that the EF- algorithm achieves higher accuracy while significantly reducing communication costs, and it satisfies the orthogonality constraint more precisely. contrast, the Penalty method performs poorly. When using relatively small penalty coefficient, such À 10, it achieve relatively high accuracy, but fails to satisfy the constraint precisely as the EF--Landingbban based algorithm. On the other hand, increasing the penalty to À = 1000 improves constraint satisfaction but leads to a significant drop in accuracy.
Method//typerparameter
Y
Clipping
À
compress rate
0.1
0.5
10a
1.0
0.2
EF-LLnddngg Bn-LLandin-RRandom- K
0.1
0.1
108
1.0
0.2
Penalty method
0.01
10.0
Penalty method
0.001
1000.0
Table 13: Hyperparameters: EF-Landing Algorithm and Penalty Method: VGG16 on CIFAR-10
Method/HHyperppramnttr
Y
"
Clipping
À
compress rate
EF-LaaniingTop--K
0.1
0.5
108
1.0
0.2
Laaandiin--Rnddoo..
0.1
0.5
10
1.0
0.2
Penalty method
0.01
10.0
Penalty method
0.001
1000.0
Table 14: Hyperparameters: EF-Landing Algorithm and Penalty Method: ResNet-1 18 on CIFAR-10
35

---

Distributed Retraction-Fiie Free and Communication--Piiieett Optimization the Stiefel Manifold
(a) Training Loss vs Iterations
(b)
Training Loss vs Communication
2.5
EF-Landing-Top-K
2.5
EF-Landing-Top-K
B=-LandingRRandom-
Ff-Landiin-RRaddm-
Penalty A= 10
Penalty x= 10
2.0
2.0
Penalty A= 10
Penalty A= 10a
1.5
1.5
Training
Training
OK
2K
6K 8K 10K 12K 14K 16K
0K 1K 2K 3K 4K 5K 7K
Iterations
Communication (GB)
Violation Communication
(d) Test Accuracy Communication
10a
EF-Landing-Top-K EF-Landing-Ramdome
Penalty
80
Penalty 10
Test Accuracy
Violation
10
60
10
50
40
EF-Landing-Top-K EE-Landing-Random:
10-3
30
Penalty ==10
10
Penalty x= 10
2K
5K
SK
7K
Communication (GB)
Communication (GB)
Figure 14: Comparison of EF-Landing Algorithm and Penalty Method: VGG16 CIFAR-10
(a) Training Loss vs Iterations
(b) Training Loss vs Communication
EF-Landing-Top-K FF-Landing-Randomm
EF-Landing-Top-K EE-Landing-Random-
3.0
3.0
Penalty x= 10
Penalty x= 10
Penalty x= 10
Penalty x= 10
Training
Training
1.5
1.5
0.5
0.5
0K
2K
6K
10K 12K 14K 16K
500
1000
1500
2000
2500
Iterations
Communication (GB)
Violation Communication
(d) Test Accuracy Communication
10a
EF-Landing-Top-K EF-Landing-Randon
100
Penalty 10
Penalty 10a
Test Accuracy
70
Violation
11
60
10-2
10
40-
To-Landing-Top-K EF-Landing-Rantom-
30
Penalty = 10
10
Penalty A= == 10a
500
1000
1500
2000
2500
1000 1500 2000 2500 Communication (GB)
Communication
Figure 15: Comparison of EF-Landing Algorithm and Penalty Method: ResNet-18 CIFAR-10
36

---

Distributed Retraction-Fres Free and Communication--Piiieent Optimization on the Stiefel Manifold
D.4. Comparison with Decentralized Setting
We performed online PCA experiments using synthetic datasets, each comprising 1000 data points per node with 100 and p 5, following a data generation process which is detailed in Appendix D.I.1.
For the Decentralized distributed experiment, we chose the DRSGI and DRGTA algorithms from (Chen et al., 2021) as baselines. In the experiment, we set the number of nodes to 20, the communication rounds t to 1, and selected ring topology with the Metropolis constant matrix associated with the graph. Under a ring topology communication structure, each node interacts solely with its two immediate neighbors. When the number of nodes is set to 20, this configuration is approximately equivalent to the centralized setting with a compression rate of 0.1. For DRGTA, we set 3 to 0.05, while for the DRSGD algorithm, we set 3 to 0.01.
For the EF-Landing algorithm, we set À 1.0, the learning rate 7 0.2, and the compress rate to 0.1.It is worth noting that the metric used to evaluate the satisfaction of the manifold constraint follows the approach proposed in this paper, which is based on the canonical correlations (Golub & Zha, 1995) between X and X
(a) Training Loss
(b) Distance to Opt
(c) Riemannian gradient norm
EF-Landing-Top-f
10"
EF-Landing-Top-K
Riemannian gradient norm
EF-Landing-Top-
Training Loss
10
DRSGD
DRGTA
EF-Landing-Randon Random-K
Distance to Opt
DRSGD
DRGTA
Random-K
201
DRSGD
DRGTA
LLandinn-RRaddom.
10
10
16-2
10
10'7
10-1
10-
10
300
1000
1500
2000
2500
500
1000
1300
2000
2500
0
300
2000
1300
2000
2300
Iterations
Iterations
Iterations
Figure 16: Comparison of EF-Landing Algorithm and Decentralized Algorithm On Synthetic Dataset
(a) Training Loss
(b) Distance to Opt
(c) Riemannian gradient norm
EF-Landing-Top-K
L-Landdng--op--
Riemannian gradient norm
EF-Landing-Topt
10
DRSGD
EF-Landing--R Random-K DRSGD
-LandinggRandoo-KKK
EF-Landing-Randome Random-KK
DRSGD
Training Loss
DRGTA
Distance to Opt
10
DRGTA
10P
DRGTA
20
20
10-2
10
18
10-7
10
10-4
500
1000
1500
2000
500
2000
1500
2000
300
1000
1500
2000
Iterations
Iterations
Iterations
Figure 17: Comparison of EF-Landing Algorithm and Decentralized Algorithm On Synthetic Dataset 2
Figures 16 and 17 demonstrate that the EF-Landing based algorithm achieves faster convergence compared to DRGTA and DRSGD, while also exhibiting superior constraint satisfaction performance.
D.5. Comparison with Centralized Multi-LocaalUppatee Setting
Using the algorithm proposed in (Zhang al., 2024) benchmark, we conducted experiments the Online PCA problem using synthetic datasets. The number of nodes was set to 4, with total sample size of N 800, 20 or 200, and 5.
For Algorithm 1 proposed in (Zhang et al., 2024), we set the parameters as 7 = 5, 10, 17 0.001, and nn = 1.0, where r represents the number of local update rounds, r denotes the learning rate for local updates, and ny represents the learning rate at the center.
37

---

Distributed Retraction-Free and Communication-Ifficce Optimization the Stiefel Manifold
For the EF-Landing algorithm, we set À 1.0, the learning rate 0.2, and the compress rate 0.1.
Figures 18 and 19 demonstrate that the EF-Landing- -aasdd algorithm exhibits superior performance in terms of constraint violation and achieves comparable convergence speed to the benchmark.
(a) Training Loss
(b) Distance to Opt
EF-Landing-Top-
E--LandingRRandom-
EF-Landing-Top- EF-Landing-Randome Alg
Alg
Training Loss
Alg 1,r=
Distance to Opt
10
Alg =10=10
10
10-3
10-1
10"3
10-5
10
10
50
100
150 200
130 200 Communication(K3)
20
300
Communication
Rlemannian gradient
(d) Violation
-T-LandinggTop-K EF.Landing-Random- Alg =
10
LF-Landing-Top-x EF:Landing-Rande
Rlomannian gradient norm
10-2
Alg =,r=
Alg 1,t 10
Alg 1,1 10
20*
Violation
20"1
10-1
10-3
10-3
10
10-1
30
100
150
200
90
250
200
Communlcation(ke)
Communication(KS)
Figure 18: Comparison of LF-Landing Algorithm and Algorithm in [Zhang al. 2024), synthetic dataset 20
(a) Training Loss
(b) Distance to Opt
EF-Landing-Random: Random--
EF- TF-Landing-Top-K
107
EF-Landing-Top-K BF-Landdig-RRandom-K Alg 1,T 5
Alg 1,t 5
Training Loss
Alg
Distance to Opt
10
Alg
10-1
10-1
10
Communication(KB)
Communication(K3)
(c) Riemannian gradient norm
(d) Violation
107
EF EF-Landing.Top.K DF-Landing-Randdms Alg 1,T
10
EF-Landing-Top-K
Rlemannian gradlent norm
Hr-Landdng-Randomm Alg
103
Alg 1,T
Alg 1,r
10-3
Violation
10
20
30-1
10
10a1
1500
Communication(KB)
Communication(KB))
Figure 19: Comparison of EF-Landing Algorithm and Algorithm in [Zhang et al. 2024], synthetic dataset n = 200
38


Reviews:
[{"review_id": "mGA4Z61uPY", "reviewer": "Reviewer_b4uN", "summary": "Paper provides an error feedback based algorithm to solved distributed optimization problem on Stiefel manifold (set of orthonormal matrices). This algorithm generalizes recently proposed retraction-free Landing method to a low-comm complexity distributed algorithm. Authors also provide theoretical convergence results and empirical evidence to support their claims. Authors also extend their work to problems with block-level orthonormality property.", "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": "We sincerely thank the reviewer for their insightful feedback and constructive comments. Below, we address each point in detail. All newly added experiments can be found in the **Additional Result Sheet (ARS)** https://anonymous.4open.science/r/EF-Landing-B6E4\n\n**1. Landing v.s. Penalty**\n\nThe Landing method can be roughly analogous to the Augmented Lagrangian method, while the Penalty method corresponds to traditional penalty approaches in constrained optimization. Below, we provide a detailed comparison.\n\n**(a). Traditional Penalty Methods: Fundamental Trade-offs**\n   - **Small $\\lambda$ Regime**:\n     - Pros: Preserves fast convergence toward optimality.\n     - Cons: Fails to enforce constraint feasibility.\n   - **Large $\\lambda$ Regime**:\n     - Pros: Easy to ensure strict feasibility.\n     - Cons: Induces ill-conditioning problems and slows convergence.  \n   - **Practical Implementation**:\n     - Delicate schedule-based tuning (e.g., slowly increasing $\\lambda$) is necessary to balance these competing goals. Even then, achieving both fast feasibility and optimality is non-trivial and problem-dependent in practical experiments.\n\n**(b) Landing Method: Decoupling the Trade-off**  \n\n- **Key Advantage**: Employs a *constant, moderate $\\lambda$* (typically $\\lambda = 1$) to **simultaneously** ensure both optimality and feasibility.  \n- **Benefits**:  \n  - Avoids the ill-conditioning issues associated with large $\\lambda$ in penalty methods.  \n  - Eliminates the need for problem-specific $\\lambda$ selection and extensive parameter tuning.  \n\nWhile both Landing and Penalty methods achieve the same asymptotic convergence rate, Landing demonstrates superior experimental performance due to the above benefits. Our new experiments in Figures 1 - 4 in ARS validate this conclusion.\n\n**2. Error Feedback (EF)**\n\n- **Review of Prior Work.** Previous studies [Richtárik et al., 2021; Seide et al., 2014] have shown that vanilla gradient compression using contractive compressors fails to converge in distributed learning when **data heterogeneity** is present. In such cases, EF is necessary to address this issue and ensure convergence.  \n\n- **Unique Challenges in Manifold Optimization.** Our findings reveal—for the first time—that even in a deterministic single-node setting (where no data heterogeneity exists and vanilla gradient compression is expected to converge)—vanilla gradient compression unexpectedly fails when a Stiefel manifold constraint is imposed. This phenomenon highlights a fundamental distinction in manifold-constrained optimization: unlike unconstrained settings where single-node compression succeeds without error feedback, the Stiefel manifold’s geometry introduces additional barrier to gradient compression.\n\nWhile we carefully reviewed [Richtárik et al., 2021], we were unable to locate a discussion of convex constraint sets (e.g., discs). We would greatly appreciate it if the reviewer could direct us to the specific page or section on this point. We can expect that problems with disc constraint may have similar trouble like ours, but this trouble is more crucial for our settings because Stiefel manifold has no unconstrained interior points.\n\n\n**3. Compute Penalty Gradient at Server**\n\nWe thank the reviewer for the valuable insights drawn from decentralized optimization. We agree that computing client-independent terms, such as the penalty term, at the centralized server can also provide motivation for certain aspects of our algorithmic design, and we will include a detailed discussion of this in the revision. However, the central aspect of our analysis is that the orthogonality property, established in Proposition 4.1, is crucial for ensuring convergence guarantees. While the algorithm can indeed be motivated from different perspectives, the convergence guarantees cannot be established without the above orthogonality property.\n\n**4. Theoretical Novelties**\n\nApart from the above clarifications, we summarize other theoretical novelties in our response 4 to Reviewer kbBP.\n\n**5. Other Comments** \n\n- More experiments. Figures 7 & 8 in ARS show comparison with decentralized manifold methods DRSGD and DRGTA. Detailed analysis can be found in our response 1 & 2 to Reviewer kbBP. Figures 1 - 6 in ARS show comparison with penalty method for PCA and NN tasks. It is observed that penalty method fails to reach optimality and feasibility when using a fixed penalty parameter, and it also performs not so good in NN tasks due to the above trade-offs.\n- Violation. The penalty term $\\frac14\\\\|X^\\top X − I_p\\\\|^2$ implies the magnitude of the violation. \n- Hyperparameters. All penalty parameters for Landing are set to 1, and the momentum for the NN experiments is set to 0.9. Step sizes are selected on a case-by-case basis through grid search.\n- We used the notation $X$ to define compressor considering that decision variable and its gradient are of the same shape. But the reviewer’s suggestion is helpful and we will revise it.", "claims_and_evidence": "Most of theoretical claims seem correct. See below for concerns about motivation and experiments.", "methods_and_evaluation_criteria": "1. How is number of violations defined? This is crucial to understand the claims.\n2. How are the hyper parameters for each of the methods tuned? No details are provided to improve confidence in results.\n3. No comparison empirical comparison against these baselines [Chen et al., 2021], [Wang et al., 2022], [Qu et al., 2024], [Zhao et al., 2025]", "theoretical_claims": "Proofs seem correct. Most of the techniques and ideas used in the paper are already known and hence straight-forward.", "experimental_designs_or_analyses": "I don’t fully grasp why penalty method fails here.\n\n1. I have concerns of why more details about the penalty method is not provided. Both EF-Landing and penalty method (of course with appropriate compression and error feedback) have the a regularization weight \\lambda which needs to be tuned.\n2. I would also like to penalty method for the NN result plots. Not sure why they are omitted.\n3. Why is penalty method objective being omitted? Even if the values are in different range it is useful to provide it (at least in appendix if space is limited)", "relation_to_broader_scientific_literature": "See other strengths and weaknesses", "essential_references_not_discussed": "Seem alright. Not familiar with literature enough.", "other_strengths_and_weaknesses": "I have non-trivial concerns about significance and novelty of the work. Most of techniques used are known apriori and this works seems straight forward combinations of them.\n\n1. It is not super clear how landing improves over standard penalty/regularization based methods. This wasn’t discussed in details, and its convergence rate was not compared against. As far as I understand there always exists some value of regularization (penalty) weight that lead to similar approximate constraint satisfaction. Also see other sections concerns about the empirical evidence of same.\n\n2. Another concern is that the failure of compression without error feedback is not special to Stiefel manifold as implied by the authors. Same argument for example work even convex constraints (disc instead of circle) [Richtarik et al., 2021]. It even is known for unconstrained problems [Seide et al., 2014]. So it is slightly misleading for authors to omit these prior knowledge.\n\n3. While it is insightful that compressing the descent direction directly could make the two sub fields non-orthogonal, it is also natural to compute gradient of the penalty term at the centralized server as it is not client-data dependent. This is a standard known practice for regularizer in decentralized optimization. Authors omit this in their discussion of their choice.\n\nDue above concerns and lack of elaboration by authors, I don’t understand what is the novelty of the work.", "other_comments_or_suggestions": "Minor:\n1. Assumption 3.2: better to use a different variable than X to avoid confusion with variable of (1) and argument of compressor.", "questions_for_authors": "Please see above. Summarizing:\n1. Advantage over penalty method both theoretically and empirically\n2. Novelty of the technical ideas and significance of work", "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": "Rcwemwx8pe", "reviewer": "Reviewer_kbBP", "summary": "This paper introduces EF-Landing, a retraction-free and communication-efficient algorithm for distributed stochastic optimization on the Stiefel manifold.", "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": "We sincerely thank the reviewer for their insightful feedback and constructive comments. Below, we address each point in detail. All newly added experiments can be found in the **Additional Result Sheet (ARS)** https://anonymous.4open.science/r/EF-Landing-B6E4\n\n**1. Distributed learning** \n\nDecentralized Learning (DL), Federated Learning (FL), and Compressed Learning (CL) represent three **orthogonal** research directions in communication-efficient distributed learning. Specifically, DL focuses on *which neighbors to communicate with* (topology design), FL addresses *when to communicate* (synchronization frequency), and CL determines *what to communicate* (data/gradient compression). \n\nGiven that these approaches optimize along fundamentally different axes, directly comparing their efficiency or asserting the superiority of one over another might not be appropriate. Each branch presents unique theoretical and practical challenges. Thus, rather than being considered \"outdated,\" each methodology remains relevant depending on the specific problem constraints and system requirements. \n\n**2. Comparison with DL** \n\nWhile it is challenging to determine whether CL or DL is superior in general scenarios, we conduct experiments to compare them in specific settings, where we choose proper topology for DL and compression rate for CL to make the communication quantity per iteration equally matched. Figures 7 & 8 in ARS demonstrate that EF-Landing achieves slightly higher communication efficiency than decentralized manifold methods DRSGD and DRGTA [Chen et al. 2021].\n\n**3. Comparison with FL** \n\nWe appreciate the reviewer for bringing this valuable reference to our attention. We will include it in the related work. Below, we provide a comparison between the two approaches:\n\n- Communication paradigm: Zhang et al. reduce communication overhead through multiple local steps, whereas EF-Landing achieves this via gradient compression. Which approach is more efficient depends on the specific application.  \n- Computational overhead: Zhang et al. rely on manifold projection, which can be computationally expensive, while EF-Landing employs retraction-free methods that involve only matrix products.  \n- Addressing data heterogeneity: Zhang et al. introduce a correction step to mitigate data heterogeneity, whereas EF-Landing leverages error feedback for correction.  \n- Convergence: Zhang et al. do not converge exactly to the stationary solution but only to a neighborhood around it, whereas EF-Landing achieves exact convergence.\n\nFurthermore, we perform additional experiments to compare EF-Landing with Zhang et al. Figures 9 & 10 in ARS show that their performances are roughly equally matched in terms of communication quantities.\n\n**4. Theoretical innovations.**\n\nWe summarize our technical contributions below.\n\n**(a) Reduced Assumptions**  \n- Prior analyses of the Landing method [Ablin et al. 2024] require restrictive assumptions: bounded local Riemannian gradients, bound on an intermediate symmetric matrix, and unbiasedness conditions for specific Riemannian gradients.  \n- **Our Work:** We eliminate these constraints, relying only on standard smoothness and mild gradient bounds (Assumptions 3.1–3.2). This broader generality enables more applications.\n\n**(b) Perturbation-Tolerant Analysis**  \n- Existing Landing convergence guarantees fail under gradient perturbations (e.g., compressed gradients). While trivial in Euclidean settings, perturbations on the Stiefel manifold introduce non-negligible geometric distortion.  \n- **Our Work:** We rebuild the analysis from first principles, introducing a **perturbation-compatible merit function** (Lemma 5.6) that rigorously accounts for compression errors. This is the first provably robust Landing variant for compressed gradients (Theorem 5.7).  \n\n**(c) Block-Wise Orthogonal Constraints**  \n- Prior work assumes fully vectorizable variables, failing to address block-wise constraints (e.g., orthogonality in NN layers).  \n- **Our Work:** We directly tackle block-wise structures (Section 6), proving convergence under a **unified step size** (Theorem K.1). To our knowledge, this is the first analysis for block-wise orthogonal optimization, addressing practical deep learning architectures.\n\n**(d) Gradient Clipping for Safety Guarantees**  \n- Compressed gradients only remain within the safety region in expectation, risking constraint violations.  \n- **Our Work:** A novel clipping strategy enforces deterministic safety without introducing bias.  \n\n**5. Other Comments.**\n- We use the canonical metric of the Stiefel manifold.\n- The necessity of gradient clipping stems from the fact that contractive compressors only guarantee contraction in expectation. There is a small risk of gradient explosion after compression. To ensure the iteration remains within a safe region, we assume bounded gradients (It is fine to overestimate it), with which clipping ensures safety without introducing additional noise.", "claims_and_evidence": "The paper's main claims regarding retraction-free optimization, communication efficiency, and error feedback improving convergence are generally supported by theoretical analysis and empirical results.", "methods_and_evaluation_criteria": "The proposed method is designed for distributed systems and reduces communication via compression. However, it relies on centralized coordination, requiring communication between worker nodes and the master at every iteration, which may limit communication efficiency. A more decentralized approach or a method allowing multiple local iterations before synchronization could further improve efficiency.", "theoretical_claims": "The proofs seem fine.", "experimental_designs_or_analyses": "Within the current distributed setting, it would be beneficial to include a comparison with multiple local updates.\n\nConsider evaluating against methods that incorporate local updates, such as those in Zhang et al. (2024), NeurIPS, which study nonconvex federated learning on compact smooth submanifolds with heterogeneous data.\n\nZhang, J., Hu, J., So, A.M.C. and Johansson, M., 2024. Nonconvex federated learning on compact smooth submanifolds with heterogeneous data. Advances in Neural Information Processing Systems, 37, pp.109817-109844.", "relation_to_broader_scientific_literature": "The paper's main contribution lies in merging communication compression with a retraction-free optimization method. The theoretical analysis primarily follows from error feedback techniques to control errors in the Euclidean gradient, which are then incorporated into existing retraction-free analyses. As a result, the work mainly applies existing technical tools rather than introducing new theoretical insights. Additionally, the considered distributed setting is relatively simple, and extending the approach to more complex decentralized or federated settings would enhance its impact.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "A key weakness is that the main theorems and lemmas largely follow existing results without significant technical difficulty, limiting the novelty of the theoretical contributions. From an algorithmic perspective, the current distributed setting is somewhat outdated, as modern approaches often consider decentralized communication or centralized frameworks with multiple local updates before aggregation.", "other_comments_or_suggestions": "**Equation (2):** Please validate the expression of the Riemannian gradient $\\textrm{grad} f(X)$ by explicitly specifying the associated Riemannian metric used in the derivation.\n\n**Algorithm 1:** Is the gradient clipping with constant $L'$ necessary? If so, how should $L'$ be estimated in practice? Please clarify its role in ensuring convergence.", "questions_for_authors": "N/A", "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": "K0rMfTSrhY", "reviewer": "Reviewer_ytVq", "summary": "The paper introduces EF-Landing, a novel distributed optimization algorithm for stochastic optimization on the Stiefel manifold. EF-Landing is retraction-free and communication-efficient, incorporating gradient compression and error feedback mechanisms. The authors establish sharp convergence guarantees and demonstrate that EF-Landing achieves the same asymptotic linear speedup as existing methods without communication compression. The paper also generalizes EF-Landing to block-wise Stiefel manifolds, enhancing its applicability to structured constraints. Extensive numerical experiments validate the theoretical findings.", "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": "We sincerely thank the reviewer for their insightful feedback and constructive comments. Below, we reiterate our novel contributions which the reviewer had mentioned, provide other theoretical innovations for reference, and show the plan of expanding follow-up experiments.\n\n**1. Reiteration of Contributions.** \n\n- Sharp convergence analysis: Instead of analyzing convergence results case-by-case for different settings, we provided a general convergence result. It can reduce to various specific situations (deterministic or stochastic scenarios, with or without compression, with or without momentum) by choosing different auxiliary constants. When deterministic setting without compression or momentum is chosen, our result exactly corresponds to the result in [Ablin et al. 2024].\n\n- Block-wise generalization: Prior work for deep learning assumes fully vectorizable variables, failing to address block-wise constraints (e.g., orthogonality in neural network layers). Our work, however, directly tackles block-wise structures (Section 6), proving convergence under a unified step size (Theorem K.1). To our knowledge, this is the first analysis for block-wise orthogonal optimization, addressing practical deep learning architectures.\n\n- Extensive experiments: Prior work concerned with optimization on Stiefel manifolds mainly focuses on traditional problems like PCA. We reviewed the more general application of orthogonal constraints to deep learning, and conducted extensive experiments on diverse deep learning tasks. Brilliant results demonstrated the applicability and efficiency of our algorithm.\n\n\n**2. Other Theoretical Innovations.**\n\nApart from the insights the reviewer had mentioned, we also summarize more of our technical contributions below. We hope these align with the reviewer’s expectation.\n\n**(a) Reduced Assumptions.**  \n- Prior analyses of the Landing method [Ablin et al. 2024] require restrictive assumptions: bounded local Riemannian gradients, explicit bounds on intermediate symmetric matrices, and unbiasedness conditions for specific Riemannian gradients.  \n- **Our Work:** We eliminate these constraints, relying only on standard smoothness and mild gradient bounds (Assumptions 3.1–3.2). This broader generality enables more applications.  \n\n**(b) Perturbation-Tolerant Analysis.**  \n- Existing Landing convergence guarantees fail under gradient perturbations (e.g., compressed gradients). While trivial in Euclidean settings, perturbations on the Stiefel manifold introduce non-negligible geometric distortion.  \n- **Our Work:** We rebuild the analysis from first principles, introducing a **perturbation-compatible merit function** (Lemma 5.6) that rigorously accounts for compression errors. This is the first provably robust Landing variant for compressed gradients (Theorem 5.7).  \n\n**(c) Gradient Clipping for Safety Guarantees.**  \n- Compressed gradients only remain within the safety region in expectation, risking constraint violations.  \n- **Our Work:** A novel clipping strategy enforces deterministic safety without introducing bias. \n\n**3. Additional experiments.**\n\nAll newly added experiments can be found in the **Additional Result Sheet (ARS)** https://anonymous.4open.science/r/EF-Landing-B6E4. Figures 5 & 6 add the comparison of EF-Landing Algorithm and Penalty Method using VGG16 and ResNet18 on CIFAR-10, which further shows the efficiency of our algorithm. Moreover, we are expected to conduct more experiments, where more diverse datasets, more application scenarios, comparisons among more relevant methods are all taken into consideration.\n\nWe again appreciate the reviewer for the valuable feedback and for recognizing the contributions of our work.", "claims_and_evidence": "The main claims of the paper are:\n1.\tEF-Landing is the first retraction-free and communication-efficient algorithm for distributed stochastic optimization on the Stiefel manifold.\n2.\tThe algorithm ensures convergence while significantly reducing communication overhead.\n3.\tThe convergence rate of EF-Landing matches that of existing methods without communication compression.\n4.\tThe method generalizes to block-wise Stiefel manifolds, extending its practical applicability.\nThe claims are well-supported by theoretical proofs and numerical experiments. The convergence guarantees are rigorously derived, and extensive experiments confirm that EF-Landing performs comparably to existing methods while reducing communication costs. The inclusion of error feedback ensures stability and accuracy despite compression.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem. The authors use standard theoretical tools from optimization on manifolds to establish the convergence guarantees and rates for EF-Landing. The experimental evaluation includes benchmark problems such as distributed online PCA and deep learning tasks. The comparison with existing methods, including QR retraction and vanilla Landing methods, provides a solid basis for evaluating EF-Landing's effectiveness.", "theoretical_claims": "The theoretical claims of convergence analysis are well-supported by rigorous proofs. The convergence analysis begins by presenting the necessary conditions, then proceeds to establish the convergence guarantees and rates for EF-Landing. The authors present the standard assumptions for optimization on the Stiefel manifold, supporting lemmas and main convergence theorem. Besides, the authors establish convergence rate in deterministic scenario and stochastic scenario.", "experimental_designs_or_analyses": "The experimental design is sound. The authors provide experiments on two groups of problems: the distributed online PCA for deterministic scenario and deep learning using VGG16 neural network architecture with orthogonal constraints applied to the convolutional layers for stochastic scenario, comparing EF-Landing with other algorithms for optimization on Stiefel manifold, including vanilla Landing, QR retraction. The experiments are well-structured, demonstrating the effectiveness of EF-Landing in terms of both convergence rate and communication efficiency.", "relation_to_broader_scientific_literature": "The paper is well-situated within the broader literature on optimization on manifolds, distributed optimization, and communication-efficient training. It builds on prior work in these areas and makes a novel contribution by integrating error feedback with retraction-free optimization. The references to previous work, such as the Landing method and communication-efficient distributed optimization techniques, are appropriate.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n•\tThe paper provides sharp theoretical convergence guarantees for EF-Landing.\n•\tThe convergence rate of EF-Landing matches that of existing methods without communication compression.\n•\tThe method generalizes to block-wise Stiefel manifolds, extending its practical applicability.\n\nWeaknesses:\n•\tExperimental evaluation could be expanded to include more diverse datasets and application scenarios.", "other_comments_or_suggestions": "•\tExpanding experiments to additional machine learning tasks could further strengthen the empirical validation.", "questions_for_authors": "N/A", "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 authors study distributed optimization on the Stiefel manifold and propose an algorithm that combines the recently introduced Landing method with the well-established error-feedback technique from federated optimization, aimed at reducing communication costs. The paper includes convergence guarantees, a generalization to block-wise constraints, and empirical evaluation. Since the individual algorithmic components are known, the theoretical results are not particularly surprising. Reviewers raised concerns regarding insufficient discussion of related work, unclear technical novelty, lack of justification for certain algorithmic choices, and missing empirical comparisons. In the rebuttal, the authors provided additional empirical results and explanations, which partially addressed these issues. I strongly encourage the authors to thoroughly address these concerns in the next revision.
Decision: Accept (poster)