COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering

As machine learning systems are increasingly applied to diverse populations, ensuring fairness across multiple intersecting sensitive attributes (e.g., race and gender) has become critical. Traditional fair clustering algorithms often struggle with "subgroup fairness" because the number of subgroups grows exponentially with the number of sensitive attributes, leading to computational bottlenecks and numerical instability when dealing with sparse subgroups.

The authors introduce COVA-FC (COVAriance-based Fair Clustering). They first define a "subgroup-fairness gap" to quantify disparity and derive an exact, covariance-based surrogate for this gap. By relaxing the hard cluster assignments and the discrete subgroup selection into continuous forms, they transform the problem into a differentiable, gradient-based optimization task. This design allows for parallel updates of cluster assignments, significantly improving scalability compared to existing linear programming or penalty-based methods.

COVA-FC achieves competitive trade-offs between clustering cost and fairness across various benchmark datasets. The algorithm is particularly effective in settings with many sensitive attributes, where it avoids the cubic computational complexity associated with traditional linear programming approaches. Furthermore, the framework is flexible enough to incorporate "marginal fairness" (fairness for individual attributes) alongside subgroup fairness, ensuring that the model remains fair at both the granular and aggregate levels without incurring significant additional computational costs.

This work addresses a major practical limitation in algorithmic fairness: the inability to scale to complex, multi-attribute settings. By providing a numerically stable and efficient method for subgroup-fair clustering, the authors enable the deployment of fairer decision-making systems in real-world scenarios where intersectional bias is a significant concern.