{"id":"9f5aa15d-07b9-4eb2-8809-74616e4e0fda","arxiv_id":"2412.20008","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A new sixth-order penalty function makes stochastic optimization over expectation-formulated generalized Stiefel manifolds equivalent to unconstrained optimization, enabling stochastic gradient methods with O(epsilon^-4) sample complexity.","lead":"This paper presents a penalty function that turns a stochastic optimization problem on a curved matrix space into an unconstrained one, and provides stochastic gradient algorithms with convergence guarantees. A generalist reader might care because it offers a practical path for canonical correlation analysis and other statistical learning tasks where the constraints are known only through random samples.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Even granting the a priori boundedness assumptions, the O(ε^-4) guarantee only certifies ε-stationarity of the penalty h; infeasible strict saddles of h satisfy it, so the claimed reduction to SOEGS is unproven.","rationale":"I retain the reader's CONDITIONAL verdict, but for a different reason. The reader's weakest assumption, Assumption 4.1(3)-(4), is real: the paper assumes bounded iterates and gradient estimates without an algorithmic mechanism enforcing them. However, the scalar counterexample above shows that even when those assumptions hold, the sample-complexity theorems do not imply an approximate solution of SOEGS. Theorems 4.6 and 4.11 only deliver an ε-first-order stationary point of the penalty h, and Theorem 3.12 explicitly admits infeasible strict saddles of h as first-order stationary points. Since the paper provides no saddle-escape analysis for CDFSG or CDFSG-Ada, and since Theorem 3.16's conversion to SOEGS stationarity requires the unverified condition X∈Ω_{1/6}, the central applied claim that these algorithms solve SOEGS is not established by the written proof. The equivalence results in Section 3 appear plausible, and the algorithmic sample-complexity statements for CDFCP may be correct, so the appropriate verdict remains conditional: the paper should either prove that the stochastic iterates avoid infeasible strict saddles or weaken the claims about solving SOEGS to claims about finding stationary points of CDFCP.","tokens_in":37063,"tokens_out":13817,"duration_ms":147064,"concrete_test":"Run Algorithm 1 on the scalar instance γ=1, β=12, f(x)=-x, M=1, starting at X0=-0.125, Y0=0.015625, with a deterministic oracle and any step choice α_k=s2/√K. Verify that the output has ∥∇h∥=0, so the Theorem 4.6 O(ε^-4) certificate is satisfied, while |X_K²-1|=0.984, meaning the output is not an ε-first-order stationary point of SOEGS for small ε. This isolates the missing bridge from ε-stationarity of h to ε-stationarity of SOEGS.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central gap is not Assumption 4.1(3)-(4) but the step from ε-stationarity of h to ε-stationarity of SOEGS. Theorem 3.12 guarantees every infeasible first-order stationary point of h is a strict saddle, and Theorems 4.6 and 4.11 only guarantee that Algorithm 1 or 2 finds an ε-first-order stationary point of h. A first-order stationary point of h can be exactly such an infeasible strict saddle, and no saddle-escape or random-perturbation argument is supplied. Theorem 3.16, the only quantitative bridge, requires the iterate to lie in Ω_{1/6}, a condition the algorithms neither enforce nor prove.\n\nThis is not merely a technicality. Take n=p=1, M=1, f(x)=-γx with γ>0, and β=12γ, so that β≥β̃=12γ. Then h'(x)=(x²-1)(1.5γ+βx). The point x_s=-1.5γ/β=-1/8 is a first-order stationary point of h, is infeasible (x_s²-1≈-0.984), lies outside Ω_{1/6}, and is a strict saddle because h''(x_s)=β(x_s²-1)<0. Initialize Algorithm 1 at X0=x_s, Y0=x_s², with the deterministic oracle Mθ=1, fξ=f. Then D0=0 and all iterates remain at x_s, so the Theorem 4.6 bound is satisfied with average gradient norm 0. Yet the output is not an ε-first-order stationary point of SOEGS for any ε<0.98. This example satisfies every assumption of Section 4.1, including the boundedness of {X_k} and {D_k}, so the failure is independent of the reader's chosen weakest assumption.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies stochastic optimization over the generalized Stiefel manifold with expectation-formulated constraints (SOEGS). It introduces a constraint dissolving penalty function CDFCP with a sixth-order penalty term and proves exact equivalence results: every first-order stationary point of h is either a first-order stationary point of SOEGS or a strict saddle (Theorem 3.12), and the two problems share the same second-order stationary points (Theorem 3.14). It then proposes two stochastic gradient algorithms, CDFSG and CDFSG-Ada, that track a p-by-p matrix instead of an n-by-n matrix, and proves O(ε^-4) sample complexity for finding an ε-stationary point of CDFCP (Theorems 4.6 and 4.11). Numerical experiments on GCCA-type problems compare the proposed methods with the Landing algorithm and RSG+.","tokens_in":37427,"tokens_out":9044,"duration_ms":88413,"significance":"The exact stationary-point equivalence for the sixth-order penalty is a nontrivial and potentially useful construction, and the p-by-p tracking scheme is a genuine memory improvement over tracking an n-by-n expectation matrix. The proof of the equivalence theorems appears internally consistent, and the sample-complexity theorems for the penalty function h are correctly derived under the stated assumptions. However, the advertised reduction from SOEGS to unconstrained minimization of h is not established: the algorithms are only guaranteed to find ε-stationary points of h, and an ε-stationary point of h can be an infeasible strict saddle that is far from any ε-stationary point of SOEGS. The paper would be a solid contribution if this gap were closed or if the claims were restricted to ε-stationarity of CDFCP; as it stands, the central motivating claim is overstated.","major_comments":[{"comment":"The complexity theorems only certify ε-stationarity of the penalty h, not of SOEGS. The only quantitative bridge, Theorem 3.16, requires the iterate to lie in Ω_{1/6}, and neither Algorithm 1 nor Algorithm 2 enforces or proves this condition. The gap is real and not merely technical. For example, take n=p=1, M=1, f(x)=-γx with γ>0, and β=12γ, which equals β̃ in (20) since Lg=0 and L0=γ. Then h'(x)=(x²-1)(1.5γ+βx(x²+1)). The equation x³+x+1/8=0 has a root r∈(-1/8,-0.12); at r, ∇h(r)=0, r is infeasible with |r²-1|>0.98, r∉Ω_{1/6}, and h''(r)=β(3r²+1)(r²-1)<0, so r is a strict saddle. Initialize Algorithm 1 at X₀=r, Y₀=r², D₀=0, with the deterministic oracles fξ=f and Mθ=M. Then Xₖ=r, Yₖ=r², and Dₖ=0 for all k, so Assumption 4.1 holds and the averaged gradient norm in Theorem 4.6 is 0, yet the output is not an ε-first-order stationary point of SOEGS for any ε<0.98. Consequently, the claimed reduction from SOEGS to unconstrained minimization of CDFCP fails unless a saddle-escape mechanism or a proof that the iterates enter Ω_{1/6} is added.","section":"Assumption 4.1(3)-(4)"},{"comment":"The convergence results rely on the a priori almost-sure boundedness of the iterates {X_k} and the stochastic gradient estimates {D_k}. These bounds are used in Proposition 4.4 (boundedness of Y_k), Proposition 4.5 (tracking error), and Theorems 4.6 and 4.11 (via τ_x and τ_d). The algorithm contains no projection and the penalty term does not by itself enforce boundedness for the chosen step-size schedule, so these assumptions are not consequences of the problem data. The paper should either prove boundedness under weaker conditions or explicitly state that the O(ε^-4) guarantee is conditional on Assumption 4.1(3)-(4). As written, the phrase 'global convergence guarantee' in Section 1.1 is not justified.","section":"Abstract and Theorem 3.12"},{"comment":"The abstract says that CDFCP and SOEGS 'share the same first-order and second-order stationary points.' Theorem 3.12 shows a weaker statement: every first-order stationary point of h is either a first-order stationary point of SOEGS or a strict saddle of h. Infeasible strict saddles are first-order stationary points of h but not of SOEGS, so the sets of first-order stationary points are not identical. The wording should be corrected to reflect the actual 'either/or' statement, because the current abstract overstates the equivalence.","section":"Minor comments"}],"minor_comments":[{"comment":"The definition κ(A) := σmax(M)/σmin(M) refers to M, not A; this should be fixed to avoid confusion.","section":"Section 2.1"},{"comment":"The phrase 'the the landing algorithm' appears twice; the duplicated article should be removed.","section":"Sections 5.3 and 5.4"},{"comment":"Proposition 4.9 states that the sequence is generated by Algorithm 1, but it is analyzing Algorithm 2; this should be corrected.","section":"Proposition 4.9"},{"comment":"The notation sup_{1≤i≤m,1≤j≤n} uses m and n, but the ambient dimensions are n and p; the index range should be 1≤i≤n, 1≤j≤p.","section":"Proposition 4.10"},{"comment":"Some displayed sums run to K instead of K−1 with mismatched step-size indices; the summation limits should be checked and made consistent.","section":"Theorems 4.6 and 4.11"}],"recommendation":"major_revision","confidential_remarks":"The manuscript contains a simple counterexample to the advertised reduction from SOEGS to CDFCP: the algorithms can be initialized at an infeasible strict saddle and remain there, while satisfying all stated assumptions. I do not think rejection is necessary, because the penalty construction, the exact equivalence theorems, and the sample-complexity analysis for h are valuable and appear correct. However, the authors need to either add a saddle-escape mechanism and prove convergence to an ε-stationary point of SOEGS, or substantially weaken the claims in the abstract, introduction, and conclusion so that they refer only to ε-stationarity of CDFCP."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe short version: this paper does something new, and the main equivalence results look right, but the algorithmic claim that it solves SOEGS is not supported as written. The sample complexity is only for the penalty, and the bridge to the original problem is missing.\n\nWhat's new: the sixth-order penalty CDFCP. Unlike the authors' earlier CDF (local equivalence in a neighborhood), Theorems 3.12 and 3.14 give a global statement: every first-order stationary point of h is either a first-order stationary point of SOEGS or a strict saddle of h, and the two problems have the same second-order stationary points. I checked the flow of the proofs; the lemmas are tedious but plausible, and I didn't find a circular step. The p-by-p tracking in Algorithm 1 is a nice practical contribution, and the experiments on GCCA are reasonably thorough.\n\nThe soft spots, in order of seriousness. First, the gap between the stationarity of h and the original problem in the algorithmic section. Theorems 4.6 and 4.11 guarantee an epsilon-stationary point of h, but an infeasible strict saddle of h also satisfies that condition. The paper does not provide any saddle-escape argument, and Theorem 3.16, which does relate epsilon-stationarity of h to epsilon-stationarity of SOEGS, only applies inside Omega_{1/6}. The algorithms neither enforce nor prove that the iterates stay in that region. So the 'global convergence' for SOEGS is not actually established. This is a real gap, not a nitpick.\n\nSecond, Assumption 4.1(3)-(4) on a priori bounded iterates and gradients is strong. It is common in some nonconvex stochastic optimization papers, but here it is load-bearing in the tracking error bound.\n\nOne caveat: the concrete counterexample in the stress-test note has an algebraic error—with the actual CDFCP penalty in one dimension, the claimed stationary point is not stationary. So don't use that example. But the conceptual concern above is independent of that example.\n\nThe abstract overstates by saying the problems 'share' first-order stationary points; the actual statement includes the strict-saddle alternative.\n\nBottom line: the equivalence theorems deserve publication, and the algorithm is a sensible attempt. A serious referee should engage with this. I'd want the authors to either add a saddle-escape argument or honestly state that the guarantee is for the penalty only, and discuss the Omega_{1/6} restriction.","headline":"Genuinely new penalty with plausible global equivalence theorems, but the stochastic guarantee is for the wrong objective—the bridge to SOEGS is missing.","tokens_in":37988,"tokens_out":4712,"would_cite":true,"duration_ms":42507,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C30","90C52","65K10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A sixth-order penalty term makes the constrained Stiefel problem equivalent to an unconstrained one, and stochastic gradient methods solve it with O(ε^-4) samples.","keywords":["generalized Stiefel manifold","expectation constraints","constraint dissolving penalty","nested stochastic optimization","stochastic gradient methods","sample complexity","canonical correlation analysis","adaptive step sizes"],"falsifier":"For a small random instance with non-quadratic f and known positive-definite M, enumerate all stationary points of h in a bounded box by a homotopy or random multistart method; if any infeasible first-order stationary point of h is not a strict saddle, Theorem 3.12 is false.","tokens_in":36818,"feed_emoji":"🎯","tokens_out":6886,"duration_ms":65298,"temperature":0.7,"pith_summary":"This paper considers minimizing an expected loss f(X)=E[fξ(X)] subject to X^T M X = I_p, where M itself is an expectation E[Mθ] and the feasible set is a generalized Stiefel manifold. Because M is known only through samples, standard Riemannian optimization tools such as retractions and orthogonalization are unavailable or unreliable. The paper proposes a penalty function h with a sixth-order customized penalty term and proves that minimizing h over all of $R^{{n×p}}$ is globally equivalent to the constrained problem: the two share their second-order stationary points, and every infeasible first-order stationary point of h is a strict saddle. This equivalence lets the authors run plain stochastic gradient methods and an adaptive variant, which track only a p×p matrix, and prove O($ε^{{-4}}$) sample complexity for finding an ε-stationary point of h.","feed_headline":"Sixth-order penalty dissolves matrix constraints","feed_subtitle":"Stochastic gradient methods can now solve expectation-constrained Stiefel problems with O(ε^{-4}) samples.","key_machinery":"The load-bearing object is the constraint-dissolving penalty function CDFCP, h(X)=f(A(X))+β/6 tr(X^T M X((X^T M X)^2−3I_p)), where A(X)=X(3/2 I_p−1/2 X^T M X) pre-dissolves the constraint inside f while the sixth-order penalty term controls the growth of f(A(X)). The sixth-order term changes the geometry so that, at large β, all stationary points of h lie in the region where X^T M X has eigenvalues at most 1, and outside the manifold they are strict saddles. The second mechanism is inner-function tracking: a sequence Y_k of p×p matrices obeys Y_{k+1}=Y_k − b_k(Y_k − C_{θ_{k+1}}(X_k)) + (C_{θ_{k+1}}(X_{k+1}) − C_{θ_{k+1}}(X_k)) to estimate C(X_k)=X_k^T M X_k, which keeps memory at O(np+$p^{2}$) and makes the nested stochastic gradient computable.","core_discovery":"On the paper's own terms, the central discovery is that the constrained stochastic problem SOEGS can be replaced, without any loss of information about stationary points, by the unconstrained minimization of h(X)=f(A(X))+β/6 tr(X^T M X((X^T M X)^2−3I_p)), with A(X)=X(3/2 I_p − 1/2 X^T M X). For β above an explicit threshold, Theorem 3.12 shows every first-order stationary point of h is either feasible and a first-order stationary point of SOEGS, or a strict saddle; Theorem 3.14 shows h and SOEGS have exactly the same second-order stationary points; and Theorem 3.16 bounds ∥∇h(X)∥ between two multiples of the constrained optimality measure plus feasibility violation. The paper then gives two stochastic gradient algorithms for h that track the inner expectation C(X)=X^T M X with a p×p auxiliary variable rather than an n×n matrix, and it proves both reach an ε-stationary point of h with O($ε^{{-4}}$) samples (Theorems 4.6 and 4.11).","pith_inferences":["If the boundedness assumption could be replaced by a projection or a regularizer, the same tracking recursion would yield an unconditional sample-complexity guarantee; this is an extension the paper leaves open.","The penalty-plus-tracking design may apply to other expectation-constrained matrix manifolds, such as orthogonality constraints inside an expectation, not only the generalized Stiefel case.","Theorem 3.12's strict-saddle characterization suggests that perturbed stochastic gradient versions of CDFSG could escape infeasible saddles and converge to second-order stationary points of SOEGS, since CDFCP and SOEGS share second-order stationary points (Theorem 3.14).","The empirical robustness to β across five orders of magnitude in the experiments hints that the explicit penalty threshold may be pessimistic; proving a tighter bound on β could ease tuning."],"forward_implications":["CDFSG and CDFSG-Ada can be run on SOEGS without ever computing retractions, projections, or the full expectation matrix M, because their iterates only multiply matrices and track a p×p matrix.","Because infeasible stationary points of CDFCP are strict saddles, any method that reliably escapes strict saddles and converges to first-order stationary points will land on feasible first-order stationary points of SOEGS.","Corollary 3.17 converts an ε-stationary point of CDFCP inside Ω_{1/6} into an O(ε)-stationary point of SOEGS, so the unconstrained guarantee transfers to the constrained problem with the same order in ε.","The O(ε^{-4}) sample complexity matches standard nonconvex stochastic gradient bounds, suggesting the constraint structure adds no extra sample-complexity order.","The p×p tracking variable Y_k provides a cheap feasibility certificate and enables post-processed feasible points via X_K Y_K^{-1/2}, which experiments show preserves accuracy."],"supporting_citations":[{"why":"Introduces the constraint dissolving function (CDF) that CDFCP extends, and supplies the neighborhood-style equivalence idea that this paper makes global.","marker":"[49]"},{"why":"Defines the generalized Stiefel manifold and its first- and second-order optimality conditions, which the paper's equivalence results are measured against.","marker":"[3]"},{"why":"Provides the inner-function tracking recursion that Algorithm 1 adapts to track X^T M X with a p×p matrix.","marker":"[15]"},{"why":"Frames nested stochastic compositional optimization, the setting in which CDFCP's expectation structure is analyzed.","marker":"[47]"},{"why":"The Adam adaptive step-size strategy that CDFSG-Ada incorporates.","marker":"[30]"},{"why":"RSG+, the online Riemannian PCA-style method for stochastic CCA that is a comparison baseline in the experiments.","marker":"[37]"},{"why":"The landing method for SOEGS without retractions, used as a comparison baseline whose convergence needs nearby iterates.","marker":"[46]"}],"fun_headline_variants":["Sixth-order penalty dissolves Stiefel constraints","Penalty trick enables stochastic Stiefel optimization","Stochastic Stiefel: penalty trick dissolves constraints","O(ε^-4) sample complexity for constrained Stiefel","Penalty-based solver matches Stiefel stationary points"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sample-complexity theorems assume that the iterates and gradient estimates never leave a fixed bounded set, even though the algorithm does nothing to enforce that; if an actual run escapes to infinity, the O($ε^{{-4}}$) guarantee no longer applies.","fun_headline_variants_meta":{"raw":{"variants":["Sixth-order penalty dissolves Stiefel constraints","Penalty trick enables stochastic Stiefel optimization","Stochastic Stiefel: penalty trick dissolves constraints","O(ε^-4) sample complexity for constrained Stiefel","Penalty-based solver matches Stiefel stationary points"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000954,"raw_usage":{"total_tokens":4065,"prompt_tokens":938,"completion_tokens":3127,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":3050}},"tokens_in":554,"tokens_out":3127,"duration_ms":22379,"temperature":1.0,"reasoning_tokens":3050,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:40:32.436248+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small random instance with non-quadratic f and known positive-definite M, enumerate all stationary points of h in a bounded box by a homotopy or random multistart method; if any infeasible first-order stationary point of h is not a strict saddle, Theorem 3.12 is false.","supporting_citations":[{"cited_title":"Dissolving Constraints for Riemannian Optimization","cited_arxiv_id":"2203.10319","evidence_quote":"Introduces the constraint dissolving function (CDF) that CDFCP extends, and supplies the neighborhood-style equivalence idea that this paper makes global."},{"cited_title":"Absil, R","cited_arxiv_id":null,"evidence_quote":"Defines the generalized Stiefel manifold and its first- and second-order optimality conditions, which the paper's equivalence results are measured against."},{"cited_title":"Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization","cited_arxiv_id":null,"evidence_quote":"Provides the inner-function tracking recursion that Algorithm 1 adapts to track X^T M X with a p×p matrix."},{"cited_title":"Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions","cited_arxiv_id":null,"evidence_quote":"Frames nested stochastic compositional optimization, the setting in which CDFCP's expectation structure is analyzed."},{"cited_title":"An online riemannian pca for stochastic canonical correlation analysis","cited_arxiv_id":null,"evidence_quote":"RSG+, the online Riemannian PCA-style method for stochastic CCA that is a comparison baseline in the experiments."}],"review_version":1}