{"id":"4c24236c-2c7a-4405-b869-97d8f692dd84","arxiv_id":"2505.12378","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A randomized submanifold descent on the Stiefel manifold reduces retraction cost to O(r^3) and achieves O(n^2 r^{-2} / k) expected convergence for smooth nonconvex functions.","lead":"This paper introduces a randomized Riemannian optimization method that updates an orthogonally constrained variable on a random low-dimensional submanifold, cutting per-iteration retraction cost from O(np^2) to O(nr^2) or O(npr). It supplies convergence rates for nonconvex, Polyak-Lojasiewicz, and stochastic settings, with experiments on PCA, Procrustes, quadratic assignment, and orthogonal neural networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"High-probability orthogonal guarantee is overstated: the factor 1−τ is not Θ(1) and can be O(r⁴/n⁴), so Table 1's rate and Remark 5.10's iteration overhead for the orthogonal high-probability bound are incorrect for small r.","rationale":"I read the paper in good faith. The core expectation convergence (Theorem 5.7) and the per-iteration complexity analysis appear sound: Proposition 5.5's identity checks out, Lemma 5.3's factor 1/2 is correct for the Stiefel embedding, and the descent arguments telescope properly. The proposed method is concrete, reproducible code is provided, and the experiments support the central efficiency claim. The reader's weakest assumption (Assumption 5.1) is less concerning than stated, because any C² function on the compact Stiefel manifold automatically has bounded Euclidean gradient and Hessian on the constraint set; the assumption only excludes genuinely nonsmooth objectives, which are outside the main theory anyway. The load-bearing issue I found is in the high-probability contribution. Theorem 5.9 itself explicitly contains the factor 1−τ, and with 1−τ possibly as small as Θ(r⁴/n⁴) the bound degrades substantially; the problem is that Table 1 and Remark 5.10 drop this factor by claiming 1−τ = Θ(1), which is false. This is a genuine correctness issue in the presentation of one of the two advertised convergence guarantees, and it affects the claimed trade-off between permutation and orthogonal sampling. The fix is straightforward—either carry the 1/(1−τ) factor through Table 1 and the iteration-count discussion, or state a lower bound r = Ω(n) for the Θ(1) simplification—so I recommend conditional acceptance rather than rejection. I would not change the verdict on the expectation result, which remains the strongest claim in the paper.","tokens_in":35309,"tokens_out":42597,"duration_ms":453646,"concrete_test":"Evaluate τ(n,r) at n=1000, r=2: τ = exp(−4/(2048·10⁶·999²)) ≈ 1−1.95×10⁻¹⁵, so 1−τ ≈ 2×10⁻¹⁵, contradicting the claim 0.0005 ≤ 1−τ ≤ 1. Then recompute Table 1's orthogonal high-probability global entry directly from Theorem 5.9: replace O(n²/(r²k)) with O(n²/(r²(1−τ)k)); for n=1000, r=2 this changes the iteration complexity from O(n²ε⁻²) to about O(n⁶ε⁻²). Also check whether Proposition D.1's exponent should be 2048 n²(n−1) instead of 2048 n²(n−1)², following the arithmetic in its proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 5.9's orthogonal high-probability bound is min_i ||gradF(X_i)||² ≤ 16LΔ0 n(n−1)/(k(1−τ)r(r−1)) with probability at least 1−exp(−(1−τ)k/8), where τ = exp(−r²(r−1)²/(2048 n²(n−1)²)). The proof's Remark 5.10 asserts τ ∈ (0,0.9995) and therefore 1−τ = Θ(1). The inequality is reversed: for all admissible r, 0 < 1−τ ≤ 1−e^{−1/2048} ≈ 4.88e−4, and for r=2, 1−τ ≈ 1/(512 n⁴). Hence 1−τ is not uniformly Θ(1); it is O(r⁴/n⁴) when r ≪ n. Consequently, the claimed O(n²/(r²k)) high-probability rate in Table 1 carries an omitted 1/(1−τ) factor, and the number of iterations needed before the stated success probability becomes non-negligible is Ω(n⁴/r⁴), not Θ(1). This does not invalidate the expectation guarantee (Theorem 5.7), and the theorem statement itself is correct with the explicit 1−τ, but the advertised high-probability convergence and the trade-off with permutation sampling are materially weaker than presented for small submanifold dimension r.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes RSDM, a randomized Riemannian submanifold method for minimizing a smooth function F over the Stiefel manifold St(n,p). At each iteration the algorithm samples an orthogonal or permutation matrix P_k, restricts the update to a random O(r) submanifold through the parameterization U_k(Y)=P_k^T diag(Y,I_{n-r})P_k, performs a retraction step on O(r) using the projected Riemannian gradient, and sets X_{k+1}=U_k(Y_k)X_k. The advertised contributions are a reduction in per-iteration cost from O(np^2) to O(nr^2) (permutation sampling) or O(npr) (orthogonal sampling), convergence guarantees in expectation and high probability for general nonconvex objectives, linear convergence under a Riemannian PL condition, stochastic and finite-sum extensions, a deterministic variant with exact convergence, and an extension to quotient manifolds such as Grassmann and flag manifolds. The theoretical core is Proposition 5.5, which identifies the expected squared norm of the projected gradient as r(r-1)/(n(n-1)) times the full-space quantity, and the subsequent descent and telescoping arguments. The paper also reports experiments on Procrustes problems, PCA, quadratic assignment, and orthogonal neural networks, with code made available.","tokens_in":35570,"tokens_out":14796,"duration_ms":140726,"significance":"If the results stand, RSDM is a genuinely useful approach for large-scale optimization with orthogonality constraints: it has a simple implementation, a clean and parameter-free gradient-scaling identity (Proposition 5.5), and a total complexity that matches Riemannian gradient descent in the regime p=Omega(n), while avoiding expensive retractions on the full Stiefel manifold. The paper is also valuable for clearly isolating the trade-off between cheap permutation sampling and more expensive orthogonal sampling. The expectation bounds, PL analysis, stochastic analysis, and quotient-manifold extension are well structured. The main weakness is in the high-probability statements: the factor 1-tau in Theorem 5.9 is not uniformly Theta(1), so the advertised high-probability rate and the claimed O(1) iteration overhead in Remark 5.10 and Table 1 are overstated. The expectation-based central claims are not affected by this issue.","major_comments":[{"comment":"The orthogonal high-probability bound is presented as O(n^2/(r^2 k)) with success probability at least 1-exp(-(1-tau)k/8), where tau = exp(-r^2(r-1)^2/(2048 n^2(n-1)^2)). Remark 5.10 claims that tau in (0,0.9995) implies 1-tau = Theta(1), but the inequality runs in the opposite direction: for all admissible r one has 0 < 1-tau <= 1-exp(-1/2048) approx 4.88e-4, and for r << n one has 1-tau = O(r^4/n^4). Consequently the high-probability gradient bound in Theorem 5.9 contains an omitted factor 1/(1-tau), the stated success probability is non-negligible only once k = Omega(n^4/r^4), and the Table 1 high-probability entry O(n^2/(r^2 k)) together with the orthogonal/permutation trade-off in Remark 5.10 is not supported as written. The statement of Theorem 5.9 with the explicit 1/(1-tau) is formally valid, and the expectation guarantee in Theorem 5.7 is unaffected; the issue is in the advertised simplification and in Table 1.","section":"Theorem 5.9, Remark 5.10, Table 1"},{"comment":"The displayed concentration inequality P(h(X) <= r(r-1)/(n(n-1))||M||^2 - t) <= exp(-(n-1)t^2/(512||M||^4)) is not algebraically consistent with the stated conclusion exp(-r^2(r-1)^2/(2048 n^2(n-1)^2)). Substituting t = (1/2) r(r-1)/(n(n-1)) ||M||^2 gives exponent -r^2(r-1)^2/(2048 n^2(n-1)), which differs from the stated exponent by a factor (n-1). Since this tau is exactly the quantity used in Theorem 5.9, the proof needs to be corrected: either the concentration inequality as quoted from Gotze and Sambale has a different coefficient, or the exponent in Proposition D.1 must be revised.","section":"Appendix D.4, proof of Proposition D.1"}],"minor_comments":[{"comment":"In the orthogonal-sampling proof of Proposition 5.5, the displayed line after Eq. (8) uses a plus sign before E[P_{i1}P_{j1}P_{i2}P_{j2}]; from Eq. (8) this term is negative, and the final value E||grad eF_X(I_r)||^2 = (r^2-r)/(n^2-n) ||grad F_X(I_n)||^2 requires a minus sign. The final result is correct, but the displayed equality as written is not.","section":"Appendix D.3, Eq. (9)"},{"comment":"The permutation-sampling entry in the EXPECTATION columns appears to include the binomial factor binom(n,r), which would contradict Theorem 5.7 and Remark 5.8 where the expectation rate is O(n^2/(r^2 k)) for both sampling strategies. Please align the table with the theorem statements.","section":"Table 1"},{"comment":"The sentence 'Assumption 5.1 is naturally satisfied given X in St(n,p), which is a compact submanifold' is only valid if F is defined and smooth on a neighborhood of the Stiefel manifold. If F is only Riemannian smooth on St(n,p), the assumed bound on the ambient Euclidean Hessian is an additional regularity condition and should be stated as such.","section":"Assumption 5.1"},{"comment":"The expression 'k >= 4000 log(1/delta') delta'^{-2} = eOmega(1)' appears to contain a typo: the right-hand side should be a constant depending on delta', not a quantity that grows with n and r. This is related to the incorrect Theta(1) claim for 1-tau in the same remark.","section":"Remark 5.10"}],"recommendation":"major_revision","confidential_remarks":"The expectation-based theory is solid and the paper has real value, but the high-probability claims in Theorem 5.9, Remark 5.10, and Table 1 need a substantive correction, not just copyediting, because the factor 1-tau can be as small as O(r^4/n^4). I would like to see the revised version before acceptance; the central expectation results and the experiments can be preserved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper is a genuine and mostly solid contribution to Riemannian optimization on the Stiefel manifold. The core idea — restricting each update to a random r-dimensional submanifold via the orthogonal-group action, with permutation or Haar sampling — is new relative to the coordinate-descent literature, and the per-iteration complexity savings are real. The main expectation result (Theorem 5.7) is correct, and the proof via Proposition 5.5 is a nice two-strategy derivation. The experiments are honest, including the p≪n regime where the method loses to RGD; the code is available.\n\nThe soft spots are real but bounded. The one that matters: the high-probability orthogonal guarantee in Theorem 5.9 is stated with an explicit 1/(1−τ) factor, but Remark 5.10 asserts 1−τ = Θ(1). That is wrong. τ = exp(−r²(r−1)²/(2048 n²(n−1)²)), so for all admissible r, 1−τ ≤ 1−e^{−1/2048} ≈ 4.9·10⁻⁴, and for small r the bound is O(r⁴/n⁴). The inequality in the remark is reversed. Thus Table 1's high-probability column drops a load-bearing factor, and the iteration count needed to get a non-negligible success probability is Ω(n⁴/r⁴), not Θ(1) as the remark claims. The theorem statement itself is correct; the advertised interpretation is not. The fix is straightforward: correct Remark 5.10 and Table 1, and either avoid claiming Θ(1) or redesign the high-probability argument for the small-r regime.\n\nOther concerns are minor. Assumption 5.1 asks for bounded Euclidean gradient and Hessian, which is stronger than Riemannian smoothness; it is not a fatal restriction on the compact Stiefel manifold, but the paper should be explicit that all rates depend on it. The permutation high-probability bound is weak, and the authors already acknowledge that. The sign typo in the Proposition 5.5 proof is cosmetic.\n\nNet assessment: the central contribution — expectation-rate RSDM with two practical sampling schemes, matching RGD's total complexity in the p=Ω(n) regime — holds up. The high-probability orthogonal story needs repair, but it is not the paper's load-bearing wall. This is a useful paper for anyone working on scalable methods for orthogonality-constrained problems, and it deserves a serious referee. I would accept it after minor revisions, with the high-probability issue fixed.","headline":"A solid and useful randomized submanifold method for orthogonality-constrained problems whose expectation guarantees hold up, but whose high-probability orthogonal guarantee is overstated for small r due to a reversed inequality on 1−τ.","tokens_in":36144,"tokens_out":4084,"would_cite":true,"duration_ms":36864,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C30","65K05","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"Low-dimensional random submanifold updates cut the retraction cost of Riemannian optimization under orthogonality constraints from $O(np^2)$ to $O(r^3)$ while preserving convergence.","keywords":["randomized Riemannian submanifold descent","Stiefel manifold","orthogonality constraint","retraction complexity","permutation sampling","orthogonal sampling","Polyak-Lojasiewicz condition","stochastic optimization"],"falsifier":"Sample $P$ uniformly from the Haar distribution on $O(n)$ and, for a fixed skew-symmetric matrix $M$, estimate $\\mathbb{E}\\|P(r)MP(r)^\\top\\|^2/\\|M\\|^2$ by Monte Carlo; Proposition 5.5 predicts exactly $r(r-1)/(n(n-1))$, and the same value for uniform permutation sampling. A stable discrepancy beyond sampling error would falsify the identity on which every convergence theorem in the paper depends.","tokens_in":35068,"feed_emoji":"🎲","tokens_out":15038,"duration_ms":130257,"temperature":0.7,"pith_summary":"Riemannian optimization on the Stiefel manifold — the set of $n\\times p$ column-orthonormal matrices — routinely pays for a retraction that costs at least $O(np^2)$ per iteration, which becomes prohibitive as $n$ and $p$ grow. This paper proposes instead to move along a low-dimensional random submanifold of the orthogonal group, using an update of the form $X_{k+1}=U_k(Y_k)X_k$ with $U_k(Y)=P_k^\\top\\mathrm{diag}(Y,I_{n-r})P_k$; the retraction is then performed on $O(r)$ instead of $O(n)$, at cost $O(r^3)$. The authors prove that the expected squared norm of the submanifold gradient is exactly $\\frac{r(r-1)}{n(n-1)}$ times the squared norm of the full Riemannian gradient, and from this identity they derive convergence to an $\\epsilon$-stationary point in $O(n^2 r^{-2}\\epsilon^{-2})$ iterations, with per-iteration cost $O(nr^2)$ for permutation sampling and $O(npr)$ for orthogonal sampling. If the analysis is right, RSDM is a scalable alternative to retraction-based Riemannian gradient descent whose total complexity matches RGD when $p$ is on the order of $n$.","feed_headline":"Random submanifold steps match full-gradient descent at lower cost","feed_subtitle":"For large problems it reaches an epsilon-stationary point in O(n^3/epsilon^2) work.","key_machinery":"The load-bearing device is the conjugation parameterization $U_k(Y)=P_k^\\top\\mathrm{diag}(Y,I_{n-r})P_k$ together with the gradient projection identity $\\mathrm{grad}\\tilde F_k(I_r)=P_k(r)\\,\\mathrm{grad}F_k(I_n)\\,P_k(r)^\\top$, where $P_k(r)$ is the first $r$ rows of the sampled matrix. This identity turns a random step on $O(r)$ into a two-sided random projection of the full skew-symmetric gradient; the expectation of its squared norm is exactly the ratio $r(r-1)/(n(n-1))$, the factor that appears in every iteration bound. Lemma 5.2 transfers Assumption 5.1, bounded Euclidean gradient and Hessian in the ambient space, into $L$-smoothness of the pulled-back function on $O(r)$, and Lemma 5.3 controls the full gradient by the pulled-back gradient, so the descent inequality is the same as for Riemannian gradient descent with an extra dimension ratio.","core_discovery":"The paper's central claim is that the retraction bottleneck in optimization over the Stiefel manifold $\\mathrm{St}(n,p)=\\{X\\in\\mathbb{R}^{n\\times p}:X^\\top X=I_p\\}$ can be bypassed by randomizing the search direction. Each iteration samples an orthogonal or permutation matrix $P_k$ and restricts the update to the random submanifold $U_k(Y)=P_k^\\top\\mathrm{diag}(Y,I_{n-r})P_k$ with $Y\\in O(r)$; the next iterate is $X_{k+1}=U_k(Y_k)X_k$. The key quantitative fact is Proposition 5.5: for either sampling distribution, $\\mathbb{E}\\|\\mathrm{grad}\\tilde F_k(I_r)\\|^2 = \\frac{r(r-1)}{n(n-1)}\\|\\mathrm{grad}F_k(I_n)\\|^2$, and Lemma 5.3 gives $\\|\\mathrm{grad}F_k(I_n)\\|^2\\ge \\tfrac{1}{2}\\|\\mathrm{grad}F(X_k)\\|^2$. Theorem 5.7 then yields the expected sublinear rate $\\min_{i