{"id":"a7a94a8a-4663-4665-9e92-7dd9e8c57f2c","arxiv_id":"1908.05209","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":1.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A structured survey of scalable semidefinite programming covering sparsity, symmetry, low-rank factorization, first-order methods, and conservative LP/SOCP relaxations, with software pointers.","lead":"This paper surveys recent methods for making semidefinite programming, a powerful optimization tool, scale to larger problems in machine learning, control, and robotics. It organizes the field into four strategy families and lists software packages, so a practitioner can pick a starting point quickly.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Burer–Monteiro guarantee in Section 3.1.2 appears to state the wrong rank threshold: it says m < r(r+1)/2, while the cited Boumal–Voroninski–Bandeira theorem requires r(r+1)/2 > 2m. This overstates, by a factor of two, when low-rank factorizations are provably global.","rationale":"The survey's central claim is to provide a reliable entry point to scalable SDP methods, and Section 3 is one of the four pillars of that claim. The most load-bearing weakness I find is not the provenance of performance numbers but an internal correctness error in a guarantee the survey relays: the rank condition in Section 3.1.2 appears to drop a factor of two from the cited Burer–Monteiro theorem. If confirmed, this directly affects the conditions under which a practitioner may trust low-rank factorization to recover a global SDP optimum, which is exactly the kind of advice the paper offers. The reader's weakest assumption focused on representativeness of reported speedups; that is a legitimate data-assumption concern, but the threshold error is a sharper, verifiable technical issue. I agree with the reader that the Hazan update sign error in Section 3.2.1 is real and that it warrants correction. However, because it is confined to one displayed update and is easily repaired, it is less consequential than the Burer–Monteiro condition. My recommendation is unchanged from the reader's CONDITIONAL verdict: the paper is broadly well-structured and useful, but the Section 3.1.2 theorem statement should be checked against [25] and corrected, and the Hazan update should be fixed.","tokens_in":28667,"tokens_out":12785,"duration_ms":139488,"concrete_test":"Open the published version of [25, Theorem 2] (Boumal, Voroninski, and Bandeira, NIPS 2016) and transcribe the exact rank condition. If it reads r(r+1)/2 > 2m (or ≥ 2m), then the survey's 'm < r(r+1)/2' in Section 3.1.2 is false and the section needs correction. As a secondary check, run a random smooth SDP with m=4, n=6, r=3 from many random starts in Manopt: the survey's condition claims a guarantee in this regime while the cited theorem does not, so a returned second-order critical point with objective above the true SDP optimum would confirm that the survey's threshold misleads in practice.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1.2 tells readers that if m < r(r+1)/2, the feasible manifold is smooth and compact, and C is generic, then every second-order critical point of the Burer–Monteiro factorization is globally optimal to the SDP, citing [25, Theorem 2]. The theorem in the cited paper actually requires r(r+1)/2 > 2m (some versions use ≥ 2m): the factorized rank must be sufficiently large relative to the number of equality constraints to rule out spurious second-order critical points. The survey's condition is weaker by a factor of two. For example, with m=4 and r=3, the survey's inequality 4<6 would claim a guarantee, whereas the cited theorem requires 8≤6, which fails. This matters because Section 3 explicitly promises 'provably recover global low-rank solutions' in Case 1, and the Section 1.1 decision guide directs users with low-rank SDPs to this material. The earlier Barvinok–Pataki existence bound r(r+1)/2 ≤ m identifies only the minimal rank of an optimal solution, roughly sqrt(2m); the Burer–Monteiro guarantee needs rank roughly 2sqrt(m). A reader who chooses r from the existence bound can land exactly in the regime where spurious second-order critical points are generic. The Hazan sign error flagged by the reader is real but local and fixable; the threshold error changes the scope of a central guarantee and is therefore more load-bearing for the survey's practical advice.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper is a survey of four families of techniques for scaling semidefinite programming: exploiting problem structure (sparsity, symmetry, facial reduction), producing low-rank solutions (Burer–Monteiro and Frank–Wolfe methods), using ADMM and augmented Lagrangian methods, and trading off conservatism for scalability via LP/SOCP relaxations (DSOS/SDSOS and adaptive variants). It additionally provides a decision guide, applications in machine learning, control, and robotics, and a software list. The paper makes no new algorithmic or theoretical claims; its value is as an entry point to the scalable SDP literature.","tokens_in":28964,"tokens_out":10994,"duration_ms":114744,"significance":"The survey addresses a timely and important need, and its high-level organization into four methodological families is sensible and useful. It is clearly written, gives a good overview of chordal sparsity, symmetry reduction, ADMM-based conic solvers, and the DSOS/SDSOS framework, and the software list and decision guide are potentially valuable for practitioners. The paper does not present new algorithms or reproducible experiments, so its correctness rests entirely on the accuracy of its descriptions of existing results. The two technical errors identified below both occur in Section 3, which is exactly the part of the survey that the decision guide in Section 1.1.1 directs readers to for low-rank SDPs; they are therefore load-bearing for the survey's practical value.","major_comments":[{"comment":"The stated condition for the global optimality of second-order critical points is incorrect. The text says 'if m < r(r+1)/2' then, under smoothness and compactness, every second-order critical point of Problem (11) is globally optimal for almost all C, citing [25, Theorem 2]. The theorem in [25] requires r(r+1)/2 > 2m. The survey's inequality is weaker by a factor of two and is the complement of the Barvinok–Pataki existence bound in Eq. (8), so a reader who chooses r from Eq. (8) can land precisely in the regime where spurious second-order critical points are known to occur. This overstates the scope of the 'provably recover global low-rank solutions' promise in Case 1 and undermines the corresponding guidance in Section 1.1.1. Please correct the threshold and adjust the surrounding discussion, including the claim that smoothness follows from the stated inequality.","section":"§3.1.2, Burer–Monteiro guarantee"},{"comment":"The displayed update for Hazan's algorithm is wrong. The text sets X_{k+1} = (1 − α_k) X_k + α_k (−v_k v_k^T), where v_k is the eigenvector for the maximum eigenvalue of ∇f(X_k). The correct Frank–Wolfe update on the trace-one spectrahedron is X_{k+1} = (1 − α_k) X_k + α_k v_k v_k^T, with v_k an eigenvector for the minimum eigenvalue of ∇f(X_k) (equivalently, the maximum eigenvalue of −∇f(X_k)). As printed, the update has trace 1 − 2α_k, so it violates the trace-one constraint and is not a valid Frank–Wolfe step for Problem (14). This is a local but substantive error in a central algorithm description and should be corrected.","section":"§3.2.1, Hazan's Frank–Wolfe update"}],"minor_comments":[{"comment":"Typo: 'convservative' should be 'conservative'.","section":"§1.1.1"},{"comment":"The notation in the reduced problem reuses m both for the number of constraints and for the dimension of the reduced cone. Please use distinct symbols to avoid confusion.","section":"§2.2, Eq. (7)"},{"comment":"The sentence 'an optimal solution of rank≤k is guaranteed to exist here' uses an undefined variable k; it should refer to the factorization rank r.","section":"§3.1.2"},{"comment":"The accuracy statement 'f(X) ≤ f* + Ω(1/k)' should use O(1/k); Ω denotes a lower bound and is not the correct notation for an approximation guarantee.","section":"§3.2.1"},{"comment":"Reported performance figures such as the 'less than 3 × 10^-4 reconstruction error' and the order-of-magnitude speedups come from specific instances in the cited papers; a brief caveat that these numbers are instance-dependent would help practitioners calibrate expectations.","section":"§4.1"}],"recommendation":"major_revision","confidential_remarks":"The survey is useful and generally well constructed, but Section 5 and parts of the software list are drawn very heavily from the authors' own DSOS/SDSOS work (references 7–11 and 75), and SPOT is listed as the parser for that framework. This is not by itself a reason to reject, but given the disclosure statement's claim of no perceived conflicts, the editors may wish to consider whether the emphasis is appropriately balanced. The two technical errors in Section 3 should be fixed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The survey is a solid, well-structured gateway to recent work on scaling semidefinite programs. If you work near SDPs in control, ML, or robotics, this is a good first stop: the four-way organization (structure, low rank, ADMM/augmented Lagrangian, conservative relaxations) is sensible, the decision guide in Section 1.1.1 is genuinely useful, and the software list is a practical bonus. The DSOS/SDSOS material in Section 5 is clear and accurate as far as it goes, even though it is drawn largely from the authors' own papers; that is not a flaw in itself, but a caveat about the provenance of the speedup numbers would be appropriate.\n\nThat said, there are two technical errors that matter. The sign error in Hazan's update (Section 3.2.1) is real but local: writing X_{k+1} = (1−α)X_k + α(−v v^T) breaks the trace-one constraint; the plus sign is needed. That is a typo-level fix. The more serious issue is in Section 3.1.2: the survey states the Burer–Monteiro guarantee as m < r(r+1)/2, whereas the cited Boumal–Voroninski–Bandeira theorem requires r(r+1)/2 > 2m. This is off by a factor of two. A practitioner who picks r to satisfy the Barvinok–Pataki existence bound r(r+1)/2 ≤ m lands exactly in the regime where the theorem does not apply, so the survey's promise of provable global optimality is overstated in a load-bearing way. This needs to be corrected and ideally flagged so readers do not choose ranks based on the wrong threshold.\n\nThe survey makes no new algorithmic claims, which is fine for a review, and the citation pattern is broad enough that the self-citations do not dominate. Overall, I would send this to a serious referee: the errors are fixable and the survey is likely to be widely used as an entry point, so it deserves careful review rather than a desk rejection. After the corrections, I would be happy to recommend it.","headline":"A well-organized, genuinely useful entry point to the scalable SDP literature, but it overstates the Burer–Monteiro guarantee by a factor of two and has a sign error in Hazan's Frank-Wolfe update; both are fixable and should be corrected before publication.","tokens_in":29552,"tokens_out":3093,"would_cite":true,"duration_ms":28937,"reading_group":"maybe","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 survey argues that four complementary families of methods (structure exploitation, low-rank factorization, first-order splitting, and conservative LP/SOCP relaxations) now make large semidefinite programs practical in machine…","keywords":["semidefinite programming","scalability","sum of squares","chordal sparsity","low-rank factorization","ADMM","DSOS/SDSOS optimization","control and robotics"],"falsifier":"Run the four families head-to-head on a standardized suite of large SDP instances drawn from the survey's own use cases (sparse Lyapunov analysis with clique size below 15, robust PCA on a dense matrix, 100x100 sparse PCA, planar pose-graph SLAM) and compare wall-clock time to fixed accuracy against interior-point solvers. If chordal decomposition does not deliver speedups near the reported factor, or SDSOS loses far more than 2-3% optimality, or ADMM's accuracy degrades well beyond $3\\times10^{-4}$ reconstruction error, the survey's decision guide fails.","tokens_in":28414,"feed_emoji":"📐","tokens_out":9069,"duration_ms":82878,"temperature":0.7,"pith_summary":"Semidefinite programs (SDPs) are convex optimization problems over positive semidefinite matrices, and they are famously expressive but historically slow: interior-point solvers require dense matrix operations that blow up in time and memory. This survey claims that a recent wave of methods has changed that situation, and that the practical routes to scalable SDPs fall into four complementary families: exploiting structure such as sparsity and symmetry, seeking low-rank solutions through factorizations, using first-order splitting methods (ADMM and augmented Lagrangian), and trading off optimality for feasibility with linear and second-order cone approximations. A practitioner reading the survey is meant to come away with a decision guide: use structure when it is present, low-rank methods when low-rank solutions exist or are desired, first-order methods when approximate feasibility is acceptable, and conservative LP/SOCP relaxations when guaranteed feasibility matters more than optimality. The survey also curates a software list keyed to each route. The paper's claim is not that any single method wins, but that the barriers that made SDPs prohibitive in machine learning, control, and robotics are now attackable by one of these four strategies.","feed_headline":"Four routes now scale semidefinite programming to real problems","feed_subtitle":"Structure, low-rank, splitting, and relaxation tricks deliver order-of-magnitude speedups in machine learning, control, and robotics.","key_machinery":"The load-bearing machinery is a portfolio of four identities and algorithmic templates. Chordal sparsity rests on a decomposition theorem (Proposition 1): a positive semidefinite matrix with a chordal sparsity pattern is a sum of positive semidefinite matrices supported on maximal cliques, which turns one big semidefinite constraint into several small ones plus equalities. Low-rank methods rest on the factorization $X=VV^T$ with $V\\in\\mathbb{R}^{n\\times r}$, which cuts storage from $O(n^2)$ to $O(nr)$ and converts the conic problem into a nonconvex smooth one. The ADMM family rests on rewriting primal and dual SDPs as a homogeneous self-dual embedding and then applying operator splitting updates. The conservative family rests on diagonally dominant (dd) and scaled diagonally dominant (sdd) matrix cones and their polynomial counterparts (dsos and sdsos polynomials), which are semidefinite-representable inner approximations of the PSD cone whose membership constraints are LPs and SOCPs. Each template is what carries the corresponding scalability gain in the survey's narrative.","core_discovery":"On the paper's own terms, the central discovery is organizational: the many recent scalability improvements for SDPs cluster into four approaches with different cost-quality tradeoffs. Structure exploitation uses chordal sparsity and symmetry to replace one large semidefinite constraint by many smaller ones, sometimes reducing Lyapunov synthesis runtimes by a factor of about 80. Low-rank methods factor the semidefinite variable as $X = VV^T$ and typically solve the smaller nonconvex problem with Riemannian or coordinate-descent tools, with guarantees that second-order critical points are globally optimal when the number of constraints is below a threshold. ADMM and augmented Lagrangian solvers work on the homogeneous self-dual embedding of the primal-dual pair and can handle instances where interior-point solvers run out of memory, at a small cost in accuracy (for robust PCA, under $3\\times10^{-4}$ reconstruction error). Conservative relaxations replace the positive semidefinite cone with cones of diagonally dominant or scaled diagonally dominant matrices, leading to LP/SOCP problems that can be over 1000 times faster than the SDP on sparse PCA instances while sacrificing a few percent of optimality. The survey holds that these four families are largely complementary and can be combined.","pith_inferences":["Across the four families one sees a shared pattern: replace the expensive PSD cone by a cheaper surrogate and then refine it. This suggests a general recipe the paper does not spell out: any application yielding an SDP could first try a cheap LP/SOCP inner approximation, then zoom in with low-rank or first-order refinement only where the relaxation is too loose.","The survey's decision guide implies a testable engineering hypothesis: a benchmark suite spanning Lyapunov synthesis, robust PCA, sparse PCA, and pose-graph SLAM should reveal that no single method dominates, but that the optimal choice is predictable from instance structure (sparsity level, number of constraints, feasibility tolerance).","The success of adaptive DSOS/SDSOS hierarchies hints that the boundary between exact SDP and cheap relaxation is not fixed: iterative basis changes and column generation can climb from the LP/SOCP side toward SDP accuracy, which, if pushed further, could erode the need for interior-point precision in many applications.","The paper explicitly sets aside nonconvex local-descent alternatives to SDP relaxations. If those methods keep improving, the practical role of SDPs in machine learning may shift from being the solver of choice to being a certifier of solutions found by other means, a shift the survey's framework does not address."],"forward_implications":["If the survey's map is right, a practitioner facing a large SDP should first look for chordal sparsity, symmetry, or degeneracy, since structure exploitation preserves exactness while shrinking the semidefinite blocks.","For SDPs with few constraints, low-rank factorization (Burer-Monteiro) is a provably safe strategy: when $m < r(r+1)/2$, a rank-$r$ optimal solution exists, and second-order critical points of the factored problem are globally optimal for almost all objectives.","When approximate solutions with slightly violated constraints are tolerable, ADMM and augmented Lagrangian solvers can reach instances that are out of memory for interior-point solvers.","When guaranteed feasibility is required and speed matters more than optimality, DSOS/SDSOS relaxations turn the PSD constraint into LP/SOCP constraints, and adaptive improvements (change of basis, column generation) tighten the inner approximation iteratively.","The four routes can be combined, for example chordal sparsity inside a first-order solver, or low-rank factorization on a sparsity-reduced SDP, which the survey explicitly encourages."],"supporting_citations":[{"why":"Supplies the chordal-sparsity decomposition theorem (Proposition 1) that turns one large PSD constraint into many small ones, the foundation of Section 2.1.","marker":"[6]"},{"why":"Introduces the low-rank factorization that turns a PSD decision variable into a product of a thin matrix with its transpose, and the augmented Lagrangian method that Section 3.1 builds on.","marker":"[30]"},{"why":"Supplies the homogeneous self-dual embedding plus ADMM splitting that lets first-order solvers attack large conic programs, the backbone of Section 4.1.","marker":"[81]"},{"why":"Introduces DSOS/SDSOS optimization, the LP/SOCP alternatives to SOS/SDP that Section 5.1 and the 1000x sparse-PCA speedup rest on.","marker":"[10]"},{"why":"Proves that under a low-rank bound and smoothness assumptions, second-order critical points of the Burer-Monteiro factorization are globally optimal, the main theoretical support for Section 3.1.","marker":"[25]"},{"why":"Presents the augmented Lagrangian method (SDPNAL+) that Section 4.2 relies on for solving degenerate SDPs and large clustering problems.","marker":"[121]"},{"why":"Provides the Sparse-BSOS hierarchy that underlies the globally optimal SLAM results in Section 2.1.1.","marker":"[118]"},{"why":"Develops the automated facial and symmetry reduction framework that Section 2.3 uses for problems like the rimless wheel stability analysis.","marker":"[90]"}],"fun_headline_variants":["Four ways to speed up semidefinite programming","SDP scalability survey: four routes to real-world speedups","Cracking the SDP scalability wall: four strategies","Big SDPs, small effort: four scalable approaches","Semidefinite programming gets a scalability upgrade"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The survey's practical guidance stands or falls with the assumption that the speedups it reports from cited papers, roughly 80x for chordal Lyapunov SDPs, over 1000x for SDSOS on sparse PCA, and under $3\\times10^{-4}$ reconstruction error for ADMM on robust PCA, are representative of typical instances rather than favorable ones.","fun_headline_variants_meta":{"raw":{"variants":["Four ways to speed up semidefinite programming","SDP scalability survey: four routes to real-world speedups","Cracking the SDP scalability wall: four strategies","Big SDPs, small effort: four scalable approaches","Semidefinite programming gets a scalability upgrade"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000554,"raw_usage":{"total_tokens":2662,"prompt_tokens":989,"completion_tokens":1673,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":1597}},"tokens_in":605,"tokens_out":1673,"duration_ms":14018,"temperature":1.0,"reasoning_tokens":1597,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:19:27.115843+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the four families head-to-head on a standardized suite of large SDP instances drawn from the survey's own use cases (sparse Lyapunov analysis with clique size below 15, robust PCA on a dense matrix, 100x100 sparse PCA, planar pose-graph SLAM) and compare wall-clock time to fixed accuracy against interior-point solvers. If chordal decomposition does not deliver speedups near the reported factor, or SDSOS loses far more than 2-3% optimality, or ADMM's accuracy degrades well beyond $3\\times10^{-4}$ reconstruction error, the survey's decision guide fails.","supporting_citations":[{"cited_title":"O’Donoghue, E","cited_arxiv_id":null,"evidence_quote":"Supplies the homogeneous self-dual embedding plus ADMM splitting that lets first-order solvers attack large conic programs, the backbone of Section 4.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Presents the augmented Lagrangian method (SDPNAL+) that Section 4.2 relies on for solving degenerate SDPs and large clustering problems."},{"cited_title":"Weisser, J","cited_arxiv_id":null,"evidence_quote":"Provides the Sparse-BSOS hierarchy that underlies the globally optimal SLAM results in Section 2.1.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Develops the automated facial and symmetry reduction framework that Section 2.3 uses for problems like the rimless wheel stability analysis."}],"review_version":1}