acceptodds
Withdrawn from ICLR 2027

Proportionally Fair Clustering of Distributions

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Choosing cluster centers to minimize average distance from data points can leave a substantial part of the training data poorly represented. Proportional fairness asks that no group of data points large enough to deserve a center to represent them unanimously prefer a new center. Our main contribution is to expand this framework from clustering a finite set of data points to clustering a given probability distribution. A natural question is whether every distribution admits a proportionally fair clustering once the number of centers is large enough; we answer this negatively. We also identify broad families of distributions which admit a proportionally fair clustering when the number of centers is sufficiently large, and those that admit one for any number of centers. We also establish deep connections between proportional fairness for a distribution and that for a finite set of i.i.d. samples drawn from the distribution, allowing us to efficiently transfer approximation guarantees (and nonexistence results) known for the finite sample case.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
clustering, proportional fairness, distributions, measures

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_M1SkOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper extends proportionally fair clustering from finite datasets to probability distributions, investigating the existence and generalization properties of proportionally fair clusterings. The authors establish connections between finite-sample and distributional fairness, deriving both upper and lower bounds on the sample complexity required to transfer fairness guarantees. They further construct a distribution for which exact proportional fairness fails at infinitely many cluster budgets, while proving eventual existence for several broad distribution families, including absolutely continuous distributions in dimensions up to five. Additional results establish exact-core existence for specific distributions and cluster budgets. Overall, the paper provides a systematic theoretical investigation of proportional fairness in distributional clustering.

Critical strengths
  1. The paper investigates an interesting extension of proportional fairness from finite datasets to underlying probability distributions. This perspective is relevant to machine learning, where clustering algorithms are typically developed using finite samples but are expected to generalize to unseen data.
  2. The paper provides a rich set of theoretical results, including sample complexity upper and lower bounds, nonexistence constructions, and existence guarantees for several distribution families. These results offer valuable insights into the fundamental properties of proportionally fair clustering and establish meaningful connections between statistical learning and geometric analysis.
Critical weaknesses
  1. Although the paper establishes exact-core existence for several distribution families, some results are primarily existential and do not provide explicit bounds on the required number of centers or efficient algorithms for obtaining them. This limits their immediate applicability to practical clustering problems.
  2. everal theoretical guarantees, particularly those concerning four- and five-dimensional distributions and specific disk configurations, depend on computer-assisted proofs. While this approach is reasonable, the reproducibility and accessibility of the corresponding verification procedures are important for establishing confidence in these results.
Questions for authors
  1. Theorem 6 establishes exact-core existence for sufficiently large cluster budgets under certain distributional assumptions. Could the authors further discuss whether explicit bounds on the required number of centers can be obtained for some common distribution families, or whether the existence arguments could lead to efficient constructive algorithms?
  2. Some important results in Appendix E.3 and F.2 rely on exact computational verification. Could the authors clarify how these results can be independently reproduced, including the availability of verification code, computational certificates, and the corresponding execution procedures?
  3. The paper focuses on proportional fairness, whereas a substantial body of fair clustering research considers group fairness defined by sensitive attributes. Although this distinction is briefly discussed in Appendix I, a more explicit conceptual comparison in the main text would help readers better understand the differences, relationships, and potential complementarity between these fairness notions. The authors may consider discussing additional representative studies on sensitive-attribute-based fair clustering, such as [1–3], to better contextualize the contribution of this work.

[1] Zhou, P., Li, R., & Du, L. (2024). Fair Kernel K-Means: from Single Kernel to Multiple Kernel. Advances in Neural Information Processing Systems (NeurIPS), 37, 99686–99714.

[2] Kjærsgaard, R. D., Parviainen, P., Saurabh, S., Kundu, M., & Clemmensen, L. (2024). Fair Soft Clustering. Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), Proceedings of Machine Learning Research, 238, 1270–1278.

[3] Park, J., Kim, K., Lee, J., & Kim, Y. (2026). Fair Model-based Clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 40(29), 24773–24781.

Reviewer_jwDjOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
1
Soundness
2
Read review
Paper summary

The paper extends the notion of proportional fairness in clustering from a finite set of data points to probability distributions. It studies which results transfer from the finite setting and investigates exact core existence for sufficiently large kk and for every kk. The authors study these questions for different classes of distributions.

Critical strengths

Extending proportional fairness to distributions is a very interesting direction, both from an application and a theoretical viewpoint. The questions asked are relevant and the results appear potentially significant.

Critical weaknesses

My main concern is the presentation. The paper reads like a draft and is often difficult to follow. In particular, the motivation and intuition behind several important results are insufficiently explained.

Moreover, many distribution-related concepts are not defined or introduced almost no explanation (e.g. Borel probability measures, absolute continuity, Lebesgue measure, compact support, VC dimension). While many readers are familiar with these, the paper is not sufficiently self-contained without them. Example 1 feels somewhat disconnected from the main results. The proof of Lemma 1 invokes Fubini's theorem (p. 4, l. 193) without explaining its application. Several important theorems lack sufficient intuition. Theorem 4 is introduced with little context, and Theorem 5 seems particularly central but its construction is barely explained. Theorem 7 mostly refers to appendix lemmas. More generally, there are too many references to results in the appendix without explaining the underlying ideas in the main text.

Generally, the paper would benefit from extended motivation. I also feel that the results are not sufficiently discussed. Without more interpretation, some of the results fall somewhat flat. What do they imply and what are their limitations?

Minor comments:

  • Theorem 1 uses CC without explicitly introducing it and the subsequent proof sketch is rather unclear.
  • The quota convention should be stated consistently. The introduction (p. 2 l. 58) says at least βn/k\beta n/k agents, whereas Remark 1 (p. 3 l. 146) requires strictly more than βn/k\beta n/k agents (⌊βn/k⌋+1\lfloor \beta n/k\rfloor+1).
  • Note that Definition 2 only considers exact deviations. It would be helpful to explain why this quantity is introduced and why it does not incorporate the approximation factor α\alpha.
  • Calling a clustering an (α,β)(\alpha,\beta)-core is somewhat unusual, I would suggest saying that CC is in the (α,β)(\alpha,\beta)-core.
  • Figure 2 is not very informative. A figure illustrating the counterexample in Theorem 5 would be more useful.
  • There are many references to lemmas in the appendix without much explanation (e.g. proof of Theorem 7, p. 7 l. 370).
  • The constants bdb_d and their role could be explained more clearly.
  • The additional Gaussian claims attributed to GPT-6 Astra (p. 8 l. 382) are stated without proofs.
  • Presentation issues: inconsistent notation (dd vs. DD on p. 6), some typos (e.g. „we adresses“ p.1 l.49), "r replaced" p. 6 l. 283), different colored text (which seems like late additions/comments) and references that show up as ?? (p.8 l.408)
  • Section titles such as "Eventual Core" and "Always Core" could be more descriptive.
Questions for authors

Q0: What do the results imply and what are their limitations? Q1: For the nonexistence examples, what approximation factors between 1 and 2 might be possible? Q2: What prevents extending Theorem 6 to dimensions greater than 5? Is this a limitation of the proof technique? Q3: Can anything be said about the threshold K(μ)K(\mu), beyond its existence?

Reviewer_5eguOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper extends the framework of proportional fairness in centroid-based clustering towards probability distributions. It extends existing results to distributions on a proper metric space. For exact cores, the paper shows a counterexample for which no exact core exists and additionally claims to identify families that have exact cores for every k.

Critical strengths

S1: The description provides some context to the results shown and identifies open questions. S2: The results are precise and cover both existence and non-existence of approximate and exact cores.

Critical weaknesses

W1 (presentation): The paper is hard to parse, and fails to provide a clear description of the problems studied and their relationships. Likewise, the discussion is short and provides only limited insights into the observed theoretical properties.

W2 (motivation): While the paper correctly identifies that ML goals often involve “low true risk”, the transition from the finite city example to “training data drawn from D” feels abstract. Since clustering is in practice computed for a fixed set of data points, it is unclear to me how the population view is the natural choice, and the introduction does not motivate this enough.

W3 (sufficiently large k): The main exact-core result for broad families holds for “sufficiently large k”, however, this is not defined or bounded in the paper, and it remains open how k is to be selected.

W4 (overstated generality): The abstract claims to identify “broad families of distributions [...] that admit one for any number of centers”, which is stronger than what the discussion supports and overemphasizes the generality of the provided findings, which are limited to distributions on a line and uniform measures on rectangles and disks in the paper. Please align the abstract and introduction accordingly.

W5 (conjecture 1): There is partial evidence for Conjecture 1 (cores for all Gaussians), but it remains unproven, and additional GPT-6 Astra proofs for planar Gaussians are omitted.

W6 (AI overuse): The paper suffers from excessive use of AI, both in writing and in the results obtained, where it is unclear what to learn from e.g. Lemma 2 “The last two inequalities are computer-assisted.”

Minor comments: • There is a missing reference on Page 8, line 408. • The colored sentences and headers feel random.

Questions for authors

Q1: Can you explain what the population-level view offers? Q2: Can you provide a bound or a measure to determine k?

Comments on the paper

1 comment
Area_Chair_ktLyOpenReview ↗

Notification for reminding the discussion deadline.

Dear authors and reviewers,

Since there is about one day left in the discussion period, I would appreciate it if you could respond to the review and revise your manuscript.

If the authors respond to the review, I would also appreciate it if the reviewers could reply as soon as possible.

Thank you.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.