{"id":"ae4167c0-6b9c-4797-b6bb-749e4e60e4e9","arxiv_id":"2607.08035","paper_version":1,"verdict":"ACCEPT","confidence":"UNKNOWN","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":3,"one_line_summary":"PDHG converges locally linearly for SDP under strict complementarity or primal-dual nondegeneracy, and can converge sublinearly when both fail.","lead":"This paper proves that the PDHG optimization algorithm converges linearly for semidefinite programming under standard regularity conditions, and shows a case where it fails without them. It matters for practitioners solving large-scale SDPs who need to know when first-order methods will reach high accuracy.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The main theorems are rigorously proved; the sublinear example is formally derived but honestly disclosed as such.","rationale":"The reader correctly identified that the global convergence assumption is the weakest premise, but correctly assessed it as standard and non-problematic. The proofs of both main theorems are technically sound. Theorem 1's normal-contraction argument (Lemma 3) is the most delicate step, but the compactness + equality-case analysis is correct. Theorem 2's error-bound argument is clean and standard. The sublinear example is honestly disclosed as formal in the body, though the abstract slightly overstates it. This does not affect the main contributions. The numerical experiments with a public GitHub repository provide additional support. The reader's ACCEPT verdict with UNKNOWN confidence is appropriate; I would not adjust it.","tokens_in":24729,"tokens_out":4781,"duration_ms":167565,"concrete_test":"To upgrade Example 1 from formal to rigorous: prove that the eigenvalue/eigenvector expansions of Z(α) are valid analytic perturbations for small α>0 (using standard analytic perturbation theory for symmetric matrices), and show that the O(α⁵) remainder in the reduced recursion α+ = α - α³ + O(α⁵) is uniformly bounded so that the discrete Gronwall-type argument yields α_k = Θ(k^{-1/2}). If the remainder cannot be controlled, the formal prediction may not hold.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's two main positive results (Theorems 1 and 2) are rigorously proved. Theorem 1 uses a clean argument: under strict complementarity, Z* = X* - τS* is nonsingular, making the PSD projection smooth near Z*. Lemma 2 correctly identifies the fixed directions of the linearized PDHG map with the tangent space TM of the local KKT manifold. Lemma 3's compactness argument for uniform normal contraction is sound: if ||(I-Π_P)G_z u||_P = ||u||_P for u ⊥_P TM, then equality in firm nonexpansiveness forces G_z u = u ∈ TM, contradicting u ⊥_P TM. Theorem 2's proof combines strong metric subregularity (from nondegeneracy via [16,21]) with the proximal-point descent inequality in a standard way, yielding ρ_ND = μ/√(1+μ²) < 1. The reader's identified weakest assumption — that global convergence to a KKT point is assumed rather than proved — is standard in local convergence analysis and is justified by existing PDHG convergence theory [14,15] under the stepsize condition (3). The only notable gap is that Example 1 (sublinear convergence when both regularity conditions fail) is a formal asymptotic reduction, not a rigorous proof. The body is transparent about this ('formal local asymptotic reduction,' 'numerical evidence is consistent with the formal prediction'), but the abstract states it as a result ('PDHG can converge only sublinearly'). This discrepancy is minor: it concerns the negative example, not the main positive theorems, and the formal calculation is plausible and numerically supported.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper studies the local convergence behavior of the primal-dual hybrid gradient (PDHG) method applied to a standard primal-dual semidefinite programming (SDP) pair. The main results establish that PDHG converges eventually (R-)linearly whenever the limiting KKT point satisfies either strict complementarity (Theorem 1) or primal-dual nondegeneracy (Theorem 2). The proof of Theorem 1 exploits the smoothness of the PSD-cone projection near the nonsingular signed matrix Z* = X* - tau S* under strict complementarity, linearizes the PDHG fixed-point map, and proves uniform contraction of the normal component to the local KKT manifold. The proof of Theorem 2 uses the equivalence of primal-dual nondegeneracy to strong regularity of the KKT mapping, yielding strong metric subregularity, which is combined with the proximal-point descent inequality. A constructed SDP instance (Example 1) where both regularity conditions fail is shown, via formal asymptotic reduction and numerical evidence, to exhibit sublinear convergence. Numerical experiments on various SDP instances support the theory.","tokens_in":25547,"tokens_out":1943,"duration_ms":143415,"significance":"The paper addresses a well-motivated gap in the convergence theory of first-order methods for SDP. While global sublinear convergence of PDHG is well understood, the local linear regime — important for understanding practical high-accuracy behavior — had been established for LP (polyhedral case) and for ADMM on SDP, but not for PDHG on SDP. The two sufficient conditions (strict complementarity and primal-dual nondegeneracy) are classical and well-chosen, and the proof machinery is clean and modular: the preconditioned proximal point interpretation of PDHG, combined with either spectral geometry of the PSD cone or variational regularity of the KKT mapping, provides a transparent and reusable framework. The sublinear example (Example 1), while formally derived rather than rigorously proved, is a valuable contribution that sharpens the contrast with LP and is honestly disclosed. The numerical experiments cover a broad range of instances and honestly report difficult cases. Reproducible code is provided. The results are of clear interest to the optimization community.","major_comments":[{"comment":"Abstract and Theorem statements vs. Example 1: The abstract states 'We also give a simple SDP instance where both regularity conditions fail and PDHG can converge only sublinearly.' However, as disclosed in Section 6.1, Example 1 provides a formal local asymptotic reduction and numerical evidence, not a rigorous proof of sublinear convergence. The formal calculation (alpha_{k+1} = alpha_k - alpha_k^3 + O(alpha_k^5)) is plausible and the numerical evidence in Figure 3 is consistent, but the claim as stated in the abstract is stronger than what is proved. The authors should either (a) soften the abstract statement to match the formal nature of the result (e.g., 'we present an SDP instance where a formal local reduction predicts sublinear convergence, supported by numerical evidence'), or (b) upgrade Example 1 to a rigorous proof. Option (a) is sufficient given that the main positive theore","section":null},{"comment":"Section 4.3, Theorem 1, proof of Eq. (22): The passage from dist_P(z_k, M) to dist((X_k, y_k, S_k), Omega*) uses the local representation of the KKT set M from Lemma 1. The argument constructs z_k_bar = Pi_P^{aff M}(z_k) in M and then (X_k_bar, y_k_bar, S_k_bar) in Omega*. The bound dist((X_k, y_k, S_k), Omega*) <= kappa_2 ||z_k - z_k_bar||_P is stated with a constant kappa_2 > 0 but the dependence on the relationship between the P-metric and the Frobenius/Euclidean product norm is not made explicit. Since P is a fixed positive definite operator (depending on tau, sigma, A), norm equivalence gives such a constant, but the reader would benefit from a one-line justification confirming that kappa_2 is independent of k and depends only on P, A, tau, sigma.","section":null},{"comment":"Section 5, Theorem 2: The proof establishes Q-linear convergence of (X_k, y_k) to (X*, y*) in the P-metric under primal-dual nondegeneracy. The uniqueness of the KKT point under primal-dual nondegeneracy is invoked (citing [16, Theorem 18] for the equivalence to strong regularity). It would strengthen the result to state explicitly in the theorem or its proof that primal-dual nondegeneracy implies uniqueness of the KKT point, so that the strong metric subregularity estimate (7) — which bounds the distance to the specific point z* — is applicable. This is mentioned in the proof text but not in the theorem statement, and the logical flow (nondegeneracy => strong regularity => strong metric subregularity => Q-linear convergence) should be made fully transparent.","section":null}],"minor_comments":[{"comment":"Abstract: The phrase 'PDHG can converge only sublinearly' overstates Example 1, which is a formal reduction plus numerics, not a proved theorem. Consider rewording to 'a formal local reduction predicts sublinear convergence, supported by numerical evidence.'","section":null},{"comment":"Assumptions 2 and 3 (Sections 3.3 and 3.4): Each assumes that the PDHG iteration converges to a KKT point satisfying the respective regularity condition. This is standard for local convergence analysis and is justified by existing global convergence theory under the stepsize condition (3), but a brief remark explicitly citing the global convergence result (e.g., [14,15]) that guarantees convergence under (3) would help the reader understand that the assumptions are not vacuous.","section":null},{"comment":"Section 6.1, Example 1: The formal expansion is carried out to O(alpha^5). It would help the reader to briefly state why the expansion is truncated at this order (i.e., that the leading-order dynamics alpha_{k+1} = alpha_k - alpha_k^3 + O(alpha_k^5) are sufficient to determine the asymptotic rate, and higher-order terms do not change the leading behavior for sufficiently small alpha).","section":null},{"comment":"Section 4.2, Eq. (14): The derivative G_z of the PDHG map R is stated. A brief remark that this follows from the chain rule applied to the resolvent representation (12) and the Fréchet differentiability of Pi_{S^n_+} (cited from [52, Theorem 4.6]) would aid readers less familiar with the PSD projection derivative.","section":null},{"comment":"Figure 1 caption: The caption states 'In all four instances, PDHG with fixed stepsizes eventually exhibits local linear convergence.' However, panel (d) corresponds to the sublinear example (Example 1) where both SC and ND fail. The caption appears to contradict the sublinear prediction. Clarification is needed — perhaps panel (d) of Figure 1 is a different instance from Example 1, or the caption should note that the linear regime in (d) is observed only over a finite horizon.","section":null},{"comment":"Section 7.2: The two possible explanations for slow convergence (contraction factor near 1 vs. local linear regime not yet reached) are discussed. It would be useful to note whether the diagnostic sqrt(k) * ||X_k - X*||_F (used in Figure 3 for Example 1) was also checked for the instances in Figure 8, as this could help distinguish the two explanations.","section":null},{"comment":"Table 1: The column headers 'n' and 'm' are used without explicit definition in the table caption. While they are defined earlier in the paper (n is the matrix dimension, m is the number of constraints), restating this in the caption would make the table self-contained.","section":null},{"comment":"References: Several references have incomplete or future-dated publication information (e.g., [5] 'Mathematical Programming Computation, 2026'; [7] 'Optimization Letters, 20(3):503-520, 2026'; [47] 'Mathematical Programming, 2026'). These should be updated with final publication details if available.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a solid contribution with clean proofs built on well-established machinery. The main positive theorems are rigorous. The only substantive issue is the abstract's overstatement of the sublinear example (Example 1) as a proved result when it is formally derived. This is easily addressed by softening the language. The reader's identified weakest assumption (global convergence assumed, not proved) is standard for local convergence analysis and does not constitute a major concern. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"This paper proves that PDHG on SDP converges eventually R-linearly when the limit KKT point satisfies either strict complementarity or primal-dual nondegeneracy. The two proofs use genuinely different mechanisms: strict complementarity makes the PSD cone projection smooth near Z* = X* - τS*, so the author can linearize the PDHG fixed-point map and show uniform contraction normal to the local KKT manifold (Lemma 3 is the key step, and the compactness argument there is clean). Nondegeneracy takes the other route — strong metric subregularity of the KKT mapping feeds directly into the proximal-point descent inequality to give Q-linear convergence. Both arguments are built on standard machinery (He-Yuan's proximal point interpretation, Sun-Sun differentiability of the projection, Chan-Sun's equivalence of nondegeneracy and strong regularity), and the paper is honest about these debts. The sublinear Example 1 is illuminating: a 3x3 SDP where both conditions fail, and a formal asymptotic reduction predicts k^{-1/2} decay along a slow branch. The numerics in Figure 3 are consistent with this prediction. The LP contrast — where PDHG gets linear convergence even for degenerate instances — is a nice framing device that clarifies what the nonpolyhedral geometry costs you. The soft spot is minor and the stress-test note catches it correctly: Example 1 is a formal calculation, not a rigorous proof. The body is transparent about this, but the abstract states it as a result (PDHG can converge only sublinearly). This is a wording issue, not a mathematical one — the formal reduction is plausible and numerically supported, and it concerns the negative example, not the main theorems. The reader's identified weakest assumption (global convergence to a KKT point is assumed, not proved) is standard in local convergence analysis and is justified by existing PDHG convergence theory under the stepsize condition. I don't think it's a real concern. The numerical experiments are extensive and the GitHub repo provides reproducibility. The paper knows its limits: Section 6.4 lists open questions about relaxed stepsize ranges, the ADMM vs PDHG distinction, and whether there's a sharper necessary-and-sufficient regularity condition. This is a solid, well-executed theory paper for people working on first-order methods for conic optimization. It deserves a serious referee.","headline":"Clean local convergence theory for PDHG on SDP under two standard regularity conditions, plus an honest sublinear counterexample when both fail.","tokens_in":25772,"tokens_out":565,"would_cite":true,"duration_ms":60733,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"PDHG on SDP converges linearly under either of two regularity conditions","keywords":[],"falsifier":"A counterexample would be an SDP instance satisfying strict complementarity or primal-dual nondegeneracy for which PDHG (with stepsizes satisfying the stated condition) converges to the KKT point but the error does not eventually decay at a linear rate. Alternatively, a proof that the formal sublinear example in Section 6.1 actually converges linearly would contradict the paper's claim that regularity is needed.","tokens_in":25032,"feed_emoji":"📉","tokens_out":1300,"duration_ms":143752,"temperature":0.7,"pith_summary":"The paper studies the primal-dual hybrid gradient (PDHG) method applied to semidefinite programming (SDP), a convex optimization framework over the cone of positive semidefinite matrices. Global convergence theory for PDHG on SDP predicts only sublinear decay of the error, which suggests the method should slow down near the solution. This paper shows that, under either of two standard regularity conditions at the solution point, PDHG eventually enters a regime of (R-)linear convergence, where the error contracts by a fixed factor at each step. The two conditions are strict complementarity (the primal and dual matrices have complementary positive eigenspaces with no shared degenerate zero eigenspace) and primal-dual nondegeneracy (the affine constraints meet the tangent geometry of the PSD cone without hidden flat directions). The proof rests on viewing PDHG as a preconditioned proximal point method for the KKT (Karush-Kuhn-Tucker) inclusion, which yields a descent inequality in a problem-dependent metric. Under strict complementarity, the PSD cone projection is smooth near the solution, and the derivative of the PDHG map contracts directions normal to the local solution manifold. Under primal-dual nondegeneracy, the KKT mapping is strongly metrically subregular, providing a local error bound that combines with the descent inequality to give Q-linear convergence directly. The paper also constructs a small SDP instance where both conditions fail and shows that a formal local reduction of the PDHG map predicts sublinear decay at rate k^{-1/2}, which is confirmed numerically. This contrasts with linear programming, where the polyhedral geometry of the feasible set guarantees linear convergence even for degenerate instances.","feed_headline":"PDHG on SDP converges linearly under either of two regularity conditions","feed_subtitle":"Strict complementarity or primal-dual nondegeneracy unlocks eventual linear convergence; without both, sublinear decay can persist, unlike线性","key_machinery":"The key machinery is the interpretation of the PDHG iteration as the P-resolvent of the reduced KKT mapping F_KKT, where P is a block self-adjoint operator encoding the primal-dual stepsize coupling. This yields firm nonexpansiveness of the PDHG map in the P-metric. Under strict complementarity, the Fréchet derivative of the PSD cone projection (given by a Hadamard product formula involving eigenvalue ratios) linearizes the PDHG map, and the fixed-point set of this linearization equals the tangent space to the local KKT manifold. Under primal-dual nondegeneracy, strong metric subregularity of F_KKT provides the inequality ||z - z*||_P <= mu dist(0, F_KKT(z)), which combines with the descent/","core_discovery":"The central discovery is that PDHG, when applied to SDP, can be understood as a preconditioned proximal point method for the KKT inclusion, and that this viewpoint reduces the question of local linear convergence to the availability of a compatible local error bound. Under strict complementarity, the error bound comes from the spectral geometry of the PSD cone: the signed matrix Z* = X* - tau S* is nonsingular, so the cone projection is differentiable in a neighborhood, and the linearized PDHG map fixes exactly the tangent directions to the local KKT manifold while contracting all normal directions. Under primal-dual nondegeneracy, the error bound comes from strong metric subregularity of a ","pith_inferences":["The sublinear example suggests that for SDPs arising from relaxations of polynomial optimization (where strict complementarity can fail), PDHG may require restarts or acceleration to reach high accuracy, as the natural local rate can be as slow as O(k^{-1/2}).","The two distinct proof mechanisms (spectral smoothness vs. metric subregularity) may extend to other primal-dual proximal splitting methods beyond PDHG and ADMM, potentially yielding a unified local convergence theory for first-order methods on conic programs over nonpolyhedral cones.","If the stepsize condition tau*sigma*||A||^2 < 1 could be relaxed (e.g., to the larger ranges known for relaxed PDHG), the local linear convergence theory might still hold, but the proof would need a different Lyapunov function since the proximal point interpretation breaks down."],"forward_implications":["Practitioners using PDHG for large-scale SDP can expect eventual linear convergence on instances where strict complementarity or primal-dual nondegeneracy holds, which are generic properties for many SDP classes.","The constructed sublinear example provides a concrete mechanism (nonlinear PSD-cone projection at a singular matrix) for why PDHG can stagnate on certain SDPs, guiding diagnosis of slow convergence in practice.","The separation of the two regularity conditions suggests that SDP solvers could be designed or adapted to detect which regime applies and adjust stepsize or restart strategies accordingly.","The contrast with LP (where linear convergence holds even without regularity) highlights that the nonpolyhedral geometry of the PSD cone is the fundamental obstruction, not the algorithm itself.","Finite-time rank identification of the primal iterate under strict complementarity provides a theoretical basis for low-rank exploitation in PDHG implementations after a transient phase."],"fun_headline_variants":["PDHG converges linearly on SDP under strict complementarity or nondegeneracy","SDP degeneracy stalls PDHG where LP degeneracy does not","PDHG as proximal point method yields linear convergence on regular SDPs","When SDP regularity fails, PDHG can only converge sublinearly","Local linear convergence of PDHG on SDP reduces to a local error bound"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The proofs of both convergence theorems assume that the PDHG iteration has already converged to a KKT point satisfying the respective regularity condition. Global convergence of the iterates to a KKT point is taken as a premise, not established within the local theory. If PDHG fails to converge for some SDP instance (e.g., due to numerical instability or an unfavorable stepsize choice), the local linear rate guarantees do not apply.","fun_headline_variants_meta":{"raw":{"variants":["PDHG converges linearly on SDP under strict complementarity or nondegeneracy","SDP degeneracy stalls PDHG where LP degeneracy does not","PDHG as proximal point method yields linear convergence on regular SDPs","When SDP regularity fails, PDHG can only converge sublinearly","Local linear convergence of PDHG on SDP reduces to a local error bound","PDHG on SDP: linear convergence requires conditions LP problems don't need","Strict complementarity or nondegeneracy unlocks linear PDHG convergence on SDP","Semidefinite programs harder than LP for PDHG: degeneracy breaks linear convergence","PDHG linear convergence on SDP needs regularity that LP degeneracy skips","Preconditioned proximal point view explains when PDHG converges linearly on SDP"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":1531,"prompt_tokens":551,"completion_tokens":980,"prompt_tokens_details":null},"tokens_in":551,"tokens_out":980,"duration_ms":32092,"temperature":1.0,"reasoning_tokens":758,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T01:14:27.023305+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A counterexample would be an SDP instance satisfying strict complementarity or primal-dual nondegeneracy for which PDHG (with stepsizes satisfying the stated condition) converges to the KKT point but the error does not eventually decay at a linear rate. Alternatively, a proof that the formal sublinear example in Section 6.1 actually converges linearly would contradict the paper's claim that regularity is needed.","supporting_citations":[],"review_version":1}