{"id":"5d19b00e-6471-40ed-8a24-de8d9c6d54c9","arxiv_id":"2510.11519","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A minimax least-squares model with binary adversarial noise is solved with guaranteed iteration complexity by linking column geometry of the noise matrix to submodular/supermodular structure.","lead":"The paper proposes a robust least-squares framework where noise is binary and adversarial, and shows that the geometry of the noise matrix determines whether the inner maximization is submodular or supermodular. This lets the authors plug known combinatorial solvers into gradient methods with iteration-complexity guarantees.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract promises an SDP/2π result for the general linear BRLS case, but the body contains no such theorem and Section 6 lists general matrices as future work; the structured-regime results themselves are not contradicted.","rationale":"The reader's formal weakest assumption—the acute/obtuse requirement—is indeed the point on which the algorithmic guarantees rest. I agree that the structured theorems appear coherent: Proposition 2.5's characterization follows from the second-difference identity (6), Proposition 3.3's saddle-point argument via the Lovász extension is valid given the convexity/concavity inherited from compactness and Sion's theorem, and the projected-gradient lemmas (3.6, 4.1) have the right constants for the stated O(ε^{-2}) rates. The DG 1/3 approximation and the [15] submodular-minimization oracle are standard tools. So I do not see a technical defect in the main results. The serious issue is the scope mismatch: the abstract promises an SDP/2π general-linear-case result that never appears, and the conclusion states that general matrices are future work. This is an internal inconsistency, not a disagreement with consensus. The paper should be accepted only conditional on removing or substantiating that advertised result. The questionable health-data citation [9] is a further unreliability signal but is secondary to the mathematical claim. My verdict stays CONDITIONAL (i.e., UNCHANGED relative to the reader), because the core structured results do not need to be rejected; the presentation and claimed scope need correction.","tokens_in":17328,"tokens_out":19892,"duration_ms":155581,"concrete_test":"Perform a full-text scan of the submission for 'semidefinite', 'SDP', and '2/π'. If no theorem/proposition in Sections 2–4 (or an appendix) defines a semidefinite relaxation subsolver for the general linear BRLS problem and proves an approximation ratio below 2/π, then delete the corresponding sentence from the abstract or add the missing theorem and its proof. The same scan should confirm whether any numerical experiment uses such a subsolver; if none does, the claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's own strongest scope claim is the set of minimax guarantees for acute/obtuse C (Theorems 3.8, 3.11, 4.2), and those proofs are internally coherent. The load-bearing problem is that the abstract promises more: 'For the linear submodular case and the linear general case, we utilize a double-greedy algorithm and a semidefinite relaxation as the respective subsolvers; the latter attains an approximation ratio below 2/π.' I searched the body for this result. Section 4 is titled 'Submodular Linear BRLS' and gives only the double-greedy (1/3) guarantee; there is no section or theorem with an SDP subsolver, no statement of a below-2/π approximation ratio, and no algorithm or numerical experiment for a general linear case. Section 6 explicitly defers 'general noise propagation matrices lacking acute or obtuse structure' to future work. Thus the headline advertised contribution is unsupported. This matters because it changes the scope of the central claim: without the SDP result, the paper only solves the structured sign-regimes, which is a much narrower class than the abstract's 'general linear case.' The acute/obtuse restriction is not a mathematical error—Proposition 2.5 is correct—but the abstract overstates the deliverable, and the conclusion contradicts it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the binary robust least squares problem min_{x∈X} max_{y∈{0,1}^n} (1/2)||F(x)-Cy||^2. Its main theoretical contribution is a sign-structure classification: Proposition 2.5 shows that the inner objective is supermodular for every x iff C is acute (all pairwise column inner products nonnegative), and submodular iff C is obtuse (all nonpositive). On this basis the authors develop three algorithmic frameworks: for affine F and acute C, a projected-gradient method with an exact submodular-minimization subsolver finds an ε-global minimax point in O(ε^{-2}) iterations (Theorem 3.8), based on a Lovász-extension saddle-point connection (Proposition 3.3); for nonlinear F and acute C, a Moreau-envelope-based randomized method reaches an ε-stationary point in expectation in O(ε^{-4}) iterations (Theorem 3.11); for affine F and obtuse C, the double-greedy subsolver gives a (1/3, ε)-approximate minimax point in O(ε^{-2}) iterations (Theorem 4.2). Numerical experiments on health-status prediction and phase retrieval illustrate robustness gains relative to LS/LASSO.","tokens_in":17675,"tokens_out":8313,"duration_ms":69045,"significance":"Within the structured sign regimes, the results are coherent and nontrivial. Proposition 2.5 is a clean characterization, and the reduction of the inner binary quadratic maximization to submodular/supermodular oracles provides a useful bridge between combinatorial optimization and continuous minimax methods. The iteration counts are explicit, and the proofs I checked are internally consistent; the connection of double greedy to the orthogonal case treated in Chen–Kelley is a nice generalization. The paper also gives credit to the external submodular-minimization machinery it relies on. However, the abstract advertises a substantially broader contribution than the body delivers, and the numerical experiments lack code, data, and error bars.","major_comments":[{"comment":"The abstract states: 'For the linear submodular case and the linear general case, we utilize a double-greedy algorithm and a semidefinite relaxation as the respective subsolvers; the latter attains an approximation ratio below 2/π.' I searched the body for this SDP subsolver and the 2/π guarantee. Section 4 is titled 'Submodular Linear BRLS' and gives only the double-greedy (1/3) guarantee (Lemma 4.1, Theorem 4.2); there is no section or theorem with an SDP subsolver, no statement of a below-2/π approximation ratio, and no algorithm or numerical experiment for a general linear case. Section 6 explicitly defers 'general noise propagation matrices lacking acute or obtuse structure' to future work. This is a load-bearing mismatch: the advertised central contribution is unsupported, and the actual deliverable is restricted to the acute/obtuse regimes. Please either add the SDP result with pr","section":"Abstract, Section 4, Section 6"},{"comment":"The abstract also promises 'synthetic linear BRLS' among the numerical experiments, but Section 5 contains only the health-status prediction experiment (Subsection 5.1) and the phase-retrieval experiment (Subsection 5.2). No synthetic linear BRLS experiment appears. This is a presentation issue that contributes to the overstatement of the paper's coverage, and it should be corrected by either adding the experiment or removing the claim.","section":"Abstract, Section 5"}],"minor_comments":[{"comment":"The dataset is said to be 'derived from [9]', but reference [9] is 'Differential stochastic variational inequalities with parametric optimization', which appears unrelated to wearable sensor health data. Please verify the citation and provide the correct data source.","section":"Section 5.1"},{"comment":"The experiments report averages over 10 users (health) and 10 trials (phase retrieval), but no error bars, confidence intervals, or standard deviations are given. For reproducibility, please also provide code and data, or at least describe the random-generation procedure fully.","section":"Figures 2–5"},{"comment":"Typo: 'adversing structured noises' should read 'adversarial structured noise'.","section":"Section 5.2"},{"comment":"The notation for the step size in Algorithm 1 is K^{-1/2}, but the proof of Lemma 3.6 writes K^{-1/2} inconsistently in places (e.g., K^{-1/2} vs. K^{1/2} in the displayed inequalities). Please standardize the notation for readability.","section":"Throughout"},{"comment":"The example says 'the domain of y has been simply shifted and scaled from [0,1] to [-1,1]' but the problem is otherwise presented as a scalar HRLS example; it would help to state explicitly which matrix C and functions F are used, since the connection to the BRLS framework is not immediate.","section":"Example 3.4"}],"recommendation":"major_revision","confidential_remarks":"The abstract/body discrepancy is the main obstacle. The structured-regime results appear sound and are potentially publishable, but the advertised SDP/2π result for the general linear case is entirely absent from the body, and Section 6 explicitly calls it future work. I would not insist on adding the SDP result; the paper can be made acceptable by honestly restricting the claims to the acute/obtuse regimes and fixing the experimental reproducibility issues. Please also ask the authors to verify the data citation in Section 5.1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core theory is solid, but the abstract overpromises. If you read the body, the real contribution is the link between column geometry of C and supermodularity/submodularity of the inner binary maximization, plus the algorithms that exploit it. Proposition 2.5 is clean and correct, and the Lovász-extension saddle-point equivalence for the supermodular linear case is a genuine extension of the orthogonal-C closed form. The O(ε^-2), O(ε^-4), and (1/3, ε) guarantees all check out as far as I can see. The use of [10] as a baseline and for the orthogonal special case is fair, and I don't see any fitted constants or circular reasoning.\n\nThe soft spot is the abstract. It says the 'linear general case' is handled by a semidefinite relaxation with approximation ratio below 2/π. That result is nowhere in the paper. Section 4 only covers the submodular linear case with double greedy, and Section 6 explicitly defers general noise propagation matrices to future work. This is a real contradiction between the headline claim and the actual content, and it changes the scope: without the SDP result, the paper solves the structured sign regimes, not the general case. The authors need to either add the SDP theorem or rewrite the abstract to match the body.\n\nSecond, the experiments are weaker than the theory. No code, no data, no error bars. The health dataset is attributed to [9], which is a paper on differential variational inequalities, not a wearable-sensor dataset source; that citation looks wrong or at least is badly explained. Phase retrieval results are illustrative, but as it stands the numerical section doesn't meet the bar for reproducibility.\n\nNone of this undermines the acute/obtuse results. The proofs for those are coherent and the restricted scope is stated honestly in the body. It's the abstract-body mismatch and the experimental reporting that need fixing. This is a paper worth a serious referee, not a desk reject: the theoretical machinery is real, and the submodular-optimization inner solvers inside projected gradient are a legitimate contribution. I'd send it to review with the expectation of major revision.\n\nFor your purposes: cite this for the acute/obtuse characterization and the supermodular/submodular algorithmic framework, but do not cite it for any general-case SDP result unless the authors actually provide it.","headline":"The acute/obtuse geometry-to-submodularity bridge is sound and useful; the abstract's SDP/2π claim for the 'general linear case' is absent from the body and the paper should not be read as delivering it.","tokens_in":18140,"tokens_out":3180,"would_cite":true,"duration_ms":30433,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49K35","90C30","90C31"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that the sign pattern of the noise-propagation matrix decides when binary robust least squares is tractable: acute columns yield supermodular inner maximization, obtuse columns yield submodular, and both regimes carry prova","keywords":["robust least squares","binary uncertainty","minimax optimization","supermodular","submodular","Lovász extension","label corruption","projected gradient"],"falsifier":"Compute the marginal difference Theta(x, y+e_i) - Theta(x, y) for a fixed x and all pairs i,j; Proposition 2.5 predicts its sign is governed uniformly by c_i^T c_j. A single mixed-sign C (some c_i^T c_j > 0, some < 0) will produce marginal differences of both signs, confirming the structural claim's necessity. To test the algorithmic claim, run Algorithm 1 on an acute-C instance with brute-force inner maximization for n <= 10 and check the epsilon-global minimax inequality within O(epsilon^-2) iterations; failure would refute Theorem 3.8.","tokens_in":17238,"feed_emoji":"📐","tokens_out":10070,"duration_ms":85241,"temperature":0.7,"pith_summary":"The paper introduces a single minimax model, min_x max_{y in {0,1}^n} 1/2 ||F(x)-Cy||^2, that covers robust least squares with uncertain binary labels and with hypercube-constrained adversarial noise. It seeks to prove that the structure of C — specifically whether the angle between every pair of columns is acute or obtuse — determines whether the inner binary maximization is supermodular or submodular. That sign structure is the switch that lets known combinatorial optimization solvers be plugged into a projected-gradient outer loop, converting a mixed discrete-continuous problem that is NP-hard in general into a solvable minimax problem in these structured regimes. For the supermodular linear case the paper links global minimax points of the discrete problem to saddle points of a continuous Lovász extension, giving an O(epsilon^-2)-iteration algorithm for an epsilon-global minimax point; for nonlinear supermodular problems it gives an O(epsilon^-4) expected-stationarity bound, and for the submodular linear case a (1/3, epsilon)-approximate guarantee in O(epsilon^-2) iterations. A reader should care because these are concrete complexity guarantees for a class of robust least-squares problems that otherwise resist both convex reformulation and saddle-point analysis.","feed_headline":"Noise-column angles decide when robust least squares is tractable","feed_subtitle":"When all noise correlations share a sign, the inner binary search becomes sub/supermodular and solvable in provable time.","key_machinery":"The central object is the Gram matrix C^T C, whose off-diagonal entries c_i^T c_j are the pairwise noise-correlation coefficients. The sign of every off-diagonal entry is what flips the marginal gain structure: if all are nonnegative, then for fixed x the objective Theta(x,y) = 1/2 ||F(x)-Cy||^2 is supermodular in the binary variable y; if all are nonpositive, it is submodular (Proposition 2.5). This sign structure is what makes the inner maximization tractable — supermodular maximization reduces to submodular minimization via the Lovász extension, and submodular maximization admits the double-greedy 1/3-approximation — so the outer projected-gradient loop can inherit guarantees. The Lovász","core_discovery":"The paper's central claim is that the mixed discrete-continuous minimax problem min_x max_{y in {0,1}^n} 1/2 ||F(x)-Cy||^2 is governed by the sign pattern of the Gram matrix C^T C. When c_i^T c_j >= 0 for every pair (C acute), the inner objective is supermodular in y for every x; when c_i^T c_j <= 0 (C obtuse), it is submodular. In the supermodular linear case (F affine), the Lovász extension makes the inner maximization concave, so the minimax problem has a saddle point and the paper's projected-gradient method, using an exact submodular-minimization subsolver, reaches an epsilon-global minimax point in O(epsilon^-2) iterations. For nonlinear differentiable F with acute C, a Moreau-envelope","pith_inferences":["A natural decision rule not spelled out in the paper: before solving, compute the off-diagonal inner products of C; if all are nonnegative or all nonpositive, the corresponding theorem applies, so practitioners can certify tractability at preprocessing cost O(r n^2).","For matrices with mixed-sign correlations — the gap the paper leaves open — the acute/obtuse dichotomy suggests a block-decomposition heuristic: group columns by sign coherence, solve each block with the appropriate oracle, and coordinate the blocks in the outer loop; no guarantee is provided, but the paper's machinery is a natural starting point.","The equivalence between global minimax points and Lovász saddle points suggests a warm-start strategy: solve the continuous convex-concave relaxation first, then use its saddle point to seed the discrete inner solve; this could improve practical convergence and is compatible with the paper's two-step perspective.","Because the Moreau-envelope stationarity bound in Theorem 3.11 holds in expectation over a uniformly drawn iterate, stochastic variants of the outer loop (random subsampling of F) may inherit the same O(epsilon^-4) rate under standard weak-convexity assumptions; the paper does not develop this extension."],"forward_implications":["For robust linear least squares with binary label noise and an acute noise-propagation matrix, an epsilon-global minimax solution can be computed in O(epsilon^-2) iterations, making the problem polynomial-time solvable in that regime.","For nonlinear differentiable models (e.g., phase retrieval) with acute C, the Moreau-envelope-based method finds an epsilon-stationary point in expectation in O(epsilon^-4) iterations, giving a quantitative handle on the nonconvex-nonconcave case.","When C is obtuse (negative noise correlation), a double-greedy inner oracle yields a (1/3, epsilon)-approximate minimax point in O(epsilon^-2) iterations; when C is column-orthogonal the same oracle is exact, recovering a known closed-form inner solution as a special case.","The hypercube-constrained robust least squares problem (HRLS) is equivalent to BRLS in global minimax points, so the new algorithms apply to adversarial noise bounded by a hypercube, not only to binary corruption.","Experiments on health-status prediction and thresholded phase retrieval show that the BRLS estimator keeps classification accuracy above 90% under 50% label corruption where least squares and LASSO degrade to near chance."],"fun_headline_variants":["Noise correlation signs decide when BRLS is tractable","Acute noise Gram matrices unlock fast minimax algorithms","Sign-structured noise makes binary robust least squares easy","BRLS tractability hinges on noise correlation sign pattern","When noise correlations align, robust least squares turns tractable"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The guarantees rest on all pairwise column correlations of the noise-propagation matrix having one uniform sign—all nonnegative or all nonpositive—and if correlations are mixed, the inner maximization can be NP-hard and the paper gives no guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Noise correlation signs decide when BRLS is tractable","Acute noise Gram matrices unlock fast minimax algorithms","Sign-structured noise makes binary robust least squares easy","BRLS tractability hinges on noise correlation sign pattern","When noise correlations align, robust least squares turns tractable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000199,"raw_usage":{"total_tokens":1269,"prompt_tokens":864,"completion_tokens":405,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":608,"completion_tokens_details":{"reasoning_tokens":327}},"tokens_in":608,"tokens_out":405,"duration_ms":4784,"temperature":1.0,"reasoning_tokens":327,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T10:07:03.462812+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the marginal difference Theta(x, y+e_i) - Theta(x, y) for a fixed x and all pairs i,j; Proposition 2.5 predicts its sign is governed uniformly by c_i^T c_j. A single mixed-sign C (some c_i^T c_j > 0, some < 0) will produce marginal differences of both signs, confirming the structural claim's necessity. To test the algorithmic claim, run Algorithm 1 on an acute-C instance with brute-force inner maximization for n <= 10 and check the epsilon-global minimax inequality within O(epsilon^-2) iterations; failure would refute Theorem 3.8.","supporting_citations":[],"review_version":1}