{"id":"0e7bc888-0a37-48ba-81ad-d8ef6bea072a","arxiv_id":"2504.16330","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"An explicit convex hull for rank-one quadratic optimization with step function penalties is derived, enabling stronger copositive and SDP relaxations and a robust convex SVM surrogate.","lead":"This paper derives the exact convex hull of a rank-one quadratic epigraph with sign-indicator binary choices, and uses it to build copositive and semidefinite relaxations. The relaxations yield a convex surrogate for support vector machines with 0-1 loss that is robust to label noise and outliers.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Theorem 1 appears correct within its stated unbounded-variable scope.","rationale":"The reader's weakest assumption is that the proof relies on unbounded continuous variables and that the convex hull description fails if x is bounded or F adds coupling constraints. This is accurate as a scope statement, but it is not a load-bearing objection to the paper's central claim, because Theorem 1 is explicitly a result about the unbounded set X_d with F = R^n x {0,1}^n, and the paper does not claim the bounded case. I checked the proof of Proposition 3 case by case. The gamma < 0 and gamma = 0 cases are handled correctly: when gamma = 0 and alpha has unequal entries, the construction x_i = -x_j = lambda with z_i = 1 and z_j = 0 keeps d^T x = 0 and makes alpha^T x unbounded below while t = 0 stays feasible; when alpha = eta*1, the objective reduces to beta^T z plus a linear function of the sum of x, which is unbounded for any nonzero eta because t is unpenalized at gamma = 0. For gamma > 0, the reduction to the two TU subproblems is valid. I also checked the extension to arbitrary sign patterns in Theorem 1 and the one-sided set in Proposition 4; both follow from the stated variable transformations. The missing proof of Proposition 9 is a genuine omission, but the statement is a straightforward one-sided variant of Proposition 8, and its validity can be verified directly from the copositive Schur complement, so it does not undermine the central claim. The experimental claims are conditional on Gurobi finding feasible solutions, but those are empirical matters rather than correctness risks for the convex hull theorem. Overall, the central claim holds up under scrutiny, and the paper's conditional status is appropriate mainly for the omitted proof and lack of code, not for a mathematical flaw in Theorem 1.","tokens_in":34043,"tokens_out":29785,"duration_ms":286634,"concrete_test":"Independently re-derive Proposition 3 for n = 2, d = (1,1), and the case gamma = 0, alpha = eta*1: verify that the relaxation value equals the minimum over the two integer totally unimodular subproblems, and symbolically compute conv(X_d) for a small grid of objectives to confirm the formula. If any mismatch appears, Theorem 1 needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking Proposition 3 in detail, the central convex-hull claim is internally consistent. The proof's case analysis for gamma = 0 is not circular: when t is unpenalized, choosing x along a direction that keeps d^T x = 0 while alpha^T x -> -infinity makes both the MIP and the relaxation unbounded, exactly as the proof states; when alpha = eta*1, the reduction to the two totally unimodular subproblems covers both signs of eta. The reader's unboundedness caveat is a scope limitation, not a flaw: Theorem 1 is stated for x in R^n, and the paper explicitly delegates bounded-variable and more general F cases to references [3, 27, 49, 75]. The omitted proof of Proposition 9 and the absence of code are real completeness gaps, but they do not contradict the central claim.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies mixed-integer quadratic programs with sign-indicator constraints (z_i=1 implies x_i>=0, z_i=0 implies x_i<=0) and step-function penalties, and develops convex relaxations for them. The central theoretical result, Theorem 1, gives an explicit description of cl conv(X_d) for rank-one Q=dd^T in terms of two perspective terms whose denominators depend on the signs of the entries of d. Using this rank-one description, the authors derive copositive and semidefinite valid inequalities for the extended set \\bar X, specialize the resulting relaxations to support vector machines with 0-1 loss, and report computational experiments on synthetic and UCI data.","tokens_in":34198,"tokens_out":15286,"duration_ms":149271,"significance":"The proof of Theorem 1 is a genuine linear-objective separation argument rather than a restatement of a known result, and the hull description is parameter-free and directly usable. If correct, the paper provides a useful bridge between the extensively studied indicator-variable set Y_Q and the sign-indicator set X_Q, and the copositive/SDP relaxations for \\bar X, together with their SVM specialization, are of clear practical interest. The computational study is extensive, compares against big-M MIO in a fair way, and documents numerical issues honestly. The main weakness is that not all load-bearing supporting results are proved in the manuscript, which is the reason for the requested revision.","major_comments":[{"comment":"Proposition 9 is stated without proof even though Proposition 10, the SDP relaxation used in all SVM experiments of §7, is built directly on it. Because the computational claims depend on this inequality, the manuscript should either provide a proof, which should be parallel to the proof of Proposition 8, or cite a source where the result is proved.","section":"§5, Proposition 9"},{"comment":"The proof of Proposition 3 handles the remaining case gamma=1, d=1, alpha=eta*1 only for eta<=0, and the sentence \"A similar analysis applies to the case eta>0\" omits the corresponding subproblems. Since Theorem 1 and all subsequent relaxations reduce to this proposition, the eta>0 case should be written out; the needed reduction to two totally unimodular linear programs is short, but it is not present in the manuscript.","section":"§4, Proposition 3"},{"comment":"The extension from d>0 to d>=0 in the proof of Theorem 1 is asserted with the sentence \"taking sums over the support of d removes the unused components of z.\" Variables with d_i=0 still satisfy sign-indicator constraints in X_d, so a brief argument that their convex hull contributes no additional inequalities is needed for the proof to be self-contained.","section":"§4, Theorem 1"}],"minor_comments":[{"comment":"In the gamma=0 case, the phrase \"letting x_i->infinity and setting z_i=1, or by letting x_i->-infinity or z_i=0\" should read \"... and setting z_i=0,\" as the current wording is a typo.","section":"§4, Proof of Proposition 3"},{"comment":"The remark that MIO problems are \"in most cases infeasible\" for p<=5 is confusing because formulation (11) is feasible for any w when M is sufficiently large; please clarify whether solver-reported infeasibility or a modeling choice is meant.","section":"§7.1"},{"comment":"The sentence \"the proposed formulation in Proposition 10 retains convexity and can be solved to global optimality\" should be worded as a statement about a convex relaxation of the 0-1 problem, since (36) is a relaxation and not an exact reformulation of (9).","section":"§6.3"},{"comment":"The experimental section would benefit from a statement on code and data availability; the paper reports averages over many replications but no repository is referenced.","section":"§7"},{"comment":"The caption should state explicitly that the gaps reported for conic1 and conic2 are computed against the best feasible solution found by Gurobi and are therefore upper bounds on the true optimality gap, since the relaxation value is a lower bound.","section":"§7.1, Tables 1 and 2"}],"recommendation":"major_revision","confidential_remarks":"The central convex-hull claim appears sound, and I agree with the reader's assessment that the unbounded-variable assumption is a scope limitation rather than a flaw. My main concerns are completeness of the proof chain, specifically the omitted eta>0 case in Proposition 3 and the unproved Proposition 9; both are repairable within the scope of a revision. The paper fits the journal's scope well, and I would not require new experiments for acceptance, although a code/data link would strengthen reproducibility."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth your time. The central result is Theorem 1: a closed-form convex hull for the epigraph of (d^T x)^2 with sign-indicator constraints, for arbitrary d in R^n. That is genuinely new. It is not the Atamturk-Gomez rank-one indicator set Y_R1, where x_i(1-z_i)=0 forces a variable to zero when its indicator is off. Here the indicator only constrains the sign, so zero is always feasible; that is exactly the structure behind step-function penalties like 0-1 loss SVMs. The proof is by linear-objective separation, reducing to two totally unimodular subproblems after projecting out x. I checked the gamma=0 and alpha=eta*1 cases; the argument holds. The unboundedness of x is doing real work, so the hull is for R^n, not for bounded boxes. That is a scope limitation, not a flaw, since the paper says so.\n\nThe downstream material is solid too. The copositive/SDP reformulations in Section 5 are a natural bridge from the rank-one hull to general Q, and Section 6's reformulation into cones of dimension p instead of n is what makes the SVM application tractable. The experiments are honestly reported: conic1 gives much better lower bounds than Gurobi's big-M when p is large, but Gurobi wins on small p; on real data no single method dominates, and the best average performer is the hinge+conic1 combination, which is a hedge rather than a clean win. The robust-estimator claim is supported on synthetic label-noise settings, especially the clustered outlier case where hinge breaks down.\n\nSoft spots: Proposition 9 is stated without proof in a paper whose contribution is derived relaxations; it looks like a one-sided analogue of Proposition 8, but it needs to be proved in the revised version. The lower-bound tables only include instances where Gurobi found a feasible solution, and they condition on that; it is disclosed, but easy to over-read. conic2 has numerical issues at p=50, reported rather than hidden. No code or data is shipped, which matters for an applied section of this size.\n\nI would send this to peer review. The central theorem deserves expert checking, and the SVM application, even with mixed real-data results, is worth publishing if the proof gaps are closed.","headline":"A correct new convex hull for sign-indicator step penalties, with an honestly reported SVM application; the proof gaps are small and worth a serious referee.","tokens_in":34719,"tokens_out":2842,"would_cite":true,"duration_ms":26983,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C20","90C22","90C25","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a two-term perspective inequality is the exact convex hull of a rank-one quadratic with sign-indicator step penalties, and uses it to build fast convex relaxations for 0-1-loss support vector machines.","keywords":["convex hull","rank-one quadratic","step function penalties","sign indicator constraints","copositive programming","semidefinite relaxation","robust support vector machine","0-1 loss"],"falsifier":"Fix $d=(1,1)$, add the bound $-1\\le x_i\\le 1$ to every continuous variable in $X_d$, and minimize $\\alpha^\\top x+\\beta^\\top z+t$ with $\\alpha=(0,1)$, $\\beta=0$ over the mixed-integer set and over the convex set of Theorem 1; if the two optimal values differ, the unboundedness assumption is essential and the claimed hull description does not extend to bounded variables.","tokens_in":33876,"feed_emoji":"🧮","tokens_out":9535,"duration_ms":86649,"temperature":0.7,"pith_summary":"This paper works with mixed-integer quadratic problems in which a binary variable $z_i$ records the sign of a continuous variable $x_i$, so a fixed cost is paid exactly when $x_i>0$; these are step-function penalties. The central result is an exact description of the convex hull of the epigraph set $t\\ge (d^\\top x)^2$ under those sign constraints: the quadratic splits into a positive part and a negative part, each divided by the number of coordinates whose binary setting allows that sign, with each denominator capped at one. Because the general convex quadratic case can be reached through the matrix variable $X\\succeq xx^\\top$, this rank-one hull is converted into copositive and semidefinite valid inequalities. In the support vector machine application with the 0-1 loss, the resulting relaxations produce bounds that are much stronger than big-M branch-and-bound in hard instances, and the relaxed solution itself behaves as a robust classifier under label noise and outliers. If the paper is right, a non-convex 0-1 loss becomes a convex program whose size grows linearly in the number of data points.","feed_headline":"Exact convex hull for step-penalized quadratics","feed_subtitle":"A split perspective inequality turns 0-1-loss SVM into a convex program that scales with data points, not features.","key_machinery":"The load-bearing object is the rank-one epigraph set $X_d$ with sign-indicator constraints, together with the two-term perspective inequality of Theorem 1. The proof of exactness works by linear separation: for any objective, unbounded rays force the linear coefficient vector to be proportional to $d$, after which the relaxation decomposes into two totally unimodular linear programs with integer optimal solutions. The machinery then lifts this inequality from scalars $t$ and vectors $x$ to the matrix level: the infinite family over all $d\\in\\mathbb{R}^n_+$ is encoded by two copositive-matrix constraints via the copositive Schur complement, and because $X\\succeq xx^\\top$ holds, those copositive constraints are equivalent to semidefinite constraints with auxiliary vectors $g,h$ sandwiching $x$. In the SVM application the same inequalities are expressed through $W\\succeq ww^\\top$, replacing $n$-dimensional cones by $(p+1)$-dimensional ones.","core_discovery":"The claim is Theorem 1: for any vector $d\\in\\mathbb{R}^n$, the closure of the convex hull of $X_d=\\{(x,z,t)\\in\\mathbb{R}^n\\times\\{0,1\\}^n\\times\\mathbb{R}: t\\ge (d^\\top x)^2,\\ x_i z_i\\ge 0,\\ x_i(1-z_i)\\le 0\\text{ for all }i\\}$ is exactly the set with $0\\le z\\le 1$ and $$t\\ge \\frac{(d^\\top x)_+^2}{\\min\\{1,\\sum_{i\\in\\operatorname{supp}_+(d)}z_i+\\sum_{i\\in\\operatorname{supp}_-(d)}(1-z_i)\\}}+\\frac{(d^\\top x)_-^2}{\\min\\{1,\\sum_{i\\in\\operatorname{supp}_-(d)}z_i+\\sum_{i\\in\\operatorname{supp}_+(d)}(1-z_i)\\}},$$ where $(v)_+=\\max\\{v,0\\}$ and $(v)_-=\\min\\{v,0\\}$. The denominators count the coordinates that can actually contribute the relevant sign: a coordinate with $d_i>0$ is allowed to be positive when $z_i=1$, while a coordinate with $d_i<0$ allows a positive contribution when $z_i=0$, and similarly for the negative part. The paper then shows that requiring this inequality to hold for every nonnegative direction $d$ is equivalent to two copositive constraints on the matrix $X$, and because the relaxation already has $X\\succeq xx^\\top$, those copositive constraints can be rewritten as semidefinite constraints with auxiliary vectors $g,h$; in the SVM setting the same inequalities are expressed through $W\\succeq ww^\\top$, with cone dimension $p+1$ rather than $n+1$.","pith_inferences":["The paper's convex hull is stated for unconstrained sign indicators; a natural testable extension is to bounded or box-constrained $x$, where the denominators would likely count how many coordinates can actually reach the boundary, and the paper's own proof of Proposition 3 pinpoints where unboundedness enters.","Because the hull handles arbitrary sign patterns of $d$, it applies directly to any quadratic whose Hessian is a single rank-one term, such as one-dimensional projections in sparse PCA or pairwise interaction models, suggesting a decomposition algorithm that strengthens one rank-one direction at a time.","The equivalence between the infinite rank-one inequalities and copositive constraints suggests that approximation hierarchies for the copositive cone could yield polyhedral relaxations with controlled size, extending the approach beyond low-dimensional feature spaces.","The closed-form loss in Proposition 12 predicts a specific shape for robust losses; one could test whether plugging $\\phi$ into other classifiers, such as logistic regression with label noise, preserves the out-of-sample gains observed for SVM."],"forward_implications":["For any fixed rank-one matrix $Q=dd^\\top$, the relaxation given by Theorem 1 is exact: solving the convex SOCP gives the same value as the mixed-integer problem, so the nonconvex step penalty costs nothing in this case.","For a general positive-semidefinite $Q$, the family of rank-one inequalities is equivalent to finitely many copositive constraints, and these can be rewritten as semidefinite constraints; this gives a tractable relaxation that dominates the plain $X\\succeq xx^\\top$ relaxation.","In SVM with the 0-1 loss, the relaxation can be formulated with semidefinite cones of dimension $p+1$ and, for singleton subsets, $O(n)$ conic constraints, so runtime grows linearly in the number of data points and the method scales to thousands of points when $p$ is small.","Used directly as an estimator, the relaxation's solution matches or beats the hinge-loss SVM under clustered or spread label noise, and combines well with hinge loss when no outliers are present.","The derived loss $\\phi(x;d,\\lambda)$ is a closed-form non-convex robust loss that is globally solvable through the convex relaxation, giving a convex surrogate for the 0-1 loss with a concave penalty on large violations."],"supporting_citations":[{"why":"Supplies the prior rank-one convexification and perspective inequalities for indicator variables that Theorem 1 extends from sparsity indicators to sign indicators.","marker":"[7]"},{"why":"Defines the big-M MIO formulation for SVM with ramp and 0-1 loss whose weak relaxation is the main computational baseline.","marker":"[19]"},{"why":"Introduces the SVM problem and the hinge-loss surrogate that the paper contrasts with the 0-1 loss.","marker":"[23]"},{"why":"Gives the perspective cuts and the convex hull of the one-dimensional set $Y_1$ used in the extended-form interpretation of Theorem 1.","marker":"[35]"},{"why":"Provides the copositive Schur complement criterion that converts the infinite family of rank-one inequalities into finitely many copositive constraints.","marker":"[72]"},{"why":"Supplies the robustSVM baseline and its $\\ell_1$-penalized formulation used in the statistical comparisons.","marker":"[13]"},{"why":"Defines the ramp-loss SVM, one of the non-convex robust losses compared with the derived $\\phi$ loss.","marker":"[87]"},{"why":"Proposes a related MIP SVM formulation and the label-corruption experimental setup replicated in the real-data tests.","marker":"[54]"}],"fun_headline_variants":["Step-penalized quadratics: exact convex hull","Exact convexification of step-penalized quadratics","Quadratic step penalties: exact convex hull","From step penalties to convex SVM: exact hull","Convex hull for step-penalized quadratics: exact"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convex hull description is exact only when the continuous variables $x$ are unbounded and the feasible set imposes no constraints beyond the sign indicators; the proof uses unbounded rays $x_i=-x_j=\\lambda$ to eliminate coefficient differences, so bounded variables or extra coupling constraints break the argument, a case the paper explicitly leaves out.","fun_headline_variants_meta":{"raw":{"variants":["Step-penalized quadratics: exact convex hull","Exact convexification of step-penalized quadratics","Quadratic step penalties: exact convex hull","From step penalties to convex SVM: exact hull","Convex hull for step-penalized quadratics: exact"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000926,"raw_usage":{"total_tokens":4012,"prompt_tokens":1033,"completion_tokens":2979,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":649,"completion_tokens_details":{"reasoning_tokens":2900}},"tokens_in":649,"tokens_out":2979,"duration_ms":24163,"temperature":1.0,"reasoning_tokens":2900,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:06:26.937626+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix $d=(1,1)$, add the bound $-1\\le x_i\\le 1$ to every continuous variable in $X_d$, and minimize $\\alpha^\\top x+\\beta^\\top z+t$ with $\\alpha=(0,1)$, $\\beta=0$ over the mixed-integer set and over the convex set of Theorem 1; if the two optimal values differ, the unboundedness assumption is essential and the claimed hull description does not extend to bounded variables.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the big-M MIO formulation for SVM with ramp and 0-1 loss whose weak relaxation is the main computational baseline."},{"cited_title":"Frangioni and C","cited_arxiv_id":null,"evidence_quote":"Gives the perspective cuts and the convex hull of the one-dimensional set $Y_1$ used in the extended-form interpretation of Theorem 1."},{"cited_title":"Ping and F","cited_arxiv_id":null,"evidence_quote":"Provides the copositive Schur complement criterion that converts the infinite family of rank-one inequalities into finitely many copositive constraints."},{"cited_title":"Wu and Y","cited_arxiv_id":null,"evidence_quote":"Defines the ramp-loss SVM, one of the non-convex robust losses compared with the derived $\\phi$ loss."},{"cited_title":"Jammal, S","cited_arxiv_id":null,"evidence_quote":"Proposes a related MIP SVM formulation and the label-corruption experimental setup replicated in the real-data tests."}],"review_version":1}