# A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 29 May 2021.

## Builds on (most cited first, 16 of 16)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Automated Experiments on Ad Privacy Settings: A Tale of Opacity, Choice, and Discrimination](https://mlsanity.com/paper/1408.6491/) (2014)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Fairness in Clustering with Multiple Sensitive Attributes](https://mlsanity.com/paper/1910.05113/) (2019)
- [A Notion of Individual Fairness for Clustering](https://mlsanity.com/paper/2006.04960/) (2020)
- [Variational Fair Clustering](https://mlsanity.com/paper/1906.08207/) (2019)

## Built on by (most cited first, 10 of 10)

- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [The Sharpe predictor for fairness in machine learning](https://mlsanity.com/paper/2108.06415/) (2021)
- [Convergence rates of the stochastic alternating algorithm for bi-objective optimization](https://mlsanity.com/paper/2203.10605/) (2022)
- [Fair Minimum Representation Clustering](https://mlsanity.com/paper/2302.03151/) (2023)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Incorporating Fairness in Neighborhood Graphs for Fair Spectral Clustering](https://mlsanity.com/paper/2512.09810/) (2025)
- [Fast and effective algorithms for fair clustering at scale](https://mlsanity.com/paper/2605.13759/) (2026)
- [Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimization](https://mlsanity.com/paper/2606.22433/) (2026)

## Abstract (arXiv)

In the application of data clustering to human-centric decision-making systems, such as loan applications and advertisement recommendations, the clustering outcome might discriminate against people across different demographic groups, leading to unfairness. A natural conflict occurs between the cost of clustering (in terms of distance to cluster centers) and the balance representation of all demographic groups across the clusters, leading to a bi-objective optimization problem that is nonconvex and nonsmooth. To determine the complete trade-off between these two competing goals, we design a novel stochastic alternating balance fair k-means (SAfairKM) algorithm, which consists of alternating classical mini-batch k-means updates and group swap updates. The number of k-means updates and the number of swap updates essentially parameterize the weight put on optimizing each objective function. Our numerical experiments show that the proposed SAfairKM algorithm is robust and computationally efficient in constructing well-spread and high-quality Pareto fronts both on synthetic and real datasets.