{"id":"171bd85f-e471-48a1-9a5e-ee13e4a8c02c","arxiv_id":"2607.13701","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A penalty-based, lifting-free dual algorithm solves quadratic sum-of-squares programs with accelerated-gradient convergence guarantees and a reported average speed advantage over SCS (NSGM 1.40) on 240 regression benchmarks.","lead":"This paper presents a new way to solve quadratic sum-of-squares optimization problems that avoids enlarging them into harder conic forms: it adds a small penalty to keep closed-form updates and solves a smooth dual problem with accelerated gradient steps. The authors report roughly 40% faster solves than the SCS solver and far fewer failures than MOSEK on 240 constrained-regression benchmarks, with convergence guarantees.","discovery_kind":"extension","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a lifting-free regularization method for Quadratic Sum-of-Squares (QSOS) programs. A quadratic penalty is added to the SOS variables, only the affine constraints are dualized, and the resulting concave dual is maximized by Nesterov accelerated gradient. The authors provide closed-form primal updates (Lemmas 3.1–3.2), an explicit dual gradient and Lipschitz constant (Theorem 3.6), coercivity under a Slater and invertibility assumption (Theorem 4.3), asymptotic primal feasibility (Theorem 4.2), and a non-asymptotic O(1/N)+O(ρ) suboptimality bound (Theorem 4.5). Numerical experiments on 240 constrained regression problems report that the method solves all instances, is about 40% faster on average than SCS, and is more reliable than MOSEK on lifted formulations.","tokens_in":23081,"tokens_out":15974,"duration_ms":203103,"significance":"If the claims are fully established, the method would be a valuable scalable alternative to lifting-based solvers for large QSOS/QCP problems, with per-iteration cost dominated by PSD projections and no slack variables or augmented Lagrangians. The core derivations—closed-form minimizers, dual gradient, Lipschitz constant, and the suboptimality proof—are internally consistent and self-contained. The benchmark study is extensive and the empirical advantage is promising. However, the theoretical guarantees as stated do not cover the algorithm as implemented or the benchmark instances, which weakens the paper’s central message. With the gaps identified below addressed, the contribution could be suitable for publication.","major_comments":[{"comment":"The coercivity assumption (4.5), requiring each Z^(j)=A_sos^(j)A_sos^(j)T to be invertible, is violated in the constrained regression benchmarks. There m = n_f, while each SOS block has only h = (n_x+d)!/(n_x! d!) columns; for d>0, h<n_f, so rank(A_sos) ≤ h < m and Z is singular. Therefore Lemma 4.4 and Theorem 4.5 do not apply to the experiments. Please either prove coercivity under a weaker sufficient condition (e.g., A_f Q^{-1} A_f^T ≻ 0, which holds here) or explicitly state that the experiments lie outside the proven guarantees.","section":"§4, Theorem 4.3; §5"},{"comment":"The convergence analysis treats the standard accelerated gradient sequence λ^(k) without restart, but Algorithm 3.1 includes an adaptive restart (lines 7–10) and outputs the extrapolated point y^(k) (line 22). Theorem 4.1 bounds g(λ*)-g(λ^(N)), and Theorems 4.2/4.5 use λ^(N), not y^(k). No proof is given that the restarted sequence or the output y^(k) satisfies the same bounds. Please align the algorithm and the theory—either analyze the implemented variant, or change the output to λ^(k) and state that the bounds apply to that output.","section":"§3, Algorithm 3.1; §4, Theorem 4.1"},{"comment":"The statement “These guarantees are unconditional and hold for all problems without any additional assumptions” is incorrect. Theorem 4.5 requires Q≻0, a Slater point, and the invertibility condition (4.5) used in Theorem 4.3. Furthermore, the Q=0 linear SOS case highlighted in the introduction is outside the class covered by the closed-form update in (3.6). The assumptions should be clearly stated in the abstract and conclusion to avoid overclaiming.","section":"§6, Conclusion"}],"minor_comments":[{"comment":"The proof switches between treating ξ_sos as a vector in R^{h_j(h_j+1)/2} and as a symmetric matrix in S^{h_j}. Using svec/smat consistently throughout would improve readability.","section":"§4, Theorem 4.3 proof"},{"comment":"The paper does not describe how the Lipschitz constant L in (3.15) is computed or estimated for problems with m up to 20,000. Forming Γ = Σ A_sos^(j)A_sos^(j)T requires O(m^2) memory, so an implementation detail is missing. Please add the method used to obtain η=1/L.","section":"§5, Algorithm implementation"},{"comment":"The x-axis label is garbled (“Relativetimetosolve,=50”); it should be “Relative time to solve, τ”.","section":"§5, Fig. 1"},{"comment":"The proof is deferred to “[40]” with “similar arguments.” Since Nesterov’s rate is central to the paper, a more complete proof or a precise theorem statement with assumptions would be helpful.","section":"§4, Theorem 4.1 proof"},{"comment":"The abstract and conclusions claim memory scales only with the number of equality constraints, but the per-iteration PSD projection requires storing and eigendecomposing an h_j×h_j matrix. The claim should be qualified accordingly.","section":"§5, Memory claim"}],"recommendation":"major_revision","confidential_remarks":"The stress-test note claimed that assumption (4.5) holds in the benchmarks, but a direct dimension count shows it does not: for the SOS equality constraint, A_sos has more rows than columns. This is not merely a presentation issue; it means the main theorem does not cover the experiments. The authors should be asked to fix this gap, either by extending the coercivity argument or by clearly demarcating the applicability of the theorem. The rest of the technical content appears sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The math largely checks out, but the packaging is ahead of the analysis. The core idea—add a small norm penalty to SOS variables, dualize only the affine constraints—is clean and yields closed-form primal updates. I verified the central steps: Lemmas 3.1–3.2, the simplified dual (3.13), the gradient (3.14), the Lipschitz constant (3.15), the coercivity argument, and the suboptimality bound in Theorem 4.5 are internally consistent. The one minor slip is a bookkeeping error in beta_2 (Eq. 4.8), which is easily repaired. The paper is honest about building on Malick (2004) and Higham, and the related-work discussion is fair.\n\nThe bigger issues are mismatches between the claims and the analysis. The conclusion says the guarantees are \"unconditional,\" but Theorem 4.3 requires every Z^(j) = A_sos^(j) A_sos^(j)^T to be invertible, and Q must be positive definite. That rules out the Q=0 linear SOS case highlighted in the introduction and most multi-block SOS problems where a block couples to only a subset of constraints. The benchmarks use a single SOS block with well-conditioned coupling and engineered Q, so they don't stress these assumptions. More concerning: the convergence theorems are stated for the non-restarted lambda^(N) sequence, while Algorithm 3.1 uses adaptive restart and recovers the primal from y^(k). No argument connects the restarted iterates to the proven bounds. That is a genuine gap between theory and practice.\n\nThe numerical comparison has soft spots too. The paper skips the obvious direct-QCP competitors—Clarabel and COSMO—and the closest predecessor, SDLS/Henrion-Malick. The claimed memory advantage is not actually measured, and no code or data is released. These are addressable, and the observed speed and robustness gains over SCS on 240 regression problems are plausible.\n\nWhat is genuinely new is the regularization trick applied to general QSOS programs with closed-form updates and an explicit non-asymptotic bound. That is a real, if incremental, contribution to the conic first-order subfield. The derivation is self-contained and honestly sourced.\n\nThis paper deserves a serious referee. I would send it out, but with a revision request: align the abstract and conclusion with the actual assumptions, either analyze the restarted method or report results for the non-restarted variant, add multi-block experiments and Clarabel/COSMO comparisons, and release code. After that, it could be a solid journal paper.","headline":"A useful regularized-dual trick with mostly checkable bounds, but the claims outrun the analysis (restart mismatch, 'unconditional' line) and the benchmarks need better baselines.","tokens_in":23711,"tokens_out":5812,"would_cite":true,"duration_ms":616293,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C25","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Quadratic sum-of-squares programs can be solved directly, without conic lifting, by regularizing the SOS variables and maximizing a smooth concave dual.","keywords":["quadratic sum-of-squares","conic programming","dual gradient ascent","regularization","semidefinite projection","non-asymptotic convergence","first-order methods","constrained regression"],"falsifier":"Take a QSOS problem with two SOS blocks where one block's coupling matrix is rank-deficient while the combined constraint matrix is still surjective, run the algorithm, and check whether the affine feasibility residual decays as O(1/N) or stalls; the paper's coercivity theorem predicts the bound should not hold, so this separates the assumption from the method's practical behavior.","tokens_in":22918,"feed_emoji":"🧮","tokens_out":7071,"duration_ms":73059,"temperature":0.7,"pith_summary":"This paper aims to show that quadratic sum-of-squares programs—optimization problems with a convex quadratic objective and constraints expressed through sum-of-squares polynomials—can be solved without the usual trick of translating the quadratic objective into a second-order cone or semidefinite lifting that inflates the conic dimension. The proposed route adds a tunable norm penalty to the sum-of-squares variables, a small regularization that does not change the cone structure, and then maximizes the resulting concave dual with an accelerated gradient method. The payoff is a solver whose per-iteration work is dominated by one projection onto a positive semidefinite cone per SOS block, with memory that scales only with the number of equality constraints, and with a proven non-asymptotic guarantee: after N iterations the objective gap to the true optimum is O(1/N) plus a bias term that vanishes as the regularization shrinks. A sympathetic reader would care because this removes a computational bottleneck for large problems in system identification and machine learning, and the theory converts a heuristic regularization into a certified algorithm.","feed_headline":"Drop the lifting: solve quadratic sum-of-squares programs directly","feed_subtitle":"A norm penalty makes the dual smooth and concave; accelerated ascent provably closes the gap to the true optimum.","key_machinery":"The load-bearing object is the regularization term (rho/2) sum_j ||xi_sos^(j)||_2^2 added to the objective. This single modification preserves the original cone structure (no lifting), makes each SOS block's Lagrangian subproblem a Euclidean projection onto the positive semidefinite cone—a closed-form operation via eigenvalue thresholding—and makes the dual function concave, differentiable, and with Lipschitz gradient constant L = ||A_f Q^{-1} A_f^T||_2 + (1/rho) sum_j ||A_sos^(j) A_sos^(j)^T||_2. The same gradient equals the negative of the affine constraint residual, so monitoring it yields a combined primal-feasibility and optimality check. The polar-cone identity that rewrites ||P_{S_+}(","core_discovery":"The paper's central discovery is that adding the quadratic penalty (rho/2) sum_j ||xi_sos^(j)||^2 to the objective of a quadratic conic program does not merely stabilize the problem—it makes it solvable in closed form at each dual step and smooth in the dual. The partial Lagrangian separates into a free-variable piece, minimized by Q^{-1}(A_f^T lambda - w_f), and independent SOS pieces, each minimized by projecting (1/rho)(A_sos^(j)^T lambda - w_sos^(j)) onto the positive semidefinite cone. By the standard polar-cone decomposition, the dual function collapses to a concave quadratic minus squared norms of those projections, giving a globally Lipschitz gradient whose value is exactly the negat","pith_inferences":["The regularization is effectively a Moreau-Yosida smoothing of the SOS constraints in the dual, suggesting the method can be recast as a proximal point algorithm; that view would justify adaptive rho schedules (homotopy) that the paper leaves to future work.","The coercivity proof requires each SOS block's coupling Gram matrix A_sos^(j) A_sos^(j)^T to be invertible, a condition that fails in common sparse multi-block SOS problems; an extension using block-coordinate ascent or a shared regularizer across blocks would be needed to cover those instances—this is a boundary of the current claim, not a defect of the experiments, where a single surjective bloc","The same lifting-free dualization should transfer to quadratic conic programs over other cones with cheap projections (for instance, a second-order cone or a positive orthant), giving an immediate family of algorithms; the paper only demonstrates the PSD/SOS case.","A concrete testable extension is to decay rho geometrically across outer iterations and analyze the total iteration count needed to reach a target bias; the paper's fixed-rho bound suggests total complexity roughly O(1/epsilon) with a log factor, but that is not proven here."],"forward_implications":["For each iteration, the dominant computation is a single PSD projection per SOS block; no auxiliary conic variables or factorizations are introduced, so memory grows only with the number of equality constraints, not with the SOS block dimensions.","The dual gradient is the negative primal affine residual, so an O(1/N) feasibility certificate is obtained for free from the dual convergence rate; termination can be monitored without any additional solves.","Setting rho small makes the recovered solution arbitrarily close to the original optimum, with the trade-off that the Lipschitz constant and hence the iteration count grow as O(1/rho); the O(1/N) convergence of the accelerated scheme compensates for that growth.","The method applies to any QSOS problem with positive definite Q and a Slater point, including constrained regression and system identification examples; numerical evidence shows it can solve all benchmark instances where lifted interior-point solvers time out or exhaust memory."],"fun_headline_variants":["QSOS without lifting: penalty yields smooth dual","Norm penalty removes need for conic liftings in QSOS","Smooth dual via quadratic penalty: QSOS solved faster","Lifting-free QSOS: penalty makes dual concave and smooth","Quadratic penalty smooths QSOS dual, avoids lifting"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The central proofs require every SOS block to individually span all equality constraints (each A_sos^(j) A_sos^(j)^T invertible) and Q to be strictly positive definite, so the method's certified regime excludes sparse multi-block SOS problems and the linear SOS case Q=0.","fun_headline_variants_meta":{"raw":{"variants":["QSOS without lifting: penalty yields smooth dual","Norm penalty removes need for conic liftings in QSOS","Smooth dual via quadratic penalty: QSOS solved faster","Lifting-free QSOS: penalty makes dual concave and smooth","Quadratic penalty smooths QSOS dual, avoids lifting"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000468,"raw_usage":{"total_tokens":2133,"prompt_tokens":673,"completion_tokens":1460,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":417,"completion_tokens_details":{"reasoning_tokens":1375}},"tokens_in":417,"tokens_out":1460,"duration_ms":11848,"temperature":1.0,"reasoning_tokens":1375,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T04:02:08.561989+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a QSOS problem with two SOS blocks where one block's coupling matrix is rank-deficient while the combined constraint matrix is still surjective, run the algorithm, and check whether the affine feasibility residual decays as O(1/N) or stalls; the paper's coercivity theorem predicts the bound should not hold, so this separates the assumption from the method's practical behavior.","supporting_citations":[],"review_version":1}