COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering
2026-07-20 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study fair clustering, which aims to group data points without bias toward sensitive features like race or gender. They focus on cases where many combined sensitive traits create lots of small subgroups, making fairness hard to achieve without heavy computation. To solve this, the authors create a new mathematical formula that measures fairness gaps and develop an algorithm called COVA-FC that can optimize fairness efficiently. Their experiments show COVA-FC works well while being faster than existing methods, and they also show how to handle fairness both within subgroups and across individual sensitive attributes.
fair clusteringsensitive attributessubgroup fairnesscovariancegradient-based optimizationcontinuous relaxationmarginal fairnessalgorithm efficiencycost-fairness trade-offbenchmark datasets
Authors
Kyungseon Lee, Hankyo Jeong, Kunwoong Kim, Kwanho Lee, Yongdai Kim
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.