Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the fair clustering (with balanced clusters requirement) and the goal of authors is to achieve the “fairest” possible clustering achievable with cost at most U. The idea here is that we know that PoF can be unbounded, and it is unrealistic to assume that in practical applications we cannot sacrifice the clustering quality for fairness with no limit.
An important component is how to measure the amount of unfairness and then the goal is to minimize it while not violating the upper bound on affordable clustering cost. They have defined three notions called GROUP-UTILITARIAN, GROUP-EGALITARIAN and GROUP-LEXIMIN. Basically, in fair clustering, for each color h, we are given lower and upper bounds $\alpha_h, \beta_h$ and the goal is to guarantee that in each cluster the number of point from color h is at least $\alpha_h \cdot  |C_i|$ and is at most $\beta_h \cdot |C_i|$. Now, the amount of unfairness is defined by a new set of parameters $\Delta_h$ such that instead of satisfying the fair clustering requirements exactly, we have that the number of points from color h is at least $(\alpha_h - \Delta_h) \cdot  |C_i|$ and is at most $(\beta_h + \Delta_h) \cdot |C_i|$. The authors consider $\min \max_h \Delta_h$ and $\min sum_h \Delta_h$ objectives (GROUP-LEXIMIN is a lexicographical minimizing of \Delta_h: the top priority is to minimize the min value, then among those with the same min value, minimize the second min value and so on).

main_review: The theoretical guarantees of the paper are for both fair clustering with bounded cost and the fair assignment under bounded cost (i.e., a set of centers is given, and the goal is to find the best possible fair assignment under bounded cost). Both problems are NP-hard. Further they showed that the violation (which is a function of $\Delta_h$) cannot be set to arbitrarily small values (the values depend on the size of smallest non-empty cluster across all clusterings of bounded cost); otherwise, the problem becomes NP-hard (the actual bounds are given in Thm 5.3). 
On the algorithmic side, they provide a (semi-)bicriteria approximation for fair clustering under bounded cost: the algorithm finds a solution of cost at most $(2+ \gamma) OPT$ (where $\gamma$ is the approximation factor for the used color-blind clustering algorithm) with almost additive approximation optimal w.r.t. $(2+ \gamma) OPT$ and the bounds given in Thm 5.3. The approach is via a reduction from the fair algorithms under bounded cost.

**Questions for Authors**
1)	Do you have any evidence showing the bound of Thm 6.1 is reasonable? L(U’) can be arbitrarily smaller than L(U). Do you have any evidence that such dependence is required? I would like to get a sense how tights your approach is.

**Minor Comments**
1.	In abstract: “price of fairness,” -> “price of fairness”,
2.	Theorem 6.1 is not mentioning the exponential dependence on \eps in the running time. Alternatively, you can mention the number of colors is a constant.
3.	Line 198. Providing 159 without mentioning the other parameter in the dataset (e.g., number of points, centers) may not be very helpful.
4.	Line 203. A space is needed after GROUP-UTILITARIAN,
5.	Line 225. Netwok -> network
6.	Line 340 and 341 does not seem very informative. Also reference [8] does not provide any such evidence for fair clustering. Maybe you meant the result of [10]?
7.	In section 9.3, it is not clear how you are computing L(U)? Ho do you consider all possible clustering of certain bound (even approximately)? Would be helpful to elaborate more here.
8.	In the second line of the equation after line 732, \phi(i) -> \phi(j)
9.	Rephrase line 735
10.	Line 750. Isn’t the proof of Theorem 6.3 trivial? Given that we need to satisfy both upper and lower bound? In fact, why is it important to know the non-convexity for the case we are ignoring the upper bounds? 
11.	Line 822. theorem Theorem -> Theorem
12.	Line 905. Rephrase and fix the typo
13.	Line 911. We havewe no -> we have no

The problem statement and the techniques used in the paper are interesting. The drawback is that it is not clear why the result cannot be (easily) improved. Authors’ feedback on this point can be very helpful for the decision process.

=====================================================

I would like to thank the authors for their helpful response. I will keep my score for this paper.
limitations_and_societal_impact: The paper works on theoretical foundation of fairness and I do not see any immediate potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: EDIT: I increased my score following the discussions and rebuttal.
The main question in the paper is how can we cluster data so that we optimize for some fairness desiderata. In other words, if we have a target for the amount of clustering cost we are aiming for, how can we find the most fair solution, subject to that cost constraints? Put differently, the authors address the problem of minimizing the amount of "unfairness" subject to the clustering cost being below a certain threshold. The two desiderata put forth by the authors in terms of fairness have to do with "group utilitarian" objective and with "group egalitarian" (they also further study a generalization called "group leximin" objective. The authors give both positive results and some impossibility results. Finally, they run some experiments to validate their findings.

These three objectives are desiderata that have been studied in the past. Briefly, the group utilitarian objective minimizes the sum of all fairness violations, whereas the group egalitarian objective minimizes the maximum fairness violation. Going a step further, the leximin (LM) objective minimizes the maximum fairness violation first, then minimizes the second worst etc. 

One of the hardness results they prove is that for all three objectives, both fairly clustering and fairly assigning points to fixed centers is NP-hard.

On the positive side, they give an approximation algorithm that yields a (2+a)U-approximation where U is an exogenous parameter that is the upper bound on the clustering cost and a is the approximation ratio of a color-blind clustering algorithm. The algorithms presented for the different objectives depend on some assumptions about the sizes of the clusters. The idea behind the algorithms is to first run a color blind clustering algorithm to select centers, followed by an LP to get a fair assignment and a flow computation.

The authors perform some computational experiments on the adult and the census data sets to evaluate how their fairness guarantees look like.

main_review: The reviewer believes the paper studies an interesting problem which has received a lot of attention recently by both theory and ML communities however the execution brought forth by the authors is done in a manner that has several caveats.

The reviewer overall is not convinced that the problem formulation itself yields interesting insights and it does feel a bit artificial. There are many prior works on fair clustering recently and to some extent the paper doesn't adequatly compare results: A paper here "Clustering without over-representation paper" (Ahmadian et al.) seems to be relevant and one natural question is, whether changing the representation parameters until a solution returned has value smaller than U would yield comparable results?  Could the authors provide experimental evidence to show their method significantly outperfoms prior methods?

Regarding other weaknesses, the paper has an exogenous parameter U for the bound in the clustering cost which is not clear how to get it in practice, and also the Assumption 6.1 makes their main result weaker than one would expect especially in the presence of outliers or misreported values. Can the Assumption 6.1 be removed or will the proof break down completely? What about the analysis of the LP then?

Overall, the theory here could be strong if the final theorems were cleaner but this is not the case. The paper has interesting directions and is currently a collection of small results but further work is needed to have a solid Neurips contribution.
limitations_and_societal_impact: none
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies a new variant of fair clustering for different fairness (group utilitarian, group egalitarian, group leximen) and clustering objectives(k-center, k-median, k-means). The main approach is to optimize the fairness objective under the constraint that the clustering cost are bounded by some value U. The main result can be thought of as a bi-criteria approximation: If we allow that U is violated by a factor of (2+alpha) (where alpha is the approximation ratio of some clustering algorithm for the given objective) then we can get an additive approximation on the fairness objective. 

In addition to this algorithmic upper bound, the authors also give a number of complexity theory lower bounds for different variants of the problem. 

The authors also provide a proof-of-concept study of their algorithm.


main_review: The newly introduced variant of fair clustering is interesting and the proposed solutions are non-trivial. They provide a nice new approach to the fair clustering literature.

I would have loved to see some more details of the proof of Theorem 6.2 (maybe instead of some of the lower bounds). It seems that this is a central step in the paper and it would be helpful to have additional details in the main body of the paper. Also, how does this theorem relate to earlier fair clustering algorithms (for example, for 2 colors how does it relate to fairlets and similar ideas)?

In the experimental section there is no comparison to earlier work. I understand that the main results of the paper are the algorithmic/theoretical results and that the problem is somewhat different from the standard problem formulation, but I would still appreciate some comparision.

Overall, I like the paper and I recommend to accept it.

-----------------------------------------------------------------------
Thank you for your feedback. I will keep my score.



limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper derives the theoretical bound of fair clustering based on porotype based algorithms. Generally speaking, the authors expect to minimize the unfairness under the given upper bound. In this paper, the authors consider two types of fairness and two fairness clustering setting. Based on this, the authors derive the upper bound of the unfairness and design the corresponding algorithm. The major contributions of this paper lie in theoretical analysis. 


main_review: Here are my detailed comments.

1. The authors expect to provide a comprehensive understanding on the research problem with different objective functions and different porotype clustering algorithms. In the current version, there are two research problems and three objective functions. The authors elaborate the whole paper in a parallel way. Unfortunately, it makes this paper messy and difficult to follow. I suggest the authors to only focus on the simplest scenario, and first provide the complete procedure from problem definition to bound cost to algorithm. Then, other scenarios can be delivered as extensions. 
2. Figure 1 is not easy to understand. I read this part for more than three times. Maybe only the bottom example?
3. I was wondering for several days whether the problem addressed in this paper is meaningful. In Paper "Fair Algorithms for Clustering", they minimize the clustering cost with fairness constraints, while the authors of this paper formulate the problem to minimize the unfairness under the clustering cost. It seems that these two settings should achieve the similar results. However, the problem in this paper might impractical and even inflexible. I have two points on this.  (a) cluster analysis is an unsupervised task, the clustering cost is not a focused measurement due to its unachievable OPT; therefore it is difficult to set the upper bound. The authors introduce the concept of PoF, where k-means++ is used as a proxy of the lowest possible value of the clustering cost. What does PoF=1.1 mean in practical? (b) Although the authors introduce \delta_h to relax the original optimization problems in Eq. (1) or (2), there still exists the empty solution. In light of this, I would like to support the setting that minimizes the clustering cost with fairness constraints, rather than the one of this paper. For this point, I need to discuss with other reviewers.
4. The presentation is a little messy. Theorem 6.1 talks about Algorithm 1, while Algorithm 1 comes behind Theorem 6.1.
5. In Line 197, what does the "small" mean?
6. I am confused on ALG-FCBC. According to its formulation, the set of centers S are not fixed, which should be optimized during the clustering procedure. However, ALG-FCBC first calls a color-blind clustering algorithm to obtain S, and keeps S unchanged.
7. The essence of ALG-FABC is multiple LPs. In my eyes, the solution is almost brute-force. The authors do not provide the time complexity analysis. 
8. This paper focuses on theoretical analysis. Moreover, these theorems cannot be verified by experiments. The experimental section can be removed. Instead, a conclusive section is needed.

With the below discussion with authors, my major concern on problem setting is addressed and I would like to increase my score. 
limitations_and_societal_impact: In the checklist, the authors confirm that they include the limitations and societal impact in the main paper. I do not find them in both main paper and supplementary document.
review_title: null

Meta-review: The paper proposes new formulations of (and algorithms for) fair clustering. Instead of minimizing clustering cost under fairness constraints, the paper considers a dual problem where the clustering cost is given and the goal is to maximize fairness. 

The reviewers found the formulation of fairness to be interesting and potentially leading to a follow-up line of research. Almost all reviewers recommended acceptance, sometimes strongly so.  At the same time, there was a concern that the approximation factors depend inversely on the cluster size, so they could be large. However, overall, the reviewers felt that the positives outweigh the negatives.

Decision: Accept (Poster)