Pith. sign in

REVIEW 2 major objections 5 minor 27 references

Local Statistical Parity for the Estimation of Fair Decision Trees

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

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

Pith's one-line read This paper proves that a decision tree satisfies statistical parity if each decision-node split is conditionally independent of the protected attribute, and introduces C-LRT to enforce that condition during recursive tree construction.

desk verdict A correct local-parity theorem with an honest heuristic algorithm that needs a substantial empirical rework before its fairness claims are convincing. read the letter →

arxiv 2504.18262 v1 pith:XSD4SZ4Z submitted 2025-04-25 cs.LG

Andrea Quintanilla , Johan Van Horebeek This is my paper · ORCID
classification cs.LG
keywords fairdecisiontreesstatisticalparitylocalfairnessconstrainedlogisticregressionrecursivepartitioningalgorithmicCART
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 proposes a node-level fairness criterion called Local Statistical Parity and proves a theorem connecting it to the global Statistical Parity criterion for decision trees. The main theoretical result is that if every decision node's split test is independent of the protected attribute $A$ given that a case reaches that node, then the tree's output is independent of $A$, meaning the tree satisfies statistical parity. The paper then presents C-LRT, a recursive tree-growing algorithm that follows CART but chooses each split by fitting a constrained logistic regression on a single predictor, bounding the absolute covariance between the signed distance and $A$. Experiments on Adult, COMPAS, Ricci, and Law School data show that the constraint parameter $c$ trades accuracy against fairness, and very strong constraints tend to collapse the tree into a single-node constant classifier. A sympathetic reader should care because this offers a provable local-to-global fairness guarantee that fits naturally inside standard recursive tree estimation.

What carries the argument

The key objects are the domain indicator function $\mathrm{dom}_{T_t}(X)$ and the extended split function $I^*_t(X)$, which equals the actual split rule inside node $t$'s domain and a fixed dummy value $\alpha$ outside it. The local criterion is $A \perp \mathrm{dom}_{T_t}(X)$, and Lemma 6 shows that if each decision node's extended split is conditionally independent of $A$ within that node's domain, then every node, including leaves, satisfies the local criterion; Lemma 4 then lifts local parity at the leaves to global parity of the tree. For the algorithm, the machinery is Constrained Logistic Regression: at each node, for each predictor $X_j$, a logistic model $\mathrm{sign}(\theta^T X_j)$ is fit subject to $|\mathrm{Cov}(\mathrm{sd}_\theta(X_j), A)| \le c$, a convex relaxation of the independence required by the theorem.

What would settle it

On a dataset where C-LRT runs with a small constraint value $c$, compute the actual split indicator $I(\theta^T X_j < 0)$ chosen at an internal node and test whether it is independent of $A$ conditional on membership in that node, for example with a chi-square test; if the test rejects independence even as $c$ approaches zero while the tree remains non-constant, the algorithm's constraint does not implement the hypothesis of Theorem 7.

Watch

Extended reading notes

Core claim

The central claim is Theorem 7: for a decision tree $T$, if every decision node $t$ satisfies $A \perp I^*_t(X) \mid \mathrm{dom}_{T_t}(X)=1$, then $A \perp T(X)$, so the tree satisfies Statistical Parity. Here $I^*_t$ is the split test of node $t$ extended to the whole input space with a dummy value outside the node's domain, and $\mathrm{dom}_{T_t}(X)$ indicates whether a case falls into node $t$'s region. The proof proceeds by induction: the local independence condition implies every node satisfies Local Statistical Parity, and because the terminal-node domains partition the input space, local parity at the leaves implies global parity. This reduces a global fairness requirement to a condition that can be checked one split at a time during recursive tree construction.

Load-bearing premise

The practical fairness of C-LRT rests on the unproven step that bounding the covariance between a continuous score and the protected attribute is close enough to making the actual binary split independent of that attribute, and zero covariance does not imply that a thresholded score is independent.

Editorial extensions

If this is right

  • Any recursive tree-growing method can promote global statistical parity by enforcing conditional independence of each split from the protected attribute within the split's node region.
  • The condition in Theorem 7 is sufficient but not necessary: a tree can satisfy statistical parity even when some local splits depend on the protected attribute.
  • C-LRT gives a tunable fairness-accuracy trade-off through the parameter $c$, and as $c$ grows large its behavior converges to the unconstrained logistic regression tree.
  • Strong fairness constraints can push C-LRT toward degenerate single-node constant trees, so practical use requires choosing $c$ to avoid sacrificing all predictive capacity.
  • Because each split is fit on a single predictor, the method remains viable in high-dimensional settings where fitting a full multivariate split would be expensive.

Reading between the lines

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

  • The theorem is splitter-agnostic, so any node classifier that enforces conditional independence of the split indicator from $A$ could replace logistic regression and still inherit the global guarantee.
  • A direct way to test the heuristic gap in the paper is to compare two C-LRT variants: one constrained on the continuous signed distance, as proposed, and one constrained directly on the binary split indicator; if fairness metrics diverge, the covariance proxy is the limiting step.
  • The same local-to-global induction could be adapted to other fairness criteria, such as equalized odds, by stating the local condition jointly with the label $Y$, which the paper leaves as future work.
  • The observed collapse to constant trees under strict constraints suggests that enforcing parity locally may conflict with representing any non-constant function, a structural limitation worth quantifying beyond the paper's experiments.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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 proposes a local fairness criterion for decision trees, called Local Statistical Parity, and proves that if every decision node's split is conditionally independent of the protected attribute A given that the node is reached, then the whole tree satisfies Statistical Parity (Theorem 7, via Lemmas 4 and 6). Based on this theorem, the authors introduce C-LRT, a CART-like algorithm that builds logistic-regression splits subject to a covariance constraint between the signed distance and A, and evaluate it on Adult, COMPAS, Ricci, and Law School datasets. The paper reports that stronger constraints improve fairness metrics at some cost in accuracy, while noting that very strong constraints often produce degenerate constant trees.

Significance. The theoretical result is clean and potentially useful: it gives a local, recursively checkable sufficient condition for global statistical parity in decision trees, which is compatible with greedy tree induction. The proofs of Lemma 4 and Lemma 7 are straightforward and appear correct. However, the practical significance depends on whether the proposed algorithm actually enforces (or approximately enforces) the theorem's hypothesis. As discussed below, the covariance constraint used in C-LRT is only a heuristic proxy for the required conditional independence, and the empirical evaluation is partly obscured by the treatment of constant trees. If the gap between Theorem 7 and the algorithm were quantified or closed under explicit assumptions, the paper would be a solid contribution; in its current form, the applied claims need substantial revision.

major comments (2)
  1. [Section 3, Algorithm 1; Theorem 7] The link between the algorithm's constraint and Theorem 7's hypothesis is not established. Theorem 7 requires, for each decision node t, the conditional independence A ⊥ I(θ_t^T X_{j_t} > 0) given dom_{T_t}(X)=1. For binary A this is equivalent to zero covariance between the thresholded indicator and A within the node. Algorithm 1 instead bounds |Cov(θ_t^T X_{j_t}, A)|, the covariance of the continuous signed distance with A. A zero covariance of the continuous score does not imply zero covariance of a thresholded indicator: if A is Bernoulli(1/2), X|A=0 takes value 1 with probability 0.6 and -1.5 with probability 0.4, and X|A=1 takes value 1 with probability 0.4 and -2/3 with probability 0.6, then E[X|A=0]=E[X|A=1]=0, so Cov(X,A)=0, yet P(X>0|A=0)=0.6 and P(X>0|A=1)=0.4. Thus a C-LRT split with c=0 can violate the theorem's hypothesis, and no bound is given on how the split's statistical-parity violation grows with c. Section 5 explicitly acknowledges this as a relaxation, but the paper does not quantify the resulting gap, and because the fairness behavior of C-LRT is the central applied claim, this is a load-bearing missing step.
  2. [Section 4.1 and 4.2, Figure 1] The evaluation is weakened by the treatment of constant trees. The p-rule is defined to be 1 when the classifier is constant -1, and the n-rule is defined to be 1 when the classifier is constant 1. A constant tree trivially satisfies statistical parity, and Section 4.2 reports that stronger constraints select such degenerate trees more frequently. Consequently, the average fairness improvements shown in Figure 1 can be inflated by degenerate fits rather than by locally conditionally independent splits. The text notes this side effect but does not report fairness metrics restricted to non-degenerate trees or otherwise disentangle the two effects. This makes it difficult to assess the empirical claim that C-LRT balances accuracy and fairness through the proposed local criterion.
minor comments (5)
  1. [Section 4.2] The text says the experiments study the effects of parameters c and λ, but λ is never defined or used elsewhere; this appears to be a leftover from an earlier draft.
  2. [Definition 5 and Algorithm 1] The notation is inconsistent: Section 1.2 defines node tests as I(X_{j_t} < r_t), while Definition 5 and Algorithm 1 use tests of the form I(0 < θ_t^T X_{j_t}) without explicitly reconciling the two forms or explaining how θ_t and the threshold 0 relate to r_t.
  3. [Algorithm 1] There are typographical issues in the pseudocode, such as 'Dt,j←−{(xj,a,y)...' where the arrow and minus sign are conflated; this should be cleaned up.
  4. [Figure 1] The caption uses both 'LR T' and 'C-LR T' while the body uses LRT and C-LRT; the notation should be unified.
  5. [References] Reference [16] contains a typo: 'Pattern Recogonition' should be 'Pattern Recognition'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the local-to-global parity theorem follows from definitions, and C-LRT's covariance constraint is explicitly a relaxation, so no claim reduces to its own inputs.

full rationale

The paper's theoretical contribution is self-contained: Lemma 4, Lemma 6, and Theorem 7 are proved directly from the definitions of domTt and I*_t using standard conditional-independence composition; no fitted parameter appears in the derivation, and the conclusion A⊥T(X) is not an input to the assumptions. The algorithmic step is explicitly labeled a relaxation rather than an equivalence: Section 5 states 'a relaxation is introduced: instead of requiring independence (A⊥ bY(X)), it only imposes that the magnitude of covariance is less than a certain value,' and the Results section concedes the method 'works with a relaxation of the independence requirement of Theorem 7.' Therefore the covariance constraint is not being presented as a derivation of the theorem's hypothesis, and no parameter fitted to fairness data is renamed as a prediction. The empirical evaluations use held-out test sets, and constant-tree degeneracies are reported rather than hidden. All cited work (especially C-LR [5]) is external, so no self-citation chain is load-bearing. The skeptic's point that bounded covariance does not imply conditional independence of the thresholded split is a correctness/approximation limitation, not a circularity; it belongs in a validity assessment, not in a circularity score.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central derivation adds no free constants: the theorem uses only definitions. The empirical claim depends on user-chosen c and on the unproved covariance-to-independence relaxation. The theta_j coefficients are learned model parameters, not hand-set constants, so they are not listed here.

free parameters (2)
  • c = user-specified; reported grid of values (small to large)
    Controls the trade-off between accuracy and fairness; the central empirical claim is a function of this parameter, and the paper reports results across values rather than fixing it.
  • alpha = any value in R \ {0,1}; not empirically meaningful
    Definition 5 uses an arbitrary alpha outside {0,1} to extend the domain of the test function; any such value works, so it carries no empirical content.
assumptions (4)
  • domain assumption A is binary, is not among the predictors X, and the training sample is drawn i.i.d. from (X,A,Y)
    Stated in Section 1.2 Notation; simplifies the proofs and limits the scope to the settings tested.
  • domain assumption Y is binary, predictors are numerical, and trees are binary
    Assumed throughout; the method is defined only for this setting.
  • standard math Standard probability independence and conditional independence definitions
    Used in Lemmas 4, 6, and 7; unproblematic.
  • ad hoc to paper The covariance constraint |Cov(sd_theta(X_j), A)| <= c is a valid relaxation of the conditional independence required by Theorem 7
    Section 3 introduces this relaxation without proof; the empirical evaluation depends on it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Local Statistical Parity for the Estimation of Fair Decision Trees." pith.science (2026). https://pith.science/paper/XSD4SZ4Z

@misc{pith2026250418262,
  author       = {Pith},
  title        = {Pith review of: Local Statistical Parity for the Estimation of Fair Decision Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XSD4SZ4Z}},
  note         = {Machine review of arXiv:2504.18262}
}
read the original abstract

Given the high computational complexity of decision tree estimation, classical methods construct a tree by adding one node at a time in a recursive way. To facilitate promoting fairness, we propose a fairness criterion local to the tree nodes. We prove how it is related to the Statistical Parity criterion, popular in the Algorithmic Fairness literature, and show how to incorporate it into standard recursive tree estimation algorithms. We present a tree estimation algorithm called Constrained Logistic Regression Tree (C-LRT), which is a modification of the standard CART algorithm using locally linear classifiers and imposing restrictions as done in Constrained Logistic Regression. Finally, we evaluate the performance of trees estimated with C-LRT on datasets commonly used in the Algorithmic Fairness literature, using various classification and fairness metrics. The results confirm that C-LRT successfully allows to control and balance accuracy and fairness.

Figures

Figures reproduced from arXiv: 2504.18262 by the authors.

Figure 1
Figure 1. Prediction metrics (left column) and fairness metrics (right column) for LRT and C-LRT. The x-axis is associated with the value of the parameter [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 20 canonical work pages

  1. [1]

    Learning optimal and fair decision trees for non-discriminative decision-making

    Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. “Learning optimal and fair decision trees for non-discriminative decision-making”. In: Pro- ceedings of the AAAI Conference on Artificial In- telligence. Vol. 33. 01. 2019, pp. 1418–1426

    work page 2019

  2. [2]

    Machine bias

    Julia Angwin et al. “Machine bias”. In: Ethics of Data and Analytics . Auerbach Publications, 2016, pp. 254–264

    work page 2016

  3. [3]

    Fairness and Machine Learning

    Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning . http : / / www . fairmlbook . org. fairmlbook.org, 2019

    work page 2019

  4. [4]

    D. Biddle. Adverse Impact and Test Validation: A Practitioner’s Guide to Valid and Defensible Em- ployment Testing . Taylor & Francis, 2017. isbn: 9781351960618. url: https : / / books . google . com.mx/books?id=%5C_AwkDwAAQBAJ

    work page 2017

  5. [5]

    Fairness constraints: A flexible approach for fair classification

    Muhammad Bilal et al. “Fairness constraints: A flexible approach for fair classification”. In: Journal of Machine Learning Research 20 (2019), pp. 1–42. issn: 15337928

    work page 2019

  6. [6]

    Classification and Regression Trees

    Leo Breiman et al. Classification and Regression Trees. Taylor & Francis, 1984. isbn: 0412048418

    work page 1984

  7. [7]

    Fairness through awareness

    Cynthia Dwork et al. “Fairness through awareness”. In: ITCS 2012 - Innovations in Theoretical Com- puter Science Conference (2012), pp. 214–226. doi: 10.1145/2090236.2090255. arXiv: 1104.3913

    arXiv 2012

  8. [8]

    Metric learning for individual fairness

    Christina Ilvento. “Metric learning for individual fairness”. In: Leibniz International Proceedings in Informatics, LIPIcs 156.2 (2020), pp. 1–2. issn: 18688969. doi: 10 . 4230 / LIPIcs . FORC . 2020 . 2. arXiv: 1906.00250

    arXiv 2020

Show all 27 references
  1. [9]

    An algo- rithm for removing sensitive information: Applica- tion to race-independent recidivism prediction

    James E. Johndrow and Kristian Lum. “An algo- rithm for removing sensitive information: Applica- tion to race-independent recidivism prediction”. In: Annals of Applied Statistics 13.1 (2019), pp. 189–

    2019

  2. [10]

    Discrimination aware decision tree learn- ing

    Faisal Kamiran, Toon Calders, and Mykola Pech- enizkiy. “Discrimination aware decision tree learn- ing”. In: Proceedings - IEEE International Confer- ence on Data Mining, ICDM (2010), pp. 869–874. issn: 15504786. doi: 10.1109/ICDM.2010.50

    2010 doi

  3. [11]

    Counterfactual fairness

    Matt Kusner et al. “Counterfactual fairness”. In: Advances in Neural Information Processing Sys- tems 2017-Decem.NIPS (2017), pp. 4067–4077. issn: 10495258. arXiv: 1703.06856

    2017 arXiv

  4. [12]

    A survey on datasets for fairness-aware machine learning

    Tai Le Quy et al. “A survey on datasets for fairness-aware machine learning”. In: Wiley Inter- disciplinary Reviews: Data Mining and Knowledge Discovery 12.3 (2022), pp. 1–59. issn: 19424795. doi: 10.1002/widm.1452. arXiv: 2110.00530

    2022 arXiv

  5. [13]

    A Survey on Bias and Fair- ness in Machine Learning

    Ninareh Mehrabi et al. “A Survey on Bias and Fair- ness in Machine Learning”. In: ACM Computing Surveys 54.6 (2021), pp. 1–35. issn: 0360-0300. doi: 10.1145/3457607. arXiv: 1908.09635

    2021 arXiv

  6. [14]

    Algorithmic fairness: Choices, assumptions, and definitions

    Shira Mitchell et al. “Algorithmic fairness: Choices, assumptions, and definitions”. In: Annual Review of Statistics and Its Application 8 (2021), pp. 141– 11

    2021

  7. [15]

    deste- fano

    Supreme Court of the United States Ricci v. deste- fano. Ricci v. DeStefano, 557 U.S. 557 (2009)

    2009

  8. [16]

    Pattern Recogonition and Neural Net- works

    Brian Ripley. Pattern Recogonition and Neural Net- works. Cambridge University Press, 2005. isbn: 0 521 46086 7

    2005

  9. [17]

    Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead

    Cynthia Rudin. “Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead”. In: Nature machine intelligence 1.5 (2019), pp. 206–215

    2019

  10. [18]

    Individually Fair Gradi- ent Boosting

    Alexander Vargo et al. “Individually Fair Gradi- ent Boosting”. In: (2021). arXiv: 2103.16785. url: http://arxiv.org/abs/2103.16785

    2021 arXiv

  11. [19]

    Fairness definitions explained

    Sahil Verma and Julia Rubin. “Fairness definitions explained”. In: 2018 ieee/acm international work- shop on software fairness (fairware) . IEEE. 2018, pp. 1–7

    2018

  12. [20]

    LSAC National Longitudinal Bar Passage Study. LSAC Research Report Series

    Linda F Wightman. “LSAC National Longitudinal Bar Passage Study. LSAC Research Report Series.” In: (1998)

    1998

  13. [21]

    Trustworthy ai

    Jeannette M Wing. “Trustworthy ai”. In: Commu- nications of the ACM 64.10 (2021), pp. 64–71

    2021

  14. [22]

    Numerical op- timization

    Stephen Wright and Jorge Nocedal. Numerical op- timization. Springer Science, 1999

    1999

  15. [23]

    Training individually fair ML models with Sensitive Subspace Robustness

    Mikhail Yurochkin, Amanda Bower, and Yuekai Sun. “Training individually fair ML models with Sensitive Subspace Robustness”. In: (2019), pp. 1–

    2019

  16. [27]

    url: http://arxiv.org/ abs/1907.00020

    arXiv: 1907.00020. url: http://arxiv.org/ abs/1907.00020. 12 (a) Adult. (b) COMP AS. (c) Ricci. (d) Law School. Figure 1: Prediction metrics (left column) and fairness metrics (right column) for LR T and C-LR T. The x-axis is associated with the value of the parameter c of C-L...

    1907 arXiv

  17. [163]

    issn: 2326831X. doi: 10 . 1146 / annurev - statistics-042720-125902

  18. [220]

    doi: 10.1214/18- AOAS1201

    issn: 19417330. doi: 10.1214/18- AOAS1201 . arXiv: 1703.04957

    arXiv

  19. [2009]

    url: https://supreme.justia.com/cases/ federal/us/557/557/

Pith tools

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