Source-linked AI summary
Coresets for Clustering with Fairness Constraints
Lingxiao Huang, Shaofeng H. -C. Jiang, Nisheeth K. Vishnoi
TL;DR
Fair clustering needs to handle multiple, non-disjoint sensitive types, while existing approaches have faced scalability and coreset-coverage gaps. This paper constructs n-independent coresets for fair k-median and k-means, then uses them with existing algorithms. The reported experiments show substantial speedups, including on a dataset with 2.5 million records.
Problem
Prior fair coresets covered only k-means, included a log n size factor, and handled one sensitive type; no fair k-median coreset was known.
Source: §1 · p. 3Method
Results
Takeaways & Limitations
With ε = Ω(1), plugging the coresets into existing algorithms [39, 6, 5] yields scalable fair-clustering algorithms at an additional (1 + ε) approximation factor.
Source: §1 · p. 4The paper leaves open sampling-based fair coresets with non-exponential dimension dependence and coresets for general fair (k, z)-clustering.
Source: §7 · p. 23
Abstract
from arXiv · showhide
In a recent work, [19] studied the following "fair" variants of classical clustering problems such as $k$-means and $k$-median: given a set of $n$ data points in $\mathbb{R}^d$ and a binary type associated to each data point, the goal is to cluster the points while ensuring that the proportion of each type in each cluster is roughly the same as its underlying proportion. Subsequent work has focused on either extending this setting to when each data point has multiple, non-disjoint sensitive types such as race and gender [6], or to address the problem that the clustering algorithms in the above work do not scale well. The main contribution of this paper is an approach to clustering with fairness constraints that involve multiple, non-disjoint types, that is also scalable. Our approach is based on novel constructions of coresets: for the $k$-median objective, we construct an $\varepsilon$-coreset of size $O(\Gamma k^2 \varepsilon^{-d})$ where $\Gamma$ is the number of distinct collections of groups that a point may belong to, and for the $k$-means objective, we show how to construct an $\varepsilon$-coreset of size $O(\Gamma k^3\varepsilon^{-d-1})$. The former result is the first known coreset construction for the fair clustering problem with the $k$-median objective, and the latter result removes the dependence on the size of the full dataset as in [39] and generalizes it to multiple, non-disjoint types. Plugging our coresets into existing algorithms for fair clustering such as [5] results in the fastest algorithms for several cases. Empirically, we assess our approach over the \textbf{Adult}, \textbf{Bank}, \textbf{Diabetes} and \textbf{Athlete} dataset, and show that the coreset sizes are much smaller than the full dataset. We also achieve a speed-up to recent fair clustering algorithms [5,6] by incorporating our coreset construction.
1 Introduction
The paper addresses the lack of scalable coresets for fair clustering with multiple, non-disjoint types, and reports substantially faster fair-clustering algorithms when its coresets are used. It also reviews related fair-clustering algorithms and coreset constructions.
1 Introduction
- Earlier fair-clustering algorithms may require at least quadratic time, and prior fair coresets were limited to k-means with a log n size factor and one sensitive type; no k-median coreset was known.The paper situates its contributions against work on multiple non-disjoint sensitive types and poor scalability.Source: §1 · p. 3
- The paper constructs n-independent ε-coresets for multiple, non-disjoint types, with sizes O(Γk^2ε^-d) for fair k-median and O(Γk^3ε^-d-1) for fair k-means.Γ counts the distinct collections of groups to which a point may belong.Source: §1 · pp. 3–4
- A general reduction divides points into Γ membership-pattern parts and applies a Γ = 1 construction to each, while geometric observations support that case.The reduction is stated to apply to all coreset constructions; experiments cover Adult, Bank, Diabetes, and Athlete.Source: §1 · p. 4
- Approximately 5–15× speedups for [5] and 15–30× for [6] are reported across the stated datasets, including Census1990, even counting coreset construction.For fair k-median, 5% empirical error used 3% of the original data; for k-means, similar error used 20%.Source: §1 · p. 4
1.1 Other related works
- Prior fair-clustering work includes algorithms for binary types and broader group structures, while near-linear O(1)-approximation for fair (k, z)-clustering remains open.The related work also covers alternative fairness formulations and unconstrained clustering coresets.Source: §1.1 · pp. 4–6
2 Problem definition
The section defines fair clustering through assignment constraints on group counts and defines a coreset as a weighted proxy preserving constrained clustering costs. It relates proportional-fairness conditions to those constraints and states that the coreset guarantee transfers to that setting.
2 Problem definition
- A clustering satisfies assignment constraint F when each cluster Ci contains exactly Fij points from group Pj.The constrained objective minimizes total clustering cost over assignments satisfying F; if none exists, its value is infinity.Source: §2 · p. 6
- An ε-coreset is a weighted point set whose constrained clustering value approximates the full data value for every center set and assignment constraint.Points in the weighted set may be partially assigned across clusters in proportion to their weight.Source: §2 · p. 6
- Proportional fairness bounds each group’s proportion in every cluster, and such restrictions can be modeled as assignment constraints.Consequently, an ε-coreset preserves the proportionally fair clustering value within a (1 ± ε) factor.Source: §2 · pp. 6–7
- The section also defines count-based fairness through lower and upper bounds on each group’s cluster count, for which the same coreset-preservation result applies.A stated example requires at least one member of every group in every cluster.Source: §2 · p. 7
3 Technical overview
The technical overview reduces the multiple-membership setting to Γ = 1, then adapts a line-based coreset framework using structural properties of optimal fair clusters. The cluster structure differs between fair k-median and fair k-means.
3 Technical overview
- Partitioning points by their group-membership collections reduces the problem to Γ = 1; the union of the resulting coresets handles the original instance.The reduction is stated to work with any coreset construction algorithm.Source: §3 · p. 7
- For Γ = 1, the construction adapts the line-based framework of, whose nearest-center assignments form contiguous intervals, a property not guaranteed under fairness constraints.The framework projects points to lines and represents contiguous sub-intervals with selected points.Source: §3 · p. 7
- Structural results restore interval structure: fair k-median clusters partition the line into 2k − 1 intervals, while each optimal fair k-means cluster is one contiguous interval.These properties allow the framework’s parameters to be adjusted to construct fair coresets.Source: §3 · p. 8
4 Coresets for fair k-median clustering
This section develops fair k-median coresets, using group-membership patterns to reduce the multiple-group case to single-group instances. It establishes a line-case construction via a structural bound on optimal assignments and extends it to higher dimensions by projecting points onto a small set of lines and combining per-line coresets.
4 Coresets for fair k-median clustering
- The fair k-median coreset has size O(Γk^2ε^-d) and is constructed in O(kε^-d+1n + T1(n)) time.Source: §4 · p. 8
- Theorem 4.2 reduces Γ distinct group-membership classes to single-group instances, producing a coreset of size Γt from a size-t single-group coreset.Source: §4 · p. 8
- Theorem 4.2 also gives a fair k-center coreset of size O(Γkε^-d+1), using Har-Peled’s result.Source: §4 · p. 9
4.1 The line case
- In O(|X|) time, Algorithm 1 constructs an ε/3-coreset; an optimal fair solution uses at most 2k −1 contiguous intervals.Source: §4.1 · pp. 9–10
4.2 Proof of Theorem 4.3.
- The proof identifies at most 3k −2 batches that cross assignment-interval boundaries or contain a projected center.Source: §4.2 · p. 12
4.3 Extending to higher dimension
- For higher dimensions, the procedure starts with a constant-factor approximate k-center set and partitions points by their nearest center, following.Source: §4.3 · p. 13
- For each center ci, an ε/(3c)-net on its unit sphere yields at most O(kε^(-d+1)) lines, and each point in Xi is projected onto its closest line around ci.The net has size O(ε^(-d+1)) per center and may be computed in O(ε^(-d+1)) time.Source: §4.3 · p. 14
- The total projection cost is at most ε·OPT/3, after which each line receives an ε/3-coreset of size O(kε^-1) using Theorem 4.3.The per-line coresets are combined to form S.Source: §4.3 · p. 14
- Theorem 4.1 gives an ε-coreset of size O(k^2ε^-d), constructed in T1(n) + O(kε^(-d+1)n) time.The runtime includes T1(n) to compute C⋆ and APX; the remaining time is for projecting points onto lines.Source: §4.3 · p. 14
- It suffices to emit rays whose total projection cost is at most ε·OPT/3, an observation used in implementations to reduce coreset size.The remark also notes that this can avoid constructing the full set of rays, though the passage does not specify the omitted construction.Source: §4.3 · p. 14
5 Coresets for fair k-means clustering
The section gives an ε-coreset construction for fair k-means, with a general size bound and a line-based approach extended to higher dimensions.
5 Coresets for fair k-means clustering
- The general construction has size O(Γk^3epsilon^(-d-1)) and runs in O(k^2epsilon^(-d+1)n + T2(n,d,k)) time.Source: §5 · p. 14
5.1 The line case
- On a line, Algorithm 2 builds an ε/3-coreset in O(|X|), using two weighted representatives per batch and exploiting contiguous optimal fair clusters.Source: §5.1 · pp. 15–16
5.2 Extending to higher dimension
- For higher dimensions, the construction combines line-based coresets to obtain an ε-coreset for fair k-means.Source: §5.2 · pp. 18–19
6 Empirical results
Applying a 0.5-coreset speeds up FairTree and FairLP across evaluated datasets, while the accuracy-size experiments show compact coresets with controlled error.
6 Empirical results
- For k-means, the implementation uses Lloyd’s heuristic and SVD to find projection lines; for k-median, it adaptively constructs an ε-net because SVD does not give the optimal line.The median implementation still uses an ε-net, with heuristics to adapt it to the dataset.Source: §6 · p. 19
- Evaluation covers Adult (~50k), Bank (~45k), Diabetes (~100k), Athlete (~200k), and Census1990 (~2.5 million records); k=3 and 500 independent (F,C) samples determine maximum empirical error, with fair k-means compared against Uni and BICO.Bank uses marital and default, Diabetes sex and age, and Athlete and Census1990 use binary sensitive types.Source: §6 · pp. 19–20
6.1 Results
- At 5% empirical error, less than 3% of each dataset suffices, yielding ~200x faster objective evaluation and 10x acceleration including construction.The optimized implementation also avoids the ε^-d coreset-size factor.Source: Table 3 · p. 20, §6.1 · p. 21
- At fixed ε, the fair k-means coreset has lower empirical error than BICO, with construction time 0.5x–2x BICO’s.Uniform sampling can be more accurate on Diabetes, but its worst-case error is unbounded in general.Source: Table 4 · p. 21, §6.1 · p. 22
- Uniform-sampling error is comparable on Diabetes but unbounded in general and unstable as ε varies; coreset construction time scales roughly linearly with coreset size.The authors characterize the construction as output-sensitive.Source: §6.1 · p. 21
- FairTree speeds up 5x–15x and FairLP 15x–30x across datasets, including coreset construction time.The reported clustering objective on the coreset is usually 0.6–1.2 times the objective without it; FairLP on Census1990 is the exception.Source: Table 5 · p. 22, §6.1 · p. 22
7 Conclusion and future work
The paper constructs dataset-size-independent ε-coresets for fair k-median and k-means with multiple, non-disjoint types. It reports smaller coresets and reduced objective-computation time, while identifying broader clustering objectives and dimension-independent sampling as future directions.
Conclusion
- The proposed ε-coresets are independent of the full dataset size and support fair k-median and k-means with multiple, non-disjoint types.The fair k-median construction is the first known coreset construction to the authors’ knowledge; the k-means construction improves the prior coreset size and extends it to multiple non-disjoint types.Source: §7 · p. 22
- The empirical results show that the coresets are much smaller than the full dataset and reduce the running time of computing the fair clustering objective.The supplied conclusion states these outcomes but gives no numerical values.Source: §7 · pp. 22–23
Future work
- Future work includes sampling-based fair coresets whose size does not depend exponentially on dimension d, and coresets for general fair (k, z)-clustering beyond k-median, k-means, and k-center.Source: §7 · p. 23
A Other Empirical Results
The appendix reports experiments using binary sensitive types, both without normalization and with each dimension normalized to [0, 1].
Other Empirical Results
- Experiments cover binary sensitive types on unnormalized data and data with each dimension scaled to [0, 1].Source: A Other Empirical Results · p. 26
A.1 Results: with a binary type
For binary sensitive types, the experiments compare the coreset methods on Adult, Diabetes, and Bank; Uni does not achieve smaller empirical errors than the authors’ method, including on Diabetes.
Results: with a binary type
- Uni does not achieve smaller empirical errors than the authors’ method, including on Diabetes, in the binary-type experiments.The authors suggest that more types may partition the data better, allowing Uni to perform better than in the binary-type case.Source: §A.1 · p. 26
A.2 Results: with normalization
With normalized features, coreset error and size can increase substantially, and the relative performance of the methods varies by dataset and ε. The authors relate some of these differences to the geometry of the normalized data and to their algorithm’s projection step.
Results: with normalization
- At ε = 10% on Adult, normalization makes empirical error 2x and coreset size 20x those without normalization for both fair k-median and k-means.Source: §A.2 · p. 26
- For normalized Adult and Bank, the authors’ empirical error is smaller than BICO’s when ε > 20%, but larger when ε ≤ 20%.They suggest their algorithm may not capture normalized-data patterns, with its ray-emission and projection-cost step becoming a bottleneck at small ε.Source: §A.2 · p. 26
- On normalized Diabetes data, Uni may sometimes have lower empirical error; the authors suggest near-spherical data can favor uniform sampling over methods that include an ε-net on the sphere.The authors explain that normalized feature vectors tend to have similar norms and distribute around a hyper-sphere.Source: §A.2 · p. 26
- The authors expect their ray-based approach to perform better when data cluster around a few lines, rather than around a hyper-sphere.Source: §A.2 · p. 27