ArXiv

COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering

2026-07-20 · 16:14 UTC ·Kyungseon Lee, Hankyo Jeong, Kunwoong Kim... ·1 min read
Authors
Kyungseon Lee, Hankyo Jeong, Kunwoong Kim...
Categories
stat.ML, cs.LG
arXiv
https://arxiv.org/abs/2607.18119v1
PDF
https://arxiv.org/pdf/2607.18119v1

Brief

The paper addresses fair clustering when multiple sensitive attributes create many small subgroups. It defines a subgroup-fairness gap and constructs a covariance-based surrogate that exactly matches it, then applies a continuous relaxation for gradient-based optimization to produce COVA-FC. The authors also show subgroup fairness does not guarantee marginal fairness, extend the method to subgroup–marginal gaps, and report competitive cost–fairness trade-offs with faster computation versus prior baselines on benchmark datasets.

Why it matters

Defines a subgroup-fairness gap for clustering and derives a covariance-based surrogate that exactly matches this gap; introduces a continuous relaxation enabling gradient-based optimization and the algorithm COVA-FC (Lee et al., arXiv:2607.18119v1, 2026-07-20).

Key details

  • Targets settings with many sensitive attributes where subgroups grow exponentially and some subgroups have very few instances, causing existing methods to be computationally expensive or numerically unstable.
  • Proves subgroup fairness need not imply marginal fairness and extends the framework to a subgroup–marginal-fairness gap; experiments on benchmark datasets report competitive cost–fairness trade-offs and improved computational efficiency over prior baselines in both subgroup and higher-order marginal scenarios.
Source evidence

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.