Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on the socially fair k-clustering problem. The problem is well-motivated and considers a fair version of the three important and interesting clustering problems, i.e., k-median, k-means and k-center. The authors present four results:

1- A bi-criteria $(9.9)^p$-approximation algorithm that opens (k+m) centers.
2- A $(9.9)^p$-approximation algorithm with running time $O(n^{2^{O(p)} m^2})$.
3- A $(30)^p$-approximation algorithm with running time $k^m poly(n)$.
4- Empirical comparison of their algorithm with the baselines.

strength_and_weaknesses: The main result of this paper is interesting and although some ideas are not novel, they are used in a nice way. It is not clear to me the improvement that we are getting with respect to the previous work. With respect to the number of centers opened, the previous work opens a factor $(1+\epsilon)$ more but this work opens an additive $m$ more centers, this can be more or less depending on the setting, but assuming that $m$ is significantly lower that $k$ makes sense to me. Which means that the result can be considered stronger with respect to the number of centers it opens. From the approximation point of view, it is not clear to me which work is better. What is the hidden factor in the approximation guarantee of Abbasi et al?

The ideas in the second and third results are also interesting and the sparsification is nice. I do not think these results are as strong as the main result but definitely a good additional result.

The main weakness of this paper is the experiments, the main concern being the size of the datasets. The size of the considered datasets are rather small and in some cases the algorithm is slower than the baseline. Is it possible to run the bi-critria algorithm of larger datasets, say 100K points or more? The cost improvement over the baselines are significant and interesting. I think it helps to add the exact number of the centers opened by each algorithm in the main body of the paper (it can be added to the same plot as cost as well). 

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and the novelty is not impressive but good.
summary_of_the_review: The algorithm and theoretical results in good, but there is a concern regarding the performance of the algorithm in larger datasets.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The problem considered is a “socially fair” variant of (l_p,k)-clustering algorithm. Specifically, the goal is to compute k points, given N points grouped into m classes such that the max weighted sum (for a given weight vector) of L_p metric distances of each group  is minimized over all groups. The central result is a bi-approximation algorithm for this problem where a const^p approximation guarantee is achieved at the expense of m additional centers. 

The key prior results for this problem include a:

1.	Const^p*log m approximation guarantee (Makarichev and Vakilian), with a matching lower bound result (under a complexity assumption)
2.	Biapproximation algorithm with 2^O(p)/epsilon approximation guarantee but using k/(1-epsilon) centers.

The current work improves the second result in the case where m << k.

Further, using sparsification techniques developed by Li and Svenson, they show that the additional centers can be removed at the expense of a quasi-poly time.

strength_and_weaknesses: The bi-approximation result is based on an iterative rounding technique developed by Krishnaswamy et al. Over the iterations, the LP is modified by changing relevant constraints and finally they obtain an LP that is shown to be an intersection of a matroid polytope and m affine spaces. Thanks to a classic result by Grandoni, this implies that the optimal solution for this LP has a support size k +m. Simply rounding these positive fractional variables yields a solution of size k+m centers. 

This method seems to be essentially a combination of existing techniques/results, and therefore I would really appreciate the distinctions/comparisons between the current approach and that of Krishnaswamy et al. If it’s just applying the techniques known techniques to a slight generalization – the result would be rather incremental in my opinion.

The sparsification appears to need some careful enumeration but I am not able to judge the importance of the result. 

clarity,_quality,_novelty_and_reproducibility: I think the paper is quite well written. In general it does a good job covering the related work. The novelty is unclear especially in the first key result on the bi-approximation. I am not quite familiar with the Krishnaswamy et al. paper but from what I read the current result seems incremental w.r.t the former. 
summary_of_the_review: Overall, I think while the bi-approximation guarantee result is interesting, the techniques seem to be incremental. On the other hand, the sparsification result is perhaps of some mathematically more interest, but the result may be somewhat pedantic and unimportant.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies approximation algorithms for the socially fair clustering problem. In the socially fair clustering problem, the input is a metric space, n data points, m groups of the n points whose union is n but may not be disjoint, and an integer k, the goal is to find a set of k center points C from the metric space, such that the maximum (\ell_p, k)-clustering cost among all groups, is minimized. Here, the (\ell_p, k)-clustering cost is the sum of p-th power of distances from every data point to a center C.

The paper focuses on the case when m is small. In particular, it gives two O(1)-approx algorithms, one runs in poly(nkm)-time but returns k + m centers, and the other returns exactly k centers but runs in (nk)^{poly(m)} time (or poly(n) k^m for a slightly worse constant ratio). Experiments have been conducted to compare the empirical performance of the proposed algorithms to recent works. The main observation is that the proposed algorithms generally have a better ratio, this is especially true when the number of clusters k is large.
strength_and_weaknesses: # Strength:

This small-m-O(1)-approx regime seems to be new, since previous results either violate the number of centers k by a multiplicative factor (which may be much larger than m when m is small), or is super-constant approximation. The results are obtained using LP-rounding techniques that were mostly developed in previous works for related problems, but I find the adoption of them nontrivial.

# Weakness:

The algorithms do not seem to scale on larger data sets, thus is not quite practical. For instance, even with only 200 - 500 samples, the running time is already tens - hundreds of seconds (as reported in Section E.4). Also, the current baselines are mostly previous approximation algorithms. What about considering some naive baselines? For instance, what if one uses CPLEX to solve the integer program exactly, is the running time indeed very much worse? For vanilla k-clustering, often sub-sampling based preprocessing can applied, so I’m wondering what about first doing a uniform sample of the points, and then apply all these algorithms only on the sample to obtain a set of centers?
clarity,_quality,_novelty_and_reproducibility: # Clarify
The context, key assumptions are overall well-discussed. The presentation is clear, and the use of figures and tables help the presentation a lot. However, I have some detailed comments:

1. In the second paragraph, "the facility location problem" is mentioned. I think there is a unique special problem called THE facility location problem, while what you discuss later is not this problem but clustering problems. Please change for clarify.

2. page 2, "factor-constant-factor" is a typo

3. Some of the phenomenons found in the experiment are not explained. For instance, why it is the case that your algorithm performs better when k is larger? I also observe in Section E.4 that the running time is also smaller when k is larger, which is counter-intuitive since even evaluating the cost of a center set for larger k requires more time. Also, in E.2, you mentioned that the performance of the algorithm is not very sensitive to \lambda - can you justify if this might be something likely to happen in general, or because of certain property of the data set?


# Quality
The technical part is sound, and the experiment seems to be comprehensive. The main weakness is the choice of baseline does not include naive algorithms, which is mentioned int he "strength and weakness" part.


# Originality

the techniques are mostly based on previous works, but the adoption to this paper seems nontrivial. The idea of considering small-m regime seems to be new, but I also find the assumption of small m not very well justified in the paper.
summary_of_the_review: The theory part of the paper is interesting, but I recommend a weak reject overall since the impractical nature of this algorithmic work makes it less relevant to the audience of ICLR.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper considers the increasingly important notion of demographic fairness in a general clustering context, where we need to open k “facilities” (cluster centers) in order to minimize the ell_p norm of the distances to the cluster center for each of the points in the data-set (or the p’th power of the ell_p norm). The added fairness ingredient is that we are given some demographic groups, and we aim to minimize the maximum cost (total distance traveled, or its ell_p norm to the power of p) over all of the given groups. I believe this sort of algorithmic research is important in fair implementations of ML. 

The main concerns raised were novelty and run time: since more papers are being written in this general area in AI/ML, the acceptance threshold for papers in this sub-field has gone up significantly. As the authors point out, the latter is due to the time taken to solve a large linear program (LP). While this is understandable (and while it is also true that faster approaches do not have good theoretical guarantees like in this work), the authors could perhaps work on combinatorial approximation schemes for such LPs---for instance, perhaps using multiplicative weights update, as has been done recently for many classes of LPs---and also see if the LP itself can get sparsified rigorously. 

justification_for_why_not_higher_score: Novelty and scalability issues: this genre of research is important and has been attracting a good number of papers, hence the acceptance threshold for such research has gone up.
Decision: Reject