{"id":"e6562830-eb06-4d7e-b745-8e77abdae8e4","arxiv_id":"2412.17116","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A convex-hull-based relaxation plus coordinate descent and exact mixed-integer formulations let fair regression models be trained much faster, with accuracy-fairness trade-offs competitive against a state-of-the-art reduction method.","lead":"This paper presents optimization methods for training regression models under exact fairness constraints like demographic parity, including a strong convex relaxation, a coordinate descent algorithm, and an exact mixed-integer formulation. The methods produce fairness-accuracy trade-offs competitive with prior work while being orders of magnitude faster on the datasets tested.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Logistic exact-MIO claim is under-specified: no valid big-M is provided, so the exact branch-and-bound for logistic is conditional on an unstated parameter.","rationale":"The reader's weakest assumption identifies the missing big-M for non-superlinear losses, and I agree this is the most load-bearing concern about the paper's central exactness claim. Proposition 4 itself, the convex hull description, appears well argued and internally consistent: the disjunctive proof, the change of variables, and the perspective terms all check out for the single-observation set X. The issue arises when lifting this convex hull to an exact MIO for logistic regression: the convex hull of X with a linearly growing loss has finite recession directions, so the perspective constraints alone do not enforce the intended indicator semantics at integral z. The paper acknowledges this in Remark 2 and adds big-M constraints, but never specifies a valid M or proves existence of a finite one. Since w is unbounded and logistic loss is bounded below, the true problem can have unbounded optimal solutions, so no universal finite M is valid; a data-dependent M would require nontrivial bounds that the paper does not derive. This makes the 'exact' branch-and-bound claim for logistic conditional, not unconditional. The concern does not invalidate the relaxed or coordinate-descent methods, which do not rely on this big-M, and it is addressable by supplying an M bound or restricting the problem class. I also considered the single-factor exactness reduction, which silently assumes positive features when transforming (21c) into a single X; that is a real correctness gap in a secondary claim, but the big-M issue more directly affects the headline exact-formulation promise for a loss actually used in the experiments. The reader's CONDITIONAL verdict remains appropriate, so no verdict change is needed.","tokens_in":24070,"tokens_out":38968,"duration_ms":342941,"concrete_test":"On a small logistic instance (e.g., m=20, n=5, synthetic with a protected attribute), implement the MIO from §2.2/§4.1.3 with integrality on z plus the big-M constraints p_i0 ≤ M(1−z_i1), p_iℓ ≤ M z_iℓ. Solve to optimality for M ∈ {1,10,100,1000} and also by brute-force enumeration of the true discontinuous problem (3)/(10) over the same grid. Check (i) whether the MIO optimal value equals the true optimum for every M; (ii) whether the optimal z matches 1(w^T x_i > b_j) at the returned w; (iii) whether the optimal value is M-invariant. If any test fails, the exactness claim needs an explicit M bound or a different treatment for non-superlinear losses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Remark 2 concedes that for logistic loss the perspective terms in (17d) no longer force p_i0 = 0 when z_i1 = 1 (and p_iℓ = 0 when z_iℓ = 0), because logistic loss grows only linearly; the paper adds p_i0 ≤ M(1−z_i1) and p_iℓ ≤ M z_iℓ. But no data-dependent value of M is stated or bounded. Since w is unconstrained, the optimal fair logistic regression solution can be unbounded on separable data, so no finite universal M exists: too small an M cuts off the true optimum, too large an M weakens the relaxation toward NAT. The abstract's 'exact formulation' claim and the 'solving the problem exactly' phrasing in §4.1.3 therefore overstate what is delivered for logistic regression: the exact MIO is really a family of M-dependent models. This is load-bearing because logistic regression is one of the two loss classes named in the title and tested in §5.3.2, and the paper's headline contribution includes exact branch-and-bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies fair linear regression under discretized demographic-parity constraints or penalties. Its main theoretical contribution is an extended formulation, based on perspective functions, for the closed convex hull of the set X = {(v,z,s) : L(v) ≤ s, (v-b_j)z_j ≥ 0, (b_j-v)(1-z_j) ≥ 0, z ∈ {0,1}^ℓ} describing one prediction, its indicator vector over threshold intervals, and the loss epigraph. Proposition 4 asserts that the perspective system (16a)-(16c) is an extended formulation for cl conv(X); Corollary 1 uses it as a strong convex relaxation of the general fair-regression problem. The paper also proposes a coordinate-descent algorithm exploiting the single-coordinate subproblem, and a branch-and-bound MIO approach. Experiments on synthetic and real data compare the relaxation and coordinate descent against reduction-based and convex-proxy baselines, reporting substantial speedups and competitive accuracy-fairness trade-offs.","tokens_in":24256,"tokens_out":7521,"duration_ms":72549,"significance":"The convex-hull derivation in Propositions 3 and 4 is the paper's strongest asset: it is self-contained, the projection algebra in Proposition 4 checks out, and the resulting relaxation is a clean, reusable building block for threshold-based fair regression. The coordinate-descent algorithm with exact fairness evaluation is simple and practically effective, and the numerical study is honest about the scalability limits of the MIO approach (m > 100 remains hard). If the exactness claims are carefully qualified, this is a useful contribution to the fair-regression literature. However, as written, two load-bearing claims are not fully supported: the single-factor exactness reduction silently requires positive features, and the exact MIO for logistic regression depends on an unspecified big-M constant. Both issues concern the central 'exact formulation' narrative and must be addressed before the claims are fully credible.","major_comments":[{"comment":"The single-factor reduction is not valid under the stated assumption 'xi ≠ 0'. To derive (21c), (w - b_j/x_i) z_ij ≥ 0 and (b_j/x_i - w)(1 - z_ij) ≥ 0, from (v - b_j)z_ij ≥ 0 and (b_j - v)(1 - z_ij) ≥ 0 with v = w x_i, one must divide by x_i without reversing inequalities; this requires x_i > 0. For x_i < 0 both inequalities are reversed, and the breakpoints b_j/x_i appear in decreasing order, so the resulting set is not a single set of type X without re-indexing or a sign change. The exactness claim for single-factor problems therefore holds only under an unstated positivity assumption; please state it or handle the sign explicitly.","section":"§2.2, Eq. (21)"},{"comment":"The exact MIO formulation for non-superlinear losses such as logistic regression depends on big-M constraints p_i0 ≤ M(1 - z_i1) and p_iℓ ≤ M z_iℓ, but no data-dependent value of M is stated or bounded. Since w is unconstrained, fair logistic regression can be unbounded on separable data, so no finite universal M exists; too small an M cuts off optimal solutions, and too large an M weakens the relaxation. Consequently the 'exact formulation' claim in the abstract and the branch-and-bound exactness statement in §4.1.3 overstate what is delivered for logistic regression. Please provide a valid M under explicit assumptions (e.g., a norm bound or regularizer) or restrict the exactness claim to superlinear losses such as least squares.","section":"Remark 2 and §4.1.3"},{"comment":"The statement that, despite the big-M constraints for non-superlinear losses, 'we still enjoy an improved continuous relaxation compared to formulation (NAT)' is asserted without proof. The two formulations involve different variables and the strength depends on the size of M; if M is chosen only implicitly, it is not clear that the relaxation dominates NAT for all valid M. A precise comparison, or a counterexample, is needed to support this claim.","section":"Remark 2, last sentence"}],"minor_comments":[{"comment":"The index in 'i ∈ [n]' on the left-hand side of (17d) should be 'i ∈ [m]'; n is the feature dimension.","section":"Corollary 1, Eq. (17d)"},{"comment":"In the second sum of (21b), the term '1/m ∑_{i=1} z_j' is missing the observation index in z; it should be '1/m ∑_{i=1}^m z_j'.","section":"Eq. (21b)"},{"comment":"The candidate set in Algorithm 1 uses i ∈ [n] but should be i ∈ [m]; also the notation 'b_{ij}' is inconsistent with the breakpoints b_j used elsewhere.","section":"Algorithm 1"},{"comment":"The vector notation in the proof's convex-combination expression is garbled (e.g., '(bℓ, 1)' and the inner sums with e_i); please rewrite the expression so the convex combination is readable.","section":"Proposition 2 proof"},{"comment":"There is a typo: 'ridge, ℓ1 bad MCP/reverse Huber examples' should presumably read 'ridge, ℓ1, and MCP/reverse Huber examples'.","section":"§4.3"},{"comment":"The claim that the dDP1 logistic problem is solved to optimality by branch-and-bound does not specify which formulation or what big-M value is used; this should be tied to the discussion in Remark 2 so the reader can verify the exactness of the computation.","section":"§5.3.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's central convex-hull theorem appears sound, but the presentation overstates exactness in two places that are tied to the paper's headline claims: the single-factor reduction requires an implicit positivity assumption, and the logistic MIO depends on an unstated big-M. These are fixable within the manuscript's scope—by adding the assumption, deriving a bound, or qualifying the claims—so I do not recommend rejection. I would also encourage the authors to clarify in the experiments which formulation was actually solved for the logistic branch-and-bound results, since the current text leaves this ambiguous."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core contribution here is Proposition 4: a clean extended formulation of the convex hull of the loss-epigraph plus interval-indicator set. That is a genuine building block, and the resulting relaxation (17) is a real improvement over the natural big-M relaxation. The coordinate descent candidate-set result (Proposition 5) is also nice, and the experiments show meaningful speedups over FR-Reduction and better root gaps than the big-M baseline. This is a useful paper for anyone doing fair regression with exact fairness metrics.\n\nThe soft spots are real but mostly addressable. The one that matters is the logistic case. Remark 2 says you need big-M constraints p_i0 <= M(1-z_i1) and p_iℓ <= M z_iℓ, but no valid data-dependent M is given. Since w is unbounded and logistic loss grows only linearly, no finite universal M exists; too small an M cuts off the true optimum and too large an M weakens the relaxation toward NAT. So the abstract's 'exact formulation' claim and the branch-and-bound discussion in §4.1.3 overstate what is delivered for logistic regression. The exact MIO is really a family of M-dependent models, and that should be stated clearly. This does not break the convex-hull theorem, but it tempers the 'exact' language for one of the two loss classes in the title.\n\nTwo smaller issues. The single-factor exactness reduction in Eq. (21) says 'assuming xi ≠ 0' but the direction of the inequalities flips if xi is negative, so the reduction to a single set of type X really needs xi > 0. Worth a sentence. Also, 'exact' is always for the discretized dDP_ℓ, not the continuous demographic parity; the paper does acknowledge this, but the abstract could be more careful. No code is released, which makes the experiments harder to reproduce.\n\nNone of this undermines the central convex-hull result or the practical value of the relaxation and coordinate descent. The paper is honestly argued and the math checks out as far as I can see. It deserves a serious referee. I would ask for a data-dependent big-M for logistic (or a frank statement that the exact MIO is M-dependent), the xi > 0 fix, and ideally code.\n\nSend it to review, with those requests.","headline":"The convex-hull result is solid and useful; the logistic exactness claim is under-specified until a valid big-M is given.","tokens_in":24811,"tokens_out":1588,"would_cite":true,"duration_ms":16704,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C25","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that fairness in regression can be convexified: the mixed-integer substructure behind demographic parity has a closed convex hull with an explicit extended formulation, yielding a relaxation exact for single-observation…","keywords":["fair regression","demographic parity","mixed-integer optimization","convex hull","extended formulation","perspective reformulation","coordinate descent","fairness-accuracy trade-off"],"falsifier":"Take a one-observation, two-threshold logistic regression instance, enumerate the finitely many binary indicator patterns to compute the exact fair-training optimum, then solve the mixed-integer formulation (17) with integrality and the Remark 2 big-M constraints for increasing $M$. If some feasible indicator pattern corresponding to the true optimum is cut off for every finite $M$, or if the formulation's optimal value never reaches the enumerated optimum, the claimed exactness for non-superlinear losses is refuted; conversely, finding a finite $M$ that always recovers the true optimum would support it.","tokens_in":23815,"feed_emoji":"⚖️","tokens_out":8300,"duration_ms":71160,"temperature":0.7,"pith_summary":"The paper's central goal is to make regression training under exact demographic-parity constraints tractable, without replacing the fairness metric by a convex proxy. It shows that the troublesome discrete substructure — one binary indicator per observation and threshold saying whether a prediction exceeds the threshold — can be convexified exactly when considered together with the loss epigraph. The resulting extended formulation is a strong convex relaxation of the general fair-regression problem, and it is exact for the two building-block cases: one observation or one feature. On top of this relaxation the paper builds an exact branch-and-bound method, a fast standalone relaxation, and a coordinate descent procedure; reported experiments indicate the relaxation alone matches or improves the accuracy-versus-fairness trade-off of prior reduction-based methods while cutting training time by roughly an order of magnitude. A careful reader would care because this converts a hard nonconvex training problem into a convex or nearly convex one with a provable global description of its hardest substructure.","feed_headline":"New convex hull makes fair regression training 30x faster","feed_subtitle":"A strong relaxation of the fair-training problem is exact in one factor and beats big-M relaxations.","key_machinery":"The central object is the loss-epigraph-plus-indicator set $X$, together with its extended convex-hull description. The machinery is a perspective reformulation: auxiliary variables $p_0, p_1, \\ldots, p_\\ell$ represent the portions of the prediction $v$ lying in each interval defined by the thresholds $b_j$, and the inequality (16c) is a convex combination of perspective terms of the loss $L$ evaluated at the interval endpoints and interior pieces. This identity carries the argument because it lets the convex hull of the discrete indicator structure be expressed through convex inequalities in a lifted space, making the hard substructure of demographic parity globally representable without enumerating the $2^\\ell$ indicator patterns. The same representation drives the coordinate descent method: when all coordinates but one are fixed, the single-factor version of the fair problem reduces to evaluating a finite candidate set of at most $m \\cdot \\ell$ breakpoints plus the unconstrained minimizer.","core_discovery":"The paper's central discovery is that the set $X = \\{(v, z, s) \\in \\mathbb{R} \\times \\{0,1\\}^\\ell \\times \\mathbb{R} : L(v) \\leq s, (v-b_j)z_j \\geq 0, (b_j-v)(1-z_j) \\geq 0,\\ j \\in [\\ell]\\}$, which encodes the epigraph of a univariate loss alongside binary indicators for which threshold interval the prediction falls into, has a closed convex hull with an explicit extended formulation. Proposition 4 states that the set $\\tilde{X} = \\{(v, z, p_0, p, s)$ satisfying $(16a)$–$(16c)\\}$ is an extended formulation for $\\operatorname{cl}\\operatorname{conv}(X)$, where the new variables $p_j$ split the prediction $v$ into pieces across the intervals defined by the thresholds $b_1 < \\cdots < b_\\ell$. Because the general fair-regression problem is a Cartesian product of such single-observation sets, replacing $X$ by $\\operatorname{cl}\\operatorname{conv}(X)$ yields the strong convex relaxation (17) of the fair least-squares and fair logistic regression problems. This relaxation is exact for the single-observation problem ($m=1$) and, through the single-factor formulation, for the single-feature problem ($n=1$); for general instances it provides a much tighter root relaxation than the natural big-M formulation while remaining a convex problem.","pith_inferences":["Editorial extension: the same interval-indicator convexification should apply to other threshold-based fairness metrics — equal opportunity, equalized odds, or Wasserstein distances over prediction distributions — wherever the fairness violation can be written as a linear function of indicator variables on thresholds of a linear score.","Editorial extension: the artificial-threshold device (enforcing parity at several thresholds to robustify a single-threshold goal) behaves like a margin regularizer; a testable prediction is that the number and spacing of thresholds can be tuned to control the out-of-sample parity violation, with more thresholds giving larger margins at some accuracy cost.","Editorial extension: because the single-factor problem is solved exactly in the coordinate descent step, a block-coordinate variant that updates groups of coordinates by solving small exact subproblems may escape poor local optima more reliably than the reported single-coordinate updates.","Editorial extension: the strong relaxation's underestimation of the true demographic-parity violation (noted for the standalone relaxation) suggests a calibration step — e.g., post-hoc threshold adjustment or cross-validation over $\\epsilon$ — would be needed when the user requires strict in-sample parity guarantees."],"forward_implications":["If the characterization is correct, fair least-squares and logistic regression can be trained by solving one convex problem, and the reported experiments show out-of-sample accuracy-fairness trade-offs competitive with reduction-based methods at a fraction of the runtime.","For single-observation and single-factor instances the training problem is exactly solvable in polynomial time through the convex relaxation, since the relaxation is tight there.","The branch-and-bound formulation built on the strong relaxation has dramatically smaller root gaps (about 17% on average versus 77% for the big-M formulation), so optimality for small instances is reached with far fewer nodes.","Coordinate descent initialized with the relaxation's solution halves the optimality gap of the relaxation alone, terminating in seconds on instances with thousands of points, making the approach practical where exact mixed-integer optimization is not.","For logistic loss the exact mixed-integer variant still needs auxiliary big-M or SOS1 constraints to handle non-superlinear behavior, but the relaxation itself remains strong; the paper's exactness claims for that variant are conditional on those constraints being set correctly."],"supporting_citations":[{"why":"It supplies the perspective-function theory and closure properties used in the convexification (Propositions 3–4) and in Remark 2.","marker":"Rockafellar 1970"},{"why":"It establishes the NP-hardness reduction that motivates the mixed-integer approach.","marker":"Amaldi and Kann 1995"},{"why":"It provides the linear-proxy fairness approximation and the toy-data generation used as baselines in Section 4.2 and Figure 2.","marker":"Zafar et al. 2017"},{"why":"It provides the convex-surrogate approximation of demographic parity used as a comparison baseline.","marker":"Wu et al. 2019"},{"why":"It supplies the reduction-based fair-regression algorithm and the discretized demographic-parity setup that the paper's experiments benchmark against.","marker":"Agarwal et al. 2019"},{"why":"It documents that convex surrogates are too loose to enforce fairness, motivating the exact convexification.","marker":"Lohaus et al. 2020"},{"why":"It introduces SOS1 constraints, one of the two options the paper cites for handling the big-M issue in non-superlinear losses.","marker":"Beale and Tomlin 1970"}],"fun_headline_variants":["Convex hull relaxation makes fair regression training faster","Exact convex hull for fair regression speeds up training","Strong convex hull formulation accelerates fair regression","Fair regression training accelerated via convex hull"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the exact mixed-integer version with non-superlinear losses such as logistic regression, the paper relies on big-M constraints $p_{i0} \\leq M(1-z_{i1})$ and $p_{i\\ell} \\leq M z_{i\\ell}$ without specifying a valid data-dependent value for $M$; if no such $M$ is available the exactness of the branch-and-bound method for those losses is conditional on an unspecified parameter.","fun_headline_variants_meta":{"raw":{"variants":["Convex hull relaxation makes fair regression training faster","Exact convex hull for fair regression speeds up training","Strong convex hull formulation accelerates fair regression","Fair regression training accelerated via convex hull"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000764,"raw_usage":{"total_tokens":3410,"prompt_tokens":984,"completion_tokens":2426,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":2370}},"tokens_in":600,"tokens_out":2426,"duration_ms":17884,"temperature":1.0,"reasoning_tokens":2370,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:47:51.382658+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a one-observation, two-threshold logistic regression instance, enumerate the finitely many binary indicator patterns to compute the exact fair-training optimum, then solve the mixed-integer formulation (17) with integrality and the Remark 2 big-M constraints for increasing $M$. If some feasible indicator pattern corresponding to the true optimum is cut off for every finite $M$, or if the formulation's optimal value never reaches the enumerated optimum, the claimed exactness for non-superlinear losses is refuted; conversely, finding a finite $M$ that always recovers the true optimum would support it.","supporting_citations":[],"review_version":1}