acceptodds
Under review as a conference paper at ICLR 2027

PLADOS: A Parameter-free Landing Algorithm for Decentralized Optimization on the Stiefel Manifold

Abstract

Decentralized optimization on the Stiefel manifold has broad applications in machine learning and signal processing. We propose PLADOS, a parameter-free landing algorithm for decentralized optimization on the Stiefel manifold. Each iteration combines local stochastic gradient updates with a single retraction-free communication step over the communication graph. A key convex-like property of the intersection of the nonconvex Stiefel manifold and consensus constraints is characterized through a restricted secant inequality for the penalty-only scheme, ensuring local contraction of the manifold consensus error without introducing additional parameters that require tuning. For nodes using independent local batches of size , we prove that PLADOS achieves linear speedup with respect to the number of nodes with an asymptotic convergence rate of after iterations, where is the sampling variance and quantifies gradient heterogeneity. Experiments demonstrate stability across tested stepsizes and networks, time efficiency, and linear speedup with respect to the number of nodes.

Primary area:
optimization
Keywords:
Decentralized optimization, Stiefel manifold, Retraction-free methods, Linear speedup, Data heterogeneity.

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_rLuZOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

PLADOS performs, per iteration, a polynomial landing map ϕ(X)=X−13X(X⊤X−I)\phi(X)=X-\tfrac13X(X^\top X-I), one gossip round, and a projected stochastic gradient step, with no retraction. With the fixed coefficient γ=1/3\gamma=1/3, the penalty-only map satisfies a restricted secant inequality and contracts locally toward the consensus Stiefel manifold at any rate ρ>max⁡{σ2(W),1/3}\rho>\max\{\sigma_2(W),1/3\}. Combined with a polar-projection expansion, the stochastic analysis gives an average squared Riemannian gradient bound of O(σ/nbK+(nξ2)1/3K−2/3+n2/K)O(\sigma/\sqrt{nbK}+(n\xi^2)^{1/3}K^{-2/3}+n^2/K). Experiments cover PCA (synthetic, MNIST) and low-rank matrix completion with up to 32 MPI nodes, compared against DRSGD.

Critical strengths

(1) An elegant geometric core. The tangent/normal decomposition of DFDF at the consensus manifold yields a fixed-representative contraction equivalent to an RSI, with explicit radius conditions. The polar-projection expansion with a product remainder is a reusable tool. (2) To my knowledge it is the first tracker-free stochastic decentralized landing method on the Stiefel manifold with a speedup-type guarantee, using one communication round per step.

Critical weaknesses

(1) “Parameter-free” sounds too strong. Only the landing coefficient γ=1/3\gamma=1/3 is fixed, while the stepsize remains the main parameter of the method, and the convergence depends on it critically. For the diminishing schedule αk=α0/k+1\alpha_k=\alpha_0/\sqrt{k+1}, convergence itself is natural; but the speed of convergence is governed by α0\alpha_0. In Corollary 3.8, the optimization term scales as 1/α01/\alpha_0 and the network term as nα02n\alpha_0^2. For the constant step used in the speedup result, the method converges only to a neighborhood of size C2nα2ξ2C_2n\alpha^2\xi^2 (eq. 107), which is clearly visible as the plateaus in Fig. 4. So both the level the method converges to and the speed of convergence depend critically on α0\alpha_0. On top of that, the guarantees hold only for α0≤αˉ\alpha_0\le\bar\alpha (eq. 105), and αˉ\bar\alpha is determined by constants (RR, GG, CdC_d, CgC_g, C0C_0, ChC_h, nn) that a practitioner cannot compute, so the admissible stepsize is unknown and tuning cannot be avoided. It is therefore unclear to me how the method can be positioned as parameter-free (including the contrast with DRSGD in Table 1 and the claim to answer Byrd & Nocedal’s question) when its convergence critically depends on its main parameter α0\alpha_0. Relatedly, all guarantees are local, and the speedup regime requires K≳n5b/σ2K\gtrsim n^5b/\sigma^2, far beyond the tested budgets. (2) From the experiments, the benefit of PLADOS over DRSGD is not clear. PLADOS outperforms DRSGD at identical stepsizes (Fig. 2a,b; Appendix D.2), but it is not at all clear that this implies PLADOS is the better method: the best α0\alpha_0 need not coincide for the two methods. The wall-clock gain may simply reflect the cheaper retraction-free iteration, which matters little at r=5r=5, and the appendix itself reports only a “slight advantage.” It would be much more interesting to compare a tuned DRSGD with a tuned PLADOS, e.g., time-to-accuracy with each method at its best stepsize. The comparison also omits other relevant baselines (DRGTA, DESTINY, DRFGT, RF-EXTRA, EF-Landing). In addition, the LRMC step coefficients were chosen after an initial comparison and scale as n\sqrt n by design, so the reported wall-clock speedup partly reflects the stepsize choice.

Questions for authors

Clarifications that could affect my assessment:

(a) How sensitive is PLADOS to α0\alpha_0 in practice, and how should α0\alpha_0 be chosen when αˉ\bar{\alpha} depends on unknown constants? In what precise sense is the method parameter-free?

(b) Please compare PLADOS and DRSGD with each method's stepsize tuned separately (e.g., best α0\alpha_0 per method on a common grid), reporting time-to-accuracy and per-iteration cost.

(c) What happens outside the local tube, e.g., with random initialization?

Suggestion on presentation:

(d) Algorithm 1 is quite hard to read. It refers to equation (2), which in turn uses the operator PXP_{X}, and PXP_{X} is defined only inline in the introductory paragraph of Section 2, which makes it very hard to find. I would strongly recommend writing the explicit formulas inside Algorithm 1, including Si,k=PXi,k(1b∑ℓ=1b∇Fi(Xi,k;ζi,k(ℓ)))S_{i,k} = P_{X_{i,k}}\left(\frac{1}{b}\sum_{\ell=1}^{b} \nabla F_{i}(X_{i,k}; \zeta_{i,k}^{(\ell)})\right) and PXU=U−Xsym(X⊤U)P_{X}U = U - X \mathrm{sym}(X^{\top}U), with short comments on what happens at each step (stochastic gradient, landing correction, gossip, update). Also, since the iterates Xi,kX_{i,k} are infeasible, PXi,kP_{X_{i,k}} is in general not idempotent; as noted in Section 2, it coincides with the tangent projection only at feasible points. A short remark on its role at infeasible iterates (e.g., as an approximation to the tangent projection at the nearby feasible point Xˉk\bar{X}_{k}, cf. (58)) would make the update easier to interpret.

Reviewer_QJg1OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a parameter-free landing method for decentralized optimization on the Stiefel manifold. Each iteration applies a landing map with a fixed coefficient to the local parameter matrices before communication, followed by a local stochastic gradient update. The authors establish convergence guarantees and asymptotic linear speedup with respect to the number of nodes under the stated assumptions. The method is evaluated on both synthetic and real-world datasets.

Critical strengths
  1. PLADOS has a simple retraction-free update. Its landing correction uses only matrix multiplications and additions, avoiding the matrix factorizations required by standard retractions.
  2. The paper establishes stochastic convergence guarantees and asymptotic linear speedup with respect to the number of nodes, using a single communication round per iteration without gradient tracking.
  3. The experimental results demonstrate the computational efficiency of PLADOS compared with DRSGD on the tested problems.
Critical weaknesses
  1. Since decentralized retraction-free methods have been well studied in DESTINY and DRFGT, and the centralized parameter-free landing has been studied in Man-LoRA, the novelty of the proposed method appears limited. The paper should clearly explain the advantages as well as technical advances in the analysis over existing results.
  2. The experiments provided in the paper are limited to comparison with DRSGD. Comparisons with relevant decentralized retraction-free methods, such as DESTINY and DRFGT, would help establish the practical benefits of PLADOS beyond retraction-free.
Questions for authors
  1. What are the key technical advances over existing landing and consensus analyses?
  2. How does PLADOS compare empirically with DESTINY and DRFGT?
  3. Why is the landing coefficient set to γ=1/3\gamma=1/3, and would other choices yield similar guarantees?
Reviewer_q4R3OpenReview ↗
Rating
3
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents PLADOS, a parameter-free algorithm to solve decentralized optimization problems with manifold constraints. The authors first formulate the problem in a decentralized and constrained manner, and revisited the algorithms in this line of research to showcase the limitations. Then they propose Algorithm 1 which does not require further tuning on stepsizes in the constraints part. Convergence rates and complexity are given in the main theorems, and some experiments are reported to demonstrate the effectiveness of their methods.

Critical strengths
  1. From a theoretical perspective this paper is solid and sound. The assumptions as well as the proof techniques are well explained and presented. The convergence proofs are solid and correct.

  2. Experimental results cover some common problems including PCA, matrix completion, and are solid.

Critical weaknesses
  1. The weaknesses are clear and standard in this line of research in academia. It is not that this paper has critical issues, but the decentralized optimization as a whole technique may have limited applications in real world as of now and usually papers in this area have incremental contributions and are combinations of existing setups:

    (a) Most of the experiments setup in this paper are simple -- PCA, low-rank matrix completion, and MNIST.

    (b) The novelty of the proof techniques is limited -- manifold-constrained optimization, linear speedup in decentralized optimization, and parameter-free optimization, etc. all these techniques are standard in optimization literature.

  2. Some concerns about Table 1:

    (a) It might be good to specify gamma before writing it in the footnote of Table 1.

    (b) Table 1 is only limited to some decentralized algorithms and many important ones, for example [1], are missing.

    (c) Parameter-free definition refers to the stepsizes used in constraints. This might be different from prior work's definition. For example [2]. The authors may want to clarify in the paper.

References

[1] Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent

[2] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization

Questions for authors
  1. Decentralized optimization, and maybe another related topic federated optimization, might have limited applications in practice and thus wondering authors' thoughts or comments on the following: (a) for example most large-scale distributed training in industry still uses all-to-all communication while without the need of a decentralized network, and thus it is still unclear if there is other reason, other than its theoretical beauty, that decentralized network is needed for industrial applications. (b) experiments presented in this paper are mostly synthetic ones or with simple dataset like MNIST. Are there large-scale datasets examples in literature since the advantages of decentralized optimization were proven in [1] in 2017?

  2. Any examples that neural network training requires manifold constraints?

References

[1] Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.