Pith. sign in

REVIEW 2 major objections 5 minor 46 references

For any hard cluster assignment, the subgroup fairness gap equals a covariance-based surrogate, turning non-separable fair K-means into a separable, parallel-optimizable objective.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 15:58 UTC pith:DXODXBAL

load-bearing objection A correct and useful equivalence result for subgroup-fair clustering, with a real but fixable gap between the soft objective optimized and the hard assignments evaluated. the 2 major comments →

arxiv 2607.18119 v1 pith:DXODXBAL submitted 2026-07-20 stat.ML cs.LG

COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering

Kyungseon Lee , Hankyo Jeong , Kunwoong Kim , Kwanho Lee , Yongdai Kim This is my paper
classification stat.ML cs.LG MSC 62H3068T10
keywords fair clusteringsubgroup fairnesscovariance surrogatemultiple sensitive attributesK-meansmarginal fairnesscontinuous relaxationparallel assignment updates
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper targets fair K-means when fairness means cluster assignments should not track intersections of several sensitive attributes. It defines a subgroup fairness gap — the worst weighted total-variation distance between each subgroup's cluster distribution and the overall distribution — and proves that this gap equals a covariance-based quantity: the maximum, over subgroups and over sign vectors on clusters, of the covariance between cluster labels and group membership. Because that covariance form is additive over instances, the fairness penalty becomes separable, and the authors build COVA-FC, an alternating gradient algorithm that updates assignments in parallel and handles exponentially many sparse subgroups without numerical blow-up. The same surrogate extends to marginals by including subgroup-subsets into the worst-case collection, since subgroup fairness alone does not control marginal fairness. On benchmarks, COVA-FC reaches lower fairness gaps at comparable cost and scales to millions of instances.

Core claim

The central claim is Theorem 3.1: for any hard cluster assignment, the subgroup-marginal fairness gap Δ(A;W) is exactly equal to the covariance-based surrogate CR(A;W) — and also to its continuous relaxation CR(A;W) over a simplex weight v. This is not an approximation; it is an identity. The consequence is that the expensive, non-separable fairness constraint in K-means can be replaced by an instance-wise additive objective max over a sign vector β and a subgroup weight v, which admits closed-form gradient updates and parallel per-instance assignment updates. The paper also establishes that subgroup fairness alone can leave marginal group disparities arbitrarily large, and handles both by t

What carries the argument

Subgroup-fairness gap Δ(A;W)=max_{W∈W} π_W Σ_k |p_k(A)-p_{k|W}(A)|, the worst π_W-weighted total variation between overall and group-conditional cluster distributions. The covariance surrogate CR(A;W)=max_{v∈Δ} max_{β∈B∞} (1/2n) Σ_i (Σ_k β_k A_{ik}) v^T(c_i-\bar c) interprets unfairness as maximal linear dependence between cluster assignments and centered subgroup memberships. Its β-maximizer is closed-form (β_k = sign of covariance), and with v fixed the loss separates over instances; this separability is the mechanism that makes the algorithm parallel and scalable.

Load-bearing premise

The load-bearing premise is that the continuously relaxed objective's minimizers are nearly one-hot in practice, so replacing soft assignments by arg max leaves the fairness gap approximately unchanged; the paper supports this empirically but does not prove it.

What would settle it

Run COVA-FC on a dataset constructed so that the optimal soft assignment is diffuse (e.g., overlapping clusters where many instances have A_ik near 1/K at convergence). If the induced hard assignment's Δ is substantially larger than the optimized CR, the relaxation-to-hard step fails and the advertised fairness guarantee collapses.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If the identity holds, tuning the penalty λ directly controls the target fairness gap, because minimizing the surrogate is minimizing the gap itself for hard assignments.
  • COVA-FC's per-iteration cost O(n(Kd+K+2^q)) avoids cubic LP solves, making subgroup-fair clustering feasible for large n and many subgroups.
  • The instance-wise additive gradient enables GPU-parallel assignment updates, giving a 3.2× speedup over the closest variational baseline on a 1.66M-instance dataset at comparable fairness.
  • Including marginal subgroup-subsets into W enforces subgroup and first/second-order marginal fairness simultaneously with little extra computation.
  • Because the surrogate avoids inverse subgroup-cluster masses, it remains numerically stable even when some subgroups contain only a few instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The identity is a general duality: weighted total-variation distance equals an L∞-maximization over sign vectors; any clustering side constraint expressible as low statistical dependence between assignments and side information could reuse this surrogate (the authors mention size-constrained clustering as an example).
  • The same covariance template could apply in other soft-assignment clustering paradigms, such as mixture models or soft hierarchical clustering, not only K-means; the paper lists this as future work.
  • A testable extension: add entropy regularization to sharpen soft assignments and check whether this stabilizes the advertised fairness of the final hard clustering on datasets where soft minimizers are diffuse.
  • The exactness of Theorem 3.1 suggests a cheap auditing tool: compute the covariance max over β and v on a hard assignment to certify its subgroup fairness gap without iterating over all subgroups.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies fair K-means clustering with multiple sensitive attributes that define many (possibly sparse) subgroups. It defines a subgroup-fairness gap Δ(A;W) as a weighted worst-case total-variation distance between each subgroup's cluster distribution and the overall cluster distribution, and proves (Theorem 3.1) that for hard cluster assignments this gap equals a covariance-based quantity CR(A;W), as well as its continuous relaxation CR̄(A;W). The proposed algorithm, COVA-FC, minimizes the K-means loss plus λ·CR̄(A;W) over soft assignments, using alternating updates of adversarial variables (β,v) and per-instance gradient updates of the assignment matrix, and extends the framework to marginal and higher-order marginal fairness by choosing W appropriately. Experiments on Adult, Dutch, Bank, Civilcomments, Communities, ACSIncome, and CelebA compare COVA-FC with FCBC, VFC, FCA, FRA, and FairKM, and report favorable cost–fairness trade-offs, better scalability, and ablations of the two relaxations.

Significance. The main theoretical result is elegant and, if the soft-to-hard gap is bridged, it is a substantive contribution to fair clustering. The covariance identity is non-circular and, under the stated nonempty-cluster assumption, the proof of Theorem 3.1 is correct. The instance-wise decomposable surrogate is genuinely useful: it enables closed-form β updates, parallel per-instance assignment updates, and a per-iteration complexity of O(n(Kd+M+K)) rather than the LP or nK·2^q costs of several baselines. The paper is also unusually transparent about the continuous relaxations, including the concentration of soft assignments and the comparison of CR vs. Δ. The subgroup-marginal extension is well motivated by the counterexample in Appendix A.2. However, the paper's central advertised guarantee—the exact equivalence—is proven only for hard assignments, while the algorithm optimizes a soft objective and evaluates fairness on hard arg-max projections. This is the main load-bearing gap and it currently limits the strength of the empirical claims.

major comments (2)
  1. [§2.3, Eq. (9); §5.1; Theorem 3.1] Theorem 3.1 proves Δ(A;W)=CR(A;W)=CR̄(A;W) for hard assignments A. COVA-FC, however, minimizes Eq. (9) over soft assignments A∈S_K using CR̄, and Section 5.1 evaluates all fairness metrics on the hard projection Â_i = arg max_k A_ik. Nothing in Theorem 3.1 controls this projection. For example, the maximally diffuse soft assignment A_ik=1/K has CR̄(A;W)=0 for any W, while any fixed tie-breaking rule for arg max can produce an arbitrarily unfair hard clustering. The K-means term is linear in A and favors vertices, but the fairness penalty is not convex in a way that excludes interior minimizers; near-one-hot output is not guaranteed by the optimization. The paper's support is empirical (Appendix D.4 and D.6, Figures 7 and 10) and is limited to the specific datasets and λ grids tested; the statement in D.4 that 'the learned assignment is highly concentrated near one-hot vectors in practice
  2. [§2.3 and Appendix B.1 (soft-assignment proof)] The paper calls CR̄ a 'continuous relaxation' of Δ, but Δ is defined in Section 2.1 only for hard assignments. The proof in Appendix B.1 for the soft case silently redefines the conditional probabilities as p_{k|W_m}(A) = Σ_i A_ik r_m(i) / Σ_i A_ik, and then proves equality between this soft Δ and CR̄. Meanwhile, Section 5.1 evaluates Δ on the hard arg-max. Thus there are two different quantities both denoted Δ: the soft one used in the proof of Theorem 3.1 and the hard one used in the experiments. Please define the soft gap explicitly in the main text, state Theorem 3.1 for soft assignments with that definition, and then clearly separate the statement 'the algorithm minimizes a surrogate for the soft gap' from the statement 'the hard projection inherits fairness'. Without this distinction, the exactness claim is easy to over-read.
minor comments (5)
  1. [Theorems 2.1–3.1] The theorem statements do not mention the nonempty-cluster assumption, although the proof of Theorem 3.1 relies on it (both for hard assignments, |{i:A_i=k}|>0, and for soft assignments, Σ_i A_ik>0). The centroid update in Algorithm 1 also divides by Σ_i A_ik. Please state this assumption explicitly in each theorem and discuss what happens if an empty cluster occurs during optimization.
  2. [Notation throughout Sections 2–3] The symbol CR is used for three different objects: the hard covariance surrogate in Eq. (3), the relaxed surrogate in Eq. (4), and the W-version in Eq. (7). The notation becomes especially confusing because Eq. (4) and Eq. (7) use the same symbol CR with and without overline. Section 5.5 introduces the variants CR, CRv, CRA, CR, but the main text does not use this nomenclature consistently. Please choose distinct symbols (e.g., CR, CR̃, CR̄) and use them throughout.
  3. [Table 1 and §4] The complexity O(n(Kd+K+2^q)) is for the full-subgroup case M=2^q. The algorithm and its complexity are stated more generally for a collection W of size M, where the per-iteration cost is O(n(Kd+K+M)). Please state the general form in the main text to avoid the impression that the method is limited to q binary attributes or that M is always 2^q.
  4. [Figure 1 and Section 5.3] The main cost–fairness trade-off figures (Figures 1–2) do not report error bars. Section 5.3 reports averages over five random splits for the marginal extension, but the primary comparisons in Figure 1 do not. If the K-means initialization introduces variability, please add error bars or state that the runs are deterministic for the reported setting.
  5. [Section 5.1, Remark 5.1] The remark explains why the proposed gap is preferred over Balance, but the paper also reports Balance in Appendix D.2. Please add a sentence in Section 5.1 pointing to this appendix, so readers who prefer Balance know it is available for the datasets where it is well-defined.

Circularity Check

0 steps flagged

No significant circularity: the Δ=CR equivalence is a proven algebraic identity, and the soft-to-hard gap is a limitation rather than a circular reduction.

full rationale

The paper's central step, Theorem 3.1, is a genuine derivation rather than a repackaged input: Δ(A;W) and CR(A;W)/CR(A;W) are both explicitly defined in Sections 2–3, and the proof in Appendix B.1 shows their equality by elementary algebra and the dual representation of the ℓ1 norm (max_{‖β‖∞≤1} Σ β_k a_k = Σ |a_k|). The assumptions used (hard assignment, nonempty clusters, the given definition of π_m and p_{k|W_m}) do not include the target equality, and no parameter is fitted to enforce it. The paper's own earlier work is cited only as related fairness methods and as the FCA baseline; the equivalence proof does not rely on those citations. The one genuine concern — that the algorithm optimizes the soft CR while Section 5.1 evaluates Δ on the hard arg-max assignment — is acknowledged in Appendix D.4 ('Although experiments are conducted with soft assignment, the learned assignment is highly concentrated near one-hot vectors in practice') and supported empirically by the concentration analysis in Appendix D.6. This is an approximation/validity gap between the proven hard-assignment theorem and the optimization target, not a circular definition or a fitted input renamed as a prediction. Benchmarks and baselines are external, and the claimed practical gains are measured rather than derived from the equivalence. Hence no circularity is present.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 2 invented entities

Everything the central claim rests on that the reader did not pay for upstream: the dual-norm identity (standard math), the nonempty-cluster standing assumption (domain), the unproven empirical soft-to-hard bridge (the weakest premise), and the π_s weighting choice in the definition of the gap. Free parameters are the tunable hyperparameters; none are fitted to force the equivalence.

free parameters (4)
  • λ (fairness penalty weight) = sweep grid 10^-1..10^4 (Adult/Dutch/Bank), 10^-1..10^6 (Civilcomments)
    Chosen by sweeping to draw Pareto fronts; the reported 'lowest achievable SP' values come from these sweeps.
  • η_A (assignment gradient step size) = 0.004 (Adult), 0.005 (Dutch, Bank), 0.007 (Civilcomments)
    Per-dataset chosen learning rate for the A-update (Appendix D.1).
  • Number of A-updates per iteration = 100 (Adult/Dutch/Bank), 50 (Civilcomments)
    Per-dataset inner-loop count (Appendix D.1).
  • η_v (adversarial step size for v)
    Required by Algorithm 1 (Require: Step sizes η_A and η_v) but never specified in Section 5.1 or Appendix D.1; any exact reproduction must guess this value.
axioms (5)
  • standard math Dual representation: for any vector a ∈ R^K, max_{β:||β||∞≤1} Σ_k β_k a_k = Σ_k |a_k|
    Used in the proof of Theorem 3.1 (Appendix B.1) to rewrite the π-weighted absolute deviations as a covariance maximized over sign patterns β.
  • domain assumption Standing assumption that no cluster has zero mass (hard: |{i:A_i=k}|>0; soft: Σ_i A_ik > 0)
    Invoked explicitly in the proof of Theorem 3.1 (Appendix B.1) to define q_k(m); p_{k|W_m} is undefined if a cluster is empty. Violation is unlikely in practice (K=10, n >> K) but is not guaranteed by the algorithm.
  • domain assumption Optimizing the continuous relaxation (soft A, convex-combination v) yields soft assignments concentrated near one-hot, on which arg max produces a low Δ
    The theorems are exact for hard assignments (and for soft A only if Δ is redefined with soft A); the headline numbers evaluate hard arg-max assignments. The paper supports this bridge empirically (Figs. 7 and 10, Appendices D.4/D.6) but proves no bound. This is the paper's weakest load-bearing premise.
  • domain assumption π_s weighting is the correct normalization for subgroup fairness (tiny subgroups should not dominate)
    Defined in Eq. (1) with justification in Appendix A.1. The same choice allows the A.2 counterexample where the subgroup gap is 1/256 while the marginal gap is 1/2; the paper addresses this via the marginal extension (Section 3).
  • domain assumption K-means cost is the appropriate clustering objective
    Follows prior fair-clustering work [5, 14, 25, 30, 40, 42]; limits generality to K-means-type costs and squared-Euclidean geometry (L2 normalization noted for comparisons with VFC in Table 2).
invented entities (2)
  • CR(A;W) / CR̄(A;W): covariance-based (relaxed) fairness surrogate independent evidence
    purpose: Rewrite the non-separable subgroup(-marginal) fairness gap as an instance-wise additive objective to enable parallel gradient updates.
    For hard assignments, CR = CR̄ = Δ exactly (Theorem 3.1), a checkable equality on any assignment; Figure 7 verifies the relationship empirically. Not a fitted quantity.
  • Continuous relaxation replacing the worst-case subgroup by a convex-combination weight v ∈ simplex no independent evidence
    purpose: Smooth the max over subgroups to stabilize optimization.
    Algorithmic device with no external falsifiable handle; its value is justified by the proof that the simplex max equals the max over observed subgroups for hard assignments and by the ablations (Tables 9-10).

pith-pipeline@v1.3.0-alltime-deepseek · 25184 in / 28836 out tokens · 280113 ms · 2026-08-01T15:58:36.258131+00:00 · methodology

0 comments
read the original abstract

Fair clustering aims to make cluster assignments independent of sensitive attributes, but this goal becomes challenging when multiple sensitive attributes jointly define many subgroups. In such settings, directly extending existing fair clustering algorithms is computationally expensive or numerically unstable, especially when the number of subgroups grows exponentially and some subgroups contain only a few instances. To address these challenges, we define a subgroup-fairness gap for clustering and derive a covariance-based surrogate that exactly matches this gap. We then introduce a continuous relaxation of the surrogate, enabling efficient gradient-based optimization and yielding our proposed algorithm, COVA-FC. We also show that subgroup fairness alone does not imply marginal fairness, and extend our framework to capture a subgroup-marginal-fairness gap. Experiments on benchmark datasets show that COVA-FC achieves competitive cost-fairness trade-offs and improves computational efficiency over existing baselines in both subgroup and higher-order marginal settings.

Figures

Figures reproduced from arXiv: 2607.18119 by Hankyo Jeong, Kunwoong Kim, Kwanho Lee, Kyungseon Lee, Yongdai Kim.

Figure 1
Figure 1. Figure 1: Comparison of trade-offs between subgroup-fairness gap (SP) and cost on (left to right) [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Per-iteration runtime of the loop and matrix implementations of the assignment update on ACSIncome. Parallelization and comparison with VFC. We com￾pare a per-instance loop implementation of the assign￾ment update against our matrix implementation (and so parallel update) on ACSIncome with varying n ∈ {10k, 100k, 500k, 1M}. While the runtime of this loop version grows almost linearly with n, the matrix ver… view at source ↗
Figure 3
Figure 3. Figure 3: Comparison on Communities between subgroup-only COVA-FC and subgroup-marginal COVA-FC (1st+2nd-order marginal + subgroup): (left) SP, (center) MP(1), (right) MP(2) . 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Trade-offs between MP(1) and cost on (left to right) Adult, Dutch, Civilcomments, and Bank datasets, comparing the subgroup-only and subgroup-marginal variants of COVA-FC. 5.4 Computational complexity Computation time. Motivated by the computational complexity analysis in [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Comparison of trade-offs between ‘sum-aggregated’ gap (top: [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of trade-offs between subgroup Balance ( [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Plots of CR vs. ∆ on (left to right) Adult, Dutch, Civilcomments, and Bank datasets. To empirically support Theorem 3.1, we visualize the relationship between CR computed on the learned soft assignment and ∆ computed on the induced hard assignment across different values of λ. Although experiments are conducted with soft assignment, the learned assignment is highly concentrated near one-hot vectors in prac… view at source ↗
Figure 8
Figure 8. Figure 8: Plots of the total loss (clustering cost [PITH_FULL_IMAGE:figures/full_fig_p024_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Plots of ∆(A; W) across iterations on Adult dataset when using CRv (top) and CR (bottom) as the fairness penalty. (left to right) λ ranges from 0.3 to 50. Overall, these results indicate that using hard cluster assignment harms optimization stability even when the most-violated selection is relaxed by the use of v instead of m, and often fails to produce fair clusters in practice. 24 [PITH_FULL_IMAGE:figu… view at source ↗
Figure 10
Figure 10. Figure 10: Histograms of the maximum soft cluster assignment, [PITH_FULL_IMAGE:figures/full_fig_p025_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Cost-fairness trade-off on the CelebA dataset with four binary sensitive attributes (16 subgroups), using image features extracted by a pre-trained ResNet-18 model. E Broader impact COVA-FC targets subgroup unfairness under multiple sensitive attributes, a setting common in real applications such as customer segmentation, resource allocation, and large-scale demographic analysis, where unfair treatment is… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 4 canonical work pages

  1. [1]

    A reductions approach to fair classification

    Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 60–69. PMLR, 10–15 Jul 2018. URL https://proceedings...

    2018

  2. [2]

    Fair regression: Quantitative definitions and reduction-based algorithms

    Alekh Agarwal, Miroslav Dudík, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and reduction-based algorithms. InProceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, 2019. URL http://proceedings.mlr.press/v97/agarwal19d.html

    2019

  3. [3]

    Scalable fair clustering

    Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. InInternational Conference on Machine Learning, pages 405–413. PMLR, 2019

    2019

  4. [4]

    Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. URL https://doi.org/10.24432/C5XW20

    doi:10.24432/c5xw20 1996

  5. [5]

    Flores, and Maryam Negahbani

    Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas J. Flores, and Maryam Negahbani. Fair algorithms for clustering. InAdvances in Neural Information Processing Systems, volume 32, 2019.https://arxiv.org/abs/1901.02393

    Pith/arXiv arXiv 2019

  6. [6]

    Farias, and Nikolaos Trichakis

    Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. The price of fairness.Oper. Res., 59(1):17–31, January 2011. ISSN 0030-364X. doi: 10.1287/opre.1100.0865. URL https://doi.org/10.1287/opre.1100.0865

    arXiv 2011

  7. [7]

    Advancing Subgroup Fairness via Sleeping Experts

    Avrim Blum and Thodoris Lykouris. Advancing Subgroup Fairness via Sleeping Experts. In Thomas Vidick, editor,11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 55:1– 55:24, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978...

    work page doi:10.4230/lipics.itcs.2020.55 2020

  8. [8]

    Nuanced metrics for measuring unintended bias with real data for text classification

    Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. InCompanion Proceedings of The 2019 World Wide Web Conference (WWW ’19 Companion), 2019. URL https://arxiv.org/abs/1903.04561

    Pith/arXiv arXiv 2019

  9. [9]

    An overview of fairness in clustering.IEEE Access, 9:130698–130720, 2021

    Anshuman Chhabra, Karina Masalkovait˙e, and Prasant Mohapatra. An overview of fairness in clustering.IEEE Access, 9:130698–130720, 2021. doi: 10.1109/ACCESS.2021.3114099

    arXiv 2021

  10. [10]

    Fair clustering through fairlets.Advances in neural information processing systems, 30, 2017

    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets.Advances in neural information processing systems, 30, 2017

    2017

  11. [11]

    Fair regression with wasserstein barycenters

    Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors,Advances in Neural Information Processing Systems, volume 33, pages 7321–7331. Curran Associates, Inc., 2020. URL https://proceedings.neurips. cc/pap...

    2020

  12. [12]

    Retiring adult: new datasets for fair machine learning

    Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: new datasets for fair machine learning. InProceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY , USA, 2021. Curran Associates Inc. ISBN 9781713845393. 10

    2021

  13. [13]

    Empirical risk minimization under fairness constraints

    Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. InAdvances in Neural Information Processing Systems, pages 2791–2801, 2018

    2018

  14. [14]

    Fair clustering under a bounded cost

    Seyedali Esmaeili, Behzad Nikbakht, Lunjia Ren, Jan V ondrák, and Morteza Zadimoghaddam. Fair clustering under a bounded cost. InAdvances in Neural Information Processing Systems, volume 34, pages 27679–27691, 2021. https://papers.neurips.cc/paper/2021/hash/ 781877bda0783aac5f1cf765c128b437-Abstract.html

    2021

  15. [15]

    Fair diffusion: Instructing text-to-image generation models on fairness.arXiv preprint arXiv:2302.10893, 2023

    Felix Friedrich, Manuel Brack, Lukas Struppek, Dominik Hintersdorf, Patrick Schramowski, Sasha Luccioni, and Kristian Kersting. Fair diffusion: Instructing text-to-image generation models on fairness.arXiv preprint arXiv:2302.10893, 2023

    Pith/arXiv arXiv 2023

  16. [16]

    Satisfying real-world goals with dataset constraints

    Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints. InAdvances in Neural Information Processing Systems, pages 2415–2423, 2016

    2016

  17. [17]

    right to explanation

    Bryce Goodman and Seth Flaxman. European union regulations on algorithmic decision-making and a “right to explanation”.AI magazine, 38(3):50–57, 2017

    2017

  18. [18]

    Deep residual learning for image recognition

    Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016

    2016

  19. [19]

    A sequentially fair mechanism for multiple sensitive attributes.Proceedings of the AAAI Conference on Artificial Intelligence, 38(11): 12502–12510, March 2024

    Francois Hu, Philipp Ratz, and Arthur Charpentier. A sequentially fair mechanism for multiple sensitive attributes.Proceedings of the AAAI Conference on Artificial Intelligence, 38(11): 12502–12510, March 2024. ISSN 2159-5399. doi: 10.1609/aaai.v38i11.29143. URL http: //dx.doi.org/10.1609/aaai.v38i11.29143

    work page doi:10.1609/aaai.v38i11.29143 2024

  20. [20]

    Clustering with size constraints.Studies in Computational Intelligence, 137, 01 2008

    Frank Höppner and Frank Klawonn. Clustering with size constraints.Studies in Computational Intelligence, 137, 01 2008. doi: 10.1007/978-3-540-79474-5_8

    work page doi:10.1007/978-3-540-79474-5_8 2008

  21. [21]

    An empirical study of rich subgroup fairness for machine learning, 2018

    Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup fairness for machine learning, 2018

    2018

  22. [22]

    Preventing fairness gerryman- dering: Auditing and learning for subgroup fairness

    Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerryman- dering: Auditing and learning for subgroup fairness. InInternational conference on machine learning, pages 2564–2572. PMLR, 2018

    2018

  23. [23]

    Slide: A surrogate fairness constraint to ensure fairness consistency.Neural Networks, 154:441–454, 2022

    Kunwoong Kim, Ilsang Ohn, Sara Kim, and Yongdai Kim. Slide: A surrogate fairness constraint to ensure fairness consistency.Neural Networks, 154:441–454, 2022. ISSN 0893-6080. doi: https://doi.org/10.1016/j.neunet.2022.07.027. URL https://www.sciencedirect.com/ science/article/pii/S0893608022002891

    work page doi:10.1016/j.neunet.2022.07.027 2022

  24. [24]

    Fairness through matching.Transactions on Machine Learning Research, 2025

    Kunwoong Kim, Insung Kong, Jongjin Lee, Minwoo Chae, Sangchul Park, and Yongdai Kim. Fairness through matching.Transactions on Machine Learning Research, 2025. ISSN 2835-

    2025

  25. [25]

    Fair clustering via align- ment

    Kunwoong Kim, Jihu Lee, Sangchul Park, and Yongdai Kim. Fair clustering via align- ment. InForty-second International Conference on Machine Learning, 2025. URL https: //openreview.net/forum?id=jImlK83NmV

    2025

  26. [26]

    Doubly- regressing approach for subgroup fairness, 2026

    Kunwoong Kim, Kyungseon Lee, Jihu Lee, Dongyoon Yang, and Yongdai Kim. Doubly- regressing approach for subgroup fairness, 2026. URL https://arxiv.org/abs/2510. 21091

    2026

  27. [27]

    Guarantees for spectral clustering with fairness constraints

    Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstern. Guarantees for spectral clustering with fairness constraints. InInternational conference on machine learning, pages 3458–3467. PMLR, 2019

    2019

  28. [28]

    FairICP: Encouraging equalized odds via inverse condi- tional permutation

    Yuheng Lai and Leying Guan. FairICP: Encouraging equalized odds via inverse condi- tional permutation. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors,Proceedings of 11 the 42nd International Conference on Machine Learning, volume 267 ofProceedings of Machine Learning R...

    2025

  29. [29]

    A survey on datasets for fairness-aware machine learning

    Tai Le Quy, Alice Roy, Johannes Friege, Siegfried Nijssen, Fritz Großarth, and Patrick Zschech. A survey on datasets for fairness-aware machine learning. arXiv preprint, 2022. URL https: //arxiv.org/abs/2202.04053

    Pith/arXiv arXiv 2022

  30. [30]

    Deep fair clustering for visual learning

    Peizhao Li, Han Zhao, and Hongfu Liu. Deep fair clustering for visual learning. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9070–9079, 2020

    2020

  31. [31]

    Deep learning face attributes in the wild

    Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. InProceedings of International Conference on Computer Vision (ICCV), December 2015

    2015

  32. [32]

    S. Lloyd. Least squares quantization in pcm.IEEE Transactions on Information Theory, 28(2): 129–137, 1982. doi: 10.1109/TIT.1982.1056489

    arXiv 1982

  33. [33]

    A survey on bias and fairness in machine learning.ACM computing surveys (CSUR), 54(6):1–35, 2021

    Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning.ACM computing surveys (CSUR), 54(6):1–35, 2021

    2021

  34. [34]

    Bounding and approximating intersectional fairness through marginal fairness, 2023

    Mathieu Molina and Patrick Loiseau. Bounding and approximating intersectional fairness through marginal fairness, 2023. URLhttps://arxiv.org/abs/2206.05828

    Pith/arXiv arXiv 2023

  35. [35]

    A data-driven approach to predict the success of bank telemarketing.Decision Support Systems, 62:22–31, 2014

    Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing.Decision Support Systems, 62:22–31, 2014. ISSN 0167-9236. doi: 10.1016/j.dss.2014.03.001. URL https://www.sciencedirect.com/science/article/ pii/S016792361400061X

    doi:10.1016/j.dss.2014.03.001 2014

  36. [36]

    A data-driven software tool for enabling cooperative information sharing among police departments.European Journal of Operational Research, 141(3):660–678, 2002

    Michael Redmond and Alok Baveja. A data-driven software tool for enabling cooperative information sharing among police departments.European Journal of Operational Research, 141(3):660–678, 2002

    2002

  37. [37]

    Sundaram

    Savitha Sam Abraham, Deepak Padmanabhan, and Sowmya S. Sundaram. Fairness in clustering with multiple sensitive attributes. InProceedings of the 23rd International Conference on Extending Database Technology (EDBT), pages 25–36, 2020. https://openproceedings. org/2020/conf/edbt/paper_148.pdf

    2020

  38. [38]

    Carreira-Perpiñán

    Weiran Wang and Miguel Á. Carreira-Perpiñán. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application, 2013. URL https://arxiv.org/ abs/1309.1541

    Pith/arXiv arXiv 2013

  39. [39]

    Fairgan: Fairness-aware generative adversarial networks

    Depeng Xu, Shuhan Yuan, Lu Zhang, and Xintao Wu. Fairgan: Fairness-aware generative adversarial networks. In2018 IEEE international conference on big data (big data), pages 570–575. IEEE, 2018

    2018

  40. [40]

    Deep fair clustering via maximizing and minimizing mutual information: Theory, algorithm and metric

    Pengxin Zeng, Yunfan Li, Peng Hu, Dezhong Peng, Jiancheng Lv, and Xi Peng. Deep fair clustering via maximizing and minimizing mutual information: Theory, algorithm and metric. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 23986–23995, 2023

    2023

  41. [41]

    Data clustering with size constraints.Knowledge- Based Systems, 23(8):883–889, 2010

    Shunzhi Zhu, Dingding Wang, and Tao Li. Data clustering with size constraints.Knowledge- Based Systems, 23(8):883–889, 2010. ISSN 0950-7051. doi: https://doi.org/10.1016/j. knosys.2010.06.003. URL https://www.sciencedirect.com/science/article/pii/ S095070511000095X

    doi:10.1016/j 2010

  42. [42]

    Variational fair clustering

    Imtiaz Masud Ziko, Jing Yuan, Eric Granger, and Ismail Ben Ayed. Variational fair clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11202–11209, 2021. 12 A Two motivating examples A.1 Necessity of the weightπ s We illustrate why the subgroup-size weight πs is necessary in the subgroup-fairness gap. The issue is...

    2021

  43. [44]

    # subgroups per attr

    requires computational complexity linear in n similarly to COVA-FC but the additional term due to the fairness constraint is nK2 q which becomes much larger than the additional term in COVA-FC that is n(K+ 2 q) when q is large. (ii) FairKM [37] includes a quadratic term O(n2Kd), which is substantially larger than first-order updates for large-scale datase...

    1994

  44. [45]

    Limitations

    is the standard ratio-based fairness measure but degenerates on datasets where some subgroup has fewer than K instances. We use a probability-ratio version of Balance, rather than the original count-ratio form, because the latter can depend strongly on subgroup-size ratios even under perfectly balanced cluster proportions. Using the notation of Sections 2...

  45. [46]

    Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects

    Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or ...

  46. [8856]

    URLhttps://openreview.net/forum?id=dHljjaNHh1