Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold

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.

1. Reiteration of Contributions.

• 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].

• 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.

• 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.

2. Other Theoretical Innovations.

Apart 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.

(a) Reduced Assumptions.

• 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.
• 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.

(b) Perturbation-Tolerant Analysis.

• 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.
• 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).

(c) Gradient Clipping for Safety Guarantees.

• Compressed gradients only remain within the safety region in expectation, risking constraint violations.
• Our Work: A novel clipping strategy enforces deterministic safety without introducing bias.

3. Additional experiments.

All 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.

We again appreciate the reviewer for the valuable feedback and for recognizing the contributions of our work.

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

1. Distributed learning

Decentralized 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).

Given 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.

2. Comparison with DL

While 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].

3. Comparison with FL

We 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:

• 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.
• 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.
• Addressing data heterogeneity: Zhang et al. introduce a correction step to mitigate data heterogeneity, whereas EF-Landing leverages error feedback for correction.
• 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.

Furthermore, 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.

4. Theoretical innovations.

We summarize our technical contributions below.

(a) Reduced Assumptions

• 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.
• 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.

(b) Perturbation-Tolerant Analysis

• 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.
• 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).

(c) Block-Wise Orthogonal Constraints

• Prior work assumes fully vectorizable variables, failing to address block-wise constraints (e.g., orthogonality in NN layers).
• 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.

(d) Gradient Clipping for Safety Guarantees

• Compressed gradients only remain within the safety region in expectation, risking constraint violations.
• Our Work: A novel clipping strategy enforces deterministic safety without introducing bias.

5. Other Comments.

• We use the canonical metric of the Stiefel manifold.
• 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.

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

1. Landing v.s. Penalty

The 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.

(a). Traditional Penalty Methods: Fundamental Trade-offs

• Small $\lambda$ Regime:
  • Pros: Preserves fast convergence toward optimality.
  • Cons: Fails to enforce constraint feasibility.
• Large $\lambda$ Regime:
  • Pros: Easy to ensure strict feasibility.
  • Cons: Induces ill-conditioning problems and slows convergence.
• Practical Implementation:
  • 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.

(b) Landing Method: Decoupling the Trade-off

• Key Advantage: Employs a constant, moderate $\lambda$ (typically $\lambda = 1$) to simultaneously ensure both optimality and feasibility.
• Benefits:
  • Avoids the ill-conditioning issues associated with large $\lambda$ in penalty methods.
  • Eliminates the need for problem-specific $\lambda$ selection and extensive parameter tuning.

While 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.

2. Error Feedback (EF)

• 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.

• 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.

While 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.

3. Compute Penalty Gradient at Server

We 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.

4. Theoretical Novelties

Apart from the above clarifications, we summarize other theoretical novelties in our response 4 to Reviewer kbBP.

5. Other Comments

• 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.
• Violation. The penalty term $\frac14\\|X^\top X − I_p\\|^2$ implies the magnitude of the violation.
• 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.
• 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.