Pith. sign in

REVIEW 2 major objections 5 minor 29 references

Robust Least Squares Problems with Binary Uncertain Data

T0 review · 2 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2510.11519 v2 pith:5OLKRWXJ submitted 2025-10-13 math.OC

Yang Zhou , Xiaojun Chen This is my paper
classification math.OC MSC 49K3590C3090C31
keywords robustleastsquaresbinaryuncertaintyminimaxoptimizationsupermodularsubmodularLovászextensionlabelcorruptionprojectedgradient
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [Abstract, Section 4, Section 6] 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
  2. [Abstract, Section 5] 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.
minor comments (5)
  1. [Section 5.1] 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.
  2. [Figures 2–5] 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.
  3. [Section 5.2] Typo: 'adversing structured noises' should read 'adversarial structured noise'.
  4. [Throughout] 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.
  5. [Example 3.4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the minimax guarantees follow from explicit structural identities and external submodular-optimization results; the only self-citation is contextual.

full rationale

No load-bearing circularity is present. Proposition 2.5 derives supermodularity/submodularity from column inner products via the marginal-difference identity (6), not by definitional fiat. The algorithmic theorems (3.8, 3.11, 4.2) rest on external, parameter-free oracles: the strongly polynomial submodular minimization algorithm of Jiang [15], the double-greedy 1/3-approximation of Buchbinder et al. [5], and the Lovasz-extension/Sion facts [3, 23]. None of these is supplied by the paper itself, and none is equivalent to the minimax target. The Chen-Kelley self-citation [10] is used for the orthogonal baseline, the explicit inner formula, and the saddle-point motivation; it is not the engine of the acute/obtuse guarantees, so it is not circular. The abstract promises a semidefinite-relaxation subsolver with ratio below 2/pi for the general linear case, but the body contains no such theorem and Section 6 instead defers 'general noise propagation matrices lacking acute or obtuse structure' to future work; this is a scope/consistency gap, not a circular reduction. Thus score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted to data in the theoretical results; algorithm parameters K and mu are set by closed-form expressions depending on epsilon, diameter, and Lipschitz constants. Experimental quantities such as noise ratio rho, training noise delta, and C generation are scenario choices, not fitted model parameters. No unexplained new entities are postulated; the BRLS formulation itself is a modeling framework, not an invented physical entity.

assumptions (6)
  • domain assumption X is convex and compact, Y = {0,1}^n, and F is continuous (affine in the linear cases, differentiable in the nonlinear case).
    Stated in the BRLS formulation and Section 2; compactness/convexity is used for existence of minimax points and for projected-gradient convergence.
  • domain assumption C is either acute or obtuse, i.e. all off-diagonal column inner products share a common sign.
    Definition 2.3 and Proposition 2.5; this is the structural assumption that delivers supermodularity or submodularity of the inner maximization.
  • standard math Lovasz-SVP solver [15] provides a strongly polynomial algorithm for submodular minimization.
    Invoked as Theorem 3.7 and used as the exact inner oracle in Theorems 3.8 and 3.11.
  • standard math Sion's minimax theorem and the Lovasz-extension convexity/concavity correspondence (Bach, Proposition 3.2).
    Used in Proposition 3.3 to establish existence of saddle points for L-BRLS and the convex-hull characterization of y*.
  • standard math Double greedy gives a 1/3 approximation for unconstrained nonmonotone submodular maximization.
    Used in Lemma 4.1 and Theorem 4.2 for the obtuse-C case.
  • standard math Moreau-envelope and weak-convexity calculus for nonsmooth value functions.
    Used in Theorem 3.11 to define and compute epsilon-stationary points; relies on Rockafellar-Wets properties of Moreau envelopes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Robust Least Squares Problems with Binary Uncertain Data." pith.science (2026). https://pith.science/paper/5OLKRWXJ

@misc{pith2026251011519,
  author       = {Pith},
  title        = {Pith review of: Robust Least Squares Problems with Binary Uncertain Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5OLKRWXJ}},
  note         = {Machine review of arXiv:2510.11519}
}
abstract

We propose a Binary Robust Least Squares (BRLS) model that encompasses key robust least squares formulations, such as those involving uncertain binary labels and adversarial noise constrained within a hypercube. {To develop algorithms with theoretical guarantees for the BRLS problem, we exploit the structure of the inner binary maximization problem with a convex quadratic objective function. Refined guarantees are obtained when the noise correlations are sign-structured, in which case the inner problem admits sharper submodular or supermodular oracles. For the supermodular linear BRLS problem, we establish a link between saddle points of its continuous relaxation and global minimax points of BRLS, and propose a projected-gradient algorithm to find an $\epsilon$-global minimax point in $O(\epsilon^{-2})$ iterations. For the supermodular nonlinear BRLS problem, we develop a Moreau-envelope-based framework that finds an $\epsilon$-stationary point in expectation within $O(\epsilon^{-4})$ iterations. 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/\pi$. Coupled with the projected-gradient framework, these oracles yield approximate minimax guarantees within $O(\epsilon^{-2})$ iterations. Numerical experiments on health status prediction with candidate label-corruption sets, synthetic linear BRLS, and thresholded phase retrieval with missing binary labels illustrate the behavior and robustness gains of the BRLS model under structured noise compared with classical least-squares-based baselines.

Figures

Figures reproduced from arXiv: 2510.11519 by the authors.

Figure 1
Figure 1. The function Θ = (x−y) 2 in HRLS with its global minimax points (left) and ΘL in L-BRLS with its saddle point (right). The R-HRLS problem is not a convex-concave minimax problem and gradient-based methods can￾not ensure to find a global minimax point of the problem from any initial point. However, based on Proposition 3.3, we can devise an ideal two-step strategy to find a global minimax point via its relationship w… view at source ↗
Figure 2
Figure 2. Average accuracy of LS, LASSO, RLS(100%C), and RLS(70%C) models among 10 users as [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Distribution of true vs predicted labels for LS, LASSO, RLS(100%C), and RLS(70%C) [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Robustness comparison of RLS to LS and LASSO with [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: Robustness comparison of RLS to LS and LASSO with [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 3 linked inside Pith

  1. [10]

    Chen and C

    X. Chen and C. T. Kelley , Robust solutions of nonlinear least squares problems via min-max optimization , IMA J. Numer. Anal., online, (2025)

    2025

  2. [9]

    X. Chen, J. Guo, and G. Wang , Differential stochastic variational inequalities with parametric optimization , arXiv:2508.15241, (2025)

    arXiv 2025

  3. [1]

    Adibi, A

    A. Adibi, A. Mokhtari, and H. Hassani , Minimax optimization: The case of convex-submodular , in Proceedings of AISTATS, PMLR, 2022, pp. 3556--3580

    2022

  4. [2]

    Akhtiamov, R

    D. Akhtiamov, R. Ghane, and B. Hassibi , Regularized linear regression for binary classification , in Proceedings of ISIT, 2024

    2024

  5. [3]

    Bach , Learning with submodular functions: A convex optimization perspective , Found

    F. Bach , Learning with submodular functions: A convex optimization perspective , Found. Trends. Mach. Learn., 6 (2013), pp. 145--373

    2013

  6. [4]

    Bilmes , Submodularity in machine learning and artificial intelligence , arXiv:2202.00132, (2022)

    J. Bilmes , Submodularity in machine learning and artificial intelligence , arXiv:2202.00132, (2022)

    arXiv 2022

  7. [5]

    Buchbinder, M

    N. Buchbinder, M. Feldman, J. Seffi, and R. Schwartz , A tight linear time (1/2)-approximation for unconstrained submodular maximization , SIAM J. Comput., 44 (2015), pp. 1384--1402

    2015

  8. [6]

    Calinescu, C

    G. Calinescu, C. Chekuri, M. Pal, and J. Vondr \'a k , Maximizing a monotone submodular function subject to a matroid constraint , SIAM J. Comput., 40 (2011), pp. 1740--1766

    2011

Show all 29 references
  1. [7]

    Campbell, K

    R. Campbell, K. Koedijk, and P. Kofman , Increased correlation in bear markets , Financ. Anal. J., 58 (2002), pp. 87--94

    2002

  2. [8]

    Chekuri, J

    C. Chekuri, J. Vondr \'a k, and R. Zenklusen , Submodular function maximization via the multilinear relaxation and contention resolution schemes , SIAM J. Comput., 43 (2014), pp. 1831--1879

    2014

  3. [11]

    Davis and D

    D. Davis and D. Drusvyatskiy , Stochastic subgradient method converges at the rate O (k^ -1/4 ) on weakly convex functions , arXiv preprint arXiv:1802.02988, (2018)

    2018 arXiv

  4. [12]

    El Ghaoui and H

    L. El Ghaoui and H. Lebret , Robust solutions to least-squares problems with uncertain data , SIAM J. Matrix Anal. Appl., 18 (1997), pp. 1035--1064

    1997

  5. [13]

    Fujishige , Submodular Functions and Optimization , Elsevier, 2005

    S. Fujishige , Submodular Functions and Optimization , Elsevier, 2005

    2005

  6. [14]

    Gr \"o tschel, L

    M. Gr \"o tschel, L. Lov \'a sz, and A. Schrijver , Geometric Algorithms and Combinatorial Optimization , vol. 2, Springer Science & Business Media, 2012

    2012

  7. [15]

    Jiang , Minimizing convex functions with rational minimizers , J

    H. Jiang , Minimizing convex functions with rational minimizers , J. ACM, 70 (2022), pp. 1--27

    2022

  8. [16]

    C. Jin, P. Netrapalli, and M. Jordan , What is local optimality in nonconvex-nonconcave minimax optimization? , in Proceedings of ICML, PMLR, 2020, pp. 4880--4889

    2020

  9. [17]

    K. G. Murty and S. N. Kabadi , Some NP -complete problems in quadratic and nonlinear programming , tech. rep., 1985

    1985

  10. [18]

    G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher , An analysis of approximations for maximizing submodular set functions- I , Math. Program., 14 (1978), pp. 265--294

    1978

  11. [19]

    Pollet, M

    T. Pollet, M. Van Bladel , and M. Moeneclaey , BER Sensitivity of OFDM Systems to Carrier Frequency Offset and Wiener Phase Noise , IEEE Trans. Commun., 43 (1995), pp. 191--193

    1995

  12. [20]

    R. T. Rockafellar and R. J. Wets , Variational Analysis , Springer, 1998

    1998

  13. [21]

    Sehwag, A

    V. Sehwag, A. N. Bhagoji, L. Song, C. Sitawarin, D. Cullina, M. Chiang, and P. Mittal , Analyzing the robustness of open-world machine learning , in Proceedings of AISec, New York, USA, 2019, Association for Computing Machinery, pp. 105--116

    2019

  14. [22]

    Sener and V

    O. Sener and V. Koltun , Multi-task learning as multi-objective optimization , in Proceedings of NeurIPS, vol. 31, 2018

    2018

  15. [23]

    Sion , On general minimax theorems , Pacific J

    M. Sion , On general minimax theorems , Pacific J. Math., 8 (1956), pp. 171--176

    1956

  16. [24]

    D. M. Topkis , Minimizing a submodular function on a lattice , Oper. Res., 26 (1978), pp. 305--321

    1978

  17. [25]

    J. V. Neumann , Zur theorie der gesellschaftsspiele , Math. Ann., 100 (1928), pp. 295--320

    1928

  18. [26]

    V. V. Vazirani , Approximation Algorithms , vol. 1, Springer, 2001

    2001

  19. [27]

    Wolfe , Finding the nearest point in a polytope , Math

    P. Wolfe , Finding the nearest point in a polytope , Math. Program., 11 (1976), pp. 128--149

    1976

  20. [28]

    Z. Xu, H. Zhang, Y. Xu, and G. Lan , A unified single-loop alternating gradient projection algorithm for nonconvex--concave and convex--nonconcave minimax problems , Math. Program., 201 (2023), pp. 635--706

    2023

  21. [29]

    Ye , On affine scaling algorithms for nonconvex quadratic programming , Math

    Y. Ye , On affine scaling algorithms for nonconvex quadratic programming , Math. Program., 56 (1992), pp. 285--300

    1992

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.