acceptodds
Under review as a conference paper at ICLR 2027

Covariance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering

Abstract

Fair clustering aims to make cluster assignment independent of sensitive attributes, but this goal becomes challenging when multiple sensitive attributes jointly define many subgroups. In such cases, directly extending existing fair clustering algorithms can be 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 for efficient gradient-based optimization. The resulting algorithm, Cova-FC, has a first-order stationarity guarantee. We also show that a small subgroup-fairness gap 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
fair clustering, subgroup fairness, algorithmic fairness

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_eHZjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces COVA-FC, a surrogate-based approach to subgroup fair centroid-based clustering with multiple sensitive attributes. The authors define a subgroup-fairness gap and optimize a continuous relaxation of it together with the clustering cost in a covariance-based surrogate. COVA-FC is extended to account for subgroup and margin fairness simultaneously.

Critical strengths

S1: The paper proposes a covariance-based surrogate that they show exactly realizes the subgroup-fairness gap for any hard cluster assignment.

S2: The paper provides a detailed complexity analysis and runtime experiments.

Critical weaknesses

W1 (Context): Although the paper’s introduction discusses LP-based methods, VFC, and FairKM briefly, it lacks positioning within the broader context of related works. This includes the relation to other notions of fairness, e.g., group-level fair clustering methods, other clustering paradigms, or other works that target subgroup fairness. This makes it difficult to assess novelty.

W2 (Experiments / Rare Subgroups):

  • The paper identifies rare subgroups as one of the main limitations of current works. However, the experiments do not sufficiently isolate or test the algorithm on these specific scenarios, and it is not clear to me how the metric Δ(A)\Delta(A) reflects that, since it is weighted by the size of the subgroup πs\pi_s. Comparisons for the Communities dataset, which is the most interesting for the rare subgroups claim, are limited to the Appendix.
  • The reported metric in the main paper (supgroup fairness gap) is the quantity that COVA-FC optimizes, while the competitors optimize other objectives, which makes it difficult to separate algorithmic improvement from the experimental design. The gaps between the algorithms are often very small (0.0001 in Table 6), and it remains unclear to me how these differences relate to practical examples.
  • Table 2 compares only one competitor, excludes Communities, and uses L_2-normalized data. This raises the question of how other competitors perform in this setting and how much the preprocessing affects the results of the method.

Minor Comments:

  • Figure 2 is very small, making it difficult to read. Since there is enough space, I suggest adding the legend once at the top across all subplots and providing more space for the actual content.
Questions for authors

Q1: How can we interpret the very small differences, sometimes 0.0001, in the fairness metric (Table 6)? What difference would this make in practice?

Q2: How do the baselines compare regarding the subgroup-marginal fairness gap as they are?

Q3: How is the unfair clustering in the results determined? Is it a vanilla k-means clustering?

Q4: How do the results change across different values for K? The appendix includes results for K=5 and K=20, but only for COVA-FC and not for competitors, and are thus difficult to set into context.

4 comments

Weaknesses

[W1] Positioning within the broader related work.

  • We expanded the related work in Section 1. Fair clustering spans several paradigms (centroid-based, spectral, kernel, probabilistic, and deep), and fairness is imposed before clustering (e.g., fairlets), during it (penalties, as in FairKM, VFC, and ours), or after it (LP-based reassignment, as in FRA and FCBC). We also cover individual, social, and proportional fairness, and subgroup fairness, studied mainly in classification (e.g., Kearns et al., 2018).

[W2-1] Rare subgroups are not tested separately, and the size-weighted Δ(A)\Delta(A) may hide them.

  • Why size weighting is the default. Size weighting gives rare subgroups less weight, but a subgroup smaller than KK cannot appear in every cluster, so no method can close its gap (Gs≳2(K−ns)/KG_s\gtrsim 2(K-n_s)/K). A smaller α\alpha in the weight πsα\pi_s^\alpha gives rare subgroups more weight (results in Ewqn W1 above).

  • Rare-subgroup datasets. We test rare subgroups on Communities, where 886 of 1,180 subgroups have one instance and all baselines are now in the main text (Table 2, Figure 4), and on the added FairFace, whose smallest subgroup is 0.03% of the data. On both, Cova-FC keeps rare-subgroup gaps small, and a smaller α\alpha lowers them further; Reviewer Ewqn W1 above gives the table and results.

[W2-2] SP is Cova-FC’s own objective, and differences such as 0.0001 are tiny.

  • Other fairness metrics. Cova-FC also does well on Balance, which it does not optimize, attaining the highest SB on three of four datasets (VFmB W2 above).

  • Size of the differences. SP values are means over five random seeds with standard deviations of at most 0.0001 (Table 6), so these differences are not noise. They appear on Bank and Dutch, which have only three and four subgroups, where all methods do similarly. Cova-FC is designed for many subgroups, and there it leads clearly: Communities (1,180 subgroups; SP 0.0060 vs. at least 0.0094, Table R6), FairFace (126; 0.0017 vs. 0.0023), and CelebA (94; SP 0.1141 vs. 0.1299 among methods within the 2% cost budget; Table R1).

    Table R6: Comparison of clustering cost and SP on Communities. Mean ±\pm s.d.

    DatasetMethodCostSP
    CommunitiesUnfair57.25±0.234357.25\pm0.23430.0259±0.00260.0259\pm0.0026
    Cova-FC72.90±0.035572.90\pm0.03550.0060±0.0002\mathbf{0.0060}\pm0.0002
    FCBC81.68±0.468581.68\pm0.46850.0204±0.00280.0204\pm0.0028
    FairKM69.10±0.465069.10\pm0.46500.0094±0.00050.0094\pm0.0005
    FRA58.81±0.008258.81\pm0.00820.0223±0.00080.0223\pm0.0008
    VFC58.49±0.127358.49\pm0.12730.0200±0.00010.0200\pm0.0001

[Minor] Figure sizes. We increased the figure sizes for readability.

[W2-3] Table 2 has one competitor, no Communities, and uses normalized data.

  • Additional baselines. Table R7 (now Table 2) adds FRA, FairKM, FCBC, and Communities; Cova-FC attains the lowest SP on all five datasets.

  • Effect of normalization. Without it (Figure 3, Table 6), Cova-FC also attains the lowest SP on Adult (tied with FRA), Dutch, Civilcomments, and Bank.

Table R7: Comparison of SP and clustering cost on L2L_2-normalized data.

SP (Cost)

DatasetVFCFRAFairKMFCBCCova-FC
Adult0.01580.0158 (0.47)(0.47)0.00030.0003 (0.52)(0.52)0.02570.0257 (0.55)(0.55)0.00030.0003 (0.52)(0.52)0.0002\mathbf{0.0002} (0.50)(0.50)
Dutch0.01460.0146 (0.40)(0.40)0.00020.0002 (0.42)(0.42)0.02120.0212 (0.44)(0.44)0.00030.0003 (0.42)(0.42)0.0001\mathbf{0.0001} (0.42)(0.42)
Civilcomments0.00630.0063 (0.86)(0.86)0.00320.0032 (0.86)(0.86)0.02430.0243 (0.86)(0.86)0.00170.0017 (0.87)(0.87)0.0009\mathbf{0.0009} (0.90)(0.90)
Bank0.03540.0354 (0.24)(0.24)0.00040.0004 (0.28)(0.28)0.00000.0000 (0.37)(0.37)0.00030.0003 (0.28)(0.28)0.0000\mathbf{0.0000} (0.27)(0.27)
Communities0.02670.0267 (0.53)(0.53)0.02360.0236 (0.55)(0.55)0.00960.0096 (0.81)(0.81)0.03210.0321 (0.54)(0.54)0.0043\mathbf{0.0043} (0.62)(0.62)

Questions

[Q1] Practical meaning of a 0.0001 difference.

See Weakness 2-2.

[Q2] Baselines on marginal fairness gaps.

  • Section 5.3 now includes all baselines on Communities (Figure 4): our subgroup-only variant attains lower SP in most cases and the subgroup-marginal variant lower MP(1)\textup{MP}^{(1)} and MP(2)\textup{MP}^{(2)}, while VFC and FRA fail at strict levels and FCBC needs much higher cost. Appendix D.2 (Figure 5) covers the other datasets.

[Q3] What is the Unfair baseline?

  • The Unfair baseline is standard KK-means, as stated in Section 5.1 and Appendix D.1.

[Q4] Results for other KK with competitors.

  • We added all baselines on Adult at K=5,10,20K=5,10,20 (Appendix E.5, Figure 23); Cova-FC remains competitive for all three KK, with lower cost than FRA and FCBC at comparable SP.

Thank you for the rebuttal and the additional experiments, which resolved some of my concerns. However, some points remain.

(W2-2) SP is the quantity COVA-FC optimizes, while the baselines optimize different proxies. The Balance results are mixed: COVA-FC has the highest SB on three of four datasets and the highest whole-data ratio only on Adult. Since Figure 2 shows that COVA-FC needs higher cost than VFC, FRA, and FCBC at the same SB, I share VFmB's concern that part of the benefit comes from the aligned evaluation.

(Q1) My question about practical implications remains unanswered. I agree the standard deviations show the gaps are not noise, but it is still unclear what these gaps mean in practice when cost is taken into account, and what trade-off would be acceptable.

I will keep my scores.

Thank you very much for carefully reviewing our rebuttal and additional experiments, and for providing further feedback despite the short discussion period. Below, we provide clarifications on your remaining concerns.


(Reply - W2-2) SP is the quantity COVA-FC optimizes, while the baselines optimize different proxies. The Balance results are mixed: COVA-FC has the highest SB on three of four datasets and the highest whole-data ratio only on Adult. Since Figure 2 shows that COVA-FC needs higher cost than VFC, FRA, and FCBC at the same SB, I share VFmB's concern that part of the benefit comes from the aligned evaluation.

  • Shared concern with Reviewer VFmB. Since this concern is shared with Reviewer VFmB, we answer it in detail in our follow-up response to Reviewer VFmB (Reply - Q1). In short, the main benefit of Cova-FC is efficient optimization with many subgroups; the gap-based baselines optimize gaps of the same kind, and all these measures, including Balance, share the same fully fair solutions (Table R8); and most baselines are designed for one multi-category attribute, so we run them with each subgroup as a category, where they often reduce SP less.

  • Balance results. We agree that Cova-FC does not always achieve the best cost–Balance trade-off. In particular, FRA and FCBC can achieve the same SB at lower clustering cost in some settings (Figure 2), and slightly better SBprop\mathrm{SB}_{\mathrm{prop}} trade-offs on datasets other than Adult (Figure 8). With many small subgroups, Balance is unstable: a subgroup with fewer than KK members must miss some cluster and sets it to zero, and FRA, which imposes it, fails to solve its LP under strict constraints on Communities (Section 5.3); this is why SP is our main metric. Even so, Cova-FC achieves the highest subgroup Balance on Adult, Civilcomments, and Bank, despite not directly optimizing Balance.


(Reply - Q1) My question about practical implications remains unanswered. I agree the standard deviations show the gaps are not noise, but it is still unclear what these gaps mean in practice when cost is taken into account, and what trade-off would be acceptable.

  • Practical benefits of ours in presence of many subgroups. One of our main motivations and goals is to achieve high level of subgroup fairness more efficiently and stably, especially when the number of subgroups is large. On datasets with few subgroups, such as Dutch and Bank, the differences between Cova-FC and baselines can be small. However, these differences become more pronounced on Communities with 1,180 subgroups, where Cova-FC achieves SP 0.00600.0060, 0.00940.0094 for FairKM, 0.02000.0200 for VFC, 0.02040.0204 for FCBC, and 0.02230.0223 for FRA (Table R6). The advantage is thus largest with many subgroups: LP-based methods can take hours or fail under strict fairness (our follow-up response to Reviewer VFmB, Reply - Q1), whereas the runtime of Cova-FC on FairFace grows by only 3.5% from 8 to 126 subgroups (Reviewer Ewqn, Table R4).

  • Why the difference in SP is important in practice. SP measures how much the subgroup counts in each cluster differ from the expected counts: n⋅SP(A)=max⁡s∑k=1K∣ns,k−nspk∣n\cdot\mathrm{SP}(A)=\max_s\sum_{k=1}^K|n_{s,k}-n_sp_k|. For example, when n=60,000n=60{,}000, SP values of 0.00010.0001 and 0.00020.0002 correspond to total count discrepancies of 6 and 12, respectively, for the worst subgroup. Consider two clusters with equal expected proportions, i.e., p=(0.5,0.5)p=(0.5,0.5). For a subgroup of 20 individuals, assignments of (13,7)(13,7) and (16,4)(16,4) yield discrepancies of 6 and 12. In contrast, for a subgroup of 1,000 individuals, assignments of (503,497)(503,497) and (506,494)(506,494) yield the same discrepancies. Thus, even a small difference in SP can be practically significant for rare subgroups.

  • Main aim of fair clustering: achieving a good trade-off between clustering cost and fairness. Fair clustering aims to achieve fairness while preserving clustering quality (Chierichetti et al., 2017; Bera et al., 2019; Ziko et al., 2021; Esmaeili et al., 2021). For example, with K=2K=2, randomly assigning every instance the same soft assignment (0.5,0.5)(0.5,0.5) achieves perfect fairness, but ignores the underlying data structure and does not guarantee meaningful clusters. In practice, users can fix a required fairness violation ε\varepsilon and select the lowest-cost solution satisfying the threshold. For example, on Adult, Cova-FC and FRA both reach SP =0.0003=0.0003, at cost 2.522.52 and 2.892.89 (Table 6). For ε=0.0003\varepsilon=0.0003, both qualify, but Cova-FC has 12.8% lower clustering cost, indicating that it produces substantially better clustering. Thus, the practical benefit is not merely achieving a slightly lower SP, but attaining the desired fairness level while better preserving clustering quality.

Reviewer_EwqnOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates subgroup-fair clustering under multiple sensitive attributes, addressing the computational challenges and numerical instability arising from a large number of intersectional subgroups, particularly those with very few instances. The authors introduce a subgroup-fairness gap and derive an equivalent covariance-based formulation. Building on this formulation, they propose COVA-FC, which employs continuous relaxations and alternating gradient-based optimization, with a first-order stationarity guarantee. The framework is further extended to jointly consider subgroup and higher-order marginal fairness. Experiments on multiple benchmark datasets demonstrate competitive clustering cost-fairness trade-offs and improved computational efficiency compared with existing methods.

Critical strengths
  1. The paper addresses subgroup fairness under multiple sensitive attributes, considering the computational challenges and numerical instability caused by the increasing number of intersectional subgroups and their imbalanced sizes. The problem is well motivated and has practical significance.
  2. The covariance-based reformulation provides a unified framework for fair clustering, and the proposed optimization procedure is clear and reasonably supported by theoretical analysis. The experiments cover diverse datasets and demonstrate competitive cost-fairness trade-offs. The efficiency comparisons and ablation studies further support the effectiveness of the proposed approach.
Critical weaknesses
  1. The subgroup-fairness gap is weighted by subgroup proportions, which helps alleviate optimization difficulties but may also reduce the emphasis on rare subgroups. Consequently, a small overall fairness gap does not necessarily imply that all small subgroups are adequately protected. Although the authors discuss alternative weighting strategies in the appendix, a more comprehensive analysis of fairness across different subgroup sizes would strengthen the paper.
  2. The convergence analysis mainly establishes first-order stationarity for the continuous optimization problem, while the final clustering results rely on discrete assignments. The practical implications of this distinction could be further clarified. Additionally, the large-scale experiments primarily demonstrate scalability with respect to the number of instances, while the computational performance when both the dataset size and the number of subgroups increase remains less thoroughly investigated.
Questions for authors
  1. Since weighting by subgroup proportions may weaken the protection of rare subgroups, could the authors provide a more detailed analysis of fairness across different subgroup sizes? It would also be helpful to discuss how to balance numerical stability and fairness guarantees for underrepresented subgroups.
  2. The convergence analysis focuses on soft cluster assignments, while the final evaluation uses hard assignments obtained through argmax rounding. Although the authors provide a theoretical bound on the rounding gap, could they further clarify its practical tightness and discuss the potential effects when soft assignments are not sufficiently concentrated?
  3. The proposed method demonstrates promising efficiency on large-scale datasets. However, the number of subgroups in these experiments is relatively limited. Could the authors further discuss or evaluate the computational and memory costs when both the number of instances and the number of subgroups increase simultaneously?
  4. The paper could benefit from a broader discussion of recent advances in fair clustering. I suggest considering additional relevant studies, such as [1–3], which investigate fairness-aware kernel clustering, probabilistic soft clustering, and scalable model-based clustering, respectively. Discussing their connections to and differences from the proposed approach could help better position the contributions of this work.

[1] Zhou, P., Li, R., & Du, L. (2024). Fair Kernel K-Means: from Single Kernel to Multiple Kernel. Advances in Neural Information Processing Systems (NeurIPS), 37.

[2] Kjærsgaard, R. D., Parviainen, P., Saurabh, S., Kundu, M., & Clemmensen, L. (2024). Fair Soft Clustering. Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), Proceedings of Machine Learning Research, 238, 1270–1278.

[3] Park, J., Kim, K., Lee, J., & Kim, Y. (2026). Fair Model-based Clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 40(29), 24773–24781.

3 comments

Weaknesses

[W1] Size weighting may under-protect rare subgroups; analyze fairness by subgroup size. Cova-FC also keeps the gaps of rare subgroups small, and they can be lowered further by weighting each gap by πsα\pi_s^\alpha with a smaller α\alpha (α=1\alpha=1: SP). We show this with two experiments on the gap before size weighting (GsG_s).

  • Rare subgroups on Adult and Communities (Appendix E.1, Figure 13). At the same SP, Cova-FC roughly halves the gaps in six of seven subgroup-size bins compared with the gap algorithm (e.g., 0.26 vs. 0.59 on Adult). It also reaches a lower SP than the gap algorithm can, and there the gaps in all seven bins on Adult are at most about 0.05.

  • Subgroup-size bins on FairFace (Table R3). We weight each subgroup’s gap by πsα\pi_s^\alpha (α=1\alpha=1: SP; α=0\alpha=0: equal weights) and group the 126 subgroups into 13 size bins. With α=0\alpha=0, the gaps are lowest in the seven smallest bins (0.22 vs. 0.77 at α=1\alpha=1 for 27–74 members), while SP rises only to 0.0072, still below FRA, FCBC, and VFC (Table R1). With α=1\alpha=1, SP is lowest (0.0017), and the gaps are lowest in the five largest bins.

  • Choosing α\alpha. Appendix E.4 gives a grid-search rule: among values of α\alpha for which the penalty is not dominated by a tiny subgroup, we choose the one with the smallest total gap over large subgroups.

Table R3: Comparison of the median unweighted gap GsG_s of Cova-FC by subgroup size nsn_s on FairFace for different α\alpha, at the lowest SP within 2% of the Unfair cost.

α=0\alpha=0α=14\alpha=\frac14α=12\alpha=\frac12α=1\alpha=1
Cost433.89433.73432.96433.26
SP0.00720.00470.00350.0017
nsn_smedian GsG_s
27–740.220.380.720.77
81–1040.200.320.570.89
106–1780.190.280.470.82
183–2460.190.260.390.51
255–4010.180.220.280.36
415–5400.180.210.250.28
579–7150.180.190.210.21
736–7820.180.180.200.18
789–9450.190.180.190.16
947–11980.190.170.170.14
1236–14870.180.160.150.11
1534–19870.180.150.130.08
2011–33320.190.140.120.07

[W2] What stationarity of the soft problem means for the final hard clustering; scaling in both nn and MM.

  • Effect of rounding. All results use the rounded hard assignments. Propositions B.1–B.2 bound the change in SP by 2γ2\gamma, with γ=1n∑i(1−max⁡kA~ik)\gamma=\frac 1n\sum_i(1-\max_k\tilde A_{ik}); the observed rounding change is at most 0.00140.0014 (Table R5) and below the bound for every fairness penalty constant λ\lambda (Appendix E.3).

  • Spread-out assignments loosen the bound. γ\gamma grows and the bound loosens, but most instances put nearly all their weight on one cluster (Adult, λ=10\lambda=10: 2γ=0.03612\gamma=0.0361 vs. an actual 0.00140.0014) (Appendix E.3, Figure 16).

  • Scaling in both nn and M+M_+. The per-iteration complexity of Cova-FC is O(nK(d+log⁡K)+KM+log⁡(KM+))O(nK(d+\log K)+KM_+\log(KM_+)), and the memory complexity is O(n(d+K)+KM+)O(n(d+K)+KM_+). Thus, the costs involving nn and M+M_+ are additive rather than multiplicative. To address this concern, we added a 5×55\times5 runtime and memory experiment on FairFace (n=97,698n=97{,}698, M+=126M_+=126), varying nn and M+M_+ independently (Table R4). For example, at M+=8M_+=8, increasing nn from 6,106 to 97,698 increases runtime from 49.16 to 377.65 seconds and peak GPU allocated memory from 68.79 to 809.51 MiB. In contrast, at n=97,698n=97{,}698, increasing M+M_+ from 8 to 126 increases runtime only from 377.65 to 390.89 seconds, while peak GPU allocated memory remains nearly unchanged (809.51 vs. 809.53 MiB). These results are consistent with our complexity analysis (Table 1) and are included in the revised manuscript (Appendix D.5, Table 10).

Table R4: Runtime (sec) / peak GPU allocated memory (MiB) of Cova-FC on FairFace with varying nn and M+M_+.

nn / M+M_+8163263126
6,10649.16 / 68.7951.78 / 68.7955.73 / 68.8059.65 / 68.8061.10 / 68.81
12,21273.49 / 108.8577.61 / 108.8578.13 / 108.8582.27 / 108.8686.86 / 108.87
24,424112.74 / 209.51114.36 / 209.51122.68 / 209.51123.34 / 209.52127.30 / 209.53
48,849196.50 / 409.64203.72 / 409.64203.94 / 409.65210.37 / 409.65216.07 / 409.66
97,698377.65 / 809.51381.03 / 809.51380.59 / 809.52384.95 / 809.52390.89 / 809.53

Table R5: Comparison of the change from the soft gap to SP after argmax rounding, diff:=∥Δ(A^)−CR‾(A~)∥\mathrm{diff}:=\|\Delta(\hat{\mathbf A})-\overline{\textup{CR}}(\tilde{\mathbf A})\|, with its theoretical bound 2γ(A~)2\gamma(\tilde{\mathbf A}) on Adult and Dutch, where A^\hat{\mathbf A} assigns each instance to its most likely cluster under A~\tilde{\mathbf A} and γ(A~)=1n∑i=1n(1−max⁡kA~ik)\gamma(\tilde{\mathbf A})=\frac 1n\sum_{i=1}^n(1-\max_k\tilde A_{ik}).

Datasetλ\lambdaΔ(A^)\Delta(\hat{A})CR‾(A~)\overline{\mathrm{CR}}(\tilde{A})diff\mathrm{diff}2γ(A~)2\gamma(\tilde{A})
Adult100.00930.00790.00140.0361
400.00110.00090.00020.0111
700.00020.00010.00020.0015
Dutch70.02420.02360.00060.0020
150.01880.01870.00020.0009
400.00030.00010.00020.0007

Questions

[Q1] Fairness by subgroup size, and stability versus protection of rare subgroups.

See Weakness 1 above.

[Q2] How tight is the rounding bound, and what if assignments are spread out?

See Weakness 2 above.

[Q3] Cost when nn and MM grow together.

See Weakness 2 above.

[Q4] Discuss and position against FKKM, Fair Soft Clustering, and FMC.

  • Different clustering paradigms. Cova-FC and our main baselines are centroid-based, whereas FKKM is a kernel method and Fair Soft Clustering and FMC are probabilistic. We added them to the related work (Section 1) and compared Cova-FC with the two we could run, FKKM and FMC, treating each subgroup as a group (Appendix D.4).

  • Fair Soft Clustering. We could not run it, since its minimum-cost-flow construction of fairlets handles only two protected groups.

  • Cova-FC has similar or lower cost than FKKM and FMC. Cova-FC has cost lower than or similar to that of FKKM at most SP levels and lower cost than FMC, which stays above SP 0.029, on five datasets (Appendix D.4, Figure 9).


Thank you for the reviewer's response. I believe my concerns have been addressed. I will maintain my score.

Reviewer_VFmBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates the fair clustering problem based on subgroups defined by combinations of sensitive groups (e.g., black and female vs black and male etc.). While fair clustering has been extensively studied in the literature, the number of subgroups grows quickly with the number of sensitive groups, which is a challenge for scalability. The paper proposes COVA-FC, which optimizes a continous relaxation of a covariance-based surrogate for the fairness over subgroups and is more convenient for optimization as it allows per-instance assignment updates. COVA-FC applies projected gradient descent to optimize a combination of the k-means objective and a cluster-size-weighted subgroup fairness loss. The experiments compare COVA-FC against five baselines using seven datasets with numbers of protected groups varying from 3 to 1,180. The results show that the proposed solution achieves a better cost-fairness tradeoff than the baselines. Moreover, COVA-CF achieves similar or lower running time than the baselines.

Critical strengths

S1) The paper is well-written and easy to follow.

S2) The proposed solution achieves better cost-fairness trade-off than the baselines.

S3) The proposed solution is intuitive and sound.

Critical weaknesses

W1) The paper combines multiple known results (covariance formulation for fairness, continuous fair clustering, convergence guarantees for block alternating proximal-gradient). I believe that the novelty of the paper should stated more clearly in the context of previous work. For instance, the novelty of Theorem 2.1 is unclear.

W2) The evaluation applies the same group-size-weighted objective as the proposed method, but it is not clear if the baselines apply the same objective. It seems unfair to the baselines to use a different evaluation metric.

W3) COVA-FC is not compared against a continuous relaxation of the original fairness objective (instead of the covariance-based one). It is unclear to me why projected gradient descent cannot be applied to the relaxed original objective.

W4) Limited experiments for large number of protected subgroups. Intuitively, the main motivation for the proposed solution is handling large numbers of protected subgroups, but the scalability experiment in Table 3 applies the Dutch dataset only (two sensitive attributes).

W5) The following paper seems relevant and should be discussed in the related work: Chakraborty et al., Generalizing Fair Clustering to Multiple Groups: Algorithms and Applications (AAAI 2026).

Questions for authors

Q1) Can you provide a more accurate statement of the novelty of the paper compared to previous work?

Q2) How is the evaluation impacted by the fact that the proposed method uses the same objective as the one in the evaluation but that is not necessarily the case for the baselines?

Q3) Why a continuous relaxation of the original objective is not a good solution for the problem? Can it be evaluated against the proposed solution?

5 comments

Weakness


W1W1 What is new, especially in Theorem 2.1?

Our penalty equals SP exactly and weights all subgroups at once, which keeps optimization stable with many subgroups and allows mini-batch training.

  • The penalty equals SP exactly. Prior covariance-based methods (e.g., Zafar et al., 2017) use covariance as a fairness surrogate, so reducing it need not reduce the fairness gap. With subgroup weights v\mathbf v and signed cluster weights β\boldsymbol\beta, our penalty equals SP exactly (Theorems 2.1–2.2).
  • All subgroups are weighted at once. The gap algorithm reduces only the largest gap at each step, and LP-based methods (FRA, FCBC) need a constraint per subgroup–cluster pair. Our penalty weights all subgroups through the adversarial variable UU, a matrix in the convex hull of vβ⊤\mathbf v\boldsymbol\beta^\top (Section 4), which keeps optimization stable (W3).
  • Updates split over instances, so mini-batches work. With UU and the centroids fixed, the penalty is a sum of per-instance terms, each depending only on that instance’s assignment. Instances can thus be updated in parallel or one mini-batch at a time, which LP-based methods, FairKM, and FKKM cannot do. On Adult, mini-batches give nearly the same cost–SP trade-off as the full batch (Figure 25; Appendix E.6).
  • Convergence and rounding are guaranteed. The block alternating proximal-gradient method reaches an ε\varepsilon-stationary point in O(ε−4)O(\varepsilon^{-4}) iterations (Theorem B.5), and Propositions B.1–B.2 bound how much SP changes when the soft assignments are rounded.

W2W2 SP is what Cova-FC optimizes, so it may favor Cova-FC.

  • No baseline optimizes SP. VFC uses a KL penalty, FairKM squared deviations, and FRA and FCBC proportion bounds per cluster.
  • Cova-FC also does well on Balance, which it does not optimize. Now in the main text (Figure 2). Cova-FC attains the highest SB (the smallest ratio of two subgroups’ shares in a cluster) on Adult, Civilcomments, and Bank, and the highest SBprop\textup{SB}_{\textup{prop}} (the same ratio against the whole data) on Adult, while FRA and FCBC, which constrain it directly, are slightly better elsewhere (Appendix D.2).
  • Image datasets with many subgroups. On FairFace (126 subgroups) and CelebA (94) with ResNet-18 features, Cova-FC attains the lowest SP within 2% of the Unfair cost (Table R1, Appendix D.6).

Table R1: Clustering cost and SP on the image datasets. Each method uses the setting with the lowest SP whose cost is within 2% of the Unfair cost. On CelebA, FRA has no setting within this budget, so we report its lowest-cost setting. Mean ±\pm s.d.

DatasetMethodCostSP
FairFace (126)Unfair428.36±0.01428.36\pm0.010.0205±0.00020.0205\pm0.0002
VFC428.38±0.02428.38\pm0.020.0204±0.00060.0204\pm0.0006
FRA434.64±0.01434.64\pm0.010.0106±0.00020.0106\pm0.0002
FCBC435.99±0.01435.99\pm0.010.0107±0.00020.0107\pm0.0002
FairKM433.92±0.01433.92\pm0.010.0043±0.00000.0043\pm0.0000
FKKM436.07±0.02436.07\pm0.020.0023±0.00010.0023\pm0.0001
FMC434.08±0.26434.08\pm0.260.0106±0.00020.0106\pm0.0002
Cova-FC433.26±0.03433.26\pm0.030.0017±0.0000\mathbf{0.0017}\pm0.0000
CelebA (94)Unfair426.61±0.00426.61\pm0.000.2106±0.00040.2106\pm0.0004
VFC426.68±0.14426.68\pm0.140.2120±0.00430.2120\pm0.0043
FRA438.51±0.01438.51\pm0.010.1138±0.00020.1138\pm0.0002
FCBC431.82±0.01431.82\pm0.010.1837±0.00040.1837\pm0.0004
FairKM430.00±0.00430.00\pm0.000.1299±0.00000.1299\pm0.0000
FKKM428.25±0.00428.25\pm0.000.1456±0.00000.1456\pm0.0000
FMC433.41±1.06433.41\pm1.060.1798±0.01050.1798\pm0.0105
Cova-FC429.30±0.00429.30\pm0.000.1141±0.0001\mathbf{0.1141}\pm0.0001
  • CelebA cost-budget comparison. FRA achieves a slightly lower SP than Cova-FC (0.1138 vs. 0.1141), but its lowest-cost setting exceeds the 2% budget, with a 2.8% cost increase over Unfair, compared with only 0.6% for Cova-FC.

W3W3 Why not apply projected gradient descent to the soft gap?

  • Thank you. The gap algorithm can be applied to this problem, but it is hard to use on real data because it is unstable and slow. We added this comparison as Appendix E.1 and revised the motivation of the surrogate penalty in Section 2.2. The soft gap equals our penalty (Theorem 2.2), so the two differ only in optimization: with UU fixed, our objective is linear in the assignments, so Cova-FC uses projected gradient descent instead of subgradient steps.
  • Both have convergence guarantees, but ours is more stable. Cova-FC reaches an ε\varepsilon-stationary iterate in O(ε−4)O(\varepsilon^{-4}) iterations (Theorem B.5), while the gap algorithm can reach near-stationarity under suitable conditions (Davis & Drusvyatskiy, 2019). In practice, the gap algorithm also oscillates more and reduces SP less consistently at large λ\lambda (Figures 11–12).
  • Why the gap algorithm stops reducing SP. Each step of the gap algorithm reduces only the worst subgroup’s gap; the other subgroups follow only the cost, so their gaps can grow. The worst subgroup therefore keeps changing even near convergence, and at large λ\lambda the loss oscillates instead of SP decreasing. In Cova-FC, UU concentrates on one worst subgroup over iterations but keeps small weights on the others, so their gaps do not grow and SP decreases stably (Figure 24; Appendix E.6).
  • Computational efficiency. Under the same stopping rule (Appendix E.1) and at the same SP and cost, Cova-FC is 1.55×1.55\times, 2.15×2.15\times, and 3.14×3.14\times faster on Adult, Civilcomments, and Communities, with 1.51.5–3.7×3.7\times fewer iterations (Table R2).

Table R2: Comparison of the gap algorithm on Δ(A~)\Delta(\tilde{\mathbf A}) and Cova-FC on CR‾\overline{\mathrm{CR}} in terms of cost, SP, iteration count, and runtime. Parentheses show the speedup of Cova-FC.

Dataset (# Subgroups)VariantCostSPIteration / Runtime (sec)
Adult (16)Δ(A~)\Delta(\tilde{A})2.110.006520,386 / 69.04
CR‾\overline{\mathrm{CR}}2.100.006613,254 / 44.64 (×1.55\times 1.55)
Civilcomments (24)Δ(A~)\Delta(\tilde{A})645.750.007421,005 / 54.48
CR‾\overline{\mathrm{CR}}645.660.00728,543 / 25.32 (×2.15\times 2.15)
Communities (1180)Δ(A~)\Delta(\tilde{A})58.210.010020,352 / 62.32
CR‾\overline{\mathrm{CR}}58.200.01005,476 / 19.82 (×3.14\times 3.14)
  • Strength for rare subgroups. Because UU keeps weights on non-worst subgroups, Cova-FC also reduces rare-subgroup gaps. On Adult at the same SP, the unweighted gap GsG_s is about half that of the gap algorithm in six of seven subgroup-size bins. Communities shows a similar pattern (Appendix E.1, Figure 13).

W4W4 Scalability is tested only on Dutch, which has few subgroups.

  • Scaling with the number of subgroups. We added a runtime and memory experiment on FairFace (n=97,698n=97{,}698, M+=126M_+=126), varying M+M_+ from 8 to 126. At fixed nn, runtime increases only from 377.65 to 390.89 seconds, while peak GPU allocated memory remains nearly unchanged (809.51 vs. 809.53 MiB). We also vary both nn and M+M_+ independently over 25 settings, addressing joint scaling of instance and subgroup counts (Appendix D.5, Table 10).

W5W5 Discuss Chakraborty et al. (AAAI 2026).

  • We added it to the related work (Section 1, Appendix D.4). It makes every cluster match the overall group proportions exactly, so KK cannot exceed the greatest common divisor of the subgroup sizes, which is 1 with many subgroups (e.g., 17, 48, 56, 57) or any single-instance subgroup; we therefore exclude it.

Questions

Q1Q1 Clearer statement of novelty.

See Weakness 1 above.

Q2Q2 Effect of evaluating with Cova-FC’s own objective.

See Weakness 2 above.

Q3Q3 Comparison with the gap algorithm on the soft gap.

See Weakness 3 above.

Reviewer_VFmBOpenReview ↗

Response to the rebuttal

Thanks for submitting the rebuttal. What I think has improved based on the response to my comments: description of the contributions and experimental results. What seems to confirm my early concerns: (1) main benefit of Cova-FC over baselines seems to be the different objective and aligned evaluation, (2) the new results on image datasets do not show a big advantage for Cova-FC, but it hard to see because they are not shown as a tradeoff as done for earlier experiments, (3) the new variant discussed in Appendix E1 looks pretty competitive for the scale of datasets considered in the paper, maybe the best baseline.

Please let me know if I misunderstood any of these. I am doing my best to process all the new results and updates in the paper in a short time window.

Comments on the paper

1 comment

Response to Common Reviewer Concerns


Terms and conventions

  • Notation: nn instances with dd features, KK clusters, and MM observed subgroups; subgroup ss has nsn_s instances and share πs=ns/n\pi_s=n_s/n; pkp_k and pk∣sp_{k\mid s} are the shares of all instances and of subgroup ss in cluster kk; Gs=∑k∥pk−pk∣s∥G_s=\sum_k\|p_k-p_{k\mid s}\| is the unweighted gap, so SP=max⁡sπsGs\textup{SP}=\max_s\pi_sG_s.

  • SP (hard gap): Δ(A)=max⁡sπs∑k∥pk−pk∣s∥\Delta(\mathbf A)=\max_{\boldsymbol s}\pi_{\boldsymbol s}\sum_k\|p_k-p_{k\mid\boldsymbol s}\| on hard assignments (“subgroup-fairness gap”, “Δ(A)\Delta(A)”). Soft gap: Δ(A~)\Delta(\tilde{\mathbf A}) on soft assignments (“relaxed original objective”), equal to our penalty CR‾\overline{\textup{CR}} (Theorem 2.2).

  • Gap algorithm: projected subgradient descent on the soft gap (“direct optimization” in Appendix E.1, “Gap Penalty” in Figure 13).

  • Unless noted otherwise, results use K=10K=10, are means over five seeds, and are computed on hard assignments. Section, Appendix, Figure, and Table numbers refer to the revised manuscript (changes in blue); tables and figures in this response are numbered R1, R2, and so on.


A Exact fairness penalty and optimization

  • Our penalty equals SP exactly and weights all subgroups instead of the worst one, so optimization is stable, fast, and possible on mini-batches (VFmB W1, W3).

B Evaluation beyond the optimized gap

  • Balance moves to the main text; we add kernel and model-based methods (FKKM, FMC) and two image datasets with 94 and 126 subgroups (VFmB W2, Ewqn Q4, eHZj W2-2).

C Scaling with subgroup count

  • Per-iteration cost is additive in nn and MM, and mini-batches remove the dependence on nn (VFmB W4, Ewqn Q3).

D Rare subgroups and weighting

  • With α=0\alpha=0 (equal weights in πsα\pi_s^\alpha), the median gap for the smallest FairFace subgroup-size bin drops from 0.77 to 0.22, while SP rises only to 0.0072 (0.22 vs.\ 0.37 for FCBC; Appendix~E.4, Table~16).

E From soft to hard assignments

  • Rounding changes SP by at most 0.00140.0014, within our bound (Ewqn W2).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.