Relative Error Fair Clustering in the Weak-Strong Oracle Model

The authors computed the fair $k$-median cost for specified centroids and fairlet decomposition, and compared fair $k$-median cost of their proposed algorithm against uniform coresets. This evaluation criteria appears suitable.

I performed a sanity check of the proofs for the following: Lemma 3.1, Lemma B.1, Lemma B.2, Lemma B.3, Claim B.5, Lemma B.4, Lemma B.6, Lemma B.7 (B.7 is a result from another paper). The following are some issues that need to be addressed:

• Lemma 3.1: This lemma states that “the algorithm converges in xxx time”. If this refers to the running time of the algorithm, it should account not only for the weak-strong model queries but also for the running time of other invoked subroutines. For example, in Line v of Algorithm 1, there is a “for” loop over $\ell \leq j^*+1$, and the algorithm invokes the Coreset-Update subroutine over each $\ell$. Should the running time include invocations? While the running time might remain unchanged after considering these subroutine calls, it could be beneficial to include this explanation in the proof for clarity.

• Lemma B.2: Line 811~812, the inequality $\tilde{d}(y,S^{pell})\geq \tilde{d}(y,c_i)\geq R$ is not explained.

• Lemma C.2 (Page 29):

-- The authors didn’t explain on $\alpha_{WC}$; it may refer to the approximation ratio of $cost(X,WC)$ regarding optimal cost $cost(X)$, and thus $\alpha_{WC}>1$. From Line 1560 to Line 1563, it follows from Equation (7), but it seems that $\alpha_{WC}<1$; while from Line 1566 to Line 1568, it seems that $\alpha_{WC}>1$. These two derivations look like a contradiction on the range of $\alpha_{WC}$.

-- The first inequality of $cost(FC,C,\Gamma)-cost(X,C,\Gamma)$ is not explained.

-- Besides, this derivation is not explained: $\sum\sum cost(T_i^{(r)},C,Γ_i^{(r)})≤cost(X,C,\Gamma)$.

• Lemma C.4: Line 1404, need to explain $p$ in the $\sigma(p,c)$. Perhaps it should be $x$, instead of $p$?

I reviewed Experiments section in the appendix. The authors conducted experiments on only two datasets, which may not be sufficient to show the advantages of their approach.

Besides, the chosen baseline might be too simple. It could be worthwhile to consider a baseline using coresets generated by Algorithm 1 without having fairness constraint. This comparison could provide a clearer understanding of the impact of including fairness constraints.

The weak-strong oracle model is motivated by the fact that modern machine learning models often use embedding functions to estimate distances for non-metric data, which can be computationally expensive, and by the applications that involve trade-offs between information accuracy and price. The concept of fair clustering arises from the need of incorporating fairness into clustering. This paper contributes to algorithms in fair clustering within weak-strong oracle model, which is a potential application direction in the filed of modern machine learning.

I did not identify any essential references that are missing from the discussion.

Not applicable

See my comments in claims and evidences.

The experiments are not detailed, as the authors conduct only a single experiment to report the relative cost difference. Additionally, the description does not clearly specify the fairness constraints.

The paper advances the theoretical understanding of the (fair) clustering problem. The presented approach is non-trivial and requires expertise in the field to develop. While the authors do a commendable job of explaining the method at a high level, I have doubts about its practical applicability to real-world datasets with millions or billions of data points. In my opinion, this work is primarily of theoretical interest.

I acknowledge that the field of (fair) clustering is vast, making it challenging to cite all relevant references. However, the authors overlook several important works in fair clustering, particularly in the area of representative fairness. Additionally, the citations primarily focus on a specific group of authors, while there are relevant contributions beyond this clique that also deserve recognition. Below, I have listed some relevant references that should be considered to provide a more comprehensive overview of prior research.

[1] Zhang, Zhen, Xiaohong Chen, Limei Liu, Jie Chen, Junyu Huang, and Qilong Feng. "Parameterized Approximation Schemes for Fair-Range Clustering." Advances in Neural Information Processing Systems 37 (2024): 60192-60211.

[2] Gadekar, Ameet, Aristides Gionis, and Suhas Thejaswi. "Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights." In proceedings of the ACM Web Conference, 2025.

[3] Thejaswi, Suhas, Ameet Gadekar, Bruno Ordozgoiti, and Michal Osadnik. "Clustering with fair-center representation: Parameterized approximation algorithms and heuristics." In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1749-1759. 2022.

[4] Thejaswi, Suhas, Bruno Ordozgoiti, and Aristides Gionis. "Diversity-aware k-median: Clustering with fair center representation." In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, pp. 765-780. Springer, 2021.

[5] Thejaswi, Suhas, Ameet Gadekar, Bruno Ordozgoiti, and Aristides Gionis. "Diversity-aware clustering: Computational Complexity and Approximation Algorithms." arXiv preprint arXiv:2401.05502 (2024).

[6] Chen, Xianrun, Sai Ji, Chenchen Wu, Yicheng Xu, and Yang Yang. "An approximation algorithm for diversity-aware fair k-supplier problem." Theoretical Computer Science 983 (2024): 114305.

The experimentation section of the paper is rather weak. There is just a baseline comparison with uniform sampling. It is already fairly well known that uniform sampling is unable to give strong relative error guarantees. The authors must have compared to other sampling techniques.

There are not many proofs in the main body of the paper. I had a high-level look at the supplementary material for the proofs. They appear ok.

See the section on methods and evaluation. This is mostly a theoretical paper with just a very small set of experiments. There should have been more comparisons with other sampling techniques.

The paper proposes coresets for proportionality based fair version of clustering problem. To the best of my knowledge there are some results on coresets for fair clustering and similar ideas like ring based coresets are used. however, I am not sure if there has been a use of a distance oracle model in the existing literature.

This is my main issue with this paper. The paper claims ". Prior to Theorem 2, no fair k-median coreset with non-trivial approximation guarantees or coreset size was known."

There are at least 3 papers which discuss coresets for fair clustering

1. Fair Coresets and Streaming Algorithms for Fair k-means, Schmidt et al.

2. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications, Bandyapadhyay et al.

3. Coresets for clustering with fairness constraints., Huang et al.

4. and 3) are cited but not discussed. I am not sure how the authors can make the above claim when nontrivial coresets do exist. It is not at all clear to me how their coreset results compare/contrast with existing results. This is a big weakness. I believe there should not only be a detailed discussion in terms of quality of coresets, techniques etc with these papers but also, they should be compared with in the experiments section too. These papers have similar techniques for coreset construction (though not in the oracle model). Without both theoretical and experimental comparisons, I am not convinced that this paper has novelty.