{"id":"17fa6396-b984-4b5e-a6a6-cf6725e39b2b","arxiv_id":"1908.04357","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Eigenvalue ratios along a central path lower-bound the true error of an SDP solution and bound singularity degree, while for Potra-Sheng external paths a singularity degree above one forces sublinear convergence.","lead":"A solver can report that a semidefinite program is solved to precision 10^-12 while the returned matrix is actually 10^-2 away from any true solution. This paper gives a way to estimate that true distance from eigenvalue ratios along the central path, turning it into a practical alarm, and proves that a large singularity degree forces slow convergence for one family of interior-point paths.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2, the convergence-to-relint(F) bridge for the external Potra–Sheng path, is asserted by citation rather than proved; Section 4 and the Section 3 rank-bound method for this path family rest on it.","rationale":"The Section 3 proofs are careful and appear correct; Theorem 3.10 itself only needs a true upper bound on the maximum rank. The real fragility is how that upper bound is produced for the path family studied in Sections 4 and 5. The reader identified Assumption 3.2(i), and for the external Potra–Sheng path this assumption is supplied by Theorem 4.2, whose proof is deferred to two external results without a derivation. Because the right-hand side in (4.1) depends on alpha, the path is not literally the standard central path of a fixed SDP, so the transfer is not automatic. This is a genuine but addressable gap rather than a demonstrated counterexample: the numerical evidence is consistent with the theorem, and the cited literature likely contains the needed ingredients. The visual threshold choice in Section 5 is a secondary weakness of the practical method, not the central mathematical claim. Therefore the reader's CONDITIONAL verdict is appropriate; no change is needed.","tokens_in":20385,"tokens_out":18128,"duration_ms":192153,"concrete_test":"Write out a complete proof of Theorem 4.2 from the cited sources, or give a self-contained argument. Specifically: (a) check whether the Potra–Sheng path (4.1) is a special case of the trajectory studied in Goldfarb–Scheinberg [11]; (b) verify that their limit-point theorem yields the relative-interior conclusions in (4.3) without extra hypotheses such as strict complementarity or a fixed b; (c) confirm that the Milnor lemma, as used in Halická–de Klerk–Roos [12,13], applies to this external path and rules out multiple limit points. If any step fails, identify the missing hypothesis and either prove Theorem 4.2 under it or restrict Corollary 4.3, Theorem 4.4, and Theorem 4.7 accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Theorem 4.2, which asserts that the external path (4.1)–(4.2) converges to a unique limit (Xbar, ybar, Zbar) with Xbar in relint(F) and Zbar in the relative interior of the dual optimal cone. This is exactly what connects Assumption 3.2(i) to the path family used in Section 5, and it underlies the eigenvalue-rate statements of Corollary 4.3 and Theorem 4.4. The proof in the manuscript is not a proof: it says the result 'may be deduced' from Goldfarb–Scheinberg [11] and a lemma of Milnor via Halická–de Klerk–Roos [12,13], but no deduction is shown. This matters because (4.1) is not the standard central path for a fixed SDP with fixed right-hand side b; the right-hand side itself is perturbed via b + alpha A(B). The cited convergence results are for central paths of a fixed problem, and the hypotheses under which they transfer to this external path are not checked. If Theorem 4.2 fails, then the rank estimate obtained from eigenvalue ratios can be the rank of an arbitrary limit point rather than an upper bound on the maximum rank over F, so the lower bound in Theorem 3.10, applied with that estimate, is not justified; the Section 4 sufficient-condition claim also collapses. The authors' own caveat that 'we are not aware of this exact result in the literature' signals that this bridge is not a routine citation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the gap between forward error (distance to the solution set) and backward error (residual in the optimality conditions) for semidefinite programs without Slater points. In Section 3 the authors prove a lower bound on forward error, complementing Sturm's upper bound, under the assumption that the path under consideration converges to the relative interior of the solution set. The lower bound is obtained by first bounding the maximum rank over the solution set via eigenvalue ratios along the path, and then using Fan's inequality. In Section 4 the authors analyze a family of external-type 'central' paths proposed by Potra and Sheng, claiming convergence to a point in the relative interior of the solution set, and use this to argue that large singularity degree is, for this path family, a sufficient condition for sublinear convergence of some vanishing eigenvalue. Numerical case studies in Section 5 illustrate the bounds and the rank/singularity-degree estimates on five spectrahedra.","tokens_in":20572,"tokens_out":14066,"duration_ms":143744,"significance":"If the results hold, the paper makes two useful contributions. First, Theorem 3.10 is cleanly proved and gives a computable lower bound on the unmeasurable forward error once an upper bound on the maximum rank is known, thereby complementing Sturm's one-sided upper bound; the proof via Fan's inequality and the rank bound is elementary and correct. Second, the eigenvalue-ratio criteria in Proposition 3.3 and Corollaries 3.7-3.8 provide a practical, though heuristic, way to estimate maximum rank and to lower-bound singularity degree, and the numerical section gives detailed, honest case studies showing the method at work. The main theoretical claim of Section 4 - that large singularity degree is sufficient for slow convergence of a natural central path - would be significant if the underlying convergence theorem (Theorem 4.2) is fully proved, because it would make Sturm's necessary condition two-sided for that path family. The paper is clear about which statements are rigorous and which are inferred from numerical evidence, which is a strength.","major_comments":[{"comment":"The proof of Theorem 4.2 is not supplied. The text asserts that the result 'may be deduced' from Goldfarb-Scheinberg [11] and Milnor's lemma via Halicka et al. [12,13], but no deduction is shown. The path (4.1)-(4.2) is not the standard central path for a fixed SDP: the right-hand side itself is perturbed to b + alpha A(B), so the feasible set varies with alpha, and the hypotheses under which the cited convergence results transfer to this external path are not checked. This is load-bearing, because Corollary 4.3, Theorem 4.4, and Theorem 4.7 all depend on Theorem 4.2. The authors' own caveat that they are not aware of this exact result in the literature underscores the gap. A complete proof, or a reframing of Section 4 as conditional on an explicitly stated convergence assumption, is needed.","section":"Section 3.1, Lemma 3.4"},{"comment":"The proof of Lemma 3.4 is incomplete. In bounding S(alpha) by the maximum of the norms of the diagonal blocks Xi(alpha), it implicitly relies on control of the off-diagonal blocks of QX(alpha)Q^T, but Fact 2.3 only gives bounds on the diagonal blocks. The missing argument is that S(alpha) is positive definite, hence each off-diagonal block has norm at most the geometric mean of the corresponding diagonal block norms; since xi(i) is nondecreasing in i, this yields the claimed O(alpha^{xi(i)}) bound. Please include this argument explicitly.","section":"Section 4.2, Theorem 4.7"},{"comment":"The proof of Theorem 4.7 is not fully rigorous. The iterative construction of successive exposing vectors involves normalizing coefficient vectors and passing to limit points, and several key steps are compressed: the justification that (A*(y2))11 is positive semidefinite after normalization, the 'without loss of generality' block-diagonal assumption in (4.11), and the statement that 'by reasoning analogous' to the first step we may continue. In particular, the termination of the process and the claimed bound d in [sd(F), mbar] are only justified by an informal 'continue in this fashion'. Please provide a complete induction that tracks the rates of the coefficients at each reduction step and compares the number of steps with the facial reduction process defining sd(F).","section":"Section 5, Corollary 3.8"},{"comment":"The numerical estimates of maximum rank and singularity degree in Section 5 rely on choosing the threshold tau in Corollary 3.8 by visual inspection of the plots (Figures 5.1-5.5). Since the paper presents this as a method, a principled, reproducible rule for selecting tau, or a sensitivity analysis showing that the conclusions are stable over a range of tau, is needed. Without this, the applicability of the rank-bounding method to new instances is not fully demonstrated.","section":"Section 4.2, Theorem 4.4"}],"minor_comments":[{"comment":"The heading 'Analaysis' should be 'Analysis'.","section":"Section 3.1, Proposition 3.3"},{"comment":"The phrase 'blows up' in Proposition 3.3 is informal; for a formal statement, use the liminf/limsup formulation as in Corollary 3.8, and clarify that in practice the ratio may blow up slowly.","section":"Section 3, Assumption 3.2"},{"comment":"Assumption 3.2(i) is asserted to hold for 'many of the well-known algorithms', but no specific justification is given. Since all of Section 3 depends on the limit lying in relint(F), a brief discussion of which families of central paths are known to satisfy this assumption (and which are not) would sharpen the scope of the results.","section":"Section 5, Table 5.1"},{"comment":"The table would benefit from a note clarifying which entries are proven bounds versus heuristic estimates; in particular, the reported lower bounds on singularity degree for spec4 and spec5 are derived from the visual threshold choice, not from a theorem.","section":"Section 1"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is Theorem 4.2. If the authors cannot supply a complete proof, they should present Section 4 as a conditional study and soften the abstract's 'sufficient condition' claim accordingly. The Section 3 material is largely sound and worth publishing after the proof of Lemma 3.4 is completed. The paper is within scope for a mathematical optimization journal; the numerical section, while heuristic, is clearly labeled and would be acceptable after the threshold-selection issue is addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Core result worth knowing: Theorem 3.10 turns an upper bound on maximum rank into a computable lower bound on forward error, and the accompanying eigenvalue-ratio machinery in Section 3 is genuinely clean. The proof is short and correct, and the numerical examples make the point forcefully — backward error around 1e-13 with forward error around 1e-2 is exactly the kind of silent failure the SDP community should worry about. This is a real complement to Sturm's one-sided bound.\n\nWhat is new here is also what is good: the rank-bound method, the lower bound on singularity degree, and the Q-convergence-rate threshold tests are all stated as theorems with proofs that mostly hold together. I checked the Section 3 line of reasoning and it works. The authors deserve credit for not overselling the numerical side; they admit the threshold choices are by eye and they ship no code.\n\nThe soft spots are concentrated in Section 4. The stress-test concern is on target: Theorem 4.2, which says the Potra–Sheng external path converges to a point in relint(F), is not proved in the manuscript. It is deduced from Goldfarb–Scheinberg and a Milnor lemma via Halická et al., but the deduction is not shown, and (4.1) is not the standard central path with fixed b — the right-hand side itself is perturbed. That matters because the Section 4 hardness results lean on this bridge. I also agree that Theorem 4.4's one-line proof hides the implication sd(F) > 1 implies a complementarity gap, and Theorem 4.7's iterative block construction is sketched rather than fully tracked. These are addressable in revision, but they are real gaps, not cosmetic ones.\n\nNone of this undermines the main deliverable: the forward-error lower bound of Theorem 3.10 and its supporting eigenvalue-ratio tools are solid, and the numerical alarm is credible. The Section 4 claims are plausible but currently rest on an unproved convergence theorem. A serious referee should ask for a full proof of Theorem 4.2, expanded proofs of Theorems 4.4 and 4.7, and at least a heuristic formalization of the threshold choice.\n\nRecommendation: send it to peer review. It deserves referees' time, with the expectation that Section 4 will need substantial work.","headline":"A useful, mostly solid paper: the forward-error lower bound is clean and new, but the Section 4 convergence bridge is asserted by citation and needs real proof before the hardness claims can be trusted.","tokens_in":21306,"tokens_out":1643,"would_cite":true,"duration_ms":18459,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that for a class of central paths in semidefinite programming, an upper bound on the maximum rank of the solution set turns the observable tail eigenvalues of the iterates into a computable lower bound on the…","keywords":["semidefinite programming","forward error","backward error","singularity degree","central path","maximum rank","facial reduction","eigenvalue ratios"],"falsifier":"The sufficiency claim in Theorem 4.4 would be refuted by an explicit spectrahedron with singularity degree 2 whose external central path (4.1) has every vanishing eigenvalue of $X(\\alpha)$ bounded by a constant times $\\alpha$ as $\\alpha\\to 0$; following the path numerically for a small instance and measuring $\\lambda_{r+1}(X(\\alpha))/\\alpha$ would settle it.","tokens_in":20036,"feed_emoji":"📉","tokens_out":11333,"duration_ms":103053,"temperature":0.7,"pith_summary":"Semidefinite programming solvers can return a point with tiny violation of the optimality conditions but a large true distance to the solution set. This paper proves that along central paths converging to the relative interior of the solution set, any upper bound on the maximum rank of the solutions yields a computable lower bound on that true distance, formed from the tail eigenvalues of the iterate beyond the rank bound. That lower bound complements the classical upper bound, so the forward-backward error relation becomes two-sided for this class of paths. For the external central path defined by maximizing $\\alpha\\log\\det X$ over the perturbed constraints $A(X)=b+\\alpha A(B)$, the paper also shows that singularity degree (the number of facial-reduction steps needed to make the problem strictly feasible) greater than 1 forces at least one eigenvalue to vanish slower than $O(\\alpha)$, making large singularity degree, in this path family, a sufficient condition for slow convergence.","feed_headline":"SDP error bounds become two-sided along central paths","feed_subtitle":"Tracking the small eigenvalues of a central path certifies when a 'solved' semidefinite program is actually far from optimal.","key_machinery":"The key machinery is the maximum rank $r$ of the solution set $F$ (the largest rank attained by any solution), probed through two eigenvalue ratios: the adjacent-eigenvalue ratio $\\lambda_i(X(\\alpha))/\\lambda_{i+1}(X(\\alpha))$, whose first blow-up locates $r$, and the Q-convergence ratio $\\lambda_i(X(\\sigma^{k+1}))/\\lambda_i(X(\\sigma^k))$, whose limit inferior separates eigenvalues that vanish from those that do not. A rank upper bound becomes an error lower bound through the identities $\\|X\\|_F=\\|\\lambda(X)\\|_2$ and $\\langle X,Y\\rangle\\le \\lambda(X)^T\\lambda(Y)$: because every solution has rank at most $r$, the squared distance from $X(\\alpha)$ to any solution must dominate the squared norm of the tail eigenvalues. The second mechanism is the external primal-dual central path with $Z(\\alpha)=\\alpha X(\\alpha)^{-1}$, whose limit structure forces at least $\\operatorname{sd}(F)$ different vanishing rates among the blocks of $Z(\\alpha)$.","core_discovery":"The paper's central claim is that the gap between backward and forward error in semidefinite programming can be certified from eigenvalue data collected along the path, without knowing the solution set. If a central path $\\{X(\\alpha):\\alpha>0\\}$ satisfies the assumptions that $X(\\alpha)\\succ 0$ and $X(\\alpha)\\to \\bar X\\in\\operatorname{relint}(F)$, and if $r$ upper-bounds the maximum rank over $F$, then Theorem 3.10 gives $\\epsilon_f(X(\\alpha),F)\\ge \\|(\\lambda_{r+1}(X(\\alpha)),\\dots,\\lambda_n(X(\\alpha)))^T\\|_2$. The proof rests on the spectral norm identity and the trace bound $\\langle X,Y\\rangle\\le \\lambda(X)^T\\lambda(Y)$. For the external central path defined by maximizing $\\alpha\\log\\det X$ over $A(X)=b+\\alpha A(B)$, the paper proves Theorem 4.4: if $\\operatorname{sd}(F)>1$, some eigenvalue of $X(\\alpha)$ converges to $0$ at a rate that is not $O(\\alpha)$, and the dual path contains at least $\\operatorname{sd}(F)$ distinct vanishing rates.","pith_inferences":["The eigenvalue-tail lower bound could be implemented as an online stopping criterion: declare a solution unreliable whenever $\\|(\\lambda_{r+1},\\dots,\\lambda_n)\\|_2$ exceeds a user tolerance, even if the backward error looks solved; the paper demonstrates the gap numerically but does not propose this as an algorithm.","Because the relative-interior convergence assumption is not checkable from solver output, a natural stress test is to run multiple perturbed paths with different $B$ in (4.1) and see whether the rank and error bounds stabilize; instability would signal that the assumption is failing.","The paper's empirical observation that the number of distinct vanishing rates appears to upper-bound singularity degree suggests a tractable, rank-free route to singularity-degree estimation; proving or disproving this is left open by the authors.","Extending the sufficiency theorem beyond feasibility problems would require controlling the unknown optimal value $p^*$; the duality-gap proxy in Remark 3.9 is a step, and a plausible next direction is to prove analogous block-rate results for the primal-dual path of the shifted objective."],"forward_implications":["Practitioners can turn any rank upper bound, from Proposition 3.3 or Corollary 3.8, into a certified lower bound on the distance to the solution set without knowing the solution set.","For the external central path family, the classical upper bound and the new lower bound sandwich the forward error, so small backward error can coexist with large forward error exactly when singularity degree is large.","Maximum rank over $F$ can be estimated as the smallest index whose eigenvalue ratio blows up, and validated by comparing Q-convergence rates against thresholds $\\sigma^{2^{-(d-1)}}$, yielding lower bounds on singularity degree.","Since $Z(\\alpha)=\\alpha X(\\alpha)^{-1}$, the distinct vanishing rates of blocks in the dual path imply distinct Q-convergence rates in the primal path, explaining why interior-point solvers stall when the fastest block reaches machine precision.","For feasibility SDPs with bounded solution set, singularity degree greater than 1 rules out $O(\\alpha)$ convergence of all vanishing primal eigenvalues, so slow convergence is forced along this path."],"supporting_citations":[{"why":"Supplies the classical upper bound on forward error in terms of backward error and singularity degree that the new lower bound complements.","marker":"[25]"},{"why":"Provides the family of hard SDP instances with prescribed complementarity gap used in the numerical case studies (spec1 and spec4).","marker":"[29]"},{"why":"Provides the worst-case SDP family (spec2) used to demonstrate the large gap between forward and backward error.","marker":"[26]"},{"why":"Shows the limit points of the primal-dual central path satisfy the relative-interior properties used in Theorem 4.2.","marker":"[11]"},{"why":"Establishes convergence of the central path to a singleton, which Theorem 4.2 relies on.","marker":"[13]"},{"why":"Supplies the topological lemma used to rule out multiple limit points of the central path.","marker":"[17]"},{"why":"Documents the 'strange behaviour' of interior-point methods on the SDP instance used as spec3.","marker":"[28]"},{"why":"Provides the completion example used as spec5, with a known lower bound on singularity degree.","marker":"[24]"}],"fun_headline_variants":["Eigenvalue decay along central path certifies SDP error","Lower bound on true SDP error from central path spectrum","Singularity degree forces slow SDP convergence","New SDP error lower bound via eigenvalue tracking","Central path eigenvalues bound true SDP error"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the central path converges to a point in the relative interior of the solution set, the interior within the flat space that contains it, because only then does its rank equal the maximum rank over all solutions, and this condition cannot be verified from observable solver data.","fun_headline_variants_meta":{"raw":{"variants":["Eigenvalue decay along central path certifies SDP error","Lower bound on true SDP error from central path spectrum","Singularity degree forces slow SDP convergence","New SDP error lower bound via eigenvalue tracking","Central path eigenvalues bound true SDP error"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000714,"raw_usage":{"total_tokens":3215,"prompt_tokens":957,"completion_tokens":2258,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":2183}},"tokens_in":573,"tokens_out":2258,"duration_ms":17143,"temperature":1.0,"reasoning_tokens":2183,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:48:36.415270+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The sufficiency claim in Theorem 4.4 would be refuted by an explicit spectrahedron with singularity degree 2 whose external central path (4.1) has every vanishing eigenvalue of $X(\\alpha)$ bounded by a constant times $\\alpha$ as $\\alpha\\to 0$; following the path numerically for a small instance and measuring $\\lambda_{r+1}(X(\\alpha))/\\alpha$ would settle it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the classical upper bound on forward error in terms of backward error and singularity degree that the new lower bound complements."},{"cited_title":"Wei and H","cited_arxiv_id":null,"evidence_quote":"Provides the family of hard SDP instances with prescribed complementarity gap used in the numerical case studies (spec1 and spec4)."},{"cited_title":"Tun¸ cel.Polyhedral and Semidefinite Programming Methods in Combinatorial Optimiza- tion, volume 27 of Fields Institute Monographs","cited_arxiv_id":null,"evidence_quote":"Provides the worst-case SDP family (spec2) used to demonstrate the large gap between forward and backward error."},{"cited_title":"Goldfarb and K","cited_arxiv_id":null,"evidence_quote":"Shows the limit points of the primal-dual central path satisfy the relative-interior properties used in Theorem 4.2."},{"cited_title":"Halick´ a, E","cited_arxiv_id":null,"evidence_quote":"Establishes convergence of the central path to a singleton, which Theorem 4.2 relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the topological lemma used to rule out multiple limit points of the central path."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Documents the 'strange behaviour' of interior-point methods on the SDP instance used as spec3."},{"cited_title":"Sremac, H.J","cited_arxiv_id":null,"evidence_quote":"Provides the completion example used as spec5, with a known lower bound on singularity degree."}],"review_version":1}