# COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering

arXiv: https://arxiv.org/abs/2607.18119 · HTML: https://mlsanity.com/paper/2607.18119/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 49 references that are in the map.
- First posted on arXiv 20 Jul 2026.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Nuanced Metrics for Measuring Unintended Bias with Real Data for Text Classification](https://mlsanity.com/paper/1903.04561/) (2019)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [European Union regulations on algorithmic decision-making and a "right to explanation"](https://mlsanity.com/paper/1606.08813/) (2016)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Regression: Quantitative Definitions and Reduction-based Algorithms](https://mlsanity.com/paper/1905.12843/) (2019)
- [FairGAN: Fairness-aware Generative Adversarial Networks](https://mlsanity.com/paper/1805.11202/) (2018)
- [A survey on datasets for fairness-aware machine learning](https://mlsanity.com/paper/2110.00530/) (2021)
- [Fair Diffusion: Instructing Text-to-Image Generation Models on Fairness](https://mlsanity.com/paper/2302.10893/) (2023)
- [Fair Regression with Wasserstein Barycenters](https://mlsanity.com/paper/2006.07286/) (2020)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [An Empirical Study of Rich Subgroup Fairness for Machine Learning](https://mlsanity.com/paper/1808.08166/) (2018)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Satisfying Real-world Goals with Dataset Constraints](https://mlsanity.com/paper/1606.07558/) (2016)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [Fairness in Clustering with Multiple Sensitive Attributes](https://mlsanity.com/paper/1910.05113/) (2019)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metric](https://mlsanity.com/paper/2209.12396/) (2022)
- [Bounding and Approximating Intersectional Fairness through Marginal Fairness](https://mlsanity.com/paper/2206.05828/) (2022)
- [A Sequentially Fair Mechanism for Multiple Sensitive Attributes](https://mlsanity.com/paper/2309.06627/) (2023)
- [Fairness Through Matching](https://mlsanity.com/paper/2501.02793/) (2025)
- [FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation](https://mlsanity.com/paper/2404.05678/) (2024)
- [SLIDE: a surrogate fairness constraint to ensure fairness consistency](https://mlsanity.com/paper/2202.03165/) (2022)

## Abstract (arXiv)

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.