Covariance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering

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.