{"id":"1eb3bfd7-abfa-4279-b607-ab9c4dee030e","arxiv_id":"2502.02221","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Maximum Subgroup Discrepancy is a sample-efficient, interpretable distribution distance for intersectional bias detection, provably linear in the number of protected attributes and computable to global optimality via mixed-integer optimization.","lead":"The paper defines Maximum Subgroup Discrepancy, a distance between two data distributions measured by the largest disagreement over all simple feature-based subgroups, and proves it needs only linearly many samples in the number of protected features. It adds an exact integer-programming solver and shows on US Census data that the estimate stabilizes with far fewer samples than Total Variation or Wasserstein distances, while naming the most biased subgroup.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"MIO formulation (15) only searches positive-literal conjunctions; MSD definition (3)-(5) includes negated literals, so the claimed empirical MSD and recovered subgroup are lower bounds over a restricted class.","rationale":"The reader's weakest_assumption matches my main concern: the algorithm searches only positive-literal conjunctions while the formal MSD includes negations. I do not see a more fundamental flaw. Theorem 3.1 is a correct union-bound argument over a finite family of size at most 3^|P|; the sample-complexity statement is internally consistent. The MIO encoding correctly maximizes |mu_hat(chi_S)-nu_hat(chi_S)| over positive-literal conjunctions for a fixed sample. The mismatch matters because the paper repeatedly claims to compute the empirical MSD and recover the worst subgroup (Sec. 4.1, Sec. 5.3.3, App. B.3), and the linear-in-|P| guarantee is invoked for this quantity. If the intended definition were restricted to positive literals, the family size would be 2^|P|, the same theorem would apply with |P| replaced by |P| (still linear), and the paper would need to say that negated subgroups such as 'not white' are out of scope; it does not. The other concerns raised by the reader, MMD's empirical convergence and normalization of relative distances, are comparative overstatements rather than internal correctness gaps. The positivity gap is therefore the load-bearing obstacle to ACCEPT. Since the formal theorem is sound and the MIO fix is straightforward, the reader's CONDITIONAL verdict remains appropriate.","tokens_in":20181,"tokens_out":6502,"duration_ms":66133,"concrete_test":"On a small dataset (e.g., |P|=6 binary protected coordinates, N=200 per class), construct a distribution pair whose maximum in Eq. (5) is attained by a term containing a negated literal, e.g., \\bar{x}_1 \\wedge x_2. Compute the exact empirical MSD by brute-force enumeration of all 3^|P| conjunctions of literals, and solve MIO (15) on the same data. If the MIO objective is strictly less than the brute-force value, or the returned subgroup corresponds to a different term, Section 4.1's 'empirical estimate of MSD' claim is false for the formal definition. Repeating over several random instances establishes whether the gap is systematic; additionally, extending (15d)-(15e) with variables for negated literals should recover the brute-force value and close the gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3 defines MSD as a supremum over SP, the family of all conjunctions of literals x_p and \\bar{x}_p (Eqs. (3)-(5)), with |SP| <= 3^|P|. The MIO formulation in Section 4.1 does not optimize over this family. Constraints (15d)-(15e), with u_j in {0,1} and x_{i,j} in {0,1}, implement only positive literals: if feature j is selected, a sample belongs to the subgroup only when x_{i,j}=1. There is no variable or constraint encoding the literal \\bar{x}_j, so negated-category subgroups are invisible. Consequently, the sentence in Section 4.1, 'By solving this MIO problem, we find the subgroup with the highest absolute difference ... i.e., the empirical estimate of MSD', is true only for the sub-family of positive-literal conjunctions. For data whose maximally discrepant subgroup is \\bar{x}_1 \\wedge x_2 (or any union of terms), the MIO value is a strict lower bound on MSD(mu_hat,nu_hat;P) and the recovered subgroup is not the formal maximizer. This is load-bearing because the paper's practical claims, exact empirical MSD evaluation and exact recovery of the worst interpretable subgroup, are stated and used (Section 5.3.3, Appendix B.3) for the formal MSD, while Theorem 3.1 bounds a quantity that the released algorithm does not compute. The theorem itself is a correct finite-family concentration bound; the gap is between the definition and the solver. The fix is straightforward, add negated-literal indicator variables, which is why this warrants a conditional, not a rejection.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Maximum Subgroup Discrepancy (MSD), a distance between two distributions defined as the supremum, over all conjunctions of literals on a set of protected attributes P, of the absolute difference in probability mass assigned to the corresponding subgroup. The central theoretical result (Theorem 3.1, Eq. (12)) is a uniform-concentration bound showing that the empirical MSD estimates the population MSD with error O(sqrt((|P| + log(1/delta))/N)), i.e., sample complexity linear in the number of protected attributes. The paper also proposes a mixed-integer optimization (MIO) formulation (Eq. (15)) to compute the empirical MSD exactly, reports experiments on Census-based datasets comparing MSD to TV, Wasserstein, MMD, and DNF-learning baselines, and lists the recovered most-discrepant subgroups. The claimed contributions are a sample-efficient, interpretable bias metric and an exact optimization algorithm for it.","tokens_in":20293,"tokens_out":3357,"duration_ms":36856,"significance":"If the central results hold as stated, the paper addresses a real practical need: auditing intersectional bias with a finite-sample guarantee and recovering an interpretable description of the worst subgroup. The theorem is parameter-free and proved from a stated external concentration inequality, with no fitted constants entering the sample-complexity bound. The MIO formulation provides exact global solutions for the restricted family of positive-literal conjunctions on most tested instances, and the authors supply open code and detailed experimental results, which are concrete strengths. However, the paper's advertised equivalence between the formal definition of MSD, which includes negated literals, and the MIO implementation, which only searches positive-literal conjunctions, is currently broken; this gap affects the interpretation of the empirical results and of the threshold/interpretability claims. The contribution is therefore potentially significant, but the manuscript needs a substantive fix before the claims can be endorsed.","major_comments":[{"comment":"The MIO formulation (15) does not optimize over the family SP defined in Section 3. The definition of MSD in Eq. (5) is a supremum over all conjunctions of literals x_p and \\bar{x}_p, with |SP| <= 3^|P|, but constraints (15d) and (15e) with u_j in {0,1} only encode positive literals: a sample belongs to the subgroup only when x_{i,j}=1 for every selected feature j. There is no variable or constraint encoding negation, so subgroups such as \\bar{x}_1 \\wedge x_2 are not representable. Consequently the sentence in Section 4.1, \"By solving this MIO problem, we find the subgroup with the highest absolute difference ... i.e., the empirical estimate of MSD(mu,nu;P)\", is true only for the sub-family of positive-literal conjunctions. For data whose maximally discrepant subgroup uses a negation, the MIO value is a strict lower bound on the formal MSD and the recovered subgroup is not the formal maximizer. This is load-bearing because Theorem 3.1 bounds the formal quantity, while the released algorithm computes a different quantity.","section":"Section 4.1, Eq. (15)"},{"comment":"The practical claims of exact recovery of the worst subgroup and of a threshold guarantee are stated for the formal MSD but are only supported for positive-literal conjunctions. In Section 5.3.3 the paper says that global optimality of the MIO solution enables one to be sure that no subgroup violates a threshold and to obtain the most disadvantaged subgroup; Appendix B.3 lists recovered subgroups. If the formal MSD allows negated literals, then a subgroup with negation may be the true maximizer, and the solver would not find it, so both the threshold statement and the list of recovered subgroups are only valid for the restricted class. The authors should either extend the MIO with negation variables or explicitly redefine the MSD notion used in the experiments and adjust the claims accordingly.","section":"Section 5.3.3 and Appendix B.3"},{"comment":"The comparison in Table 1 between MSD and TV/Wasserstein/MMD sample complexities should be qualified. The exponential lower bounds are for estimating those distances over general or high-dimensional measure classes, whereas MSD is a supremum over a finite class of conjunctions; the linear bound in |P| is a direct consequence of this restriction (|SP| <= 3^|P|). The paper should state clearly that the sample-complexity advantage is obtained by moving to a weaker, restricted notion of distance, not by a better estimator for the same class of distances. This does not invalidate the contribution, but it is central to how readers should interpret the table and the claims of practical feasibility.","section":"Table 1 and Section 3.1"}],"minor_comments":[{"comment":"The heading \"Datasests\" contains a typo and should read \"Datasets\".","section":"Section 5.1"},{"comment":"The relationship between MSDD (Eq. (2)) and MSD (Eq. (5)) is easy to confuse because MSDD is defined for an arbitrary distance Delta, while MSD is then introduced as a specific choice of Delta. The paper should add a sentence explicitly stating that MSD is the instance of MSDD obtained by taking Delta(A,B) = |A - B| over the same family of subgroups.","section":"Section 1.1 and Eq. (2)"},{"comment":"The legend in Figure 2 mentions \"Proportion of subgroups evaluated within 10 minutes\", but the axes label is \"Mean number of considered subgroups\". It should be clarified whether the plotted quantity is a proportion or a count, and the caption should describe how configurations that were not solved to optimality are excluded.","section":"Figure 2"},{"comment":"The sentence \"The MSD points are on the diagonal since we know we have the maximum overall subgroups when the formulation is solved to global optimality\" is only correct for the positive-literal sub-family, given the issue raised in the first major comment; this wording should be revised.","section":"Section 5.3.1"},{"comment":"The paper reports that 13 out of 250 seeded setups did not solve to global optimality within 10 minutes, but does not state how these runs are treated in the plots and averages. It should clarify whether the reported values for those runs are best feasible solutions, best bounds, or whether those configurations are omitted.","section":"Section 5.3.2"}],"recommendation":"major_revision","confidential_remarks":"The core concentration result (Theorem 3.1) is sound, and the paper has genuine strengths: a parameter-free proof, exact global optimization for a well-defined sub-family, open code, and substantial real-data evaluation. The main blocker is the mismatch between the formal definition of MSD over all conjunctions of literals and the MIO solver that only searches positive-literal conjunctions. This is fixable by adding negation variables to the MIO or by explicitly changing the definition of MSD to positive-literal conjunctions and adjusting the claims, but until then the paper's headline claims about empirical MSD evaluation and exact recovery of the worst subgroup are not supported. I would encourage the authors to make the fix and resubmit; with the fix, the paper could be acceptable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead the MSD bias-detection paper. The mathematical center holds: MSD as sup over conjunctions of literal indicators, with Theorem 3.1 a clean union bound over at most 3^|P| terms, giving O(|P|/epsilon^2) samples. The MIO (15) is a legitimate way to search single conjunctions, and the experiments compare it against TV, W1/W2, MMD, Ripper, and BRCG on ten Census-derived datasets, with code on GitHub and 13/250 timeouts disclosed. That is real evidence, and the interpretable output naming the worst subgroup is a genuine plus.\n\nBut there is a disconnect between the definition and the solver that the paper never flags. Section 3 defines literals as x_p and its negation, so MSD ranges over conjunctions that may include negated features. The MIO constrains u_j=1 to require x_{i,j}=1; there is no way to select \"not x_j\". So the computed value is a lower bound on the formal MSD, and the claimed \"exact empirical estimate\" and \"exact worst-subgroup recovery\" are true only for positive-literal conjunctions. This matters more than a cosmetic mismatch: the theorem's coverage is the full family, and the practical guarantee you would want to advertise is for the quantity the solver actually computes. The fix looks easy — add a second binary indicator per attribute for the negated literal — and the concentration bound still holds. So conditional is the right call, not rejection.\n\nThe paper is also a little loose relative to its own Figure 3 and Section 5.3.2: MMD converges comparably to MSD on these problems, which undercuts the Table 1 \"exponentially worse\" MMD entry if read without the caveats. The paper does acknowledge this (\"one cannot be certain that this holds always\"), so it is an overstated table, not a hidden failure. The \"exponentially fewer samples\" headline also relies on normalizing by the largest-sample estimate, which is itself unconverged for TV and Wasserstein; they admit part of this. Finally, unions of subgroups are not searchable at all — a bias on an age band that spans several bins is invisible by construction. That is a design choice for a conjunction metric, but it should be stated as a limitation in the main text, not left to the reader to infer.\n\nFor a KDD audience, the paper deserves a serious referee; I would accept it and require a revision that aligns the MIO with the formal definition (or redefines MSD over positive conjunctions), discloses the lower-bound nature of the output, and tempers Table 1 and the sample-complexity headline. Worth a reading group slot after that.","headline":"The theorem and experiments are solid, but the MIO solver searches only positive-literal conjunctions while the metric includes negations, so the claimed exact empirical MSD is actually a lower bound; fixable and worth engaging.","tokens_in":21121,"tokens_out":3739,"would_cite":true,"duration_ms":37227,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G05","68Q32","90C11"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces Maximum Subgroup Discrepancy, a distance whose sample complexity is linear in the number of protected attributes, and provides an exact mixed-integer solver that recovers the most disadvantaged subgroup.","keywords":["intersectional fairness","Maximum Subgroup Discrepancy","DNF learning","sample complexity","mixed-integer optimization","bias detection","distribution distance","subgroup fairness"],"falsifier":"Construct distributions $\\mu$ and $\\nu$ over a small protected space with two binary attributes such that the largest discrepancy over the full term class $\\mathcal{S}_P$ is attained by the negated term $\\bar{x}_{p_1}$, then solve the MIO formulation (15) on $10^4$ samples. The returned conjunction will be a positive literal or a conjunction of positive literals, and its achieved discrepancy will be strictly below the discrepancy of $\\bar{x}_{p_1}$, so the reported empirical MSD will not match the formal MSD over $\\mathcal{S}_P$; that outcome is directly observable.","tokens_in":19768,"feed_emoji":"⚖️","tokens_out":12540,"duration_ms":122490,"temperature":0.7,"pith_summary":"The paper introduces Maximum Subgroup Discrepancy (MSD), a distance between probability distributions that reports the largest difference in subgroup weight over every subgroup formed by fixing values of protected attributes. Its central claim is that MSD can be estimated from data with error behaving like $\\sqrt{|P|/N}$, linear in the number of protected attributes, in contrast to total variation, Wasserstein, Hellinger, and MMD, whose worst-case sample complexity is exponential in dimension. If true, exhaustive intersectional bias audits become practical on modest sample sizes, and the method returns a human-readable description of the most disadvantaged subgroup. The paper also gives a mixed-integer optimization formulation that provably finds the empirical MSD and the subgroup attaining it, and validates stability and sample requirements on real-world benchmark datasets.","feed_headline":"New metric finds worst subgroup with linear sample cost","feed_subtitle":"Where total variation and Wasserstein need exponential samples, MSD guarantees a bound linear in protected attributes.","key_machinery":"The mechanism is the finite family of terms. A term $\\chi_S$ is a conjunction of literals $x_p$ or $\\bar{x}_p$ over protected attributes, and MSD is the supremum of the signed weight difference over all such terms. The key identity is the term count: because each of the $|P|$ attributes is either absent, positive, or negated, $|\\mathcal{S}_P| \\le 3^{|P|}$, so $\\log|\\mathcal{S}_P| \\le 2|P|$; plugging this into a uniform-concentration bound over bounded functions gives the $O(\\sqrt{|P|/N})$ error. The practical computation is a mixed-integer linear program with variables $u_j$ indicating which literals appear, variables $y_i$ indicating whether sample $i$ lies in the subgroup, an absolute-value objective via big-M constraints, and a minimum-subgroup-size constraint $N_{\\min}$; its global optimum is the empirical MSD over conjunctions.","core_discovery":"The paper defines $\\text{MSD}(\\mu,\\nu;P)$ as the supremum, over all terms $\\chi_S$ (conjunctions of literals on protected attributes $P$), of $|\\mu(\\chi_S)-\\nu(\\chi_S)|$. Theorem 3.1 states that with probability at least $1-2\\delta$, $$\\text{MSD}(\\mu,\\nu;P) \\le \\text{MSD}(\\hat{\\mu},\\hat{\\nu};P) + 4\\sqrt{\\frac{2|P|+\\log(2/\\delta)}{2N}},$$ with $N=\\min(N_1,N_2)$, so the sample complexity is $O((|P|+\\log(1/\\delta))/\\varepsilon^2)$. The proof uses the fact that there are at most $3^{|P|}$ terms, so $\\log|\\mathcal{S}_P| \\le 2|P|$, and applies uniform concentration over this finite family. Estimation is recast as weighted 0-1 classification with conjunctions as classifiers, and an MIO model with binary variables for literals and sample memberships solves the empirical maximum to global optimality. Experiments on public benchmark datasets show MSD converging at sample sizes where total variation and Wasserstein estimates still vary, recovering readable subgroups such as 'DIS=2 AND MIL=4' or 'white women'.","pith_inferences":["Because the MIO constraints only encode positive literals, the practical 'most disadvantaged subgroup' can miss negated terms and unions; on data where the worst subgroup is of that form, the reported MSD is a lower bound and the recovered subgroup is not the true maximizer.","A natural extension is a multi-term DNF version of MSD that maximizes over unions of subgroups, but its sample complexity would likely depend on the DNF size and would not inherit the simple linear-in-|P| bound of the single-term definition.","Theorem 3.1 plus global optimality could be packaged as a bias-certification primitive: fix an acceptable discrepancy threshold and a confidence level, collect $O(|P|/\\varepsilon^2)$ samples, and either certify all conjunction subgroups or return the violating rule.","Practitioners who want the statistical guarantee should use an exact MIO solver rather than heuristic single-term learners, because non-global solutions can silently return a smaller MSD and a wrong subgroup."],"forward_implications":["A data auditor needs $O(|P|/\\varepsilon^2)$ samples to estimate the worst subgroup discrepancy to accuracy $\\varepsilon$ with high probability, rather than a number exponential in the protected attributes.","Because the MIO solution is globally optimal, the empirical MSD comes with a certified upper bound over all searched subgroups, and the method simultaneously returns the most disadvantaged subgroup as an interpretable rule.","MSD sits between the $\\ell_\\infty$ distance and total variation, so it catches intersectional disparities invisible to per-attribute demographic parity without incurring total variation's exponential sample demand.","On the evaluated datasets, MSD stabilizes at a few thousand samples where total variation and Wasserstein estimates still fluctuate, and the recovered subgroups match semantically meaningful groups.","Within the paper's MSDD framework, MSD can serve as the base distance for both data-quality checks (dataset versus a reference population) and model-output audits (positive versus negative class)."],"supporting_citations":[{"why":"Supplies the uniform-concentration inequality (its Theorem 2.13) that yields the bound in Theorem 3.1.","marker":"[41]"},{"why":"Provides the Wasserstein-1 undecidability and infinite sample-complexity lower bound contrasted in Table 1.","marker":"[37]"},{"why":"Gives the exponential minimax lower bound for MMD that MSD is claimed to avoid.","marker":"[53]"},{"why":"Establishes the exponential total-variation and Hellinger lower bound cited in Table 1.","marker":"[14]"},{"why":"The 0-1 error DNF formulation whose constraint structure the MIO model extends.","marker":"[51]"},{"why":"The column-generation DNF learner used as a non-global baseline in the experimental comparison.","marker":"[13]"},{"why":"The rule-learning baseline whose MSD estimates are compared with the MIO solver.","marker":"[9]"},{"why":"Supplies the public benchmark datasets used throughout the evaluation.","marker":"[15]"}],"fun_headline_variants":["Worst-subgroup bias metric needs only linear samples","Linear-sample metric pinpoints most biased subgroup","MSD: bias detection that scales with features, not subgroups","Find the worst bias subgroup with linear sample cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The linear sample-complexity guarantee and the 'worst subgroup' claim hold only when the most discrepant subgroup is a single conjunction of attribute-equals-value conditions over pre-binarized, pre-binned protected attributes; subgroups that are unions, negated categories, or cuts inside a bin are outside the searched class, and on such data MSD becomes a lower bound and the recovered subgroup is the wrong one.","fun_headline_variants_meta":{"raw":{"variants":["Worst-subgroup bias metric needs only linear samples","Linear-sample metric pinpoints most biased subgroup","MSD: bias detection that scales with features, not subgroups","Find the worst bias subgroup with linear sample cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00038,"raw_usage":{"total_tokens":2075,"prompt_tokens":1061,"completion_tokens":1014,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":677,"completion_tokens_details":{"reasoning_tokens":952}},"tokens_in":677,"tokens_out":1014,"duration_ms":8234,"temperature":1.0,"reasoning_tokens":952,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T12:59:58.755824+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct distributions $\\mu$ and $\\nu$ over a small protected space with two binary attributes such that the largest discrepancy over the full term class $\\mathcal{S}_P$ is attained by the negated term $\\bar{x}_{p_1}$, then solve the MIO formulation (15) on $10^4$ samples. The returned conjunction will be a positive literal or a conjunction of positive literals, and its achieved discrepancy will be strictly below the discrepancy of $\\bar{x}_{p_1}$, so the reported empirical MSD will not match the formal MSD over $\\mathcal{S}_P$; that outcome is directly observable.","supporting_citations":[{"cited_title":"2018.Foundations of machine learning","cited_arxiv_id":null,"evidence_quote":"Supplies the uniform-concentration inequality (its Theorem 2.13) that yields the bound in Theorem 3.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Wasserstein-1 undecidability and infinite sample-complexity lower bound contrasted in Table 1."},{"cited_title":"Sriperumbudur, and Bernhard Schölkopf","cited_arxiv_id":null,"evidence_quote":"Gives the exponential minimax lower bound for MMD that MSD is claimed to avoid."},{"cited_title":"Varshney, and Dmitry M","cited_arxiv_id":null,"evidence_quote":"The 0-1 error DNF formulation whose constraint structure the MIO model extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The column-generation DNF learner used as a non-global baseline in the experimental comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The rule-learning baseline whose MSD estimates are compared with the MIO solver."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the public benchmark datasets used throughout the evaluation."}],"review_version":1}