REVIEW 3 major objections 6 minor 1 cited by
Fair and Accurate Regression: Strong Formulations and Algorithms
T0 review · 3 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict The convex-hull result is solid and useful; the logistic exactness claim is under-specified until a valid big-M is given. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§2.2, Eq. (21)] 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.
- [Remark 2 and §4.1.3] 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.
- [Remark 2, last sentence] 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.
minor comments (6)
- [Corollary 1, Eq. (17d)] The index in 'i ∈ [n]' on the left-hand side of (17d) should be 'i ∈ [m]'; n is the feature dimension.
- [Eq. (21b)] 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'.
- [Algorithm 1] 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.
- [Proposition 2 proof] 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.
- [§4.3] There is a typo: 'ridge, ℓ1 bad MCP/reverse Huber examples' should presumably read 'ridge, ℓ1, and MCP/reverse Huber examples'.
- [§5.3.3] 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.
Circularity Check
No significant circularity: the convex-hull derivation is self-contained, and the only caveat (unspecified big-M for logistic) is an under-specification, not a circular step.
full rationale
The central claim (Proposition 4) is that X~ = {(v,z,p0,p,s) : (16a)-(16c)} is an extended formulation for cl conv(X). The proof decomposes X as a disjunction of ℓ+1 sets X^j, writes the standard convex hull via multipliers α (Eq. 18), eliminates α to obtain Eq. 19, and applies invertible changes of variables p0=(1−z1)p0, pℓ=zℓ pℓ, and pj=(z_j−z_{j+1})p_j+z_{j+1}(b_{j+1}−b_j) to recover exactly (16a)-(16c). Each step is an algebraic equivalence under stated assumptions (L(b_j) finite; perspective closure at 0 via Rockafellar 1970, a standard textbook result). No equation is defined in terms of the target claim, and no parameter is fitted to data that it is later said to predict. Proposition 3 is a validity check by cases and is independent of the convex-hull characterization. The numerical comparisons use hyperparameters such as λ, ϵ, and grid granularity, but the mathematical results do not depend on those experimental choices. The paper's self-citations (Atamtürk & Gómez 2019, 2020; Deza & Atamtürk 2022) appear only as related-work pointers to sparse-regression and screening techniques and are not load-bearing for the convexification or relaxation-strength claims. The only notable caveat is in Remark 2: for losses that do not grow superlinearly, such as logistic loss, the paper states that big-M constraints pi0 ≤ M(1−zi1) and piℓ ≤ M ziℓ are needed but does not provide a valid data-dependent value for M. This is a completeness/correctness risk for the exact logistic MIO variant, not an instance of a result reducing to its own input or to a self-citation chain.
Assumptions & free parameters
free parameters (4)
- Threshold grid b_j and grid size ell
- Fairness bound epsilon or regularization weight lambda
- Big-M constant M
- Optional regularizer coefficient mu and penalty type
assumptions (7)
- standard math Convex loss functions with finite values at breakpoints
- domain assumption Empirical distribution approximates population distribution
- domain assumption Finite threshold grid dDP_ell approximates continuous DP
- ad hoc to paper Features are nonzero and implicitly positive in the single-factor reduction
- ad hoc to paper Big-M can be chosen sufficiently large without cutting off optima
- standard math NP-hardness of (8)-(10) follows from Amaldi and Kann (1995)
- domain assumption Two protected classes with binary sensitive attribute
Cite this review
Pith. "Pith review of Fair and Accurate Regression: Strong Formulations and Algorithms." pith.science (2026). https://pith.science/paper/77VUTAZX
@misc{pith2026241217116,
author = {Pith},
title = {Pith review of: Fair and Accurate Regression: Strong Formulations and Algorithms},
year = {2026},
howpublished = {\url{https://pith.science/paper/77VUTAZX}},
note = {Machine review of arXiv:2412.17116}
}
read the original abstract
This paper introduces mixed-integer optimization methods to solve regression problems that incorporate fairness metrics. We propose an exact formulation for training fair regression models. To tackle this computationally hard problem, we study the polynomially-solvable single-factor and single-observation subproblems as building blocks and derive their closed convex hull descriptions. Strong formulations obtained for the general fair regression problem in this manner are utilized to solve the problem with a branch-and-bound algorithm exactly or as a relaxation to produce fair and accurate models rapidly. Moreover, to handle large-scale instances, we develop a coordinate descent algorithm motivated by the convex-hull representation of the single-factor fair regression problem to improve a given solution efficiently. Numerical experiments conducted on fair least squares and fair logistic regression problems show competitive statistical performance with state-of-the-art methods while significantly reducing training times.
Figures
Figures from the paper (5 more)
Forward citations
Cited by 1 Pith paper
-
Responsible Machine Learning via Mixed-Integer Optimization
A comprehensive tutorial that synthesizes how mixed-integer optimization can encode interpretability, robustness, and fairness constraints into machine learning models.
Reference graph
Works this paper leans on
-
[12]
Unbiased Subdata Selection for Fair Classification: A Unified Framework and Scalable Algorithms
Qing Ye and Weijun Xie. Unbiased subdata selection for fair classification: A unified framework and scalable algorithms. arXiv preprint arXiv:2012.12356 ,
work page Pith review arXiv 2012
-
[13]
Distributionally fair stochastic optimization using wasserstein distance
Qing Ye, Grani A Hanasusanto, and Weijun Xie. Distributionally fair stochastic optimization using wasserstein distance. arXiv preprint arXiv:2402.01872 ,
-
[1970]
Yves Rychener, Bahar Taskesen, and Daniel Kuhn. Metrizing fairness. arXiv preprint arXiv:2205.15049 ,
-
[1972]
Spectral algorithms for computing fair support vector machines
Mahbod Olfat and Anil Aswani. Spectral algorithms for computing fair support vector machines. In International Conference on Artificial Intelligence and Statistics , pages 1933–1942. PMLR,
work page 1933
-
[1996]
DOI: https://doi.org/10.24432/C5XW20. Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. A convex framework for fair regression. arXiv preprint arXiv:1706.02409 ,
-
[1998]
Ohannessian, and Nathan Srebro
Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro. Learning non-discriminatory predictors. In Proceedings of the 2017 Conference on Learning Theory , volume 65 of Proceedings of Machine Learning Research, pages 1920–1953. PMLR, 07–10 Jul
work page 2017
-
[2000]
Rank-one Convexification for Sparse Regression
Alper Atamt¨ urk and Andr´ es G´ omez. Rank-one convexification for sparse regression.arXiv preprint arXiv:1901.10334,
work page Pith review arXiv 1901
-
[2009]
DOI: https://doi.org/10.24432/C53W3X. Ralph Tyrell Rockafellar. Convex Analysis. Princeton University Press,
Show all 14 references
-
[2010]
The fairness regularizer is computed by solving the optimization problem (23)
A Appendix A.1 Coordinate descent implementation details We describe an efficient implementation of a single iteration of the coordinate descent algorithm 1 to compute wt+1 k = arg minwk∈ ˜B L(wk) + λR(wk), where L(wk) is the loss function and R(wk) is the fairness regularize....
2017
-
[2018]
Fair decision rules for binary classification.arXiv preprint arXiv:2107.01325 ,
Connor Lawless and Oktay G¨ unl¨ uk. Fair decision rules for binary classification.arXiv preprint arXiv:2107.01325 ,
-
[2019]
Edoardo Amaldi and Viggo Kann
doi: 10.1609/aaai.v33i01.33011418. Edoardo Amaldi and Viggo Kann. The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science, 147(1-2):181–210,
-
[2020]
Controlling attribute effect in linear regression
Toon Calders, Asim Karim, Faisal Kamiran, Wasif Ali, and Xiangliang Zhang. Controlling attribute effect in linear regression. In 2013 IEEE 13th International Conference on Data Mining , pages 71–80. IEEE,
2013
-
[2023]
Fairness-aware classifier with prejudice remover regularizer
Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness-aware classifier with prejudice remover regularizer. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28,
2012
-
[2024]
Learning optimal fair decision trees: Trade-offs between interpretability, fairness, and accuracy
Nathanael Jo, Sina Aghaei, Jack Benson, Andres Gomez, and Phebe Vayanos. Learning optimal fair decision trees: Trade-offs between interpretability, fairness, and accuracy. In Proceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society , pages 181–192,
2023
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.